"Fossies" - the Fresh Open Source Software Archive

Member "knot-2.8.3/src/contrib/ucw/lists.c" (16 Jul 2019, 4818 Bytes) of package /linux/misc/dns/knot-2.8.3.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "lists.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2  *  BIRD Library -- Linked Lists
    3  *
    4  *  (c) 1998 Martin Mares <mj@ucw.cz>
    5  *  (c) 2015, 2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
    6  *
    7  *  Can be freely distributed and used under the terms of the GNU GPL.
    8  */
    9 
   10 /**
   11  * DOC: Linked lists
   12  *
   13  * The BIRD library provides a set of functions for operating on linked
   14  * lists. The lists are internally represented as standard doubly linked
   15  * lists with synthetic head and tail which makes all the basic operations
   16  * run in constant time and contain no extra end-of-list checks. Each list
   17  * is described by a &list structure, nodes can have any format as long
   18  * as they start with a &node structure. If you want your nodes to belong
   19  * to multiple lists at once, you can embed multiple &node structures in them
   20  * and use the SKIP_BACK() macro to calculate a pointer to the start of the
   21  * structure from a &node pointer, but beware of obscurity.
   22  *
   23  * There also exist safe linked lists (&slist, &snode and all functions
   24  * being prefixed with |s_|) which support asynchronous walking very
   25  * similar to that used in the &fib structure.
   26  */
   27 
   28 #include <stdlib.h>
   29 #include <string.h>
   30 #include "contrib/ucw/lists.h"
   31 #include "contrib/mempattern.h"
   32 
   33 /**
   34  * add_tail - append a node to a list
   35  * \p l: linked list
   36  * \p n: list node
   37  *
   38  * add_tail() takes a node \p n and appends it at the end of the list \p l.
   39  */
   40 void
   41 add_tail(list_t *l, node_t *n)
   42 {
   43   node_t *z = l->tail;
   44 
   45   n->next = (node_t *) &l->null;
   46   n->prev = z;
   47   z->next = n;
   48   l->tail = n;
   49 }
   50 
   51 /**
   52  * add_head - prepend a node to a list
   53  * \p l: linked list
   54  * \p n: list node
   55  *
   56  * add_head() takes a node \p n and prepends it at the start of the list \p l.
   57  */
   58 void
   59 add_head(list_t *l, node_t *n)
   60 {
   61   node_t *z = l->head;
   62 
   63   n->next = z;
   64   n->prev = (node_t *) &l->head;
   65   z->prev = n;
   66   l->head = n;
   67 }
   68 
   69 /**
   70  * insert_node - insert a node to a list
   71  * \p n: a new list node
   72  * \p after: a node of a list
   73  *
   74  * Inserts a node \p n to a linked list after an already inserted
   75  * node \p after.
   76  */
   77 void
   78 insert_node(node_t *n, node_t *after)
   79 {
   80   node_t *z = after->next;
   81 
   82   n->next = z;
   83   n->prev = after;
   84   after->next = n;
   85   z->prev = n;
   86 }
   87 
   88 /**
   89  * rem_node - remove a node from a list
   90  * \p n: node to be removed
   91  *
   92  * Removes a node \p n from the list it's linked in.
   93  */
   94 void
   95 rem_node(node_t *n)
   96 {
   97   node_t *z = n->prev;
   98   node_t *x = n->next;
   99 
  100   z->next = x;
  101   x->prev = z;
  102   n->prev = 0;
  103   n->next = 0;
  104 }
  105 
  106 /**
  107  * init_list - create an empty list
  108  * \p l: list
  109  *
  110  * init_list() takes a &list structure and initializes its
  111  * fields, so that it represents an empty list.
  112  */
  113 void
  114 init_list(list_t *l)
  115 {
  116   l->head = (node_t *) &l->null;
  117   l->null = NULL;
  118   l->tail = (node_t *) &l->head;
  119 }
  120 
  121 /**
  122  * add_tail_list - concatenate two lists
  123  * \p to: destination list
  124  * \p l: source list
  125  *
  126  * This function appends all elements of the list \p l to
  127  * the list \p to in constant time.
  128  */
  129 void
  130 add_tail_list(list_t *to, list_t *l)
  131 {
  132   node_t *p = to->tail;
  133   node_t *q = l->head;
  134 
  135   p->next = q;
  136   q->prev = p;
  137   q = l->tail;
  138   q->next = (node_t *) &to->null;
  139   to->tail = q;
  140 }
  141 
  142 /**
  143  * list_dup - duplicate list
  144  * \p to: destination list
  145  * \p l: source list
  146  *
  147  * This function duplicates all elements of the list \p l to
  148  * the list \p to in linear time.
  149  *
  150  * This function only works with a homogenous item size.
  151  */
  152 void list_dup(list_t *dst, list_t *src, size_t itemsz)
  153 {
  154     node_t *n = 0;
  155     WALK_LIST(n, *src) {
  156         node_t *i = malloc(itemsz);
  157         memcpy(i, n, itemsz);
  158         add_tail(dst, i);
  159     }
  160 }
  161 
  162 /**
  163  * list_size - gets number of nodes
  164  * \p l: list
  165  *
  166  * This function counts nodes in list \p l and returns this number.
  167  */
  168 size_t list_size(const list_t *l)
  169 {
  170     size_t count = 0;
  171 
  172     node_t *n = 0;
  173     WALK_LIST(n, *l) {
  174         count++;
  175     }
  176 
  177     return count;
  178 }
  179 
  180 /**
  181  * ptrlist_add - add pointer to pointer list
  182  * \p to: destination list
  183  * \p val: added pointer
  184  * \p mm: memory context
  185  */
  186 ptrnode_t *ptrlist_add(list_t *to, void *val, knot_mm_t *mm)
  187 {
  188     ptrnode_t *node = mm_alloc(mm , sizeof(ptrnode_t));
  189     if (node == NULL) {
  190         return NULL;
  191     } else {
  192         node->d = val;
  193     }
  194     add_tail(to, &node->n);
  195     return node;
  196 }
  197 
  198 /**
  199  * ptrlist_free - free all nodes in pointer list
  200  * \p list: list nodes
  201  * \p mm: memory context
  202  */
  203 void ptrlist_free(list_t *list, knot_mm_t *mm)
  204 {
  205     node_t *n = NULL, *nxt = NULL;
  206     WALK_LIST_DELSAFE(n, nxt, *list) {
  207         mm_free(mm, n);
  208     }
  209     init_list(list);
  210 }
  211 
  212 /**
  213  * ptrlist_rem - remove pointer node
  214  * \p val: pointer to remove
  215  * \p mm: memory context
  216  */
  217 void ptrlist_rem(ptrnode_t *node, knot_mm_t *mm)
  218 {
  219     rem_node(&node->n);
  220     mm_free(mm, node);
  221 }
  222 
  223 /**
  224  * ptrlist_deep_free - free all nodes incl referenced data
  225  * \p list: list nodes
  226  * \p mm: memory context
  227  */
  228 void ptrlist_deep_free(list_t *l, knot_mm_t *mm)
  229 {
  230     ptrnode_t *n;
  231     WALK_LIST(n, *l) {
  232         mm_free(mm, n->d);
  233     }
  234     ptrlist_free(l, mm);
  235 }