aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--collections/double_ended_queue.adoc19
-rw-r--r--collections/double_ended_queue.c36
-rw-r--r--collections/double_ended_queue.h6
3 files changed, 54 insertions, 7 deletions
diff --git a/collections/double_ended_queue.adoc b/collections/double_ended_queue.adoc
index 70cbbaf..9ecf9cb 100644
--- a/collections/double_ended_queue.adoc
+++ b/collections/double_ended_queue.adoc
@@ -1,7 +1,7 @@
Double Ended Queue
==================
Tucker Evans
-v0.2, 2020-06-10
+v0.3, 2020-06-10
A double ended queue implemented in a circular buffer.
@@ -440,6 +440,23 @@ 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
diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c
index 4de6a27..015b90b 100644
--- a/collections/double_ended_queue.c
+++ b/collections/double_ended_queue.c
@@ -88,7 +88,7 @@ deq *root;
int size;
tmp = malloc(root->limit * 2 * sizeof(void*));
- assert(root->base);
+ assert(tmp);
if (root->beg <= root->end) {
tmp = memcpy(tmp, root->base + root->beg,
@@ -405,3 +405,37 @@ deq *root;
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
index c45b11b..6448c8a 100644
--- a/collections/double_ended_queue.h
+++ b/collections/double_ended_queue.h
@@ -36,12 +36,8 @@ 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*));
-
-
-/*TODO
- * resevee
- */
#endif