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