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