Coverage Report

Created: 2025-06-13 06:43

/src/php-src/ext/spl/spl_heap.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
   +----------------------------------------------------------------------+
3
   | Copyright (c) The PHP Group                                          |
4
   +----------------------------------------------------------------------+
5
   | This source file is subject to version 3.01 of the PHP license,      |
6
   | that is bundled with this package in the file LICENSE, and is        |
7
   | available through the world-wide-web at the following url:           |
8
   | https://www.php.net/license/3_01.txt                                 |
9
   | If you did not receive a copy of the PHP license and are unable to   |
10
   | obtain it through the world-wide-web, please send a note to          |
11
   | license@php.net so we can mail you a copy immediately.               |
12
   +----------------------------------------------------------------------+
13
   | Authors: Etienne Kneuss <colder@php.net>                             |
14
   +----------------------------------------------------------------------+
15
 */
16
17
#ifdef HAVE_CONFIG_H
18
# include "config.h"
19
#endif
20
21
#include "php.h"
22
#include "zend_interfaces.h"
23
#include "zend_exceptions.h"
24
25
#include "spl_heap.h"
26
#include "spl_heap_arginfo.h"
27
#include "spl_exceptions.h"
28
#include "spl_functions.h" /* For spl_set_private_debug_info_property() */
29
30
386
#define PTR_HEAP_BLOCK_SIZE 64
31
32
0
#define SPL_HEAP_CORRUPTED       0x00000001
33
772
#define SPL_HEAP_WRITE_LOCKED    0x00000002
34
35
static zend_object_handlers spl_handler_SplHeap;
36
static zend_object_handlers spl_handler_SplPriorityQueue;
37
38
PHPAPI zend_class_entry  *spl_ce_SplHeap;
39
PHPAPI zend_class_entry  *spl_ce_SplMaxHeap;
40
PHPAPI zend_class_entry  *spl_ce_SplMinHeap;
41
PHPAPI zend_class_entry  *spl_ce_SplPriorityQueue;
42
43
44
typedef void (*spl_ptr_heap_dtor_func)(void *);
45
typedef void (*spl_ptr_heap_ctor_func)(void *);
46
typedef int  (*spl_ptr_heap_cmp_func)(void *, void *, zval *);
47
48
typedef struct _spl_ptr_heap {
49
  void                   *elements;
50
  spl_ptr_heap_ctor_func  ctor;
51
  spl_ptr_heap_dtor_func  dtor;
52
  spl_ptr_heap_cmp_func   cmp;
53
  int                     count;
54
  int                     flags;
55
  size_t                  max_size;
56
  size_t                  elem_size;
57
} spl_ptr_heap;
58
59
typedef struct _spl_heap_object spl_heap_object;
60
typedef struct _spl_heap_it spl_heap_it;
61
62
struct _spl_heap_object {
63
  spl_ptr_heap       *heap;
64
  int                 flags;
65
  zend_function      *fptr_cmp;
66
  zend_function      *fptr_count;
67
  zend_object         std;
68
};
69
70
typedef struct _spl_pqueue_elem {
71
  zval data;
72
  zval priority;
73
} spl_pqueue_elem;
74
75
1.04k
static inline spl_heap_object *spl_heap_from_obj(zend_object *obj) /* {{{ */ {
76
1.04k
  return (spl_heap_object*)((char*)(obj) - XtOffsetOf(spl_heap_object, std));
77
1.04k
}
78
/* }}} */
79
80
0
#define Z_SPLHEAP_P(zv)  spl_heap_from_obj(Z_OBJ_P((zv)))
81
82
0
static zend_always_inline void *spl_heap_elem(spl_ptr_heap *heap, size_t i) {
83
0
  return (void *) ((char *) heap->elements + heap->elem_size * i);
84
0
}
85
86
0
static zend_always_inline void spl_heap_elem_copy(spl_ptr_heap *heap, void *to, void *from) {
87
0
  assert(to != from);
88
89
  /* Specialized for cases of heap and priority queue. With the size being
90
   * constant known at compile time the compiler can fully inline calls to memcpy. */
91
0
  if (heap->elem_size == sizeof(spl_pqueue_elem)) {
92
0
    memcpy(to, from, sizeof(spl_pqueue_elem));
93
0
  } else {
94
0
    ZEND_ASSERT(heap->elem_size == sizeof(zval));
95
0
    memcpy(to, from, sizeof(zval));
96
0
  }
97
0
}
98
99
0
static void spl_ptr_heap_zval_dtor(void *elem) { /* {{{ */
100
0
  zval_ptr_dtor((zval *) elem);
101
0
}
102
/* }}} */
103
104
0
static void spl_ptr_heap_zval_ctor(void *elem) { /* {{{ */
105
0
  Z_TRY_ADDREF_P((zval *) elem);
106
0
}
107
/* }}} */
108
109
0
static void spl_ptr_heap_pqueue_elem_dtor(void *elem) { /* {{{ */
110
0
  spl_pqueue_elem *pq_elem = elem;
111
0
  zval_ptr_dtor(&pq_elem->data);
112
0
  zval_ptr_dtor(&pq_elem->priority);
113
0
}
114
/* }}} */
115
116
0
static void spl_ptr_heap_pqueue_elem_ctor(void *elem) { /* {{{ */
117
0
  spl_pqueue_elem *pq_elem = elem;
118
0
  Z_TRY_ADDREF_P(&pq_elem->data);
119
0
  Z_TRY_ADDREF_P(&pq_elem->priority);
120
0
}
121
/* }}} */
122
123
0
static zend_result spl_ptr_heap_cmp_cb_helper(zval *object, spl_heap_object *heap_object, zval *a, zval *b, zend_long *result) { /* {{{ */
124
0
  zval zresult;
125
126
0
  zend_call_method_with_2_params(Z_OBJ_P(object), heap_object->std.ce, &heap_object->fptr_cmp, "compare", &zresult, a, b);
127
128
0
  if (EG(exception)) {
129
0
    return FAILURE;
130
0
  }
131
132
0
  *result = zval_get_long(&zresult);
133
0
  zval_ptr_dtor(&zresult);
134
135
0
  return SUCCESS;
136
0
}
137
/* }}} */
138
139
static void spl_pqueue_extract_helper(zval *result, spl_pqueue_elem *elem, int flags) /* {{{ */
140
0
{
141
0
  if ((flags & SPL_PQUEUE_EXTR_BOTH) == SPL_PQUEUE_EXTR_BOTH) {
142
0
    array_init(result);
143
0
    Z_TRY_ADDREF(elem->data);
144
0
    add_assoc_zval_ex(result, "data", sizeof("data") - 1, &elem->data);
145
0
    Z_TRY_ADDREF(elem->priority);
146
0
    add_assoc_zval_ex(result, "priority", sizeof("priority") - 1, &elem->priority);
147
0
    return;
148
0
  }
149
150
0
  if (flags & SPL_PQUEUE_EXTR_DATA) {
151
0
    ZVAL_COPY(result, &elem->data);
152
0
    return;
153
0
  }
154
155
0
  if (flags & SPL_PQUEUE_EXTR_PRIORITY) {
156
0
    ZVAL_COPY(result, &elem->priority);
157
0
    return;
158
0
  }
159
160
0
  ZEND_UNREACHABLE();
161
0
}
162
/* }}} */
163
164
0
static int spl_ptr_heap_zval_max_cmp(void *x, void *y, zval *object) { /* {{{ */
165
0
  zval *a = x, *b = y;
166
167
0
  if (EG(exception)) {
168
0
    return 0;
169
0
  }
170
171
0
  if (object) {
172
0
    spl_heap_object *heap_object = Z_SPLHEAP_P(object);
173
0
    if (heap_object->fptr_cmp) {
174
0
      zend_long lval = 0;
175
0
      if (spl_ptr_heap_cmp_cb_helper(object, heap_object, a, b, &lval) == FAILURE) {
176
        /* exception or call failure */
177
0
        return 0;
178
0
      }
179
0
      return ZEND_NORMALIZE_BOOL(lval);
180
0
    }
181
0
  }
182
183
0
  return zend_compare(a, b);
184
0
}
185
/* }}} */
186
187
0
static int spl_ptr_heap_zval_min_cmp(void *x, void *y, zval *object) { /* {{{ */
188
0
  zval *a = x, *b = y;
189
190
0
  if (EG(exception)) {
191
0
    return 0;
192
0
  }
193
194
0
  if (object) {
195
0
    spl_heap_object *heap_object = Z_SPLHEAP_P(object);
196
0
    if (heap_object->fptr_cmp) {
197
0
      zend_long lval = 0;
198
0
      if (spl_ptr_heap_cmp_cb_helper(object, heap_object, a, b, &lval) == FAILURE) {
199
        /* exception or call failure */
200
0
        return 0;
201
0
      }
202
0
      return ZEND_NORMALIZE_BOOL(lval);
203
0
    }
204
0
  }
205
206
0
  return zend_compare(b, a);
207
0
}
208
/* }}} */
209
210
0
static int spl_ptr_pqueue_elem_cmp(void *x, void *y, zval *object) { /* {{{ */
211
0
  spl_pqueue_elem *a = x;
212
0
  spl_pqueue_elem *b = y;
213
0
  zval *a_priority_p = &a->priority;
214
0
  zval *b_priority_p = &b->priority;
215
216
0
  if (EG(exception)) {
217
0
    return 0;
218
0
  }
219
220
0
  if (object) {
221
0
    spl_heap_object *heap_object = Z_SPLHEAP_P(object);
222
0
    if (heap_object->fptr_cmp) {
223
0
      zend_long lval = 0;
224
0
      if (spl_ptr_heap_cmp_cb_helper(object, heap_object, a_priority_p, b_priority_p, &lval) == FAILURE) {
225
        /* exception or call failure */
226
0
        return 0;
227
0
      }
228
0
      return ZEND_NORMALIZE_BOOL(lval);
229
0
    }
230
0
  }
231
232
0
  return zend_compare(a_priority_p, b_priority_p);
233
0
}
234
/* }}} */
235
236
/* Specialized comparator used when we are absolutely sure an instance of the
237
 * not inherited SplPriorityQueue class contains only priorities as longs. This
238
 * fact is tracked during insertion into the queue. */
