ext/spl/spl_dllist.c

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

DEFINITIONS
