[mirror_frr.git] / lib / linklist.h

/* Generic linked list
 * 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
 */

#ifndef _ZEBRA_LINKLIST_H
#define _ZEBRA_LINKLIST_H

#ifdef __cplusplus
extern "C" {
#endif

/* listnodes must always contain data to be valid. Adding an empty node
 * to a list is invalid
 */
struct listnode {
	struct listnode *next;
	struct listnode *prev;

	/* private member, use getdata() to retrieve, do not access directly */
	void *data;
};

struct list {
	struct listnode *head;
	struct listnode *tail;

	/* invariant: count is the number of listnodes in the list */
	unsigned int count;

	uint8_t flags;
/* Indicates that listnode memory is managed by the application and
 * doesn't need to be freed by this library via listnode_delete etc.
 */
#define LINKLIST_FLAG_NODE_MEM_BY_APP (1 << 0)

	/*
	 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
	 * Used as definition of sorted for listnode_add_sort
	 */
	int (*cmp)(void *val1, void *val2);

	/* callback to free user-owned data when listnode is deleted. supplying
	 * this callback is very much encouraged!
	 */
	void (*del)(void *val);
};

#define listnextnode(X) ((X) ? ((X)->next) : NULL)
#define listnextnode_unchecked(X) ((X)->next)
#define listhead(X) ((X) ? ((X)->head) : NULL)
#define listhead_unchecked(X) ((X)->head)
#define listtail(X) ((X) ? ((X)->tail) : NULL)
#define listtail_unchecked(X) ((X)->tail)
#define listcount(X) ((X)->count)
#define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
/* return X->data only if X and X->data are not NULL */
#define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
/* App is going to manage listnode memory */
#define listset_app_node_mem(X) ((X)->flags |= LINKLIST_FLAG_NODE_MEM_BY_APP)
#define listnode_init(X, val) ((X)->data = (val))

/*
 * Create a new linked list.
 *
 * Returns:
 *    the created linked list
 */
extern struct list *list_new(void);

/*
 * Add a new element to the tail of a list.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * data
 *    element to add
 */
extern struct listnode *listnode_add(struct list *list, void *data);

/*
 * Add a new element to the beginning of a list.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * data
 *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 */
extern void listnode_add_head(struct list *list, void *data);

/*
 * Insert a new element into a list with insertion sort.
 *
 * If list->cmp is set, this function is used to determine the position to
 * insert the new element. If it is not set, this function is equivalent to
 * listnode_add.
 *
 * Runtime is O(N).
 *
 * list
 *    list to operate on
 *
 * val
 *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 */
extern void listnode_add_sort(struct list *list, void *val);

/*
 * Insert a new element into a list after another element.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * pp
 *    listnode to insert after
 *
 * data
 *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 *
 * Returns:
 *    pointer to newly created listnode that contains the inserted data
 */
extern struct listnode *listnode_add_after(struct list *list,
					   struct listnode *pp, void *data);

/*
 * Insert a new element into a list before another element.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * pp
 *    listnode to insert before
 *
 * data
 *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 *
 * Returns:
 *    pointer to newly created listnode that contains the inserted data
 */
extern struct listnode *listnode_add_before(struct list *list,
					    struct listnode *pp, void *data);

/*
 * Move a node to the tail of a list.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * node
 *    node to move to tail
 */
extern void listnode_move_to_tail(struct list *list, struct listnode *node);

/*
 * Delete an element from a list.
 *
 * Runtime is O(N).
 *
 * list
 *    list to operate on
 *
 * data
 *    data to insert into list
 */
extern void listnode_delete(struct list *list, const void *data);

/*
 * Find the listnode corresponding to an element in a list.
 *
 * list
 *    list to operate on
 *
 * data
 *    data to search for
 *
 * Returns:
 *    pointer to listnode storing the given data if found, NULL otherwise
 */
extern struct listnode *listnode_lookup(struct list *list, const void *data);

/*
 * Retrieve the element at the head of a list.
 *
 * list
 *    list to operate on
 *
 * Returns:
 *    data at head of list, or NULL if list is empty
 */
extern void *listnode_head(struct list *list);

/*
 * Sort a list in place.
 *
 * The sorting algorithm used is quicksort. Runtimes are equivalent to those of
 * quicksort plus N. The sort is not stable.
 *
 * For portability reasons, the comparison function takes a pointer to pointer
 * to void. This pointer should be dereferenced to get the actual data pointer.
 * It is always safe to do this.
 *
 * list
 *    list to sort
 *
 * cmp
 *    comparison function for quicksort. Should return less than, equal to or
 *    greater than zero if the first argument is less than, equal to or greater
 *    than the second argument.
 */
extern void list_sort(struct list *list,
		      int (*cmp)(const void **, const void **));

/*
 * Convert a list to an array of void pointers.
 *
 * Starts from the list head and ends either on the last node of the list or
 * when the provided array cannot store any more elements.
 *
 * list
 *    list to convert
 *
 * arr
 *    Pre-allocated array of void *
 *
 * arrlen
 *    Number of elements in arr
 *
 * Returns:
 *    arr
 */
void **list_to_array(struct list *list, void **arr, size_t arrlen);

/*
 * Delete a list and NULL its pointer.
 *
 * If non-null, list->del is called with each data element.
 *
 * plist
 *    pointer to list pointer; this will be set to NULL after the list has been
 *    deleted
 */
extern void list_delete(struct list **plist);

/*
 * Delete all nodes from a list without deleting the list itself.
 *
 * If non-null, list->del is called with each data element.
 *
 * list
 *    list to operate on
 */
extern void list_delete_all_node(struct list *list);

/*
 * Delete a node from a list.
 *
 * list->del is not called with the data associated with the node.
 *
 * Runtime is O(1).
 *
 * list
 *    list to operate on
 *
 * node
 *    the node to delete
 */
extern void list_delete_node(struct list *list, struct listnode *node);

/*
 * Insert a new element into a list with insertion sort if there is no
 * duplicate element present in the list. This assumes the input list is
 * sorted. If unsorted, it will check for duplicate until it finds out
 * the position to do insertion sort with the unsorted list.
 *
 * If list->cmp is set, this function is used to determine the position to
 * insert the new element. If it is not set, this function is equivalent to
 * listnode_add. duplicate element is determined by cmp function returning 0.
 *
 * Runtime is O(N).
 *
 * list
 *    list to operate on
 *
 * val
 *    If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
 */

extern bool listnode_add_sort_nodup(struct list *list, void *val);

/*
 * Duplicate the specified list, creating a shallow copy of each of its
 * elements.
 *
 * list
 *    list to duplicate
 *
 * Returns:
 *    the duplicated list
 */
extern struct list *list_dup(struct list *list);

/* List iteration macro.
 * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
 * It is safe to delete the listnode using this macro.
 */
#define ALL_LIST_ELEMENTS(list, node, nextnode, data)                          \
	(node) = listhead(list), ((data) = NULL);                              \
	(node) != NULL                                                         \
		&& ((data) = static_cast(data, listgetdata(node)),             \
		    (nextnode) = node->next, 1);                               \
	(node) = (nextnode), ((data) = NULL)

/* read-only list iteration macro.
 * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 * use this macro when it is *immediately obvious* the listnode is not
 * deleted in the body of the loop. Does not have forward-reference overhead
 * of previous macro.
 */
#define ALL_LIST_ELEMENTS_RO(list, node, data)                                 \
	(node) = listhead(list), ((data) = NULL);                              \
	(node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1);  \
	(node) = listnextnode(node), ((data) = NULL)

/* 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)

extern struct listnode *listnode_lookup_nocheck(struct list *list, void *data);

/*
 * Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail
 * it back in *list, and add a new node.
 *
 * Return: the new node.
 */
extern struct listnode *listnode_add_force(struct list **list, void *val);

#ifdef __cplusplus
}
#endif

