From f449f278dd3c70e479a035f50a9bb817a9b433ba Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:24:08 +0200 Subject: Adding upstream version 3.2.6. Signed-off-by: Daniel Baumann --- src/contrib/ucw/lists.c | 264 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 264 insertions(+) create mode 100644 src/contrib/ucw/lists.c (limited to 'src/contrib/ucw/lists.c') diff --git a/src/contrib/ucw/lists.c b/src/contrib/ucw/lists.c new file mode 100644 index 0000000..01af28f --- /dev/null +++ b/src/contrib/ucw/lists.c @@ -0,0 +1,264 @@ +/* + * BIRD Library -- Linked Lists + * + * (c) 1998 Martin Mares + * (c) 2015, 2020-2022 CZ.NIC, z.s.p.o. + * + * 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 +#include +#include + +#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 = z; + n->prev = z->prev; + z->prev->next = n; + z->prev = n; + assert(z->next == NULL); +} + +/** + * 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->next; + n->prev = z; + z->next->prev = n; + z->next = n; + assert(z->prev == NULL); +} + +/** + * 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.next = &l->tail; + l->head.prev = NULL; + l->tail.next = NULL; + l->tail.prev = &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.prev; + node_t *q = l->head.next; + + p->next = q; + q->prev = p; + to->tail.prev = l->tail.prev; +} + +/** + * 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; +} + +/** + * fix_list - correction of head/tail pointers when list had been memmove'd + * \p l: list + * + * WARNING: must not be called on empty list + */ +void fix_list(list_t *l) +{ + node_t *n = HEAD(*l); + assert(n->next != NULL); + n->prev = &l->head; + + n = TAIL(*l); + assert(n->prev != NULL); + n->next = &l->tail; +} + +/** + * 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); +} -- cgit v1.2.3