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


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-07-23 06:33

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	536k	{
26	536k	l->head = NULL;
27	536k	l->tail = NULL;
28	536k	l->count = 0;
29	536k	l->size = size;
30	536k	l->dtor = dtor;
31	536k	l->persistent = persistent;
32	536k	}
33
34		ZEND_API void zend_llist_add_element(zend_llist l, const void element)
35	411k	{
36	411k	zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
37
38	411k	tmp->prev = l->tail;
39	411k	tmp->next = NULL;
40	411k	if (l->tail) {
41	108	l->tail->next = tmp;
42	411k	} else {
43	411k	l->head = tmp;
44	411k	}
45	411k	l->tail = tmp;
46	411k	memcpy(tmp->data, element, l->size);
47
48	411k	++l->count;
49	411k	}
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	137k	if ((current)->prev) {\
72	0	(current)->prev->next = (current)->next;\
73	137k	} else {\
74	137k	(l)->head = (current)->next;\
75	137k	}\
76	137k	if ((current)->next) {\
77	0	(current)->next->prev = (current)->prev;\
78	137k	} else {\
79	137k	(l)->tail = (current)->prev;\
80	137k	}\
81	137k	if ((l)->dtor) {\
82	137k	(l)->dtor((current)->data);\
83	137k	}\
84	137k	pefree((current), (l)->persistent);\
85	137k	--l->count;
86
87
88		ZEND_API void zend_llist_del_element(zend_llist l, void element, int (compare)(void element1, void *element2))
89	137k	{
90	137k	zend_llist_element *current=l->head;
91
92	137k	while (current) {
93	137k	if (compare(current->data, element)) {
94	137k	DEL_LLIST_ELEMENT(current, l);
95	137k	break;
96	137k	}
97	0	current = current->next;
98	0	}
99	137k	}
100
101
102		ZEND_API void zend_llist_destroy(zend_llist *l)
103	805k	{
104	805k	zend_llist_element current=l->head, next;
105
106	1.07M	while (current) {
107	274k	next = current->next;
108	274k	if (l->dtor) {
109	274k	l->dtor(current->data);
110	274k	}
111	274k	pefree(current, l->persistent);
112	274k	current = next;
113	274k	}
114
115	805k	l->head = NULL;
116	805k	l->tail = NULL;
117	805k	l->count = 0;
118	805k	}
119
120
121		ZEND_API void zend_llist_clean(zend_llist *l)
122	268k	{
123	268k	zend_llist_destroy(l);
124	268k	}
125
126
127		ZEND_API void zend_llist_remove_tail(zend_llist *l)
128	0	{
129	0	zend_llist_element *old_tail = l->tail;
130	0	if (!old_tail) {
131	0	return;
132	0	}
133
134	0	if (old_tail->prev) {
135	0	old_tail->prev->next = NULL;
136	0	} else {
137	0	l->head = NULL;
138	0	}
139
140	0	l->tail = old_tail->prev;
141	0	--l->count;
142
143	0	if (l->dtor) {
144	0	l->dtor(old_tail->data);
145	0	}
146	0	pefree(old_tail, l->persistent);
147	0	}
148
149
150		ZEND_API void zend_llist_copy(zend_llist dst, zend_llist src)
151	0	{
152	0	zend_llist_element *ptr;
153
154	0	zend_llist_init(dst, src->size, src->dtor, src->persistent);
155	0	ptr = src->head;
156	0	while (ptr) {
157	0	zend_llist_add_element(dst, ptr->data);
158	0	ptr = ptr->next;
159	0	}
160	0	}
161
162
163		ZEND_API void zend_llist_apply_with_del(zend_llist l, int (func)(void *data))
164	16	{
165	16	zend_llist_element element, next;
166
167	16	element=l->head;
168	20	while (element) {
169	4	next = element->next;
170	4	if (func(element->data)) {
171	0	DEL_LLIST_ELEMENT(element, l);
172	0	}
173	4	element = next;
174	4	}
175	16	}
176
177
178		ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
179	536k	{
180	536k	zend_llist_element *element;
181
182	745k	for (element=l->head; element; element=element->next) {
183	208k	func(element->data);
184	208k	}
185	536k	}
186
187		static void zend_llist_swap(zend_llist_element p, zend_llist_element q)
188	0	{
189	0	zend_llist_element *t;
190	0	t = *p;
191	0	p = q;
192	0	*q = t;
193	0	}
194
195		ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
196	0	{
197	0	size_t i;
198
199	0	zend_llist_element **elements;
200	0	zend_llist_element element, *ptr;
201
202	0	if (l->count == 0) {
203	0	return;
204	0	}
205
206	0	elements = (zend_llist_element *) emalloc(l->count sizeof(zend_llist_element *));
207
208	0	ptr = &elements[0];
209
210	0	for (element=l->head; element; element=element->next) {
211	0	*ptr++ = element;
212	0	}
213
214	0	zend_sort(elements, l->count, sizeof(zend_llist_element *),
215	0	(compare_func_t) comp_func, (swap_func_t) zend_llist_swap);
216
217	0	l->head = elements[0];
218	0	elements[0]->prev = NULL;
219
220	0	for (i = 1; i < l->count; i++) {
221	0	elements[i]->prev = elements[i-1];
222	0	elements[i-1]->next = elements[i];
223	0	}
224	0	elements[i-1]->next = NULL;
225	0	l->tail = elements[i-1];
226	0	efree(elements);
227	0	}
228
229
230		ZEND_API void zend_llist_apply_with_argument(zend_llist l, llist_apply_with_arg_func_t func, void arg)
231	268k	{
232	268k	zend_llist_element *element;
233
234	537k	for (element=l->head; element; element=element->next) {
235	268k	func(element->data, arg);
236	268k	}
237	268k	}
238
239
240		ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...)
241	4	{
242	4	zend_llist_element *element;
243	4	va_list args;
244
245	4	va_start(args, num_args);
246	4	for (element=l->head; element; element=element->next) {
247	0	func(element->data, num_args, args);
248	0	}
249	4	va_end(args);
250	4	}
251
252
253		ZEND_API size_t zend_llist_count(zend_llist *l)
254	7	{
255	7	return l->count;
256	7	}
257
258
259		ZEND_API void zend_llist_get_first_ex(zend_llist l, zend_llist_position *pos)
260	14	{
261	14	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
262
263	14	*current = l->head;
264	14	if (*current) {
265	14	return (*current)->data;
266	14	} else {
267	0	return NULL;
268	0	}
269	14	}
270
271
272		ZEND_API void zend_llist_get_last_ex(zend_llist l, zend_llist_position *pos)
273	0	{
274	0	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
275
276	0	*current = l->tail;
277	0	if (*current) {
278	0	return (*current)->data;
279	0	} else {
280	0	return NULL;
281	0	}
282	0	}
283
284
285		ZEND_API void zend_llist_get_next_ex(zend_llist l, zend_llist_position *pos)
286	14	{
287	14	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
288
289	14	if (*current) {
290	14	current = (current)->next;
291	14	if (*current) {
292	0	return (*current)->data;
293	0	}
294	14	}
295	14	return NULL;
296	14	}
297
298
299		ZEND_API void zend_llist_get_prev_ex(zend_llist l, zend_llist_position *pos)
300	0	{
301	0	zend_llist_position *current = pos ? pos : &l->traverse_ptr;
302
303	0	if (*current) {
304	0	current = (current)->prev;
305	0	if (*current) {
306	0	return (*current)->data;
307	0	}
308	0	}
309	0	return NULL;
310	0	}