239
0
static int spl_ptr_pqueue_elem_cmp_long(void *x, void *y, zval *object) {
240
0
  zend_long a = Z_LVAL(((spl_pqueue_elem*) x)->priority);
241
0
  zend_long b = Z_LVAL(((spl_pqueue_elem*) y)->priority);
242
0
  return a>b ? 1 : (a<b ? -1 : 0);
243
0
}
244
245
/* same as spl_ptr_pqueue_elem_cmp_long */
246
0
static int spl_ptr_pqueue_elem_cmp_double(void *x, void *y, zval *object) {
247
0
  double a = Z_DVAL(((spl_pqueue_elem*) x)->priority);
248
0
  double b = Z_DVAL(((spl_pqueue_elem*) y)->priority);
249
0
  return ZEND_THREEWAY_COMPARE(a, b);
250
0
}
251
252
static spl_ptr_heap *spl_ptr_heap_init(spl_ptr_heap_cmp_func cmp, spl_ptr_heap_ctor_func ctor, spl_ptr_heap_dtor_func dtor, size_t elem_size) /* {{{ */
253
386
{
254
386
  spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
255
256
386
  heap->dtor     = dtor;
257
386
  heap->ctor     = ctor;
258
386
  heap->cmp      = cmp;
259
386
  heap->elements = ecalloc(PTR_HEAP_BLOCK_SIZE, elem_size);
260
386
  heap->max_size = PTR_HEAP_BLOCK_SIZE;
261
386
  heap->count    = 0;
262
386
  heap->flags    = 0;
263
386
  heap->elem_size = elem_size;
264
265
386
  return heap;
266
386
}
267
/* }}} */
268
269
0
static void spl_ptr_heap_insert(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */
270
0
  int i;
271
272
0
  if (heap->count+1 > heap->max_size) {
273
0
    size_t alloc_size = heap->max_size * heap->elem_size;
274
    /* we need to allocate more memory */
275
0
    heap->elements  = safe_erealloc(heap->elements, 2, alloc_size, 0);
276
0
    memset((char *) heap->elements + alloc_size, 0, alloc_size);
277
0
    heap->max_size *= 2;
278
0
  }
279
280
0
  heap->flags |= SPL_HEAP_WRITE_LOCKED;
281
282
  /* sifting up */
283
0
  for (i = heap->count; i > 0 && heap->cmp(spl_heap_elem(heap, (i-1)/2), elem, cmp_userdata) < 0; i = (i-1)/2) {
284
0
    spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, (i-1)/2));
