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     ! 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: }