1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2013 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 zend_llist_element *next;
95
96 while (current) {
97 next = current->next;
98 if (compare(current->data, element)) {
99 DEL_LLIST_ELEMENT(current, l);
100 break;
101 }
102 current = next;
103 }
104 }
105
106
zend_llist_destroy(zend_llist * l)107 ZEND_API void zend_llist_destroy(zend_llist *l)
108 {
109 zend_llist_element *current=l->head, *next;
110
111 while (current) {
112 next = current->next;
113 if (l->dtor) {
114 l->dtor(current->data);
115 }
116 pefree(current, l->persistent);
117 current = next;
118 }
119
120 l->count = 0;
121 }
122
123
zend_llist_clean(zend_llist * l)124 ZEND_API void zend_llist_clean(zend_llist *l)
125 {
126 zend_llist_destroy(l);
127 l->head = l->tail = NULL;
128 }
129
130
zend_llist_remove_tail(zend_llist * l)131 ZEND_API void *zend_llist_remove_tail(zend_llist *l)
132 {
133 zend_llist_element *old_tail;
134 void *data;
135
136 if ((old_tail = l->tail)) {
137 if (old_tail->prev) {
138 old_tail->prev->next = NULL;
139 } else {
140 l->head = NULL;
141 }
142
143 data = old_tail->data;
144
145 l->tail = old_tail->prev;
146 if (l->dtor) {
147 l->dtor(data);
148 }
149 pefree(old_tail, l->persistent);
150
151 --l->count;
152
153 return data;
154 }
155
156 return NULL;
157 }
158
159
zend_llist_copy(zend_llist * dst,zend_llist * src)160 ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
161 {
162 zend_llist_element *ptr;
163
164 zend_llist_init(dst, src->size, src->dtor, src->persistent);
165 ptr = src->head;
166 while (ptr) {
167 zend_llist_add_element(dst, ptr->data);
168 ptr = ptr->next;
169 }
170 }
171
172
zend_llist_apply_with_del(zend_llist * l,int (* func)(void * data))173 ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
174 {
175 zend_llist_element *element, *next;
176
177 element=l->head;
178 while (element) {
179 next = element->next;
180 if (func(element->data)) {
181 DEL_LLIST_ELEMENT(element, l);
182 }
183 element = next;
184 }
185 }
186
187
zend_llist_apply(zend_llist * l,llist_apply_func_t func TSRMLS_DC)188 ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
189 {
190 zend_llist_element *element;
191
192 for (element=l->head; element; element=element->next) {
193 func(element->data TSRMLS_CC);
194 }
195 }
196
zend_llist_sort(zend_llist * l,llist_compare_func_t comp_func TSRMLS_DC)197 ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
198 {
199 size_t i;
200
201 zend_llist_element **elements;
202 zend_llist_element *element, **ptr;
203
204 if (l->count <= 0) {
205 return;
206 }
207
208 elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
209
210 ptr = &elements[0];
211
212 for (element=l->head; element; element=element->next) {
213 *ptr++ = element;
214 }
215
216 zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
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 TSRMLS_DC)231 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC)
232 {
233 zend_llist_element *element;
234
235 for (element=l->head; element; element=element->next) {
236 func(element->data, arg TSRMLS_CC);
237 }
238 }
239
240
zend_llist_apply_with_arguments(zend_llist * l,llist_apply_with_args_func_t func TSRMLS_DC,int num_args,...)241 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, 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 TSRMLS_CC);
249 }
250 va_end(args);
251 }
252
253
zend_llist_count(zend_llist * l)254 ZEND_API int 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