285
0
  }
286
0
  heap->count++;
287
288
0
  heap->flags &= ~SPL_HEAP_WRITE_LOCKED;
289
290
0
  if (EG(exception)) {
291
    /* exception thrown during comparison */
292
0
    heap->flags |= SPL_HEAP_CORRUPTED;
293
0
  }
294
295
0
  spl_heap_elem_copy(heap, spl_heap_elem(heap, i), elem);
296
0
}
297
/* }}} */
298
299
0
static void *spl_ptr_heap_top(spl_ptr_heap *heap) { /* {{{ */
300
0
  if (heap->count == 0) {
301
0
    return NULL;
302
0
  }
303
304
0
  return heap->elements;
305
0
}
306
/* }}} */
307
308
0
static zend_result spl_ptr_heap_delete_top(spl_ptr_heap *heap, void *elem, void *cmp_userdata) { /* {{{ */
309
0
  int i, j;
310
0
  const int limit = (heap->count-1)/2;
311
0
  void *bottom;
312
313
0
  if (heap->count == 0) {
314
0
    return FAILURE;
315
0
  }
316
317
0
  heap->flags |= SPL_HEAP_WRITE_LOCKED;
318
319
0
  if (elem) {
320
0
    spl_heap_elem_copy(heap, elem, spl_heap_elem(heap, 0));
321
0
  } else {
322
0
    heap->dtor(spl_heap_elem(heap, 0));
323
0
  }
324
325
0
  bottom = spl_heap_elem(heap, --heap->count);
326
327
0
  for (i = 0; i < limit; i = j) {
328
    /* Find smaller child */
329
0
    j = i * 2 + 1;
330
0
    if (j != heap->count && heap->cmp(spl_heap_elem(heap, j+1), spl_heap_elem(heap, j), cmp_userdata) > 0) {
331
0
      j++; /* next child is bigger */
332
0
    }
333
334
    /* swap elements between two levels */
335
0
    if(heap->cmp(bottom, spl_heap_elem(heap, j), cmp_userdata) < 0) {
336
0
      spl_heap_elem_copy(heap, spl_heap_elem(heap, i), spl_heap_elem(heap, j));
337
0
    } else {
338
0
      break;
339
0
    }
340
0
  }
341
342
0
  heap->flags &= ~SPL_HEAP_WRITE_LOCKED;
343
344
0
  if (EG(exception)) {
345
    /* exception thrown during comparison */
346
0
    heap->flags |= SPL_HEAP_CORRUPTED;
347
0
  }
348
349
0
  void *to = spl_heap_elem(heap, i);
350
0
  if (to != bottom) {
351
0
    spl_heap_elem_copy(heap, to, bottom);
352
0
  }
353
0
  return SUCCESS;
354
0
}
355
/* }}} */
356
357
0
static spl_ptr_heap *spl_ptr_heap_clone(spl_ptr_heap *from) { /* {{{ */
358
0
  int i;
359
360
0
  spl_ptr_heap *heap = emalloc(sizeof(spl_ptr_heap));
361
362
0
  heap->dtor     = from->dtor;
363
0
  heap->ctor     = from->ctor;
364
0
  heap->cmp      = from->cmp;
365
0
  heap->max_size = from->max_size;
366
0
  heap->count    = from->count;
367
0
  heap->flags    = from->flags;
368
0
  heap->elem_size = from->elem_size;
369
370
0
  heap->elements = safe_emalloc(from->elem_size, from->max_size, 0);
371
0
  memcpy(heap->elements, from->elements, from->elem_size * from->max_size);
372
373
0
  for (i = 0; i < heap->count; ++i) {
374
0
    heap->ctor(spl_heap_elem(heap, i));
375
0
  }
376
377
0
  return heap;
378
0
}
379
/* }}} */
380
381
386
static void spl_ptr_heap_destroy(spl_ptr_heap *heap) { /* {{{ */
382
  /* Heap might be null if we OOMed during object initialization. */
383
386
  if (!heap) {
384
0
    return;
385
0
  }
386
387
386
  int i;
388
389
386
  heap->flags |= SPL_HEAP_WRITE_LOCKED;
390
391
386
  for (i = 0; i < heap->count; ++i) {
392
0
    heap->dtor(spl_heap_elem(heap, i));
393
0
  }
394
395
386
  heap->flags &= ~SPL_HEAP_WRITE_LOCKED;
396
397
386
  efree(heap->elements);
398
386
  efree(heap);
399
386
}
400
/* }}} */
401
402
0
static int spl_ptr_heap_count(spl_ptr_heap *heap) { /* {{{ */
403
0
  return heap->count;
404
0
}
405
/* }}} */
406
407
static void spl_heap_object_free_storage(zend_object *object) /* {{{ */
408
386
{
409
386
  spl_heap_object *intern = spl_heap_from_obj(object);
410
411
386
  zend_object_std_dtor(&intern->std);
412
413
386
  spl_ptr_heap_destroy(intern->heap);
414
386
}
415
/* }}} */
416
417
static zend_object *spl_heap_object_new_ex(zend_class_entry *class_type, zend_object *orig, int clone_orig) /* {{{ */
418
386
{
419
386
  spl_heap_object   *intern;
420
386
  zend_class_entry  *parent = class_type;
421
386
  int                inherited = 0;
422
423
386
  intern = zend_object_alloc(sizeof(spl_heap_object), parent);
424
425
386
  zend_object_std_init(&intern->std, class_type);
426
386
  object_properties_init(&intern->std, class_type);
427
428
386
  if (orig) {
429
0
    spl_heap_object *other = spl_heap_from_obj(orig);
430
0
    intern->std.handlers = other->std.handlers;
431
432
0
    if (clone_orig) {
433
0
      intern->heap = spl_ptr_heap_clone(other->heap);
434
0
    } else {
435
0
      intern->heap = other->heap;
436
0
    }
437
438
0
    intern->flags = other->flags;
439
0
    intern->fptr_cmp = other->fptr_cmp;
440
0
    intern->fptr_count = other->fptr_count;
441
0
    return &intern->std;
442
0
  }
443
444
386
  while (parent) {
445
386
    if (parent == spl_ce_SplPriorityQueue) {
446
147
      intern->heap = spl_ptr_heap_init(spl_ptr_pqueue_elem_cmp, spl_ptr_heap_pqueue_elem_ctor, spl_ptr_heap_pqueue_elem_dtor, sizeof(spl_pqueue_elem));
447
147
      intern->flags = SPL_PQUEUE_EXTR_DATA;
448
147
      break;
449
147
    }
450
451
239
    if (parent == spl_ce_SplMinHeap || parent == spl_ce_SplMaxHeap
452
239
        || parent == spl_ce_SplHeap) {
453
239
      intern->heap = spl_ptr_heap_init(
454
239
        parent == spl_ce_SplMinHeap ? spl_ptr_heap_zval_min_cmp : spl_ptr_heap_zval_max_cmp,
455
239
        spl_ptr_heap_zval_ctor, spl_ptr_heap_zval_dtor, sizeof(zval));
456
239
      break;
457
239
    }
458
459
0
    parent = parent->parent;
460
0
    inherited = 1;
461
0
  }
462
463
386
  ZEND_ASSERT(parent);
464
465
386
  if (inherited) {
466
0
    intern->fptr_cmp = zend_hash_str_find_ptr(&class_type->function_table, "compare", sizeof("compare") - 1);
467
0
    if (intern->fptr_cmp->common.scope == parent) {
468
0
      intern->fptr_cmp = NULL;
469
0
    }
470
    /* Find count() method */
471
0
    intern->fptr_count = zend_hash_find_ptr(&class_type->function_table, ZSTR_KNOWN(ZEND_STR_COUNT));
472
0
    if (intern->fptr_count->common.scope == parent) {
473
0
      intern->fptr_count = NULL;
474
0
    }
475
0
  }
476
477
386
  return &intern->std;
478
386
}
479
/* }}} */
480
481
static zend_object *spl_heap_object_new(zend_class_entry *class_type) /* {{{ */
482
386
{
483
386
  return spl_heap_object_new_ex(class_type, NULL, 0);
484
386
}
485
/* }}} */
486
487
static zend_object *spl_heap_object_clone(zend_object *old_object) /* {{{ */
488
0
{
489
0
  zend_object *new_object = spl_heap_object_new_ex(old_object->ce, old_object, 1);
490
491
0
  zend_objects_clone_members(new_object, old_object);
492
493
0
  return new_object;
494
0
}
495
/* }}} */
496
497
static zend_result spl_heap_object_count_elements(zend_object *object, zend_long *count) /* {{{ */
498
0
{
499
0
  spl_heap_object *intern = spl_heap_from_obj(object);
500
501
0
  if (intern->fptr_count) {
502
0
    zval rv;
503
0
    zend_call_method_with_0_params(object, intern->std.ce, &intern->fptr_count, "count", &rv);
504
0
    if (!Z_ISUNDEF(rv)) {
505
0
      *count = zval_get_long(&rv);
506
0
      zval_ptr_dtor(&rv);
507
0
      return SUCCESS;
508
0
    }
509
0
    *count = 0;
510
0
    return FAILURE;
511
0
  }
512
513
0
  *count = spl_ptr_heap_count(intern->heap);
514
515
0
  return SUCCESS;
516
0
}
517
/* }}} */
518
519
0
static HashTable* spl_heap_object_get_debug_info(const zend_class_entry *ce, zend_object *obj) { /* {{{ */
520
0
  spl_heap_object *intern = spl_heap_from_obj(obj);
521
0
  zval tmp, heap_array;
522
0
  HashTable *debug_info;
523
0
  HashTable *properties = zend_std_get_properties_ex(&intern->std);
524
525
  /* +3 As we are adding 3 additional key-entries */
526
0
  debug_info = zend_new_array(zend_hash_num_elements(properties) + 3);
527
0
  zend_hash_copy(debug_info, properties, (copy_ctor_func_t) zval_add_ref);
528
529
0
  ZVAL_LONG(&tmp, intern->flags);
530
0
  spl_set_private_debug_info_property(ce, "flags", strlen("flags"), debug_info, &tmp);
531
532
0
  ZVAL_BOOL(&tmp, intern->heap->flags&SPL_HEAP_CORRUPTED);
533
0
  spl_set_private_debug_info_property(ce, "isCorrupted", strlen("isCorrupted"), debug_info, &tmp);
534
535
0
  array_init(&heap_array);
536
537
0
  for (zend_ulong i = 0; i < intern->heap->count; ++i) {
538
0
    if (ce == spl_ce_SplPriorityQueue) {
539
0
      spl_pqueue_elem *pq_elem = spl_heap_elem(intern->heap, i);
540
0
      zval elem;
541
0
      spl_pqueue_extract_helper(&elem, pq_elem, SPL_PQUEUE_EXTR_BOTH);
542
0
      add_index_zval(&heap_array, i, &elem);
543
0
    } else {
544
0
      zval *elem = spl_heap_elem(intern->heap, i);
545
0
      add_index_zval(&heap_array, i, elem);
546
0
      Z_TRY_ADDREF_P(elem);
547
0
    }
548
0
  }
549
550
0
  spl_set_private_debug_info_property(ce, "heap", strlen("heap"), debug_info, &heap_array);
551
552
0
  return debug_info;
553
0
}
554
/* }}} */
555
556
static HashTable *spl_heap_object_get_gc(zend_object *obj, zval **gc_data, int *gc_data_count) /* {{{ */
557
591
{
558
591
  spl_heap_object *intern = spl_heap_from_obj(obj);
559
591
  *gc_data = (zval *) intern->heap->elements;
560
591
  *gc_data_count = intern->heap->count;
561
562
591
  return zend_std_get_properties(obj);
563
591
}
564
/* }}} */
565
566
static HashTable *spl_pqueue_object_get_gc(zend_object *obj, zval **gc_data, int *gc_data_count) /* {{{ */
567
69
{
568
69
  spl_heap_object *intern = spl_heap_from_obj(obj);
569
69
  *gc_data = (zval *) intern->heap->elements;
570
  /* Two zvals (value and priority) per pqueue entry */
571
69
  *gc_data_count = 2 * intern->heap->count;
572
573
69
  return zend_std_get_properties(obj);
574
69
}
575
/* }}} */
576
577
/* {{{ Return the number of elements in the heap. */
578
PHP_METHOD(SplHeap, count)
579
0
{
580
0
  zend_long count;
581
0
  spl_heap_object *intern = Z_SPLHEAP_P(ZEND_THIS);
582
583
0
  if (zend_parse_parameters_none() == FAILURE) {
584
0
    RETURN_THROWS();
585
0
  }
586
587
0
  count = spl_ptr_heap_count(intern->heap);
588
0
  RETURN_LONG(count);
589
0
}
590
/* }}} */
591
592
/* {{{ Return true if the heap is empty. */
593
PHP_METHOD(SplHeap, isEmpty)
594
0
{
595
0
  spl_heap_object *intern = Z_SPLHEAP_P(ZEND_THIS);
596
597
0
  if (zend_parse_parameters_none() == FAILURE) {
598
0
    RETURN_THROWS();
599
0
  }
600
601
0
  RETURN_BOOL(spl_ptr_heap_count(intern->heap) == 0);
602
0
}
603
/* }}} */
604
605
static zend_result spl_heap_consistency_validations(const spl_heap_object *intern, bool write)
606
0
{
607
0
  if (intern->heap->flags & SPL_HEAP_CORRUPTED) {
608
0
    zend_throw_exception(spl_ce_RuntimeException, "Heap is corrupted, heap properties are no longer ensured.", 0);
609
0
    return FAILURE;
610
0
  }
611
612
0
  if (write && (intern->heap->flags & SPL_HEAP_WRITE_LOCKED)) {
613
0
    zend_throw_exception(spl_ce_RuntimeException, "Heap cannot be changed when it is already being modified.", 0);
614
0
    return FAILURE;
615
0
  }
616
617
0
  return SUCCESS;
618
0
}
619
620
/* {{{ Push $value on the heap */
621
PHP_METHOD(SplHeap, insert)
622
0
{
623
0
  zval *value;
624
0
  spl_heap_object *intern;
625
626
0
  ZEND_PARSE_PARAMETERS_START(1, 1)
627
0
    Z_PARAM_ZVAL(value);
628
0
  ZEND_PARSE_PARAMETERS_END();
629
630
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
631
632
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, true) != SUCCESS)) {
633
0
    RETURN_THROWS();
634
0
  }
