From 154874afda4a8df885e51c01f7681f04fb0b8e61 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sat, 9 Apr 2022 09:43:53 +0200 Subject: neue Verzeichnisstruktur --- src/deque.c | 485 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 485 insertions(+) create mode 100644 src/deque.c (limited to 'src/deque.c') diff --git a/src/deque.c b/src/deque.c new file mode 100644 index 0000000..881d1d3 --- /dev/null +++ b/src/deque.c @@ -0,0 +1,485 @@ +#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