diff options
Diffstat (limited to 'src/libmowgli/container/queue.c')
| -rw-r--r-- | src/libmowgli/container/queue.c | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/src/libmowgli/container/queue.c b/src/libmowgli/container/queue.c new file mode 100644 index 0000000..39150d3 --- /dev/null +++ b/src/libmowgli/container/queue.c @@ -0,0 +1,231 @@ +/* + * libmowgli: A collection of useful routines for programming. + * queue.c: Double-ended queues, also known as deque. + * + * Copyright (c) 2007 William Pitcock <nenolod -at- sacredspiral.co.uk> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice is present in all copies. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mowgli.h" + +static mowgli_heap_t *mowgli_queue_heap = NULL; + +void +mowgli_queue_bootstrap(void) +{ + mowgli_queue_heap = mowgli_heap_create(sizeof(mowgli_queue_t), 256, BH_NOW); + + if (mowgli_queue_heap == NULL) + mowgli_log("mowgli_queue_heap was not created, expect problems."); +} + +mowgli_queue_t * +mowgli_queue_shift(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + return_val_if_fail(head != NULL, NULL); + + out->next = head; + out->data = data; + + if (head != NULL) + { + out->prev = head->prev; + + if (out->prev != NULL) + out->prev->next = out; + + head->prev = out; + } + + return out; +} + +mowgli_queue_t * +mowgli_queue_push(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *out = mowgli_heap_alloc(mowgli_queue_heap); + + return_val_if_fail(head != NULL, NULL); + + out->prev = head; + out->data = data; + + if (head != NULL) + head->next = out; + + return out; +} + +mowgli_queue_t * +mowgli_queue_remove(mowgli_queue_t *head) +{ + mowgli_queue_t *out; + + return_val_if_fail(head != NULL, NULL); + + if (head->prev != NULL) + head->prev->next = head->next; + + if (head->next != NULL) + head->next->prev = head->prev; + + out = head->prev != NULL ? head->prev : head->next; + + mowgli_heap_free(mowgli_queue_heap, head); + + return out; +} + +mowgli_queue_t * +mowgli_queue_find(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n; + + return_val_if_fail(head != NULL, NULL); + + for (n = head; n != NULL; n = n->next) + if (n->data == data) + return n; + + return NULL; +} + +mowgli_queue_t * +mowgli_queue_remove_data(mowgli_queue_t *head, void *data) +{ + mowgli_queue_t *n = mowgli_queue_find(head, data); + + return_val_if_fail(head != NULL, NULL); + + if (n != NULL) + return mowgli_queue_remove(n); + + return NULL; +} + +void +mowgli_queue_destroy(mowgli_queue_t *head) +{ + mowgli_queue_t *n, *n2; + + return_if_fail(head != NULL); + + for (n = head, n2 = n ? n->next : NULL; n != NULL; n = n2, n2 = n ? n->next : NULL) + mowgli_queue_remove(n); +} + +mowgli_queue_t * +mowgli_queue_skip(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + return_val_if_fail(head != NULL, NULL); + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->next, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_rewind(mowgli_queue_t *head, int nodes) +{ + mowgli_queue_t *n; + int iter; + + return_val_if_fail(head != NULL, NULL); + + for (iter = 0, n = head; n != NULL && iter < nodes; n = n->prev, iter++); + + return n; +} + +mowgli_queue_t * +mowgli_queue_head(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + return_val_if_fail(n != NULL, NULL); + + for (tn = n; tn != NULL && tn->prev != NULL; tn = tn->prev); + + return tn; +} + +mowgli_queue_t * +mowgli_queue_tail(mowgli_queue_t *n) +{ + mowgli_queue_t *tn; + + return_val_if_fail(n != NULL, NULL); + + for (tn = n; tn != NULL && tn->next != NULL; tn = tn->next); + + return tn; +} + +void * +mowgli_queue_pop_head(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->next; + + mowgli_queue_remove(tn); + + return out; +} + +void * +mowgli_queue_pop_tail(mowgli_queue_t **n) +{ + mowgli_queue_t *tn; + void *out; + + return_val_if_fail(n != NULL, NULL); + return_val_if_fail(*n != NULL, NULL); + + tn = *n; + out = tn->data; + *n = tn->prev; + + mowgli_queue_remove(tn); + + return out; +} + +int +mowgli_queue_length(mowgli_queue_t *head) +{ + int iter; + mowgli_queue_t *n; + + return_val_if_fail(head != NULL, -1); + + for (n = head, iter = 0; n != NULL; n = n->next, iter++); + + return iter; +} |