#endif /* _ZEBRA_LINKLIST_H */
Commit	Line	Data
718e3744	1	/* Generic linked list
	2	* Copyright (C) 1997, 2000 Kunihiro Ishiguro
	3	*
	4	* This file is part of GNU Zebra.
	5	*
	6	* GNU Zebra is free software; you can redistribute it and/or modify it
	7	* under the terms of the GNU General Public License as published by the
	8	* Free Software Foundation; either version 2, or (at your option) any
	9	* later version.
	10	*
	11	* GNU Zebra is distributed in the hope that it will be useful, but
	12	* WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	* General Public License for more details.
	15	*
896014f4 DL	16	* You should have received a copy of the GNU General Public License along
	17	* with this program; see the file COPYING; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
718e3744	19	*/
	20
	21	#ifndef _ZEBRA_LINKLIST_H
	22	#define _ZEBRA_LINKLIST_H
	23
5e244469 RW	24	#ifdef __cplusplus
	25	extern "C" {
	26	#endif
	27
1eb8ef25	28	/* listnodes must always contain data to be valid. Adding an empty node
	29	* to a list is invalid
	30	*/
d62a17ae	31	struct listnode {
	32	struct listnode *next;
	33	struct listnode *prev;
	34
	35	/* private member, use getdata() to retrieve, do not access directly */
	36	void *data;
718e3744	37	};
718e3744	38
d62a17ae	39	struct list {
	40	struct listnode *head;
	41	struct listnode *tail;
1eb8ef25	42
d62a17ae	43	/* invariant: count is the number of listnodes in the list */
d62a17ae	44	unsigned int count;
1eb8ef25	45
5c733b88 AK	46	uint8_t flags;
	47	/* Indicates that listnode memory is managed by the application and
	48	* doesn't need to be freed by this library via listnode_delete etc.
	49	*/
	50	#define LINKLIST_FLAG_NODE_MEM_BY_APP (1 << 0)
	51
d62a17ae	52	/*
	53	* Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
	54	* Used as definition of sorted for listnode_add_sort
	55	*/
	56	int (cmp)(void val1, void *val2);
1eb8ef25	57
d62a17ae	58	/* callback to free user-owned data when listnode is deleted. supplying
	59	* this callback is very much encouraged!
	60	*/
	61	void (del)(void val);
718e3744	62	};
718e3744	63
54dd6122	64	#define listnextnode(X) ((X) ? ((X)->next) : NULL)
39050c7e	65	#define listnextnode_unchecked(X) ((X)->next)
54dd6122	66	#define listhead(X) ((X) ? ((X)->head) : NULL)
64268e1a	67	#define listhead_unchecked(X) ((X)->head)
54dd6122	68	#define listtail(X) ((X) ? ((X)->tail) : NULL)
5c733b88	69	#define listtail_unchecked(X) ((X)->tail)
718e3744	70	#define listcount(X) ((X)->count)
718e3744	71	#define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
67533c11 VJ	72	/* return X->data only if X and X->data are not NULL */
67533c11 VJ	73	#define listgetdata(X) (assert(X), assert((X)->data != NULL), (X)->data)
5c733b88 AK	74	/* App is going to manage listnode memory */
	75	#define listset_app_node_mem(X) ((X)->flags \|= LINKLIST_FLAG_NODE_MEM_BY_APP)
	76	#define listnode_init(X, val) ((X)->data = (val))
718e3744	77
6fd8c487 QY	78	/*
	79	* Create a new linked list.
	80	*
	81	* Returns:
	82	* the created linked list
	83	*/
	84	extern struct list *list_new(void);
	85
	86	/*
	87	* Add a new element to the tail of a list.
	88	*
	89	* Runtime is O(1).
	90	*
	91	* list
	92	* list to operate on
	93	*
	94	* data
	95	* element to add
	96	*/
315999e9	97	extern struct listnode listnode_add(struct list list, void *data);
6fd8c487	98
9ea82f28 RW	99	/*
	100	* Add a new element to the beginning of a list.
	101	*
	102	* Runtime is O(1).
	103	*
	104	* list
	105	* list to operate on
	106	*
	107	* data
5c733b88	108	* If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
9ea82f28 RW	109	*/
	110	extern void listnode_add_head(struct list list, void data);
	111
6fd8c487 QY	112	/*
	113	* Insert a new element into a list with insertion sort.
	114	*
	115	* If list->cmp is set, this function is used to determine the position to
	116	* insert the new element. If it is not set, this function is equivalent to
	117	* listnode_add.
	118	*
	119	* Runtime is O(N).
	120	*
	121	* list
	122	* list to operate on
	123	*
	124	* val
5c733b88	125	* If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
6fd8c487 QY	126	*/
	127	extern void listnode_add_sort(struct list list, void val);
	128
	129	/*
	130	* Insert a new element into a list after another element.
	131	*
	132	* Runtime is O(1).
	133	*
	134	* list
	135	* list to operate on
	136	*
	137	* pp
	138	* listnode to insert after
	139	*
	140	* data
5c733b88	141	* If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
6fd8c487 QY	142	*
	143	* Returns:
	144	* pointer to newly created listnode that contains the inserted data
	145	*/
	146	extern struct listnode listnode_add_after(struct list list,
	147	struct listnode pp, void data);
	148
	149	/*
	150	* Insert a new element into a list before another element.
	151	*
	152	* Runtime is O(1).
	153	*
	154	* list
	155	* list to operate on
	156	*
	157	* pp
	158	* listnode to insert before
	159	*
	160	* data
5c733b88	161	* If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
6fd8c487 QY	162	*
	163	* Returns:
	164	* pointer to newly created listnode that contains the inserted data
	165	*/
	166	extern struct listnode listnode_add_before(struct list list,
	167	struct listnode pp, void data);
	168
	169	/*
	170	* Move a node to the tail of a list.
	171	*
	172	* Runtime is O(1).
	173	*
	174	* list
	175	* list to operate on
	176	*
	177	* node
	178	* node to move to tail
	179	*/
	180	extern void listnode_move_to_tail(struct list list, struct listnode node);
	181
	182	/*
	183	* Delete an element from a list.
	184	*
	185	* Runtime is O(N).
	186	*
	187	* list
	188	* list to operate on
	189	*
	190	* data
	191	* data to insert into list
	192	*/
396cd636	193	extern void listnode_delete(struct list list, const void data);
6fd8c487 QY	194
	195	/*
	196	* Find the listnode corresponding to an element in a list.
	197	*
	198	* list
	199	* list to operate on
	200	*
	201	* data
	202	* data to search for
	203	*
	204	* Returns:
	205	* pointer to listnode storing the given data if found, NULL otherwise
	206	*/
396cd636	207	extern struct listnode listnode_lookup(struct list list, const void *data);
6fd8c487 QY	208
	209	/*
	210	* Retrieve the element at the head of a list.
	211	*
	212	* list
	213	* list to operate on
	214	*
	215	* Returns:
	216	* data at head of list, or NULL if list is empty
	217	*/
	218	extern void listnode_head(struct list list);
	219
6fd8c487 QY	220	/*
	221	* Sort a list in place.
	222	*
	223	* The sorting algorithm used is quicksort. Runtimes are equivalent to those of
	224	* quicksort plus N. The sort is not stable.
	225	*
	226	* For portability reasons, the comparison function takes a pointer to pointer
	227	* to void. This pointer should be dereferenced to get the actual data pointer.
	228	* It is always safe to do this.
	229	*
	230	* list
	231	* list to sort
	232	*
	233	* cmp
	234	* comparison function for quicksort. Should return less than, equal to or
	235	* greater than zero if the first argument is less than, equal to or greater
	236	* than the second argument.
	237	*/
3a5c3bcb	238	extern void list_sort(struct list *list,
6fd8c487	239	int (cmp)(const void , const void *));
4440e3cd QY	240
	241	/*
	242	* Convert a list to an array of void pointers.
	243	*
	244	* Starts from the list head and ends either on the last node of the list or
	245	* when the provided array cannot store any more elements.
	246	*
	247	* list
	248	* list to convert
	249	*
	250	* arr
	251	* Pre-allocated array of void *
	252	*
	253	* arrlen
	254	* Number of elements in arr
	255	*
	256	* Returns:
	257	* arr
	258	*/
	259	void *list_to_array(struct list list, void **arr, size_t arrlen);
d62a17ae	260
6fd8c487 QY	261	/*
	262	* Delete a list and NULL its pointer.
	263	*
	264	* If non-null, list->del is called with each data element.
	265	*
	266	* plist
	267	* pointer to list pointer; this will be set to NULL after the list has been
	268	* deleted
	269	*/
6a154c88	270	extern void list_delete(struct list **plist);
6fd8c487	271
6fd8c487 QY	272	/*
	273	* Delete all nodes from a list without deleting the list itself.
	274	*
	275	* If non-null, list->del is called with each data element.
	276	*
	277	* list
	278	* list to operate on
	279	*/
	280	extern void list_delete_all_node(struct list *list);
718e3744	281
6fd8c487 QY	282	/*
	283	* Delete a node from a list.
	284	*
	285	* list->del is not called with the data associated with the node.
	286	*
	287	* Runtime is O(1).
	288	*
	289	* list
	290	* list to operate on
	291	*
	292	* node
	293	* the node to delete
	294	*/
	295	extern void list_delete_node(struct list list, struct listnode node);
718e3744	296
9b68e496	297	/*
	298	* Insert a new element into a list with insertion sort if there is no
	299	* duplicate element present in the list. This assumes the input list is
	300	* sorted. If unsorted, it will check for duplicate until it finds out
	301	* the position to do insertion sort with the unsorted list.
	302	*
	303	* If list->cmp is set, this function is used to determine the position to
	304	* insert the new element. If it is not set, this function is equivalent to
	305	* listnode_add. duplicate element is determined by cmp function returning 0.
	306	*
	307	* Runtime is O(N).
	308	*
	309	* list
	310	* list to operate on
	311	*
	312	* val
5c733b88	313	* If MEM_BY_APP is set this is listnode. Otherwise it is element to add.
9b68e496	314	*/
	315
	316	extern bool listnode_add_sort_nodup(struct list list, void val);
0f166881 RW	317
	318	/*
	319	* Duplicate the specified list, creating a shallow copy of each of its
	320	* elements.
	321	*
	322	* list
	323	* list to duplicate
	324	*
	325	* Returns:
	326	* the duplicated list
	327	*/
	328	extern struct list list_dup(struct list list);
	329
d62a17ae	330	/* List iteration macro.
1eb8ef25	331	* Usage: for (ALL_LIST_ELEMENTS (...) { ... }
	332	* It is safe to delete the listnode using this macro.
	333	*/
d62a17ae	334	#define ALL_LIST_ELEMENTS(list, node, nextnode, data) \
	335	(node) = listhead(list), ((data) = NULL); \
	336	(node) != NULL \
343cd13e RW	337	&& ((data) = static_cast(data, listgetdata(node)), \
343cd13e RW	338	(nextnode) = node->next, 1); \
d62a17ae	339	(node) = (nextnode), ((data) = NULL)
1eb8ef25	340
	341	/* read-only list iteration macro.
	342	* Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
	343	* use this macro when it is immediately obvious the listnode is not
	344	* deleted in the body of the loop. Does not have forward-reference overhead
	345	* of previous macro.
	346	*/
d62a17ae	347	#define ALL_LIST_ELEMENTS_RO(list, node, data) \
d62a17ae	348	(node) = listhead(list), ((data) = NULL); \
343cd13e	349	(node) != NULL && ((data) = static_cast(data, listgetdata(node)), 1); \
d62a17ae	350	(node) = listnextnode(node), ((data) = NULL)
718e3744	351
1eb8ef25	352	/* these do not cleanup list nodes and referenced data, as the functions
	353	* do - these macros simply {de,at}tach a listnode from/to a list.
	354	*/
d62a17ae	355
1eb8ef25	356	/* List node attach macro. */
d62a17ae	357	#define LISTNODE_ATTACH(L, N) \
	358	do { \
	359	(N)->prev = (L)->tail; \
	360	(N)->next = NULL; \
	361	if ((L)->head == NULL) \
	362	(L)->head = (N); \
	363	else \
	364	(L)->tail->next = (N); \
	365	(L)->tail = (N); \
	366	(L)->count++; \
	367	} while (0)
718e3744	368
1eb8ef25	369	/* List node detach macro. */
d62a17ae	370	#define LISTNODE_DETACH(L, N) \
	371	do { \
	372	if ((N)->prev) \
	373	(N)->prev->next = (N)->next; \
	374	else \
	375	(L)->head = (N)->next; \
	376	if ((N)->next) \
	377	(N)->next->prev = (N)->prev; \
	378	else \
	379	(L)->tail = (N)->prev; \
	380	(L)->count--; \
	381	} while (0)
718e3744	382
2fe55afe PG	383	extern struct listnode listnode_lookup_nocheck(struct list list, void *data);
2fe55afe PG	384
75839aab MS	385	/*
	386	* Add a node to *list, if non-NULL. Otherwise, allocate a new list, mail
	387	* it back in *list, and add a new node.
	388	*
	389	* Return: the new node.
	390	*/
	391	extern struct listnode listnode_add_force(struct list list, void val);
33bca8a1	392
5e244469 RW	393	#ifdef __cplusplus
	394	}
	395	#endif
	396
718e3744	397	#endif /* _ZEBRA_LINKLIST_H */