diff options
| -rw-r--r-- | .gitignore | 34 | ||||
| -rw-r--r-- | CMakeLists.txt | 13 | ||||
| -rw-r--r-- | README | 51 | ||||
| -rw-r--r-- | array.c | 120 | ||||
| -rw-r--r-- | array.h | 27 | ||||
| -rw-r--r-- | bowl.c | 828 | ||||
| -rw-r--r-- | bowl.h | 413 | ||||
| -rw-r--r-- | data.c | 81 | ||||
| -rw-r--r-- | examples/list.c | 23 | ||||
| -rw-r--r-- | examples/tree.c | 46 | ||||
| -rw-r--r-- | main.c | 11 | ||||
| -rw-r--r-- | utils.c | 46 | ||||
| -rw-r--r-- | utils.h | 19 |
13 files changed, 512 insertions, 1200 deletions
@@ -1,34 +1,2 @@ -# Object files -*.o -*.ko -*.obj -*.elf - -# Precompiled Headers -*.gch -*.pch - -# Libraries -*.lib -*.a -*.la -*.lo - -# Shared objects (inc. Windows DLLs) -*.dll -*.so -*.so.* -*.dylib - -# Executables -*.exe -*.out -*.app -*.i*86 -*.x86_64 -*.hex - -# Debug files -*.dSYM/ -*.su build/ +.vscode/ diff --git a/CMakeLists.txt b/CMakeLists.txt index c68025a..5ab2f46 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -3,11 +3,16 @@ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c11") set(CMAKE_BUILD_TYPE Debug) project(bowl) -add_library(bowl SHARED bowl.c) +add_library(bowl SHARED bowl.c + data.c + utils.c + array.c) target_include_directories(bowl PUBLIC ".") -################### TESTING CODE BELOW ################### +################### EXAMPLES ################### +add_executable(ex_tree examples/tree.c) +target_link_libraries(ex_tree bowl) -add_executable(bowl_test main.c) -target_link_libraries(bowl_test bowl)
\ No newline at end of file +add_executable(ex_list examples/list.c) +target_link_libraries(ex_list bowl)
\ No newline at end of file @@ -1,19 +1,16 @@ -libdtree -======== +libbowl +======= The last C datastructure library you will use. Provides a versatile -tree-like structure that can act as lists, sets and more! Many -features are still experimental and the API might change at any point -so be aware. +structure that can act as lists, sets and more! + How to build ------------ -libdyntree is built with cmake. It has no external dependencies and -compilation has been tested with gcc 6+ on Linx systems. It was tested -with C99 but shouldbe able to compile with ANSI C as well. +An out-of-source build is recommended. -```console +``` $> mkdir build; cd build $> cmake .. $> make -j 2 @@ -22,42 +19,6 @@ $> make -j 2 This will create a `.so` file. If you require a static object, you can change the linking behaviour in the `CMakeLists.txt` file. -How to use ----------- - -Everything resolves around `dtree` objects and providing fields to API -functions. Generally, memory is managed for you by libdtree: - -```C -dt_err err; -dtree *data; -err = dtree_malloc(&data); -``` - -Alternatively you can use the shortcut alloc functions provided: - -```C -dtree *str_node = dtree_alloc_literal("My string in this node!"); -dtree *num_node = dtree_alloc_numeral(1337); - -dtree *key, *val; -dtree *pair_node = dtree *dtree_allocpair_new(&key, &val); -``` - -Nodes can change their type, provided they get reset before assigning -a different type of data to them first. The available types are listed -below: - - - Unset - - Literal - - Numerical - - Recursive - - Pair - - Pointer - -Some more advanced functions include a getter, a search, a keyed -search as well as tree merge and split functions. Please consult the -wiki for details on how to use some of these functions. License ------- @@ -0,0 +1,120 @@ +#include "bowl.h" +#include "array.h" +#include "utils.h" + +#include <malloc.h> + + +err_t array_malloc(struct bowl *self, size_t size) +{ + CHECK(self, INVALID_STATE) + CHECK((size > 0), INVALID_PARAMS) + + struct bowl_arr *arr = malloc(sizeof(struct bowl_arr)); + CHECK(arr, MALLOC_FAILED) + arr->size = 2; + arr->used = 0; + + struct bowl **ptr = calloc(sizeof(struct bowl *), arr->size); + CHECK(ptr, MALLOC_FAILED) + arr->ptr = ptr; + + self->_pl.array = arr; + return OK; +} + +err_t array_insert(struct bowl *self, struct bowl *new) +{ + CHECK(self, INVALID_PARAMS) + CHECK(new, INVALID_PARAMS) + + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + + err_t e = _array_rescale((void ***) &arr->ptr, &arr->size, arr->used); + if(e) return e; + + arr->ptr[arr->used++] = new; + return OK; +} + +err_t array_insert_key(struct bowl *self, size_t idx, struct bowl *new) +{ + CHECK(self, INVALID_PARAMS) + CHECK(new, INVALID_PARAMS) + + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + CHECK((idx < arr->used), INVALID_PARAMS) + + err_t e = _array_rescale((void ***) &arr->ptr, &arr->size, arr->used); + if(e) return e; + + for(int i = idx + 1; idx < arr->used; i++) + arr->ptr[i] = arr->ptr[i - 1]; + + arr->ptr[idx] = new; + arr->used++; + + return OK; +} + +err_t array_swap_key(struct bowl *self, size_t idx, struct bowl *new, struct bowl **old) +{ + CHECK(self, INVALID_PARAMS) + CHECK(new, INVALID_PARAMS) + + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + + (*old) = NULL; // Explicitly set to NULL if no such key + CHECK((idx < arr->used), INVALID_PARAMS) + + (*old) = arr->ptr[idx]; + arr->ptr[idx] = new; + + return OK; +} + +err_t array_remove(struct bowl *self, struct bowl *to_remove) +{ + CHECK(self, INVALID_PARAMS) + CHECK(to_remove, INVALID_PARAMS) + + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + + size_t idx; + err_t e = _array_search((void **) arr->ptr, arr->size, &idx, to_remove); + if(e) return e; + + e = _array_remove((void **) arr->ptr, idx, arr->size, NULL); + return e; +} + +err_t array_remove_key(struct bowl *self, size_t idx, struct bowl **out) +{ + CHECK(self, INVALID_PARAMS); + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + CHECK((idx < arr->used), INVALID_PARAMS) + + err_t e = _array_remove((void **) arr->ptr, idx, arr->size, (void **) out); + return e; +} + +err_t array_free(struct bowl *self) +{ + CHECK(self, INVALID_PARAMS) + struct bowl_arr *arr = self->_pl.array; + CHECK(arr, INVALID_STATE) + + for(int i = 0; i < arr->used; i++) { + err_t e = bowl_free(arr->ptr[i]); + if(e) break; + } + + free(arr->ptr); + free(arr); + return OK; +}
\ No newline at end of file @@ -0,0 +1,27 @@ +#ifndef _ARRAY_H_ +#define _ARRAY_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include "bowl.h" + +err_t array_malloc(struct bowl *, size_t); + +err_t array_insert(struct bowl *, struct bowl *); + +err_t array_insert_key(struct bowl *, size_t idx, struct bowl *); + +err_t array_swap_key(struct bowl *, size_t idx, struct bowl *, struct bowl **); + +err_t array_remove(struct bowl *, struct bowl *); + +err_t array_remove_key(struct bowl *, size_t, struct bowl **); + +err_t array_free(struct bowl *); + +#ifdef __cplusplus +} +#endif +#endif // _ARRAY_H_
\ No newline at end of file @@ -1,815 +1,123 @@ -// Include our header file #include "bowl.h" +#include "array.h" -// Runtime includes #include <stdlib.h> -#include <stdio.h> #include <memory.h> #include <stdbool.h> -#define RDB_REC_DEF_SIZE 2 -#define RDB_REC_MULTIPLY 2 +#define ARRAY_START_SIZE 2 +#define HASH_START_SIZE 24 -#define ORIGINAL (short) 0 -#define SHALLOW (short) 1 -#define DEEP (short) 2 - -/*** Forward declared functions ***/ - -int list_search(struct bowl**, struct bowl*, struct bowl*); - -void list_print(struct bowl *data, const char *offset); - -/******/ - -dt_err bowl_malloc(struct bowl *(*data)) -{ - (*data) = (struct bowl*) malloc(sizeof(struct bowl)); - if(*data == NULL) { - printf("Creating bowl object FAILED"); - return MALLOC_FAILED; - } - - memset(*data, 0, sizeof(struct bowl)); - - (*data)->type = UNSET; - return SUCCESS; -} - -dt_err bowl_resettype(struct bowl *data) -{ - if(data->type == LITERAL) { - if(data->payload.literal) free(data->payload.literal); - - } else if(data->type == LIST || data->type == PAIR) { - - /* Iterate over all children and clear them */ - int i; - dt_err err; - for(i = 0; i < data->size; i++) { - err = bowl_free(data->payload.list[i]); - if(err) return err; - } - } - - /* Set the data type to unset */ - data->type = UNSET; - data->encset = 0; - data->size = 0; - data->used = 0; - - /* Forcibly clean union memory to avoid bleeding data */ - memset(&data->payload, 0, sizeof(data->payload)); - - return SUCCESS; -} - -dt_err bowl_addliteral(struct bowl *data, const char *literal) -{ - /* Make sure we are a literal or unset data object */ - if(data->type != UNSET) - if(data->type != LITERAL) return INVALID_PAYLOAD; - - size_t length = REAL_STRLEN(literal); - - /* Get rid of previous data */ - if(data->payload.literal) free(data->payload.literal); - - /* Allocate space for the data */ - char *tmp = (char *) malloc(sizeof(char) * length); - if(tmp == NULL) { - printf("Allocating space for literal data FAILED"); - return MALLOC_FAILED; - } - - /* Copy the string over and store it in the union */ - strcpy(tmp, literal); - data->payload.literal = tmp; - data->type = LITERAL; - data->size = length; - data->used = length; - - return SUCCESS; -} - - -dt_err bowl_addpointer(struct bowl *data, void *ptr) -{ - if(data->type != UNSET) - if(data->type != POINTER) return INVALID_PAYLOAD; - - data->payload.pointer = ptr; - data->type = POINTER; - data->size = sizeof(ptr); - data->used = sizeof(ptr); - - return SUCCESS; -} - - -dt_err bowl_addnumeral(struct bowl *data, long numeral) -{ - /* Make sure we are a literal or unset data object */ - if(data->type != UNSET) - if(data->type != NUMERIC) return INVALID_PAYLOAD; - - data->payload.numeral = numeral; - data->type = NUMERIC; - data->size = sizeof(int); - data->used = sizeof(int); - return SUCCESS; -} - - -dt_err bowl_addboolean(struct bowl *data, bool b) -{ - /* Make sure we are a literal or unset data object */ - if(data->type != UNSET) - if(data->type != BOOLEAN) return INVALID_PAYLOAD; - - data->payload.boolean = b; - data->type = BOOLEAN; - data->size = sizeof(bool); - data->used = sizeof(bool); - return SUCCESS; -} - - -dt_err bowl_addlist(struct bowl *data, struct bowl *(*new_data)) -{ - /* Make sure we are a literal or unset data object */ - if(data->type != UNSET) - if(data->type != LIST) return INVALID_PAYLOAD; - - dt_err err; - - /* This means elements already exist */ - if(data->size > 0) { - - /* Used should never > size */ - if(data->used >= data->size) { - data->size += RDB_REC_MULTIPLY; - - // TODO Use Realloc - struct bowl **tmp = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - memcpy(tmp, data->payload.list, sizeof(struct bowl*) * data->used); - - /* Free the list WITHOUT the children! */ - free(data->payload.list); - data->payload.list = tmp; - } - - /* This means the data object is new */ - } else { - struct bowl **tmp = (struct bowl**) malloc(sizeof(struct bowl*) * RDB_REC_DEF_SIZE); - data->payload.list = tmp; - data->type = LIST; - data->used = 0; - data->size = RDB_REC_DEF_SIZE; - } - - err = bowl_malloc(new_data); - if(err) return err; - - /* Reference the slot, assign it, then move our ctr */ - data->payload.list[data->used++] = *new_data; - - return SUCCESS; -} - - -dt_err bowl_addpair(struct bowl *data, struct bowl *(*key), struct bowl *(*value)) -{ - /* Make sure we are a literal or unset data object */ - if(data->type != UNSET) return INVALID_PAYLOAD; - - dt_err err; - - /* Malloc two nodes */ - err = bowl_malloc(key); - if(err) goto cleanup; - - err = bowl_malloc(value); - if(err) goto cleanup; - - /** Malloc space for PAIR */ - data->size = 2; - struct bowl **tmp = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - if(!tmp) goto cleanup; - - data->payload.list = tmp; - - { /* Assign data to new array */ - data->payload.list[data->used] = *key; - data->used++; - data->payload.list[data->used] = *value; - data->used++; - } - - /* Assign our new type and return */ - data->type = PAIR; - return SUCCESS; - - /* Code we run when we can't allocate structs anymore */ - cleanup: - free(*key); - free(*value); - free(tmp); - return MALLOC_FAILED; -} - - -dt_err bowl_split_trees(struct bowl *data, struct bowl *sp) -{ - /* Make sure we are a literal or unset data object */ - if(data->type == UNSET) return INVALID_PAYLOAD; - - /* Check that sp is really a child of data */ - struct bowl *dp; - int ret = list_search(&dp, data, sp); - if(ret != 0) return DATA_NOT_RELATED; - if(dp == NULL) return NODE_NOT_FOUND; - - /* Find the exact list reference and remove it */ - int i; - for(i = 0; i < dp->used; i++) { - if(dp->payload.list[i] == NULL) continue; - - /* Manually remove the entry */ - if(dp->payload.list[i] == sp) { - dp->used--; - dp->payload.list[i] = NULL; - } - } - - return SUCCESS; -} - - -dt_err bowl_merge_trees(struct bowl *data, struct bowl *merge) -{ - /* REALLY make sure the type is correct */ - if(data->type == UNSET) return INVALID_PARAMS; - if(!(data->type == LIST || data->type == PAIR)) - return INVALID_PAYLOAD; - - /* This means elements already exist */ - if(data->size > 0) { - - /* Used should never > size */ - if(data->used >= data->size) { - data->size += RDB_REC_MULTIPLY; - - struct bowl **tmp = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - memcpy(tmp, data->payload.list, sizeof(struct bowl*) * data->used); - - /* Free the list WITHOUT the children! */ - free(data->payload.list); - data->payload.list = tmp; - } - - /* This means the data object is new */ - } else { - struct bowl **tmp = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - data->payload.list = tmp; - data->type = LIST; - data->used = 0; - data->size = RDB_REC_DEF_SIZE; - } - - /* Reference the slot, assign it, then move our ctr */ - data->payload.list[data->used] = merge; - data->used++; - - return SUCCESS; -} - - -dt_err bowl_copy_deep(struct bowl *data, struct bowl *(*copy)) -{ - if(data == NULL) return INVALID_PARAMS; - dt_err err = SUCCESS; - - int it_type = -1; - bowl_t type = data->type; - - /* Check if we're the first call */ - if((*copy) == NULL) bowl_malloc(copy); - (*copy)->copy = DEEP; - - switch(type) { - case LITERAL: - bowl_addliteral(*copy, data->payload.literal); - break; - - case NUMERIC: - bowl_addnumeral(*copy, data->payload.numeral); - break; - - case BOOLEAN: - bowl_addboolean(*copy, data->payload.boolean); - break; - - case LIST: - { - int i; - int num = (int) data->used; - - for(i = 0; i < num; i++) { - struct bowl *node = data->payload.list[i]; - - struct bowl *new; - bowl_addlist(*copy, &new); - bowl_copy_deep(node, &new); - } - - break; - } - - case PAIR: - { - struct bowl *key, *val; - bowl_addpair(*copy, &key, &val); - - struct bowl *orig_key = data->payload.list[0]; - struct bowl *orig_val = data->payload.list[1]; - - bowl_copy_deep(orig_key, &key); - bowl_copy_deep(orig_val, &val); - - break; - } - - case POINTER: - bowl_addpointer(*copy, data->payload.pointer); - break; - - default: - err = INVALID_PAYLOAD; - break; - } - - return err; -} - - -dt_err bowl_parent(struct bowl *root, struct bowl *data, struct bowl **parent) +void *_get_data(struct bowl *ptr) { - if(root == NULL || data == NULL) return INVALID_PARAMS; - - /* Blank the search pointer for easy error checking */ - (*parent) = NULL; - - switch(root->type) { - - /* Dead-end data stores automatically return @{NODE_NOT_FOUND} */ - case POINTER: - case LITERAL: - case BOOLEAN: - case NUMERIC: - return NODE_NOT_FOUND; - - case PAIR: - case LIST: - { - int i; - for(i = 0; i < root->used; i++) { - - /* Check if the node we're looking at is what we're searching for */ - if(root->payload.list[i] == data) { - (*parent) = root; - return SUCCESS; - } - - dt_err err = bowl_parent(root->payload.list[i], data, parent); - if(err == SUCCESS) return SUCCESS; - } - } - break; - - default: - return INVALID_PAYLOAD; + switch(ptr->type) { + case ARRAY | HASH: return ptr->_pl.array; + case LINKED: return ptr->_pl.linked; + case LEAF: return ptr->_pl.data; + default: return NULL; } - - return NODE_NOT_FOUND; } - -dt_err bowl_copy(struct bowl *data, struct bowl *(*copy)) +err_t bowl_malloc(struct bowl **ptr, bowl_t type) { - if(data == NULL) return INVALID_PARAMS; - dt_err err = SUCCESS; - - /* Allocate a new node */ - err = bowl_malloc(copy); - if(err) goto exit; - - /* Mark as shallow copy */ - (*copy)->copy = SHALLOW; - - /* Find out how to handle specific payloads */ - switch(data->type) { - case LITERAL: - err = bowl_addliteral(*copy, data->payload.literal); - break; + CHECK((type != 0), INVALID_PARAMS) - case NUMERIC: - err = bowl_addnumeral(*copy, data->payload.numeral); - break; + (*ptr) = malloc(sizeof(struct bowl)); + CHECK(*ptr, MALLOC_FAILED) - case BOOLEAN: - err = bowl_addboolean(*copy, data->payload.boolean); - break; + memset(*ptr, 0, sizeof(struct bowl)); + (*ptr)->type = type; - case LIST: - (*copy)->type = LIST; - (*copy)->payload.list = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - memcpy((*copy)->payload.list, data->payload.list, sizeof(struct bowl*) * data->used); - break; - - case PAIR: - (*copy)->type = PAIR; - (*copy)->payload.list = (struct bowl**) malloc(sizeof(struct bowl*) * data->size); - memcpy((*copy)->payload.list, data->payload.list, sizeof(struct bowl*) * data->used); - break; - - case POINTER: - (*copy)->type = POINTER; - memcpy((*copy)->payload.pointer, data->payload.pointer, sizeof(void*)); - break; - - default: - return INVALID_PAYLOAD; + switch((*ptr)->type) { + case LEAF: return OK; // No further allocation needed + case ARRAY: return array_malloc(*ptr, ARRAY_START_SIZE); + default: return INVALID_STATE; } - exit: - return err; + return OK; } - -dt_err bowl_search_payload(struct bowl *data, struct bowl *(*found), void *payload, bowl_t type) +err_t bowl_insert(struct bowl *self, struct bowl *new) { - if(data == NULL) return INVALID_PARAMS; - - /* Make sure our pointer is clean */ - *found = NULL; - - if(data->type == LIST|| data->type == PAIR) { - - int i; - for(i = 0; i < data->used; i++) { - dt_err err = bowl_search_payload(data->payload.list[i], found, payload, type); - if(err == SUCCESS) return SUCCESS; - } - - } else { - - /* Check the type aligns */ - if(data->type != type) return NODE_NOT_FOUND; - - switch(type) { - case LITERAL: - if(strcmp(data->payload.literal, (char*) payload) == 0) - *found = data; - break; - - case NUMERIC: - if(data->payload.numeral == (long) payload) - *found = data; - break; - - case BOOLEAN: - if(data->payload.boolean == (bool) payload) - *found = data; - break; - - case POINTER: - if(data->payload.pointer == payload) - *found = data; - break; - - default: return NODE_NOT_FOUND; - } - - } - - return (*found == NULL) ? NODE_NOT_FOUND : SUCCESS; -} - -// FIXME: This is horrible. Do via context? -static int reached = 0; -dt_err bowl_search_keypayload(struct bowl *data, struct bowl *(*found), void *payload, bowl_t type, int depth) -{ - if(data == NULL) return INVALID_PARAMS; - if(reached++ >= depth) return QUERY_TOO_DEEP; - - /* Make sure our pointer is clean */ - *found = NULL; - - /* We can only search LISTed values or PAIRs */ - if(data->type == PAIR) { - struct bowl *key = data->payload.list[0]; - - bowl_t tt; - int hit = -1; - - if(strcmp(key->payload.literal, (char*) payload) == 0) { - tt = LITERAL; - hit = 0; - } - - if(key->payload.numeral == (long) payload) { - tt = NUMERIC; - hit = 0; - } - - if(key->payload.boolean == (bool) payload) { - tt = BOOLEAN; - hit = 0; - } - - if(hit == 0) *found = data->payload.list[1]; - - } else if(data->type == LIST) { - - int i; - for(i = 0; i < data->used; i++) { - bowl_search_keypayload(data->payload.list[i], found, payload, type, depth); - } - - } else { - - - } - - if(data->type == LIST|| data->type == PAIR) { - - int i; - for(i = 0; i < data->used; i++) { - dt_err err = bowl_search_payload(data->payload.list[i], found, payload, type); - if(err == SUCCESS) return SUCCESS; - } - - } else { - - /* Check the type aligns */ - if(data->type != type) return NODE_NOT_FOUND; - - switch(type) { - case LITERAL: - if(strcmp(data->payload.literal, (char*) payload) == 0) - *found = data; - break; - - case NUMERIC: - if(data->payload.numeral == (long) payload) - *found = data; - break; + CHECK(self, INVALID_PARAMS) + CHECK(new, INVALID_PARAMS) - case BOOLEAN: - if(data->payload.boolean == (bool) payload) - *found = data; - - case POINTER: - if(data->payload.pointer == payload) - *found = data; - break; - - default: return NODE_NOT_FOUND; - } + switch(self->type) { + case LEAF: return INVALID_PARAMS; + case ARRAY: return array_insert(self, new); + default: return INVALID_STATE; } - return (*found == NULL) ? NODE_NOT_FOUND : SUCCESS; + return OK; } - -void list_print(struct bowl *data, const char *offset) +err_t bowl_insert_key(struct bowl *self, size_t idx, struct bowl *child) { - bowl_t type = data->type; - - switch(type) { - case UNSET: - printf("[NULL]\n"); - break; - - case LITERAL: - printf("%s['%s']\n", offset, data->payload.literal); - break; - - case NUMERIC: - printf("%s[%lu]\n", offset, data->payload.numeral); - break; - - case BOOLEAN: - printf("%s['%s']\n", offset, (data->payload.boolean) ? "TRUE" : "FALSE"); - break; - - case PAIR: - { - bowl_t k_type = data->payload.list[0]->type; - bowl_t v_type = data->payload.list[1]->type; - - if(k_type == LITERAL) printf("%s['%s']", offset, data->payload.list[0]->payload.literal); - if(k_type == NUMERIC) printf("%s[%lu]", offset, data->payload.list[0]->payload.numeral); - if(k_type == BOOLEAN) printf("%s[%s]", offset, (data->payload.list[0]->payload.boolean) ? "TRUE" : "FALSE"); - - char new_offset[REAL_STRLEN(offset) + 2]; - strcpy(new_offset, offset); - strcat(new_offset, " "); - - if(k_type == LIST || k_type == PAIR) list_print(data->payload.list[0], new_offset); - - /* Print the value now */ - if(v_type == LITERAL) printf(" => ['%s']\n", data->payload.list[1]->payload.literal); - if(v_type== NUMERIC) printf(" => [%lu]\n", data->payload.list[1]->payload.numeral); - if(v_type == BOOLEAN) printf(" => [%s]\n", (data->payload.list[1]->payload.boolean) ? "TRUE" : "FALSE"); - - if(v_type == LIST || k_type == PAIR) list_print(data->payload.list[1], new_offset); - - break; - } - - case LIST: - { - int i; - printf("%s[LIST]\n", offset); - for(i = 0; i < data->used; i++) { - bowl_t t = data->payload.list[i]->type; - - /* Calculate the new offset */ - char new_offset[REAL_STRLEN(offset) + 2]; - strcpy(new_offset, offset); - strcat(new_offset, " "); - - switch(t) { - case LITERAL: - case BOOLEAN: - case NUMERIC: - list_print(data->payload.list[i], new_offset); - continue; - - case LIST: - list_print(data->payload.list[i], new_offset); - continue; - - case PAIR: - printf("%s[PAIR] <==> ", new_offset); - list_print(data->payload.list[i], new_offset); - continue; - - default: - break; - } - } - break; - } + CHECK(self, INVALID_PARAMS) + CHECK(child, INVALID_PARAMS) + CHECK((idx >= 0), INVALID_PARAMS) - default: - break; + switch(self->type) { + case LEAF: return INVALID_PARAMS; + case ARRAY: return array_insert_key(self, idx, child); + default: return INVALID_STATE; } } - -void bowl_print(struct bowl *data) +err_t bowl_swap_key(struct bowl *self, size_t idx, struct bowl *child, struct bowl **prev) { - list_print(data, ""); -} + CHECK(self, INVALID_PARAMS) + CHECK(child, INVALID_PARAMS) + CHECK((idx >= 0), INVALID_PARAMS) -dt_err bowl_get(struct bowl *data, void *(*val)) -{ - if(data->type == LITERAL) *val = data->payload.literal; - if(data->type == NUMERIC) *val = &data->payload.numeral; - if(data->type == BOOLEAN) *val = &data->payload.boolean; - if(data->type == LIST || data->type == PAIR) *val = (struct bowl*) data->payload.list; - return SUCCESS; -} - - -dt_err bowl_free(struct bowl *data) -{ - if(data == NULL) return SUCCESS; - if(data->copy == SHALLOW) return NODE_NOT_ORIGINAL; + switch(self->type) { + case LEAF: return INVALID_PARAMS; + case ARRAY: return array_swap_key(self, idx, child, prev); - if(data->type == LITERAL) { - if(data->payload.literal) free(data->payload.literal); - - } else if(data->type == LIST || data->type == PAIR) { - int i; - dt_err err; - for(i = 0; i < data->used; i++) { - - err = bowl_free(data->payload.list[i]); - if(err) return err; - } - - free(data->payload.list); - - } else if(data->type == POINTER) { - if(data->copy != SHALLOW && data->payload.pointer) - free(data->payload.pointer); + default: return INVALID_STATE; } - - free(data); - return SUCCESS; } - -dt_err bowl_free_shallow(struct bowl *data) +err_t bowl_remove(struct bowl *self, struct bowl *child) { - if(data == NULL) return SUCCESS; + CHECK(self, INVALID_PARAMS) + CHECK(child, INVALID_PARAMS) - if(data->type == LITERAL) { - if(data->payload.literal) free(data->payload.literal); - } else if(data->type == LIST || data->type == PAIR) { - int i; - dt_err err; - for(i = 0; i < data->size; i++) { - err = bowl_free(data->payload.list[i]); - if(err) return err; - } + switch(self->type) { + case LEAF: return INVALID_PARAMS; + case ARRAY: return array_remove(self, child); - free(data->payload.list); + default: return INVALID_STATE; } - - free(data); - return SUCCESS; } - -const char *bowl_dtype(struct bowl *data) +err_t bowl_remove_key(struct bowl *self, size_t idx, struct bowl **prev) { - switch(data->type) { - case LITERAL: return "Literal"; - case NUMERIC: return "Numeric"; - case BOOLEAN: return "Boolean"; - case LIST: return "List"; - case PAIR: return "Pair"; - case POINTER: return "Pointer"; - default: return "Unknown"; - } -} + CHECK(self, INVALID_PARAMS) + CHECK((idx >= 0), INVALID_PARAMS) + switch(self->type) { + case LEAF: return INVALID_PARAMS; + case ARRAY: return array_remove_key(self, idx, prev); -/**************** PRIVATE UTILITY FUNCTIONS ******************/ - - -/** - * Steps down the list hirarchy of a dyntree node to - * find a sub-child target. Returns 0 if it can be found. - * - * @param data - * @param target - * @return - */ -int list_search(struct bowl **direct_parent, struct bowl *data, struct bowl *target) -{ - /* Check if data is actually valid */ - if(data == NULL) return 1; - - /* Compare the pointers :) */ - if(data == target) return 0; - - int res = 1; - if(data->type == LIST || data->type == PAIR) { - int i; - for(i = 0; i < data->used; i++) { - res = list_search(direct_parent, data->payload.list[i], target); - if(res == 0) { - - /* Save the node that contains our child for later */ - (*direct_parent) = data; - return res; - } - } + default: return INVALID_STATE; } - - return res; } - -/** - * Small utility function that checks if a datablock is valid to write into. - * Potentially releases previously owned memory to prevent memory leaks - * - * @param data The bowl object to check - * @return - */ -dt_err data_check(struct bowl *data) +err_t bowl_free(struct bowl *self) { - /* Check if the data block has children */ - if(data->type == LIST) - { - printf("Won't override heap payload with data!"); - return INVALID_PAYLOAD; - } + CHECK(self, INVALID_PARAMS) - /* Free the existing string */ - if(data->type == LITERAL) - { - if(data->payload.literal) free(data->payload.literal); + err_t e; + switch(self->type) { + case LEAF: e = data_free(self->_pl.data); break; + case ARRAY: e = array_free(self); break; + default: e = INVALID_STATE; break; } + if(e) return e; - return SUCCESS; + free(self); + return OK; } @@ -1,378 +1,97 @@ -/* - * Please use the API to create and destroy objects as only this way - * memory-safety and memory leaks can be guaranteed. - * - * With the API you can easily create structures like the following: - * - * root [list] - * child1 [list] - * key [literal] - "Username" - * value [literal] - "spacekookie" - * child2 [list] - * key [literal] - "Age" - * value [numerical] - 23 - * child3 - * subchild [list] - * ... - * - * Freeing the root node will free all children - */ - #ifndef _BOWL_H_ #define _BOWL_H_ +#ifdef __cplusplus +extern "C" { +#endif + #include <memory.h> #include <stdbool.h> -/* A helpful macro that can take care of \0 termated strings! */ #define REAL_STRLEN(str) (strlen(str) + 1) +#define CHECK(ptr, err) if(!ptr) return err; -/* Also make sure we're _always_ interpreted as a C file */ -#ifdef __cplusplus -extern "C" { -#endif - +/** Define some generic error codes first that we can propagate **/ +typedef enum err_t { + OK = 0, + ERR = -1, + NOT_IMPLEMENTED = 1, // A runtime error for missing features + + INVALID_PARAMS = 2, // A function didn't get the required parameters + MALLOC_FAILED = 3, // A memory allocation failed + INVALID_STATE = 4, // Calling an operation on an invalid state +} err_t; + +typedef enum data_t { + LITERAL, // Any string that is \0 terminated + INTEGER, // Integer value + REAL, // Floating point value + BOOLEAN, // A 1-byte boolean + RAW // A platform-length pointer +} data_t; -/* Type that determines what data is stored inside a tree-node */ typedef enum bowl_t { - UNSET, LITERAL, NUMERIC, LONG_NUMERIC, BOOLEAN, LIST, PAIR, POINTER + LEAF = 1, ARRAY, HASH, LINKED } bowl_t; - struct bowl { - bowl_t type; - short encset; - size_t size, used; - short copy; + bowl_t type; union { - char *literal; - bool boolean; - struct bowl *(*list); - void *pointer; -#ifdef __LONG_LONG_SUPPORT__ - long long numeral; -#else - long numeral; -#endif - - } payload; + struct data *data; + struct bowl_arr *array; + struct b_ptr *linked; + } _pl; }; +struct data { + data_t type; + union { + char *literal; + bool boolean; + long integer; + double real; + void *raw; + } _pl; +}; -/** Define some generic error codes first that we can propagate **/ -typedef enum dt_err { - - /* General purpose error codes */ - FAILURE = -1, - SUCCESS = 0, - - INVALID_PARAMS, // A function didn't get the required parameters - MALLOC_FAILED, // A memory allocation failed - INVALID_PAYLOAD, // The payload of a node is invalid - DATA_NOT_RELATED, // Tried to split non-related trees - NODE_NOT_FOUND, // The sought after node was not found - NODE_NOT_ORIGINAL, // Tried to free a node which was a shallow copy - QUERY_TOO_DEEP, - -} dt_err; - - -/** - * Malloc a new bowl object - * - * @param data Reference pointer to bowl element - * @return - */ -dt_err bowl_malloc(struct bowl *(*data)); - - -/** - * Reset the type of a node and free child data - * - * @param data - * @return - */ -dt_err bowl_resettype(struct bowl *data); - - -/** - * Set the data element to a literal and save it's length - * - * @param data Reference to a bowl object - * @param literal String to store - * @return - */ -dt_err bowl_addliteral(struct bowl *data, const char *literal); - - -/** - * Set the data element to a numeral - * - * @param data Reference to a bowl object - * @param numeral Number to store - * @return - */ -dt_err bowl_addnumeral(struct bowl *data, long numeral); - - -/** - * Set the data element to a boolean. Do you really - * need this? Consider using @bowl_add_numeral instead. - * - * @param data Reference to a bowl object - * @param b boolean value (true, false) - * @return - */ -dt_err bowl_addboolean(struct bowl *data, bool b); - - -/** - * Add two new elements as a PAIR node under an existing node - * - * @param data bowl node to become the sub-root - * @param key Reference pointer to the key node - * @param value Reference pointer to the value node - * @return - */ -dt_err bowl_addpair(struct bowl *data, struct bowl *(*key), struct bowl *(*value)); - - -/** - * Add a new data element to the resursive data store - * - * @param data Root reference - * @param new_data Reference pointer to a new bowl node - * @return - */ -dt_err bowl_addlist(struct bowl *data, struct bowl *(*new_data)); - - -/** - * This function enables you to store your own structures in a node. It however - * also requires you to do some of your own memory management. - * - * WARNING: Can leak memory if pointer is previously set! - * - * To make sure that this function CAN NOT leak memory you should run - * "bowl_resettype" on the root element to remove the pointer. - * - * Also make sure that no other part of your application will use the - * pointer at a later date! - * - * @param data Root reference - * @param ptr A pointer to store in this node - * @return - */ -dt_err bowl_addpointer(struct bowl *data, void *ptr); - - -/** - * This function takes two nodes as arguments. The nodes MUST be - * related or an error will be thrown. Both nodes will still - * be accessable after this operation but no longer be related to - * each other. - * - * The second node will be removed from the tree of the root node. - * - * - * - * @param data Root reference - * @param sp Subtree node related to root to split off - * @return - */ -dt_err bowl_split_trees(struct bowl *data, struct bowl *sp); - - -/** - * This function is very simmilar to dt_err "bowl_addlist" - * with the difference that it doesn't allocate new memory but instead - * works with existing nodes. - * - * You need to provide a ROOT node which is of type list. It will - * procede to add the second (merge) node into the child-list of the - * root data node - essentially making them related. - * - * This allows for very efficient tree merging. - * - * @param data Root reference - * @param merge Second root reference to merge - * @return - */ -dt_err bowl_merge_trees(struct bowl *data, struct bowl *merge); - - -/** - * You can use this function to search the structure of a root node to find the - * parent of the node you provide as "data". It will leave the search pointer - * blanked if the node can't be found in the structure. - * - * @param root Root reference to search - * @param data The node we are searching for - * @param parent The node parent we are interested in - * @return - */ -dt_err bowl_parent(struct bowl *root, struct bowl *data, struct bowl **parent); - - -/** - * Recursive tree search function that will return the first occurence match - * to a provided payload (with an exact type). If you have data duplication - * in your tree this _might_ return some false positives. - * - * @param data Root reference to search - * @param found Empty pointer to put found node into - * @param payload What should be found - * @param type What type of data should be found - * @return - */ -dt_err bowl_search_payload(struct bowl *data, struct bowl *(*found), void *payload, bowl_t type); - - -/** - * Much like #{bowl_search_payload} but limiting it's search to keys in a list structure of certain depth. - * This means that in a key-value store structure only top-level items can be searched or the entire - * depth of the tree (or any vaue in between) - * - * @param data - * @param found - * @param payload - * @param type - * @return - */ -dt_err bowl_search_keypayload(struct bowl *data, struct bowl *(*found), void *payload, bowl_t type, int depth); - - -/** - * Performs a deep copy of a data node hirarchy. Does not copy externally - * pointed structures. Does garuantee safety of hirarchy. - * - * @param data - * @param copy - * @return - */ -dt_err bowl_copy_deep(struct bowl *data, struct bowl *(*copy)); - - -/** - * Performs a copy operation on a single node. Copies the payload on a pointer - * level which means that strings and numbers will be duplicated whereas external - * pointers and lists will only be references to the original content. - * - * Freeing the copy has no effect on the original payloads stored in other - * nodes. - * - * @param data - * @param copy - * @return - */ -dt_err bowl_copy(struct bowl *data, struct bowl *(*copy)); - - -/** - * A retrieve function to get data back from a node that doesn't require - * you to manually access parts of the struct. - * - * Needs to be provided with a reference to a pointer that can then be - * written to. You can make the reference type specific if you know - * what kind of data you're expecting. Please however note that compiler - * errors might occur if you provide a wrong pointer type. - * - * @param data Node reference to access - * @param val Reference pointer to write into - * @return - */ -dt_err bowl_get(struct bowl *data, void *(*val)); - - -/** - * Return the type of a node as plain text - * - * @param data - * @return - */ -const char *bowl_dtype(struct bowl *data); - - -/** - * Prints the data bowl object and all of its children - * - * @param data - */ -void bowl_print(struct bowl *data); - - -/** - * Will free the data reference and all of it's children. It will however NOT - * touch pointers to objects that weren't allocated by libdyntree! - * - * @param data - * @return - */ -dt_err bowl_free_shallow(struct bowl *data); +struct bowl_arr { + size_t size, used; + struct bowl **ptr; +}; +struct b_ptr { + struct bowl *self; + struct b_ptr *next; +}; -/** - * Like #{bowl_free_shallow} but will also remove structs that - * weren't allocated by libdyntree. Will throw warnings when trying - * to free payloads from shallow copy nodes - * - * @param data - * @return - */ -dt_err bowl_free(struct bowl *data); +/// Allocate memory for an new, empty bowl node +err_t bowl_malloc(struct bowl **, bowl_t); +/// Insert one node into another +err_t bowl_insert(struct bowl *, struct bowl *); -/************************** - * - * Error handling functions - * - **************************/ +/// Insert a node into a specific index of another node +err_t bowl_insert_key(struct bowl *, size_t idx, struct bowl *); -const char *bowl_err_getmsg(dt_err *e); +/// Insert and swap a key in place, returning the old one +err_t bowl_swap_key(struct bowl *, size_t idx, struct bowl *, struct bowl **); -/*************************** - * - * Encoding/ Decoding support hooks - * - ***************************/ +/// Remove a bowl node by it's pointer reference +err_t bowl_remove(struct bowl *, struct bowl *); -/** - * This function sets the wanted encoding setting on a - * root node (and assumes for children). Without setting flags via - * this function first the encode will fail. - * - * @param data Root reference - * @param setting Look at DYNTREE_JSON flags for options - * @return - */ -dt_err bowl_encode_set(struct bowl *data, short setting); +/// Removing a bowl node with a key +err_t bowl_remove_key(struct bowl *, size_t idx, struct bowl **); -/** - * A simple list node walker that encodes a dyn_tree node hirarchy - * into a json string. Requires the encoding setting to be set on the - * root node in order to successfully encode. - * - * Can throw errors and initialise NULL return string. - * - * @param data - * @param json_data - * @return - */ -dt_err bowl_encode_json(struct bowl *data, char *json_data); +/// Cascade-free memory from a bowl node +err_t bowl_free(struct bowl *); +/// Allocate memory for a new data node +err_t data_malloc(struct bowl **, data_t, ...); -/** - * Decodes a json string into a dyn_tree node hirarchy while providing - * memory safety and error checking. Will gracefully return errors - * if the provided json string is invalid or contains errors. - * - * @param data New root reference - * @param json_data Input json string - * @return - */ -dt_err bowl_decode_json(struct bowl *(*data), const char *json_data, size_t len); +/// Free all data node memory +err_t data_free(struct data *); #ifdef __cplusplus } #endif -#endif //_DYNTREE_H_ +#endif // _BOWL_H_
\ No newline at end of file @@ -0,0 +1,81 @@ +#include "bowl.h" + +#include <stdlib.h> +#include <memory.h> +#include <stdbool.h> +#include <stdarg.h> + +/// Allocate memory for a new data node +err_t data_malloc(struct bowl **self, data_t type, ...) +{ + err_t e; + va_list args; + + struct data *d = calloc(sizeof(struct data), 1); + CHECK(d, MALLOC_FAILED) + d->type = type; + + va_start(args, type); + switch(type) { + case LITERAL: { + char *lit = va_arg(args, char *); + size_t len = REAL_STRLEN(lit); + + d->_pl.literal = calloc(sizeof(char), len); + if(!d->_pl.literal) { + e = MALLOC_FAILED; + goto fail; + } + + strcpy(d->_pl.literal, lit); + break; + }; + case INTEGER: { + int i = va_arg(args, long); + d->_pl.integer = i; + break; + } + case REAL: { + int r = va_arg(args, double); + d->_pl.real = r; + break; + } + case BOOLEAN: { + int b = va_arg(args, int); + d->_pl.boolean = (bool) b; + break; + } + case RAW: { + void *raw = va_arg(args, void *); + d->_pl.raw = raw; + break; + } + default: e = INVALID_PARAMS; goto fail; + } + va_end(args); + + e = bowl_malloc(self, LEAF); + if(e) goto fail; + + (*self)->_pl.data = d; + return OK; + +fail: + if(d->type == LITERAL && d->_pl.literal) free(d->_pl.literal); + if(*self) bowl_free(*self); + if(d) free(d); + return e; +} + +/// Free all data node memory +err_t data_free(struct data *self) +{ + CHECK(self, INVALID_PARAMS) + switch(self->type) { + case LITERAL: free(self->_pl.literal); break; + default: break; + } + + free(self); + return OK; +} diff --git a/examples/list.c b/examples/list.c new file mode 100644 index 0000000..a09588b --- /dev/null +++ b/examples/list.c @@ -0,0 +1,23 @@ +#include <bowl.h> + +int main() +{ + + // Root node which contains a list + struct bowl *root; + bowl_malloc(&root, ARRAY); + + struct bowl *a; + data_malloc(&a, LITERAL, "Destroy capitalism"); + bowl_insert(root, a); + + struct bowl *b; + data_malloc(&b, INTEGER, 1312); + bowl_insert(root, b); + + struct bowl *c; + data_malloc(&c, LITERAL, "Alerta, Antifascista!"); + bowl_insert(root, c); + + return bowl_free(root); +}
\ No newline at end of file diff --git a/examples/tree.c b/examples/tree.c new file mode 100644 index 0000000..e55acb9 --- /dev/null +++ b/examples/tree.c @@ -0,0 +1,46 @@ +#include <bowl.h> + +int main() +{ + err_t e; + + // Initialise a root node + struct bowl *root; + e = bowl_malloc(&root, ARRAY); + if(e) return e; + + // First Node + struct bowl *a; + e = data_malloc(&a, LITERAL, "Destroy capitalism"); + if(e) return e; + + // Second Node + struct bowl *b; + e = data_malloc(&b, INTEGER, 1312); + if(e) return e; + + // Third node is another ARRAY + struct bowl *c; + e = bowl_malloc(&c, ARRAY); + if(e) return e; + + // Fourth node is another string + struct bowl *d; + e = data_malloc(&d, LITERAL, "Alerta, Antifascista!"); + if(e) return e; + + // Add the d node to c + e = bowl_insert(c, d); + if(e) e; + + // Add other nodes to root + e = bowl_insert(root, a); + if(e) return e; + e = bowl_insert(root, b); + if(e) return e; + e = bowl_insert(root, c); + if(e) return e; + + e = bowl_free(root); + return e; +}
\ No newline at end of file @@ -1,11 +0,0 @@ -// Some static tests - -#include <stdio.h> -#include <string.h> -// #include <bowl.h> - -int main(int argn, char **argv) -{ - - return 0; -}
\ No newline at end of file @@ -0,0 +1,46 @@ +#include <stdlib.h> +#include <stdio.h> +#include "utils.h" + +#define DELTA 0x2 +#define OVERSHOOT 0x8 + +err_t _array_rescale(void ***ptr, size_t *len, size_t use) +{ + CHECK(len, INVALID_PARAMS) + CHECK((use <= *len), INVALID_PARAMS) + CHECK(ptr, INVALID_PARAMS) + + // This is a simple linear scale strategy + if ((int) (*len - OVERSHOOT) >= (int) (use + DELTA)) *len -= OVERSHOOT; + if (use + DELTA >= *len) *len += DELTA; + + *ptr = realloc(*ptr, *len * sizeof(void *)); + return OK; +} + +err_t _array_search(void **ptr, size_t len, size_t *out, void *in) +{ + CHECK(ptr, INVALID_PARAMS) + CHECK(in, INVALID_PARAMS) + CHECK((len > 0), INVALID_PARAMS) + (*out) = -1; + + for(int i = 0; i < len; i++) + if((*ptr) == in) (*out) = i; + + return OK; +} + +err_t _array_remove(void **ptr, size_t idx, size_t len, void **out) +{ + CHECK(ptr, INVALID_PARAMS) + CHECK((idx >= 0), INVALID_PARAMS) + CHECK((len > idx), INVALID_PARAMS) + + if(out != NULL) (*out) = ptr[idx]; + for(int i = idx + 1; idx < len; i++) + ptr[i - 1] = ptr[i]; + + return OK; +} @@ -0,0 +1,19 @@ +#ifndef _UTIL_H_ +#define _UTIL_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include "bowl.h" + +err_t _array_rescale(void ***, size_t *len, size_t use); + +err_t _array_search(void **, size_t, size_t *out, void *in); + +err_t _array_remove(void **, size_t idx, size_t len, void **out); + +#ifdef __cplusplus +} +#endif +#endif // _UTIL_H_
\ No newline at end of file |