/src/CMake/Utilities/cmcurl/lib/llist.c

Source
/***************************************************************************
 *                                  _   _ ____  _
 *  Project                     ___| | | |  _ \| |
 *                             / __| | | | |_) | |
 *                            | (__| |_| |  _ <| |___
 *                             \___|\___/|_| \_\_____|
 *
 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution. The terms
 * are also available at https://curl.se/docs/copyright.html.
 *
 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
 * copies of the Software, and permit persons to whom the Software is
 * furnished to do so, under the terms of the COPYING file.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 * SPDX-License-Identifier: curl
 *
 ***************************************************************************/
#include "curl_setup.h"

#include "llist.h"

#ifdef DEBUGBUILD
#define LLISTINIT 0x100cc001 /* random pattern */
#define NODEINIT  0x12344321 /* random pattern */
#define NODEREM   0x54321012 /* random pattern */

#define VERIFYNODE(x) verifynode(x)
static struct Curl_llist_node *verifynode(struct Curl_llist_node *n)
{
  DEBUGASSERT(!n || (n->_init == NODEINIT));
  return n;
}
#else
#define VERIFYNODE(x) x
#endif
/*
 * @unittest: 1300
 */
void Curl_llist_init(struct Curl_llist *l, Curl_llist_dtor dtor)
{
  l->_size = 0;
  l->_dtor = dtor;
  l->_head = NULL;
  l->_tail = NULL;
#ifdef DEBUGBUILD
  l->_init = LLISTINIT;
#endif
}

/*
 * Curl_llist_insert_next()
 *
 * Inserts a new list element after the given one 'e'. If the given existing
 * entry is NULL and the list already has elements, the new one will be
 * inserted first in the list.
 *
 * The 'ne' argument should be a pointer into the object to store.
 *
 * @unittest: 1300
 */
void Curl_llist_insert_next(struct Curl_llist *list,
                            struct Curl_llist_node *e, /* may be NULL */
                            const void *p,
                            struct Curl_llist_node *ne)
{
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  DEBUGASSERT(ne);

#ifdef DEBUGBUILD
  ne->_init = NODEINIT;
#endif
  ne->_ptr = CURL_UNCONST(p);
  ne->_list = list;
  if(list->_size == 0) {
    list->_head = ne;
    list->_head->_prev = NULL;
    list->_head->_next = NULL;
    list->_tail = ne;
  }
  else {
    /* if 'e' is NULL here, we insert the new element first in the list */
    ne->_next = e ? e->_next : list->_head;
    ne->_prev = e;
    if(!e) {
      list->_head->_prev = ne;
      list->_head = ne;
    }
    else if(e->_next) {
      e->_next->_prev = ne;
    }
    else {
      list->_tail = ne;
    }
    if(e)
      e->_next = ne;
  }

  ++list->_size;
}

/*
 * Curl_llist_append()
 *
 * Adds a new list element to the end of the list.
 *
 * The 'ne' argument should be a pointer into the object to store.
 *
 * @unittest: 1300
 */
void Curl_llist_append(struct Curl_llist *list, const void *p,
                       struct Curl_llist_node *ne)
{
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  DEBUGASSERT(ne);
  Curl_llist_insert_next(list, list->_tail, p, ne);
}

void *Curl_node_take_elem(struct Curl_llist_node *e)
{
  void *ptr;
  struct Curl_llist *list;
  if(!e)
    return NULL;

  list = e->_list;
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  DEBUGASSERT(list->_size);
  DEBUGASSERT(e->_init == NODEINIT);
  if(list) {
    if(e == list->_head) {
      list->_head = e->_next;

      if(!list->_head)
        list->_tail = NULL;
      else
        e->_next->_prev = NULL;
    }
    else {
      if(e->_prev)
        e->_prev->_next = e->_next;

      if(!e->_next)
        list->_tail = e->_prev;
      else
        e->_next->_prev = e->_prev;
    }
    --list->_size;
  }
  ptr = e->_ptr;

  e->_list = NULL;
  e->_ptr  = NULL;
  e->_prev = NULL;
  e->_next = NULL;
#ifdef DEBUGBUILD
  e->_init = NODEREM; /* specific pattern on remove - not zero */
#endif

  return ptr;
}

