From 754414b451c4ca93d139f61b82bacfa81d236a04 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Sun, 21 Jun 2020 16:26:28 -0400 Subject: Move double ended queue files to own directory --- collections/double_ended_queue.adoc | 527 --------------------- collections/double_ended_queue.c | 441 ----------------- collections/double_ended_queue.h | 43 -- .../double_ended_queue/double_ended_queue.adoc | 527 +++++++++++++++++++++ .../double_ended_queue/double_ended_queue.c | 441 +++++++++++++++++ .../double_ended_queue/double_ended_queue.h | 43 ++ 6 files changed, 1011 insertions(+), 1011 deletions(-) delete mode 100644 collections/double_ended_queue.adoc delete mode 100644 collections/double_ended_queue.c delete mode 100644 collections/double_ended_queue.h create mode 100644 collections/double_ended_queue/double_ended_queue.adoc create mode 100644 collections/double_ended_queue/double_ended_queue.c create mode 100644 collections/double_ended_queue/double_ended_queue.h diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc deleted file mode 100644 index c5a1323..0000000 --- a/collections/double_ended_queue.adoc +++ /dev/null @@ -1,527 +0,0 @@ -Double Ended Queue -================== -Tucker Evans -v1.0, 2020-06-10 - -A double ended queue implemented in a circular buffer. - -NOTE: There is currently no way to distinquish between a failed retrieval -(pop_front, index, back, etc.) and returning a NULL value. Keep this in mind if -you plan on storing NULL values in the queue, there are plans to fix this in -the future. - -Types ------ - -+deq+ -~~~~~ -This structure holds all internal information regarding a double ended queue. -All functions (except constructors) expect a pointer to this struct as their -first parameter. - -Functions ---------- - -+deq* deq_new()+ -~~~~~~~~~~~~~~~~ -Constructs an empty double ended queue. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_new(); ----- - -`deq* deq_with_capacity(int capacity)` -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Constructs an empty double ended queue with space for +capacity+ items. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_with_capacity(16); ----- - -+int deq_size(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the number of elements in queue +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_new(); -assert(deq_size(queue) == 0); -deq_push_back(queue, NULL); -assert(deq_size(queue) == 1); ----- - -+int deq_capacity(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the maximun number of elements in queue +self+ before the buffer needs -to be resized. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_with_capacity(16); -assert(deq_capacity(queue) == 16); ----- - -+deq* deq_cp(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~ -Returns a copy of the queue +self+. -All elements are kept in the same order however the placement in the buffer may -change. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_with_capacity(16); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -deq *new = deq_cp(queue); -assert(strcmp(deq_pop_back, str2) == 0); -assert(strcmp(deq_pop_back, str1) == 0); ----- - -+void deq_free(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~ -Frees all internal memory and +self+. - -NOTE: All item pointers are still valid after a call to +deq_free+, deq_clear -should be called before if they are no longer needed to avoid memory leaks. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_new(); -deq_free(queue); ----- - -+void deq_clear(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Free all elements within queue +self+, and sets queue to empty (size 0). - -NOTE: Does not free internal memory of +self+ or +self+ itself, if this is desired +deq_free()+ should be called immediatly after this. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -deq_clear(queue); -assert(deq_size(queue) == 0); -deq_free(queue); ----- - -+void deq_push_front(deq *self, void *item)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Pushes +item+ into front of +self+. This may cause a resize of internal buffer. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_new(); -deq_push_front(queue, NULL); -assert(deq_size(queue) == 1); ----- - -+void deq_push_back(deq *self, void *item)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Pushes +item+ into back of +self+. This may cause a resize of internal buffer. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_new(); -deq_push_back(queue, NULL); -assert(deq_size(queue) == 1); ----- - -+void deq_set(deq *self, int index, void *item)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Sets the element at position +index+ in +self+ to +item+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -deq_set(queue, 0, str2); - -assert(str_cmp(deq_pop_back(queue), str2) == 0); -assert(str_cmp(deq_pop_back(queue), str2) == 0); ----- - -+void deq_insert(deq *self, int index, void *item)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Inserts +item+ into queue +self+ at index +index+, all items after the index -are pushed toward the end. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -deq_insert(queue, 1, str_dup(str3)); - -assert(str_cmp(deq_index(queue, 1), str3) == 0); -assert(str_cmp(deq_index(queue, 2), str2) == 0); ----- - -+void* deq_pop_front(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Pops an item off of the front of the queue +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -assert(str_cmp(deq_pop_front(queue), str1) == 0); -assert(str_cmp(deq_pop_front(queue), str2) == 0); ----- - -+void* deq_pop_back(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Pops an item off of the back of the queue +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -assert(str_cmp(deq_pop_back(queue), str2) == 0); -assert(str_cmp(deq_pop_back(queue), str1) == 0); ----- - -+void* deq_index(deq *self, int index)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the element at position +index+ of +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -assert(str_cmp(deq_index(queue, 1), str2) == 0); ----- - -+void* deq_front(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the element at the front of the queue +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -assert(strcmp(deq_front(queue), str1) == 0); ----- - -+void* deq_back(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the element at the back of the queue +self+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -assert(strcmp(deq_back(queue), str2) == 0); ----- - -+void deq_swap(deq *self, int i, int j)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Swaps elements at positions +i+ and +j+, does nothing if +i+ or +j+ are out of -bounds. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); - -deq_swap(queue, 0, 1); - -assert(str_cmp(deq_front(queue), str2) == 0); -assert(str_cmp(deq_back(queue), str1) == 0); ----- - -+void* deq_swap_rm_front(deq *self, int index)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Swaps front element with item at +index+, and pops item now at front. -Does not keep order of elements, but faster that +deq_remove()+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -assert(str_cmp(deq_swap_front(queue, 2), str3) == 0); -assert(str_cmp(deq_front(queue, str2) == 0); -assert(deq_size == 2); ----- - -+void* deq_swap_rm_back(deq *self, int index)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Swaps back element with item at +index+, and pops item now at back. -Will return same element as +deq_remove(self, index)+. -Does not keep order of elements, but faster that +deq_remove()+. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -assert(str_cmp(deq_swap_rm_back(queue, 2), str3) == 0); -assert(str_cmp(deq_back(queue, str2) == 0); -assert(deq_size == 2); ----- - -+void deq_truncate(deq *self, int size)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Truncates queue +self+ to +size+ elements, elements in positions > +size+ will -no longer be accessable through +self+. Does nothing if +size+ > current number -of elements. NOTE: Does not currently reduce memory footprint - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -deq_truncate(queue, 1); - -assert(deq_size == 1); ----- - -+void deq_reserve(deq *self, int additional)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Reserves space for +additional+ items. May reserve more memory to avoid too -many reallocations. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" - -deq *queue = deq_with_capacity(16); - -deq_reserve(queue, 20); -assert(deq_capacity(queue) >= 20); ----- - -+void deq_remove(deq *self, int index)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Element at position +index+ of +self+ is removed from queue and the remaining -items are shifted towards the front. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -deq_remove(queue, 1); - -assert(deq_size == 2); -assert(strcmp(deq_front(queue), str1) == 0); -assert(strcmp(deq_back(queue), str3) == 0); ----- - -+void deq_print(deq *self, (char* to_string(void*)))+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Prints out the contents of the queue +self+ to +stdout+ (surounded by square brackets and separated by commas ','). +to_string+ is a -function that takes a pointer to the type of elements stored in +self+ and -returns a string representation. - -Examples -^^^^^^^^ -[source,c] ----- -#include "double_ended_queue.h" -#include - -char* to_string(str) -void *str; -{ - return str; -} - -int main() -{ -char *str1 = "ONE"; -char *str2 = "TWO"; -char *str3 = "THREE"; - -deq *queue = deq_new(); -deq_push_back(queue, str_dup(str1)); -deq_push_back(queue, str_dup(str2)); -deq_push_back(queue, str_dup(str3)); - -printf("DEQ CONTENTS:\n\t") -deq_print(queue, to_string) -} ----- - -Output: ----- -DEQ_CONTENTS: - [ONE,TWO,THREE] ----- diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c deleted file mode 100644 index 015b90b..0000000 --- a/collections/double_ended_queue.c +++ /dev/null @@ -1,441 +0,0 @@ -#include "double_ended_queue.h" -#include -#include -#include - -#include - -/*Checks bounds for index (y) in queue*/ -#define DEQ_IN_BOUNDS(x, y) (y < deq_size(x)) \ - -#define START_SIZE 64; - -/*TODO add returned error codes for current void functions - * (resize, push, etc.) - * - * Should all functions return a status code and take in a dest argument? - */ - -/* Double ended queue as a circular buffer - * base is pointer to buffer. - * beg: postiton of the first element is stored. - * end: position for the next element to be stored. - * limit: the maximum number of elements. - */ - -struct double_ended_queue { - void **base; - int beg, end, limit; -}; - -deq* deq_new() -{ - deq *root; - - root = malloc(sizeof(deq)); - assert(root); - - root->limit = START_SIZE; - root->beg = root->end = 0; - root->base = malloc(root->limit * sizeof(void*)); - assert(root->base); - - return root; -} - -deq* deq_with_capacity(n) -int n; -{ - deq *root; - - root = malloc(sizeof(deq)); - assert(root); - - root->limit = n; - root->beg = root->end = 0; - root->base = malloc(root->limit * sizeof(void*)); - assert(root->base); - - return root; -} - -int deq_size(root) -deq *root; -{ - if (!root) - return -1; - - if (root->beg <= root->end) - return (root->end - root->beg); - - return (root->limit - root->beg) + (root->end); -} - -int deq_capacity(root) -deq *root; -{ - if (!root) { - return -1; - } else { - return root->limit; - } -} - -void deq_resize(root) -deq *root; -{ - void **tmp; - int size; - - tmp = malloc(root->limit * 2 * sizeof(void*)); - assert(tmp); - - if (root->beg <= root->end) { - tmp = memcpy(tmp, root->base + root->beg, - deq_size(root) * sizeof(void*)); - } else { - /*copy beg<->limit*/ - size = root->limit - root->beg; - tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*)); - assert(tmp); - - /*copy base<->end*/ - tmp = memcpy(tmp + size, root->base, - root->end * sizeof(void*)); - assert(tmp); - } - - root->limit *= 2; - - free(root->base); - root->base = tmp; -} - -void* deq_index(root, index) -deq *root; -int index; -{ - void **tmp; - - if (!root || !DEQ_IN_BOUNDS(root,index)) - return NULL; - - return root->base[(root->beg + index) % root->limit]; -} - -void deq_push_front(root, item) -deq *root; -void *item; -{ - void **tmp; - - if (!root) - return; - - if (root->end >= root->limit) - deq_resize(root); - - --root->beg; - root->beg %= root->limit; - - root->base[root->beg] = item; - - if (root->end == root->beg) - root->end = root->limit; -} - -void deq_push_back(root, item) -deq *root; -void *item; -{ - void **tmp; - - if (!root) - return; - - if (root->end >= root->limit) - deq_resize(root); - - root->base[root->end++] = item; - root->end %= root->limit; - - if (root->end == root->beg) - root->end = root->limit; -} - -void deq_set(root, index, item) -deq *root; -int index; -void *item; -{ - if (!root || !DEQ_IN_BOUNDS(root, index)) - return; - root->base[(root->beg + index) % root->limit] = item; -} - -void deq_insert(root, index, item) -deq *root; -int index; -void *item; -{ - if (!root) - return; - - if (index > deq_size(root)) - return; - - if (root->end >= root->limit) - deq_resize(root); - - index = (root->beg + index) % root->limit; - - if (root->beg < root->end) { - memmove(root->base + index + 1, root->base + index, - (root->end - index) * sizeof(void*)); - ++root->end; - root->end = root->end % root->limit; - } else if (index < root->end) { - memmove(root->base + index + 1, - root->base + index, - (root->end - index) * sizeof(void*)); - ++root->end; - } else { - memmove(root->base + root->beg - 1, root->base + root->beg, - (index - root->beg) * sizeof(void*)); - --root->beg; - } - - if (root->end == root->beg) - root->end = root->limit; - - root->base[index] = item; -} - -void* deq_pop_front(root) -deq *root; -{ - void* tmp; - if (!root || root->beg == root->end) - return NULL; - - tmp = root->base[root->beg]; - - ++root->beg; - root->beg %= root->limit; - - return tmp; -} - -void* deq_pop_back(root) -deq *root; -{ - if (!root || root->end == root->beg) - return NULL; - - --root->end; - root->end %= root->limit; - - return root->base[root->end]; -} - -void* deq_swap_rm_front(root, index) -deq *root; -int index; -{ - if (!root || !DEQ_IN_BOUNDS(root,index)) - return NULL; - - deq_swap(root, 0, index); - return deq_pop_front(root); -} - -void* deq_swap_rm_back(root, index) -deq *root; -int index; -{ - if (!root || !DEQ_IN_BOUNDS(root,index)) - return NULL; - - deq_swap(root,deq_size(root) - 1,index); - return deq_pop_back(root); -} - -void deq_swap(root, i, j) -deq *root; -int i, j; -{ - int len; - void *tmp; - - if (!root) - return; - - len = deq_size(root); - - if (i >= len || j >= len) - return; - - i += root->beg; - i %= root->limit; - - j += root->beg; - j %= root->limit; - - tmp = root->base[i]; - root->base[i] = root->base[j]; - root->base[j] = tmp; -} - -void deq_remove(root, index) -deq *root; -int index; -{ - if (!root || !DEQ_IN_BOUNDS(root,index)); - return; - - index = (root->beg + index) % root->limit; - - root->base[index] = NULL; - - if (root->beg < root->end || index >= root->beg) { - memmove(root->base + root->beg + 1, - root->base + root->beg, - (index - root->beg) * sizeof(void*)); - ++root->beg; - } else { - memmove(root->base + index, root->base + index + 1, - (--root->end - index) * sizeof(void*)); - } -} - -/* Note: Elements are not freed - * deq_clear should be called before if they are no longer needed. - */ -void deq_free(root) -deq *root; -{ - free(root->base); - root->base = NULL; - - free(root); -} - -void deq_clear(root) -deq *root; -{ - int i, size; - - size = deq_size(root); - for (i = 0; i < size; i++) { - free(deq_index(root, i)); - } -} - -void deq_print(root, to_string) -deq *root; -char* to_string(void*); -{ - int i, size;; - - size = deq_size(root); - - printf("["); - for (i = 0; i < size; i++) { - printf("%s,", to_string(deq_index(root, i))); - } - printf("\b]\n"); -} - -void deq_debug_print(root) -deq *root; -{ - void **tmp; - - fprintf(stderr, "VEC[b: %p, beg: %d, end:%d]:\n\t ", - root->base, root->beg, root->end); - for (tmp = root->base; tmp < root->base + root->limit; tmp++){ - fprintf(stderr, "[%p]", *tmp); - } - fprintf(stderr, "\n"); -} - -deq* deq_cp(root) -deq *root; -{ - deq *copy; - - copy = deq_with_capacity(root->limit); - assert(copy->base); - - copy->base = memcpy(copy->base, root->base, - root->limit * sizeof(void*)); - assert(copy->base); - - copy->beg = root->beg; - copy->end = root->end; - - return copy; -} - -/*Note: Does not currently reduce memory footprint*/ -void deq_truncate(root, size) -deq *root; -int size; -{ - if (!root || size > deq_size(root)) - return; - - root->end = (root->beg + size) % root->limit; -} - -void* deq_front(root) -deq *root; -{ - if (!root) - return NULL; - - return root->base[root->beg]; -} - -void* deq_back(root) -deq *root; -{ - if (!root) - return NULL; - - return root->base[(root->end - 1) % root->limit]; -} - -void deq_reserve(root, size) -deq *root; -int size; -{ - void **tmp; - int i, cur_size; - - cur_size = deq_size(root); - for (i = root->limit; i - cur_size < size; i*=2); - - tmp = malloc(i * sizeof(void*)); - assert(tmp); - - if (root->beg <= root->end) { - tmp = memcpy(tmp, root->base + root->beg, - deq_size(root) * sizeof(void*)); - } else { - /*copy beg<->limit*/ - size = root->limit - root->beg; - tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*)); - assert(tmp); - - /*copy base<->end*/ - tmp = memcpy(tmp + size, root->base, - root->end * sizeof(void*)); - assert(tmp); - } - - root->limit *= 2; - - free(root->base); - root->base = tmp; -} diff --git a/collections/double_ended_queue.h b/collections/double_ended_queue.h deleted file mode 100644 index 6448c8a..0000000 --- a/collections/double_ended_queue.h +++ /dev/null @@ -1,43 +0,0 @@ -#ifndef VECTOR_H -#define VECTOR_H - -typedef struct double_ended_queue deq; - -/*constructors*/ -deq* deq_new(); -deq* deq_with_capacity(int); - -/*management*/ -int deq_size(deq*); -int deq_capacity(deq*); -deq* deq_cp(deq*); - -/* Note: Elements are not freed - * deq_clear should be called before if they are no longer needed.*/ -void deq_free(deq*); - -/*Free all elements within queue*/ -void deq_clear(deq*); - -/*data*/ -void deq_push_front(deq*, void*); -void deq_push_back(deq*, void*); -void deq_set(deq*, int, void*); -void deq_insert(deq*, int, void*); -void* deq_pop_front(deq*); -void* deq_pop_back(deq*); -void* deq_index(deq*, int); -void* deq_front(deq*); -void* deq_back(deq*); -void* deq_swap_rm_front(deq*, int); -void* deq_swap_rm_back(deq*, int); - -void deq_swap(deq*, int, int); - -/*Note: Does not currently reduce memory footprint*/ -void deq_truncate(deq*, int); -void deq_reserve(deq*, int); - -void deq_remove(deq*, int); -void deq_print(deq*, char* (void*)); -#endif diff --git a/collections/double_ended_queue/double_ended_queue.adoc b/collections/double_ended_queue/double_ended_queue.adoc new file mode 100644 index 0000000..c5a1323 --- /dev/null +++ b/collections/double_ended_queue/double_ended_queue.adoc @@ -0,0 +1,527 @@ +Double Ended Queue +================== +Tucker Evans +v1.0, 2020-06-10 + +A double ended queue implemented in a circular buffer. + +NOTE: There is currently no way to distinquish between a failed retrieval +(pop_front, index, back, etc.) and returning a NULL value. Keep this in mind if +you plan on storing NULL values in the queue, there are plans to fix this in +the future. + +Types +----- + ++deq+ +~~~~~ +This structure holds all internal information regarding a double ended queue. +All functions (except constructors) expect a pointer to this struct as their +first parameter. + +Functions +--------- + ++deq* deq_new()+ +~~~~~~~~~~~~~~~~ +Constructs an empty double ended queue. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_new(); +---- + +`deq* deq_with_capacity(int capacity)` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Constructs an empty double ended queue with space for +capacity+ items. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_with_capacity(16); +---- + ++int deq_size(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the number of elements in queue +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_new(); +assert(deq_size(queue) == 0); +deq_push_back(queue, NULL); +assert(deq_size(queue) == 1); +---- + ++int deq_capacity(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the maximun number of elements in queue +self+ before the buffer needs +to be resized. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_with_capacity(16); +assert(deq_capacity(queue) == 16); +---- + ++deq* deq_cp(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~ +Returns a copy of the queue +self+. +All elements are kept in the same order however the placement in the buffer may +change. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_with_capacity(16); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +deq *new = deq_cp(queue); +assert(strcmp(deq_pop_back, str2) == 0); +assert(strcmp(deq_pop_back, str1) == 0); +---- + ++void deq_free(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~ +Frees all internal memory and +self+. + +NOTE: All item pointers are still valid after a call to +deq_free+, deq_clear +should be called before if they are no longer needed to avoid memory leaks. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_new(); +deq_free(queue); +---- + ++void deq_clear(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Free all elements within queue +self+, and sets queue to empty (size 0). + +NOTE: Does not free internal memory of +self+ or +self+ itself, if this is desired +deq_free()+ should be called immediatly after this. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +deq_clear(queue); +assert(deq_size(queue) == 0); +deq_free(queue); +---- + ++void deq_push_front(deq *self, void *item)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Pushes +item+ into front of +self+. This may cause a resize of internal buffer. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_new(); +deq_push_front(queue, NULL); +assert(deq_size(queue) == 1); +---- + ++void deq_push_back(deq *self, void *item)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Pushes +item+ into back of +self+. This may cause a resize of internal buffer. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_new(); +deq_push_back(queue, NULL); +assert(deq_size(queue) == 1); +---- + ++void deq_set(deq *self, int index, void *item)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Sets the element at position +index+ in +self+ to +item+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +deq_set(queue, 0, str2); + +assert(str_cmp(deq_pop_back(queue), str2) == 0); +assert(str_cmp(deq_pop_back(queue), str2) == 0); +---- + ++void deq_insert(deq *self, int index, void *item)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Inserts +item+ into queue +self+ at index +index+, all items after the index +are pushed toward the end. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +deq_insert(queue, 1, str_dup(str3)); + +assert(str_cmp(deq_index(queue, 1), str3) == 0); +assert(str_cmp(deq_index(queue, 2), str2) == 0); +---- + ++void* deq_pop_front(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Pops an item off of the front of the queue +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +assert(str_cmp(deq_pop_front(queue), str1) == 0); +assert(str_cmp(deq_pop_front(queue), str2) == 0); +---- + ++void* deq_pop_back(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Pops an item off of the back of the queue +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +assert(str_cmp(deq_pop_back(queue), str2) == 0); +assert(str_cmp(deq_pop_back(queue), str1) == 0); +---- + ++void* deq_index(deq *self, int index)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the element at position +index+ of +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +assert(str_cmp(deq_index(queue, 1), str2) == 0); +---- + ++void* deq_front(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the element at the front of the queue +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +assert(strcmp(deq_front(queue), str1) == 0); +---- + ++void* deq_back(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the element at the back of the queue +self+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +assert(strcmp(deq_back(queue), str2) == 0); +---- + ++void deq_swap(deq *self, int i, int j)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Swaps elements at positions +i+ and +j+, does nothing if +i+ or +j+ are out of +bounds. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); + +deq_swap(queue, 0, 1); + +assert(str_cmp(deq_front(queue), str2) == 0); +assert(str_cmp(deq_back(queue), str1) == 0); +---- + ++void* deq_swap_rm_front(deq *self, int index)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Swaps front element with item at +index+, and pops item now at front. +Does not keep order of elements, but faster that +deq_remove()+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +assert(str_cmp(deq_swap_front(queue, 2), str3) == 0); +assert(str_cmp(deq_front(queue, str2) == 0); +assert(deq_size == 2); +---- + ++void* deq_swap_rm_back(deq *self, int index)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Swaps back element with item at +index+, and pops item now at back. +Will return same element as +deq_remove(self, index)+. +Does not keep order of elements, but faster that +deq_remove()+. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +assert(str_cmp(deq_swap_rm_back(queue, 2), str3) == 0); +assert(str_cmp(deq_back(queue, str2) == 0); +assert(deq_size == 2); +---- + ++void deq_truncate(deq *self, int size)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Truncates queue +self+ to +size+ elements, elements in positions > +size+ will +no longer be accessable through +self+. Does nothing if +size+ > current number +of elements. NOTE: Does not currently reduce memory footprint + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +deq_truncate(queue, 1); + +assert(deq_size == 1); +---- + ++void deq_reserve(deq *self, int additional)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Reserves space for +additional+ items. May reserve more memory to avoid too +many reallocations. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" + +deq *queue = deq_with_capacity(16); + +deq_reserve(queue, 20); +assert(deq_capacity(queue) >= 20); +---- + ++void deq_remove(deq *self, int index)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Element at position +index+ of +self+ is removed from queue and the remaining +items are shifted towards the front. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +deq_remove(queue, 1); + +assert(deq_size == 2); +assert(strcmp(deq_front(queue), str1) == 0); +assert(strcmp(deq_back(queue), str3) == 0); +---- + ++void deq_print(deq *self, (char* to_string(void*)))+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Prints out the contents of the queue +self+ to +stdout+ (surounded by square brackets and separated by commas ','). +to_string+ is a +function that takes a pointer to the type of elements stored in +self+ and +returns a string representation. + +Examples +^^^^^^^^ +[source,c] +---- +#include "double_ended_queue.h" +#include + +char* to_string(str) +void *str; +{ + return str; +} + +int main() +{ +char *str1 = "ONE"; +char *str2 = "TWO"; +char *str3 = "THREE"; + +deq *queue = deq_new(); +deq_push_back(queue, str_dup(str1)); +deq_push_back(queue, str_dup(str2)); +deq_push_back(queue, str_dup(str3)); + +printf("DEQ CONTENTS:\n\t") +deq_print(queue, to_string) +} +---- + +Output: +---- +DEQ_CONTENTS: + [ONE,TWO,THREE] +---- diff --git a/collections/double_ended_queue/double_ended_queue.c b/collections/double_ended_queue/double_ended_queue.c new file mode 100644 index 0000000..015b90b --- /dev/null +++ b/collections/double_ended_queue/double_ended_queue.c @@ -0,0 +1,441 @@ +#include "double_ended_queue.h" +#include +#include +#include + +#include + +/*Checks bounds for index (y) in queue*/ +#define DEQ_IN_BOUNDS(x, y) (y < deq_size(x)) \ + +#define START_SIZE 64; + +/*TODO add returned error codes for current void functions + * (resize, push, etc.) + * + * Should all functions return a status code and take in a dest argument? + */ + +/* Double ended queue as a circular buffer + * base is pointer to buffer. + * beg: postiton of the first element is stored. + * end: position for the next element to be stored. + * limit: the maximum number of elements. + */ + +struct double_ended_queue { + void **base; + int beg, end, limit; +}; + +deq* deq_new() +{ + deq *root; + + root = malloc(sizeof(deq)); + assert(root); + + root->limit = START_SIZE; + root->beg = root->end = 0; + root->base = malloc(root->limit * sizeof(void*)); + assert(root->base); + + return root; +} + +deq* deq_with_capacity(n) +int n; +{ + deq *root; + + root = malloc(sizeof(deq)); + assert(root); + + root->limit = n; + root->beg = root->end = 0; + root->base = malloc(root->limit * sizeof(void*)); + assert(root->base); + + return root; +} + +int deq_size(root) +deq *root; +{ + if (!root) + return -1; + + if (root->beg <= root->end) + return (root->end - root->beg); + + return (root->limit - root->beg) + (root->end); +} + +int deq_capacity(root) +deq *root; +{ + if (!root) { + return -1; + } else { + return root->limit; + } +} + +void deq_resize(root) +deq *root; +{ + void **tmp; + int size; + + tmp = malloc(root->limit * 2 * sizeof(void*)); + assert(tmp); + + if (root->beg <= root->end) { + tmp = memcpy(tmp, root->base + root->beg, + deq_size(root) * sizeof(void*)); + } else { + /*copy beg<->limit*/ + size = root->limit - root->beg; + tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*)); + assert(tmp); + + /*copy base<->end*/ + tmp = memcpy(tmp + size, root->base, + root->end * sizeof(void*)); + assert(tmp); + } + + root->limit *= 2; + + free(root->base); + root->base = tmp; +} + +void* deq_index(root, index) +deq *root; +int index; +{ + void **tmp; + + if (!root || !DEQ_IN_BOUNDS(root,index)) + return NULL; + + return root->base[(root->beg + index) % root->limit]; +} + +void deq_push_front(root, item) +deq *root; +void *item; +{ + void **tmp; + + if (!root) + return; + + if (root->end >= root->limit) + deq_resize(root); + + --root->beg; + root->beg %= root->limit; + + root->base[root->beg] = item; + + if (root->end == root->beg) + root->end = root->limit; +} + +void deq_push_back(root, item) +deq *root; +void *item; +{ + void **tmp; + + if (!root) + return; + + if (root->end >= root->limit) + deq_resize(root); + + root->base[root->end++] = item; + root->end %= root->limit; + + if (root->end == root->beg) + root->end = root->limit; +} + +void deq_set(root, index, item) +deq *root; +int index; +void *item; +{ + if (!root || !DEQ_IN_BOUNDS(root, index)) + return; + root->base[(root->beg + index) % root->limit] = item; +} + +void deq_insert(root, index, item) +deq *root; +int index; +void *item; +{ + if (!root) + return; + + if (index > deq_size(root)) + return; + + if (root->end >= root->limit) + deq_resize(root); + + index = (root->beg + index) % root->limit; + + if (root->beg < root->end) { + memmove(root->base + index + 1, root->base + index, + (root->end - index) * sizeof(void*)); + ++root->end; + root->end = root->end % root->limit; + } else if (index < root->end) { + memmove(root->base + index + 1, + root->base + index, + (root->end - index) * sizeof(void*)); + ++root->end; + } else { + memmove(root->base + root->beg - 1, root->base + root->beg, + (index - root->beg) * sizeof(void*)); + --root->beg; + } + + if (root->end == root->beg) + root->end = root->limit; + + root->base[index] = item; +} + +void* deq_pop_front(root) +deq *root; +{ + void* tmp; + if (!root || root->beg == root->end) + return NULL; + + tmp = root->base[root->beg]; + + ++root->beg; + root->beg %= root->limit; + + return tmp; +} + +void* deq_pop_back(root) +deq *root; +{ + if (!root || root->end == root->beg) + return NULL; + + --root->end; + root->end %= root->limit; + + return root->base[root->end]; +} + +void* deq_swap_rm_front(root, index) +deq *root; +int index; +{ + if (!root || !DEQ_IN_BOUNDS(root,index)) + return NULL; + + deq_swap(root, 0, index); + return deq_pop_front(root); +} + +void* deq_swap_rm_back(root, index) +deq *root; +int index; +{ + if (!root || !DEQ_IN_BOUNDS(root,index)) + return NULL; + + deq_swap(root,deq_size(root) - 1,index); + return deq_pop_back(root); +} + +void deq_swap(root, i, j) +deq *root; +int i, j; +{ + int len; + void *tmp; + + if (!root) + return; + + len = deq_size(root); + + if (i >= len || j >= len) + return; + + i += root->beg; + i %= root->limit; + + j += root->beg; + j %= root->limit; + + tmp = root->base[i]; + root->base[i] = root->base[j]; + root->base[j] = tmp; +} + +void deq_remove(root, index) +deq *root; +int index; +{ + if (!root || !DEQ_IN_BOUNDS(root,index)); + return; + + index = (root->beg + index) % root->limit; + + root->base[index] = NULL; + + if (root->beg < root->end || index >= root->beg) { + memmove(root->base + root->beg + 1, + root->base + root->beg, + (index - root->beg) * sizeof(void*)); + ++root->beg; + } else { + memmove(root->base + index, root->base + index + 1, + (--root->end - index) * sizeof(void*)); + } +} + +/* Note: Elements are not freed + * deq_clear should be called before if they are no longer needed. + */ +void deq_free(root) +deq *root; +{ + free(root->base); + root->base = NULL; + + free(root); +} + +void deq_clear(root) +deq *root; +{ + int i, size; + + size = deq_size(root); + for (i = 0; i < size; i++) { + free(deq_index(root, i)); + } +} + +void deq_print(root, to_string) +deq *root; +char* to_string(void*); +{ + int i, size;; + + size = deq_size(root); + + printf("["); + for (i = 0; i < size; i++) { + printf("%s,", to_string(deq_index(root, i))); + } + printf("\b]\n"); +} + +void deq_debug_print(root) +deq *root; +{ + void **tmp; + + fprintf(stderr, "VEC[b: %p, beg: %d, end:%d]:\n\t ", + root->base, root->beg, root->end); + for (tmp = root->base; tmp < root->base + root->limit; tmp++){ + fprintf(stderr, "[%p]", *tmp); + } + fprintf(stderr, "\n"); +} + +deq* deq_cp(root) +deq *root; +{ + deq *copy; + + copy = deq_with_capacity(root->limit); + assert(copy->base); + + copy->base = memcpy(copy->base, root->base, + root->limit * sizeof(void*)); + assert(copy->base); + + copy->beg = root->beg; + copy->end = root->end; + + return copy; +} + +/*Note: Does not currently reduce memory footprint*/ +void deq_truncate(root, size) +deq *root; +int size; +{ + if (!root || size > deq_size(root)) + return; + + root->end = (root->beg + size) % root->limit; +} + +void* deq_front(root) +deq *root; +{ + if (!root) + return NULL; + + return root->base[root->beg]; +} + +void* deq_back(root) +deq *root; +{ + if (!root) + return NULL; + + return root->base[(root->end - 1) % root->limit]; +} + +void deq_reserve(root, size) +deq *root; +int size; +{ + void **tmp; + int i, cur_size; + + cur_size = deq_size(root); + for (i = root->limit; i - cur_size < size; i*=2); + + tmp = malloc(i * sizeof(void*)); + assert(tmp); + + if (root->beg <= root->end) { + tmp = memcpy(tmp, root->base + root->beg, + deq_size(root) * sizeof(void*)); + } else { + /*copy beg<->limit*/ + size = root->limit - root->beg; + tmp = memcpy(tmp, root->base + root->beg, size * sizeof(void*)); + assert(tmp); + + /*copy base<->end*/ + tmp = memcpy(tmp + size, root->base, + root->end * sizeof(void*)); + assert(tmp); + } + + root->limit *= 2; + + free(root->base); + root->base = tmp; +} diff --git a/collections/double_ended_queue/double_ended_queue.h b/collections/double_ended_queue/double_ended_queue.h new file mode 100644 index 0000000..6448c8a --- /dev/null +++ b/collections/double_ended_queue/double_ended_queue.h @@ -0,0 +1,43 @@ +#ifndef VECTOR_H +#define VECTOR_H + +typedef struct double_ended_queue deq; + +/*constructors*/ +deq* deq_new(); +deq* deq_with_capacity(int); + +/*management*/ +int deq_size(deq*); +int deq_capacity(deq*); +deq* deq_cp(deq*); + +/* Note: Elements are not freed + * deq_clear should be called before if they are no longer needed.*/ +void deq_free(deq*); + +/*Free all elements within queue*/ +void deq_clear(deq*); + +/*data*/ +void deq_push_front(deq*, void*); +void deq_push_back(deq*, void*); +void deq_set(deq*, int, void*); +void deq_insert(deq*, int, void*); +void* deq_pop_front(deq*); +void* deq_pop_back(deq*); +void* deq_index(deq*, int); +void* deq_front(deq*); +void* deq_back(deq*); +void* deq_swap_rm_front(deq*, int); +void* deq_swap_rm_back(deq*, int); + +void deq_swap(deq*, int, int); + +/*Note: Does not currently reduce memory footprint*/ +void deq_truncate(deq*, int); +void deq_reserve(deq*, int); + +void deq_remove(deq*, int); +void deq_print(deq*, char* (void*)); +#endif -- cgit v1.1