*/
#include <zebra.h>
+#include <stdlib.h>
#include "linklist.h"
#include "memory.h"
DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List")
DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node")
-/* Allocate new list. */
-struct list *
-list_new (void)
+struct list *list_new(void)
{
- return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
+ return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
}
/* Free list. */
-void
-list_free (struct list *l)
+static void list_free_internal(struct list *l)
{
- XFREE (MTYPE_LINK_LIST, l);
+ XFREE(MTYPE_LINK_LIST, l);
}
/* Allocate new listnode. Internal use only. */
-static struct listnode *
-listnode_new (void)
+static struct listnode *listnode_new(void)
{
- return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
+ return XCALLOC(MTYPE_LINK_NODE, sizeof(struct listnode));
}
/* Free listnode. */
-static void
-listnode_free (struct listnode *node)
+static void listnode_free(struct listnode *node)
{
- XFREE (MTYPE_LINK_NODE, node);
+ XFREE(MTYPE_LINK_NODE, node);
}
-/* Add new data to the list. */
-void
-listnode_add (struct list *list, void *val)
+void listnode_add(struct list *list, void *val)
{
- struct listnode *node;
-
- assert (val != NULL);
-
- node = listnode_new ();
-
- node->prev = list->tail;
- node->data = val;
-
- if (list->head == NULL)
- list->head = node;
- else
- list->tail->next = node;
- list->tail = node;
-
- list->count++;
+ struct listnode *node;
+
+ assert(val != NULL);
+
+ node = listnode_new();
+
+ node->prev = list->tail;
+ node->data = val;
+
+ if (list->head == NULL)
+ list->head = node;
+ else
+ list->tail->next = node;
+ list->tail = node;
+
+ list->count++;
}
-/*
- * Add a node to the list. If the list was sorted according to the
- * cmp function, insert a new node with the given val such that the
- * list remains sorted. The new node is always inserted; there is no
- * notion of omitting duplicates.
- */
-void
-listnode_add_sort (struct list *list, void *val)
+void listnode_add_head(struct list *list, void *val)
{
- struct listnode *n;
- struct listnode *new;
-
- assert (val != NULL);
-
- new = listnode_new ();
- new->data = val;
-
- 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;
- }
+ struct listnode *node;
+
+ assert(val != NULL);
+
+ node = listnode_new();
+
+ node->next = list->head;
+ node->data = val;
+
+ if (list->head == NULL)
+ list->head = node;
+ else
+ list->head->prev = node;
+ list->head = node;
+
+ list->count++;
+}
+
+void listnode_add_sort(struct list *list, void *val)
+{
+ struct listnode *n;
+ struct listnode *new;
+
+ assert(val != NULL);
+
+ new = listnode_new();
+ new->data = val;
+
+ 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;
+ new->prev = list->tail;
- if (list->tail)
- list->tail->next = new;
- else
- list->head = new;
+ if (list->tail)
+ list->tail->next = new;
+ else
+ list->head = new;
- list->tail = new;
- list->count++;
+ list->tail = new;
+ list->count++;
}
-struct listnode *
-listnode_add_after (struct list *list, struct listnode *pp, void *val)
+struct listnode *listnode_add_after(struct list *list, struct listnode *pp,
+ void *val)
{
- struct listnode *nn;
-
- assert (val != NULL);
-
- nn = listnode_new ();
- nn->data = 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 *nn;
+
+ assert(val != NULL);
+
+ nn = listnode_new();
+ nn->data = 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 *listnode_add_before(struct list *list, struct listnode *pp,
+ void *val)
{
- struct listnode *nn;
-
- assert (val != NULL);
-
- nn = listnode_new ();
- nn->data = 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;
+ struct listnode *nn;
+
+ assert(val != NULL);
+
+ nn = listnode_new();
+ nn->data = 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;
}
-/* Move given listnode to tail of the list */
-void
-listnode_move_to_tail (struct list *l, struct listnode *n)
+void listnode_move_to_tail(struct list *l, struct listnode *n)
{
- LISTNODE_DETACH(l,n);
- LISTNODE_ATTACH(l,n);
+ LISTNODE_DETACH(l, n);
+ LISTNODE_ATTACH(l, n);
}
-/* Delete specific date pointer from the list. */
-void
-listnode_delete (struct list *list, void *val)
+void listnode_delete(struct list *list, void *val)
{
- struct listnode *node;
-
- assert(list);
- for (node = list->head; node; node = node->next)
- {
- if (node->data == val)
- {
- 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 (node);
- return;
- }
- }
+ struct listnode *node = listnode_lookup(list, val);
+
+ if (node)
+ list_delete_node(list, node);
}
-/* Return first node's data if it is there. */
-void *
-listnode_head (struct list *list)
+void *listnode_head(struct list *list)
{
- struct listnode *node;
+ struct listnode *node;
+
+ assert(list);
+ node = list->head;
+
+ if (node)
+ return node->data;
+ return NULL;
+}
- assert(list);
- node = list->head;
+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(node);
+ }
+ list->head = list->tail = NULL;
+ list->count = 0;
+}
- if (node)
- return node->data;
- return NULL;
+void list_delete(struct list **list)
+{
+ assert(*list);
+ list_delete_all_node(*list);
+ list_free_internal(*list);
+ *list = NULL;
}
-/* Delete all listnode from the list. */
-void
-list_delete_all_node (struct list *list)
+struct listnode *listnode_lookup(struct list *list, void *data)
{
- 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 (node);
- }
- list->head = list->tail = NULL;
- list->count = 0;
+ struct listnode *node;
+
+ assert(list);
+ for (node = listhead(list); node; node = listnextnode(node))
+ if (data == listgetdata(node))
+ return node;
+ return NULL;
}
-/* Delete all listnode then free list itself. */
-void
-list_delete (struct list *list)
+void list_delete_node(struct list *list, struct listnode *node)
{
- assert(list);
- list_delete_all_node (list);
- list_free (list);
+ 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(node);
}
-/* Lookup the node which has given data. */
-struct listnode *
-listnode_lookup (struct list *list, void *data)
+void list_add_list(struct list *list, struct list *add)
{
- struct listnode *node;
+ struct listnode *n;
- assert(list);
- for (node = listhead(list); node; node = listnextnode (node))
- if (data == listgetdata (node))
- return node;
- return NULL;
+ for (n = listhead(add); n; n = listnextnode(n))
+ listnode_add(list, n->data);
}
-/* Delete the node from list. For ospfd and ospf6d. */
-void
-list_delete_node (struct list *list, struct listnode *node)
+struct list *list_dup(struct list *list)
{
- 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 (node);
+ struct list *new = list_new();
+ struct listnode *ln;
+ void *data;
+
+ new->cmp = list->cmp;
+ new->del = list->del;
+
+ for (ALL_LIST_ELEMENTS_RO(list, ln, data))
+ listnode_add(new, data);
+
+ return new;
}
-/* ospf_spf.c */
-void
-list_add_list (struct list *l, struct list *m)
+void list_sort(struct list *list, int (*cmp)(const void **, const void **))
{
- struct listnode *n;
+ struct listnode *ln, *nn;
+ int i = -1;
+ void *data;
+ size_t n = list->count;
+ void **items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
+ int (*realcmp)(const void *, const void *) =
+ (int (*)(const void *, const void *))cmp;
+
+ 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]);
- for (n = listhead (m); n; n = listnextnode (n))
- listnode_add (l, n->data);
+ XFREE(MTYPE_TMP, items);
}
projects / mirror_frr.git / blobdiff