/src/php-src/Zend/zend_llist.c
Line | Count | Source (jump to first uncovered line) |
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 | | |
24 | | ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent) |
25 | 600k | { |
26 | 600k | l->head = NULL; |
27 | 600k | l->tail = NULL; |
28 | 600k | l->count = 0; |
29 | 600k | l->size = size; |
30 | 600k | l->dtor = dtor; |
31 | 600k | l->persistent = persistent; |
32 | 600k | } |
33 | | |
34 | | ZEND_API void zend_llist_add_element(zend_llist *l, const void *element) |
35 | 444k | { |
36 | 444k | zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent); |
37 | | |
38 | 444k | tmp->prev = l->tail; |
39 | 444k | tmp->next = NULL; |
40 | 444k | if (l->tail) { |
41 | 69 | l->tail->next = tmp; |
42 | 444k | } else { |
43 | 444k | l->head = tmp; |
44 | 444k | } |
45 | 444k | l->tail = tmp; |
46 | 444k | memcpy(tmp->data, element, l->size); |
47 | | |
48 | 444k | ++l->count; |
49 | 444k | } |
50 | | |
51 | | |
52 | | ZEND_API void zend_llist_prepend_element(zend_llist *l, const void *element) |
53 | 0 | { |
54 | 0 | zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent); |
55 | |
|
56 | 0 | tmp->next = l->head; |
57 | 0 | tmp->prev = NULL; |
58 | 0 | if (l->head) { |
59 | 0 | l->head->prev = tmp; |
60 | 0 | } else { |
61 | 0 | l->tail = tmp; |
62 | 0 | } |
63 | 0 | l->head = tmp; |
64 | 0 | memcpy(tmp->data, element, l->size); |
65 | |
|
66 | 0 | ++l->count; |
67 | 0 | } |
68 | | |
69 | | |
70 | | #define DEL_LLIST_ELEMENT(current, l) \ |
71 | 138k | if ((current)->prev) {\ |
72 | 0 | (current)->prev->next = (current)->next;\ |
73 | 138k | } else {\ |
74 | 138k | (l)->head = (current)->next;\ |
75 | 138k | }\ |
76 | 138k | if ((current)->next) {\ |
77 | 0 | (current)->next->prev = (current)->prev;\ |
78 | 138k | } else {\ |
79 | 138k | (l)->tail = (current)->prev;\ |
80 | 138k | }\ |
81 | 138k | if ((l)->dtor) {\ |
82 | 138k | (l)->dtor((current)->data);\ |
83 | 138k | }\ |
84 | 138k | pefree((current), (l)->persistent);\ |
85 | 138k | --l->count; |
86 | | |
87 | | |
88 | | ZEND_API void zend_llist_del_element(zend_llist *l, void *element, int (*compare)(void *element1, void *element2)) |
89 | 138k | { |
90 | 138k | zend_llist_element *current=l->head; |
91 | | |
92 | 138k | while (current) { |
93 | 138k | if (compare(current->data, element)) { |
94 | 138k | DEL_LLIST_ELEMENT(current, l); |
95 | 138k | break; |
96 | 138k | } |
97 | 0 | current = current->next; |
98 | 0 | } |
99 | 138k | } |
100 | | |
101 | | |
102 | | ZEND_API void zend_llist_destroy(zend_llist *l) |
103 | 900k | { |
104 | 900k | zend_llist_element *current=l->head, *next; |
105 | | |
106 | 1.20M | while (current) { |
107 | 306k | next = current->next; |
108 | 306k | if (l->dtor) { |
109 | 306k | l->dtor(current->data); |
110 | 306k | } |
111 | 306k | pefree(current, l->persistent); |
112 | 306k | current = next; |
113 | 306k | } |
114 | | |
115 | 900k | l->head = NULL; |
116 | 900k | l->tail = NULL; |
117 | 900k | l->count = 0; |
118 | 900k | } |
119 | | |
120 | | |
121 | | ZEND_API void zend_llist_clean(zend_llist *l) |
122 | 300k | { |
123 | 300k | zend_llist_destroy(l); |
124 | 300k | l->head = l->tail = NULL; |
125 | 300k | } |
126 | | |
127 | | |
128 | | ZEND_API void zend_llist_remove_tail(zend_llist *l) |
129 | 0 | { |
130 | 0 | zend_llist_element *old_tail = l->tail; |
131 | 0 | if (!old_tail) { |
132 | 0 | return; |
133 | 0 | } |
134 | | |
135 | 0 | if (old_tail->prev) { |
136 | 0 | old_tail->prev->next = NULL; |
137 | 0 | } else { |
138 | 0 | l->head = NULL; |
139 | 0 | } |
140 | |
|
141 | 0 | l->tail = old_tail->prev; |
142 | 0 | --l->count; |
143 | |
|
144 | 0 | if (l->dtor) { |
145 | 0 | l->dtor(old_tail->data); |
146 | 0 | } |
147 | 0 | pefree(old_tail, l->persistent); |
148 | 0 | } |
149 | | |
150 | | |
151 | | ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src) |
152 | 0 | { |
153 | 0 | zend_llist_element *ptr; |
154 | |
|
155 | 0 | zend_llist_init(dst, src->size, src->dtor, src->persistent); |
156 | 0 | ptr = src->head; |
157 | 0 | while (ptr) { |
158 | 0 | zend_llist_add_element(dst, ptr->data); |
159 | 0 | ptr = ptr->next; |
160 | 0 | } |
161 | 0 | } |
162 | | |
163 | | |
164 | | ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data)) |
165 | 16 | { |
166 | 16 | zend_llist_element *element, *next; |
167 | | |
168 | 16 | element=l->head; |
169 | 20 | while (element) { |
170 | 4 | next = element->next; |
171 | 4 | if (func(element->data)) { |
172 | 0 | DEL_LLIST_ELEMENT(element, l); |
173 | 0 | } |
174 | 4 | element = next; |
175 | 4 | } |
176 | 16 | } |
177 | | |
178 | | |
179 | | ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func) |
180 | 600k | { |
181 | 600k | zend_llist_element *element; |
182 | | |
183 | 798k | for (element=l->head; element; element=element->next) { |
184 | 197k | func(element->data); |
185 | 197k | } |
186 | 600k | } |
187 | | |
188 | | static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q) |
189 | 0 | { |
190 | 0 | zend_llist_element *t; |
191 | 0 | t = *p; |
192 | 0 | *p = *q; |
193 | 0 | *q = t; |
194 | 0 | } |
195 | | |
196 | | ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func) |
197 | 0 | { |
198 | 0 | size_t i; |
199 | |
|
200 | 0 | zend_llist_element **elements; |
201 | 0 | zend_llist_element *element, **ptr; |
202 | |
|
203 | 0 | if (l->count == 0) { |
204 | 0 | return; |
205 | 0 | } |
206 | | |
207 | 0 | elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *)); |
208 | |
|
209 | 0 | ptr = &elements[0]; |
210 | |
|
211 | 0 | for (element=l->head; element; element=element->next) { |
212 | 0 | *ptr++ = element; |
213 | 0 | } |
214 | |
|
215 | 0 | zend_sort(elements, l->count, sizeof(zend_llist_element *), |
216 | 0 | (compare_func_t) comp_func, (swap_func_t) zend_llist_swap); |
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 | 0 | } |
225 | 0 | elements[i-1]->next = NULL; |
226 | 0 | l->tail = elements[i-1]; |
227 | 0 | efree(elements); |
228 | 0 | } |
229 | | |
230 | | |
231 | | ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg) |
232 | 300k | { |
233 | 300k | zend_llist_element *element; |
234 | | |
235 | 600k | for (element=l->head; element; element=element->next) { |
236 | 300k | func(element->data, arg); |
237 | 300k | } |
238 | 300k | } |
239 | | |
240 | | |
241 | | ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func, int num_args, ...) |
242 | 4 | { |
243 | 4 | zend_llist_element *element; |
244 | 4 | va_list args; |
245 | | |
246 | 4 | va_start(args, num_args); |
247 | 4 | for (element=l->head; element; element=element->next) { |
248 | 0 | func(element->data, num_args, args); |
249 | 0 | } |
250 | 4 | va_end(args); |
251 | 4 | } |
252 | | |
253 | | |
254 | | ZEND_API size_t zend_llist_count(zend_llist *l) |
255 | 12 | { |
256 | 12 | return l->count; |
257 | 12 | } |
258 | | |
259 | | |
260 | | ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos) |
261 | 24 | { |
262 | 24 | zend_llist_position *current = pos ? pos : &l->traverse_ptr; |
263 | | |
264 | 24 | *current = l->head; |
265 | 24 | if (*current) { |
266 | 24 | return (*current)->data; |
267 | 24 | } else { |
268 | 0 | return NULL; |
269 | 0 | } |
270 | 24 | } |
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 | 0 | } else { |
281 | 0 | return NULL; |
282 | 0 | } |
283 | 0 | } |
284 | | |
285 | | |
286 | | ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos) |
287 | 24 | { |
288 | 24 | zend_llist_position *current = pos ? pos : &l->traverse_ptr; |
289 | | |
290 | 24 | if (*current) { |
291 | 24 | *current = (*current)->next; |
292 | 24 | if (*current) { |
293 | 0 | return (*current)->data; |
294 | 0 | } |
295 | 24 | } |
296 | 24 | return NULL; |
297 | 24 | } |
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 | 0 | } |
309 | 0 | } |
310 | 0 | return NULL; |
311 | 0 | } |