diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:36:22 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:36:22 +0000 |
commit | b88bb292821fd7742604ec4e280acebd9a049f62 (patch) | |
tree | 625e4e19e6619f7481e5a8103f876520950769f6 /src/contrib/ucw/lists.c | |
parent | Initial commit. (diff) | |
download | knot-upstream.tar.xz knot-upstream.zip |
Adding upstream version 3.0.5.upstream/3.0.5upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/contrib/ucw/lists.c')
-rw-r--r-- | src/contrib/ucw/lists.c | 244 |
1 files changed, 244 insertions, 0 deletions
diff --git a/src/contrib/ucw/lists.c b/src/contrib/ucw/lists.c new file mode 100644 index 0000000..84c6eaa --- /dev/null +++ b/src/contrib/ucw/lists.c @@ -0,0 +1,244 @@ +/* + * BIRD Library -- Linked Lists + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * (c) 2015, 2020 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +/** + * DOC: Linked lists + * + * The BIRD library provides a set of functions for operating on linked + * lists. The lists are internally represented as standard doubly linked + * lists with synthetic head and tail which makes all the basic operations + * run in constant time and contain no extra end-of-list checks. Each list + * is described by a &list structure, nodes can have any format as long + * as they start with a &node structure. If you want your nodes to belong + * to multiple lists at once, you can embed multiple &node structures in them + * and use the SKIP_BACK() macro to calculate a pointer to the start of the + * structure from a &node pointer, but beware of obscurity. + * + * There also exist safe linked lists (&slist, &snode and all functions + * being prefixed with |s_|) which support asynchronous walking very + * similar to that used in the &fib structure. + */ + +#include <stdlib.h> +#include <string.h> +#include "contrib/ucw/lists.h" +#include "contrib/mempattern.h" + +/** + * add_tail - append a node to a list + * \p l: linked list + * \p n: list node + * + * add_tail() takes a node \p n and appends it at the end of the list \p l. + */ +void +add_tail(list_t *l, node_t *n) +{ + node_t *z = l->tail; + + n->next = (node_t *) &l->null; + n->prev = z; + z->next = n; + l->tail = n; +} + +/** + * add_head - prepend a node to a list + * \p l: linked list + * \p n: list node + * + * add_head() takes a node \p n and prepends it at the start of the list \p l. + */ +void +add_head(list_t *l, node_t *n) +{ + node_t *z = l->head; + + n->next = z; + n->prev = (node_t *) &l->head; + z->prev = n; + l->head = n; +} + +/** + * insert_node - insert a node to a list + * \p n: a new list node + * \p after: a node of a list + * + * Inserts a node \p n to a linked list after an already inserted + * node \p after. + */ +void +insert_node(node_t *n, node_t *after) +{ + node_t *z = after->next; + + n->next = z; + n->prev = after; + after->next = n; + z->prev = n; +} + +/** + * rem_node - remove a node from a list + * \p n: node to be removed + * + * Removes a node \p n from the list it's linked in. + */ +void +rem_node(node_t *n) +{ + node_t *z = n->prev; + node_t *x = n->next; + + z->next = x; + x->prev = z; + n->prev = 0; + n->next = 0; +} + +/** + * init_list - create an empty list + * \p l: list + * + * init_list() takes a &list structure and initializes its + * fields, so that it represents an empty list. + */ +void +init_list(list_t *l) +{ + l->head = (node_t *) &l->null; + l->null = NULL; + l->tail = (node_t *) &l->head; +} + +/** + * add_tail_list - concatenate two lists + * \p to: destination list + * \p l: source list + * + * This function appends all elements of the list \p l to + * the list \p to in constant time. + */ +void +add_tail_list(list_t *to, list_t *l) +{ + node_t *p = to->tail; + node_t *q = l->head; + + p->next = q; + q->prev = p; + q = l->tail; + q->next = (node_t *) &to->null; + to->tail = q; +} + +/** + * list_dup - duplicate list + * \p to: destination list + * \p l: source list + * + * This function duplicates all elements of the list \p l to + * the list \p to in linear time. + * + * This function only works with a homogenous item size. + */ +void list_dup(list_t *dst, list_t *src, size_t itemsz) +{ + node_t *n; + WALK_LIST(n, *src) { + node_t *i = malloc(itemsz); + memcpy(i, n, itemsz); + add_tail(dst, i); + } +} + +/** + * list_size - gets number of nodes + * \p l: list + * + * This function counts nodes in list \p l and returns this number. + */ +size_t list_size(const list_t *l) +{ + size_t count = 0; + + node_t *n; + WALK_LIST(n, *l) { + count++; + } + + return count; +} + +/** + * ptrlist_add - add pointer to pointer list + * \p to: destination list + * \p val: added pointer + * \p mm: memory context + */ +ptrnode_t *ptrlist_add(list_t *to, void *val, knot_mm_t *mm) +{ + ptrnode_t *node = mm_alloc(mm , sizeof(ptrnode_t)); + if (node == NULL) { + return NULL; + } else { + node->d = val; + } + add_tail(to, &node->n); + return node; +} + +/** + * ptrlist_free - free all nodes in pointer list + * \p list: list nodes + * \p mm: memory context + */ +void ptrlist_free(list_t *list, knot_mm_t *mm) +{ + node_t *n, *nxt; + WALK_LIST_DELSAFE(n, nxt, *list) { + mm_free(mm, n); + } + init_list(list); +} + +/** + * ptrlist_rem - remove pointer node + * \p val: pointer to remove + * \p mm: memory context + */ +void ptrlist_rem(ptrnode_t *node, knot_mm_t *mm) +{ + rem_node(&node->n); + mm_free(mm, node); +} + +/** + * ptrlist_deep_free - free all nodes incl referenced data + * \p list: list nodes + * \p mm: memory context + */ +void ptrlist_deep_free(list_t *l, knot_mm_t *mm) +{ + ptrnode_t *n; + WALK_LIST(n, *l) { + mm_free(mm, n->d); + } + ptrlist_free(l, mm); +} + +void ptrlist_free_custom(list_t *l, knot_mm_t *mm, ptrlist_free_cb free_cb) +{ + ptrnode_t *n; + WALK_LIST(n, *l) { + free_cb(n->d); + } + ptrlist_free(l, mm); +} |