# list

## NAME



           LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_HEAD,
           LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER,
           LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE -
           implementation of a doubly linked list
    


## LIBRARY



           Standard C library (_libc_ , _-lc_)
    


## SYNOPSIS



           **#include <sys/queue.h>**
    
           **LIST_ENTRY(TYPE);**
    
           **LIST_HEAD(HEADNAME, TYPE);**
           **LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD** _head_**);**
           **void LIST_INIT(LIST_HEAD ***_head_**);**
    
           **int LIST_EMPTY(LIST_HEAD ***_head_**);**
    
           **void LIST_INSERT_HEAD(LIST_HEAD ***_head_**,**
                                   **struct TYPE ***_elm_**, LIST_ENTRY** _NAME_**);**
           **void LIST_INSERT_BEFORE(struct TYPE ***_listelm_**,**
                                   **struct TYPE ***_elm_**, LIST_ENTRY** _NAME_**);**
           **void LIST_INSERT_AFTER(struct TYPE ***_listelm_**,**
                                   **struct TYPE ***_elm_**, LIST_ENTRY** _NAME_**);**
    
           **struct TYPE *LIST_FIRST(LIST_HEAD ***_head_**);**
           **struct TYPE *LIST_NEXT(struct TYPE ***_elm_**, LIST_ENTRY** _NAME_**);**
    
           **LIST_FOREACH(struct TYPE ***_var_**, LIST_HEAD ***_head_**, LIST_ENTRY** _NAME_**);**
    
           **void LIST_REMOVE(struct TYPE ***_elm_**, LIST_ENTRY** _NAME_**);**
    


## DESCRIPTION



           These macros define and operate on doubly linked lists.
    
           In the macro definitions, _TYPE_ is the name of a user-defined
           structure, that must contain a field of type _LIST_ENTRY_ , named
           _NAME_.  The argument _HEADNAME_ is the name of a user-defined
           structure that must be declared using the macro **LIST_HEAD**().
    
       **Creation**
           A list is headed by a structure defined by the **LIST_HEAD**() macro.
           This structure contains a single pointer to the first element on
           the list.  The elements are doubly linked so that an arbitrary
           element can be removed without traversing the list.  New elements
           can be added to the list after an existing element, before an
           existing element, or at the head of the list.  A _LIST_HEAD_
           structure is declared as follows:
    
               LIST_HEAD(HEADNAME, TYPE) head;
    
           where _struct HEADNAME_ is the structure to be defined, and _struct_
           _TYPE_ is the type of the elements to be linked into the list.  A
           pointer to the head of the list can later be declared as:
    
               struct HEADNAME *headp;
    
           (The names _head_ and _headp_ are user selectable.)
    
           **LIST_ENTRY**() declares a structure that connects the elements in
           the list.
    
           **LIST_HEAD_INITIALIZER**() evaluates to an initializer for the list
           _head_.
    
           **LIST_INIT**() initializes the list referenced by _head_.
    
           **LIST_EMPTY**() evaluates to true if there are no elements in the
           list.
    
       **Insertion**
           **LIST_INSERT_HEAD**() inserts the new element _elm_ at the head of the
           list.
    
           **LIST_INSERT_BEFORE**() inserts the new element _elm_ before the
           element _listelm_.
    
           **LIST_INSERT_AFTER**() inserts the new element _elm_ after the element
           _listelm_.
    
       **Traversal**
           **LIST_FIRST**() returns the first element in the list, or NULL if the
           list is empty.
    
           **LIST_NEXT**() returns the next element in the list, or NULL if this
           is the last.
    
           **LIST_FOREACH**() traverses the list referenced by _head_ in the
           forward direction, assigning each element in turn to _var_.
    
       **Removal**
           **LIST_REMOVE**() removes the element _elm_ from the list.
    


## RETURN VALUE



           **LIST_EMPTY**() returns nonzero if the list is empty, and zero if the
           list contains at least one entry.
    
           **LIST_FIRST**(), and **LIST_NEXT**() return a pointer to the first or
           next _TYPE_ structure, respectively.
    
           **LIST_HEAD_INITIALIZER**() returns an initializer that can be
           assigned to the list _head_.
    


## STANDARDS



           BSD.
    


## BUGS



           **LIST_FOREACH**() doesn't allow _var_ to be removed or freed within the
           loop, as it would interfere with the traversal.
           **LIST_FOREACH_SAFE**(), which is present on the BSDs but is not
           present in glibc, fixes this limitation by allowing _var_ to safely
           be removed from the list and freed from within the loop without
           interfering with the traversal.
    


## EXAMPLES



           #include <stddef.h>
           #include <stdio.h>
           #include <stdlib.h>
           #include <sys/queue.h>
    
           struct entry {
               int data;
               LIST_ENTRY(entry) entries;              /* List */
           };
    
           LIST_HEAD(listhead, entry);
    
           int
           main(void)
           {
               struct entry *n1, *n2, *n3, *np;
               struct listhead head;                   /* List head */
               int i;
    
               LIST_INIT(&head);                       /* Initialize the list */
    
               n1 = malloc(sizeof(struct entry));      /* Insert at the head */
               LIST_INSERT_HEAD(&head, n1, entries);
    
               n2 = malloc(sizeof(struct entry));      /* Insert after */
               LIST_INSERT_AFTER(n1, n2, entries);
    
               n3 = malloc(sizeof(struct entry));      /* Insert before */
               LIST_INSERT_BEFORE(n2, n3, entries);
    
               i = 0;                                  /* Forward traversal */
               LIST_FOREACH(np, &head, entries)
                   np->data = i++;
    
               LIST_REMOVE(n2, entries);               /* Deletion */
               free(n2);
                                                       /* Forward traversal */
               LIST_FOREACH(np, &head, entries)
                   printf("%i\n", np->data);
                                                       /* List deletion */
               n1 = LIST_FIRST(&head);
               while (n1 != NULL) {
                   n2 = LIST_NEXT(n1, entries);
                   free(n1);
                   n1 = n2;
               }
               LIST_INIT(&head);
    
               exit(EXIT_SUCCESS);
           }
    


* * *