xref: /PHP-5.6/ext/spl/spl_dllist.c (revision 49493a2d)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 5                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2016 The PHP Group                                |
6    +----------------------------------------------------------------------+
7    | This source file is subject to version 3.01 of the PHP 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.php.net/license/3_01.txt                                  |
11    | If you did not receive a copy of the PHP license and are unable to   |
12    | obtain it through the world-wide-web, please send a note to          |
13    | license@php.net so we can mail you a copy immediately.               |
14    +----------------------------------------------------------------------+
15    | Authors: Etienne Kneuss <colder@php.net>                             |
16    +----------------------------------------------------------------------+
17  */
18 
19 /* $Id$ */
20 
21 #ifdef HAVE_CONFIG_H
22 # include "config.h"
23 #endif
24 
25 #include "php.h"
26 #include "zend_exceptions.h"
27 #include "zend_hash.h"
28 
29 #include "php_spl.h"
30 #include "ext/standard/info.h"
31 #include "ext/standard/php_var.h"
32 #include "ext/standard/php_smart_str.h"
33 #include "spl_functions.h"
34 #include "spl_engine.h"
35 #include "spl_iterators.h"
36 #include "spl_dllist.h"
37 #include "spl_exceptions.h"
38 
39 zend_object_handlers spl_handler_SplDoublyLinkedList;
40 PHPAPI zend_class_entry  *spl_ce_SplDoublyLinkedList;
41 PHPAPI zend_class_entry  *spl_ce_SplQueue;
42 PHPAPI zend_class_entry  *spl_ce_SplStack;
43 
44 #define SPL_LLIST_DELREF(elem) if(!--(elem)->rc) { \
45 	efree(elem); \
46 }
47 
48 #define SPL_LLIST_CHECK_DELREF(elem) if((elem) && !--(elem)->rc) { \
49 	efree(elem); \
50 }
51 
52 #define SPL_LLIST_ADDREF(elem) (elem)->rc++
53 #define SPL_LLIST_CHECK_ADDREF(elem) if(elem) (elem)->rc++
54 
55 #define SPL_DLLIST_IT_DELETE 0x00000001 /* Delete flag makes the iterator delete the current element on next */
56 #define SPL_DLLIST_IT_LIFO   0x00000002 /* LIFO flag makes the iterator traverse the structure as a LastInFirstOut */
57 #define SPL_DLLIST_IT_MASK   0x00000003 /* Mask to isolate flags related to iterators */
58 #define SPL_DLLIST_IT_FIX    0x00000004 /* Backward/Forward bit is fixed */
59 
60 #ifdef accept
61 #undef accept
62 #endif
63 
64 typedef struct _spl_ptr_llist_element {
65 	struct _spl_ptr_llist_element *prev;
66 	struct _spl_ptr_llist_element *next;
67 	int                            rc;
68 	void                          *data;
69 } spl_ptr_llist_element;
70 
71 typedef void (*spl_ptr_llist_dtor_func)(spl_ptr_llist_element * TSRMLS_DC);
72 typedef void (*spl_ptr_llist_ctor_func)(spl_ptr_llist_element * TSRMLS_DC);
73 
74 typedef struct _spl_ptr_llist {
75 	spl_ptr_llist_element   *head;
76 	spl_ptr_llist_element   *tail;
77 	spl_ptr_llist_dtor_func  dtor;
78 	spl_ptr_llist_ctor_func  ctor;
79 	int count;
80 } spl_ptr_llist;
81 
82 typedef struct _spl_dllist_object spl_dllist_object;
83 typedef struct _spl_dllist_it spl_dllist_it;
84 
85 struct _spl_dllist_object {
86 	zend_object            std;
87 	spl_ptr_llist         *llist;
88 	int                    traverse_position;
89 	spl_ptr_llist_element *traverse_pointer;
90 	zval                  *retval;
91 	int                    flags;
92 	zend_function         *fptr_offset_get;
93 	zend_function         *fptr_offset_set;
94 	zend_function         *fptr_offset_has;
95 	zend_function         *fptr_offset_del;
96 	zend_function         *fptr_count;
97 	zend_class_entry      *ce_get_iterator;
98 	HashTable             *debug_info;
99 };
100 
101 /* define an overloaded iterator structure */
102 struct _spl_dllist_it {
103 	zend_user_iterator     intern;
104 	int                    traverse_position;
105 	spl_ptr_llist_element *traverse_pointer;
106 	int                    flags;
107 	spl_dllist_object     *object;
108 };
109 
110 /* {{{  spl_ptr_llist */
spl_ptr_llist_zval_dtor(spl_ptr_llist_element * elem TSRMLS_DC)111 static void spl_ptr_llist_zval_dtor(spl_ptr_llist_element *elem TSRMLS_DC) { /* {{{ */
112 	if (elem->data) {
113 		zval_ptr_dtor((zval **)&elem->data);
114 	}
115 }
116 /* }}} */
117 
spl_ptr_llist_zval_ctor(spl_ptr_llist_element * elem TSRMLS_DC)118 static void spl_ptr_llist_zval_ctor(spl_ptr_llist_element *elem TSRMLS_DC) { /* {{{ */
119 	Z_ADDREF_P((zval *)elem->data);
120 }
121 /* }}} */
122 
spl_ptr_llist_init(spl_ptr_llist_ctor_func ctor,spl_ptr_llist_dtor_func dtor)123 static spl_ptr_llist *spl_ptr_llist_init(spl_ptr_llist_ctor_func ctor, spl_ptr_llist_dtor_func dtor) /* {{{ */
124 {
125 	spl_ptr_llist *llist = emalloc(sizeof(spl_ptr_llist));
126 
127 	llist->head  = NULL;
128 	llist->tail  = NULL;
129 	llist->count = 0;
130 	llist->dtor  = dtor;
131 	llist->ctor  = ctor;
132 
133 	return llist;
134 }
135 /* }}} */
136 
spl_ptr_llist_count(spl_ptr_llist * llist)137 static long spl_ptr_llist_count(spl_ptr_llist *llist) /* {{{ */
138 {
139 	return (long)llist->count;
140 }
141 /* }}} */
142 
spl_ptr_llist_destroy(spl_ptr_llist * llist TSRMLS_DC)143 static void spl_ptr_llist_destroy(spl_ptr_llist *llist TSRMLS_DC) /* {{{ */
144 {
145 	spl_ptr_llist_element   *current = llist->head, *next;
146 	spl_ptr_llist_dtor_func  dtor    = llist->dtor;
147 
148 	while (current) {
149 		next = current->next;
150 		if(current && dtor) {
151 			dtor(current TSRMLS_CC);
152 		}
153 		SPL_LLIST_DELREF(current);
154 		current = next;
155 	}
156 
157 	efree(llist);
158 }
159 /* }}} */
160 
spl_ptr_llist_offset(spl_ptr_llist * llist,long offset,int backward)161 static spl_ptr_llist_element *spl_ptr_llist_offset(spl_ptr_llist *llist, long offset, int backward) /* {{{ */
162 {
163 
164 	spl_ptr_llist_element *current;
165 	int pos = 0;
166 
167 	if (backward) {
168 		current = llist->tail;
169 	} else {
170 		current = llist->head;
171 	}
172 
173 	while (current && pos < offset) {
174 		pos++;
175 		if (backward) {
176 			current = current->prev;
177 		} else {
178 			current = current->next;
179 		}
180 	}
181 
182 	return current;
183 }
184 /* }}} */
185 
spl_ptr_llist_unshift(spl_ptr_llist * llist,void * data TSRMLS_DC)186 static void spl_ptr_llist_unshift(spl_ptr_llist *llist, void *data TSRMLS_DC) /* {{{ */
187 {
188 	spl_ptr_llist_element *elem = emalloc(sizeof(spl_ptr_llist_element));
189 
190 	elem->data = data;
191 	elem->rc   = 1;
192 	elem->prev = NULL;
193 	elem->next = llist->head;
194 
195 	if (llist->head) {
196 		llist->head->prev = elem;
197 	} else {
198 		llist->tail = elem;
199 	}
200 
201 	llist->head = elem;
202 	llist->count++;
203 
204 	if (llist->ctor) {
205 		llist->ctor(elem TSRMLS_CC);
206 	}
207 }
208 /* }}} */
209 
spl_ptr_llist_push(spl_ptr_llist * llist,void * data TSRMLS_DC)210 static void spl_ptr_llist_push(spl_ptr_llist *llist, void *data TSRMLS_DC) /* {{{ */
211 {
212 	spl_ptr_llist_element *elem = emalloc(sizeof(spl_ptr_llist_element));
213 
214 	elem->data = data;
215 	elem->rc   = 1;
216 	elem->prev = llist->tail;
217 	elem->next = NULL;
218 
219 	if (llist->tail) {
220 		llist->tail->next = elem;
221 	} else {
222 		llist->head = elem;
223 	}
224 
225 	llist->tail = elem;
226 	llist->count++;
227 
228 	if (llist->ctor) {
229 		llist->ctor(elem TSRMLS_CC);
230 	}
231 }
232 /* }}} */
233 
spl_ptr_llist_pop(spl_ptr_llist * llist TSRMLS_DC)234 static void *spl_ptr_llist_pop(spl_ptr_llist *llist TSRMLS_DC) /* {{{ */
235 {
236 	void                     *data;
237 	spl_ptr_llist_element    *tail = llist->tail;
238 
239 	if (tail == NULL) {
240 		return NULL;
241 	}
242 
243 	if (tail->prev) {
244 		tail->prev->next = NULL;
245 	} else {
246 		llist->head = NULL;
247 	}
248 
249 	llist->tail = tail->prev;
250 	llist->count--;
251 	data = tail->data;
252 
253 	if (llist->dtor) {
254 		llist->dtor(tail TSRMLS_CC);
255 	}
256 
257 	tail->data = NULL;
258 
259 	SPL_LLIST_DELREF(tail);
260 
261 	return data;
262 }
263 /* }}} */
264 
spl_ptr_llist_last(spl_ptr_llist * llist)265 static void *spl_ptr_llist_last(spl_ptr_llist *llist) /* {{{ */
266 {
267 	spl_ptr_llist_element *tail = llist->tail;
268 
269 	if (tail == NULL) {
270 		return NULL;
271 	} else {
272 		return tail->data;
273 	}
274 }
275 /* }}} */
276 
spl_ptr_llist_first(spl_ptr_llist * llist)277 static void *spl_ptr_llist_first(spl_ptr_llist *llist) /* {{{ */
278 {
279 	spl_ptr_llist_element *head = llist->head;
280 
281 	if (head == NULL) {
282 		return NULL;
283 	} else {
284 		return head->data;
285 	}
286 }
287 /* }}} */
288 
spl_ptr_llist_shift(spl_ptr_llist * llist TSRMLS_DC)289 static void *spl_ptr_llist_shift(spl_ptr_llist *llist TSRMLS_DC) /* {{{ */
290 {
291 	void                    *data;
292 	spl_ptr_llist_element   *head = llist->head;
293 
294 	if (head == NULL) {
295 		return NULL;
296 	}
297 
298 	if (head->next) {
299 		head->next->prev = NULL;
300 	} else {
301 		llist->tail = NULL;
302 	}
303 
304 	llist->head = head->next;
305 	llist->count--;
306 	data = head->data;
307 
308 	if (llist->dtor) {
309 		llist->dtor(head TSRMLS_CC);
310 	}
311 	head->data = NULL;
312 
313 	SPL_LLIST_DELREF(head);
314 
315 	return data;
316 }
317 /* }}} */
318 
spl_ptr_llist_copy(spl_ptr_llist * from,spl_ptr_llist * to TSRMLS_DC)319 static void spl_ptr_llist_copy(spl_ptr_llist *from, spl_ptr_llist *to TSRMLS_DC) /* {{{ */
320 {
321 	spl_ptr_llist_element   *current = from->head, *next;
322 	spl_ptr_llist_ctor_func  ctor    = from->ctor;
323 
324 	while (current) {
325 		next = current->next;
326 
327 		if (ctor) {
328 			ctor(current TSRMLS_CC);
329 		}
330 
331 		spl_ptr_llist_push(to, current->data TSRMLS_CC);
332 		current = next;
333 	}
334 
335 }
336 /* }}} */
337 
338 /* }}} */
339 
spl_dllist_object_free_storage(void * object TSRMLS_DC)340 static void spl_dllist_object_free_storage(void *object TSRMLS_DC) /* {{{ */
341 {
342 	spl_dllist_object *intern = (spl_dllist_object *)object;
343 	zval              *tmp    = NULL;
344 
345 	zend_object_std_dtor(&intern->std TSRMLS_CC);
346 
347 	while(intern->llist->count > 0) {
348 		tmp = (zval *)spl_ptr_llist_pop(intern->llist TSRMLS_CC);
349 		zval_ptr_dtor(&tmp);
350 	}
351 
352 	spl_ptr_llist_destroy(intern->llist TSRMLS_CC);
353 	SPL_LLIST_CHECK_DELREF(intern->traverse_pointer);
354 	zval_ptr_dtor(&intern->retval);
355 
356 	if (intern->debug_info != NULL) {
357 		zend_hash_destroy(intern->debug_info);
358 		efree(intern->debug_info);
359 	}
360 
361 	efree(object);
362 }
363 /* }}} */
364 
365 zend_object_iterator *spl_dllist_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC);
366 
spl_dllist_object_new_ex(zend_class_entry * class_type,spl_dllist_object ** obj,zval * orig,int clone_orig TSRMLS_DC)367 static zend_object_value spl_dllist_object_new_ex(zend_class_entry *class_type, spl_dllist_object **obj, zval *orig, int clone_orig TSRMLS_DC) /* {{{ */
368 {
369 	zend_object_value  retval = {0};
370 	spl_dllist_object *intern;
371 	zend_class_entry  *parent = class_type;
372 	int                inherited = 0;
373 
374 	intern = ecalloc(1, sizeof(spl_dllist_object));
375 	*obj = intern;
376 	ALLOC_INIT_ZVAL(intern->retval);
377 
378 	zend_object_std_init(&intern->std, class_type TSRMLS_CC);
379 	object_properties_init(&intern->std, class_type);
380 
381 	intern->flags = 0;
382 	intern->traverse_position = 0;
383 	intern->debug_info = NULL;
384 
385 	if (orig) {
386 		spl_dllist_object *other = (spl_dllist_object*)zend_object_store_get_object(orig TSRMLS_CC);
387 		intern->ce_get_iterator = other->ce_get_iterator;
388 
389 		if (clone_orig) {
390 			intern->llist = (spl_ptr_llist *)spl_ptr_llist_init(other->llist->ctor, other->llist->dtor);
391 			spl_ptr_llist_copy(other->llist, intern->llist TSRMLS_CC);
392 			intern->traverse_pointer  = intern->llist->head;
393 			SPL_LLIST_CHECK_ADDREF(intern->traverse_pointer);
394 		} else {
395 			intern->llist = other->llist;
396 			intern->traverse_pointer  = intern->llist->head;
397 			SPL_LLIST_CHECK_ADDREF(intern->traverse_pointer);
398 		}
399 
400 		intern->flags = other->flags;
401 	} else {
402 		intern->llist = (spl_ptr_llist *)spl_ptr_llist_init(spl_ptr_llist_zval_ctor, spl_ptr_llist_zval_dtor);
403 		intern->traverse_pointer  = intern->llist->head;
404 		SPL_LLIST_CHECK_ADDREF(intern->traverse_pointer);
405 	}
406 
407 	while (parent) {
408 		if (parent == spl_ce_SplStack) {
409 			intern->flags |= (SPL_DLLIST_IT_FIX | SPL_DLLIST_IT_LIFO);
410 			retval.handlers = &spl_handler_SplDoublyLinkedList;
411 		} else if (parent == spl_ce_SplQueue) {
412 			intern->flags |= SPL_DLLIST_IT_FIX;
413 			retval.handlers = &spl_handler_SplDoublyLinkedList;
414 		}
415 
416 		if (parent == spl_ce_SplDoublyLinkedList) {
417 			retval.handlers = &spl_handler_SplDoublyLinkedList;
418 			break;
419 		}
420 
421 		parent = parent->parent;
422 		inherited = 1;
423 	}
424 
425 	retval.handle = zend_objects_store_put(intern, (zend_objects_store_dtor_t)zend_objects_destroy_object, spl_dllist_object_free_storage, NULL TSRMLS_CC);
426 
427 	if (!parent) { /* this must never happen */
428 		php_error_docref(NULL TSRMLS_CC, E_COMPILE_ERROR, "Internal compiler error, Class is not child of SplDoublyLinkedList");
429 	}
430 	if (inherited) {
431 		zend_hash_find(&class_type->function_table, "offsetget",    sizeof("offsetget"),    (void **) &intern->fptr_offset_get);
432 		if (intern->fptr_offset_get->common.scope == parent) {
433 			intern->fptr_offset_get = NULL;
434 		}
435 		zend_hash_find(&class_type->function_table, "offsetset",    sizeof("offsetset"),    (void **) &intern->fptr_offset_set);
436 		if (intern->fptr_offset_set->common.scope == parent) {
437 			intern->fptr_offset_set = NULL;
438 		}
439 		zend_hash_find(&class_type->function_table, "offsetexists", sizeof("offsetexists"), (void **) &intern->fptr_offset_has);
440 		if (intern->fptr_offset_has->common.scope == parent) {
441 			intern->fptr_offset_has = NULL;
442 		}
443 		zend_hash_find(&class_type->function_table, "offsetunset",  sizeof("offsetunset"),  (void **) &intern->fptr_offset_del);
444 		if (intern->fptr_offset_del->common.scope == parent) {
445 			intern->fptr_offset_del = NULL;
446 		}
447 		zend_hash_find(&class_type->function_table, "count",        sizeof("count"),        (void **) &intern->fptr_count);
448 		if (intern->fptr_count->common.scope == parent) {
449 			intern->fptr_count = NULL;
450 		}
451 	}
452 
453 	return retval;
454 }
455 /* }}} */
456 
spl_dllist_object_new(zend_class_entry * class_type TSRMLS_DC)457 static zend_object_value spl_dllist_object_new(zend_class_entry *class_type TSRMLS_DC) /* {{{ */
458 {
459 	spl_dllist_object *tmp;
460 	return spl_dllist_object_new_ex(class_type, &tmp, NULL, 0 TSRMLS_CC);
461 }
462 /* }}} */
463 
spl_dllist_object_clone(zval * zobject TSRMLS_DC)464 static zend_object_value spl_dllist_object_clone(zval *zobject TSRMLS_DC) /* {{{ */
465 {
466 	zend_object_value   new_obj_val;
467 	zend_object        *old_object;
468 	zend_object        *new_object;
469 	zend_object_handle  handle = Z_OBJ_HANDLE_P(zobject);
470 	spl_dllist_object  *intern;
471 
472 	old_object  = zend_objects_get_address(zobject TSRMLS_CC);
473 	new_obj_val = spl_dllist_object_new_ex(old_object->ce, &intern, zobject, 1 TSRMLS_CC);
474 	new_object  = &intern->std;
475 
476 	zend_objects_clone_members(new_object, new_obj_val, old_object, handle TSRMLS_CC);
477 
478 	return new_obj_val;
479 }
480 /* }}} */
481 
spl_dllist_object_count_elements(zval * object,long * count TSRMLS_DC)482 static int spl_dllist_object_count_elements(zval *object, long *count TSRMLS_DC) /* {{{ */
483 {
484 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(object TSRMLS_CC);
485 
486 	if (intern->fptr_count) {
487 		zval *rv;
488 		zend_call_method_with_0_params(&object, intern->std.ce, &intern->fptr_count, "count", &rv);
489 		if (rv) {
490 			zval_ptr_dtor(&intern->retval);
491 			MAKE_STD_ZVAL(intern->retval);
492 			ZVAL_ZVAL(intern->retval, rv, 1, 1);
493 			convert_to_long(intern->retval);
494 			*count = (long) Z_LVAL_P(intern->retval);
495 			return SUCCESS;
496 		}
497 		*count = 0;
498 		return FAILURE;
499 	}
500 
501 	*count = spl_ptr_llist_count(intern->llist);
502 	return SUCCESS;
503 }
504 /* }}} */
505 
spl_dllist_object_get_debug_info(zval * obj,int * is_temp TSRMLS_DC)506 static HashTable* spl_dllist_object_get_debug_info(zval *obj, int *is_temp TSRMLS_DC) /* {{{{ */
507 {
508 	spl_dllist_object     *intern  = (spl_dllist_object*)zend_object_store_get_object(obj TSRMLS_CC);
509 	spl_ptr_llist_element *current = intern->llist->head, *next;
510 	zval *tmp, zrv, *dllist_array;
511 	char *pnstr;
512 	int  pnlen;
513 	int  i = 0;
514 
515 	*is_temp = 0;
516 
517 	if (intern->debug_info == NULL) {
518 		ALLOC_HASHTABLE(intern->debug_info);
519 		zend_hash_init(intern->debug_info, 1, NULL, ZVAL_PTR_DTOR, 0);
520 	}
521 
522 	if (intern->debug_info->nApplyCount == 0) {
523 		INIT_PZVAL(&zrv);
524 		Z_ARRVAL(zrv) = intern->debug_info;
525 
526 		if (!intern->std.properties) {
527 			rebuild_object_properties(&intern->std);
528 		}
529 		zend_hash_copy(intern->debug_info, intern->std.properties, (copy_ctor_func_t) zval_add_ref, (void *) &tmp, sizeof(zval *));
530 
531 		pnstr = spl_gen_private_prop_name(spl_ce_SplDoublyLinkedList, "flags", sizeof("flags")-1, &pnlen TSRMLS_CC);
532 		add_assoc_long_ex(&zrv, pnstr, pnlen+1, intern->flags);
533 		efree(pnstr);
534 
535 		ALLOC_INIT_ZVAL(dllist_array);
536 		array_init(dllist_array);
537 
538 		while (current) {
539 			next = current->next;
540 
541 			add_index_zval(dllist_array, i, (zval *)current->data);
542 			Z_ADDREF_P(current->data);
543 			i++;
544 
545 			current = next;
546 		}
547 
548 		pnstr = spl_gen_private_prop_name(spl_ce_SplDoublyLinkedList, "dllist", sizeof("dllist")-1, &pnlen TSRMLS_CC);
549 		add_assoc_zval_ex(&zrv, pnstr, pnlen+1, dllist_array);
550 		efree(pnstr);
551 	}
552 
553 	return intern->debug_info;
554 }
555 /* }}}} */
556 
557 /* {{{ proto bool SplDoublyLinkedList::push(mixed $value) U
558 	   Push $value on the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,push)559 SPL_METHOD(SplDoublyLinkedList, push)
560 {
561 	zval *value;
562 	spl_dllist_object *intern;
563 
564 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
565 		return;
566 	}
567 
568 	SEPARATE_ARG_IF_REF(value);
569 
570 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
571 	spl_ptr_llist_push(intern->llist, value TSRMLS_CC);
572 
573 	RETURN_TRUE;
574 }
575 /* }}} */
576 
577 /* {{{ proto bool SplDoublyLinkedList::unshift(mixed $value) U
578 	   Unshift $value on the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,unshift)579 SPL_METHOD(SplDoublyLinkedList, unshift)
580 {
581 	zval *value;
582 	spl_dllist_object *intern;
583 
584 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &value) == FAILURE) {
585 		return;
586 	}
587 
588 	SEPARATE_ARG_IF_REF(value);
589 
590 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
591 	spl_ptr_llist_unshift(intern->llist, value TSRMLS_CC);
592 
593 	RETURN_TRUE;
594 }
595 /* }}} */
596 
597 /* {{{ proto mixed SplDoublyLinkedList::pop() U
598 	   Pop an element out of the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,pop)599 SPL_METHOD(SplDoublyLinkedList, pop)
600 {
601 	zval *value;
602 	spl_dllist_object *intern;
603 
604 	if (zend_parse_parameters_none() == FAILURE) {
605 		return;
606 	}
607 
608 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
609 	value = (zval *)spl_ptr_llist_pop(intern->llist TSRMLS_CC);
610 
611 	if (value == NULL) {
612 		zend_throw_exception(spl_ce_RuntimeException, "Can't pop from an empty datastructure", 0 TSRMLS_CC);
613 		return;
614 	}
615 
616 	RETURN_ZVAL(value, 1, 1);
617 }
618 /* }}} */
619 
620 /* {{{ proto mixed SplDoublyLinkedList::shift() U
621 	   Shift an element out of the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,shift)622 SPL_METHOD(SplDoublyLinkedList, shift)
623 {
624 	zval *value;
625 	spl_dllist_object *intern;
626 
627 	if (zend_parse_parameters_none() == FAILURE) {
628 		return;
629 	}
630 
631 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
632 	value  = (zval *)spl_ptr_llist_shift(intern->llist TSRMLS_CC);
633 
634 	if (value == NULL) {
635 		zend_throw_exception(spl_ce_RuntimeException, "Can't shift from an empty datastructure", 0 TSRMLS_CC);
636 		return;
637 	}
638 
639 	RETURN_ZVAL(value, 1, 1);
640 }
641 /* }}} */
642 
643 /* {{{ proto mixed SplDoublyLinkedList::top() U
644 	   Peek at the top element of the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,top)645 SPL_METHOD(SplDoublyLinkedList, top)
646 {
647 	zval *value;
648 	spl_dllist_object *intern;
649 
650 	if (zend_parse_parameters_none() == FAILURE) {
651 		return;
652 	}
653 
654 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
655 	value  = (zval *)spl_ptr_llist_last(intern->llist);
656 
657 	if (value == NULL) {
658 		zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty datastructure", 0 TSRMLS_CC);
659 		return;
660 	}
661 
662 	RETURN_ZVAL(value, 1, 0);
663 }
664 /* }}} */
665 
666 /* {{{ proto mixed SplDoublyLinkedList::bottom() U
667 	   Peek at the bottom element of the SplDoublyLinkedList */
SPL_METHOD(SplDoublyLinkedList,bottom)668 SPL_METHOD(SplDoublyLinkedList, bottom)
669 {
670 	zval *value;
671 	spl_dllist_object *intern;
672 
673 	if (zend_parse_parameters_none() == FAILURE) {
674 		return;
675 	}
676 
677 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
678 	value  = (zval *)spl_ptr_llist_first(intern->llist);
679 
680 	if (value == NULL) {
681 		zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty datastructure", 0 TSRMLS_CC);
682 		return;
683 	}
684 
685 	RETURN_ZVAL(value, 1, 0);
686 }
687 /* }}} */
688 
689 /* {{{ proto int SplDoublyLinkedList::count() U
690  Return the number of elements in the datastructure. */
SPL_METHOD(SplDoublyLinkedList,count)691 SPL_METHOD(SplDoublyLinkedList, count)
692 {
693 	long count;
694 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
695 
696 	if (zend_parse_parameters_none() == FAILURE) {
697 		return;
698 	}
699 
700 	count = spl_ptr_llist_count(intern->llist);
701 	RETURN_LONG(count);
702 }
703 /* }}} */
704 
705 /* {{{ proto int SplDoublyLinkedList::isEmpty() U
706  Return true if the SplDoublyLinkedList is empty. */
SPL_METHOD(SplDoublyLinkedList,isEmpty)707 SPL_METHOD(SplDoublyLinkedList, isEmpty)
708 {
709 	long count;
710 
711 	if (zend_parse_parameters_none() == FAILURE) {
712 		return;
713 	}
714 
715 	spl_dllist_object_count_elements(getThis(), &count TSRMLS_CC);
716 	RETURN_BOOL(count==0);
717 }
718 /* }}} */
719 
720 /* {{{ proto int SplDoublyLinkedList::setIteratorMode($flags) U
721  Set the mode of iteration */
SPL_METHOD(SplDoublyLinkedList,setIteratorMode)722 SPL_METHOD(SplDoublyLinkedList, setIteratorMode)
723 {
724 	long value;
725 	spl_dllist_object *intern;
726 
727 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "l", &value) == FAILURE) {
728 		return;
729 	}
730 
731 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
732 
733 	if (intern->flags & SPL_DLLIST_IT_FIX
734 		&& (intern->flags & SPL_DLLIST_IT_LIFO) != (value & SPL_DLLIST_IT_LIFO)) {
735 		zend_throw_exception(spl_ce_RuntimeException, "Iterators' LIFO/FIFO modes for SplStack/SplQueue objects are frozen", 0 TSRMLS_CC);
736 		return;
737 	}
738 
739 	intern->flags = value & SPL_DLLIST_IT_MASK;
740 
741 	RETURN_LONG(intern->flags);
742 }
743 /* }}} */
744 
745 /* {{{ proto int SplDoublyLinkedList::getIteratorMode() U
746  Return the mode of iteration */
SPL_METHOD(SplDoublyLinkedList,getIteratorMode)747 SPL_METHOD(SplDoublyLinkedList, getIteratorMode)
748 {
749 	spl_dllist_object *intern;
750 
751 	if (zend_parse_parameters_none() == FAILURE) {
752 		return;
753 	}
754 
755 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
756 
757 	RETURN_LONG(intern->flags);
758 }
759 /* }}} */
760 
761 /* {{{ proto bool SplDoublyLinkedList::offsetExists(mixed $index) U
762  Returns whether the requested $index exists. */
SPL_METHOD(SplDoublyLinkedList,offsetExists)763 SPL_METHOD(SplDoublyLinkedList, offsetExists)
764 {
765 	zval              *zindex;
766 	spl_dllist_object *intern;
767 	long               index;
768 
769 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &zindex) == FAILURE) {
770 		return;
771 	}
772 
773 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
774 	index  = spl_offset_convert_to_long(zindex TSRMLS_CC);
775 
776 	RETURN_BOOL(index >= 0 && index < intern->llist->count);
777 } /* }}} */
778 
779 /* {{{ proto mixed SplDoublyLinkedList::offsetGet(mixed $index) U
780  Returns the value at the specified $index. */
SPL_METHOD(SplDoublyLinkedList,offsetGet)781 SPL_METHOD(SplDoublyLinkedList, offsetGet)
782 {
783 	zval                  *zindex, *value;
784 	long                   index;
785 	spl_dllist_object     *intern;
786 	spl_ptr_llist_element *element;
787 
788 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &zindex) == FAILURE) {
789 		return;
790 	}
791 
792 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
793 	index  = spl_offset_convert_to_long(zindex TSRMLS_CC);
794 
795 	if (index < 0 || index >= intern->llist->count) {
796 		zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid or out of range", 0 TSRMLS_CC);
797 		return;
798 	}
799 
800 	element = spl_ptr_llist_offset(intern->llist, index, intern->flags & SPL_DLLIST_IT_LIFO);
801 
802 	if (element != NULL) {
803 		value = (zval *)element->data;
804 		RETURN_ZVAL(value, 1, 0);
805 	} else {
806 		zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid", 0 TSRMLS_CC);
807 		return;
808 	}
809 } /* }}} */
810 
811 /* {{{ proto void SplDoublyLinkedList::offsetSet(mixed $index, mixed $newval) U
812  Sets the value at the specified $index to $newval. */
SPL_METHOD(SplDoublyLinkedList,offsetSet)813 SPL_METHOD(SplDoublyLinkedList, offsetSet)
814 {
815 	zval                  *zindex, *value;
816 	spl_dllist_object     *intern;
817 
818 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &zindex, &value) == FAILURE) {
819 		return;
820 	}
821 	SEPARATE_ARG_IF_REF(value);
822 
823 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
824 
825 	if (Z_TYPE_P(zindex) == IS_NULL) {
826 		/* $obj[] = ... */
827 		spl_ptr_llist_push(intern->llist, value TSRMLS_CC);
828 	} else {
829 		/* $obj[$foo] = ... */
830 		long                   index;
831 		spl_ptr_llist_element *element;
832 
833 		index = spl_offset_convert_to_long(zindex TSRMLS_CC);
834 
835 		if (index < 0 || index >= intern->llist->count) {
836 			zval_ptr_dtor(&value);
837 			zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid or out of range", 0 TSRMLS_CC);
838 			return;
839 		}
840 
841 		element = spl_ptr_llist_offset(intern->llist, index, intern->flags & SPL_DLLIST_IT_LIFO);
842 
843 		if (element != NULL) {
844 			/* call dtor on the old element as in spl_ptr_llist_pop */
845 			if (intern->llist->dtor) {
846 				intern->llist->dtor(element TSRMLS_CC);
847 			}
848 
849 			/* the element is replaced, delref the old one as in
850 			 * SplDoublyLinkedList::pop() */
851 			zval_ptr_dtor((zval **)&element->data);
852 			element->data = value;
853 
854 			/* new element, call ctor as in spl_ptr_llist_push */
855 			if (intern->llist->ctor) {
856 				intern->llist->ctor(element TSRMLS_CC);
857 			}
858 		} else {
859 			zval_ptr_dtor(&value);
860 			zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid", 0 TSRMLS_CC);
861 			return;
862 		}
863 	}
864 } /* }}} */
865 
866 /* {{{ proto void SplDoublyLinkedList::offsetUnset(mixed $index) U
867  Unsets the value at the specified $index. */
SPL_METHOD(SplDoublyLinkedList,offsetUnset)868 SPL_METHOD(SplDoublyLinkedList, offsetUnset)
869 {
870 	zval                  *zindex;
871 	long                   index;
872 	spl_dllist_object     *intern;
873 	spl_ptr_llist_element *element;
874 	spl_ptr_llist         *llist;
875 
876 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z", &zindex) == FAILURE) {
877 		return;
878 	}
879 
880 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
881 	index  = spl_offset_convert_to_long(zindex TSRMLS_CC);
882 	llist  = intern->llist;
883 
884 	if (index < 0 || index >= intern->llist->count) {
885 		zend_throw_exception(spl_ce_OutOfRangeException, "Offset out of range", 0 TSRMLS_CC);
886 		return;
887 	}
888 
889 	element = spl_ptr_llist_offset(intern->llist, index, intern->flags & SPL_DLLIST_IT_LIFO);
890 
891 	if (element != NULL) {
892 		/* connect the neightbors */
893 		if (element->prev) {
894 			element->prev->next = element->next;
895 		}
896 
897 		if (element->next) {
898 			element->next->prev = element->prev;
899 		}
900 
901 		/* take care of head/tail */
902 		if (element == llist->head) {
903 			llist->head = element->next;
904 		}
905 
906 		if (element == llist->tail) {
907 			llist->tail = element->prev;
908 		}
909 
910 		/* finally, delete the element */
911 		llist->count--;
912 
913 		if(llist->dtor) {
914 			llist->dtor(element TSRMLS_CC);
915 		}
916 
917 		if (intern->traverse_pointer == element) {
918 			SPL_LLIST_DELREF(element);
919 			intern->traverse_pointer = NULL;
920 		}
921 
922 		zval_ptr_dtor((zval **)&element->data);
923 		element->data = NULL;
924 
925 		SPL_LLIST_DELREF(element);
926 	} else {
927 		zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid", 0 TSRMLS_CC);
928 		return;
929 	}
930 } /* }}} */
931 
spl_dllist_it_dtor(zend_object_iterator * iter TSRMLS_DC)932 static void spl_dllist_it_dtor(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
933 {
934 	spl_dllist_it *iterator = (spl_dllist_it *)iter;
935 
936 	SPL_LLIST_CHECK_DELREF(iterator->traverse_pointer);
937 
938 	zend_user_it_invalidate_current(iter TSRMLS_CC);
939 	zval_ptr_dtor((zval**)&iterator->intern.it.data);
940 
941 	efree(iterator);
942 }
943 /* }}} */
944 
spl_dllist_it_helper_rewind(spl_ptr_llist_element ** traverse_pointer_ptr,int * traverse_position_ptr,spl_ptr_llist * llist,int flags TSRMLS_DC)945 static void spl_dllist_it_helper_rewind(spl_ptr_llist_element **traverse_pointer_ptr, int *traverse_position_ptr, spl_ptr_llist *llist, int flags TSRMLS_DC) /* {{{ */
946 {
947 	SPL_LLIST_CHECK_DELREF(*traverse_pointer_ptr);
948 
949 	if (flags & SPL_DLLIST_IT_LIFO) {
950 		*traverse_position_ptr = llist->count-1;
951 		*traverse_pointer_ptr  = llist->tail;
952 	} else {
953 		*traverse_position_ptr = 0;
954 		*traverse_pointer_ptr  = llist->head;
955 	}
956 
957 	SPL_LLIST_CHECK_ADDREF(*traverse_pointer_ptr);
958 }
959 /* }}} */
960 
spl_dllist_it_helper_move_forward(spl_ptr_llist_element ** traverse_pointer_ptr,int * traverse_position_ptr,spl_ptr_llist * llist,int flags TSRMLS_DC)961 static void spl_dllist_it_helper_move_forward(spl_ptr_llist_element **traverse_pointer_ptr, int *traverse_position_ptr, spl_ptr_llist *llist, int flags TSRMLS_DC) /* {{{ */
962 {
963 	if (*traverse_pointer_ptr) {
964 		spl_ptr_llist_element *old = *traverse_pointer_ptr;
965 
966 		if (flags & SPL_DLLIST_IT_LIFO) {
967 			*traverse_pointer_ptr = old->prev;
968 			(*traverse_position_ptr)--;
969 
970 			if (flags & SPL_DLLIST_IT_DELETE) {
971 				zval *prev = (zval *)spl_ptr_llist_pop(llist TSRMLS_CC);
972 
973 				if (prev) {
974 					zval_ptr_dtor((zval **)&prev);
975 				}
976 			}
977 		} else {
978 			*traverse_pointer_ptr = old->next;
979 
980 			if (flags & SPL_DLLIST_IT_DELETE) {
981 				zval *prev = (zval *)spl_ptr_llist_shift(llist TSRMLS_CC);
982 
983 				if (prev) {
984 					zval_ptr_dtor((zval **)&prev);
985 				}
986 			} else {
987 				(*traverse_position_ptr)++;
988 			}
989 		}
990 
991 		SPL_LLIST_DELREF(old);
992 		SPL_LLIST_CHECK_ADDREF(*traverse_pointer_ptr);
993 	}
994 }
995 /* }}} */
996 
spl_dllist_it_rewind(zend_object_iterator * iter TSRMLS_DC)997 static void spl_dllist_it_rewind(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
998 {
999 	spl_dllist_it     *iterator = (spl_dllist_it *)iter;
1000 	spl_dllist_object *object   = iterator->object;
1001 	spl_ptr_llist     *llist    = object->llist;
1002 
1003 	spl_dllist_it_helper_rewind(&iterator->traverse_pointer, &iterator->traverse_position, llist, object->flags TSRMLS_CC);
1004 }
1005 /* }}} */
1006 
spl_dllist_it_valid(zend_object_iterator * iter TSRMLS_DC)1007 static int spl_dllist_it_valid(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
1008 {
1009 	spl_dllist_it         *iterator = (spl_dllist_it *)iter;
1010 	spl_ptr_llist_element *element  = iterator->traverse_pointer;
1011 
1012 	return (element != NULL ? SUCCESS : FAILURE);
1013 }
1014 /* }}} */
1015 
spl_dllist_it_get_current_data(zend_object_iterator * iter,zval *** data TSRMLS_DC)1016 static void spl_dllist_it_get_current_data(zend_object_iterator *iter, zval ***data TSRMLS_DC) /* {{{ */
1017 {
1018 	spl_dllist_it         *iterator = (spl_dllist_it *)iter;
1019 	spl_ptr_llist_element *element  = iterator->traverse_pointer;
1020 
1021 	if (element == NULL || element->data == NULL) {
1022 		*data = NULL;
1023 	} else {
1024 		*data = (zval **)&element->data;
1025 	}
1026 }
1027 /* }}} */
1028 
spl_dllist_it_get_current_key(zend_object_iterator * iter,zval * key TSRMLS_DC)1029 static void spl_dllist_it_get_current_key(zend_object_iterator *iter, zval *key TSRMLS_DC) /* {{{ */
1030 {
1031 	spl_dllist_it *iterator = (spl_dllist_it *)iter;
1032 
1033 	ZVAL_LONG(key, iterator->traverse_position);
1034 }
1035 /* }}} */
1036 
spl_dllist_it_move_forward(zend_object_iterator * iter TSRMLS_DC)1037 static void spl_dllist_it_move_forward(zend_object_iterator *iter TSRMLS_DC) /* {{{ */
1038 {
1039 	spl_dllist_it     *iterator = (spl_dllist_it *)iter;
1040 	spl_dllist_object *object   = iterator->object;
1041 
1042 	zend_user_it_invalidate_current(iter TSRMLS_CC);
1043 
1044 	spl_dllist_it_helper_move_forward(&iterator->traverse_pointer, &iterator->traverse_position, object->llist, object->flags TSRMLS_CC);
1045 }
1046 /* }}} */
1047 
1048 /* {{{  proto int SplDoublyLinkedList::key() U
1049    Return current array key */
SPL_METHOD(SplDoublyLinkedList,key)1050 SPL_METHOD(SplDoublyLinkedList, key)
1051 {
1052 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1053 
1054 	if (zend_parse_parameters_none() == FAILURE) {
1055 		return;
1056 	}
1057 
1058 	RETURN_LONG(intern->traverse_position);
1059 }
1060 /* }}} */
1061 
1062 /* {{{ proto void SplDoublyLinkedList::prev() U
1063    Move to next entry */
SPL_METHOD(SplDoublyLinkedList,prev)1064 SPL_METHOD(SplDoublyLinkedList, prev)
1065 {
1066 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1067 
1068 	if (zend_parse_parameters_none() == FAILURE) {
1069 		return;
1070 	}
1071 
1072 	spl_dllist_it_helper_move_forward(&intern->traverse_pointer, &intern->traverse_position, intern->llist, intern->flags ^ SPL_DLLIST_IT_LIFO TSRMLS_CC);
1073 }
1074 /* }}} */
1075 
1076 /* {{{ proto void SplDoublyLinkedList::next() U
1077    Move to next entry */
SPL_METHOD(SplDoublyLinkedList,next)1078 SPL_METHOD(SplDoublyLinkedList, next)
1079 {
1080 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1081 
1082 	if (zend_parse_parameters_none() == FAILURE) {
1083 		return;
1084 	}
1085 
1086 	spl_dllist_it_helper_move_forward(&intern->traverse_pointer, &intern->traverse_position, intern->llist, intern->flags TSRMLS_CC);
1087 }
1088 /* }}} */
1089 
1090 /* {{{ proto bool SplDoublyLinkedList::valid() U
1091    Check whether the datastructure contains more entries */
SPL_METHOD(SplDoublyLinkedList,valid)1092 SPL_METHOD(SplDoublyLinkedList, valid)
1093 {
1094 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1095 
1096 	if (zend_parse_parameters_none() == FAILURE) {
1097 		return;
1098 	}
1099 
1100 	RETURN_BOOL(intern->traverse_pointer != NULL);
1101 }
1102 /* }}} */
1103 
1104 /* {{{ proto void SplDoublyLinkedList::rewind() U
1105    Rewind the datastructure back to the start */
SPL_METHOD(SplDoublyLinkedList,rewind)1106 SPL_METHOD(SplDoublyLinkedList, rewind)
1107 {
1108 	spl_dllist_object *intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1109 
1110 	if (zend_parse_parameters_none() == FAILURE) {
1111 		return;
1112 	}
1113 
1114 	spl_dllist_it_helper_rewind(&intern->traverse_pointer, &intern->traverse_position, intern->llist, intern->flags TSRMLS_CC);
1115 }
1116 /* }}} */
1117 
1118 /* {{{ proto mixed|NULL SplDoublyLinkedList::current() U
1119    Return current datastructure entry */
SPL_METHOD(SplDoublyLinkedList,current)1120 SPL_METHOD(SplDoublyLinkedList, current)
1121 {
1122 	spl_dllist_object     *intern  = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1123 	spl_ptr_llist_element *element = intern->traverse_pointer;
1124 
1125 	if (zend_parse_parameters_none() == FAILURE) {
1126 		return;
1127 	}
1128 
1129 	if (element == NULL || element->data == NULL) {
1130 		RETURN_NULL();
1131 	} else {
1132 		zval *data    = (zval *)element->data;
1133 		RETURN_ZVAL(data, 1, 0);
1134 	}
1135 }
1136 /* }}} */
1137 /* {{{ proto string SplDoublyLinkedList::serialize()
1138  Serializes storage */
SPL_METHOD(SplDoublyLinkedList,serialize)1139 SPL_METHOD(SplDoublyLinkedList, serialize)
1140 {
1141 	spl_dllist_object     *intern   = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1142 	smart_str              buf      = {0};
1143 	spl_ptr_llist_element *current  = intern->llist->head, *next;
1144 	zval                   *flags;
1145 	php_serialize_data_t   var_hash;
1146 
1147 	if (zend_parse_parameters_none() == FAILURE) {
1148 		return;
1149 	}
1150 
1151 	PHP_VAR_SERIALIZE_INIT(var_hash);
1152 
1153 	/* flags */
1154 	MAKE_STD_ZVAL(flags);
1155 	ZVAL_LONG(flags, intern->flags);
1156 	php_var_serialize(&buf, &flags, &var_hash TSRMLS_CC);
1157 	zval_ptr_dtor(&flags);
1158 
1159 	/* elements */
1160 	while (current) {
1161 		smart_str_appendc(&buf, ':');
1162 		next = current->next;
1163 
1164 		php_var_serialize(&buf, (zval **)&current->data, &var_hash TSRMLS_CC);
1165 
1166 		current = next;
1167 	}
1168 
1169 	smart_str_0(&buf);
1170 
1171 	/* done */
1172 	PHP_VAR_SERIALIZE_DESTROY(var_hash);
1173 
1174 	if (buf.c) {
1175 		RETURN_STRINGL(buf.c, buf.len, 0);
1176 	} else {
1177 		RETURN_NULL();
1178 	}
1179 
1180 } /* }}} */
1181 
1182 /* {{{ proto void SplDoublyLinkedList::unserialize(string serialized)
1183  Unserializes storage */
SPL_METHOD(SplDoublyLinkedList,unserialize)1184 SPL_METHOD(SplDoublyLinkedList, unserialize)
1185 {
1186 	spl_dllist_object     *intern   = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1187 	zval                  *flags, *elem;
1188 	char *buf;
1189 	int buf_len;
1190 	const unsigned char *p, *s;
1191 	php_unserialize_data_t var_hash;
1192 
1193 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "s", &buf, &buf_len) == FAILURE) {
1194 		return;
1195 	}
1196 
1197 	if (buf_len == 0) {
1198 		return;
1199 	}
1200 
1201 	s = p = (const unsigned char*)buf;
1202 	PHP_VAR_UNSERIALIZE_INIT(var_hash);
1203 
1204 	/* flags */
1205 	ALLOC_INIT_ZVAL(flags);
1206 	if (!php_var_unserialize(&flags, &p, s + buf_len, &var_hash TSRMLS_CC) || Z_TYPE_P(flags) != IS_LONG) {
1207 		zval_ptr_dtor(&flags);
1208 		goto error;
1209 	}
1210 	var_push_dtor(&var_hash, &flags);
1211 	intern->flags = Z_LVAL_P(flags);
1212 	zval_ptr_dtor(&flags);
1213 
1214 	/* elements */
1215 	while(*p == ':') {
1216 		++p;
1217 		ALLOC_INIT_ZVAL(elem);
1218 		if (!php_var_unserialize(&elem, &p, s + buf_len, &var_hash TSRMLS_CC)) {
1219 			zval_ptr_dtor(&elem);
1220 			goto error;
1221 		}
1222 		var_push_dtor(&var_hash, &elem);
1223 
1224 		spl_ptr_llist_push(intern->llist, elem TSRMLS_CC);
1225 	}
1226 
1227 	if (*p != '\0') {
1228 		goto error;
1229 	}
1230 
1231 	PHP_VAR_UNSERIALIZE_DESTROY(var_hash);
1232 	return;
1233 
1234 error:
1235 	PHP_VAR_UNSERIALIZE_DESTROY(var_hash);
1236 	zend_throw_exception_ex(spl_ce_UnexpectedValueException, 0 TSRMLS_CC, "Error at offset %ld of %d bytes", (long)((char*)p - buf), buf_len);
1237 	return;
1238 
1239 } /* }}} */
1240 
1241 /* {{{ proto void SplDoublyLinkedList::add(mixed $index, mixed $newval) U
1242  Inserts a new entry before the specified $index consisting of $newval. */
SPL_METHOD(SplDoublyLinkedList,add)1243 SPL_METHOD(SplDoublyLinkedList, add)
1244 {
1245 	zval                  *zindex, *value;
1246 	spl_dllist_object     *intern;
1247 	spl_ptr_llist_element *element;
1248 	long                  index;
1249 
1250 	if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz", &zindex, &value) == FAILURE) {
1251 		return;
1252 	}
1253 
1254 	intern = (spl_dllist_object*)zend_object_store_get_object(getThis() TSRMLS_CC);
1255 	index  = spl_offset_convert_to_long(zindex TSRMLS_CC);
1256 
1257 	if (index < 0 || index > intern->llist->count) {
1258 		zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid or out of range", 0 TSRMLS_CC);
1259 		return;
1260 	}
1261 
1262 	Z_ADDREF_P(value);
1263 	if (index == intern->llist->count) {
1264 		/* If index is the last entry+1 then we do a push because we're not inserting before any entry */
1265 		spl_ptr_llist_push(intern->llist, value TSRMLS_CC);
1266 	} else {
1267 		/* Create the new element we want to insert */
1268 		spl_ptr_llist_element *elem = emalloc(sizeof(spl_ptr_llist_element));
1269 
1270 		/* Get the element we want to insert before */
1271 		element = spl_ptr_llist_offset(intern->llist, index, intern->flags & SPL_DLLIST_IT_LIFO);
1272 
1273 		elem->data = value;
1274 		elem->rc   = 1;
1275 		/* connect to the neighbours */
1276 		elem->next = element;
1277 		elem->prev = element->prev;
1278 
1279 		/* connect the neighbours to this new element */
1280 		if (elem->prev == NULL) {
1281 			intern->llist->head = elem;
1282 		} else {
1283 			element->prev->next = elem;
1284 		}
1285 		element->prev = elem;
1286 
1287 		intern->llist->count++;
1288 
1289 		if (intern->llist->ctor) {
1290 			intern->llist->ctor(elem TSRMLS_CC);
1291 		}
1292 	}
1293 } /* }}} */
1294 
1295 
1296 /* iterator handler table */
1297 zend_object_iterator_funcs spl_dllist_it_funcs = {
1298 	spl_dllist_it_dtor,
1299 	spl_dllist_it_valid,
1300 	spl_dllist_it_get_current_data,
1301 	spl_dllist_it_get_current_key,
1302 	spl_dllist_it_move_forward,
1303 	spl_dllist_it_rewind
1304 };
1305 
spl_dllist_get_iterator(zend_class_entry * ce,zval * object,int by_ref TSRMLS_DC)1306 zend_object_iterator *spl_dllist_get_iterator(zend_class_entry *ce, zval *object, int by_ref TSRMLS_DC) /* {{{ */
1307 {
1308 	spl_dllist_it     *iterator;
1309 	spl_dllist_object *dllist_object = (spl_dllist_object*)zend_object_store_get_object(object TSRMLS_CC);
1310 
1311 	if (by_ref) {
1312 		zend_throw_exception(spl_ce_RuntimeException, "An iterator cannot be used with foreach by reference", 0 TSRMLS_CC);
1313 		return NULL;
1314 	}
1315 
1316 	Z_ADDREF_P(object);
1317 
1318 	iterator                     = emalloc(sizeof(spl_dllist_it));
1319 	iterator->intern.it.data     = (void*)object;
1320 	iterator->intern.it.funcs    = &spl_dllist_it_funcs;
1321 	iterator->intern.ce          = ce;
1322 	iterator->intern.value       = NULL;
1323 	iterator->traverse_position  = dllist_object->traverse_position;
1324 	iterator->traverse_pointer   = dllist_object->traverse_pointer;
1325 	iterator->flags              = dllist_object->flags & SPL_DLLIST_IT_MASK;
1326 	iterator->object             = dllist_object;
1327 
1328 	SPL_LLIST_CHECK_ADDREF(iterator->traverse_pointer);
1329 
1330 
1331 	return (zend_object_iterator*)iterator;
1332 }
1333 /* }}} */
1334 
1335 /*  Function/Class/Method definitions */
1336 ZEND_BEGIN_ARG_INFO(arginfo_dllist_setiteratormode, 0)
1337 	ZEND_ARG_INFO(0, flags)
1338 ZEND_END_ARG_INFO()
1339 
1340 ZEND_BEGIN_ARG_INFO(arginfo_dllist_push, 0)
1341 	ZEND_ARG_INFO(0, value)
1342 ZEND_END_ARG_INFO()
1343 
1344 ZEND_BEGIN_ARG_INFO_EX(arginfo_dllist_offsetGet, 0, 0, 1)
1345 	ZEND_ARG_INFO(0, index)
1346 ZEND_END_ARG_INFO()
1347 
1348 ZEND_BEGIN_ARG_INFO_EX(arginfo_dllist_offsetSet, 0, 0, 2)
1349 	ZEND_ARG_INFO(0, index)
1350 	ZEND_ARG_INFO(0, newval)
1351 ZEND_END_ARG_INFO()
1352 
1353 ZEND_BEGIN_ARG_INFO(arginfo_dllist_void, 0)
1354 ZEND_END_ARG_INFO()
1355 
1356 ZEND_BEGIN_ARG_INFO(arginfo_dllist_serialized, 0)
1357 	ZEND_ARG_INFO(0, serialized)
1358 ZEND_END_ARG_INFO();
1359 
1360 static const zend_function_entry spl_funcs_SplQueue[] = {
1361 	SPL_MA(SplQueue, enqueue, SplDoublyLinkedList, push,  arginfo_dllist_push, ZEND_ACC_PUBLIC)
1362 	SPL_MA(SplQueue, dequeue, SplDoublyLinkedList, shift, arginfo_dllist_void, ZEND_ACC_PUBLIC)
1363 	PHP_FE_END
1364 };
1365 
1366 static const zend_function_entry spl_funcs_SplDoublyLinkedList[] = {
1367 	SPL_ME(SplDoublyLinkedList, pop,             arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1368 	SPL_ME(SplDoublyLinkedList, shift,           arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1369 	SPL_ME(SplDoublyLinkedList, push,            arginfo_dllist_push,            ZEND_ACC_PUBLIC)
1370 	SPL_ME(SplDoublyLinkedList, unshift,         arginfo_dllist_push,            ZEND_ACC_PUBLIC)
1371 	SPL_ME(SplDoublyLinkedList, top,             arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1372 	SPL_ME(SplDoublyLinkedList, bottom,          arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1373 	SPL_ME(SplDoublyLinkedList, isEmpty,         arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1374 	SPL_ME(SplDoublyLinkedList, setIteratorMode, arginfo_dllist_setiteratormode, ZEND_ACC_PUBLIC)
1375 	SPL_ME(SplDoublyLinkedList, getIteratorMode, arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1376 	/* Countable */
1377 	SPL_ME(SplDoublyLinkedList, count,           arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1378 	/* ArrayAccess */
1379 	SPL_ME(SplDoublyLinkedList, offsetExists,    arginfo_dllist_offsetGet,       ZEND_ACC_PUBLIC)
1380 	SPL_ME(SplDoublyLinkedList, offsetGet,       arginfo_dllist_offsetGet,       ZEND_ACC_PUBLIC)
1381 	SPL_ME(SplDoublyLinkedList, offsetSet,       arginfo_dllist_offsetSet,       ZEND_ACC_PUBLIC)
1382 	SPL_ME(SplDoublyLinkedList, offsetUnset,     arginfo_dllist_offsetGet,       ZEND_ACC_PUBLIC)
1383 
1384 	SPL_ME(SplDoublyLinkedList, add,             arginfo_dllist_offsetSet,       ZEND_ACC_PUBLIC)
1385 
1386 	/* Iterator */
1387 	SPL_ME(SplDoublyLinkedList, rewind,          arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1388 	SPL_ME(SplDoublyLinkedList, current,         arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1389 	SPL_ME(SplDoublyLinkedList, key,             arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1390 	SPL_ME(SplDoublyLinkedList, next,            arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1391 	SPL_ME(SplDoublyLinkedList, prev,            arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1392 	SPL_ME(SplDoublyLinkedList, valid,           arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1393 	/* Serializable */
1394 	SPL_ME(SplDoublyLinkedList,  unserialize,    arginfo_dllist_serialized,      ZEND_ACC_PUBLIC)
1395 	SPL_ME(SplDoublyLinkedList,  serialize,      arginfo_dllist_void,            ZEND_ACC_PUBLIC)
1396 	PHP_FE_END
1397 };
1398 /* }}} */
1399 
PHP_MINIT_FUNCTION(spl_dllist)1400 PHP_MINIT_FUNCTION(spl_dllist) /* {{{ */
1401 {
1402 	REGISTER_SPL_STD_CLASS_EX(SplDoublyLinkedList, spl_dllist_object_new, spl_funcs_SplDoublyLinkedList);
1403 	memcpy(&spl_handler_SplDoublyLinkedList, zend_get_std_object_handlers(), sizeof(zend_object_handlers));
1404 
1405 	spl_handler_SplDoublyLinkedList.clone_obj      = spl_dllist_object_clone;
1406 	spl_handler_SplDoublyLinkedList.count_elements = spl_dllist_object_count_elements;
1407 	spl_handler_SplDoublyLinkedList.get_debug_info = spl_dllist_object_get_debug_info;
1408 
1409 	REGISTER_SPL_CLASS_CONST_LONG(SplDoublyLinkedList, "IT_MODE_LIFO",  SPL_DLLIST_IT_LIFO);
1410 	REGISTER_SPL_CLASS_CONST_LONG(SplDoublyLinkedList, "IT_MODE_FIFO",  0);
1411 	REGISTER_SPL_CLASS_CONST_LONG(SplDoublyLinkedList, "IT_MODE_DELETE",SPL_DLLIST_IT_DELETE);
1412 	REGISTER_SPL_CLASS_CONST_LONG(SplDoublyLinkedList, "IT_MODE_KEEP",  0);
1413 
1414 	REGISTER_SPL_IMPLEMENTS(SplDoublyLinkedList, Iterator);
1415 	REGISTER_SPL_IMPLEMENTS(SplDoublyLinkedList, Countable);
1416 	REGISTER_SPL_IMPLEMENTS(SplDoublyLinkedList, ArrayAccess);
1417 	REGISTER_SPL_IMPLEMENTS(SplDoublyLinkedList, Serializable);
1418 
1419 	spl_ce_SplDoublyLinkedList->get_iterator = spl_dllist_get_iterator;
1420 
1421 	REGISTER_SPL_SUB_CLASS_EX(SplQueue,           SplDoublyLinkedList,        spl_dllist_object_new, spl_funcs_SplQueue);
1422 	REGISTER_SPL_SUB_CLASS_EX(SplStack,           SplDoublyLinkedList,        spl_dllist_object_new, NULL);
1423 
1424 	spl_ce_SplQueue->get_iterator = spl_dllist_get_iterator;
1425 	spl_ce_SplStack->get_iterator = spl_dllist_get_iterator;
1426 
1427 	return SUCCESS;
1428 }
1429 /* }}} */
1430 /*
1431  * Local variables:
1432  * tab-width: 4
1433  * c-basic-offset: 4
1434  * End:
1435  * vim600: fdm=marker
1436  * vim: noet sw=4 ts=4
1437  */
1438