Add reserve function for double ended queue.

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