From 024cb7031b29c3d6b2f3a42ca18116195d30ea61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 12 Aug 2020 17:35:02 +0200 Subject: Neustart der Implementierung von Deque's --- deque.c | 124 +++++++++++----------------------------------------------------- 1 file changed, 21 insertions(+), 103 deletions(-) diff --git a/deque.c b/deque.c index 7125764..22e2d82 100644 --- a/deque.c +++ b/deque.c @@ -1,125 +1,43 @@ +#include #include #include -#include -#define NELEM(x) (sizeof(x) / sizeof(x[0])) +#define NELEM(x) (sizeof(x) / sizeof(x[0])) typedef int T; -struct chunk { - int head, tail; - T array[8]; -}; - -static void -chunk_init(struct chunk *c) -{ - c->head = 0; - c->tail = 0; -} - -static bool -chunk_put(struct chunk *c, T data) -{ - const int next = (c->head + 1) % NELEM(c->array); - - if ( next == c->tail ) /* full? */ - return false; - - c->array[c->head] = data; - c->head = next; - - return true; -} - -static bool -chunk_get(struct chunk *c, T *data) -{ - if ( c->head == c->tail ) /* empty? */ - return false; - - const int next = (c->tail + 1) % NELEM(c->array); - - *data = c->array[c->tail]; - c->tail = next; - - return true; -} - -static int -chunk_size(struct chunk *c) -{ - return (c->head + NELEM(c->array) - c->tail) % NELEM(c->array); -} - -static bool -chunk_full(struct chunk *c) -{ - return ((c->head + 1) % NELEM(c->array)) == c->tail; -} - -static bool -chunk_empty(struct chunk *c) -{ - return c->head == c->tail; -} - -static T* -chunk_at(struct chunk *c, int idx) -{ - if ( idx < 0 || idx >= chunk_size(c) ) /* invalid index? */ - return NULL; - - return &c->array[(c->head + idx) % NELEM(c->array)]; -} - -/* ================= */ +#define START_CAPACITY 8 struct deque { - int head, tail, capacity; - - struct chunk **chunks; + T ** chunks; + size_t head; + size_t tail; + size_t capacity; }; void deque_init(struct deque *d) { - int i; - - d->head = 0; - d->tail = 0; - d->capacity = 1; + d->head = 0; + d->tail = 0; + d->capacity = START_CAPACITY; - d->chunks = calloc(d->capacity, sizeof(struct chunk *)); - - for ( i = 0; i != d->capacity; ++i ) { - d->chunks[i] = malloc(sizeof(struct chunk)); - chunk_init(d->chunks[i]); - } + d->chunks = calloc(d->capacity, sizeof(*d->chunks)); } - -int main(void) +void +deque_free(struct deque *d) { - struct chunk c; - int data; - - chunk_init(&c); + free(d->chunks); +} - chunk_put(&c, '0'); - chunk_put(&c, '0'); - chunk_get(&c, &data); - chunk_get(&c, &data); +int +main(void) +{ + struct deque c; - chunk_put(&c, 'A'); - chunk_put(&c, 'B'); - chunk_put(&c, 'C'); - chunk_put(&c, 'D'); - chunk_put(&c, 'E'); - chunk_put(&c, 'F'); - chunk_put(&c, 'G'); + deque_init(&c); + deque_free(&c); - printf("head: %d -- tail: %d -- size: %d\n", c.head, c.tail, chunk_size(&c)); return 0; } - -- cgit v1.3 From 26ac3307fd93588a243a289ac569be8e8b2d4c9f Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Wed, 12 Aug 2020 20:19:59 +0200 Subject: vereinfache Code (sizeof braucht oft keine oder nur wenige Klammern) --- deque.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/deque.c b/deque.c index 22e2d82..903f64f 100644 --- a/deque.c +++ b/deque.c @@ -22,7 +22,7 @@ deque_init(struct deque *d) d->tail = 0; d->capacity = START_CAPACITY; - d->chunks = calloc(d->capacity, sizeof(*d->chunks)); + d->chunks = calloc(d->capacity, sizeof *d->chunks); } void -- cgit v1.3 From b46907ed64dd56415a4ca0d0dfac954003a14faf Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 13 Aug 2020 08:58:47 +0200 Subject: Aktiviere eine bessere Warnstufe des Compilers, wenn zwischen signed und unsigned Werten wild hin- und hergeschalten wird. --- makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/makefile b/makefile index 0c229d6..12d1935 100644 --- a/makefile +++ b/makefile @@ -1,6 +1,6 @@ .PHONY: all clean -CFLAGS=-O3 -Wall -Werror -Wno-unused-function -pedantic -std=c99 -g +CFLAGS=-O3 -Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g all: list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque -- cgit v1.3 From 69e65c19890a9e6128cf06b5ae9b03c31b18f304 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 13 Aug 2020 17:11:22 +0200 Subject: Sichere den Zwischenstand: Management der Chunks sollte nun funktionieren! --- deque.c | 120 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 111 insertions(+), 9 deletions(-) diff --git a/deque.c b/deque.c index 903f64f..6cf114d 100644 --- a/deque.c +++ b/deque.c @@ -6,29 +6,114 @@ typedef int T; -#define START_CAPACITY 8 +#define START_MAP_CAPACITY 4 +#define CHUNK_CAPACITY 10 struct deque { - T ** chunks; - size_t head; - size_t tail; + T **map; + + size_t first_chunk; + size_t last_chunk; + size_t capacity; }; void deque_init(struct deque *d) { - d->head = 0; - d->tail = 0; - d->capacity = START_CAPACITY; + d->first_chunk = 0; + d->last_chunk = 0; - d->chunks = calloc(d->capacity, sizeof *d->chunks); + // TODO: Error handling + d->map = calloc(START_MAP_CAPACITY, sizeof *d->map); + if ( d->map != NULL ) { + d->capacity = START_MAP_CAPACITY; + + for ( size_t i = 0; i != d->capacity; ++i ) { + d->map[i] = NULL; + } + } } void deque_free(struct deque *d) { - free(d->chunks); + // free all chunks + for ( size_t i = 0; i != d->capacity; ++i ) { + free(d->map[i]); + } + + // free the map itself + free(d->map); +} + +static void +grow_map(struct deque *d) +{ + const size_t capacity = d->capacity + (d->capacity / 2); + T ** map = calloc(capacity, sizeof *map); + + // copy elements + size_t i; + for ( i = 0; i != d->capacity; ++i ) { + map[i] = d->map[(i + d->first_chunk) % d->capacity]; + } + + // initialize the rest (new) elements with NULL + for ( ; i != capacity; ++i ) { + map[i] = NULL; + } + + // free old & assign new map + free(d->map); + d->map = map; + + // adjust pointers + d->first_chunk = 0; + d->last_chunk = d->capacity - 1; + + // set new capacity + d->capacity = capacity; +} + +static void +append_chunk(struct deque *d) +{ + size_t next = (d->last_chunk + 1) % d->capacity; + + if ( next == d->first_chunk ) { // Resize the map + grow_map(d); + + next = d->last_chunk + 1; + } + + d->map[d->last_chunk] = calloc(CHUNK_CAPACITY, sizeof **d->map); + d->last_chunk = next; +} + +static void +prepend_chunk(struct deque *d) +{ + size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity; + + if ( prev == d->last_chunk ) { + grow_map(d); + + prev = d->capacity - 1; + } + + d->map[prev] = calloc(CHUNK_CAPACITY, sizeof **d->map); + d->first_chunk = prev; +} + +static void +deque_show(struct deque *d) +{ + printf("first: %zu -- last: %zu -- capacity: %zu\n", d->first_chunk, d->last_chunk, d->capacity); + for ( size_t i = 0; i != d->capacity; ++i ) { + printf("%zu(%p) ", i, (void *) d->map[i]); + } + puts(""); } int @@ -37,6 +122,23 @@ main(void) struct deque c; deque_init(&c); + + deque_show(&c); + append_chunk(&c); + deque_show(&c); + append_chunk(&c); + deque_show(&c); + append_chunk(&c); + deque_show(&c); + prepend_chunk(&c); + deque_show(&c); + append_chunk(&c); + deque_show(&c); + prepend_chunk(&c); + deque_show(&c); + prepend_chunk(&c); + deque_show(&c); + deque_free(&c); return 0; -- cgit v1.3 From 9990de5ea16ed1f6c6df647a9dd43f7c4f5f2653 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 14 Aug 2020 17:44:55 +0200 Subject: Erste Version der DEQUE kann Elemente aufnehemen und wieder entfernen. --- deque.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 96 insertions(+), 19 deletions(-) diff --git a/deque.c b/deque.c index 6cf114d..070040b 100644 --- a/deque.c +++ b/deque.c @@ -7,7 +7,7 @@ typedef int T; #define START_MAP_CAPACITY 4 -#define CHUNK_CAPACITY 10 +#define CHUNK_CAPACITY 17 struct deque { T **map; @@ -15,6 +15,8 @@ struct deque { size_t first_chunk; size_t last_chunk; + size_t start; + size_t size; size_t capacity; }; @@ -23,6 +25,8 @@ deque_init(struct deque *d) { d->first_chunk = 0; d->last_chunk = 0; + d->start = 0; + d->size = 0; // TODO: Error handling d->map = calloc(START_MAP_CAPACITY, sizeof *d->map); @@ -50,7 +54,7 @@ deque_free(struct deque *d) static void grow_map(struct deque *d) { - const size_t capacity = d->capacity + (d->capacity / 2); + const size_t capacity = d->capacity + d->capacity / 2; T ** map = calloc(capacity, sizeof *map); // copy elements @@ -77,7 +81,7 @@ grow_map(struct deque *d) } static void -append_chunk(struct deque *d) +map_append_chunk(struct deque *d) { size_t next = (d->last_chunk + 1) % d->capacity; @@ -92,7 +96,7 @@ append_chunk(struct deque *d) } static void -prepend_chunk(struct deque *d) +map_prepend_chunk(struct deque *d) { size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity; @@ -106,10 +110,87 @@ prepend_chunk(struct deque *d) d->first_chunk = prev; } +static void +map_remove_front_chunk(struct deque *d) +{ + if ( d->first_chunk == d->last_chunk ) + return; + + const size_t next = (d->first_chunk + 1) % d->capacity; + + free(d->map[d->first_chunk]); + d->map[d->first_chunk] = NULL; + + d->first_chunk = next; +} + +static void +map_remove_tail_chunk(struct deque *d) +{ + if ( d->first_chunk == d->last_chunk ) + return; + + const size_t prev = (d->last_chunk + d->capacity - 1) % d->capacity; + + free(d->map[prev]); + d->map[prev] = NULL; + + d->last_chunk = prev; +} + +void +deque_get_at(struct deque *d, size_t idx, T *data) +{ + const size_t offset = d->start + idx; + const size_t chunk_off = offset % CHUNK_CAPACITY; + const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + + *data = d->map[chunk_num][chunk_off]; +} + +void +deque_push_back(struct deque *d, T data) +{ + const size_t offset = d->start + d->size; + const size_t chunk_off = offset % CHUNK_CAPACITY; + size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + + if ( chunk_num == d->last_chunk ) { + map_append_chunk(d); + chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + } + + d->map[chunk_num][chunk_off] = data; + ++d->size; +} + +bool +deque_pop_front(struct deque *d, T *data) +{ + if ( d->size == 0 ) + return false; + + const size_t chunk_off = d->start % CHUNK_CAPACITY; + const size_t chunk_num = ((d->start / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + + *data = d->map[chunk_num][chunk_off]; + + --d->size; + ++d->start; + + if ( d->size == 0 || d->start == CHUNK_CAPACITY ) { + map_remove_front_chunk(d); + d->start = 0; + } + + return true; +} + static void deque_show(struct deque *d) { - printf("first: %zu -- last: %zu -- capacity: %zu\n", d->first_chunk, d->last_chunk, d->capacity); + printf("first: %zu -- last: %zu -- size: %zu -- capacity: %zu -- start: %zu\n", + d->first_chunk, d->last_chunk, d->size, d->capacity, d->start); for ( size_t i = 0; i != d->capacity; ++i ) { printf("%zu(%p) ", i, (void *) d->map[i]); } @@ -123,20 +204,16 @@ main(void) deque_init(&c); - deque_show(&c); - append_chunk(&c); - deque_show(&c); - append_chunk(&c); - deque_show(&c); - append_chunk(&c); - deque_show(&c); - prepend_chunk(&c); - deque_show(&c); - append_chunk(&c); - deque_show(&c); - prepend_chunk(&c); - deque_show(&c); - prepend_chunk(&c); + for ( int i = 0; i != 100; ++i ) { + deque_push_back(&c, i); + //deque_show(&c); + } + + T data; + while ( deque_pop_front(&c, &data) ) { + printf("%u, ", data); + } + putchar('\n'); deque_show(&c); deque_free(&c); -- cgit v1.3 From 1e6334eaa1ae4423061cea0455b08d6e096001f3 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 14 Aug 2020 17:55:16 +0200 Subject: Verwende etwas sprechendere Namen... --- deque.c | 102 ++++++++++++++++++++++++++++++++-------------------------------- 1 file changed, 51 insertions(+), 51 deletions(-) diff --git a/deque.c b/deque.c index 070040b..eab623b 100644 --- a/deque.c +++ b/deque.c @@ -12,28 +12,28 @@ typedef int T; struct deque { T **map; - size_t first_chunk; - size_t last_chunk; + size_t map_begin; + size_t map_end; + size_t map_capacity; - size_t start; + size_t offset; size_t size; - size_t capacity; }; void deque_init(struct deque *d) { - d->first_chunk = 0; - d->last_chunk = 0; - d->start = 0; - d->size = 0; + 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); if ( d->map != NULL ) { - d->capacity = START_MAP_CAPACITY; + d->map_capacity = START_MAP_CAPACITY; - for ( size_t i = 0; i != d->capacity; ++i ) { + for ( size_t i = 0; i != d->map_capacity; ++i ) { d->map[i] = NULL; } } @@ -43,7 +43,7 @@ void deque_free(struct deque *d) { // free all chunks - for ( size_t i = 0; i != d->capacity; ++i ) { + for ( size_t i = 0; i != d->map_capacity; ++i ) { free(d->map[i]); } @@ -54,13 +54,13 @@ deque_free(struct deque *d) static void grow_map(struct deque *d) { - const size_t capacity = d->capacity + d->capacity / 2; - T ** map = calloc(capacity, sizeof *map); + const size_t capacity = d->map_capacity + d->map_capacity / 2; + T ** map = calloc(map_capacity, sizeof *map); // copy elements size_t i; - for ( i = 0; i != d->capacity; ++i ) { - map[i] = d->map[(i + d->first_chunk) % d->capacity]; + for ( i = 0; i != d->map_capacity; ++i ) { + map[i] = d->map[(i + d->map_begin) % d->map_capacity]; } // initialize the rest (new) elements with NULL @@ -73,77 +73,77 @@ grow_map(struct deque *d) d->map = map; // adjust pointers - d->first_chunk = 0; - d->last_chunk = d->capacity - 1; + d->map_begin = 0; + d->map_end = d->map_capacity - 1; - // set new capacity - d->capacity = capacity; + // set new map_capacity + d->map_capacity = capacity; } static void map_append_chunk(struct deque *d) { - size_t next = (d->last_chunk + 1) % d->capacity; + size_t next = (d->map_end + 1) % d->map_capacity; - if ( next == d->first_chunk ) { // Resize the map + if ( next == d->map_begin ) { // Resize the map grow_map(d); - next = d->last_chunk + 1; + next = d->map_end + 1; } - d->map[d->last_chunk] = calloc(CHUNK_CAPACITY, sizeof **d->map); - d->last_chunk = next; + d->map[d->map_end] = calloc(CHUNK_CAPACITY, sizeof **d->map); + d->map_end = next; } static void map_prepend_chunk(struct deque *d) { - size_t prev = (d->first_chunk + d->capacity - 1) % d->capacity; + size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity; - if ( prev == d->last_chunk ) { + if ( prev == d->map_end ) { grow_map(d); - prev = d->capacity - 1; + prev = d->map_capacity - 1; } - d->map[prev] = calloc(CHUNK_CAPACITY, sizeof **d->map); - d->first_chunk = prev; + d->map[prev] = calloc(CHUNK_CAPACITY, sizeof **d->map); + d->map_begin = prev; } static void map_remove_front_chunk(struct deque *d) { - if ( d->first_chunk == d->last_chunk ) + if ( d->map_begin == d->map_end ) return; - const size_t next = (d->first_chunk + 1) % d->capacity; + const size_t next = (d->map_begin + 1) % d->map_capacity; - free(d->map[d->first_chunk]); - d->map[d->first_chunk] = NULL; + free(d->map[d->map_begin]); + d->map[d->map_begin] = NULL; - d->first_chunk = next; + d->map_begin = next; } static void map_remove_tail_chunk(struct deque *d) { - if ( d->first_chunk == d->last_chunk ) + if ( d->map_begin == d->map_end ) return; - const size_t prev = (d->last_chunk + d->capacity - 1) % d->capacity; + const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; free(d->map[prev]); d->map[prev] = NULL; - d->last_chunk = prev; + d->map_end = prev; } void deque_get_at(struct deque *d, size_t idx, T *data) { - const size_t offset = d->start + idx; + const size_t offset = d->offset + idx; const size_t chunk_off = offset % CHUNK_CAPACITY; - const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; } @@ -151,13 +151,13 @@ deque_get_at(struct deque *d, size_t idx, T *data) void deque_push_back(struct deque *d, T data) { - const size_t offset = d->start + d->size; + const size_t offset = d->offset + d->size; const size_t chunk_off = offset % CHUNK_CAPACITY; - size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; - if ( chunk_num == d->last_chunk ) { + if ( chunk_num == d->map_end ) { map_append_chunk(d); - chunk_num = ((offset / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; } d->map[chunk_num][chunk_off] = data; @@ -170,17 +170,17 @@ deque_pop_front(struct deque *d, T *data) if ( d->size == 0 ) return false; - const size_t chunk_off = d->start % CHUNK_CAPACITY; - const size_t chunk_num = ((d->start / CHUNK_CAPACITY) + d->first_chunk) % d->capacity; + const size_t chunk_off = d->offset % CHUNK_CAPACITY; + const size_t chunk_num = ((d->offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; --d->size; - ++d->start; + ++d->offset; - if ( d->size == 0 || d->start == CHUNK_CAPACITY ) { + if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) { map_remove_front_chunk(d); - d->start = 0; + d->offset = 0; } return true; @@ -189,9 +189,9 @@ deque_pop_front(struct deque *d, T *data) static void deque_show(struct deque *d) { - printf("first: %zu -- last: %zu -- size: %zu -- capacity: %zu -- start: %zu\n", - d->first_chunk, d->last_chunk, d->size, d->capacity, d->start); - for ( size_t i = 0; i != d->capacity; ++i ) { + 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 ) { printf("%zu(%p) ", i, (void *) d->map[i]); } puts(""); -- cgit v1.3 From 327da44ec896f65c12befb5872ce364d0a1fd074 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 14 Aug 2020 18:27:17 +0200 Subject: Überflüssige Klammern entfernt MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/deque.c b/deque.c index eab623b..56df165 100644 --- a/deque.c +++ b/deque.c @@ -55,7 +55,7 @@ static void grow_map(struct deque *d) { const size_t capacity = d->map_capacity + d->map_capacity / 2; - T ** map = calloc(map_capacity, sizeof *map); + T ** map = calloc(capacity, sizeof *map); // copy elements size_t i; @@ -143,7 +143,7 @@ deque_get_at(struct deque *d, size_t idx, T *data) { const size_t offset = d->offset + idx; const size_t chunk_off = offset % CHUNK_CAPACITY; - const size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; + const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; } @@ -153,11 +153,11 @@ deque_push_back(struct deque *d, T data) { const size_t offset = d->offset + d->size; const size_t chunk_off = offset % CHUNK_CAPACITY; - size_t chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; + size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; if ( chunk_num == d->map_end ) { map_append_chunk(d); - chunk_num = ((offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; + chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; } d->map[chunk_num][chunk_off] = data; @@ -171,7 +171,7 @@ deque_pop_front(struct deque *d, T *data) return false; const size_t chunk_off = d->offset % CHUNK_CAPACITY; - const size_t chunk_num = ((d->offset / CHUNK_CAPACITY) + d->map_begin) % d->map_capacity; + const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; -- cgit v1.3 From f024ba4245b37c80dce976c77b519c90115fd205 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 14 Aug 2020 18:28:32 +0200 Subject: Implement deque_push_front() --- deque.c | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/deque.c b/deque.c index 56df165..5800997 100644 --- a/deque.c +++ b/deque.c @@ -164,6 +164,22 @@ deque_push_back(struct deque *d, T data) ++d->size; } +void +deque_push_front(struct deque *d, T data) +{ + if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei! + map_prepend_chunk(d); + d->offset = CHUNK_CAPACITY; + } + + --d->offset; + + size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + d->map[chunk_num][d->offset] = data; + ++d->size; +} + bool deque_pop_front(struct deque *d, T *data) { @@ -209,6 +225,10 @@ main(void) //deque_show(&c); } + for ( int i = 0; i != 100; ++i ) { + deque_push_front(&c, 1000 + i); + } + T data; while ( deque_pop_front(&c, &data) ) { printf("%u, ", data); -- cgit v1.3 From 8beef34c04e1844545af284707478d57195ddfff Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 14 Aug 2020 18:54:02 +0200 Subject: Implement deque_pop_back() --- deque.c | 26 +++++++++++++++++++++++--- 1 file changed, 23 insertions(+), 3 deletions(-) diff --git a/deque.c b/deque.c index 5800997..36af05a 100644 --- a/deque.c +++ b/deque.c @@ -172,12 +172,33 @@ deque_push_front(struct deque *d, T data) d->offset = CHUNK_CAPACITY; } + ++d->size; --d->offset; size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; d->map[chunk_num][d->offset] = data; - ++d->size; +} + +bool +deque_pop_back(struct deque *d, T *data) +{ + if ( d->size == 0 ) + return false; + + --d->size; + + const size_t offset = d->offset + d->size; + const size_t chunk_off = offset % CHUNK_CAPACITY; + const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + *data = d->map[chunk_num][chunk_off]; + + if ( d->size == 0 || chunk_off == 0 ) { + map_remove_tail_chunk(d); + } + + return true; } bool @@ -186,10 +207,9 @@ deque_pop_front(struct deque *d, T *data) if ( d->size == 0 ) return false; - const size_t chunk_off = d->offset % CHUNK_CAPACITY; const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; - *data = d->map[chunk_num][chunk_off]; + *data = d->map[chunk_num][d->offset]; --d->size; ++d->offset; -- cgit v1.3 From eceae48ed4ab43cfe013fbe5b674ed9de80f7a3b Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 09:15:52 +0200 Subject: Kennzeichne die freigegebene Map mit einem NULL-Zeiger --- deque.c | 1 + 1 file changed, 1 insertion(+) diff --git a/deque.c b/deque.c index 36af05a..e019adc 100644 --- a/deque.c +++ b/deque.c @@ -49,6 +49,7 @@ deque_free(struct deque *d) // free the map itself free(d->map); + d->map = NULL; } static void -- cgit v1.3 From 7028633c6c6211a01bcad0515499a4cb893ea646 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 09:27:30 +0200 Subject: code cleanup --- deque.c | 45 ++++++++++++++++++++++++++++----------------- 1 file changed, 28 insertions(+), 17 deletions(-) diff --git a/deque.c b/deque.c index e019adc..3e78410 100644 --- a/deque.c +++ b/deque.c @@ -114,8 +114,9 @@ map_prepend_chunk(struct deque *d) static void map_remove_front_chunk(struct deque *d) { - if ( d->map_begin == d->map_end ) + if ( d->map_begin == d->map_end ) { return; + } const size_t next = (d->map_begin + 1) % d->map_capacity; @@ -128,8 +129,9 @@ map_remove_front_chunk(struct deque *d) static void map_remove_tail_chunk(struct deque *d) { - if ( d->map_begin == d->map_end ) + if ( d->map_begin == d->map_end ) { return; + } const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; @@ -139,29 +141,36 @@ map_remove_tail_chunk(struct deque *d) d->map_end = prev; } -void +bool deque_get_at(struct deque *d, size_t idx, T *data) { - const size_t offset = d->offset + idx; - const size_t chunk_off = offset % CHUNK_CAPACITY; - const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + if ( idx >= d->size ) { + return false; + } + + const size_t pos = d->offset + idx; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; + + return true; } void deque_push_back(struct deque *d, T data) { - const size_t offset = d->offset + d->size; - const size_t chunk_off = offset % CHUNK_CAPACITY; - size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + 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; if ( chunk_num == d->map_end ) { map_append_chunk(d); - chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; } d->map[chunk_num][chunk_off] = data; + ++d->size; } @@ -176,7 +185,7 @@ deque_push_front(struct deque *d, T data) ++d->size; --d->offset; - size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; d->map[chunk_num][d->offset] = data; } @@ -184,14 +193,15 @@ deque_push_front(struct deque *d, T data) bool deque_pop_back(struct deque *d, T *data) { - if ( d->size == 0 ) + if ( d->size == 0 ) { return false; + } --d->size; - const size_t offset = d->offset + d->size; - const size_t chunk_off = offset % CHUNK_CAPACITY; - const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + const size_t pos = d->offset + d->size; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][chunk_off]; @@ -205,8 +215,9 @@ deque_pop_back(struct deque *d, T *data) bool deque_pop_front(struct deque *d, T *data) { - if ( d->size == 0 ) + if ( d->size == 0 ) { return false; + } const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; @@ -231,7 +242,7 @@ deque_show(struct deque *d) for ( size_t i = 0; i != d->map_capacity; ++i ) { printf("%zu(%p) ", i, (void *) d->map[i]); } - puts(""); + putchar('\n'); } int -- cgit v1.3 From 3c1c032a05ab6a2bd2b4b86508e8b9fca1b06872 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 09:33:54 +0200 Subject: Zwei neue Funktionen (deque_size() und deque_is_empty()) hinzugefügt MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/deque.c b/deque.c index 3e78410..5687a41 100644 --- a/deque.c +++ b/deque.c @@ -52,6 +52,18 @@ deque_free(struct deque *d) d->map = NULL; } +size_t +deque_size(struct deque *d) +{ + return d->size; +} + +bool +deque_is_empty(struct deque *d) +{ + return d->map_begin == d->map_end; +} + static void grow_map(struct deque *d) { -- cgit v1.3 From c97164c73bde2226e9d9243771f5e58157db7218 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 09:55:30 +0200 Subject: makefile: Aktiviere noch mehr Fehlerprüfungen. Deaktiviere Optimierungen (damit man besser mit gdb debuggen kann). MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/makefile b/makefile index 12d1935..9748166 100644 --- a/makefile +++ b/makefile @@ -1,6 +1,6 @@ .PHONY: all clean -CFLAGS=-O3 -Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g +CFLAGS=-Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g all: list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque -- cgit v1.3 From 5f57d99e789947005da5da2de809c24dbc9ca56f Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 10:41:22 +0200 Subject: reorg code... --- deque.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/deque.c b/deque.c index 5687a41..da3c221 100644 --- a/deque.c +++ b/deque.c @@ -182,7 +182,6 @@ deque_push_back(struct deque *d, T data) } d->map[chunk_num][chunk_off] = data; - ++d->size; } @@ -194,12 +193,12 @@ deque_push_front(struct deque *d, T data) d->offset = CHUNK_CAPACITY; } - ++d->size; --d->offset; const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; d->map[chunk_num][d->offset] = data; + ++d->size; } bool @@ -231,11 +230,12 @@ deque_pop_front(struct deque *d, T *data) return false; } + --d->size; + const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; *data = d->map[chunk_num][d->offset]; - --d->size; ++d->offset; if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) { -- cgit v1.3 From 861f4a49a425dcf052fc36cef963a99d82a9c974 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 14:06:30 +0200 Subject: neue Funktion: deque_set_at() implementiert. --- deque.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) diff --git a/deque.c b/deque.c index da3c221..a4fbc1b 100644 --- a/deque.c +++ b/deque.c @@ -169,6 +169,22 @@ deque_get_at(struct deque *d, size_t idx, T *data) return true; } +bool +deque_set_at(struct deque *d, size_t idx, T data) +{ + if ( idx >= d->size ) { + return false; + } + + const size_t pos = d->offset + idx; + const size_t chunk_off = pos % CHUNK_CAPACITY; + const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; + + d->map[chunk_num][chunk_off] = data; + + return true; +} + void deque_push_back(struct deque *d, T data) { -- cgit v1.3 From a1979af4de4c3f2d6a3cea3d3181170b67647143 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 14:32:59 +0200 Subject: vereinfache das Kopieren der Chunkzeiger. --- deque.c | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-) diff --git a/deque.c b/deque.c index a4fbc1b..f1da207 100644 --- a/deque.c +++ b/deque.c @@ -71,9 +71,12 @@ grow_map(struct deque *d) T ** map = calloc(capacity, sizeof *map); // copy elements - size_t i; - for ( i = 0; i != d->map_capacity; ++i ) { - map[i] = d->map[(i + d->map_begin) % d->map_capacity]; + size_t i, j; + for ( i = 0, j = d->map_begin; i != d->map_capacity; ++i, ++j ) { + if ( j == d->map_capacity ) { + j = 0; + } + map[i] = d->map[j]; } // initialize the rest (new) elements with NULL @@ -280,15 +283,6 @@ main(void) deque_init(&c); - for ( int i = 0; i != 100; ++i ) { - deque_push_back(&c, i); - //deque_show(&c); - } - - for ( int i = 0; i != 100; ++i ) { - deque_push_front(&c, 1000 + i); - } - T data; while ( deque_pop_front(&c, &data) ) { printf("%u, ", data); -- cgit v1.3 From 5a869f2d5656523646b7526d59d48f49708a4c8c Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 16:31:12 +0200 Subject: Einfache Testroutine hinzugefügt. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 67 insertions(+) diff --git a/deque.c b/deque.c index f1da207..0e0bbf0 100644 --- a/deque.c +++ b/deque.c @@ -1,3 +1,4 @@ +#include #include #include #include @@ -276,9 +277,75 @@ deque_show(struct deque *d) putchar('\n'); } +void +test_deque(void) +{ + struct deque d[1]; + + deque_init(d); + + const int N = 10000000; + + for ( int i = 0; i != N; ++i ) { + deque_push_front(d, i); + } + + for ( int i = 0; i != N; ++i ) { + int data; + assert(deque_pop_back(d, &data) == true); + assert(data == i); + } + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_back(d, i); + } + + for ( int i = 0; i != N; ++i ) { + int data; + assert(deque_pop_front(d, &data) == true); + assert(data == i); + } + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_back(d, i); + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + assert(deque_pop_back(d, &data) == true); + assert(data == i); + } + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + deque_push_front(d, i); + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + assert(deque_pop_front(d, &data) == true); + assert(data == i); + } + + deque_free(d); +} + int main(void) { + test_deque(); + struct deque c; deque_init(&c); -- cgit v1.3 From 94a6f299a5c21effb0ed9fdde9b747427e1fbc90 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 15 Aug 2020 17:59:29 +0200 Subject: Es werden nun mehr Testfälle geprüft MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- deque.c | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) diff --git a/deque.c b/deque.c index 0e0bbf0..168669e 100644 --- a/deque.c +++ b/deque.c @@ -295,6 +295,7 @@ test_deque(void) assert(deque_pop_back(d, &data) == true); assert(data == i); } + assert(deque_is_empty(d) == true); deque_free(d); @@ -309,6 +310,7 @@ test_deque(void) assert(deque_pop_front(d, &data) == true); assert(data == i); } + assert(deque_is_empty(d) == true); deque_free(d); @@ -323,6 +325,35 @@ test_deque(void) assert(deque_pop_back(d, &data) == true); assert(data == i); } + assert(deque_is_empty(d) == true); + + deque_free(d); + + deque_init(d); + + for ( int i = 0; i != N; ++i ) { + if ( i & 1 ) { + deque_push_front(d, i); + } + else { + deque_push_back(d, i); + } + } + + for ( int i = N - 1; i >= 0; --i ) { + int data; + if ( i & 1 ) { + assert(deque_pop_front(d, &data) == true); + } + else { + assert(deque_pop_back(d, &data) == true); + } + if ( data != i ) { + printf("i: %d - data: %d\n", i, data); + } + assert(data == i); + } + assert(deque_is_empty(d) == true); deque_free(d); @@ -337,6 +368,7 @@ test_deque(void) assert(deque_pop_front(d, &data) == true); assert(data == i); } + assert(deque_is_empty(d) == true); deque_free(d); } -- cgit v1.3