/*
 * @unittest: 1300
 */
UNITTEST void Curl_node_uremove(struct Curl_llist_node *e, void *user);
UNITTEST void Curl_node_uremove(struct Curl_llist_node *e, void *user)
{
  struct Curl_llist *list;
  void *ptr;
  if(!e)
    return;

  list = e->_list;
  DEBUGASSERT(list);
  if(list) {
    ptr = Curl_node_take_elem(e);
    if(list->_dtor)
      list->_dtor(user, ptr);
  }
}

void Curl_node_remove(struct Curl_llist_node *e)
{
  Curl_node_uremove(e, NULL);
}

void Curl_llist_destroy(struct Curl_llist *list, void *user)
{
  if(list) {
    DEBUGASSERT(list->_init == LLISTINIT);
    while(list->_size > 0)
      Curl_node_uremove(list->_tail, user);
  }
}

/* Curl_llist_head() returns the first 'struct Curl_llist_node *', which
   might be NULL */
struct Curl_llist_node *Curl_llist_head(struct Curl_llist *list)
{
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  return VERIFYNODE(list->_head);
}

#ifdef UNITTESTS
/* Curl_llist_tail() returns the last 'struct Curl_llist_node *', which
   might be NULL */
struct Curl_llist_node *Curl_llist_tail(struct Curl_llist *list)
{
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  return VERIFYNODE(list->_tail);
}
#endif

/* Curl_llist_count() returns a size_t the number of nodes in the list */
size_t Curl_llist_count(struct Curl_llist *list)
{
  DEBUGASSERT(list);
  DEBUGASSERT(list->_init == LLISTINIT);
  return list->_size;
}

/* Curl_node_elem() returns the custom data from a Curl_llist_node */
void *Curl_node_elem(struct Curl_llist_node *n)
{
  DEBUGASSERT(n);
  DEBUGASSERT(n->_init == NODEINIT);
  return n->_ptr;
}

/* Curl_node_next() returns the next element in a list from a given
   Curl_llist_node */
struct Curl_llist_node *Curl_node_next(struct Curl_llist_node *n)
{
  DEBUGASSERT(n);
  DEBUGASSERT(n->_init == NODEINIT);
  return VERIFYNODE(n->_next);
}

#ifdef UNITTESTS

/* Curl_node_prev() returns the previous element in a list from a given
   Curl_llist_node */
struct Curl_llist_node *Curl_node_prev(struct Curl_llist_node *n)
{
  DEBUGASSERT(n);
  DEBUGASSERT(n->_init == NODEINIT);
  return VERIFYNODE(n->_prev);
}

#endif

struct Curl_llist *Curl_node_llist(struct Curl_llist_node *n)
{
  DEBUGASSERT(n);
  DEBUGASSERT(!n->_list || n->_init == NODEINIT);
  return n->_list;
}

Coverage Report

Created: 2026-03-12 06:35

