Return to lists.c CVS log

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

Annotation of embedaddon/bird2/lib/lists.c, revision 1.1.1.1

1.1       misho       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: }
                    161: 
                    162: LIST_INLINE uint
                    163: list_length(list *l)
                    164: {
                    165:   uint len = 0;
                    166:   node *n;
                    167: 
                    168:   WALK_LIST(n, *l)
                    169:     len++;
                    170: 
                    171:   return len;
                    172: }