1 : /*
2 : +----------------------------------------------------------------------+
3 : | Zend Engine |
4 : +----------------------------------------------------------------------+
5 : | Copyright (c) 1998-2007 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,v 1.35.2.1.2.2 2007/02/16 08:33:28 dmitry Exp $ */
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 10372 : {
28 10372 : l->head = NULL;
29 10372 : l->tail = NULL;
30 10372 : l->count = 0;
31 10372 : l->size = size;
32 10372 : l->dtor = dtor;
33 10372 : l->persistent = persistent;
34 10372 : }
35 :
36 :
37 : ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
38 2126 : {
39 2126 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
40 :
41 2126 : tmp->prev = l->tail;
42 2126 : tmp->next = NULL;
43 2126 : if (l->tail) {
44 424 : l->tail->next = tmp;
45 : } else {
46 1702 : l->head = tmp;
47 : }
48 2126 : l->tail = tmp;
49 2126 : memcpy(tmp->data, element, l->size);
50 :
51 2126 : ++l->count;
52 2126 : }
53 :
54 :
55 : ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
56 4 : {
57 4 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
58 :
59 4 : tmp->next = l->head;
60 4 : tmp->prev = NULL;
61 4 : if (l->head) {
62 2 : l->head->prev = tmp;
63 : } else {
64 2 : l->tail = tmp;
65 : }
66 4 : l->head = tmp;
67 4 : memcpy(tmp->data, element, l->size);
68 :
69 4 : ++l->count;
70 4 : }
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 817 : {
93 817 : zend_llist_element *current=l->head;
94 : zend_llist_element *next;
95 :
96 2111 : while (current) {
97 953 : next = current->next;
98 953 : if (compare(current->data, element)) {
99 476 : DEL_LLIST_ELEMENT(current, l);
100 476 : break;
101 : }
102 477 : current = next;
103 : }
104 817 : }
105 :
106 :
107 : ZEND_API void zend_llist_destroy(zend_llist *l)
108 9712 : {
109 9712 : zend_llist_element *current=l->head, *next;
110 :
111 21078 : while (current) {
112 1654 : next = current->next;
113 1654 : if (l->dtor) {
114 434 : l->dtor(current->data);
115 : }
116 1654 : pefree(current, l->persistent);
117 1654 : current = next;
118 : }
119 :
120 9712 : l->count = 0;
121 9712 : }
122 :
123 :
124 : ZEND_API void zend_llist_clean(zend_llist *l)
125 14 : {
126 14 : zend_llist_destroy(l);
127 14 : l->head = l->tail = NULL;
128 14 : }
129 :
130 :
131 : ZEND_API void *zend_llist_remove_tail(zend_llist *l)
132 0 : {
133 : zend_llist_element *old_tail;
134 : void *data;
135 :
136 0 : if ((old_tail = l->tail)) {
137 0 : if (old_tail->prev) {
138 0 : old_tail->prev->next = NULL;
139 : } else {
140 0 : l->head = NULL;
141 : }
142 :
143 0 : data = old_tail->data;
144 :
145 0 : l->tail = old_tail->prev;
146 0 : if (l->dtor) {
147 0 : l->dtor(data);
148 : }
149 0 : pefree(old_tail, l->persistent);
150 :
151 0 : --l->count;
152 :
153 0 : 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 4 : {
162 : zend_llist_element *ptr;
163 :
164 4 : zend_llist_init(dst, src->size, src->dtor, src->persistent);
165 4 : ptr = src->head;
166 12 : while (ptr) {
167 4 : zend_llist_add_element(dst, ptr->data);
168 4 : ptr = ptr->next;
169 : }
170 4 : }
171 :
172 :
173 : ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
174 220 : {
175 : zend_llist_element *element, *next;
176 :
177 220 : element=l->head;
178 440 : 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 220 : }
186 :
187 :
188 : ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
189 1097 : {
190 : zend_llist_element *element;
191 :
192 1097 : for (element=l->head; element; element=element->next) {
193 0 : func(element->data TSRMLS_CC);
194 : }
195 1097 : }
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 3995 : {
233 : zend_llist_element *element;
234 :
235 4047 : for (element=l->head; element; element=element->next) {
236 52 : func(element->data, arg TSRMLS_CC);
237 : }
238 3995 : }
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 103 : {
256 103 : return l->count;
257 : }
258 :
259 :
260 : ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
261 196 : {
262 196 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
263 :
264 196 : *current = l->head;
265 196 : if (*current) {
266 192 : return (*current)->data;
267 : } else {
268 4 : 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 821 : {
288 821 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
289 :
290 821 : if (*current) {
291 821 : *current = (*current)->next;
292 821 : if (*current) {
293 647 : return (*current)->data;
294 : }
295 : }
296 174 : 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 : */
|
