/src/php-src/Zend/zend_llist.c

Source (jump to first uncovered line)
/*
   +----------------------------------------------------------------------+
   | Zend Engine                                                          |
   +----------------------------------------------------------------------+
   | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |
   +----------------------------------------------------------------------+
   | This source file is subject to version 2.00 of the Zend license,     |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.zend.com/license/2_00.txt.                                |
   | If you did not receive a copy of the Zend license and are unable to  |
   | obtain it through the world-wide-web, please send a note to          |
   | license@zend.com so we can mail you a copy immediately.              |
   +----------------------------------------------------------------------+
   | Authors: Andi Gutmans <andi@php.net>                                 |
   |          Zeev Suraski <zeev@php.net>                                 |
   +----------------------------------------------------------------------+
*/

#include "zend.h"
#include "zend_llist.h"
#include "zend_sort.h"

ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
{
  l->head  = NULL;
  l->tail  = NULL;
  l->count = 0;
  l->size  = size;
  l->dtor  = dtor;
  l->persistent = persistent;
}

ZEND_API void zend_llist_add_element(zend_llist *l, const void *element)
{
  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

  tmp->prev = l->tail;
  tmp->next = NULL;
  if (l->tail) {
    l->tail->next = tmp;
  } else {
    l->head = tmp;
  }
  l->tail = tmp;
  memcpy(tmp->data, element, l->size);

  ++l->count;
}


ZEND_API void zend_llist_prepend_element(zend_llist *l, const void *element)
{
  zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);

  tmp->next = l->head;
  tmp->prev = NULL;
  if (l->head) {
    l->head->prev = tmp;
  } else {
    l->tail = tmp;
  }
  l->head = tmp;
  memcpy(tmp->data, element, l->size);

  ++l->count;
}


#define DEL_LLIST_ELEMENT(current, l) \
      if ((current)->prev) {\
        (current)->prev->next = (current)->next;\
      } else {\
        (l)->head = (current)->next;\
      }\
      if ((current)->next) {\
        (current)->next->prev = (current)->prev;\
      } else {\
        (l)->tail = (current)->prev;\
      }\
      if ((l)->dtor) {\
        (l)->dtor((current)->data);\
      }\
      pefree((current), (l)->persistent);\
      --l->count;


ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
{
  zend_llist_element *current=l->head;

  while (current) {
    if (compare(current->data, element)) {
      DEL_LLIST_ELEMENT(current, l);
      break;
    }
    current = current->next;
  }
}


ZEND_API void zend_llist_destroy(zend_llist *l)
{
  zend_llist_element *current=l->head, *next;

  while (current) {
    next = current->next;
    if (l->dtor) {
      l->dtor(current->data);
    }
    pefree(current, l->persistent);
    current = next;
  }

  l->head  = NULL;
  l->tail  = NULL;
  l->count = 0;
}


ZEND_API void zend_llist_clean(zend_llist *l)
{
  zend_llist_destroy(l);
  l->head = l->tail = NULL;
}


ZEND_API void zend_llist_remove_tail(zend_llist *l)
{
  zend_llist_element *old_tail = l->tail;
  if (!old_tail) {
    return;
  }

  if (old_tail->prev) {
    old_tail->prev->next = NULL;
  } else {
    l->head = NULL;
  }

  l->tail = old_tail->prev;
  --l->count;

  if (l->dtor) {
    l->dtor(old_tail->data);
  }
  pefree(old_tail, l->persistent);
}


ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
{
  zend_llist_element *ptr;

  zend_llist_init(dst, src->size, src->dtor, src->persistent);
  ptr = src->head;
  while (ptr) {
    zend_llist_add_element(dst, ptr->data);
    ptr = ptr->next;
  }
}


ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
{
  zend_llist_element *element, *next;

  element=l->head;
  while (element) {
    next = element->next;
    if (func(element->data)) {
      DEL_LLIST_ELEMENT(element, l);
    }
    element = next;
  }
}


ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
{
  zend_llist_element *element;

  for (element=l->head; element; element=element->next) {
    func(element->data);
  }
}

static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)
{
  zend_llist_element *t;
  t = *p;
  *p = *q;
  *q = t;
}

ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
{
  size_t i;

  zend_llist_element **elements;
  zend_llist_element *element, **ptr;

  if (l->count == 0) {
    return;
  }

  elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));

  ptr = &elements[0];

  for (element=l->head; element; element=element->next) {
    *ptr++ = element;
  }

  zend_sort(elements, l->count, sizeof(zend_llist_element *),
      (compare_func_t) comp_func, (swap_func_t) zend_llist_swap);

  l->head = elements[0];
  elements[0]->prev = NULL;

  for (i = 1; i < l->count; i++) {
    elements[i]->prev = elements[i-1];
    elements[i-1]->next = elements[i];
  }
  elements[i-1]->next = NULL;
  l->tail = elements[i-1];
  efree(elements);
}


ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg)
{
  zend_llist_element *element;

  for (element=l->head; element; element=element->next) {
    func(element->data, arg);
  }
}


ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)
{
  zend_llist_element *element;
  va_list args;

  va_start(args, num_args);
  for (element=l->head; element; element=element->next) {
    func(element->data, num_args, args);
  }
  va_end(args);
}