635
636
0
  Z_TRY_ADDREF_P(value);
637
0
  spl_ptr_heap_insert(intern->heap, value, ZEND_THIS);
638
639
0
  RETURN_TRUE;
640
0
}
641
/* }}} */
642
643
/* {{{ extract the element out of the top of the heap */
644
PHP_METHOD(SplHeap, extract)
645
0
{
646
0
  spl_heap_object *intern;
647
648
0
  if (zend_parse_parameters_none() == FAILURE) {
649
0
    RETURN_THROWS();
650
0
  }
651
652
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
653
654
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, true) != SUCCESS)) {
655
0
    RETURN_THROWS();
656
0
  }
657
658
0
  if (spl_ptr_heap_delete_top(intern->heap, return_value, ZEND_THIS) == FAILURE) {
659
0
    zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0);
660
0
    RETURN_THROWS();
661
0
  }
662
0
}
663
/* }}} */
664
665
/* {{{ Push $value with the priority $priodiry on the priorityqueue */
666
PHP_METHOD(SplPriorityQueue, insert)
667
0
{
668
0
  zval *data, *priority;
669
0
  spl_heap_object *intern;
670
0
  spl_pqueue_elem elem;
671
672
0
  ZEND_PARSE_PARAMETERS_START(2, 2)
673
0
    Z_PARAM_ZVAL(data);
674
0
    Z_PARAM_ZVAL(priority);
675
0
  ZEND_PARSE_PARAMETERS_END();
676
677
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
678
679
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, true) != SUCCESS)) {
680
0
    RETURN_THROWS();
681
0
  }
