From daef8f38f309bb8203547a574caed7974ce9fcbd Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 16 Aug 2020 09:50:08 +0200 Subject: Noch mehr assert()s, Weniger Durchläufe reichen aber auch aus! MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'deque.c') diff --git a/deque.c b/deque.c index 168669e..bf233cf 100644 --- a/deque.c +++ b/deque.c @@ -284,7 +284,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 +296,7 @@ test_deque(void) assert(data == i); } assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); deque_free(d); @@ -311,6 +312,7 @@ test_deque(void) assert(data == i); } assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); deque_free(d); @@ -326,6 +328,7 @@ test_deque(void) assert(data == i); } assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); deque_free(d); @@ -354,6 +357,7 @@ test_deque(void) assert(data == i); } assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); deque_free(d); @@ -369,6 +373,7 @@ test_deque(void) assert(data == i); } assert(deque_is_empty(d) == true); + assert(deque_size(d) == 0); deque_free(d); } -- cgit v1.3 From f6f15c219312f7f3a9d6d850861bafa6b4e9613a Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Mon, 17 Aug 2020 22:33:18 +0200 Subject: überflüssiges Makro NELEM entfernt! MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'deque.c') diff --git a/deque.c b/deque.c index bf233cf..91c7a50 100644 --- a/deque.c +++ b/deque.c @@ -3,8 +3,6 @@ #include #include -#define NELEM(x) (sizeof(x) / sizeof(x[0])) - typedef int T; #define START_MAP_CAPACITY 4 -- cgit v1.3 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