/src/frr/lib/linklist.c

Source
// 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;
}

Coverage Report

Created: 2026-01-13 06:56

Line	Count	Source
1		// SPDX-License-Identifier: GPL-2.0-or-later
2		/* Generic linked list routine.
3		* Copyright (C) 1997, 2000 Kunihiro Ishiguro
4		*/
5
6		#include <zebra.h>
7		#include <stdlib.h>
8
9		#include "linklist.h"
10		#include "memory.h"
11		#include "libfrr_trace.h"
12
13	8	DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List");
14	8	DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node");
15	8
16	8	/* these do not cleanup list nodes and referenced data, as the functions
17	8	* do - these macros simply {de,at}tach a listnode from/to a list.
18	8	*/
19	8
20	8	/* List node attach macro. */
21	8	#define LISTNODE_ATTACH(L, N) \
22	8	do { \
23	0	(N)->prev = (L)->tail; \
24	0	(N)->next = NULL; \
25	0	if ((L)->head == NULL) \
26	0	(L)->head = (N); \
27	0	else \
28	0	(L)->tail->next = (N); \
29	0	(L)->tail = (N); \
30	0	(L)->count++; \
31	0	} while (0)
32
33		/* List node detach macro. */
34		#define LISTNODE_DETACH(L, N) \
35	0	do { \
36	0	if ((N)->prev) \
37	0	(N)->prev->next = (N)->next; \
38	0	else \
39	0	(L)->head = (N)->next; \
40	0	if ((N)->next) \
41	0	(N)->next->prev = (N)->prev; \
42	0	else \
43	0	(L)->tail = (N)->prev; \
44	0	(L)->count--; \
45	0	} while (0)
46
47		struct list *list_new(void)
48	86.6k	{
49	86.6k	return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
50	86.6k	}
51
52		/* Free list. */
53		static void list_free_internal(struct list *l)
54	84.5k	{
55	84.5k	XFREE(MTYPE_LINK_LIST, l);
56	84.5k	}
57
58
59		/* Allocate new listnode. Internal use only. */
60		static struct listnode listnode_new(struct list list, void *val)
61	332k	{
62	332k	struct listnode *node;
63
64		/* if listnode memory is managed by the app then the val
65		* passed in is the listnode
66		*/
67	332k	if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
68	0	node = val;
69	0	node->prev = node->next = NULL;
70	332k	} else {
71	332k	node = XCALLOC(MTYPE_LINK_NODE, sizeof(struct listnode));
72	332k	node->data = val;
73	332k	}
74	332k	return node;
75	332k	}
76
77		/* Free listnode. */
78		static void listnode_free(struct list list, struct listnode node)
79	323k	{
80	323k	if (!(list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP))
81	323k	XFREE(MTYPE_LINK_NODE, node);
82	323k	}
83
84		struct listnode listnode_add(struct list list, void *val)
85	239k	{
86	239k	frrtrace(2, frr_libfrr, list_add, list, val);
87
88	239k	struct listnode *node;
89
90	239k	assert(val != NULL);
91
92	239k	node = listnode_new(list, val);
93
94	239k	node->prev = list->tail;
95
96	239k	if (list->head == NULL)
97	16.0k	list->head = node;
98	223k	else
99	223k	list->tail->next = node;
100	239k	list->tail = node;
101
102	239k	list->count++;
103
104	239k	return node;
105	239k	}
106
107		void listnode_add_head(struct list list, void val)
108	0	{
109	0	struct listnode *node;
110
111	0	assert(val != NULL);
112
113	0	node = listnode_new(list, val);
114
115	0	node->next = list->head;
116
117	0	if (list->head == NULL) {
118	0	list->head = node;
119	0	list->tail = node;
120	0	} else
121	0	list->head->prev = node;
122	0	list->head = node;
123
124	0	list->count++;
125	0	}
126
127		bool listnode_add_sort_nodup(struct list list, void val)
128	0	{
129	0	struct listnode *n;
130	0	struct listnode *new;
131	0	int ret;
132	0	void *data;
133
134	0	assert(val != NULL);
135
136	0	if (list->flags & LINKLIST_FLAG_NODE_MEM_BY_APP) {
137	0	n = val;
138	0	data = n->data;
139	0	} else {
140	0	data = val;
141	0	}
142
143	0	if (list->cmp) {
144	0	for (n = list->head; n; n = n->next) {
145	0	ret = (*list->cmp)(data, n->data);
146	0	if (ret < 0) {
147	0	new = listnode_new(list, val);
148
149	0	new->next = n;
150	0	new->prev = n->prev;
151
152	0	if (n->prev)
153	0	n->prev->next = new;
154	0	else
155	0	list->head = new;
156	0	n->prev = new;
157	0	list->count++;
158	0	return true;
159	0	}
160		/* found duplicate return false */
161	0	if (ret == 0)
162	0	return false;
163	0	}
164	0	}
165
166	0	new = listnode_new(list, val);
167
168	0	LISTNODE_ATTACH(list, new);
169
170	0	return true;
171	0	}
172
173		struct list list_dup(struct list list)
174	0	{
175	0	struct list *dup;
176	0	struct listnode *node;
177	0	void *data;
178
179	0	assert(list);
180
181	0	dup = list_new();
182	0	dup->cmp = list->cmp;
183	0	dup->del = list->del;
184	0	for (ALL_LIST_ELEMENTS_RO(list, node, data))
185	0	listnode_add(dup, data);
186
187	0	return dup;
188	0	}
189
190		void listnode_add_sort(struct list list, void val)
191	93.2k	{
192	93.2k	struct listnode *n;
193	93.2k	struct listnode *new;
194
195	93.2k	assert(val != NULL);
196
197	93.2k	new = listnode_new(list, val);
198	93.2k	val = new->data;
199
200	93.2k	if (list->cmp) {
201	373k	for (n = list->head; n; n = n->next) {
202	308k	if ((*list->cmp)(val, n->data) < 0) {
203	28.4k	new->next = n;
204	28.4k	new->prev = n->prev;
205
206	28.4k	if (n->prev)
207	14.7k	n->prev->next = new;
208	13.7k	else
209	13.7k	list->head = new;
210	28.4k	n->prev = new;
211	28.4k	list->count++;
212	28.4k	return;
213	28.4k	}
214	308k	}
215	93.2k	}
216
217	64.8k	new->prev = list->tail;
218
219	64.8k	if (list->tail)
220	505	list->tail->next = new;
221	64.3k	else
222	64.3k	list->head = new;
223
224	64.8k	list->tail = new;
225	64.8k	list->count++;
226	64.8k	}
227
228		struct listnode listnode_add_after(struct list list, struct listnode *pp,
229		void *val)
230	0	{
231	0	struct listnode *nn;
232
233	0	assert(val != NULL);
234
235	0	nn = listnode_new(list, val);
236
237	0	if (pp == NULL) {
238	0	if (list->head)
239	0	list->head->prev = nn;
240	0	else
241	0	list->tail = nn;
242
243	0	nn->next = list->head;
244	0	nn->prev = pp;
245
246	0	list->head = nn;
247	0	} else {
248	0	if (pp->next)
249	0	pp->next->prev = nn;
250	0	else
251	0	list->tail = nn;
252
253	0	nn->next = pp->next;
254	0	nn->prev = pp;
255
256	0	pp->next = nn;
257	0	}
258	0	list->count++;
259	0	return nn;
260	0	}
261
262		struct listnode listnode_add_before(struct list list, struct listnode *pp,
263		void *val)
264	0	{
265	0	struct listnode *nn;
266
267	0	assert(val != NULL);
268
269	0	nn = listnode_new(list, val);
270
271	0	if (pp == NULL) {
272	0	if (list->tail)
273	0	list->tail->next = nn;
274	0	else
275	0	list->head = nn;
276
277	0	nn->prev = list->tail;
278	0	nn->next = pp;
279
280	0	list->tail = nn;
281	0	} else {
282	0	if (pp->prev)
283	0	pp->prev->next = nn;
284	0	else
285	0	list->head = nn;
286
287	0	nn->prev = pp->prev;
288	0	nn->next = pp;
289
290	0	pp->prev = nn;
291	0	}
292	0	list->count++;
293	0	return nn;
294	0	}
295
296		void listnode_move_to_tail(struct list l, struct listnode n)
297	0	{
298	0	LISTNODE_DETACH(l, n);
299	0	LISTNODE_ATTACH(l, n);
300	0	}
301
302		void listnode_delete(struct list list, const void val)
303	320k	{
304	320k	frrtrace(2, frr_libfrr, list_remove, list, val);
305
306	320k	struct listnode *node = listnode_lookup(list, val);
307
308	320k	if (node)
309	320k	list_delete_node(list, node);
310	320k	}
311
312		void listnode_head(struct list list)
313	0	{
314	0	struct listnode *node;
315
316	0	assert(list);
317	0	node = list->head;
318
319	0	if (node)
320	0	return node->data;
321	0	return NULL;
322	0	}
323
324		void list_delete_all_node(struct list *list)
325	84.5k	{
326	84.5k	struct listnode *node;
327	84.5k	struct listnode *next;
328
329	84.5k	assert(list);
330	87.6k	for (node = list->head; node; node = next) {
331	3.10k	next = node->next;
332	3.10k	if (*list->del)
333	3.10k	(*list->del)(node->data);
334	3.10k	listnode_free(list, node);
335	3.10k	}
336	84.5k	list->head = list->tail = NULL;
337	84.5k	list->count = 0;
338	84.5k	}
339
340		void list_delete(struct list **list)
341	84.5k	{
342	84.5k	assert(*list);
343	84.5k	list_delete_all_node(*list);
344	84.5k	list_free_internal(*list);
345	84.5k	*list = NULL;
346	84.5k	}
347
348		struct listnode listnode_lookup(struct list list, const void *data)
349	370k	{
350	370k	struct listnode *node;
351
352	370k	assert(list);
353	14.5M	for (node = listhead(list); node; node = listnextnode(node))
354	14.5M	if (data == listgetdata(node))
355	348k	return node;
356	22.6k	return NULL;
357	370k	}
358
359		struct listnode listnode_lookup_nocheck(struct list list, void *data)
360	0	{
361	0	if (!list)
362	0	return NULL;
363	0	return listnode_lookup(list, data);
364	0	}
365
366		void list_delete_node(struct list list, struct listnode node)
367	320k	{
368	320k	frrtrace(2, frr_libfrr, list_delete_node, list, node);
369
370	320k	if (node->prev)
371	142k	node->prev->next = node->next;
372	178k	else
373	178k	list->head = node->next;
374	320k	if (node->next)
375	175k	node->next->prev = node->prev;
376	145k	else
377	145k	list->tail = node->prev;
378	320k	list->count--;
379	320k	listnode_free(list, node);
380	320k	}
381
382		void list_sort(struct list list, int (cmp)(const void , const void ))
383	0	{
384	0	frrtrace(1, frr_libfrr, list_sort, list);
385
386	0	struct listnode ln, nn;
387	0	int i = -1;
388	0	void *data;
389	0	size_t n = list->count;
390	0	void **items;
391	0	int (realcmp)(const void , const void *) =
392	0	(int ()(const void , const void *))cmp;
393
394	0	if (!n)
395	0	return;
396
397	0	items = XCALLOC(MTYPE_TMP, (sizeof(void )) n);
398
399	0	for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
400	0	items[++i] = data;
401	0	list_delete_node(list, ln);
402	0	}
403
404	0	qsort(items, n, sizeof(void *), realcmp);
405
406	0	for (unsigned int j = 0; j < n; ++j)
407	0	listnode_add(list, items[j]);
408
409	0	XFREE(MTYPE_TMP, items);
410	0	}
411
412		struct listnode listnode_add_force(struct list list, void val)
413	0	{
414	0	if (*list == NULL)
415	0	*list = list_new();
416	0	return listnode_add(*list, val);
417	0	}
418
419		void *list_to_array(struct list list, void **arr, size_t arrlen)
420	0	{
421	0	struct listnode *ln;
422	0	void *vp;
423	0	size_t idx = 0;
424
425	0	for (ALL_LIST_ELEMENTS_RO(list, ln, vp)) {
426	0	arr[idx++] = vp;
427	0	if (idx == arrlen)
428	0	break;
429	0	}
430
431	0	return arr;
432	0	}