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
zend_llist_init(zend_llist * l,size_t size,llist_dtor_func_t dtor,unsigned char persistent)24 ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
25 {
26 l->head = NULL;
27 l->tail = NULL;
28 l->count = 0;
29 l->size = size;
30 l->dtor = dtor;
31 l->persistent = persistent;
32 }
33
zend_llist_add_element(zend_llist * l,const void * element)34 ZEND_API void zend_llist_add_element(zend_llist *l, const void *element)
35 {
36 zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
37
38 tmp->prev = l->tail;
39 tmp->next = NULL;
40 if (l->tail) {
41 l->tail->next = tmp;
42 } else {
43 l->head = tmp;
44 }
45 l->tail = tmp;
46 memcpy(tmp->data, element, l->size);
47
48 ++l->count;
49 }
50
51
zend_llist_prepend_element(zend_llist * l,const void * element)52 ZEND_API void zend_llist_prepend_element(zend_llist *l, const void *element)
53 {
54 zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
55
56 tmp->next = l->head;
57 tmp->prev = NULL;
58 if (l->head) {
59 l->head->prev = tmp;
60 } else {
61 l->tail = tmp;
62 }
63 l->head = tmp;
64 memcpy(tmp->data, element, l->size);
65
66 ++l->count;
67 }
68
69
70 #define DEL_LLIST_ELEMENT(current, l) \
71 if ((current)->prev) {\
72 (current)->prev->next = (current)->next;\
73 } else {\
74 (l)->head = (current)->next;\
75 }\
76 if ((current)->next) {\
77 (current)->next->prev = (current)->prev;\
78 } else {\
79 (l)->tail = (current)->prev;\
80 }\
81 if ((l)->dtor) {\
82 (l)->dtor((current)->data);\
83 }\
84 pefree((current), (l)->persistent);\
85 --l->count;
86
87
zend_llist_del_element(zend_llist * l,void * element,int (* compare)(void * element1,void * element2))88 ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2))
89 {
90 zend_llist_element *current=l->head;
91
92 while (current) {
93 if (compare(current->data, element)) {
94 DEL_LLIST_ELEMENT(current, l);
95 break;
96 }
97 current = current->next;
98 }
99 }
100
101
zend_llist_destroy(zend_llist * l)102 ZEND_API void zend_llist_destroy(zend_llist *l)
103 {
104 zend_llist_element *current=l->head, *next;
105
106 while (current) {
107 next = current->next;
108 if (l->dtor) {
109 l->dtor(current->data);
110 }
111 pefree(current, l->persistent);
112 current = next;
113 }
114
115 l->count = 0;
116 }
117
118
zend_llist_clean(zend_llist * l)119 ZEND_API void zend_llist_clean(zend_llist *l)
120 {
121 zend_llist_destroy(l);
122 l->head = l->tail = NULL;
123 }
124
125
zend_llist_remove_tail(zend_llist * l)126 ZEND_API void zend_llist_remove_tail(zend_llist *l)
127 {
128 zend_llist_element *old_tail = l->tail;
129 if (!old_tail) {
130 return;
131 }
132
133 if (old_tail->prev) {
134 old_tail->prev->next = NULL;
135 } else {
136 l->head = NULL;
137 }
138
139 l->tail = old_tail->prev;
140 --l->count;
141
142 if (l->dtor) {
143 l->dtor(old_tail->data);
144 }
145 pefree(old_tail, l->persistent);
146 }
147
148
zend_llist_copy(zend_llist * dst,zend_llist * src)149 ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
150 {
151 zend_llist_element *ptr;
152
153 zend_llist_init(dst, src->size, src->dtor, src->persistent);
154 ptr = src->head;
155 while (ptr) {
156 zend_llist_add_element(dst, ptr->data);
157 ptr = ptr->next;
158 }
159 }
160
161
zend_llist_apply_with_del(zend_llist * l,int (* func)(void * data))162 ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
163 {
164 zend_llist_element *element, *next;
165
166 element=l->head;
167 while (element) {
168 next = element->next;
169 if (func(element->data)) {
170 DEL_LLIST_ELEMENT(element, l);
171 }
172 element = next;
173 }
174 }
175
176
zend_llist_apply(zend_llist * l,llist_apply_func_t func)177 ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func)
178 {
179 zend_llist_element *element;
180
181 for (element=l->head; element; element=element->next) {
182 func(element->data);
183 }
184 }
185
zend_llist_swap(zend_llist_element ** p,zend_llist_element ** q)186 static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q)
187 {
188 zend_llist_element *t;
189 t = *p;
190 *p = *q;
191 *q = t;
192 }
193
zend_llist_sort(zend_llist * l,llist_compare_func_t comp_func)194 ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
195 {
196 size_t i;
197
198 zend_llist_element **elements;
199 zend_llist_element *element, **ptr;
200
201 if (l->count == 0) {
202 return;
203 }
204
205 elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
206
207 ptr = &elements[0];
208
209 for (element=l->head; element; element=element->next) {
210 *ptr++ = element;
211 }
212
213 zend_sort(elements, l->count, sizeof(zend_llist_element *),
214 (compare_func_t) comp_func, (swap_func_t) zend_llist_swap);
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)229 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg)
230 {
231 zend_llist_element *element;
232
233 for (element=l->head; element; element=element->next) {
234 func(element->data, arg);
235 }
236 }
237
238
zend_llist_apply_with_arguments(zend_llist * l,llist_apply_with_args_func_t func,int num_args,...)239 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, 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);
247 }
248 va_end(args);
249 }
250
251
zend_llist_count(zend_llist * l)252 ZEND_API size_t 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
