summaryrefslogtreecommitdiffstats
path: root/src/libdnssec/list
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 00:53:35 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-06 00:53:35 +0000
commit69c6a41ffb878ef98c9378ed4b1634a404cfaa7f (patch)
treeb2a4f704565d62fbb129ab9dc3b35977c50e6e7f /src/libdnssec/list
parentInitial commit. (diff)
downloadknot-upstream.tar.xz
knot-upstream.zip
Adding upstream version 2.7.6.upstream/2.7.6upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/libdnssec/list')
-rw-r--r--src/libdnssec/list/list.c298
-rw-r--r--src/libdnssec/list/ucw_clists.h260
2 files changed, 558 insertions, 0 deletions
diff --git a/src/libdnssec/list/list.c b/src/libdnssec/list/list.c
new file mode 100644
index 0000000..5d9aded
--- /dev/null
+++ b/src/libdnssec/list/list.c
@@ -0,0 +1,298 @@
+/* Copyright (C) 2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <stdlib.h>
+
+#include "libdnssec/list.h"
+#include "libdnssec/list/ucw_clists.h"
+#include "libdnssec/error.h"
+#include "libdnssec/shared/shared.h"
+
+struct dnssec_list {
+ clist list;
+};
+
+struct dnssec_item {
+ cnode node;
+ void *data;
+};
+
+/*!
+ * Allocate new list item and set item data.
+ */
+static dnssec_item_t *item_new(void *data)
+{
+ dnssec_item_t *item = malloc(sizeof(*item));
+ if (item) {
+ clear_struct(item);
+ item->data = data;
+ }
+
+ return item;
+}
+
+/*!
+ * Wrapper around libc free with unused context.
+ */
+static void wrap_free(void *ptr, void *ctx _unused_)
+{
+ free(ptr);
+}
+
+/* -- public API ----------------------------------------------------------- */
+
+_public_
+void *dnssec_item_get(const dnssec_item_t *item)
+{
+ return item ? item->data : NULL;
+}
+
+_public_
+void dnssec_item_set(dnssec_item_t *item, void *data)
+{
+ if (item) {
+ item->data = data;
+ }
+}
+
+_public_
+dnssec_list_t *dnssec_list_new(void)
+{
+ dnssec_list_t *list = malloc(sizeof(*list));
+ if (list) {
+ clist_init(&list->list);
+ }
+
+ return list;
+}
+
+_public_
+void dnssec_list_clear(dnssec_list_t *list)
+{
+ if (!list) {
+ return;
+ }
+
+ dnssec_list_foreach(item, list) {
+ free(item);
+ }
+}
+
+_public_
+void dnssec_list_clear_full(dnssec_list_t *list, dnssec_item_free_cb free_cb,
+ void *free_ctx)
+{
+ if (!list) {
+ return;
+ }
+
+ if (!free_cb) {
+ free_cb = wrap_free;
+ }
+
+ dnssec_list_foreach(item, list) {
+ free_cb(item->data, free_ctx);
+ free(item);
+ }
+}
+
+_public_
+void dnssec_list_free(dnssec_list_t *list)
+{
+ if (!list) {
+ return;
+ }
+
+ dnssec_list_clear(list);
+ free(list);
+}
+
+_public_
+void dnssec_list_free_full(dnssec_list_t *list, dnssec_item_free_cb free_cb,
+ void *free_ctx)
+{
+ if (!list) {
+ return;
+ }
+
+ dnssec_list_clear_full(list, free_cb, free_ctx);
+ free(list);
+}
+
+_public_
+dnssec_item_t *dnssec_list_head(dnssec_list_t *list)
+{
+ if (!list) {
+ return NULL;
+ }
+
+ return clist_head(&list->list);
+}
+
+_public_
+dnssec_item_t *dnssec_list_tail(dnssec_list_t *list)
+{
+ if (!list) {
+ return NULL;
+ }
+
+ return clist_tail(&list->list);
+}
+
+_public_
+dnssec_item_t *dnssec_list_next(dnssec_list_t *list, dnssec_item_t *item)
+{
+ if (!list || !item) {
+ return NULL;
+ }
+
+ return clist_next(&list->list, &item->node);
+}
+
+_public_
+dnssec_item_t *dnssec_list_prev(dnssec_list_t *list, dnssec_item_t *item)
+{
+ if (!list || !item) {
+ return NULL;
+ }
+
+ return clist_prev(&list->list, &item->node);
+}
+
+_public_
+dnssec_item_t *dnssec_list_nth(dnssec_list_t *list, size_t position)
+{
+ size_t index = 0;
+ dnssec_item_t *item = dnssec_list_head(list);
+
+ while (item) {
+ if (index == position) {
+ return item;
+ } else {
+ item = dnssec_list_next(list, item);
+ index += 1;
+ }
+ }
+
+ return NULL;
+}
+
+_public_
+bool dnssec_list_is_empty(dnssec_list_t *list)
+{
+ return !list || clist_empty(&list->list);
+}
+
+_public_
+size_t dnssec_list_size(dnssec_list_t *list)
+{
+ return list ? clist_size(&list->list) : 0;
+}
+
+_public_
+int dnssec_list_insert_before(dnssec_item_t *item, void *data)
+{
+ if (!item) {
+ return DNSSEC_EINVAL;
+ }
+
+ dnssec_item_t *add = item_new(data);
+ if (!add) {
+ return DNSSEC_ENOMEM;
+ }
+
+ clist_insert_before(&add->node, &item->node);
+
+ return DNSSEC_EOK;
+}
+
+_public_
+int dnssec_list_insert_after(dnssec_item_t *item, void *data)
+{
+ if (!item) {
+ return DNSSEC_EINVAL;
+ }
+
+ dnssec_item_t *add = item_new(data);
+ if (!add) {
+ return DNSSEC_ENOMEM;
+ }
+
+ clist_insert_after(&add->node, &item->node);
+
+ return DNSSEC_EOK;
+}
+
+_public_
+int dnssec_list_append(dnssec_list_t *list, void *data)
+{
+ if (!list) {
+ return DNSSEC_EINVAL;
+ }
+
+ dnssec_item_t *add = item_new(data);
+ if (!add) {
+ return DNSSEC_ENOMEM;
+ }
+
+ clist_add_tail(&list->list , &add->node);
+
+ return DNSSEC_EOK;
+}
+
+_public_
+int dnssec_list_prepend(dnssec_list_t *list, void *data)
+{
+ if (!list) {
+ return DNSSEC_EINVAL;
+ }
+
+ dnssec_item_t *add = item_new(data);
+ if (!add) {
+ return DNSSEC_ENOMEM;
+ }
+
+ clist_add_head(&list->list , &add->node);
+
+ return DNSSEC_EOK;
+}
+
+_public_
+void dnssec_list_remove(dnssec_item_t *item)
+{
+ if (item) {
+ clist_remove(&item->node);
+ free(item);
+ }
+}
+
+_public_
+dnssec_item_t *dnssec_list_search(dnssec_list_t *list, void *data)
+{
+ dnssec_list_foreach(item, list) {
+ if (item->data == data) {
+ return item;
+ }
+ }
+
+ return NULL;
+}
+
+_public_
+bool dnssec_list_contains(dnssec_list_t *list, void *data)
+{
+ return dnssec_list_search(list, data) != NULL;
+}
diff --git a/src/libdnssec/list/ucw_clists.h b/src/libdnssec/list/ucw_clists.h
new file mode 100644
index 0000000..080d01e
--- /dev/null
+++ b/src/libdnssec/list/ucw_clists.h
@@ -0,0 +1,260 @@
+/*
+ * UCW Library -- Circular Linked Lists
+ *
+ * (c) 2003--2010 Martin Mares <mj@ucw.cz>
+ *
+ * This software may be freely distributed and used according to the terms
+ * of the GNU Lesser General Public License.
+ */
+
+#ifndef _UCW_CLISTS_H
+#define _UCW_CLISTS_H
+
+/**
+ * Common header for list nodes.
+ **/
+typedef struct cnode {
+ struct cnode *next, *prev;
+} cnode;
+
+/**
+ * Circular doubly linked list.
+ **/
+typedef struct clist {
+ struct cnode head;
+} clist;
+
+/**
+ * Initialize a new circular linked list. Must be called before any other function.
+ **/
+static inline void clist_init(clist *l)
+{
+ cnode *head = &l->head;
+ head->next = head->prev = head;
+}
+
+/**
+ * Return the first node on \p l or NULL if \p l is empty.
+ **/
+static inline void *clist_head(clist *l)
+{
+ return (l->head.next != &l->head) ? l->head.next : NULL;
+}
+
+/**
+ * Return the last node on \p l or NULL if \p l is empty.
+ **/
+static inline void *clist_tail(clist *l)
+{
+ return (l->head.prev != &l->head) ? l->head.prev : NULL;
+}
+
+/**
+ * Find the next node to \p n or NULL if \p n is the last one.
+ **/
+static inline void *clist_next(clist *l, cnode *n)
+{
+ return (n->next != &l->head) ? (void *) n->next : NULL;
+}
+
+/**
+ * Find the previous node to \p n or NULL if \p n is the first one.
+ **/
+static inline void *clist_prev(clist *l, cnode *n)
+{
+ return (n->prev != &l->head) ? (void *) n->prev : NULL;
+}
+
+/**
+ * Return a non-zero value iff \p l is empty.
+ **/
+static inline int clist_empty(clist *l)
+{
+ return (l->head.next == &l->head);
+}
+
+/**
+ * Loop over all nodes in the \ref list and perform the next C statement on them. The current node is stored in \p n which must be defined before as pointer to any type.
+ * The list should not be changed during this loop command.
+ **/
+#define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
+
+/**
+ * Same as \ref CLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store some temporary pointers.
+ **/
+#define CLIST_WALK_DELSAFE(n,list,tmp) for(n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)
+
+/**
+ * Same as \ref CLIST_WALK(), but it defines the variable for the current node in place. \p type should be a pointer type.
+ **/
+#define CLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
+
+/**
+ * Same as \ref CLIST_WALK_DELSAFE(), but it defines the variable for the current node in place. \p type should be a pointer type. The temporary variable must be still known before.
+ **/
+#define CLIST_FOR_EACH_DELSAFE(type,n,list,tmp) for(type n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)
+
+/**
+ * Reversed version of \ref CLIST_FOR_EACH().
+ **/
+#define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)
+
+/**
+ * Insert a new node just after the node \p after. To insert at the head of the list, use \ref clist_add_head() instead.
+ **/
+static inline void clist_insert_after(cnode *what, cnode *after)
+{
+ cnode *before = after->next;
+ what->next = before;
+ what->prev = after;
+ before->prev = what;
+ after->next = what;
+}
+
+/**
+ * Insert a new node just before the node \p before. To insert at the tail of the list, use \ref clist_add_tail() instead.
+ **/
+static inline void clist_insert_before(cnode *what, cnode *before)
+{
+ cnode *after = before->prev;
+ what->next = before;
+ what->prev = after;
+ before->prev = what;
+ after->next = what;
+}
+
+/**
+ * Insert a new node in front of all other nodes.
+ **/
+static inline void clist_add_head(clist *l, cnode *n)
+{
+ clist_insert_after(n, &l->head);
+}
+
+/**
+ * Insert a new node after all other nodes.
+ **/
+static inline void clist_add_tail(clist *l, cnode *n)
+{
+ clist_insert_before(n, &l->head);
+}
+
+/**
+ * Remove node \p n.
+ **/
+static inline void clist_remove(cnode *n)
+{
+ cnode *before = n->prev;
+ cnode *after = n->next;
+ before->next = after;
+ after->prev = before;
+}
+
+/**
+ * Remove the first node in \p l, if it exists. Return the pointer to that node or NULL.
+ **/
+static inline void *clist_remove_head(clist *l)
+{
+ cnode *n = clist_head(l);
+ if (n)
+ clist_remove(n);
+ return n;
+}
+
+/**
+ * Remove the last node in \p l, if it exists. Return the pointer to that node or NULL.
+ **/
+static inline void *clist_remove_tail(clist *l)
+{
+ cnode *n = clist_tail(l);
+ if (n)
+ clist_remove(n);
+ return n;
+}
+
+/**
+ * Merge two lists by inserting the list \p what just after the node \p after in a different list.
+ * The first list is then cleared.
+ **/
+static inline void clist_insert_list_after(clist *what, cnode *after)
+{
+ if (!clist_empty(what))
+ {
+ cnode *w = &what->head;
+ w->prev->next = after->next;
+ after->next->prev = w->prev;
+ w->next->prev = after;
+ after->next = w->next;
+ clist_init(what);
+ }
+}
+
+/**
+ * Move all items from a source list to a destination list. The source list
+ * becomes empty, the original contents of the destination list are destroyed.
+ **/
+static inline void clist_move(clist *to, clist *from)
+{
+ clist_init(to);
+ clist_insert_list_after(from, &to->head);
+ clist_init(from);
+}
+
+/**
+ * Compute the number of nodes in \p l. Beware of linear time complexity.
+ **/
+static inline unsigned int clist_size(clist *l)
+{
+ unsigned int i = 0;
+ CLIST_FOR_EACH(cnode *, n, *l)
+ i++;
+ return i;
+}
+
+/**
+ * Remove a node \p n and mark it as unlinked by setting the previous and next pointers to NULL.
+ **/
+static inline void clist_unlink(cnode *n)
+{
+ clist_remove(n);
+ n->prev = n->next = NULL;
+}
+
+/**
+ * Remove the first node on \p l and mark it as unlinked.
+ * Return the pointer to that node or NULL.
+ **/
+static inline void *clist_unlink_head(clist *l)
+{
+ cnode *n = clist_head(l);
+ if (n)
+ clist_unlink(n);
+ return n;
+}
+
+/**
+ * Remove the last node on \p l and mark it as unlinked.
+ * Return the pointer to that node or NULL.
+ **/
+static inline void *clist_unlink_tail(clist *l)
+{
+ cnode *n = clist_tail(l);
+ if (n)
+ clist_unlink(n);
+ return n;
+}
+
+/**
+ * Check if a node is linked a list. Unlinked nodes are recognized by having their
+ * previous and next pointers equal to NULL. Returns 0 or 1.
+ *
+ * Nodes initialized to all zeroes are unlinked, inserting a node anywhere in a list
+ * makes it linked. Normal removal functions like \ref clist_remove() do not mark nodes
+ * as unlinked, you need to call \ref clist_unlink() instead.
+ **/
+static inline int clist_is_linked(cnode *n)
+{
+ return !!n->next;
+}
+
+#endif