682
683
0
  ZVAL_COPY(&elem.data, data);
684
0
  ZVAL_COPY(&elem.priority, priority);
685
686
  /* If we know this call came from non inherited SplPriorityQueue it's
687
   * possible to do specialization on the type of the priority parameter. */
688
0
  if (!intern->fptr_cmp) {
689
0
    int type = Z_TYPE(elem.priority);
690
0
    spl_ptr_heap_cmp_func new_cmp =
691
0
      (type == IS_LONG) ? spl_ptr_pqueue_elem_cmp_long :
692
0
      ((type == IS_DOUBLE) ? spl_ptr_pqueue_elem_cmp_double : spl_ptr_pqueue_elem_cmp);
693
694
0
    if (intern->heap->count == 0) { /* Specialize empty queue */
695
0
      intern->heap->cmp = new_cmp;
696
0
    } else if (new_cmp != intern->heap->cmp) { /* Despecialize on type conflict. */
697
0
      intern->heap->cmp = spl_ptr_pqueue_elem_cmp;
698
0
    }
699
0
  }
700
701
0
  spl_ptr_heap_insert(intern->heap, &elem, ZEND_THIS);
702
703
0
  RETURN_TRUE;
704
0
}
705
/* }}} */
706
707
/* {{{ extract the element out of the top of the priority queue */
708
PHP_METHOD(SplPriorityQueue, extract)
709
0
{
710
0
  spl_pqueue_elem elem;
711
0
  spl_heap_object *intern;
712
713
0
  if (zend_parse_parameters_none() == FAILURE) {
714
0
    RETURN_THROWS();
715
0
  }
716
717
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
718
719
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, true) != SUCCESS)) {
720
0
    RETURN_THROWS();
721
0
  }
722
723
0
  if (spl_ptr_heap_delete_top(intern->heap, &elem, ZEND_THIS) == FAILURE) {
724
0
    zend_throw_exception(spl_ce_RuntimeException, "Can't extract from an empty heap", 0);
725
0
    RETURN_THROWS();
726
0
  }
