From 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:53:30 +0200 Subject: Adding upstream version 8.4.4. Signed-off-by: Daniel Baumann --- lib/linklist.c | 446 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 446 insertions(+) create mode 100644 lib/linklist.c (limited to 'lib/linklist.c') diff --git a/lib/linklist.c b/lib/linklist.c new file mode 100644 index 0000000..ece24db --- /dev/null +++ b/lib/linklist.c @@ -0,0 +1,446 @@ +/* Generic linked list routine. + * Copyright (C) 1997, 2000 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra 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 2, or (at your option) any + * later version. + * + * GNU Zebra 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; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include + +#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; + 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; +} -- cgit v1.2.3