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 272370 2008-12-31 11:15: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 961723 : {
28 961723 : l->head = NULL;
29 961723 : l->tail = NULL;
30 961723 : l->count = 0;
31 961723 : l->size = size;
32 961723 : l->dtor = dtor;
33 961723 : l->persistent = persistent;
34 961723 : }
35 :
36 :
37 : ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
38 205049 : {
39 205049 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
40 :
41 205049 : tmp->prev = l->tail;
42 205049 : tmp->next = NULL;
43 205049 : if (l->tail) {
44 24721 : l->tail->next = tmp;
45 : } else {
46 180328 : l->head = tmp;
47 : }
48 205049 : l->tail = tmp;
49 205049 : memcpy(tmp->data, element, l->size);
50 :
51 205049 : ++l->count;
52 205049 : }
53 :
54 :
55 : ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
56 261 : {
57 261 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
58 :
59 261 : tmp->next = l->head;
60 261 : tmp->prev = NULL;
61 261 : if (l->head) {
62 160 : l->head->prev = tmp;
63 : } else {
64 101 : l->tail = tmp;
65 : }
66 261 : l->head = tmp;
67 261 : memcpy(tmp->data, element, l->size);
68 :
69 261 : ++l->count;
70 261 : }
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 25591 : {
93 25591 : zend_llist_element *current=l->head;
94 : zend_llist_element *next;
95 :
96 51275 : while (current) {
97 25273 : next = current->next;
98 25273 : if (compare(current->data, element)) {
99 25180 : DEL_LLIST_ELEMENT(current, l);
100 25180 : break;
101 : }
102 93 : current = next;
103 : }
104 25591 : }
105 :
106 :
107 : ZEND_API void zend_llist_destroy(zend_llist *l)
108 944186 : {
109 944186 : zend_llist_element *current=l->head, *next;
110 :
111 2068508 : while (current) {
112 180136 : next = current->next;
113 180136 : if (l->dtor) {
114 844 : l->dtor(current->data);
115 : }
116 180136 : pefree(current, l->persistent);
117 180136 : current = next;
118 : }
119 :
120 944186 : l->count = 0;
121 944186 : }
122 :
123 :
124 : ZEND_API void zend_llist_clean(zend_llist *l)
125 17970 : {
126 17970 : zend_llist_destroy(l);
127 17970 : l->head = l->tail = NULL;
128 17970 : }
129 :
130 :
131 : ZEND_API void *zend_llist_remove_tail(zend_llist *l)
132 12 : {
133 : zend_llist_element *old_tail;
134 : void *data;
135 :
136 12 : if ((old_tail = l->tail)) {
137 12 : if (old_tail->prev) {
138 12 : old_tail->prev->next = NULL;
139 : } else {
140 0 : l->head = NULL;
141 : }
142 :
143 12 : data = old_tail->data;
144 :
145 12 : l->tail = old_tail->prev;
146 12 : if (l->dtor) {
147 0 : l->dtor(data);
148 : }
149 12 : pefree(old_tail, l->persistent);
150 :
151 12 : --l->count;
152 :
153 12 : 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 268 : {
162 : zend_llist_element *ptr;
163 :
164 268 : zend_llist_init(dst, src->size, src->dtor, src->persistent);
165 268 : ptr = src->head;
166 814 : while (ptr) {
167 278 : zend_llist_add_element(dst, ptr->data);
168 278 : ptr = ptr->next;
169 : }
170 268 : }
171 :
172 :
173 : ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
174 17633 : {
175 : zend_llist_element *element, *next;
176 :
177 17633 : element=l->head;
178 35266 : 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 17633 : }
186 :
187 :
188 : ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
189 88221 : {
190 : zend_llist_element *element;
191 :
192 88240 : for (element=l->head; element; element=element->next) {
193 19 : func(element->data TSRMLS_CC);
194 : }
195 88221 : }
196 :
197 : ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
198 1 : {
199 : size_t i;
200 :
201 : zend_llist_element **elements;
202 : zend_llist_element *element, **ptr;
203 :
204 1 : if (l->count <= 0) {
205 1 : 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 163506 : {
233 : zend_llist_element *element;
234 :
235 163563 : for (element=l->head; element; element=element->next) {
236 57 : func(element->data, arg TSRMLS_CC);
237 : }
238 163506 : }
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 242 : {
262 242 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
263 :
264 242 : *current = l->head;
265 242 : if (*current) {
266 241 : 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 17795 : {
275 17795 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
276 :
277 17795 : *current = l->tail;
278 17795 : if (*current) {
279 17795 : 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 435 : {
288 435 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
289 :
290 435 : if (*current) {
291 435 : *current = (*current)->next;
292 435 : if (*current) {
293 244 : return (*current)->data;
294 : }
295 : }
296 191 : 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 : */
|
