1 #include "../common.h"
2
3 #include "../php/iterators/php_deque_iterator.h"
4 #include "../php/handlers/php_deque_handlers.h"
5 #include "../php/classes/php_deque_ce.h"
6
7 #include "ds_deque.h"
8
ds_deque_increment_head(ds_deque_t * deque)9 static inline void ds_deque_increment_head(ds_deque_t *deque)
10 {
11 deque->head = (deque->head + 1) & (deque->capacity - 1);
12 }
13
ds_deque_decrement_head(ds_deque_t * deque)14 static inline void ds_deque_decrement_head(ds_deque_t *deque)
15 {
16 deque->head = (deque->head - 1) & (deque->capacity - 1);
17 }
18
ds_deque_increment_tail(ds_deque_t * deque)19 static inline void ds_deque_increment_tail(ds_deque_t *deque)
20 {
21 deque->tail = (deque->tail + 1) & (deque->capacity - 1);
22 }
23
ds_deque_decrement_tail(ds_deque_t * deque)24 static inline void ds_deque_decrement_tail(ds_deque_t *deque)
25 {
26 deque->tail = (deque->tail - 1) & (deque->capacity - 1);
27 }
28
ds_deque_memmove(ds_deque_t * deque,zend_long dst,zend_long src,zend_long length)29 static inline void ds_deque_memmove(
30 ds_deque_t *deque,
31 zend_long dst,
32 zend_long src,
33 zend_long length
34 ) {
35 memmove(&deque->buffer[dst], &deque->buffer[src], length * sizeof(zval));
36 }
37
ds_deque_get_capacity_for_size(zend_long size)38 static inline zend_long ds_deque_get_capacity_for_size(zend_long size)
39 {
40 return (zend_long) ds_next_power_of_2((uint32_t) size, DS_DEQUE_MIN_CAPACITY);
41 }
42
ds_deque()43 ds_deque_t *ds_deque()
44 {
45 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t));
46
47 deque->buffer = ds_allocate_zval_buffer(DS_DEQUE_MIN_CAPACITY);
48 deque->capacity = DS_DEQUE_MIN_CAPACITY;
49 deque->head = 0;
50 deque->tail = 0;
51 deque->size = 0;
52
53 return deque;
54 }
55
ds_deque_preallocated(zend_long size)56 static ds_deque_t *ds_deque_preallocated(zend_long size)
57 {
58 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t));
59
60 deque->capacity = ds_deque_get_capacity_for_size(size);
61 deque->buffer = ds_allocate_zval_buffer(deque->capacity);
62 deque->head = 0;
63 deque->tail = 0;
64 deque->size = 0;
65
66 return deque;
67 }
68
ds_deque_from_buffer(zval * buffer,zend_long capacity,zend_long size)69 static ds_deque_t *ds_deque_from_buffer(zval *buffer, zend_long capacity, zend_long size)
70 {
71 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t));
72
73 deque->buffer = buffer;
74 deque->capacity = capacity;
75 deque->head = 0;
76 deque->tail = size;
77 deque->size = size;
78
79 return deque;
80 }
81
ds_deque_clone(ds_deque_t * deque)82 ds_deque_t *ds_deque_clone(ds_deque_t *deque)
83 {
84 zval *source;
85 zval *buffer = ds_allocate_zval_buffer(deque->capacity);
86 zval *target = buffer;
87
88 DS_DEQUE_FOREACH(deque, source) {
89 ZVAL_COPY(target, source);
90 target++;
91 }
92 DS_DEQUE_FOREACH_END();
93
94 return ds_deque_from_buffer(buffer, deque->capacity, deque->size);
95 }
96
97
ds_deque_valid_position(ds_deque_t * deque,zend_long index)98 static inline bool ds_deque_valid_position(ds_deque_t *deque, zend_long index)
99 {
100 if (index < 0 || index >= deque->size) {
101 INDEX_OUT_OF_RANGE(index, deque->size);
102 return false;
103 }
104
105 return true;
106 }
107
108 // Makes sure that the deque's head is at index 0.
ds_deque_reset_head(ds_deque_t * deque)109 void ds_deque_reset_head(ds_deque_t *deque)
110 {
111 if (deque->head == 0) {
112 return;
113 }
114
115 if (deque->head < deque->tail) {
116 ds_deque_memmove(deque, 0, deque->head, deque->size);
117
118 } else {
119 zend_long h = deque->head;
120 zend_long t = deque->tail;
121 zend_long r = deque->capacity - h; // Number of values on the right.
122
123 // Check if there's enough room to push the left partition forward and
124 // the wrapped values (right partition) to the front.
125 if (r < (h - t)) {
126 ds_deque_memmove(deque, r, 0, t);
127 ds_deque_memmove(deque, 0, h, r);
128
129 } else {
130 // We don't have enough temporary space to work with, so create
131 // a new buffer, copy to it, then replace the current buffer.
132 zval *buffer = ds_allocate_zval_buffer(deque->capacity);
133
134 memcpy(&buffer[0], &deque->buffer[h], r * sizeof(zval));
135 memcpy(&buffer[r], &deque->buffer[0], t * sizeof(zval));
136
137 FREE_AND_REPLACE(deque->buffer, buffer);
138 }
139 }
140
141 deque->head = 0;
142 deque->tail = deque->size;
143 }
144
ds_deque_reallocate(ds_deque_t * deque,zend_long capacity)145 static void ds_deque_reallocate(ds_deque_t *deque, zend_long capacity)
146 {
147 ds_deque_reset_head(deque);
148
149 deque->buffer = ds_reallocate_zval_buffer(deque->buffer, capacity, deque->capacity, deque->size);
150 deque->capacity = capacity;
151 deque->head = 0;
152 deque->tail = deque->size; // Could have been zero before if buffer was full.
153 }
154
ds_deque_double_capacity(ds_deque_t * deque)155 static inline void ds_deque_double_capacity(ds_deque_t *deque)
156 {
157 ds_deque_reallocate(deque, deque->capacity << 1);
158 }
159
ds_deque_allocate(ds_deque_t * deque,zend_long size)160 void ds_deque_allocate(ds_deque_t *deque, zend_long size)
161 {
162 zend_long capacity = ds_deque_get_capacity_for_size(size);
163
164 // if (capacity == deque->capacity) {
165 // ds_deque_reallocate(deque, capacity << 1);
166 // }
167
168 if (capacity > deque->capacity) {
169 ds_deque_reallocate(deque, capacity);
170 }
171 }
172
ds_deque_auto_truncate(ds_deque_t * deque)173 static inline void ds_deque_auto_truncate(ds_deque_t *deque)
174 {
175 // Automatically truncate if the size of the deque drops to a quarter of the capacity.
176 if (deque->size <= deque->capacity / 4) {
177 if (deque->capacity / 2 >= DS_DEQUE_MIN_CAPACITY) {
178 ds_deque_reallocate(deque, deque->capacity / 2);
179 }
180 }
181 }
182
ds_deque_clear(ds_deque_t * deque)183 void ds_deque_clear(ds_deque_t *deque)
184 {
185 zval *val;
186
187 DS_DEQUE_FOREACH(deque, val) {
188 zval_ptr_dtor(val);
189 }
190 DS_DEQUE_FOREACH_END();
191
192 deque->buffer = ds_reallocate_zval_buffer(deque->buffer, DS_DEQUE_MIN_CAPACITY, deque->capacity, 0);
193 deque->head = 0;
194 deque->tail = 0;
195 deque->size = 0;
196 deque->capacity = DS_DEQUE_MIN_CAPACITY;
197 }
198
ds_deque_free(ds_deque_t * deque)199 void ds_deque_free(ds_deque_t *deque)
200 {
201 zval *val;
202
203 DS_DEQUE_FOREACH(deque, val) {
204 zval_ptr_dtor(val);
205 }
206 DS_DEQUE_FOREACH_END();
207
208 efree(deque->buffer);
209 efree(deque);
210 }
211
212 /**
213 * Translates a positional index into a buffer pointer.
214 */
ds_deque_lookup_index(ds_deque_t * deque,zend_long index)215 static inline zend_long ds_deque_lookup_index(ds_deque_t *deque, zend_long index)
216 {
217 return (deque->head + index) & (deque->capacity - 1);
218 }
219
220 /**
221 * Translates a positional index into a buffer index.
222 */
ds_deque_lookup(ds_deque_t * deque,zend_long index)223 static inline zval *ds_deque_lookup(ds_deque_t *deque, zend_long index)
224 {
225 return deque->buffer + ds_deque_lookup_index(deque, index);
226 }
227
ds_deque_get(ds_deque_t * deque,zend_long index)228 zval *ds_deque_get(ds_deque_t *deque, zend_long index)
229 {
230 if ( ! ds_deque_valid_position(deque, index)) {
231 return NULL;
232 }
233
234 return ds_deque_lookup(deque, index);
235 }
236
ds_deque_set(ds_deque_t * deque,zend_long index,zval * value)237 void ds_deque_set(ds_deque_t *deque, zend_long index, zval *value)
238 {
239 if (ds_deque_valid_position(deque, index)) {
240 zval *ptr = ds_deque_lookup(deque, index);
241 zval_ptr_dtor(ptr);
242 ZVAL_COPY(ptr, value);
243 }
244 }
245
ds_deque_reverse(ds_deque_t * deque)246 void ds_deque_reverse(ds_deque_t *deque)
247 {
248 if (deque->head < deque->tail) {
249 ds_reverse_zval_range(
250 deque->buffer + deque->head,
251 deque->buffer + deque->tail
252 );
253
254 } else {
255 zend_long head = deque->head;
256 zend_long tail = deque->tail;
257 zend_long mask = deque->capacity - 1;
258
259 while (head != tail) {
260 tail = (tail - 1) & mask;
261 SWAP_ZVAL(
262 deque->buffer[head],
263 deque->buffer[tail]
264 );
265 head = (head + 1) & mask;
266 }
267 }
268 }
269
ds_deque_reversed(ds_deque_t * deque)270 ds_deque_t *ds_deque_reversed(ds_deque_t *deque)
271 {
272 zval *src;
273 zval *buf = ds_allocate_zval_buffer(deque->capacity);
274 zval *dst = &buf[deque->size - 1];
275
276 DS_DEQUE_FOREACH(deque, src) {
277 ZVAL_COPY(dst, src);
278 dst--;
279 }
280 DS_DEQUE_FOREACH_END();
281
282 return ds_deque_from_buffer(buf, deque->capacity, deque->size);
283 }
284
285
ds_deque_shift(ds_deque_t * deque,zval * return_value)286 void ds_deque_shift(ds_deque_t *deque, zval *return_value)
287 {
288 SET_AS_RETURN_AND_UNDEF(&deque->buffer[deque->head]);
289 ds_deque_increment_head(deque);
290
291 deque->size--;
292 ds_deque_auto_truncate(deque);
293 }
294
ds_deque_shift_throw(ds_deque_t * deque,zval * return_value)295 void ds_deque_shift_throw(ds_deque_t *deque, zval *return_value)
296 {
297 if (deque->size == 0) {
298 NOT_ALLOWED_WHEN_EMPTY();
299 return;
300 }
301
302 ds_deque_shift(deque, return_value);
303 }
304
ds_deque_pop(ds_deque_t * deque,zval * return_value)305 void ds_deque_pop(ds_deque_t *deque, zval *return_value)
306 {
307 ds_deque_decrement_tail(deque);
308 SET_AS_RETURN_AND_UNDEF(&deque->buffer[deque->tail]);
309
310 deque->size--;
311 ds_deque_auto_truncate(deque);
312 }
313
ds_deque_pop_throw(ds_deque_t * deque,zval * return_value)314 void ds_deque_pop_throw(ds_deque_t *deque, zval *return_value)
315 {
316 if (deque->size == 0) {
317 NOT_ALLOWED_WHEN_EMPTY();
318 return;
319 }
320
321 ds_deque_pop(deque, return_value);
322 }
323
ds_deque_remove(ds_deque_t * deque,zend_long index,zval * return_value)324 void ds_deque_remove(ds_deque_t *deque, zend_long index, zval *return_value)
325 {
326 if ( ! ds_deque_valid_position(deque, index)) {
327 return;
328 }
329
330 // Basic shift if it's the first element in the sequence.
331 if (index == 0) {
332 ds_deque_shift(deque, return_value);
333 return;
334 }
335
336 // Basic pop if it's the last element in the sequence.
337 if (index == deque->size - 1) {
338 ds_deque_pop(deque, return_value);
339 return;
340 }
341
342 // Translate the positional index to a buffer index.
343 index = ds_deque_lookup_index(deque, index);
344
345 // Copy the value into the return value, then clear it.
346 SET_AS_RETURN_AND_UNDEF(&deque->buffer[index]);
347
348 if (index < deque->tail) {
349 // Shift all values between the index and the tail.
350 ds_deque_memmove(deque, index, index + 1, deque->tail - index);
351 deque->tail--;
352
353 } else {
354 // Index comes after tail, and we know at this point that the index
355 // is valid, so it must be after the head which has wrapped around.
356
357 // Unshift all values between the head and the index.
358 ds_deque_memmove(deque, deque->head + 1, deque->head, index - deque->head);
359 deque->head++;
360 }
361
362 deque->size--;
363 ds_deque_auto_truncate(deque);
364 }
365
ds_deque_unshift_va(ds_deque_t * deque,VA_PARAMS)366 void ds_deque_unshift_va(ds_deque_t *deque, VA_PARAMS)
367 {
368 ds_deque_allocate(deque, deque->size + argc);
369 deque->size += argc;
370
371 while (argc--) {
372 ds_deque_decrement_head(deque);
373 ZVAL_COPY(&deque->buffer[deque->head], &argv[argc]);
374 }
375 }
376
ds_deque_push(ds_deque_t * deque,zval * value)377 void ds_deque_push(ds_deque_t *deque, zval *value)
378 {
379 if (deque->size == deque->capacity) {
380 ds_deque_double_capacity(deque);
381 }
382
383 ZVAL_COPY(&deque->buffer[deque->tail], value);
384 ds_deque_increment_tail(deque);
385 deque->size++;
386 }
387
ds_deque_push_va(ds_deque_t * deque,VA_PARAMS)388 void ds_deque_push_va(ds_deque_t *deque, VA_PARAMS)
389 {
390 ds_deque_allocate(deque, deque->size + argc);
391
392 while (argc) {
393 ZVAL_COPY(&deque->buffer[deque->tail], argv);
394 ds_deque_increment_tail(deque);
395 deque->size++;
396
397 argc--;
398 argv++;
399 }
400 }
401
ds_deque_insert_va(ds_deque_t * deque,zend_long position,VA_PARAMS)402 void ds_deque_insert_va(ds_deque_t *deque, zend_long position, VA_PARAMS)
403 {
404 zval *dst;
405 zend_long index;
406
407 // Basic push if inserting at the back.
408 if (position == deque->size) {
409 ds_deque_push_va(deque, VA_ARGS);
410 return;
411 }
412
413 // Basic unshift if inserting at the front.
414 if (position == 0) {
415 ds_deque_unshift_va(deque, VA_ARGS);
416 return;
417 }
418
419 // Check that the insert position is not out of range.
420 if ( ! ds_deque_valid_position(deque, position)) {
421 return;
422 }
423
424 // No op if no values.
425 if (argc <= 0) {
426 return;
427 }
428
429 // Make sure that we have enough room for the new values.
430 ds_deque_allocate(deque, deque->size + argc);
431
432 // Translate the positional index to a buffer index.
433 index = ds_deque_lookup_index(deque, position);
434
435 if (index <= deque->tail) {
436 // The deque is either contiguous or we're inserting in between the
437 // start of the buffer and the tail, where the head has wrapped around.
438
439 // Check for overflow, which is possible because the head won't
440 // always be at the start of the buffer.
441 if ((deque->tail + argc) > deque->capacity) {
442
443 // There isn't enough free space to the right of the tail,
444 // so move the entire sequence all the way to the left.
445 ds_deque_memmove(deque, 0, deque->head, deque->size);
446
447 index -= deque->head;
448 deque->head = 0;
449 deque->tail = deque->size;
450 }
451
452 // Move the subsequence after the insertion point to the right
453 // to make room for the new values.
454 ds_deque_memmove(deque, (index + argc), index, (deque->tail - index));
455 deque->tail += argc;
456 dst = &deque->buffer[index];
457
458 } else {
459 // We're inserting between a wrapped around head and the end of the
460 // buffer, and it's guaranteed that there's enough free space.
461 ds_deque_memmove(deque, (deque->head - argc), deque->head, (index - deque->head));
462 deque->head -= argc;
463 dst = &deque->buffer[index - argc];
464 }
465
466 deque->size += argc;
467
468 // Copy the new values into place.
469 while (argc--) {
470 ZVAL_COPY(dst++, argv++);
471 }
472 }
473
ds_deque_find_index(ds_deque_t * deque,zval * value)474 static zend_long ds_deque_find_index(ds_deque_t *deque, zval *value)
475 {
476 zend_long head = deque->head;
477 zend_long mask = deque->capacity - 1;
478
479 zend_long index;
480
481 for (index = 0; index < deque->size; index++, head++) {
482 if (zend_is_identical(value, &deque->buffer[head & mask])) {
483 return index;
484 }
485 }
486
487 return FAILURE;
488 }
489
ds_deque_join(ds_deque_t * deque,char * str,size_t len,zval * return_value)490 void ds_deque_join(ds_deque_t *deque, char *str, size_t len, zval *return_value)
491 {
492 ds_deque_reset_head(deque);
493
494 ZVAL_STR(
495 return_value,
496 ds_join_zval_buffer(deque->buffer, deque->size, str, len)
497 );
498 }
499
ds_deque_find(ds_deque_t * deque,zval * value,zval * return_value)500 void ds_deque_find(ds_deque_t *deque, zval *value, zval *return_value)
501 {
502 zend_long index = ds_deque_find_index(deque, value);
503
504 if (index >= 0) {
505 ZVAL_LONG(return_value, index);
506 } else {
507 ZVAL_FALSE(return_value);
508 }
509 }
510
ds_deque_contains_va(ds_deque_t * deque,VA_PARAMS)511 bool ds_deque_contains_va(ds_deque_t *deque, VA_PARAMS)
512 {
513 while (argc-- > 0) {
514 if (ds_deque_find_index(deque, argv++) == FAILURE) {
515 return false;
516 }
517 }
518
519 return true;
520 }
521
ds_deque_rotate(ds_deque_t * deque,zend_long n)522 void ds_deque_rotate(ds_deque_t *deque, zend_long n)
523 {
524 if (deque->size < 2) {
525 return;
526 }
527
528 if (n < 0) {
529 for (n = llabs(n) % deque->size; n > 0; n--) {
530
531 // Pop, unshift
532 ds_deque_decrement_head(deque);
533 ds_deque_decrement_tail(deque);
534
535 // Tail is now at last value, head is before the first.
536 SWAP_ZVAL(deque->buffer[deque->tail], deque->buffer[deque->head]);
537 }
538 } else if (n > 0) {
539 for (n = n % deque->size; n > 0; n--) {
540
541 // Tail is one past the last value, head is at first value.
542 SWAP_ZVAL(deque->buffer[deque->tail], deque->buffer[deque->head]);
543
544 // Shift, push
545 ds_deque_increment_head(deque);
546 ds_deque_increment_tail(deque);
547 }
548 }
549 }
550
ds_deque_to_array(ds_deque_t * deque,zval * array)551 void ds_deque_to_array(ds_deque_t *deque, zval *array)
552 {
553 if (deque->size == 0) {
554 array_init(array);
555 return;
556
557 } else {
558 zval *value;
559 array_init_size(array, deque->size);
560
561 DS_DEQUE_FOREACH(deque, value) {
562 add_next_index_zval(array, value);
563 Z_TRY_ADDREF_P(value);
564 }
565 DS_DEQUE_FOREACH_END();
566 }
567 }
568
ds_deque_index_exists(ds_deque_t * deque,zend_long index)569 bool ds_deque_index_exists(ds_deque_t *deque, zend_long index)
570 {
571 return index >= 0 && index < deque->size;
572 }
573
ds_deque_isset(ds_deque_t * deque,zend_long index,int check_empty)574 bool ds_deque_isset(ds_deque_t *deque, zend_long index, int check_empty)
575 {
576 if (!ds_deque_index_exists(deque, index)) {
577 return false;
578 }
579
580 return ds_zval_isset(ds_deque_lookup(deque, index), check_empty);
581 }
582
ds_deque_get_last(ds_deque_t * deque)583 zval *ds_deque_get_last(ds_deque_t *deque)
584 {
585 return &deque->buffer[(deque->tail - 1) & (deque->capacity - 1)];
586 }
587
ds_deque_get_last_throw(ds_deque_t * deque)588 zval *ds_deque_get_last_throw(ds_deque_t *deque)
589 {
590 if (deque->size == 0) {
591 NOT_ALLOWED_WHEN_EMPTY();
592 return NULL;
593 }
594
595 return ds_deque_get_last(deque);
596 }
597
ds_deque_get_first(ds_deque_t * deque)598 zval *ds_deque_get_first(ds_deque_t *deque)
599 {
600 return &deque->buffer[deque->head];
601 }
602
ds_deque_get_first_throw(ds_deque_t * deque)603 zval *ds_deque_get_first_throw(ds_deque_t *deque)
604 {
605 if (deque->size == 0) {
606 NOT_ALLOWED_WHEN_EMPTY();
607 return NULL;
608 }
609
610 return ds_deque_get_first(deque);
611 }
612
iterator_add(zend_object_iterator * iterator,void * puser)613 static int iterator_add(zend_object_iterator *iterator, void *puser)
614 {
615 ds_deque_push((ds_deque_t *) puser, iterator->funcs->get_current_data(iterator));
616 return ZEND_HASH_APPLY_KEEP;
617 }
618
add_traversable_to_deque(ds_deque_t * deque,zval * obj)619 static void add_traversable_to_deque(ds_deque_t *deque, zval *obj)
620 {
621 spl_iterator_apply(obj, iterator_add, deque);
622 }
623
add_array_to_deque(ds_deque_t * deque,HashTable * arr)624 static void add_array_to_deque(ds_deque_t *deque, HashTable *arr)
625 {
626 zval *value;
627 ZEND_HASH_FOREACH_VAL(arr, value) {
628 ds_deque_push(deque, value);
629 }
630 ZEND_HASH_FOREACH_END();
631 }
632
ds_deque_push_all(ds_deque_t * deque,zval * values)633 void ds_deque_push_all(ds_deque_t *deque, zval *values)
634 {
635 if ( ! values) {
636 return;
637 }
638
639 if (ds_is_array(values)) {
640 add_array_to_deque(deque, Z_ARRVAL_P(values));
641 return;
642 }
643
644 if (ds_is_traversable(values)) {
645 add_traversable_to_deque(deque, values);
646 return;
647 }
648
649 ARRAY_OR_TRAVERSABLE_REQUIRED();
650 }
651
ds_deque_merge(ds_deque_t * deque,zval * values)652 ds_deque_t *ds_deque_merge(ds_deque_t *deque, zval *values)
653 {
654 if (values && (ds_is_array(values) || ds_is_traversable(values))) {
655 ds_deque_t *merged = ds_deque_clone(deque);
656 ds_deque_push_all(merged, values);
657 return merged;
658 }
659
660 ARRAY_OR_TRAVERSABLE_REQUIRED();
661 return NULL;
662 }
663
ds_deque_sort_callback(ds_deque_t * deque)664 void ds_deque_sort_callback(ds_deque_t *deque)
665 {
666 ds_deque_reset_head(deque);
667 ds_user_sort_zval_buffer(deque->buffer, deque->size);
668 }
669
ds_deque_sort(ds_deque_t * deque)670 void ds_deque_sort(ds_deque_t *deque)
671 {
672 ds_deque_reset_head(deque);
673 ds_sort_zval_buffer(deque->buffer, deque->size);
674 }
675
ds_deque_apply(ds_deque_t * deque,FCI_PARAMS)676 void ds_deque_apply(ds_deque_t *deque, FCI_PARAMS)
677 {
678 zval *value;
679 zval retval;
680
681 DS_DEQUE_FOREACH(deque, value) {
682 fci.param_count = 1;
683 fci.params = value;
684 fci.retval = &retval;
685
686 if (zend_call_function(&fci, &fci_cache) == FAILURE || Z_ISUNDEF(retval)) {
687 return;
688 }
689
690 zval_ptr_dtor(value);
691 ZVAL_COPY_VALUE(value, &retval);
692 }
693
694 DS_DEQUE_FOREACH_END();
695 }
696
ds_deque_map(ds_deque_t * deque,FCI_PARAMS)697 ds_deque_t *ds_deque_map(ds_deque_t *deque, FCI_PARAMS)
698 {
699 zval retval;
700 zval *value;
701 zval *buffer = ds_allocate_zval_buffer(deque->capacity);
702 zval *target = buffer;
703
704 DS_DEQUE_FOREACH(deque, value) {
705 fci.param_count = 1;
706 fci.params = value;
707 fci.retval = &retval;
708
709 if (zend_call_function(&fci, &fci_cache) == FAILURE || Z_ISUNDEF(retval)) {
710
711 // Release the values copied into the buffer on failure.
712 target--;
713 while (target > buffer) {
714 zval_ptr_dtor(target--);
715 }
716
717 zval_ptr_dtor(&retval);
718 efree(buffer);
719 return NULL;
720 }
721
722 ZVAL_COPY(target++, &retval);
723 zval_ptr_dtor(&retval);
724 }
725 DS_DEQUE_FOREACH_END();
726
727 return ds_deque_from_buffer(buffer, deque->capacity, deque->size);
728 }
729
ds_deque_filter_callback(ds_deque_t * deque,FCI_PARAMS)730 ds_deque_t *ds_deque_filter_callback(ds_deque_t *deque, FCI_PARAMS)
731 {
732 if (deque->size == 0) {
733 return ds_deque();
734
735 } else {
736 zval retval;
737 zval *val;
738 zval *buf = ds_allocate_zval_buffer(deque->capacity);
739 zval *dst = buf;
740
741 DS_DEQUE_FOREACH(deque, val) {
742 fci.param_count = 1;
743 fci.params = val;
744 fci.retval = &retval;
745
746 // Catch potential exceptions or other errors during comparison.
747 if (zend_call_function(&fci, &fci_cache) == FAILURE || Z_ISUNDEF(retval)) {
748
749 // Release the values copied into the buffer on failure.
750 dst--;
751 while (dst >= buf) {
752 zval_ptr_dtor(dst--);
753 }
754
755 zval_ptr_dtor(&retval);
756 efree(buf);
757 return NULL;
758 }
759
760 // Copy the value into the buffer if the callback returned true.
761 if (EXPECTED_BOOL_IS_TRUE(&retval)) {
762 ZVAL_COPY(dst++, val);
763 }
764
765 zval_ptr_dtor(&retval);
766 }
767
768 DS_DEQUE_FOREACH_END();
769 return ds_deque_from_buffer(buf, ds_deque_get_capacity_for_size(dst - buf), (dst - buf));
770 }
771 }
772
ds_deque_filter(ds_deque_t * deque)773 ds_deque_t *ds_deque_filter(ds_deque_t *deque)
774 {
775 if (deque->size == 0) {
776 return ds_deque();
777
778 } else {
779 zval *buf = ds_allocate_zval_buffer(deque->capacity);
780 zval *dst = buf;
781 zval *src = NULL;
782
783 DS_DEQUE_FOREACH(deque, src) {
784 if (zend_is_true(src)) {
785 ZVAL_COPY(dst++, src);
786 }
787 }
788 DS_DEQUE_FOREACH_END();
789
790 return ds_deque_from_buffer(buf, ds_deque_get_capacity_for_size(dst - buf), (dst - buf));
791 }
792 }
793
ds_deque_reduce(ds_deque_t * deque,zval * initial,zval * return_value,FCI_PARAMS)794 void ds_deque_reduce(ds_deque_t *deque, zval *initial, zval *return_value, FCI_PARAMS)
795 {
796 zval *value;
797 zval carry;
798 zval params[2];
799
800 if (initial == NULL) {
801 ZVAL_NULL(&carry);
802 } else {
803 ZVAL_COPY_VALUE(&carry, initial);
804 }
805
806 DS_DEQUE_FOREACH(deque, value) {
807 ZVAL_COPY_VALUE(¶ms[0], &carry);
808 ZVAL_COPY_VALUE(¶ms[1], value);
809
810 fci.param_count = 2;
811 fci.params = params;
812 fci.retval = &carry;
813
814 if (zend_call_function(&fci, &fci_cache) == FAILURE || Z_ISUNDEF(carry)) {
815 zval_ptr_dtor(&carry);
816 ZVAL_NULL(return_value);
817 return;
818 }
819
820 Z_TRY_DELREF_P(&carry);
821 }
822 DS_DEQUE_FOREACH_END();
823 ZVAL_COPY(return_value, &carry);
824 }
825
ds_deque_slice(ds_deque_t * deque,zend_long index,zend_long length)826 ds_deque_t *ds_deque_slice(ds_deque_t *deque, zend_long index, zend_long length)
827 {
828 ds_normalize_slice_args(&index, &length, deque->size);
829
830 if (length == 0) {
831 return ds_deque();
832
833 } else {
834 ds_deque_t *result = ds_deque_preallocated(length);
835
836 for (; length > 0; length--) {
837 ds_deque_push(result, ds_deque_lookup(deque, index++));
838 }
839
840 return result;
841 }
842 }
843
ds_deque_sum(ds_deque_t * deque,zval * return_value)844 void ds_deque_sum(ds_deque_t *deque, zval *return_value)
845 {
846 zval *value;
847
848 ZVAL_LONG(return_value, 0);
849
850 DS_DEQUE_FOREACH(deque, value) {
851 DS_ADD_TO_SUM(value, return_value);
852 }
853 DS_DEQUE_FOREACH_END();
854 }
855