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