Lines Matching refs:deque
9 static inline void ds_deque_increment_head(ds_deque_t *deque) in ds_deque_increment_head() argument
11 deque->head = (deque->head + 1) & (deque->capacity - 1); in ds_deque_increment_head()
14 static inline void ds_deque_decrement_head(ds_deque_t *deque) in ds_deque_decrement_head() argument
16 deque->head = (deque->head - 1) & (deque->capacity - 1); in ds_deque_decrement_head()
19 static inline void ds_deque_increment_tail(ds_deque_t *deque) in ds_deque_increment_tail() argument
21 deque->tail = (deque->tail + 1) & (deque->capacity - 1); in ds_deque_increment_tail()
24 static inline void ds_deque_decrement_tail(ds_deque_t *deque) in ds_deque_decrement_tail() argument
26 deque->tail = (deque->tail - 1) & (deque->capacity - 1); in ds_deque_decrement_tail()
30 ds_deque_t *deque, in ds_deque_memmove() argument
35 memmove(&deque->buffer[dst], &deque->buffer[src], length * sizeof(zval)); in ds_deque_memmove()
45 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t)); in ds_deque() local
47 deque->buffer = ds_allocate_zval_buffer(DS_DEQUE_MIN_CAPACITY); in ds_deque()
48 deque->capacity = DS_DEQUE_MIN_CAPACITY; in ds_deque()
49 deque->head = 0; in ds_deque()
50 deque->tail = 0; in ds_deque()
51 deque->size = 0; in ds_deque()
53 return deque; in ds_deque()
58 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t)); in ds_deque_preallocated() local
60 deque->capacity = ds_deque_get_capacity_for_size(size); in ds_deque_preallocated()
61 deque->buffer = ds_allocate_zval_buffer(deque->capacity); in ds_deque_preallocated()
62 deque->head = 0; in ds_deque_preallocated()
63 deque->tail = 0; in ds_deque_preallocated()
64 deque->size = 0; in ds_deque_preallocated()
66 return deque; in ds_deque_preallocated()
71 ds_deque_t *deque = ecalloc(1, sizeof(ds_deque_t)); in ds_deque_from_buffer() local
73 deque->buffer = buffer; in ds_deque_from_buffer()
74 deque->capacity = capacity; in ds_deque_from_buffer()
75 deque->head = 0; in ds_deque_from_buffer()
76 deque->tail = size; in ds_deque_from_buffer()
77 deque->size = size; in ds_deque_from_buffer()
79 return deque; in ds_deque_from_buffer()
82 ds_deque_t *ds_deque_clone(ds_deque_t *deque) in ds_deque_clone() argument
85 zval *buffer = ds_allocate_zval_buffer(deque->capacity); in ds_deque_clone()
88 DS_DEQUE_FOREACH(deque, source) { in ds_deque_clone()
94 return ds_deque_from_buffer(buffer, deque->capacity, deque->size); in ds_deque_clone()
98 static inline bool ds_deque_valid_position(ds_deque_t *deque, zend_long index) in ds_deque_valid_position() argument
100 if (index < 0 || index >= deque->size) { in ds_deque_valid_position()
101 INDEX_OUT_OF_RANGE(index, deque->size); in ds_deque_valid_position()
109 void ds_deque_reset_head(ds_deque_t *deque) in ds_deque_reset_head() argument
111 if (deque->head == 0) { in ds_deque_reset_head()
115 if (deque->head < deque->tail) { in ds_deque_reset_head()
116 ds_deque_memmove(deque, 0, deque->head, deque->size); in ds_deque_reset_head()
119 zend_long h = deque->head; in ds_deque_reset_head()
120 zend_long t = deque->tail; in ds_deque_reset_head()
121 zend_long r = deque->capacity - h; // Number of values on the right. in ds_deque_reset_head()
126 ds_deque_memmove(deque, r, 0, t); in ds_deque_reset_head()
127 ds_deque_memmove(deque, 0, h, r); in ds_deque_reset_head()
132 zval *buffer = ds_allocate_zval_buffer(deque->capacity); in ds_deque_reset_head()
134 memcpy(&buffer[0], &deque->buffer[h], r * sizeof(zval)); in ds_deque_reset_head()
135 memcpy(&buffer[r], &deque->buffer[0], t * sizeof(zval)); in ds_deque_reset_head()
137 FREE_AND_REPLACE(deque->buffer, buffer); in ds_deque_reset_head()
141 deque->head = 0; in ds_deque_reset_head()
142 deque->tail = deque->size; in ds_deque_reset_head()
145 static void ds_deque_reallocate(ds_deque_t *deque, zend_long capacity) in ds_deque_reallocate() argument
147 ds_deque_reset_head(deque); in ds_deque_reallocate()
149 …deque->buffer = ds_reallocate_zval_buffer(deque->buffer, capacity, deque->capacity, deque->size); in ds_deque_reallocate()
150 deque->capacity = capacity; in ds_deque_reallocate()
151 deque->head = 0; in ds_deque_reallocate()
152 deque->tail = deque->size; // Could have been zero before if buffer was full. in ds_deque_reallocate()
155 static inline void ds_deque_double_capacity(ds_deque_t *deque) in ds_deque_double_capacity() argument
157 ds_deque_reallocate(deque, deque->capacity << 1); in ds_deque_double_capacity()
160 void ds_deque_allocate(ds_deque_t *deque, zend_long size) in ds_deque_allocate() argument
168 if (capacity > deque->capacity) { in ds_deque_allocate()
169 ds_deque_reallocate(deque, capacity); in ds_deque_allocate()
173 static inline void ds_deque_auto_truncate(ds_deque_t *deque) in ds_deque_auto_truncate() argument
176 if (deque->size <= deque->capacity / 4) { in ds_deque_auto_truncate()
177 if (deque->capacity / 2 >= DS_DEQUE_MIN_CAPACITY) { in ds_deque_auto_truncate()
178 ds_deque_reallocate(deque, deque->capacity / 2); in ds_deque_auto_truncate()
183 void ds_deque_clear(ds_deque_t *deque) in ds_deque_clear() argument
187 DS_DEQUE_FOREACH(deque, val) { in ds_deque_clear()
192 …deque->buffer = ds_reallocate_zval_buffer(deque->buffer, DS_DEQUE_MIN_CAPACITY, deque->capacity,… in ds_deque_clear()
193 deque->head = 0; in ds_deque_clear()
194 deque->tail = 0; in ds_deque_clear()
195 deque->size = 0; in ds_deque_clear()
196 deque->capacity = DS_DEQUE_MIN_CAPACITY; in ds_deque_clear()
199 void ds_deque_free(ds_deque_t *deque) in ds_deque_free() argument
203 DS_DEQUE_FOREACH(deque, val) { in ds_deque_free()
208 efree(deque->buffer); in ds_deque_free()
209 efree(deque); in ds_deque_free()
215 static inline zend_long ds_deque_lookup_index(ds_deque_t *deque, zend_long index) in ds_deque_lookup_index() argument
217 return (deque->head + index) & (deque->capacity - 1); in ds_deque_lookup_index()
223 static inline zval *ds_deque_lookup(ds_deque_t *deque, zend_long index) in ds_deque_lookup() argument
225 return deque->buffer + ds_deque_lookup_index(deque, index); in ds_deque_lookup()
228 zval *ds_deque_get(ds_deque_t *deque, zend_long index) in ds_deque_get() argument
230 if ( ! ds_deque_valid_position(deque, index)) { in ds_deque_get()
234 return ds_deque_lookup(deque, index); in ds_deque_get()
237 void ds_deque_set(ds_deque_t *deque, zend_long index, zval *value) in ds_deque_set() argument
239 if (ds_deque_valid_position(deque, index)) { in ds_deque_set()
240 zval *ptr = ds_deque_lookup(deque, index); in ds_deque_set()
246 void ds_deque_reverse(ds_deque_t *deque) in ds_deque_reverse() argument
248 if (deque->head < deque->tail) { in ds_deque_reverse()
250 deque->buffer + deque->head, in ds_deque_reverse()
251 deque->buffer + deque->tail in ds_deque_reverse()
255 zend_long head = deque->head; in ds_deque_reverse()
256 zend_long tail = deque->tail; in ds_deque_reverse()
257 zend_long mask = deque->capacity - 1; in ds_deque_reverse()
262 deque->buffer[head], in ds_deque_reverse()
263 deque->buffer[tail] in ds_deque_reverse()
270 ds_deque_t *ds_deque_reversed(ds_deque_t *deque) in ds_deque_reversed() argument
273 zval *buf = ds_allocate_zval_buffer(deque->capacity); in ds_deque_reversed()
274 zval *dst = &buf[deque->size - 1]; in ds_deque_reversed()
276 DS_DEQUE_FOREACH(deque, src) { in ds_deque_reversed()
282 return ds_deque_from_buffer(buf, deque->capacity, deque->size); in ds_deque_reversed()
286 void ds_deque_shift(ds_deque_t *deque, zval *return_value) in ds_deque_shift() argument
288 SET_AS_RETURN_AND_UNDEF(&deque->buffer[deque->head]); in ds_deque_shift()
289 ds_deque_increment_head(deque); in ds_deque_shift()
291 deque->size--; in ds_deque_shift()
292 ds_deque_auto_truncate(deque); in ds_deque_shift()
295 void ds_deque_shift_throw(ds_deque_t *deque, zval *return_value) in ds_deque_shift_throw() argument
297 if (deque->size == 0) { in ds_deque_shift_throw()
302 ds_deque_shift(deque, return_value); in ds_deque_shift_throw()
305 void ds_deque_pop(ds_deque_t *deque, zval *return_value) in ds_deque_pop() argument
307 ds_deque_decrement_tail(deque); in ds_deque_pop()
308 SET_AS_RETURN_AND_UNDEF(&deque->buffer[deque->tail]); in ds_deque_pop()
310 deque->size--; in ds_deque_pop()
311 ds_deque_auto_truncate(deque); in ds_deque_pop()
314 void ds_deque_pop_throw(ds_deque_t *deque, zval *return_value) in ds_deque_pop_throw() argument
316 if (deque->size == 0) { in ds_deque_pop_throw()
321 ds_deque_pop(deque, return_value); in ds_deque_pop_throw()
324 void ds_deque_remove(ds_deque_t *deque, zend_long index, zval *return_value) in ds_deque_remove() argument
326 if ( ! ds_deque_valid_position(deque, index)) { in ds_deque_remove()
332 ds_deque_shift(deque, return_value); in ds_deque_remove()
337 if (index == deque->size - 1) { in ds_deque_remove()
338 ds_deque_pop(deque, return_value); in ds_deque_remove()
343 index = ds_deque_lookup_index(deque, index); in ds_deque_remove()
346 SET_AS_RETURN_AND_UNDEF(&deque->buffer[index]); in ds_deque_remove()
348 if (index < deque->tail) { in ds_deque_remove()
350 ds_deque_memmove(deque, index, index + 1, deque->tail - index); in ds_deque_remove()
351 deque->tail--; in ds_deque_remove()
358 ds_deque_memmove(deque, deque->head + 1, deque->head, index - deque->head); in ds_deque_remove()
359 deque->head++; in ds_deque_remove()
362 deque->size--; in ds_deque_remove()
363 ds_deque_auto_truncate(deque); in ds_deque_remove()
366 void ds_deque_unshift_va(ds_deque_t *deque, VA_PARAMS) in ds_deque_unshift_va() argument
368 ds_deque_allocate(deque, deque->size + argc); in ds_deque_unshift_va()
369 deque->size += argc; in ds_deque_unshift_va()
372 ds_deque_decrement_head(deque); in ds_deque_unshift_va()
373 ZVAL_COPY(&deque->buffer[deque->head], &argv[argc]); in ds_deque_unshift_va()
377 void ds_deque_push(ds_deque_t *deque, zval *value) in ds_deque_push() argument
379 if (deque->size == deque->capacity) { in ds_deque_push()
380 ds_deque_double_capacity(deque); in ds_deque_push()
383 ZVAL_COPY(&deque->buffer[deque->tail], value); in ds_deque_push()
384 ds_deque_increment_tail(deque); in ds_deque_push()
385 deque->size++; in ds_deque_push()
388 void ds_deque_push_va(ds_deque_t *deque, VA_PARAMS) in ds_deque_push_va() argument
390 ds_deque_allocate(deque, deque->size + argc); in ds_deque_push_va()
393 ZVAL_COPY(&deque->buffer[deque->tail], argv); in ds_deque_push_va()
394 ds_deque_increment_tail(deque); in ds_deque_push_va()
395 deque->size++; in ds_deque_push_va()
402 void ds_deque_insert_va(ds_deque_t *deque, zend_long position, VA_PARAMS) in ds_deque_insert_va() argument
408 if (position == deque->size) { in ds_deque_insert_va()
409 ds_deque_push_va(deque, VA_ARGS); in ds_deque_insert_va()
415 ds_deque_unshift_va(deque, VA_ARGS); in ds_deque_insert_va()
420 if ( ! ds_deque_valid_position(deque, position)) { in ds_deque_insert_va()
430 ds_deque_allocate(deque, deque->size + argc); in ds_deque_insert_va()
433 index = ds_deque_lookup_index(deque, position); in ds_deque_insert_va()
435 if (index <= deque->tail) { in ds_deque_insert_va()
441 if ((deque->tail + argc) > deque->capacity) { in ds_deque_insert_va()
445 ds_deque_memmove(deque, 0, deque->head, deque->size); in ds_deque_insert_va()
447 index -= deque->head; in ds_deque_insert_va()
448 deque->head = 0; in ds_deque_insert_va()
449 deque->tail = deque->size; in ds_deque_insert_va()
454 ds_deque_memmove(deque, (index + argc), index, (deque->tail - index)); in ds_deque_insert_va()
455 deque->tail += argc; in ds_deque_insert_va()
456 dst = &deque->buffer[index]; in ds_deque_insert_va()
461 ds_deque_memmove(deque, (deque->head - argc), deque->head, (index - deque->head)); in ds_deque_insert_va()
462 deque->head -= argc; in ds_deque_insert_va()
463 dst = &deque->buffer[index - argc]; in ds_deque_insert_va()
466 deque->size += argc; in ds_deque_insert_va()
474 static zend_long ds_deque_find_index(ds_deque_t *deque, zval *value) in ds_deque_find_index() argument
476 zend_long head = deque->head; in ds_deque_find_index()
477 zend_long mask = deque->capacity - 1; in ds_deque_find_index()
481 for (index = 0; index < deque->size; index++, head++) { in ds_deque_find_index()
482 if (zend_is_identical(value, &deque->buffer[head & mask])) { in ds_deque_find_index()
490 void ds_deque_join(ds_deque_t *deque, char *str, size_t len, zval *return_value) in ds_deque_join() argument
492 ds_deque_reset_head(deque); in ds_deque_join()
496 ds_join_zval_buffer(deque->buffer, deque->size, str, len) in ds_deque_join()
500 void ds_deque_find(ds_deque_t *deque, zval *value, zval *return_value) in ds_deque_find() argument
502 zend_long index = ds_deque_find_index(deque, value); in ds_deque_find()
511 bool ds_deque_contains_va(ds_deque_t *deque, VA_PARAMS) in ds_deque_contains_va() argument
514 if (ds_deque_find_index(deque, argv++) == FAILURE) { in ds_deque_contains_va()
522 void ds_deque_rotate(ds_deque_t *deque, zend_long n) in ds_deque_rotate() argument
524 if (deque->size < 2) { in ds_deque_rotate()
529 for (n = llabs(n) % deque->size; n > 0; n--) { in ds_deque_rotate()
532 ds_deque_decrement_head(deque); in ds_deque_rotate()
533 ds_deque_decrement_tail(deque); in ds_deque_rotate()
536 SWAP_ZVAL(deque->buffer[deque->tail], deque->buffer[deque->head]); in ds_deque_rotate()
539 for (n = n % deque->size; n > 0; n--) { in ds_deque_rotate()
542 SWAP_ZVAL(deque->buffer[deque->tail], deque->buffer[deque->head]); in ds_deque_rotate()
545 ds_deque_increment_head(deque); in ds_deque_rotate()
546 ds_deque_increment_tail(deque); in ds_deque_rotate()
551 void ds_deque_to_array(ds_deque_t *deque, zval *array) in ds_deque_to_array() argument
553 if (deque->size == 0) { in ds_deque_to_array()
559 array_init_size(array, deque->size); in ds_deque_to_array()
561 DS_DEQUE_FOREACH(deque, value) { in ds_deque_to_array()
569 bool ds_deque_index_exists(ds_deque_t *deque, zend_long index) in ds_deque_index_exists() argument
571 return index >= 0 && index < deque->size; in ds_deque_index_exists()
574 bool ds_deque_isset(ds_deque_t *deque, zend_long index, int check_empty) in ds_deque_isset() argument
576 if (!ds_deque_index_exists(deque, index)) { in ds_deque_isset()
580 return ds_zval_isset(ds_deque_lookup(deque, index), check_empty); in ds_deque_isset()
583 zval *ds_deque_get_last(ds_deque_t *deque) in ds_deque_get_last() argument
585 return &deque->buffer[(deque->tail - 1) & (deque->capacity - 1)]; in ds_deque_get_last()
588 zval *ds_deque_get_last_throw(ds_deque_t *deque) in ds_deque_get_last_throw() argument
590 if (deque->size == 0) { in ds_deque_get_last_throw()
595 return ds_deque_get_last(deque); in ds_deque_get_last_throw()
598 zval *ds_deque_get_first(ds_deque_t *deque) in ds_deque_get_first() argument
600 return &deque->buffer[deque->head]; in ds_deque_get_first()
603 zval *ds_deque_get_first_throw(ds_deque_t *deque) in ds_deque_get_first_throw() argument
605 if (deque->size == 0) { in ds_deque_get_first_throw()
610 return ds_deque_get_first(deque); in ds_deque_get_first_throw()
619 static void add_traversable_to_deque(ds_deque_t *deque, zval *obj) in add_traversable_to_deque() argument
621 spl_iterator_apply(obj, iterator_add, deque); in add_traversable_to_deque()
624 static void add_array_to_deque(ds_deque_t *deque, HashTable *arr) in add_array_to_deque() argument
628 ds_deque_push(deque, value); in add_array_to_deque()
633 void ds_deque_push_all(ds_deque_t *deque, zval *values) in ds_deque_push_all() argument
640 add_array_to_deque(deque, Z_ARRVAL_P(values)); in ds_deque_push_all()
645 add_traversable_to_deque(deque, values); in ds_deque_push_all()
652 ds_deque_t *ds_deque_merge(ds_deque_t *deque, zval *values) in ds_deque_merge() argument
655 ds_deque_t *merged = ds_deque_clone(deque); in ds_deque_merge()
664 void ds_deque_sort_callback(ds_deque_t *deque) in ds_deque_sort_callback() argument
666 ds_deque_reset_head(deque); in ds_deque_sort_callback()
667 ds_user_sort_zval_buffer(deque->buffer, deque->size); in ds_deque_sort_callback()
670 void ds_deque_sort(ds_deque_t *deque) in ds_deque_sort() argument
672 ds_deque_reset_head(deque); in ds_deque_sort()
673 ds_sort_zval_buffer(deque->buffer, deque->size); in ds_deque_sort()
676 void ds_deque_apply(ds_deque_t *deque, FCI_PARAMS) in ds_deque_apply() argument
681 DS_DEQUE_FOREACH(deque, value) { in ds_deque_apply()
697 ds_deque_t *ds_deque_map(ds_deque_t *deque, FCI_PARAMS) in ds_deque_map() argument
701 zval *buffer = ds_allocate_zval_buffer(deque->capacity); in ds_deque_map()
704 DS_DEQUE_FOREACH(deque, value) { in ds_deque_map()
727 return ds_deque_from_buffer(buffer, deque->capacity, deque->size); in ds_deque_map()
730 ds_deque_t *ds_deque_filter_callback(ds_deque_t *deque, FCI_PARAMS) in ds_deque_filter_callback() argument
732 if (deque->size == 0) { in ds_deque_filter_callback()
738 zval *buf = ds_allocate_zval_buffer(deque->capacity); in ds_deque_filter_callback()
741 DS_DEQUE_FOREACH(deque, val) { in ds_deque_filter_callback()
773 ds_deque_t *ds_deque_filter(ds_deque_t *deque) in ds_deque_filter() argument
775 if (deque->size == 0) { in ds_deque_filter()
779 zval *buf = ds_allocate_zval_buffer(deque->capacity); in ds_deque_filter()
783 DS_DEQUE_FOREACH(deque, src) { in ds_deque_filter()
794 void ds_deque_reduce(ds_deque_t *deque, zval *initial, zval *return_value, FCI_PARAMS) in ds_deque_reduce() argument
806 DS_DEQUE_FOREACH(deque, value) { in ds_deque_reduce()
826 ds_deque_t *ds_deque_slice(ds_deque_t *deque, zend_long index, zend_long length) in ds_deque_slice() argument
828 ds_normalize_slice_args(&index, &length, deque->size); in ds_deque_slice()
837 ds_deque_push(result, ds_deque_lookup(deque, index++)); in ds_deque_slice()
844 void ds_deque_sum(ds_deque_t *deque, zval *return_value) in ds_deque_sum() argument
850 DS_DEQUE_FOREACH(deque, value) { in ds_deque_sum()
