Merge branch 'deque'

1 files changed, 60 insertions, 6 deletions

diff --git a/deque.c b/deque.c
index 168669e..c4b1795 100644
--- a/deque.c
+++ b/deque.c
@@ -3,7 +3,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-#define NELEM(x) (sizeof(x) / sizeof(x[0]))
+#include "util.h"
 
 typedef int T;
 
@@ -21,16 +21,28 @@ struct deque {
         size_t size;
 };
 
+static void *
+allocate(size_t n, size_t sz)
+{
+        void *ptr = calloc(n, sz);
+        if ( ptr == NULL ) {
+                ERROR("out of memory!");
+        }
+        return ptr;
+}
+
 void
 deque_init(struct deque *d)
 {
+        assert(d != NULL);
+
         d->map_begin = 0;
         d->map_end   = 0;
         d->offset    = 0;
         d->size      = 0;
 
         // TODO: Error handling
-        d->map = calloc(START_MAP_CAPACITY, sizeof *d->map);
+        d->map = allocate(START_MAP_CAPACITY, sizeof *d->map);
         if ( d->map != NULL ) {
                 d->map_capacity = START_MAP_CAPACITY;
 
@@ -43,6 +55,8 @@ deque_init(struct deque *d)
 void
 deque_free(struct deque *d)
 {
+        assert(d != NULL);
+
         // free all chunks
         for ( size_t i = 0; i != d->map_capacity; ++i ) {
                 free(d->map[i]);
@@ -56,20 +70,26 @@ deque_free(struct deque *d)
 size_t
 deque_size(struct deque *d)
 {
+        assert(d != NULL);
+
         return d->size;
 }
 
 bool
 deque_is_empty(struct deque *d)
 {
+        assert(d != NULL);
+
         return d->map_begin == d->map_end;
 }
 
 static void
 grow_map(struct deque *d)
 {
+        assert(d != NULL);
+
         const size_t capacity = d->map_capacity + d->map_capacity / 2;
-        T **         map      = calloc(capacity, sizeof *map);
+        T **         map      = allocate(capacity, sizeof *map);
 
         // copy elements
         size_t i, j;
@@ -100,6 +120,8 @@ grow_map(struct deque *d)
 static void
 map_append_chunk(struct deque *d)
 {
+        assert(d != NULL);
+
         size_t next = (d->map_end + 1) % d->map_capacity;
 
         if ( next == d->map_begin ) { // Resize the map
@@ -108,13 +130,15 @@ map_append_chunk(struct deque *d)
                 next = d->map_end + 1;
         }
 
-        d->map[d->map_end] = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map);
         d->map_end         = next;
 }
 
 static void
 map_prepend_chunk(struct deque *d)
 {
+        assert(d != NULL);
+
         size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity;
 
         if ( prev == d->map_end ) {
@@ -123,13 +147,15 @@ map_prepend_chunk(struct deque *d)
                 prev = d->map_capacity - 1;
         }
 
-        d->map[prev] = calloc(CHUNK_CAPACITY, sizeof **d->map);
+        d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map);
         d->map_begin = prev;
 }
 
 static void
 map_remove_front_chunk(struct deque *d)
 {
+        assert(d != NULL);
+
         if ( d->map_begin == d->map_end ) {
                 return;
         }
@@ -145,6 +171,8 @@ map_remove_front_chunk(struct deque *d)
 static void
 map_remove_tail_chunk(struct deque *d)
 {
+        assert(d != NULL);
+
         if ( d->map_begin == d->map_end ) {
                 return;
         }
@@ -160,6 +188,10 @@ map_remove_tail_chunk(struct deque *d)
 bool
 deque_get_at(struct deque *d, size_t idx, T *data)
 {
+        assert(d != NULL);
+        assert(idx < d->size);
+        assert(data != NULL);
+
         if ( idx >= d->size ) {
                 return false;
         }
@@ -176,6 +208,9 @@ deque_get_at(struct deque *d, size_t idx, T *data)
 bool
 deque_set_at(struct deque *d, size_t idx, T data)
 {
+        assert(d != NULL);
+        assert(idx < d->size);
+
         if ( idx >= d->size ) {
                 return false;
         }
@@ -192,6 +227,8 @@ deque_set_at(struct deque *d, size_t idx, T data)
 void
 deque_push_back(struct deque *d, T data)
 {
+        assert(d != NULL);
+
         const size_t pos       = d->offset + d->size;
         const size_t chunk_off = pos % CHUNK_CAPACITY;
         size_t       chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity;
@@ -208,6 +245,8 @@ deque_push_back(struct deque *d, T data)
 void
 deque_push_front(struct deque *d, T data)
 {
+        assert(d != NULL);
+
         if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei!
                 map_prepend_chunk(d);
                 d->offset = CHUNK_CAPACITY;
@@ -224,6 +263,9 @@ deque_push_front(struct deque *d, T data)
 bool
 deque_pop_back(struct deque *d, T *data)
 {
+        assert(d != NULL);
+        assert(data != NULL);
+
         if ( d->size == 0 ) {
                 return false;
         }
@@ -246,6 +288,9 @@ deque_pop_back(struct deque *d, T *data)
 bool
 deque_pop_front(struct deque *d, T *data)
 {
+        assert(d != NULL);
+        assert(data != NULL);
+
         if ( d->size == 0 ) {
                 return false;
         }
@@ -269,6 +314,8 @@ deque_pop_front(struct deque *d, T *data)
 static void
 deque_show(struct deque *d)
 {
+        assert(d != NULL);
+
         printf("first: %zu -- last: %zu -- size: %zu -- map_capacity: %zu -- offset: %zu\n",
                d->map_begin, d->map_end, d->size, d->map_capacity, d->offset);
         for ( size_t i = 0; i != d->map_capacity; ++i ) {
@@ -284,7 +331,7 @@ test_deque(void)
 
         deque_init(d);
 
-        const int N = 10000000;
+        const int N = 100000;
 
         for ( int i = 0; i != N; ++i ) {
                 deque_push_front(d, i);
@@ -296,6 +343,7 @@ test_deque(void)
                 assert(data == i);
         }
         assert(deque_is_empty(d) == true);
+        assert(deque_size(d) == 0);
 
         deque_free(d);
 
@@ -311,6 +359,7 @@ test_deque(void)
                 assert(data == i);
         }
         assert(deque_is_empty(d) == true);
+        assert(deque_size(d) == 0);
 
         deque_free(d);
 
@@ -326,6 +375,7 @@ test_deque(void)
                 assert(data == i);
         }
         assert(deque_is_empty(d) == true);
+        assert(deque_size(d) == 0);
 
         deque_free(d);
 
@@ -354,6 +404,7 @@ test_deque(void)
                 assert(data == i);
         }
         assert(deque_is_empty(d) == true);
+        assert(deque_size(d) == 0);
 
         deque_free(d);
 
@@ -369,8 +420,11 @@ test_deque(void)
                 assert(data == i);
         }
         assert(deque_is_empty(d) == true);
+        assert(deque_size(d) == 0);
 
         deque_free(d);
+
+        puts("all tests passed.");
 }
 
 int