1 #ifndef DS_PRIORITY_QUEUE_H 2 #define DS_PRIORITY_QUEUE_H 3 4 #include "../common.h" 5 6 typedef struct _ds_priority_queue_node_t { 7 zval value; 8 zval priority; 9 } ds_priority_queue_node_t; 10 11 typedef struct _ds_priority_queue_t { 12 ds_priority_queue_node_t *nodes; 13 uint32_t capacity; 14 uint32_t size; 15 uint32_t next; 16 } ds_priority_queue_t; 17 18 #define DS_PRIORITY_QUEUE_MIN_CAPACITY 8 19 20 #define DS_PRIORITY_QUEUE_FOREACH_NODE(queue, node) \ 21 do { \ 22 ds_priority_queue_t *_queue = queue; \ 23 ds_priority_queue_node_t *_node = &_queue->nodes[0]; \ 24 ds_priority_queue_node_t *_last = &_queue->nodes[queue->size - 1]; \ 25 \ 26 for (; _node <= _last; ++_node) { \ 27 node = _node; 28 29 30 #define DS_PRIORITY_QUEUE_FOREACH_VALUE(queue, value) \ 31 ds_priority_queue_node_t *__node = NULL; \ 32 DS_PRIORITY_QUEUE_FOREACH_NODE(queue, __node) \ 33 value = &__node->value; 34 35 36 #define DS_PRIORITY_QUEUE_FOREACH(queue, value, priority) \ 37 ds_priority_queue_node_t *__node = NULL; \ 38 DS_PRIORITY_QUEUE_FOREACH_NODE(queue, __node) \ 39 value = &__node->value; \ 40 priority = &__node->priority; 41 42 43 #define DS_PRIORITY_QUEUE_FOREACH_END() \ 44 } \ 45 } while (0) \ 46 47 /** 48 * Has to exist because of the uint32_t insertion order stamp. 49 * 50 * @todo this isn't necessary because we can re-index when the stamp == max int 51 */ 52 #define DS_PRIORITY_QUEUE_MAX_CAPACITY (1 << 31) 53 54 #define DS_PRIORITY_QUEUE_SIZE(queue) ((queue)->size) 55 #define DS_PRIORITY_QUEUE_IS_EMPTY(queue) (DS_PRIORITY_QUEUE_SIZE(queue) == 0) 56 57 ds_priority_queue_t *ds_priority_queue(); 58 59 void ds_priority_queue_allocate(ds_priority_queue_t *queue, uint32_t capacity); 60 61 uint32_t ds_priority_queue_capacity(ds_priority_queue_t *queue); 62 63 zval *ds_priority_queue_peek(ds_priority_queue_t *queue); 64 65 void ds_priority_queue_pop(ds_priority_queue_t *queue, zval *return_value); 66 67 void ds_priority_queue_push(ds_priority_queue_t *queue, zval *value, zval *priority); 68 69 void ds_priority_queue_to_array(ds_priority_queue_t *queue, zval *array); 70 71 void ds_priority_queue_free(ds_priority_queue_t *queue); 72 73 void ds_priority_queue_clear(ds_priority_queue_t *queue); 74 75 ds_priority_queue_t *ds_priority_queue_clone(ds_priority_queue_t * queue); 76 77 ds_priority_queue_node_t* ds_priority_queue_create_sorted_buffer(ds_priority_queue_t *queue); 78 79 #endif 80
