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