summaryrefslogtreecommitdiffstats
path: root/lib/linklist.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/linklist.c')
-rw-r--r--lib/linklist.c432
1 files changed, 432 insertions, 0 deletions
diff --git a/lib/linklist.c b/lib/linklist.c
new file mode 100644
index 0000000..28dd777
--- /dev/null
+++ b/lib/linklist.c
@@ -0,0 +1,432 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/* Generic linked list routine.
+ * Copyright (C) 1997, 2000 Kunihiro Ishiguro
+ */
+
+#include <zebra.h>
+#include <stdlib.h>
+
+#include "linklist.h"
+#include "memory.h"
+#include "libfrr_trace.h"
+
+DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List");
+DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node");
+
+/* these *do not* cleanup list nodes and referenced data, as the functions
+ * do - these macros simply {de,at}tach a listnode from/to a list.
+ */
+
+/* List node attach macro. */
+#define LISTNODE_ATTACH(L, N) \
+ do { \
+ (N)->prev = (L)->tail; \
+ (N)->next = NULL; \
+ if ((L)->head == NULL) \
+ (L)->head = (N); \
+ else \
+ (L)->tail->next = (N); \
+ (L)->tail = (N); \
+ (L)->count++; \
+ } while (0)
+
+/* List node detach macro. */
+#define LISTNODE_DETACH(L, N) \
+ do { \
+ if ((N)->prev) \
+ (N)->prev->next = (N)->next; \
+ else \
+ (L)->head = (N)->next; \
+ if ((N)->next) \
+ (N)->next->prev = (N)->prev; \
+ else \
+ (L)->tail = (N)->prev; \
+ (L)->count--; \
+ } while (0)
+
+struct list *list_new(void)
+{
+ return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
+}
+
+/* Free list. */
+static void list_free_internal(struct list *l)
+{
+ XFREE(MTYPE_LINK_LIST, l);
+}
+
+
+/* Allocate new listnode. Internal use only. */
+static struct listnode *listnode_new(struct list *list, void *val)
+{
+ struct listnode *node;
+
+ /* if listnode memory is managed by the app then the val
+ * passed in is the listnode
+ */
+ if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
+ node = val;
+ node->prev = node->next = NULL;
+ } else {
+ node = XCALLOC(MTYPE_LINK_NODE, sizeof(struct listnode));
+ node->data = val;
+ }
+ return node;
+}
+
+/* Free listnode. */
+static void listnode_free(struct list *list, struct listnode *node)
+{
+ if (!(list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP))
+ XFREE(MTYPE_LINK_NODE, node);
+}
+
+struct listnode *listnode_add(struct list *list, void *val)
+{
+ frrtrace(2, frr_libfrr, list_add, list, val);
+
+ struct listnode *node;
+
+ assert(val != NULL);
+
+ node = listnode_new(list, val);
+
+ node->prev = list->tail;
+
+ if (list->head == NULL)
+ list->head = node;
+ else
+ list->tail->next = node;
+ list->tail = node;
+
+ list->count++;
+
+ return node;
+}
+
+void listnode_add_head(struct list *list, void *val)
+{
+ struct listnode *node;
+
+ assert(val != NULL);
+
+ node = listnode_new(list, val);
+
+ node->next = list->head;
+
+ if (list->head == NULL) {
+ list->head = node;
+ list->tail = node;
+ } else
+ list->head->prev = node;
+ list->head = node;
+
+ list->count++;
+}
+
+bool listnode_add_sort_nodup(struct list *list, void *val)
+{
+ struct listnode *n;
+ struct listnode *new;
+ int ret;
+ void *data;
+
+ assert(val != NULL);
+
+ if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
+ n = val;
+ data = n->data;
+ } else {
+ data = val;
+ }
+
+ if (list->cmp) {
+ for (n = list->head; n; n = n->next) {
+ ret = (*list->cmp)(data, n->data);
+ if (ret < 0) {
+ new = listnode_new(list, val);
+
+ new->next = n;
+ new->prev = n->prev;
+
+ if (n->prev)
+ n->prev->next = new;
+ else
+ list->head = new;
+ n->prev = new;
+ list->count++;
+ return true;
+ }
+ /* found duplicate return false */
+ if (ret == 0)
+ return false;
+ }
+ }
+
+ new = listnode_new(list, val);
+
+ LISTNODE_ATTACH(list, new);
+
+ return true;
+}
+
+struct list *list_dup(struct list *list)
+{
+ struct list *dup;
+ struct listnode *node;
+ void *data;
+
+ assert(list);
+
+ dup = list_new();
+ dup->cmp = list->cmp;
+ dup->del = list->del;
+ for (ALL_LIST_ELEMENTS_RO(list, node, data))
+ listnode_add(dup, data);
+
+ return dup;
+}
+
+void listnode_add_sort(struct list *list, void *val)
+{
+ struct listnode *n;
+ struct listnode *new;
+
+ assert(val != NULL);
+
+ new = listnode_new(list, val);
+ val = new->data;
+
+ if (list->cmp) {
+ for (n = list->head; n; n = n->next) {
+ if ((*list->cmp)(val, n->data) < 0) {
+ new->next = n;
+ new->prev = n->prev;
+
+ if (n->prev)
+ n->prev->next = new;
+ else
+ list->head = new;
+ n->prev = new;
+ list->count++;
+ return;
+ }
+ }
+ }
+
+ new->prev = list->tail;
+
+ if (list->tail)
+ list->tail->next = new;
+ else
+ list->head = new;
+
+ list->tail = new;
+ list->count++;
+}
+
+struct listnode *listnode_add_after(struct list *list, struct listnode *pp,
+ void *val)
+{
+ struct listnode *nn;
+
+ assert(val != NULL);
+
+ nn = listnode_new(list, val);
+
+ if (pp == NULL) {
+ if (list->head)
+ list->head->prev = nn;
+ else
+ list->tail = nn;
+
+ nn->next = list->head;
+ nn->prev = pp;
+
+ list->head = nn;
+ } else {
+ if (pp->next)
+ pp->next->prev = nn;
+ else
+ list->tail = nn;
+
+ nn->next = pp->next;
+ nn->prev = pp;
+
+ pp->next = nn;
+ }
+ list->count++;
+ return nn;
+}
+
+struct listnode *listnode_add_before(struct list *list, struct listnode *pp,
+ void *val)
+{
+ struct listnode *nn;
+
+ assert(val != NULL);
+
+ nn = listnode_new(list, val);
+
+ if (pp == NULL) {
+ if (list->tail)
+ list->tail->next = nn;
+ else
+ list->head = nn;
+
+ nn->prev = list->tail;
+ nn->next = pp;
+
+ list->tail = nn;
+ } else {
+ if (pp->prev)
+ pp->prev->next = nn;
+ else
+ list->head = nn;
+
+ nn->prev = pp->prev;
+ nn->next = pp;
+
+ pp->prev = nn;
+ }
+ list->count++;
+ return nn;
+}
+
+void listnode_move_to_tail(struct list *l, struct listnode *n)
+{
+ LISTNODE_DETACH(l, n);
+ LISTNODE_ATTACH(l, n);
+}
+
+void listnode_delete(struct list *list, const void *val)
+{
+ frrtrace(2, frr_libfrr, list_remove, list, val);
+
+ struct listnode *node = listnode_lookup(list, val);
+
+ if (node)
+ list_delete_node(list, node);
+}
+
+void *listnode_head(struct list *list)
+{
+ struct listnode *node;
+
+ assert(list);
+ node = list->head;
+
+ if (node)
+ return node->data;
+ return NULL;
+}
+
+void list_delete_all_node(struct list *list)
+{
+ struct listnode *node;
+ struct listnode *next;
+
+ assert(list);
+ for (node = list->head; node; node = next) {
+ next = node->next;
+ if (*list->del)
+ (*list->del)(node->data);
+ listnode_free(list, node);
+ }
+ list->head = list->tail = NULL;
+ list->count = 0;
+}
+
+void list_delete(struct list **list)
+{
+ assert(*list);
+ list_delete_all_node(*list);
+ list_free_internal(*list);
+ *list = NULL;
+}
+
+struct listnode *listnode_lookup(struct list *list, const void *data)
+{
+ struct listnode *node;
+
+ assert(list);
+ for (node = listhead(list); node; node = listnextnode(node))
+ if (data == listgetdata(node))
+ return node;
+ return NULL;
+}
+
+struct listnode *listnode_lookup_nocheck(struct list *list, void *data)
+{
+ if (!list)
+ return NULL;
+ return listnode_lookup(list, data);
+}
+
+void list_delete_node(struct list *list, struct listnode *node)
+{
+ frrtrace(2, frr_libfrr, list_delete_node, list, node);
+
+ if (node->prev)
+ node->prev->next = node->next;
+ else
+ list->head = node->next;
+ if (node->next)
+ node->next->prev = node->prev;
+ else
+ list->tail = node->prev;
+ list->count--;
+ listnode_free(list, node);
+}
+
+void list_sort(struct list *list, int (*cmp)(const void **, const void **))
+{
+ frrtrace(1, frr_libfrr, list_sort, list);
+
+ struct listnode *ln, *nn;
+ int i = -1;
+ void *data;
+ size_t n = list->count;
+ void **items;
+ int (*realcmp)(const void *, const void *) =
+ (int (*)(const void *, const void *))cmp;
+
+ if (!n)
+ return;
+
+ items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
+
+ for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
+ items[++i] = data;
+ list_delete_node(list, ln);
+ }
+
+ qsort(items, n, sizeof(void *), realcmp);
+
+ for (unsigned int j = 0; j < n; ++j)
+ listnode_add(list, items[j]);
+
+ XFREE(MTYPE_TMP, items);
+}
+
+struct listnode *listnode_add_force(struct list **list, void *val)
+{
+ if (*list == NULL)
+ *list = list_new();
+ return listnode_add(*list, val);
+}
+
+void **list_to_array(struct list *list, void **arr, size_t arrlen)
+{
+ struct listnode *ln;
+ void *vp;
+ size_t idx = 0;
+
+ for (ALL_LIST_ELEMENTS_RO(list, ln, vp)) {
+ arr[idx++] = vp;
+ if (idx == arrlen)
+ break;
+ }
+
+ return arr;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 00:24:38 +0000