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 272367 2008-12-31 11:12:40Z 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 893780 : {
28 893780 : l->head = NULL;
29 893780 : l->tail = NULL;
30 893780 : l->count = 0;
31 893780 : l->size = size;
32 893780 : l->dtor = dtor;
33 893780 : l->persistent = persistent;
34 893780 : }
35 : /* }}} */
36 :
37 : ZEND_API void zend_llist_add_element(zend_llist *l, void *element) /* {{{ */
38 187105 : {
39 187105 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
40 :
41 187105 : tmp->prev = l->tail;
42 187105 : tmp->next = NULL;
43 187105 : if (l->tail) {
44 18393 : l->tail->next = tmp;
45 : } else {
46 168712 : l->head = tmp;
47 : }
48 187105 : l->tail = tmp;
49 187105 : memcpy(tmp->data, element, l->size);
50 :
51 187105 : ++l->count;
52 187105 : }
53 : /* }}} */
54 :
55 : ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element) /* {{{ */
56 250 : {
57 250 : zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
58 :
59 250 : tmp->next = l->head;
60 250 : tmp->prev = NULL;
61 250 : if (l->head) {
62 152 : l->head->prev = tmp;
63 : } else {
64 98 : l->tail = tmp;
65 : }
66 250 : l->head = tmp;
67 250 : memcpy(tmp->data, element, l->size);
68 :
69 250 : ++l->count;
70 250 : }
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 24654 : {
93 24654 : zend_llist_element *current=l->head;
94 : zend_llist_element *next;
95 :
96 49473 : while (current) {
97 24372 : next = current->next;
98 24372 : if (compare(current->data, element)) {
99 24207 : DEL_LLIST_ELEMENT(current, l);
100 24207 : break;
101 : }
102 165 : current = next;
103 : }
104 24654 : }
105 : /* }}} */
106 :
107 : ZEND_API void zend_llist_destroy(zend_llist *l) /* {{{ */
108 876918 : {
109 876918 : zend_llist_element *current=l->head, *next;
110 :
111 1916990 : while (current) {
112 163154 : next = current->next;
113 163154 : if (l->dtor) {
114 933 : l->dtor(current->data);
115 : }
116 163154 : pefree(current, l->persistent);
117 163154 : current = next;
118 : }
119 :
120 876918 : l->count = 0;
121 876918 : }
122 : /* }}} */
123 :
124 : ZEND_API void zend_llist_clean(zend_llist *l) /* {{{ */
125 17389 : {
126 17389 : zend_llist_destroy(l);
127 17389 : l->head = l->tail = NULL;
128 17389 : }
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 257 : {
162 : zend_llist_element *ptr;
163 :
164 257 : zend_llist_init(dst, src->size, src->dtor, src->persistent);
165 257 : ptr = src->head;
166 781 : while (ptr) {
167 267 : zend_llist_add_element(dst, ptr->data);
168 267 : ptr = ptr->next;
169 : }
170 257 : }
171 : /* }}} */
172 :
173 : ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data)) /* {{{ */
174 17007 : {
175 : zend_llist_element *element, *next;
176 :
177 17007 : element=l->head;
178 34014 : 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 17007 : }
186 : /* }}} */
187 :
188 : ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC) /* {{{ */
189 85091 : {
190 : zend_llist_element *element;
191 :
192 85110 : for (element=l->head; element; element=element->next) {
193 19 : func(element->data TSRMLS_CC);
194 : }
195 85091 : }
196 : /* }}} */
197 :
198 : ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC) /* {{{ */
199 1 : {
200 : size_t i;
201 :
202 : zend_llist_element **elements;
203 : zend_llist_element *element, **ptr;
204 :
205 1 : if (l->count <= 0) {
206 1 : return;
207 : }
208 :
209 0 : elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
210 :
211 0 : ptr = &elements[0];
212 :
213 0 : for (element=l->head; element; element=element->next) {
214 0 : *ptr++ = element;
215 : }
216 :
217 0 : zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
218 :
219 0 : l->head = elements[0];
220 0 : elements[0]->prev = NULL;
221 :
222 0 : for (i = 1; i < l->count; i++) {
223 0 : elements[i]->prev = elements[i-1];
224 0 : elements[i-1]->next = elements[i];
225 : }
226 0 : elements[i-1]->next = NULL;
227 0 : l->tail = elements[i-1];
228 0 : efree(elements);
229 : }
230 : /* }}} */
231 :
232 : ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC) /* {{{ */
233 144517 : {
234 : zend_llist_element *element;
235 :
236 144574 : for (element=l->head; element; element=element->next) {
237 57 : func(element->data, arg TSRMLS_CC);
238 : }
239 144517 : }
240 : /* }}} */
241 :
242 : ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...) /* {{{ */
243 0 : {
244 : zend_llist_element *element;
245 : va_list args;
246 :
247 0 : va_start(args, num_args);
248 0 : for (element=l->head; element; element=element->next) {
249 0 : func(element->data, num_args, args TSRMLS_CC);
250 : }
251 0 : va_end(args);
252 0 : }
253 : /* }}} */
254 :
255 : ZEND_API int zend_llist_count(zend_llist *l) /* {{{ */
256 0 : {
257 0 : return l->count;
258 : }
259 : /* }}} */
260 :
261 : ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos) /* {{{ */
262 300 : {
263 300 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
264 :
265 300 : *current = l->head;
266 300 : if (*current) {
267 299 : return (*current)->data;
268 : } else {
269 1 : return NULL;
270 : }
271 : }
272 : /* }}} */
273 :
274 : ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos) /* {{{ */
275 17165 : {
276 17165 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
277 :
278 17165 : *current = l->tail;
279 17165 : if (*current) {
280 17165 : return (*current)->data;
281 : } else {
282 0 : return NULL;
283 : }
284 : }
285 : /* }}} */
286 :
287 : ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos) /* {{{ */
288 495 : {
289 495 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
290 :
291 495 : if (*current) {
292 495 : *current = (*current)->next;
293 495 : if (*current) {
294 279 : return (*current)->data;
295 : }
296 : }
297 216 : return NULL;
298 : }
299 : /* }}} */
300 :
301 : ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos) /* {{{ */
302 0 : {
303 0 : zend_llist_position *current = pos ? pos : &l->traverse_ptr;
304 :
305 0 : if (*current) {
306 0 : *current = (*current)->prev;
307 0 : if (*current) {
308 0 : return (*current)->data;
309 : }
310 : }
311 0 : return NULL;
312 : }
313 : /* }}} */
314 :
315 : /*
316 : * Local variables:
317 : * tab-width: 4
318 : * c-basic-offset: 4
319 : * indent-tabs-mode: t
320 : * End:
321 : */
|
