aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTucker Evans <tucker@tuckerevans.com>2020-07-06 11:48:31 -0400
committerTucker Evans <tucker@tuckerevans.com>2020-07-06 11:48:31 -0400
commit392b0b46e151dbb3e441d1c2dcf361bb39dc7794 (patch)
tree11b1af6dc1b0264e64745a4816eea293a5171ad4
parent8f17093d39db99acd88405873af90b4bfd428a64 (diff)
parentda39577a66c9aa355699419149ce050a9cb1c500 (diff)
Merge branch 'develop'v0.2.1
-rw-r--r--collections/double_ended_queue/double_ended_queue.adoc205
-rw-r--r--collections/double_ended_queue/double_ended_queue.c277
-rw-r--r--collections/double_ended_queue/double_ended_queue.h34
-rw-r--r--license.txt22
4 files changed, 284 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
diff --git a/license.txt b/license.txt
new file mode 100644
index 0000000..41b9e5b
--- /dev/null
+++ b/license.txt
@@ -0,0 +1,22 @@
+MIT License
+
+Copyright (c) 2020 Tucker Evans
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+