727
728
0
  spl_pqueue_extract_helper(return_value, &elem, intern->flags);
729
0
  spl_ptr_heap_pqueue_elem_dtor(&elem);
730
0
}
731
/* }}} */
732
733
/* {{{ Peek at the top element of the priority queue */
734
PHP_METHOD(SplPriorityQueue, top)
735
0
{
736
0
  spl_heap_object *intern;
737
0
  spl_pqueue_elem *elem;
738
739
0
  if (zend_parse_parameters_none() == FAILURE) {
740
0
    RETURN_THROWS();
741
0
  }
742
743
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
744
745
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, false) != SUCCESS)) {
746
0
    RETURN_THROWS();
747
0
  }
748
749
0
  elem = spl_ptr_heap_top(intern->heap);
750
751
0
  if (!elem) {
752
0
    zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0);
753
0
    RETURN_THROWS();
754
0
  }
755
756
0
  spl_pqueue_extract_helper(return_value, elem, intern->flags);
757
0
}
758
/* }}} */
759
760
761
/* {{{ Set the flags of extraction*/
762
PHP_METHOD(SplPriorityQueue, setExtractFlags)
763
0
{
764
0
  zend_long value;
765
0
  spl_heap_object *intern;
766
767
0
  if (zend_parse_parameters(ZEND_NUM_ARGS(), "l", &value) == FAILURE) {
768
0
    RETURN_THROWS();
769
0
  }
770
771
0
  value &= SPL_PQUEUE_EXTR_MASK;
772
0
  if (!value) {
773
0
    zend_throw_exception(spl_ce_RuntimeException, "Must specify at least one extract flag", 0);
774
0
    RETURN_THROWS();
775
0
  }
776
777
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
778
0
  intern->flags = value;
779
0
  RETURN_LONG(intern->flags);
780
0
}
781
/* }}} */
782
783
/* {{{ Get the flags of extraction*/
784
PHP_METHOD(SplPriorityQueue, getExtractFlags)
785
0
{
786
0
  spl_heap_object *intern;
787
788
0
  if (zend_parse_parameters_none() == FAILURE) {
789
0
    RETURN_THROWS();
790
0
  }
791
792
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
793
794
0
  RETURN_LONG(intern->flags);
795
0
}
796
/* }}} */
797
798
/* {{{ Recover from a corrupted state*/
799
PHP_METHOD(SplHeap, recoverFromCorruption)
800
0
{
801
0
  spl_heap_object *intern;
802
803
0
  if (zend_parse_parameters_none() == FAILURE) {
804
0
    RETURN_THROWS();
805
0
  }
806
807
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
808
809
0
  intern->heap->flags = intern->heap->flags & ~SPL_HEAP_CORRUPTED;
810
811
0
  RETURN_TRUE;
812
0
}
813
/* }}} */
814
815
/* {{{ Tells if the heap is in a corrupted state*/
816
PHP_METHOD(SplHeap, isCorrupted)
817
0
{
818
0
  spl_heap_object *intern;
819
820
0
  if (zend_parse_parameters_none() == FAILURE) {
821
0
    RETURN_THROWS();
822
0
  }
823
824
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
825
826
0
  RETURN_BOOL(intern->heap->flags & SPL_HEAP_CORRUPTED);
827
0
}
828
/* }}} */
829
830
/* {{{ compare the priorities */
831
PHP_METHOD(SplPriorityQueue, compare)
832
0
{
833
0
  zval *a, *b;
834
835
0
  if (zend_parse_parameters(ZEND_NUM_ARGS(), "zz", &a, &b) == FAILURE) {
836
0
    RETURN_THROWS();
837
0
  }
838
839
0
  RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL));
