diff options
Diffstat (limited to 'collections/double_ended_queue')
| -rw-r--r-- | collections/double_ended_queue/double_ended_queue.adoc | 205 | ||||
| -rw-r--r-- | collections/double_ended_queue/double_ended_queue.c | 277 | ||||
| -rw-r--r-- | collections/double_ended_queue/double_ended_queue.h | 34 |
3 files changed, 262 insertions, 254 deletions
diff --git a/collections/double_ended_queue/double_ended_queue.adoc b/collections/double_ended_queue/double_ended_queue.adoc index 52a085f..50e2b76 100644 --- a/collections/double_ended_queue/double_ended_queue.adoc +++ b/collections/double_ended_queue/double_ended_queue.adoc @@ -1,7 +1,7 @@ Double Ended Queue ================== Tucker Evans -v1.0.1, 2020-06-10 +v1.0.2, 2020-07-06 A double ended queue implemented in a circular buffer. @@ -107,32 +107,15 @@ assert(strcmp(deq_pop_back, str2) == 0); assert(strcmp(deq_pop_back, str1) == 0); ---- -[[deq_free]] -+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_free()+>>, <<deq_clear,+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); ----- - -[[deq_clear]] -+void deq_clear(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Free all elements within queue +self+, and sets queue to empty (size 0). +[[deq_print]] ++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. -NOTE: Does not free internal memory of +self+ or +self+ itself, if this is -desired <<deq_free,+deq_free()+>> should be called immediately after this. +NOTE: Strings are freed after printing, therefore +strdup()+ should be used on +any strings that are not for the sole purpose of printing here. Examples ^^^^^^^^ @@ -141,16 +124,32 @@ Examples #include "double_ended_queue.h" #include <string.h> +char* to_string(str) +void *str; +{ + return strdup(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)); -deq_clear(queue); -assert(deq_size(queue) == 0); -deq_free(queue); +printf("DEQ CONTENTS:\n\t") +deq_print(queue, to_string) +} +---- + +Output: +---- +DEQ_CONTENTS: + [ONE,TWO,THREE] ---- [[deq_push_front]] @@ -185,10 +184,10 @@ deq_push_back(queue, NULL); assert(deq_size(queue) == 1); ---- -[[deq_set]] -+void deq_set(deq *self, int index, void *item)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Sets the element at position +index+ in +self+ to +item+. +[[deq_front]] ++void* deq_front(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the element at the front of the queue +self+. Examples ^^^^^^^^ @@ -204,17 +203,13 @@ 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); +assert(strcmp(deq_front(queue), str1) == 0); ---- -[[deq_insert]] -+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. +[[deq_back]] ++void* deq_back(deq *self)+ +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Returns the element at the back of the queue +self+. Examples ^^^^^^^^ @@ -225,16 +220,12 @@ Examples 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); +assert(strcmp(deq_back(queue), str2) == 0); ---- [[deq_pop_front]] @@ -283,6 +274,31 @@ assert(str_cmp(deq_pop_back(queue), str2) == 0); assert(str_cmp(deq_pop_back(queue), str1) == 0); ---- +[[deq_set]] ++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 <string.h> + +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); +---- + [[deq_index]] +void* deq_index(deq *self, int index)+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -307,10 +323,11 @@ deq_push_back(queue, str_dup(str3)); assert(str_cmp(deq_index(queue, 1), str2) == 0); ---- -[[deq_front]] -+void* deq_front(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the element at the front of the queue +self+. +[[deq_insert]] ++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 ^^^^^^^^ @@ -321,18 +338,23 @@ Examples 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)); -assert(strcmp(deq_front(queue), str1) == 0); +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); ---- -[[deq_back]] -+void* deq_back(deq *self)+ -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Returns the element at the back of the queue +self+. +[[deq_remove]] ++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 ^^^^^^^^ @@ -343,12 +365,18 @@ Examples 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(strcmp(deq_back(queue), str2) == 0); +deq_remove(queue, 1); + +assert(deq_size == 2); +assert(strcmp(deq_front(queue), str1) == 0); +assert(strcmp(deq_back(queue), str3) == 0); ---- [[deq_swap]] @@ -478,11 +506,13 @@ deq_reserve(queue, 20); assert(deq_capacity(queue) >= 20); ---- -[[deq_remove]] -+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. +[[deq_clear]] ++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,+deq_free()+>> should be called immediately after this. Examples ^^^^^^^^ @@ -493,58 +523,31 @@ Examples 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); +deq_clear(queue); +assert(deq_size(queue) == 0); +deq_free(queue); ---- -[[deq_print]] -+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. +[[deq_free]] ++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_free()+>>, <<deq_clear,+deq_clear()+>> should be called before +if they are no longer needed to avoid memory leaks. Examples ^^^^^^^^ [source,c] ---- #include "double_ended_queue.h" -#include <string.h> - -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] +deq_free(queue); ---- diff --git a/collections/double_ended_queue/double_ended_queue.c b/collections/double_ended_queue/double_ended_queue.c index f5e9880..c08169d 100644 --- a/collections/double_ended_queue/double_ended_queue.c +++ b/collections/double_ended_queue/double_ended_queue.c @@ -28,6 +28,19 @@ struct double_ended_queue { int beg, end, limit; }; +void deq_debug_print(root) +deq *root; +{ + void **tmp; + + fprintf(stderr, "DEQ[base: %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_new() { deq *root; @@ -111,16 +124,40 @@ deq *root; root->base = tmp; } -void* deq_index(root, index) +deq* deq_cp(root) deq *root; -int index; { - void **tmp; + deq *copy; - if (!root || !DEQ_IN_BOUNDS(root,index)) - return NULL; + copy = deq_with_capacity(root->limit); + assert(copy->base); - return root->base[(root->beg + index) % root->limit]; + copy->base = memcpy(copy->base, root->base, + root->limit * sizeof(void*)); + assert(copy->base); + + copy->beg = root->beg; + copy->end = root->end; + + return copy; +} + +void deq_print(root, to_string) +deq *root; +char* to_string(void*); +{ + int i, size;; + char *tmp; + + size = deq_size(root); + + printf("["); + for (i = 0; i < size; i++) { + printf("%s,", tmp = to_string(deq_index(root, i))); + free(tmp); + tmp = NULL; + } + printf("\b]\n"); } void deq_push_front(root, item) @@ -163,54 +200,23 @@ void *item; root->end = root->limit; } -void deq_set(root, index, item) +void* deq_front(root) deq *root; -int index; -void *item; { - if (!root || !DEQ_IN_BOUNDS(root, index)) - return; - root->base[(root->beg + index) % root->limit] = item; + if (!root) + return NULL; + + return root->base[root->beg]; } -void deq_insert(root, index, item) +void* deq_back(root) 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; + return NULL; - root->base[index] = item; + return root->base[(root->end - 1) % root->limit]; } - void* deq_pop_front(root) deq *root; { @@ -238,63 +244,78 @@ deq *root; return root->base[root->end]; } -void* deq_swap_rm_front(root, index) +void deq_set(root, index, item) deq *root; int index; +void *item; { - if (!root || !DEQ_IN_BOUNDS(root,index)) - return NULL; - - deq_swap(root, 0, index); - return deq_pop_front(root); + if (!root || !DEQ_IN_BOUNDS(root, index)) + return; + root->base[(root->beg + index) % root->limit] = item; } -void* deq_swap_rm_back(root, index) +void* deq_index(root, index) deq *root; int index; { + void **tmp; + if (!root || !DEQ_IN_BOUNDS(root,index)) return NULL; - deq_swap(root,deq_size(root) - 1,index); - return deq_pop_back(root); + return root->base[(root->beg + index) % root->limit]; } -void deq_swap(root, i, j) +void deq_insert(root, index, item) deq *root; -int i, j; +int index; +void *item; { - int len; - void *tmp; - if (!root) return; - len = deq_size(root); - - if (i >= len || j >= len) + if (index > deq_size(root)) return; - i += root->beg; - i %= root->limit; + if (root->end >= root->limit) + deq_resize(root); - j += root->beg; - j %= root->limit; + index = (root->beg + index) % root->limit; - tmp = root->base[i]; - root->base[i] = root->base[j]; - root->base[j] = tmp; + 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_remove(root, index) deq *root; int index; { + void *tmp; + if (!root || !DEQ_IN_BOUNDS(root,index)); return; index = (root->beg + index) % root->limit; + tmp = root->base[index]; root->base[index] = NULL; if (root->beg < root->end || index >= root->beg) { @@ -306,78 +327,58 @@ int index; memmove(root->base + index, root->base + index + 1, (--root->end - index) * sizeof(void*)); } + + return tmp; } -/* Note: Elements are not freed - * deq_clear should be called before if they are no longer needed. - */ -void deq_free(root) +void deq_swap(root, i, j) deq *root; +int i, j; { - free(root->base); - root->base = NULL; + int len; + void *tmp; - free(root); -} + if (!root) + return; -void deq_clear(root) -deq *root; -{ - int i, size; + len = deq_size(root); - size = deq_size(root); - for (i = 0; i < size; i++) { - free(deq_index(root, i)); - } -} + if (i >= len || j >= len) + return; -void deq_print(root, to_string) -deq *root; -char* to_string(void*); -{ - int i, size;; + i += root->beg; + i %= root->limit; - size = deq_size(root); + j += root->beg; + j %= root->limit; - printf("["); - for (i = 0; i < size; i++) { - printf("%s,", to_string(deq_index(root, i))); - } - printf("\b]\n"); + tmp = root->base[i]; + root->base[i] = root->base[j]; + root->base[j] = tmp; } -void deq_debug_print(root) +void* deq_swap_rm_front(root, index) deq *root; +int index; { - void **tmp; + if (!root || !DEQ_IN_BOUNDS(root,index)) + return NULL; - fprintf(stderr, "DEQ[base: %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_swap(root, 0, index); + return deq_pop_front(root); } -deq* deq_cp(root) +void* deq_swap_rm_back(root, index) deq *root; +int index; { - 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; + if (!root || !DEQ_IN_BOUNDS(root,index)) + return NULL; - return copy; + deq_swap(root,deq_size(root) - 1,index); + return deq_pop_back(root); } -/*Note: Does not currently reduce memory footprint*/ void deq_truncate(root, size) deq *root; int size; @@ -388,24 +389,6 @@ int size; 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; @@ -439,3 +422,23 @@ int size; free(root->base); root->base = tmp; } + +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_free(root) +deq *root; +{ + free(root->base); + root->base = NULL; + + free(root); +} diff --git a/collections/double_ended_queue/double_ended_queue.h b/collections/double_ended_queue/double_ended_queue.h index df3b038..fe1f6ad 100644 --- a/collections/double_ended_queue/double_ended_queue.h +++ b/collections/double_ended_queue/double_ended_queue.h @@ -11,33 +11,35 @@ deq* deq_with_capacity(int); 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*); +void deq_print(deq*, char* (void*)); /*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_front(deq*); +void* deq_back(deq*); void* deq_pop_front(deq*); void* deq_pop_back(deq*); + +void deq_set(deq*, int, void*); 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_insert(deq*, int, void*); +void* deq_remove(deq*, int); void deq_swap(deq*, int, int); +void* deq_swap_rm_front(deq*, int); +void* deq_swap_rm_back(deq*, int); -/*Note: Does not currently reduce memory footprint*/ +/*memory*/ void deq_truncate(deq*, int); + /*Note: Does not currently reduce memory footprint*/ void deq_reserve(deq*, int); -void deq_remove(deq*, int); -void deq_print(deq*, char* (void*)); +void deq_clear(deq*); + /*Free all elements within queue*/ +void deq_free(deq*); + /* Note: Elements are not freed + * deq_clear should be called before if they are no longer needed.*/ + #endif |