1: /*
2: +----------------------------------------------------------------------+
3: | Zend Engine |
4: +----------------------------------------------------------------------+
5: | Copyright (c) 1998-2014 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.1.1.4 2014/06/15 20:04:04 misho 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: {
28: l->head = NULL;
29: l->tail = NULL;
30: l->count = 0;
31: l->size = size;
32: l->dtor = dtor;
33: l->persistent = persistent;
34: }
35:
36:
37: ZEND_API void zend_llist_add_element(zend_llist *l, void *element)
38: {
39: zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
40:
41: tmp->prev = l->tail;
42: tmp->next = NULL;
43: if (l->tail) {
44: l->tail->next = tmp;
45: } else {
46: l->head = tmp;
47: }
48: l->tail = tmp;
49: memcpy(tmp->data, element, l->size);
50:
51: ++l->count;
52: }
53:
54:
55: ZEND_API void zend_llist_prepend_element(zend_llist *l, void *element)
56: {
57: zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent);
58:
59: tmp->next = l->head;
60: tmp->prev = NULL;
61: if (l->head) {
62: l->head->prev = tmp;
63: } else {
64: l->tail = tmp;
65: }
66: l->head = tmp;
67: memcpy(tmp->data, element, l->size);
68:
69: ++l->count;
70: }
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: {
93: zend_llist_element *current=l->head;
94: zend_llist_element *next;
95:
96: while (current) {
97: next = current->next;
98: if (compare(current->data, element)) {
99: DEL_LLIST_ELEMENT(current, l);
100: break;
101: }
102: current = next;
103: }
104: }
105:
106:
107: ZEND_API void zend_llist_destroy(zend_llist *l)
108: {
109: zend_llist_element *current=l->head, *next;
110:
111: while (current) {
112: next = current->next;
113: if (l->dtor) {
114: l->dtor(current->data);
115: }
116: pefree(current, l->persistent);
117: current = next;
118: }
119:
120: l->count = 0;
121: }
122:
123:
124: ZEND_API void zend_llist_clean(zend_llist *l)
125: {
126: zend_llist_destroy(l);
127: l->head = l->tail = NULL;
128: }
129:
130:
131: ZEND_API void *zend_llist_remove_tail(zend_llist *l)
132: {
133: zend_llist_element *old_tail;
134: void *data;
135:
136: if ((old_tail = l->tail)) {
137: if (old_tail->prev) {
138: old_tail->prev->next = NULL;
139: } else {
140: l->head = NULL;
141: }
142:
143: data = old_tail->data;
144:
145: l->tail = old_tail->prev;
146: if (l->dtor) {
147: l->dtor(data);
148: }
149: pefree(old_tail, l->persistent);
150:
151: --l->count;
152:
153: return data;
154: }
155:
156: return NULL;
157: }
158:
159:
160: ZEND_API void zend_llist_copy(zend_llist *dst, zend_llist *src)
161: {
162: zend_llist_element *ptr;
163:
164: zend_llist_init(dst, src->size, src->dtor, src->persistent);
165: ptr = src->head;
166: while (ptr) {
167: zend_llist_add_element(dst, ptr->data);
168: ptr = ptr->next;
169: }
170: }
171:
172:
173: ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data))
174: {
175: zend_llist_element *element, *next;
176:
177: element=l->head;
178: while (element) {
179: next = element->next;
180: if (func(element->data)) {
181: DEL_LLIST_ELEMENT(element, l);
182: }
183: element = next;
184: }
185: }
186:
187:
188: ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
189: {
190: zend_llist_element *element;
191:
192: for (element=l->head; element; element=element->next) {
193: func(element->data TSRMLS_CC);
194: }
195: }
196:
197: ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
198: {
199: size_t i;
200:
201: zend_llist_element **elements;
202: zend_llist_element *element, **ptr;
203:
204: if (l->count <= 0) {
205: return;
206: }
207:
208: elements = (zend_llist_element **) emalloc(l->count * sizeof(zend_llist_element *));
209:
210: ptr = &elements[0];
211:
212: for (element=l->head; element; element=element->next) {
213: *ptr++ = element;
214: }
215:
216: zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
217:
218: l->head = elements[0];
219: elements[0]->prev = NULL;
220:
221: for (i = 1; i < l->count; i++) {
222: elements[i]->prev = elements[i-1];
223: elements[i-1]->next = elements[i];
224: }
225: elements[i-1]->next = NULL;
226: l->tail = elements[i-1];
227: 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: {
233: zend_llist_element *element;
234:
235: for (element=l->head; element; element=element->next) {
236: func(element->data, arg TSRMLS_CC);
237: }
238: }
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: {
243: zend_llist_element *element;
244: va_list args;
245:
246: va_start(args, num_args);
247: for (element=l->head; element; element=element->next) {
248: func(element->data, num_args, args TSRMLS_CC);
249: }
250: va_end(args);
251: }
252:
253:
254: ZEND_API int zend_llist_count(zend_llist *l)
255: {
256: return l->count;
257: }
258:
259:
260: ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos)
261: {
262: zend_llist_position *current = pos ? pos : &l->traverse_ptr;
263:
264: *current = l->head;
265: if (*current) {
266: return (*current)->data;
267: } else {
268: return NULL;
269: }
270: }
271:
272:
273: ZEND_API void *zend_llist_get_last_ex(zend_llist *l, zend_llist_position *pos)
274: {
275: zend_llist_position *current = pos ? pos : &l->traverse_ptr;
276:
277: *current = l->tail;
278: if (*current) {
279: return (*current)->data;
280: } else {
281: return NULL;
282: }
283: }
284:
285:
286: ZEND_API void *zend_llist_get_next_ex(zend_llist *l, zend_llist_position *pos)
287: {
288: zend_llist_position *current = pos ? pos : &l->traverse_ptr;
289:
290: if (*current) {
291: *current = (*current)->next;
292: if (*current) {
293: return (*current)->data;
294: }
295: }
296: return NULL;
297: }
298:
299:
300: ZEND_API void *zend_llist_get_prev_ex(zend_llist *l, zend_llist_position *pos)
301: {
302: zend_llist_position *current = pos ? pos : &l->traverse_ptr;
303:
304: if (*current) {
305: *current = (*current)->prev;
306: if (*current) {
307: return (*current)->data;
308: }
309: }
310: 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: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to zend_llist.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend