From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- deque.c | 485 ---------------------------------------------------------------- 1 file changed, 485 deletions(-) delete mode 100644 deque.c (limited to 'deque.c') diff --git a/deque.c b/deque.c deleted file mode 100644 index 881d1d3..0000000 --- a/deque.c +++ /dev/null @@ -1,485 +0,0 @@ -#include -#include -#include -#include - -#include "util.h" - -#define START_MAP_CAPACITY 4 -#define CHUNK_CAPACITY 17 - -/* --8<-- deque_type */ -typedef int T; - -struct deque { - T **map; - - size_t map_begin; - size_t map_end; - size_t map_capacity; - - size_t offset; - size_t size; -}; -/* -->8-- */ - -/* --8<-- deque_allocate */ -static void * -allocate(size_t n, size_t sz) -{ - void *ptr = calloc(n, sz); - if ( ptr == NULL ) { - ERROR("out of memory!"); - } - return ptr; -} -/* -->8-- */ - -/* --8<-- deque_init */ -void -deque_init(struct deque *d) -{ - assert(d); - - d->map_begin = 0; - d->map_end = 0; - d->offset = 0; - d->size = 0; - - // TODO: Error handling - d->map = allocate(START_MAP_CAPACITY, sizeof *d->map); - if ( d->map ) { - d->map_capacity = START_MAP_CAPACITY; - - for ( size_t i = 0; i != d->map_capacity; ++i ) { - d->map[i] = NULL; - } - } -} -/* -->8-- */ - -/* --8<-- deque_free */ -void -deque_free(struct deque *d) -{ - assert(d); - - // free all chunks - for ( size_t i = 0; i != d->map_capacity; ++i ) { - free(d->map[i]); - } - - // free the map itself - free(d->map); - d->map = NULL; -} -/* -->8-- */ - -/* --8<-- deque_size */ -size_t -deque_size(struct deque *d) -{ - assert(d); - - return d->size; -} -/* -->8-- */ - -/* --8<-- deque_is_empty */ -bool -deque_is_empty(struct deque *d) -{ - assert(d); - - return d->map_begin == d->map_end; -} -/* -->8-- */ - -/* --8<-- deque_grow_map */ -static void -grow_map(struct deque *d) -{ - assert(d); - - const size_t capacity = d->map_capacity + d->map_capacity / 2; - T ** map = allocate(capacity, sizeof *map); - - // copy elements - 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 - for ( ; i != capacity; ++i ) { - map[i] = NULL; - } - - // free old & assign new map - free(d->map); - d->map = map; - - // adjust pointers - d->map_begin = 0; - d->map_end = d->map_capacity - 1; - - // set new map_capacity - d->map_capacity = capacity; -} -/* -->8-- */ - -/* --8<-- deque_map_append_chunk */ -static void -map_append_chunk(struct deque *d) -{ - assert(d); - - size_t next = (d->map_end + 1) % d->map_capacity; - - if ( next == d->map_begin ) { // Resize the map - grow_map(d); - - next = d->map_end + 1; - } - - d->map[d->map_end] = allocate(CHUNK_CAPACITY, sizeof **d->map); - d->map_end = next; -} -/* -->8-- */ - -/* --8<-- deque_map_prepend_chunk */ -static void -map_prepend_chunk(struct deque *d) -{ - assert(d); - - size_t prev = (d->map_begin + d->map_capacity - 1) % d->map_capacity; - - if ( prev == d->map_end ) { - grow_map(d); - - prev = d->map_capacity - 1; - } - - d->map[prev] = allocate(CHUNK_CAPACITY, sizeof **d->map); - d->map_begin = prev; -} -/* -->8-- */ - -/* --8<-- deque_map_remove_front_chunk */ -static void -map_remove_front_chunk(struct deque *d) -{ - assert(d); - - if ( d->map_begin == d->map_end ) { - return; - } - - const size_t next = (d->map_begin + 1) % d->map_capacity; - - free(d->map[d->map_begin]); - d->map[d->map_begin] = NULL; - - d->map_begin = next; -} -/* -->8-- */ - -/* --8<-- deque_remove_tail_chunk */ -static void -map_remove_tail_chunk(struct deque *d) -{ - assert(d); - - if ( d->map_begin == d->map_end ) { - return; - } - - const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; - - free(d->map[prev]); - d->map[prev] = NULL; - - d->map_end = prev; -} -/* -->8-- */ - -/* --8<-- deque_get_at */ -bool -deque_get_at(struct deque *d, size_t idx, T *data) -{ - assert(d); - assert(idx < d->size); - assert(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; - - *data = d->map[chunk_num][chunk_off]; - - return true; -} -/* -->8-- */ - -/* --8<-- deque_set_at */ -bool -deque_set_at(struct deque *d, size_t idx, T data) -{ - assert(d); - assert(idx < d->size); - - 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; -} -/* -->8-- */ - -/* --8<-- deque_push_back */ -void -deque_push_back(struct deque *d, T data) -{ - assert(d); - - 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 = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; - } - - d->map[chunk_num][chunk_off] = data; - ++d->size; -} -/* -->8-- */ - -/* --8<-- deque_push_front */ -void -deque_push_front(struct deque *d, T data) -{ - assert(d); - - if ( d->offset == 0 ) { // Im ersten Element ist kein Platz mehr frei! - map_prepend_chunk(d); - d->offset = CHUNK_CAPACITY; - } - - --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; -} -/* -->8-- */ - -/* --8<-- deque_pop_back */ -bool -deque_pop_back(struct deque *d, T *data) -{ - assert(d); - assert(data); - - if ( d->size == 0 ) { - return false; - } - - --d->size; - - 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]; - - if ( d->size == 0 || chunk_off == 0 ) { - map_remove_tail_chunk(d); - } - - return true; -} -/* -->8-- */ - -/* --8<-- deque_pop_front */ -bool -deque_pop_front(struct deque *d, T *data) -{ - assert(d); - assert(data); - - if ( d->size == 0 ) { - 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->offset; - - if ( d->size == 0 || d->offset == CHUNK_CAPACITY ) { - map_remove_front_chunk(d); - d->offset = 0; - } - - return true; -} -/* -->8-- */ - -static void -deque_show(struct deque *d) -{ - assert(d); - - 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]); - } - putchar('\n'); -} - -void -test_deque(void) -{ -#ifndef NDEBUG - struct deque d[1]; - - deque_init(d); - - const int N = 100000; - - 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); - } - assert(deque_is_empty(d) == true); - assert(deque_size(d) == 0); - - 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); - } - assert(deque_is_empty(d) == true); - assert(deque_size(d) == 0); - - 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); - } - assert(deque_is_empty(d) == true); - assert(deque_size(d) == 0); - - 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); - assert(deque_size(d) == 0); - - 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); - } - assert(deque_is_empty(d) == true); - assert(deque_size(d) == 0); - - deque_free(d); - - puts("all tests passed."); -#endif -} - -int -main(void) -{ - test_deque(); - - struct deque c; - - deque_init(&c); - - T data; - while ( deque_pop_front(&c, &data) ) { - printf("%u, ", data); - } - putchar('\n'); - deque_show(&c); - - deque_free(&c); - - return 0; -} -- cgit v1.3