Return to lists.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

bird 1.6.3

    1: /*
    2:  *	BIRD Library -- Linked Lists
    3:  *
    4:  *	(c) 1998 Martin Mares <mj@ucw.cz>
    5:  *
    6:  *	Can be freely distributed and used under the terms of the GNU GPL.
    7:  */
    8: 
    9: /**
   10:  * DOC: Linked lists
   11:  *
   12:  * The BIRD library provides a set of functions for operating on linked
   13:  * lists. The lists are internally represented as standard doubly linked
   14:  * lists with synthetic head and tail which makes all the basic operations
   15:  * run in constant time and contain no extra end-of-list checks. Each list
   16:  * is described by a &list structure, nodes can have any format as long
   17:  * as they start with a &node structure. If you want your nodes to belong
   18:  * to multiple lists at once, you can embed multiple &node structures in them
   19:  * and use the SKIP_BACK() macro to calculate a pointer to the start of the
   20:  * structure from a &node pointer, but beware of obscurity.
   21:  *
   22:  * There also exist safe linked lists (&slist, &snode and all functions
   23:  * being prefixed with |s_|) which support asynchronous walking very
   24:  * similar to that used in the &fib structure.
   25:  */
   26: 
   27: #define _BIRD_LISTS_C_
   28: 
   29: #include "nest/bird.h"
   30: #include "lib/lists.h"
   31: 
   32: /**
   33:  * add_tail - append a node to a list
   34:  * @l: linked list
   35:  * @n: list node
   36:  *
   37:  * add_tail() takes a node @n and appends it at the end of the list @l.
   38:  */
   39: LIST_INLINE void
   40: add_tail(list *l, node *n)
   41: {
   42:   node *z = l->tail;
   43: 
   44:   n->next = &l->tail_node;
   45:   n->prev = z;
   46:   z->next = n;
   47:   l->tail = n;
   48: }
   49: 
   50: /**
   51:  * add_head - prepend a node to a list
   52:  * @l: linked list
   53:  * @n: list node
   54:  *
   55:  * add_head() takes a node @n and prepends it at the start of the list @l.
   56:  */
   57: LIST_INLINE void
   58: add_head(list *l, node *n)
   59: {
   60:   node *z = l->head;
   61: 
   62:   n->next = z;
   63:   n->prev = &l->head_node;
   64:   z->prev = n;
   65:   l->head = n;
   66: }
   67: 
   68: /**
   69:  * insert_node - insert a node to a list
   70:  * @n: a new list node
   71:  * @after: a node of a list
   72:  *
   73:  * Inserts a node @n to a linked list after an already inserted
   74:  * node @after.
   75:  */
   76: LIST_INLINE void
   77: insert_node(node *n, node *after)
   78: {
   79:   node *z = after->next;
   80: 
   81:   n->next = z;
   82:   n->prev = after;
   83:   after->next = n;
   84:   z->prev = n;
   85: }
   86: 
   87: /**
   88:  * rem_node - remove a node from a list
   89:  * @n: node to be removed
   90:  *
   91:  * Removes a node @n from the list it's linked in. Afterwards, node @n is cleared.
   92:  */
   93: LIST_INLINE void
   94: rem_node(node *n)
   95: {
   96:   node *z = n->prev;
   97:   node *x = n->next;
   98: 
   99:   z->next = x;
  100:   x->prev = z;
  101:   n->next = NULL;
  102:   n->prev = NULL;
  103: }
  104: 
  105: /**
  106:  * replace_node - replace a node in a list with another one
  107:  * @old: node to be removed
  108:  * @new: node to be inserted
  109:  *
  110:  * Replaces node @old in the list it's linked in with node @new.  Node
  111:  * @old may be a copy of the original node, which is not accessed
  112:  * through the list. The function could be called with @old == @new,
  113:  * which just fixes neighbors' pointers in the case that the node
  114:  * was reallocated.
  115:  */
  116: LIST_INLINE void
  117: replace_node(node *old, node *new)
  118: {
  119:   old->next->prev = new;
  120:   old->prev->next = new;
  121: 
  122:   new->prev = old->prev;
  123:   new->next = old->next;
  124: }
  125: 
  126: /**
  127:  * init_list - create an empty list
  128:  * @l: list
  129:  *
  130:  * init_list() takes a &list structure and initializes its
  131:  * fields, so that it represents an empty list.
  132:  */
  133: LIST_INLINE void
  134: init_list(list *l)
  135: {
  136:   l->head = &l->tail_node;
  137:   l->null = NULL;
  138:   l->tail = &l->head_node;
  139: }
  140: 
  141: /**
  142:  * add_tail_list - concatenate two lists
  143:  * @to: destination list
  144:  * @l: source list
  145:  *
  146:  * This function appends all elements of the list @l to
  147:  * the list @to in constant time.
  148:  */
  149: LIST_INLINE void
  150: add_tail_list(list *to, list *l)
  151: {
  152:   node *p = to->tail;
  153:   node *q = l->head;
  154: 
  155:   p->next = q;
  156:   q->prev = p;
  157:   q = l->tail;
  158:   q->next = &to->tail_node;
  159:   to->tail = q;
  160: }