From fa75450d127d745542f863077f141ea0c5cfe975 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 20 Aug 2020 09:43:59 +0200 Subject: Eine einfache Fehlerbehandlung hinzugefügt. Von produktionsreifem Code sind wir allerdings noch weit entfernt! MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 55 insertions(+), 4 deletions(-) (limited to 'deque.c') diff --git a/deque.c b/deque.c index 91c7a50..c4b1795 100644 --- a/deque.c +++ b/deque.c @@ -3,6 +3,8 @@ #include #include +#include "util.h" + typedef int T; #define START_MAP_CAPACITY 4 @@ -19,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; @@ -41,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]); @@ -54,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; @@ -98,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 @@ -106,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 ) { @@ -121,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; } @@ -143,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; } @@ -158,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; } @@ -174,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; } @@ -190,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; @@ -206,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; @@ -222,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; } @@ -244,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; } @@ -267,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 ) { @@ -374,6 +423,8 @@ test_deque(void) assert(deque_size(d) == 0); deque_free(d); + + puts("all tests passed."); } int -- cgit v1.3