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