840
0
}
841
/* }}} */
842
843
/* {{{ Peek at the top element of the heap */
844
PHP_METHOD(SplHeap, top)
845
0
{
846
0
  zval *value;
847
0
  spl_heap_object *intern;
848
849
0
  if (zend_parse_parameters_none() == FAILURE) {
850
0
    RETURN_THROWS();
851
0
  }
852
853
0
  intern = Z_SPLHEAP_P(ZEND_THIS);
854
855
0
  if (UNEXPECTED(spl_heap_consistency_validations(intern, false) != SUCCESS)) {
856
0
    RETURN_THROWS();
857
0
  }
858
859
0
  value = spl_ptr_heap_top(intern->heap);
860
861
0
  if (!value) {
862
0
    zend_throw_exception(spl_ce_RuntimeException, "Can't peek at an empty heap", 0);
863
0
    RETURN_THROWS();
864
0
  }
865
866
0
  RETURN_COPY_DEREF(value);
867
0
}
868
/* }}} */
869
870
/* {{{ compare the values */
871
PHP_METHOD(SplMinHeap, compare)
872
0
{
873
0
  zval *a, *b;
874
875
0
  if (zend_parse_parameters(ZEND_NUM_ARGS(), "zz", &a, &b) == FAILURE) {
876
0
    RETURN_THROWS();
877
0
  }
878
879
0
  RETURN_LONG(spl_ptr_heap_zval_min_cmp(a, b, NULL));
880
0
}
881
/* }}} */
882
883
/* {{{ compare the values */
884
PHP_METHOD(SplMaxHeap, compare)
885
0
{
886
0
  zval *a, *b;
887
888
0
  if (zend_parse_parameters(ZEND_NUM_ARGS(), "zz", &a, &b) == FAILURE) {
889
0
    RETURN_THROWS();
890
0
  }
891
892
0
  RETURN_LONG(spl_ptr_heap_zval_max_cmp(a, b, NULL));
893
0
}
894
/* }}} */
895
896
static void spl_heap_it_dtor(zend_object_iterator *iter) /* {{{ */
897
0
{
898
0
  zend_user_it_invalidate_current(iter);
899
0
  zval_ptr_dtor(&iter->data);
900
0
}
901
/* }}} */
902
903
static void spl_heap_it_rewind(zend_object_iterator *iter) /* {{{ */
904
0
{
905
  /* do nothing, the iterator always points to the top element */
906
0
}
907
/* }}} */
908
909
static zend_result spl_heap_it_valid(zend_object_iterator *iter) /* {{{ */
910
0
{
911
0
  return ((Z_SPLHEAP_P(&iter->data))->heap->count != 0 ? SUCCESS : FAILURE);
912
0
}
913
/* }}} */
914
915
static zval *spl_heap_it_get_current_data(zend_object_iterator *iter) /* {{{ */
916
0
{
917
0
  spl_heap_object *object = Z_SPLHEAP_P(&iter->data);
918
919
0
  if (UNEXPECTED(spl_heap_consistency_validations(object, false) != SUCCESS)) {
920
0
    return NULL;
921
0
  }
922
923
0
  if (object->heap->count == 0) {
924
0
    return NULL;
925
0
  } else {
926
0
    return spl_heap_elem(object->heap, 0);
927
0
  }
928
0
}
929
/* }}} */
930
931
static zval *spl_pqueue_it_get_current_data(zend_object_iterator *iter) /* {{{ */
932
0
{
933
0
  zend_user_iterator *user_it = (zend_user_iterator *) iter;
934
0
  spl_heap_object *object = Z_SPLHEAP_P(&iter->data);
935
936
0
  if (UNEXPECTED(spl_heap_consistency_validations(object, false) != SUCCESS)) {
937
0
    return NULL;
938
0
  }
939
940
0
  if (object->heap->count == 0) {
941
0
    return NULL;
942
0
  }
943
944
0
  if (Z_ISUNDEF(user_it->value)) {
945
0
    spl_pqueue_elem *elem = spl_heap_elem(object->heap, 0);
946
0
    spl_pqueue_extract_helper(&user_it->value, elem, object->flags);
947
0
  }
948
0
  return &user_it->value;
949
0
}
950
/* }}} */
951
952
static void spl_heap_it_get_current_key(zend_object_iterator *iter, zval *key) /* {{{ */
953
0
{
954
0
  spl_heap_object *object = Z_SPLHEAP_P(&iter->data);
955
956
0
  ZVAL_LONG(key, object->heap->count - 1);
957
0
}
958
/* }}} */
959
960
static void spl_heap_it_move_forward(zend_object_iterator *iter) /* {{{ */
961
0
{
962
0
  spl_heap_object *object = Z_SPLHEAP_P(&iter->data);
963
964
0
  if (UNEXPECTED(spl_heap_consistency_validations(object, false) != SUCCESS)) {
965
0
    return;
966
0
  }
967
968
0
  spl_ptr_heap_delete_top(object->heap, NULL, &iter->data);
969
0
  zend_user_it_invalidate_current(iter);
970
0
}
971
/* }}} */
972
973
/* {{{ Return current array key */
974
PHP_METHOD(SplHeap, key)
975
0
{
976
0
  spl_heap_object *intern = Z_SPLHEAP_P(ZEND_THIS);
977
978
0
  if (zend_parse_parameters_none() == FAILURE) {
979
0
    RETURN_THROWS();
980
0
  }
981
982
0
  RETURN_LONG(intern->heap->count - 1);
983
0
}
984
/* }}} */
985
986
/* {{{ Move to next entry */
987
PHP_METHOD(SplHeap, next)
988
0
{
989
0
  spl_heap_object *intern = Z_SPLHEAP_P(ZEND_THIS);
990
991
0
  if (zend_parse_parameters_none() == FAILURE) {
992
0
    RETURN_THROWS();
993
0
  }
994
995
0
  spl_ptr_heap_delete_top(intern->heap, NULL, ZEND_THIS);
996
0
}
997
/* }}} */
998
999
/* {{{ Check whether the datastructure contains more entries */
1000
PHP_METHOD(SplHeap, valid)
1001
0
{
1002
0
  spl_heap_object *intern = Z_SPLHEAP_P(ZEND_THIS);
1003
1004
0
  if (zend_parse_parameters_none() == FAILURE) {
1005
0
    RETURN_THROWS();
1006
0
  }
1007
1008
0
  RETURN_BOOL(intern->heap->count != 0);
1009
0
}
1010
/* }}} */
1011
1012
/* {{{ Rewind the datastructure back to the start */
1013
PHP_METHOD(SplHeap, rewind)
1014
0
{
1015
0
  if (zend_parse_parameters_none() == FAILURE) {
1016
0
    RETURN_THROWS();
1017
0
  }
1018
  /* do nothing, the iterator always points to the top element */
1019
0
}
1020
/* }}} */
1021
1022
/* {{{ Return current datastructure entry */
1023
PHP_METHOD(SplHeap, current)
1024
0
{
1025
0
  spl_heap_object *intern  = Z_SPLHEAP_P(ZEND_THIS);
1026
1027
0
  if (zend_parse_parameters_none() == FAILURE) {
1028
0
    RETURN_THROWS();
1029
0
  }
1030
1031
0
  if (!intern->heap->count) {
1032
0
    RETURN_NULL();
1033
0
  } else {
1034
0
    zval *element = spl_heap_elem(intern->heap, 0);
1035
0
    RETURN_COPY_DEREF(element);
1036
0
  }
1037
0
}
1038
/* }}} */
1039
1040
/* {{{ Return current datastructure entry */
1041
PHP_METHOD(SplPriorityQueue, current)
1042
0
{
1043
0
  spl_heap_object  *intern  = Z_SPLHEAP_P(ZEND_THIS);
1044
1045
0
  if (zend_parse_parameters_none() == FAILURE) {
1046
0
    RETURN_THROWS();
1047
0
  }
1048
1049
0
  if (!intern->heap->count) {
1050
0
    RETURN_NULL();
1051
0
  } else {
1052
0
    spl_pqueue_elem *elem = spl_heap_elem(intern->heap, 0);
1053
0
    spl_pqueue_extract_helper(return_value, elem, intern->flags);
1054
0
  }
1055
0
}
1056
/* }}} */
1057
1058
/* {{{ */
1059
PHP_METHOD(SplHeap, __debugInfo)
1060
0
{
1061
0
  if (zend_parse_parameters_none() == FAILURE) {
1062
0
    RETURN_THROWS();
1063
0
  }
1064
1065
0
  RETURN_ARR(spl_heap_object_get_debug_info(spl_ce_SplHeap, Z_OBJ_P(ZEND_THIS)));
1066
0
} /* }}} */
1067
1068
/* {{{ */
1069
PHP_METHOD(SplPriorityQueue, __debugInfo)
1070
0
{
1071
0
  if (zend_parse_parameters_none() == FAILURE) {
1072
0
    RETURN_THROWS();
1073
0
  }
1074
1075
0
  RETURN_ARR(spl_heap_object_get_debug_info(spl_ce_SplPriorityQueue, Z_OBJ_P(ZEND_THIS)));
1076
0
} /* }}} */
1077
1078
/* iterator handler table */
1079
static const zend_object_iterator_funcs spl_heap_it_funcs = {
1080
  spl_heap_it_dtor,
1081
  spl_heap_it_valid,
1082
  spl_heap_it_get_current_data,
1083
  spl_heap_it_get_current_key,
1084
  spl_heap_it_move_forward,
1085
  spl_heap_it_rewind,
1086
  NULL,
1087
  NULL, /* get_gc */
1088
};
1089
1090
static const zend_object_iterator_funcs spl_pqueue_it_funcs = {
1091
  spl_heap_it_dtor,
1092
  spl_heap_it_valid,
1093
  spl_pqueue_it_get_current_data,
1094
  spl_heap_it_get_current_key,
1095
  spl_heap_it_move_forward,
1096
  spl_heap_it_rewind,
1097
  NULL,
1098
  NULL, /* get_gc */
1099
};
1100
1101
static zend_object_iterator *spl_heap_get_iterator(zend_class_entry *ce, zval *object, int by_ref) /* {{{ */
1102
0
{
1103
0
  if (by_ref) {
1104
0
    zend_throw_error(NULL, "An iterator cannot be used with foreach by reference");
1105
0
    return NULL;
1106
0
  }
1107
1108
0
  zend_user_iterator *iterator = emalloc(sizeof(zend_user_iterator));
1109
0
  zend_iterator_init(&iterator->it);
1110
1111
0
  ZVAL_OBJ_COPY(&iterator->it.data, Z_OBJ_P(object));
1112
0
  iterator->it.funcs = &spl_heap_it_funcs;
1113
0
  iterator->ce       = ce;
1114
0
  ZVAL_UNDEF(&iterator->value);
1115
1116
0
  return &iterator->it;
1117
0
}
1118
/* }}} */
1119
1120
static zend_object_iterator *spl_pqueue_get_iterator(zend_class_entry *ce, zval *object, int by_ref) /* {{{ */
1121
0
{
1122
0
  if (by_ref) {
1123
0
    zend_throw_error(NULL, "An iterator cannot be used with foreach by reference");
1124
0
    return NULL;
1125
0
  }
1126
1127
0
  zend_user_iterator *iterator = emalloc(sizeof(zend_user_iterator));
1128
0
  zend_iterator_init(&iterator->it);
1129
1130
0
  ZVAL_OBJ_COPY(&iterator->it.data, Z_OBJ_P(object));
1131
0
  iterator->it.funcs = &spl_pqueue_it_funcs;
1132
0
  iterator->ce       = ce;
1133
0
  ZVAL_UNDEF(&iterator->value);
1134
1135
0
  return &iterator->it;
1136
0
}
1137
/* }}} */
1138
1139
PHP_MINIT_FUNCTION(spl_heap) /* {{{ */
1140
16
{
1141
16
  spl_ce_SplHeap = register_class_SplHeap(zend_ce_iterator, zend_ce_countable);
1142
16
  spl_ce_SplHeap->create_object = spl_heap_object_new;
1143
16
  spl_ce_SplHeap->default_object_handlers = &spl_handler_SplHeap;
1144
16
  spl_ce_SplHeap->get_iterator = spl_heap_get_iterator;
1145
1146
16
  memcpy(&spl_handler_SplHeap, &std_object_handlers, sizeof(zend_object_handlers));
1147
1148
16
  spl_handler_SplHeap.offset         = XtOffsetOf(spl_heap_object, std);
1149
16
  spl_handler_SplHeap.clone_obj      = spl_heap_object_clone;
1150
16
  spl_handler_SplHeap.count_elements = spl_heap_object_count_elements;
1151
16
  spl_handler_SplHeap.get_gc         = spl_heap_object_get_gc;
1152
16
  spl_handler_SplHeap.free_obj = spl_heap_object_free_storage;
1153
1154
16
  spl_ce_SplMinHeap = register_class_SplMinHeap(spl_ce_SplHeap);
1155
16
  spl_ce_SplMinHeap->create_object = spl_heap_object_new;
1156
16
  spl_ce_SplMinHeap->get_iterator = spl_heap_get_iterator;
1157
1158
16
  spl_ce_SplMaxHeap = register_class_SplMaxHeap(spl_ce_SplHeap);
1159
16
  spl_ce_SplMaxHeap->create_object = spl_heap_object_new;
1160
16
  spl_ce_SplMaxHeap->get_iterator = spl_heap_get_iterator;
1161
1162
16
  spl_ce_SplPriorityQueue = register_class_SplPriorityQueue(zend_ce_iterator, zend_ce_countable);
1163
16
  spl_ce_SplPriorityQueue->create_object = spl_heap_object_new;
1164
16
  spl_ce_SplPriorityQueue->default_object_handlers = &spl_handler_SplPriorityQueue;
1165
16
  spl_ce_SplPriorityQueue->get_iterator = spl_pqueue_get_iterator;
1166
1167
16
  memcpy(&spl_handler_SplPriorityQueue, &std_object_handlers, sizeof(zend_object_handlers));
1168
1169
16
  spl_handler_SplPriorityQueue.offset         = XtOffsetOf(spl_heap_object, std);
1170
16
  spl_handler_SplPriorityQueue.clone_obj      = spl_heap_object_clone;
1171
16
  spl_handler_SplPriorityQueue.count_elements = spl_heap_object_count_elements;
1172
16
  spl_handler_SplPriorityQueue.get_gc         = spl_pqueue_object_get_gc;
1173
16
  spl_handler_SplPriorityQueue.free_obj = spl_heap_object_free_storage;
1174
1175
16
  return SUCCESS;
1176
16
}
1177
/* }}} */