ZEND_API size_t zend_llist_count(zend_llist *l)
{
  return l->count;
}


ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
{
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  *current = l->head;
  if (*current) {
    return (*current)->data;
  } else {
    return NULL;
  }
}


ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
{
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  *current = l->tail;
  if (*current) {
    return (*current)->data;
  } else {
    return NULL;
  }
}


ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
{
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  if (*current) {
    *current = (*current)->next;
    if (*current) {
      return (*current)->data;
    }
  }
  return NULL;
}


ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
{
  zend_llist_position *current = pos ? pos : &l->traverse_ptr;

  if (*current) {
    *current = (*current)->prev;
    if (*current) {
      return (*current)->data;
    }
  }
  return NULL;
}

Coverage Report

Created: 2025-06-13 06:43

Line	Count	Source (jump to first uncovered line)
1		/*
2		+----------------------------------------------------------------------+
3		\| Zend Engine \|
4		+----------------------------------------------------------------------+
5		\| Copyright (c) Zend Technologies Ltd. (http://www.zend.com) \|
6		+----------------------------------------------------------------------+
7		\| This source file is subject to version 2.00 of the Zend license, \|
8		\| that is bundled with this package in the file LICENSE, and is \|
9		\| available through the world-wide-web at the following url: \|
10		\| http://www.zend.com/license/2_00.txt. \|
11		\| If you did not receive a copy of the Zend license and are unable to \|
12		\| obtain it through the world-wide-web, please send a note to \|
13		\| license@zend.com so we can mail you a copy immediately. \|
14		+----------------------------------------------------------------------+
15		\| Authors: Andi Gutmans <andi@php.net> \|
16		\| Zeev Suraski <zeev@php.net> \|
17		+----------------------------------------------------------------------+
18		*/
19
20		#include "zend.h"
21		#include "zend_llist.h"
22		#include "zend_sort.h"
23
24		ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
25	600k	{
26	600k	l->head = NULL;
27	600k	l->tail = NULL;
28	600k	l->count = 0;
29	600k	l->size = size;
30	600k	l->dtor = dtor;
31	600k	l->persistent = persistent;
32	600k	}
33
34		ZEND_API void zend_llist_add_element(zend_llist l, const void element)
35	444k	{
36	444k	zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
37
38	444k	tmp->prev = l->tail;
39	444k	tmp->next = NULL;
40	444k	if (l->tail) {
41	69	l->tail->next = tmp;
42	444k	} else {
43	444k	l->head = tmp;
44	444k	}
45	444k	l->tail = tmp;
46	444k	memcpy(tmp->data, element, l->size);
47
48	444k	++l->count;
49	444k	}
50
51
52		ZEND_API void zend_llist_prepend_element(zend_llist l, const void element)
53	0	{
54	0	zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
55
56	0	tmp->next = l->head;
57	0	tmp->prev = NULL;
58	0	if (l->head) {
59	0	l->head->prev = tmp;
60	0	} else {
61	0	l->tail = tmp;
62	0	}
63	0	l->head = tmp;
64	0	memcpy(tmp->data, element, l->size);
65
66	0	++l->count;
67	0	}
68
69
70		#define DEL_LLIST_ELEMENT(current, l) \
71	138k	if ((current)->prev) {\
72	0	(current)->prev->next = (current)->next;\
73	138k	} else {\
74	138k	(l)->head = (current)->next;\
75	138k	}\
76	138k	if ((current)->next) {\
77	0	(current)->next->prev = (current)->prev;\
78	138k	} else {\
79	138k	(l)->tail = (current)->prev;\
80	138k	}\
81	138k	if ((l)->dtor) {\
82	138k	(l)->dtor((current)->data);\
83	138k	}\
84	138k	pefree((current), (l)->persistent);\
85	138k	--l->count;
86
87
88		ZEND_API void zend_llist_del_element(zend_llist l, void element, int (compare)(void element1, void *element2))
89	138k	{
90	138k	zend_llist_element *current=l->head;
91
92	138k	while (current) {
93	138k	if (compare(current->data, element)) {
94	138k	DEL_LLIST_ELEMENT(current, l);
95	138k	break;
96	138k	}
97	0	current = current->next;
98	0	}
99	138k	}
100
101
102		ZEND_API void zend_llist_destroy(zend_llist *l)
103	900k	{
104	900k	zend_llist_element current=l->head, next;
105
106	1.20M	while (current) {
107	306k	next = current->next;
108	306k	if (l->dtor) {
109	306k	l->dtor(current->data);
110	306k	}
111	306k	pefree(current, l->persistent);
112	306k	current = next;
113	306k	}
114
115	900k	l->head = NULL;
116	900k	l->tail = NULL;
117	900k	l->count = 0;
118	900k	}
119
120
121		ZEND_API void zend_llist_clean(zend_llist *l)
122	300k	{
123	300k	zend_llist_destroy(l);
124	300k	l->head = l->tail = NULL;
125	300k	}
126
127
128		ZEND_API void zend_llist_remove_tail(zend_llist *l)
129	0	{
130	0	zend_llist_element *old_tail = l->tail;
131	0	if (!old_tail) {
132	0	return;
133	0	}
134
135	0	if (old_tail->prev) {
136	0	old_tail->prev->next = NULL;
137	0	} else {
138	0	l->head = NULL;
139	0	}
140
141	0	l->tail = old_tail->prev;
142	0	--l->count;
143
144	0	if (l->dtor) {
145	0	l->dtor(old_tail->data);
146	0	}
147	0	pefree(old_tail, l->persistent);
148	0	}
149
150
151		ZEND_API void zend_llist_copy(zend_llist dst, zend_llist src)
152	0	{
153	0	zend_llist_element *ptr;
154
155	0	zend_llist_init(dst, src->size, src->dtor, src->persistent);
156	0	ptr = src->head;
157	0	while (ptr) {
158	0	zend_llist_add_element(dst, ptr->data);
159	0	ptr = ptr->next;
160	0	}
161	0	}
162
163
164		ZEND_API void zend_llist_apply_with_del(zend_llist l, int (func)(void *data))
165	16	{
166	16	zend_llist_element element, next;
167
168	16	element=l->head;
169	20	while (element) {
170	4	next = element->next;
171	4	if (func(element->data)) {
172	0	DEL_LLIST_ELEMENT(element, l);
173	0	}
174	4	element = next;
175	4	}
176	16	}
177
178
179		ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
180	600k	{
181	600k	zend_llist_element *element;
182
183	798k	for (element=l->head; element; element=element->next) {
184	197k	func(element->data);
185	197k	}
186	600k	}
187
188		static void zend_llist_swap(zend_llist_element p, zend_llist_element q)
189	0	{
190	0	zend_llist_element *t;
191	0	t = *p;
192	0	p = q;
193	0	*q = t;
194	0	}
195
196		ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
197	0	{
198	0	size_t i;
199
200	0	zend_llist_element **elements;
201	0	zend_llist_element element, *ptr;
202
203	0	if (l->count == 0) {
204	0	return;
205	0	}
206
207	0	elements = (zend_llist_element *) emalloc(l->count sizeof(zend_llist_element *));
208
209	0	ptr = &elements[0];
210
211	0	for (element=l->head; element; element=element->next) {
212	0	*ptr++ = element;
213	0	}
214
215	0	zend_sort(elements, l->count, sizeof(zend_llist_element *),
216	0	(compare_func_t) comp_func, (swap_func_t) zend_llist_swap);
217
218	0	l->head = elements[0];
219	0	elements[0]->prev = NULL;
220
221	0	for (i = 1; i < l->count; i++) {
222	0	elements[i]->prev = elements[i-1];
223	0	elements[i-1]->next = elements[i];
224	0	}
225	0	elements[i-1]->next = NULL;
226	0	l->tail = elements[i-1];
227	0	efree(elements);
228	0	}
229
230
231		ZEND_API void zend_llist_apply_with_argument(zend_llist l, llist_apply_with_arg_func_t func, void arg)
232	300k	{
233	300k	zend_llist_element *element;
234
235	600k	for (element=l->head; element; element=element->next) {
236	300k	func(element->data, arg);
237	300k	}
238	300k	}
239
240
241		ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)
242	4	{
243	4	zend_llist_element *element;
244	4	va_list args;
245
246	4	va_start(args, num_args);
247	4	for (element=l->head; element; element=element->next) {
248	0	func(element->data, num_args, args);
249	0	}
250	4	va_end(args);
251	4	}
252
253
254		ZEND_API size_t zend_llist_count(zend_llist *l)
255	12	{
256	12	return l->count;
257	12	}
258
259
260		ZEND_API void zend_llist_get_first_ex(zend_llist l, zend_llist_position *pos)
261	24	{
262	24	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
263
264	24	*current = l->head;
265	24	if (*current) {
266	24	return (*current)->data;
267	24	} else {
268	0	return NULL;
269	0	}
270	24	}
271
272
273		ZEND_API void zend_llist_get_last_ex(zend_llist l, zend_llist_position *pos)
274	0	{
275	0	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
276
277	0	*current = l->tail;
278	0	if (*current) {
279	0	return (*current)->data;
280	0	} else {
281	0	return NULL;
282	0	}
283	0	}
284
285
286		ZEND_API void zend_llist_get_next_ex(zend_llist l, zend_llist_position *pos)
287	24	{
288	24	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
289
290	24	if (*current) {
291	24	current = (current)->next;
292	24	if (*current) {
293	0	return (*current)->data;
294	0	}
295	24	}
296	24	return NULL;
297	24	}
298
299
300		ZEND_API void zend_llist_get_prev_ex(zend_llist l, zend_llist_position *pos)
301	0	{
302	0	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
303
304	0	if (*current) {
305	0	current = (current)->prev;
306	0	if (*current) {
307	0	return (*current)->data;
308	0	}
309	0	}
310	0	return NULL;
311	0	}