Lines Matching refs:queue
54 static inline void reallocate_to_capacity(ds_priority_queue_t *queue, uint32_t capacity) in reallocate_to_capacity() argument
56 queue->nodes = reallocate_nodes(queue->nodes, capacity); in reallocate_to_capacity()
57 queue->capacity = capacity; in reallocate_to_capacity()
60 static inline void increase_capacity(ds_priority_queue_t *queue) in increase_capacity() argument
62 reallocate_to_capacity(queue, queue->capacity * 2); in increase_capacity()
65 void ds_priority_queue_allocate(ds_priority_queue_t *queue, uint32_t capacity) in ds_priority_queue_allocate() argument
69 if (capacity > queue->capacity) { in ds_priority_queue_allocate()
70 reallocate_to_capacity(queue, capacity); in ds_priority_queue_allocate()
76 ds_priority_queue_t *queue = ecalloc(1, sizeof(ds_priority_queue_t)); in ds_priority_queue() local
78 queue->nodes = allocate_nodes(DS_PRIORITY_QUEUE_MIN_CAPACITY); in ds_priority_queue()
79 queue->capacity = DS_PRIORITY_QUEUE_MIN_CAPACITY; in ds_priority_queue()
80 queue->size = 0; in ds_priority_queue()
81 queue->next = 0; in ds_priority_queue()
83 return queue; in ds_priority_queue()
86 uint32_t ds_priority_queue_capacity(ds_priority_queue_t *queue) in ds_priority_queue_capacity() argument
88 return queue->capacity; in ds_priority_queue_capacity()
91 void ds_priority_queue_push(ds_priority_queue_t *queue, zval *value, zval *priority) in ds_priority_queue_push() argument
101 if (queue->size == queue->capacity) { in ds_priority_queue_push()
102 increase_capacity(queue); in ds_priority_queue_push()
105 nodes = queue->nodes; in ds_priority_queue_push()
107 for (index = queue->size; index > 0; index = parent) { in ds_priority_queue_push()
126 node = &queue->nodes[index]; in ds_priority_queue_push()
129 STAMP(node) = ++queue->next; in ds_priority_queue_push()
134 queue->size++; in ds_priority_queue_push()
137 static inline void ds_priority_queue_compact(ds_priority_queue_t *queue) in ds_priority_queue_compact() argument
139 …if (queue->size <= (queue->capacity / 4) && (queue->capacity / 2) >= DS_PRIORITY_QUEUE_MIN_CAPACIT… in ds_priority_queue_compact()
140 reallocate_to_capacity(queue, queue->capacity / 2); in ds_priority_queue_compact()
144 void ds_priority_queue_pop(ds_priority_queue_t *queue, zval *return_value) in ds_priority_queue_pop() argument
150 ds_priority_queue_node_t *nodes = queue->nodes; in ds_priority_queue_pop()
152 const uint32_t size = queue->size; in ds_priority_queue_pop()
174 queue->size--; in ds_priority_queue_pop()
180 … if (swap < queue->size && ds_priority_queue_node_compare(&nodes[swap], &nodes[swap + 1]) < 0) { in ds_priority_queue_pop()
195 ds_priority_queue_compact(queue); in ds_priority_queue_pop()
198 static ds_priority_queue_node_t *copy_nodes(ds_priority_queue_t *queue) in copy_nodes() argument
200 ds_priority_queue_node_t *copies = allocate_nodes(queue->capacity); in copy_nodes()
202 ds_priority_queue_node_t *src = queue->nodes; in copy_nodes()
203 ds_priority_queue_node_t *end = queue->nodes + queue->size; in copy_nodes()
214 ds_priority_queue_t *ds_priority_queue_clone(ds_priority_queue_t * queue) in ds_priority_queue_clone() argument
218 clone->nodes = copy_nodes(queue); in ds_priority_queue_clone()
219 clone->capacity = queue->capacity; in ds_priority_queue_clone()
220 clone->size = queue->size; in ds_priority_queue_clone()
221 clone->next = queue->next; in ds_priority_queue_clone()
226 zval *ds_priority_queue_peek(ds_priority_queue_t *queue) in ds_priority_queue_peek() argument
228 if (queue->size == 0) { in ds_priority_queue_peek()
233 return &queue->nodes[0].value; in ds_priority_queue_peek()
244 ds_priority_queue_node_t* ds_priority_queue_create_sorted_buffer(ds_priority_queue_t *queue) in ds_priority_queue_create_sorted_buffer() argument
246 ds_priority_queue_node_t *buffer = allocate_nodes(queue->size); in ds_priority_queue_create_sorted_buffer()
248 memcpy(buffer, queue->nodes, queue->size * sizeof(ds_priority_queue_node_t)); in ds_priority_queue_create_sorted_buffer()
249 qsort(buffer, queue->size, sizeof(ds_priority_queue_node_t), priority_sort); in ds_priority_queue_create_sorted_buffer()
254 void ds_priority_queue_to_array(ds_priority_queue_t *queue, zval *array) in ds_priority_queue_to_array() argument
256 if (DS_PRIORITY_QUEUE_IS_EMPTY(queue)) { in ds_priority_queue_to_array()
262 buf = ds_priority_queue_create_sorted_buffer(queue); in ds_priority_queue_to_array()
264 end = buf + queue->size; in ds_priority_queue_to_array()
266 array_init_size(array, queue->size); in ds_priority_queue_to_array()
277 void ds_priority_queue_clear(ds_priority_queue_t *queue) in ds_priority_queue_clear() argument
279 ds_priority_queue_node_t *pos = queue->nodes; in ds_priority_queue_clear()
280 ds_priority_queue_node_t *end = queue->nodes + queue->size; in ds_priority_queue_clear()
287 queue->size = 0; in ds_priority_queue_clear()
289 reallocate_to_capacity(queue, DS_PRIORITY_QUEUE_MIN_CAPACITY); in ds_priority_queue_clear()
292 void ds_priority_queue_free(ds_priority_queue_t *queue) in ds_priority_queue_free() argument
294 ds_priority_queue_clear(queue); in ds_priority_queue_free()
295 efree(queue->nodes); in ds_priority_queue_free()
296 efree(queue); in ds_priority_queue_free()
