From 7d6b295c9e3f2ae3279039fb50f9e3bb0478074c Mon Sep 17 00:00:00 2001 From: Katharina Fey Date: Sat, 30 Jul 2016 21:26:43 +0200 Subject: Initial commit of the library --- .gitignore | 1 + CMakeLists.txt | 25 ++++ README | 20 +++ include/dtree/dyn_err.h | 29 +++++ include/dtree/dyn_tree.h | 77 ++++++++++++ lib/dyn_tree.c | 319 +++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 471 insertions(+) create mode 100644 CMakeLists.txt create mode 100644 README create mode 100644 include/dtree/dyn_err.h create mode 100644 include/dtree/dyn_tree.h create mode 100644 lib/dyn_tree.c diff --git a/.gitignore b/.gitignore index f805e81..de789df 100644 --- a/.gitignore +++ b/.gitignore @@ -31,3 +31,4 @@ # Debug files *.dSYM/ *.su +build/ diff --git a/CMakeLists.txt b/CMakeLists.txt new file mode 100644 index 0000000..6a90f6b --- /dev/null +++ b/CMakeLists.txt @@ -0,0 +1,25 @@ +############################################ +# +# libdyntree uses cmake because it's simple +# Build instructions can be found in the README +# +############################################ + +# Set some flags +cmake_minimum_required(VERSION 2.8.11) +set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c11") +set(CMAKE_BUILD_TYPE Debug) + +# Create our project for further reference +project(libdyntree) +set(DYN_TREE_SRC lib/dyn_tree.c) + +# Define our library in cmake +add_library(libdyntree STATIC ${DYN_TREE_SRC}) + +# Include the subdirectories to search for headers +target_include_directories(libdyntree PUBLIC "include") +target_include_directories(libdyntree PRIVATE "lib") + +# since the name starts with 'lib' dont add it again +set_target_properties(libdyntree PROPERTIES PREFIX "") diff --git a/README b/README new file mode 100644 index 0000000..c918f0e --- /dev/null +++ b/README @@ -0,0 +1,20 @@ +# libdyntree + +:tree: A dynamic n-ary tree to store recursive structures, key-value stores and single fields in a fast and comprehensive C datastructure. + +## 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 C11 but should be able to run on C99 or older. + +```console +$> mkdir build; cd build +$> cmake .. +$> make -j 2 +``` + +This will create a `.a` file. If you require a shared object, you can change the linking behaviour in the `CMakeLists.txt` file. + + +## How to use + +Using libdyntree is straighforward with a comprehensive API. Everything resolves around `dtree` objects and providing fields to API functions. Every function is documented as outlined in the header files. \ No newline at end of file diff --git a/include/dtree/dyn_err.h b/include/dtree/dyn_err.h new file mode 100644 index 0000000..23dae0f --- /dev/null +++ b/include/dtree/dyn_err.h @@ -0,0 +1,29 @@ + +/* Make sure we're not included multiple times */ +#ifndef _DYN_ERR_H +#define _DYN_ERR_H + +/* 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 dt_err { + + /* General purpose error codes */ + FAILURE = -1, + SUCCESS = 0, + + INVALID_PARAMS, + MALLOC_FAILED, + INVALID_PAYLOAD + +} dt_err; + +const char *rdb_error_getmsg(dt_err *e); + +#ifdef __cplusplus +} +#endif +#endif /* _DYN_ERR_H */ \ No newline at end of file diff --git a/include/dtree/dyn_tree.h b/include/dtree/dyn_tree.h new file mode 100644 index 0000000..e1db1d6 --- /dev/null +++ b/include/dtree/dyn_tree.h @@ -0,0 +1,77 @@ +/* + * 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 [recursive] + * child1 [recursive] + * key [literal] - "Username" + * value [literal] - "spacekookie" + * child2 [recursive] + * key [literal] - "Age" + * value [numerical] - 23 + * child3 + * subchild [recursive] + * ... + * + * Freeing the root node will free all children + */ + +#ifndef _DYNTREE_H_ +#define _DYNTREE_H_ + +#include "dyn_err.h" +#include + + +/* Also make sure we're _always_ interpreted as a C file */ +#ifdef __cplusplus +extern "C" { +#endif + +typedef enum { + UNSET, LITERAL, NUMERAL, RECURSIVE, PAIR +} dt_uni_t; + +typedef struct dtree { + dt_uni_t type; + size_t size, used; + union { + char *literal; + int numeral; + struct dtree *(*recursive); + } payload; +} dtree; + +/** Malloc a new dtree object */ +dt_err dtree_malloc(dtree *(*data)); + +dt_err dtree_resettype(dtree *data); + +/** Set the data element to a literal and save it's length */ +dt_err dtree_addliteral(dtree *data, const char *literal, size_t length); + +/** Set the data element to a numeral */ +dt_err dtree_addnumeral(dtree *data, int numeral); + +/** Add two new elements as a PAIR node under an existing node */ +dt_err dtree_addpair(dtree *data, dtree *(*key), dtree *(*value)); + +/** Add a new data element to the resursive data store */ +dt_err dtree_addrecursive(dtree *data, dtree *(*new_data)); + +dt_err dtree_get(dtree *data, void *(*val)); + +const char *dtree_dtype(dt_uni_t type); + +/** Prints*/ +void dtree_print(dtree *data); + +/** Will free all memory allocated by this element and it's children */ +dt_err dtree_free(dtree *data); + +#ifdef __cplusplus +} +#endif +#endif //_DYNTREE_H_ diff --git a/lib/dyn_tree.c b/lib/dyn_tree.c new file mode 100644 index 0000000..4665332 --- /dev/null +++ b/lib/dyn_tree.c @@ -0,0 +1,319 @@ +// Include our header file +#include + +// Runtime includes +#include +#include +#include +#include + +#define RDB_REC_DEF_SIZE 2 +#define RDB_REC_MULTIPLY 2 +#define REAL_STRLEN(str) (strlen(str) + 1) + +dt_err dtree_malloc(dtree *(*data)) +{ + (*data) = (dtree*) malloc(sizeof(dtree)); + if(*data == NULL) { + printf("Creating dtree object FAILED"); + return MALLOC_FAILED; + } + + memset(*data, 0, sizeof(dtree)); + + (*data)->type = UNSET; + return SUCCESS; +} + +dt_err dtree_resettype(dtree *data) +{ + if(data->type == LITERAL) { + if(data->payload.literal) free(data->payload.literal); + } else if(data->type == RECURSIVE || data->type == PAIR) { + + /* Iterate over all children and clear them */ + int i; + dt_err err; + for(i = 0; i < data->size; i++) { + err = dtree_free(data->payload.recursive[i]); + if(err) return err; + } + } + + /* Set the data type to unset */ + data->type = UNSET; + data->size = 0; + data->used = 0; + + return SUCCESS; +} + +dt_err dtree_addliteral(dtree *data, const char *literal, size_t length) +{ + /* Make sure we are a literal or unset data object */ + if(data->type != UNSET) + if(data->type != LITERAL) return INVALID_PAYLOAD; + + /* 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 dtree_addnumeral(dtree *data, int numeral) +{ + /* Make sure we are a literal or unset data object */ + if(data->type != UNSET) + if(data->type != NUMERAL) return INVALID_PAYLOAD; + + data->payload.numeral = numeral; + data->type = NUMERAL; + data->size = sizeof(int); + data->used = sizeof(int); + return SUCCESS; +} + +dt_err dtree_addrecursive(dtree *data, dtree *(*new_data)) +{ + /* Make sure we are a literal or unset data object */ + if(data->type != UNSET) + if(data->type != RECURSIVE) 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 + dtree **tmp = (dtree**) malloc(sizeof(dtree*) * data->size); + memcpy(tmp, data->payload.recursive, sizeof(dtree*) * data->used); + + /* Free the list WITHOUT the children! */ + free(data->payload.recursive); + data->payload.recursive = tmp; + } + + /* This means the data object is new */ + } else { + dtree **tmp = (dtree**) malloc(sizeof(dtree*) * data->size); + data->payload.recursive = tmp; + data->type = RECURSIVE; + data->used = 0; + data->size = RDB_REC_DEF_SIZE; + } + + err = dtree_malloc(new_data); + if(err) return err; + + /* Reference the slot, assign it, then move our ctr */ + data->payload.recursive[data->used] = *new_data; + data->used++; + + return SUCCESS; +} + +dt_err dtree_addpair(dtree *data, dtree *(*key), dtree *(*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 = dtree_malloc(key); + if(err) goto cleanup; + + err = dtree_malloc(value); + if(err) goto cleanup; + + /** Malloc space for PAIR */ + data->size = 2; + dtree **tmp = (dtree**) malloc(sizeof(dtree*) * data->size); + if(!tmp) goto cleanup; + + data->payload.recursive = tmp; + + { /* Assign data to new array */ + data->payload.recursive[data->used] = *key; + data->used++; + data->payload.recursive[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; +} + +void recursive_print(dtree *data, const char *offset) +{ + dt_uni_t type = data->type; + + switch(type) { + case UNSET: + printf("[NULL]\n"); + break; + case LITERAL: + printf("%s['%s']\n", offset, data->payload.literal); + break; + case NUMERAL: + printf("%s[%d]\n", offset, data->payload.numeral); + break; + case PAIR: + { + dt_uni_t k_type = data->payload.recursive[0]->type; + dt_uni_t v_type = data->payload.recursive[1]->type; + + if(k_type == LITERAL) printf("%s['%s']", offset, data->payload.recursive[0]->payload.literal); + if(k_type == NUMERAL) printf("%s[%d]", offset, data->payload.recursive[0]->payload.numeral); + + char new_offset[REAL_STRLEN(offset) + 2]; + strcpy(new_offset, offset); + strcat(new_offset, " "); + + if(k_type == RECURSIVE || k_type == PAIR) recursive_print(data->payload.recursive[0], new_offset); + + /* Print the value now */ + + if(k_type == LITERAL) printf(" => ['%s']\n", data->payload.recursive[1]->payload.literal); + if(k_type == NUMERAL) printf(" => [%d]\n", data->payload.recursive[1]->payload.numeral); + + if(k_type == RECURSIVE || k_type == PAIR) recursive_print(data->payload.recursive[1], new_offset); + } + break; + + case RECURSIVE: + { + int i; + printf("%s[RECURSIVE]\n", offset); + for(i = 0; i < data->used; i++) { + dt_uni_t type = data->payload.recursive[i]->type; + + + char new_offset[REAL_STRLEN(offset) + 2]; + strcpy(new_offset, offset); + strcat(new_offset, " "); + + if(type == LITERAL || type == NUMERAL) { + recursive_print(data->payload.recursive[i], new_offset); + continue; + } + + if(type == RECURSIVE) + { + recursive_print(data->payload.recursive[i], new_offset); + continue; + } + + if(type == PAIR) { + printf("%s[PAIR] <==> ", new_offset); + recursive_print(data->payload.recursive[i], new_offset); + } + } + break; + } + + default: + break; + + } +} + +void dtree_print(dtree *data) +{ + recursive_print(data, ""); +} + +dt_err dtree_get(dtree *data, void *(*val)) +{ + if(data->type == LITERAL) *val = (char*) data->payload.literal; + if(data->type == NUMERAL) *val = (int*) &data->payload.numeral; + if(data->type == RECURSIVE || data->type == PAIR) + *val = (dtree*) data->payload.recursive; + + return SUCCESS; +} + +dt_err dtree_free(dtree *data) +{ + if(data == NULL) return SUCCESS; + + if(data->type == LITERAL) { + if(data->payload.literal) free(data->payload.literal); + } else if(data->type == RECURSIVE || data->type == PAIR) { + int i; + dt_err err; + for(i = 0; i < data->size; i++) { + err = dtree_free(data->payload.recursive[i]); + if(err) return err; + } + + free(data->payload.recursive); + } + + free(data); + return SUCCESS; +} + +const char *dtree_dtype(dt_uni_t type) +{ + switch(type) { + case LITERAL: return "Literal"; + case NUMERAL: return "Numeral"; + case RECURSIVE: return "Recursive"; + default: return "Unknown"; + } +} + +/**************** PRIVATE UTILITY FUNCTIONS ******************/ + + +/** + * 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 dtree object to check + * @return + */ +dt_err data_check(dtree *data) +{ + /* Check if the data block has children */ + if(data->type == RECURSIVE) + { + printf("Won't override heap payload with data!"); + return INVALID_PAYLOAD; + } + + /* Free the existing string */ + if(data->type == LITERAL) + { + if(data->payload.literal) free(data->payload.literal); + } + + return SUCCESS; +} -- cgit v1.2.3