Line	Count	Source
1		/***************************************************************************
2		* _ _ ____ _
3		* Project ___\| \| \| \| _ \\| \|
4		* / __\| \| \| \| \|_) \| \|
5		* \| (__\| \|_\| \| _ <\| \|___
6		* \___\|\___/\|_\| \_\_____\|
7		*
8		* Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
9		*
10		* This software is licensed as described in the file COPYING, which
11		* you should have received as part of this distribution. The terms
12		* are also available at https://curl.se/docs/copyright.html.
13		*
14		* You may opt to use, copy, modify, merge, publish, distribute and/or sell
15		* copies of the Software, and permit persons to whom the Software is
16		* furnished to do so, under the terms of the COPYING file.
17		*
18		* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19		* KIND, either express or implied.
20		*
21		* SPDX-License-Identifier: curl
22		*
23		***************************************************************************/
24		#include "curl_setup.h"
25
26		#include "llist.h"
27
28		#ifdef DEBUGBUILD
29		#define LLISTINIT 0x100cc001 /* random pattern */
30		#define NODEINIT 0x12344321 /* random pattern */
31		#define NODEREM 0x54321012 /* random pattern */
32
33		#define VERIFYNODE(x) verifynode(x)
34		static struct Curl_llist_node verifynode(struct Curl_llist_node n)
35		{
36		DEBUGASSERT(!n \|\| (n->_init == NODEINIT));
37		return n;
38		}
39		#else
40	0	#define VERIFYNODE(x) x
41		#endif
42		/*
43		* @unittest: 1300
44		*/
45		void Curl_llist_init(struct Curl_llist *l, Curl_llist_dtor dtor)
46	0	{
47	0	l->_size = 0;
48	0	l->_dtor = dtor;
49	0	l->_head = NULL;
50	0	l->_tail = NULL;
51		#ifdef DEBUGBUILD
52		l->_init = LLISTINIT;
53		#endif
54	0	}
55
56		/*
57		* Curl_llist_insert_next()
58		*
59		* Inserts a new list element after the given one 'e'. If the given existing
60		* entry is NULL and the list already has elements, the new one will be
61		* inserted first in the list.
62		*
63		* The 'ne' argument should be a pointer into the object to store.
64		*
65		* @unittest: 1300
66		*/
67		void Curl_llist_insert_next(struct Curl_llist *list,
68		struct Curl_llist_node e, / may be NULL */
69		const void *p,
70		struct Curl_llist_node *ne)
71	0	{
72	0	DEBUGASSERT(list);
73	0	DEBUGASSERT(list->_init == LLISTINIT);
74	0	DEBUGASSERT(ne);
75
76		#ifdef DEBUGBUILD
77		ne->_init = NODEINIT;
78		#endif
79	0	ne->_ptr = CURL_UNCONST(p);
80	0	ne->_list = list;
81	0	if(list->_size == 0) {
82	0	list->_head = ne;
83	0	list->_head->_prev = NULL;
84	0	list->_head->_next = NULL;
85	0	list->_tail = ne;
86	0	}
87	0	else {
88		/* if 'e' is NULL here, we insert the new element first in the list */
89	0	ne->_next = e ? e->_next : list->_head;
90	0	ne->_prev = e;
91	0	if(!e) {
92	0	list->_head->_prev = ne;
93	0	list->_head = ne;
94	0	}
95	0	else if(e->_next) {
96	0	e->_next->_prev = ne;
97	0	}
98	0	else {
99	0	list->_tail = ne;
100	0	}
101	0	if(e)
102	0	e->_next = ne;
103	0	}
104
105	0	++list->_size;
106	0	}
107
108		/*
109		* Curl_llist_append()
110		*
111		* Adds a new list element to the end of the list.
112		*
113		* The 'ne' argument should be a pointer into the object to store.
114		*
115		* @unittest: 1300
116		*/
117		void Curl_llist_append(struct Curl_llist list, const void p,
118		struct Curl_llist_node *ne)
119	0	{
120	0	DEBUGASSERT(list);
121	0	DEBUGASSERT(list->_init == LLISTINIT);
122	0	DEBUGASSERT(ne);
123	0	Curl_llist_insert_next(list, list->_tail, p, ne);
124	0	}
125
126		void Curl_node_take_elem(struct Curl_llist_node e)
127	0	{
128	0	void *ptr;
129	0	struct Curl_llist *list;
130	0	if(!e)
131	0	return NULL;
132
133	0	list = e->_list;
134	0	DEBUGASSERT(list);
135	0	DEBUGASSERT(list->_init == LLISTINIT);
136	0	DEBUGASSERT(list->_size);
137	0	DEBUGASSERT(e->_init == NODEINIT);
138	0	if(list) {
139	0	if(e == list->_head) {
140	0	list->_head = e->_next;
141
142	0	if(!list->_head)
143	0	list->_tail = NULL;
144	0	else
145	0	e->_next->_prev = NULL;
146	0	}
147	0	else {
148	0	if(e->_prev)
149	0	e->_prev->_next = e->_next;
150
151	0	if(!e->_next)
152	0	list->_tail = e->_prev;
153	0	else
154	0	e->_next->_prev = e->_prev;
155	0	}
156	0	--list->_size;
157	0	}
158	0	ptr = e->_ptr;
159
160	0	e->_list = NULL;
161	0	e->_ptr = NULL;
162	0	e->_prev = NULL;
163	0	e->_next = NULL;
164		#ifdef DEBUGBUILD
165		e->_init = NODEREM; /* specific pattern on remove - not zero */
166		#endif
167
168	0	return ptr;
169	0	}
170
171		/*
172		* @unittest: 1300
173		*/
174		UNITTEST void Curl_node_uremove(struct Curl_llist_node e, void user);
175		UNITTEST void Curl_node_uremove(struct Curl_llist_node e, void user)
176	0	{
177	0	struct Curl_llist *list;
178	0	void *ptr;
179	0	if(!e)
180	0	return;
181
182	0	list = e->_list;
183	0	DEBUGASSERT(list);
184	0	if(list) {
185	0	ptr = Curl_node_take_elem(e);
186	0	if(list->_dtor)
187	0	list->_dtor(user, ptr);
188	0	}
189	0	}
190
191		void Curl_node_remove(struct Curl_llist_node *e)
192	0	{
193	0	Curl_node_uremove(e, NULL);
194	0	}
195
196		void Curl_llist_destroy(struct Curl_llist list, void user)
197	0	{
198	0	if(list) {
199	0	DEBUGASSERT(list->_init == LLISTINIT);
200	0	while(list->_size > 0)
201	0	Curl_node_uremove(list->_tail, user);
202	0	}
203	0	}
204
205		/* Curl_llist_head() returns the first 'struct Curl_llist_node *', which
206		might be NULL */
207		struct Curl_llist_node Curl_llist_head(struct Curl_llist list)
208	0	{
209	0	DEBUGASSERT(list);
210	0	DEBUGASSERT(list->_init == LLISTINIT);
211	0	return VERIFYNODE(list->_head);
212	0	}
213
214		#ifdef UNITTESTS
215		/* Curl_llist_tail() returns the last 'struct Curl_llist_node *', which
216		might be NULL */
217		struct Curl_llist_node Curl_llist_tail(struct Curl_llist list)
218		{
219		DEBUGASSERT(list);
220		DEBUGASSERT(list->_init == LLISTINIT);
221		return VERIFYNODE(list->_tail);
222		}
223		#endif
224
225		/* Curl_llist_count() returns a size_t the number of nodes in the list */
226		size_t Curl_llist_count(struct Curl_llist *list)
227	0	{
228	0	DEBUGASSERT(list);
229	0	DEBUGASSERT(list->_init == LLISTINIT);
230	0	return list->_size;
231	0	}
232
233		/* Curl_node_elem() returns the custom data from a Curl_llist_node */
234		void Curl_node_elem(struct Curl_llist_node n)
235	0	{
236	0	DEBUGASSERT(n);
237	0	DEBUGASSERT(n->_init == NODEINIT);
238	0	return n->_ptr;
239	0	}
240
241		/* Curl_node_next() returns the next element in a list from a given
242		Curl_llist_node */
243		struct Curl_llist_node Curl_node_next(struct Curl_llist_node n)
244	0	{
245	0	DEBUGASSERT(n);
246	0	DEBUGASSERT(n->_init == NODEINIT);
247	0	return VERIFYNODE(n->_next);
248	0	}
249
250		#ifdef UNITTESTS
251
252		/* Curl_node_prev() returns the previous element in a list from a given
253		Curl_llist_node */
254		struct Curl_llist_node Curl_node_prev(struct Curl_llist_node n)
255		{
256		DEBUGASSERT(n);
257		DEBUGASSERT(n->_init == NODEINIT);
258		return VERIFYNODE(n->_prev);
259		}
260
261		#endif
262
263		struct Curl_llist Curl_node_llist(struct Curl_llist_node n)
264	0	{
265	0	DEBUGASSERT(n);
266	0	DEBUGASSERT(!n->_list \|\| n->_init == NODEINIT);
267	0	return n->_list;
268	0	}