From caad27814fab468f66de0a3138e3900342d3acde Mon Sep 17 00:00:00 2001 From: Katharina Fey Date: Sat, 27 Aug 2016 01:07:35 +0200 Subject: API Changes. - Renaming the recursive field to "list" functions - Renaming main file to dtree for less confusion - Allowing for long values to be stored - not just integers - Adjusting quick access functions to use new API --- include/dtree/dtree.h | 414 +++++++++++++++++++++++++++++++++ include/dtree/dyn_tree.h | 382 ------------------------------- lib/dtree.c | 581 +++++++++++++++++++++++++++++++++++++++++++++++ lib/dyn_tree.c | 520 ------------------------------------------ 4 files changed, 995 insertions(+), 902 deletions(-) create mode 100644 include/dtree/dtree.h delete mode 100644 include/dtree/dyn_tree.h create mode 100644 lib/dtree.c delete mode 100644 lib/dyn_tree.c diff --git a/include/dtree/dtree.h b/include/dtree/dtree.h new file mode 100644 index 0000000..b46b000 --- /dev/null +++ b/include/dtree/dtree.h @@ -0,0 +1,414 @@ +/* + * 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 + +/* A helpful macro that can take care of \0 termated strings! */ +#define REAL_STRLEN(str) (strlen(str) + 1) + +#define DYNTREE_ENCODE_NONE 0x0 +#define DYNTREE_JSON_MINIFIED 0xA +#define DYNTREE_JSON_HUMAN 0xB + +/* Also make sure we're _always_ interpreted as a C file */ +#ifdef __cplusplus +extern "C" { +#endif + + +/* Type that determines what data is stored inside a tree-node */ +typedef enum dt_uni_t { + UNSET, LITERAL, NUMERAL, RECURSIVE, PAIR, POINTER +} dt_uni_t; + + +typedef struct dtree { + dt_uni_t type; + short encset; + size_t size, used; + short copy; + union { + char *literal; + long numeral; + struct dtree *(*recursive); + void *pointer; + } payload; +} dtree; + + +/** 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, + DATA_NOT_RELATED, + NODE_NOT_FOUND, + +} dt_err; + + +/** + * Malloc a new dtree object + * + * @param data Reference pointer to dtree element + * @return + */ +dt_err dtree_malloc(dtree *(*data)); + + +/** + * Reset the type of a node and free child data + * + * @param data + * @return + */ +dt_err dtree_resettype(dtree *data); + + +/** + * Set the data element to a literal and save it's length + * + * @param data Reference to a dtree object + * @param literal String to store + * @param length TRUE string length to use. + * @return + */ +dt_err dtree_addliteral(dtree *data, const char *literal); + + +/** + * Set the data element to a numeral + * + * @param data Reference to a dtree object + * @param numeral Number to store + * @return + */ +dt_err dtree_addnumeral(dtree *data, long numeral); + + +/** + * Add two new elements as a PAIR node under an existing node + * + * @param data dtree 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 dtree_addpair(dtree *data, dtree *(*key), dtree *(*value)); + + +/** + * Add a new data element to the resursive data store + * + * @param data Root reference + * @param new_data Reference pointer to a new dtree node + * @return + */ +dt_err dtree_addlist(dtree *data, dtree *(*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 + * "dtree_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 dtree_addpointer(dtree *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 dtree_split_trees(dtree *data, dtree *sp); + + +/** + * This function is very simmilar to dt_err "dtree_addrecursive" + * 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 recursive. 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 dtree_merge_trees(dtree *data, dtree *merge); + + +/** + * 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 dtree_search_payload(dtree *data, dtree *(*found), void *payload, dt_uni_t type); + + +/** + * 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 dtree_deep_copy(dtree *data, dtree *(*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 dtree_copy(dtree *data, dtree *(*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 or leave it as a void* to let + * libdyntree do the casting for you. + * + * @param data Node reference to access + * @param val Reference pointer to write into + * @return + */ +dt_err dtree_get(dtree *data, void *(*val)); + + +/** + * Return the type of a node as plain text + * + * @param data + * @return + */ +const char *dtree_dtype(dtree *data); + + +/** + * Prints the data dtree object and all of its children + * + * @param data + */ +void dtree_print(dtree *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 dtree_free_shallow(dtree *data); + + +/** + * Like #{dtree_free_shallow} but will also remove structs that + * weren't allocated by libdyntree + * + * @param data + * @return + */ +dt_err dtree_free(dtree *data); + + +/************************** + * + * Error handling functions + * + **************************/ + +const char *dtree_err_getmsg(dt_err *e); + +/*************************** + * + * Encoding/ Decoding support hooks + * + ***************************/ + +/** + * 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 dtree_encode_set(dtree *data, short setting); + +/** + * A simple recursive 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 dtree_encode_json(dtree *data, char *json_data); + + +/** + * 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 dtree_decode_json(dtree *(*data), const char *json_data); + + + +/*** Some helper functions for more non-C oriented developers ***/ + +/** + * Shortcut function that allocates a new string node. Beware however: + * + * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! + * + * @param string + * @return + */ +static dtree *dtree_alloc_literal(const char *string) +{ + dtree *node; + dtree_malloc(&node); + dtree_addliteral(node, string); + return node; +} + +/** + * Shortcut function that allocates a new numerical node. + * Beware however: + * + * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! + * + * @param num + * @return + */ +static dtree *dtree_alloc_numeral(const long num) +{ + dtree *node; + dtree_malloc(&node); + dtree_addnumeral(node, num); + return node; +} + +/** + * Shortcut function which creates two nodes as pair under a root + * node which is returned. Beware however: + * + * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! + * + @param key Will be the key node + * @param val Will be the value node + * @return New root node with key-val children + */ +static dtree *dtree_allocpair_new(dtree **key, dtree **val) +{ + dtree *root; + dtree_malloc(&root); + dtree_addpair(root, key, val); + return root; +} + + +/** + * Shortcut function which allocates a list of nodes in a list under + * a root node recursively. + * + * WARNING: Return value is allocated on heap. MUST FREE MANUALLY! + * WARNING: THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! + * + * @param root + * @param count + * @return + */ +static dtree **dtree_alloc_listlist(dtree **root, unsigned int count) +{ + dtree **nodes = malloc(sizeof(dtree**) * count); + + dtree_malloc(root); + + int i; + for(i = 0; i < count; i++) + dtree_addlist(*root, &nodes[i]); + + return nodes; +} + +#ifdef __cplusplus +} +#endif +#endif //_DYNTREE_H_ diff --git a/include/dtree/dyn_tree.h b/include/dtree/dyn_tree.h deleted file mode 100644 index 42aa378..0000000 --- a/include/dtree/dyn_tree.h +++ /dev/null @@ -1,382 +0,0 @@ -/* - * 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 - -/* A helpful macro that can take care of \0 termated strings! */ -#define REAL_STRLEN(str) (strlen(str) + 1) - -#define DYNTREE_ENCODE_NONE 0x0 -#define DYNTREE_JSON_MINIFIED 0xA -#define DYNTREE_JSON_HUMAN 0xB - -/* Also make sure we're _always_ interpreted as a C file */ -#ifdef __cplusplus -extern "C" { -#endif - - -/* Type that determines what data is stored inside a tree-node */ -typedef enum dt_uni_t { - UNSET, LITERAL, NUMERAL, RECURSIVE, PAIR, POINTER -} dt_uni_t; - - -typedef struct dtree { - dt_uni_t type; - short encset; - size_t size, used; - union { - char *literal; - long numeral; - struct dtree *(*recursive); - void *pointer; - } payload; -} dtree; - - -/** 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, - DATA_NOT_RELATED, - NODE_NOT_FOUND, - -} dt_err; - - -/** - * Malloc a new dtree object - * - * @param data Reference pointer to dtree element - * @return - */ -dt_err dtree_malloc(dtree *(*data)); - - -/** - * Reset the type of a node and free child data - * - * @param data - * @return - */ -dt_err dtree_resettype(dtree *data); - - -/** - * Set the data element to a literal and save it's length - * - * @param data Reference to a dtree object - * @param literal String to store - * @param length TRUE string length to use. - * @return - */ -dt_err dtree_addliteral(dtree *data, const char *literal, size_t length); - - -/** - * Set the data element to a numeral - * - * @param data Reference to a dtree object - * @param numeral Number to store - * @return - */ -dt_err dtree_addnumeral(dtree *data, int numeral); - - -/** - * Add two new elements as a PAIR node under an existing node - * - * @param data dtree 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 dtree_addpair(dtree *data, dtree *(*key), dtree *(*value)); - - -/** - * Add a new data element to the resursive data store - * - * @param data Root reference - * @param new_data Reference pointer to a new dtree node - * @return - */ -dt_err dtree_addrecursive(dtree *data, dtree *(*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 - * "dtree_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 dtree_addpointer(dtree *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 dtree_split_trees(dtree *data, dtree *sp); - -/** - * This function is very simmilar to dt_err "dtree_addrecursive" - * 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 recursive. 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 dtree_merge_trees(dtree *data, dtree *merge); - - -/** - * 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 dtree_search_payload(dtree *data, dtree *(*found), void *payload, dt_uni_t type); - -/** - * 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 or leave it as a void* to let - * libdyntree do the casting for you. - * - * @param data Node reference to access - * @param val Reference pointer to write into - * @return - */ -dt_err dtree_get(dtree *data, void *(*val)); - - -/** - * Return the type of a node as plain text - * - * @param data - * @return - */ -const char *dtree_dtype(dtree *data); - - -/** - * Prints the data dtree object and all of its children - * - * @param data - */ -void dtree_print(dtree *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 dtree_free_shallow(dtree *data); - -/** - * Like #{dtree_free_shallow} but will also remove structs that - * weren't allocated by libdyntree - * - * @param data - * @return - */ -dt_err dtree_free(dtree *data); - -/************************** - * - * Error handling functions - * - **************************/ - -const char *dtree_err_getmsg(dt_err *e); - -/*************************** - * - * Encoding/ Decoding support hooks - * - ***************************/ - -/** - * 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 dtree_encode_set(dtree *data, short setting); - -/** - * A simple recursive 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 dtree_encode_json(dtree *data, char *json_data); - - -/** - * 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 dtree_decode_json(dtree *(*data), const char *json_data); - - - -/*** Some helper functions for more non-C oriented developers ***/ - -/** - * Shortcut function that allocates a new string node. Beware however: - * - * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! - * - * @param string - * @return - */ -static dtree *dtree_alloc_literal(const char *string) -{ - dtree *node; - dtree_malloc(&node); - dtree_addliteral(node, string, REAL_STRLEN(string)); - return node; -} - -/** - * Shortcut function that allocates a new numerical node. - * Beware however: - * - * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! - * - * @param num - * @return - */ -static dtree *dtree_alloc_numeral(const long num) -{ - dtree *node; - dtree_malloc(&node); - dtree_addnumeral(node, num); - return node; -} - -/** - * Shortcut function which creates two nodes as pair under a root - * node which is returned. Beware however: - * - * THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! - * - @param key Will be the key node - * @param val Will be the value node - * @return New root node with key-val children - */ -static dtree *dtree_allocpair_new(dtree **key, dtree **val) -{ - dtree *root; - dtree_malloc(&root); - dtree_addpair(root, key, val); - return root; -} - - -/** - * Shortcut function which allocates a list of nodes in a list under - * a root node recursively. - * - * WARNING: Return value is allocated on heap. MUST FREE MANUALLY! - * WARNING: THIS FUNCTION DOES NOT RETURN WARNINGS OR ERROR CODES! - * - * @param root - * @param count - * @return - */ -static dtree **dtree_alloc_reclist(dtree **root, unsigned int count) -{ - dtree **nodes = malloc(sizeof(dtree**) * count); - - dtree_malloc(root); - - int i; - for(i = 0; i < count; i++) - dtree_addrecursive(*root, &nodes[i]); - - return nodes; -} - -#ifdef __cplusplus -} -#endif -#endif //_DYNTREE_H_ diff --git a/lib/dtree.c b/lib/dtree.c new file mode 100644 index 0000000..746ca13 --- /dev/null +++ b/lib/dtree.c @@ -0,0 +1,581 @@ +// Include our header file +#include + +// Runtime includes +#include +#include +#include +#include + +#define RDB_REC_DEF_SIZE 2 +#define RDB_REC_MULTIPLY 2 + +#define ORIGINAL (short) 0 +#define SHALLOW (short) 1 +#define DEEP (short) 2 + +/*** Forward declared functions ***/ + +int recursive_search(dtree**, dtree *, dtree *); + +/******/ + + +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->encset = DYNTREE_ENCODE_NONE; + data->size = 0; + data->used = 0; + + return SUCCESS; +} + +dt_err dtree_addliteral(dtree *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 dtree_addpointer(dtree *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 dtree_addnumeral(dtree *data, long 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_addlist(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; +} + + +dt_err dtree_split_trees(dtree *data, dtree *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 */ + dtree *dp; + int ret = recursive_search(&dp, data, sp); + if(ret != 0) return DATA_NOT_RELATED; + if(dp == NULL) return NODE_NOT_FOUND; + + /* Find the exact recursive reference and remove it */ + int i; + for(i = 0; i < dp->used; i++) { + if(dp->payload.recursive[i] == NULL) continue; + + /* Manually remove the entry */ + if(dp->payload.recursive[i] == sp) { + dp->used--; + dp->payload.recursive[i] = NULL; + } + } + + return SUCCESS; +} + + +dt_err dtree_merge_trees(dtree *data, dtree *merge) +{ + /* REALLY make sure the type is correct */ + if(data->type == UNSET) return INVALID_PARAMS; + if(!(data->type == RECURSIVE || 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; + + 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; + } + + /* Reference the slot, assign it, then move our ctr */ + data->payload.recursive[data->used] = merge; + data->used++; + + return SUCCESS; +} + + +dt_err dtree_deep_copy(dtree *data, dtree *(*copy)) +{ + if(data == NULL) return INVALID_PARAMS; + + return SUCCESS; +} + +dt_err dtree_copy(dtree *data, dtree *(*copy)) +{ + if(data == NULL) return INVALID_PARAMS; + dt_err err = SUCCESS; + + /* Allocate a new node */ + err = dtree_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 = dtree_addliteral(*copy, data->payload.literal); + break; + + case NUMERAL: + err = dtree_addnumeral(*copy, data->payload.numeral); + break; + + case RECURSIVE: + (*copy)->type = RECURSIVE; + (*copy)->payload.recursive = (dtree**) malloc(sizeof(dtree*) * data->size); + memcpy((*copy)->payload.recursive, data->payload.recursive, sizeof(dtree*) * data->used); + break; + + case PAIR: + (*copy)->type = PAIR; + (*copy)->payload.recursive = (dtree**) malloc(sizeof(dtree*) * data->size); + memcpy((*copy)->payload.recursive, data->payload.recursive, sizeof(dtree*) * data->used); + break; + + case POINTER: + (*copy)->type = POINTER; + memcpy((*copy)->payload.pointer, data->payload.pointer, sizeof(void*)); + break; + + default: + return INVALID_PAYLOAD; + } + + exit: + return err; +} + + +dt_err dtree_search_payload(dtree *data, dtree *(*found), void *payload, dt_uni_t type) +{ + if(data == NULL) return INVALID_PARAMS; + + /* Make sure our pointer is clean */ + *found = NULL; + + if(data->type == RECURSIVE|| data->type == PAIR) { + + int i; + for(i = 0; i < data->used; i++) { + dt_err err = dtree_search_payload(data->payload.recursive[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 NUMERAL: + if(data->payload.numeral == (long) 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; +} + + +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[%lu]\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[%lu]", 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(" => [%lu]\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 t = data->payload.recursive[i]->type; + + + char new_offset[REAL_STRLEN(offset) + 2]; + strcpy(new_offset, offset); + strcat(new_offset, " "); + + if(t == LITERAL || t == NUMERAL) { + recursive_print(data->payload.recursive[i], new_offset); + continue; + } + + if(t == RECURSIVE) + { + recursive_print(data->payload.recursive[i], new_offset); + continue; + } + + if(t == 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->used; i++) { + err = dtree_free(data->payload.recursive[i]); + if(err) return err; + } + + free(data->payload.recursive); + + } else if(data->type == POINTER) { + if(data->payload.pointer) free(data->payload.pointer); + } + + free(data); + return SUCCESS; +} + + +dt_err dtree_free_shallow(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(dtree *data) +{ + switch(data->type) { + case LITERAL: return "Literal"; + case NUMERAL: return "Numeral"; + case RECURSIVE: return "Recursive"; + case PAIR: return "Pair"; + case POINTER: return "Pointer"; + default: return "Unknown"; + } +} + +/**************** PRIVATE UTILITY FUNCTIONS ******************/ + +/** + * Steps down the recursive hirarchy of a dyntree node to + * find a sub-child target. Returns 0 if it can be found. + * + * @param data + * @param target + * @return + */ +int recursive_search(dtree **direct_parent, dtree *data, dtree *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 == RECURSIVE || data->type == PAIR) { + int i; + for(i = 0; i < data->used; i++) { + res = recursive_search(direct_parent, data->payload.recursive[i], target); + if(res == 0) { + + /* Save the node that contains our child for later */ + (*direct_parent) = data; + return res; + } + } + } + + 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 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; +} diff --git a/lib/dyn_tree.c b/lib/dyn_tree.c deleted file mode 100644 index 49cfd78..0000000 --- a/lib/dyn_tree.c +++ /dev/null @@ -1,520 +0,0 @@ -// Include our header file -#include - -// Runtime includes -#include -#include -#include -#include - -#define RDB_REC_DEF_SIZE 2 -#define RDB_REC_MULTIPLY 2 - -/*** Forward declared functions ***/ - -int recursive_search(dtree**, dtree *, dtree *); - -/******/ - - -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->encset = DYNTREE_ENCODE_NONE; - 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_addpointer(dtree *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 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; -} - - -dt_err dtree_split_trees(dtree *data, dtree *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 */ - dtree *dp; - int ret = recursive_search(&dp, data, sp); - if(ret != 0) return DATA_NOT_RELATED; - if(dp == NULL) return NODE_NOT_FOUND; - - /* Find the exact recursive reference and remove it */ - int i; - for(i = 0; i < dp->used; i++) { - if(dp->payload.recursive[i] == NULL) continue; - - /* Manually remove the entry */ - if(dp->payload.recursive[i] == sp) { - dp->used--; - dp->payload.recursive[i] = NULL; - } - } - - return SUCCESS; -} - - -dt_err dtree_merge_trees(dtree *data, dtree *merge) -{ - /* REALLY make sure the type is correct */ - if(data->type == UNSET) return INVALID_PARAMS; - if(!(data->type == RECURSIVE || 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; - - 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; - } - - /* Reference the slot, assign it, then move our ctr */ - data->payload.recursive[data->used] = merge; - data->used++; - - return SUCCESS; -} - - -dt_err dtree_search_payload(dtree *data, dtree *(*found), void *payload, dt_uni_t type) -{ - if(data == NULL) return INVALID_PARAMS; - - /* Make sure our pointer is clean */ - *found = NULL; - - if(data->type == RECURSIVE|| data->type == PAIR) { - - int i; - for(i = 0; i < data->used; i++) { - dt_err err = dtree_search_payload(data->payload.recursive[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 NUMERAL: - if(data->payload.numeral == (long) 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; -} - - -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[%lu]\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[%lu]", 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(" => [%lu]\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 t = data->payload.recursive[i]->type; - - - char new_offset[REAL_STRLEN(offset) + 2]; - strcpy(new_offset, offset); - strcat(new_offset, " "); - - if(t == LITERAL || t == NUMERAL) { - recursive_print(data->payload.recursive[i], new_offset); - continue; - } - - if(t == RECURSIVE) - { - recursive_print(data->payload.recursive[i], new_offset); - continue; - } - - if(t == 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->used; i++) { - err = dtree_free(data->payload.recursive[i]); - if(err) return err; - } - - free(data->payload.recursive); - - } else if(data->type == POINTER) { - if(data->payload.pointer) free(data->payload.pointer); - } - - free(data); - return SUCCESS; -} - - -dt_err dtree_free_shallow(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(dtree *data) -{ - switch(data->type) { - case LITERAL: return "Literal"; - case NUMERAL: return "Numeral"; - case RECURSIVE: return "Recursive"; - case PAIR: return "Pair"; - case POINTER: return "Pointer"; - default: return "Unknown"; - } -} - -/**************** PRIVATE UTILITY FUNCTIONS ******************/ - -/** - * Steps down the recursive hirarchy of a dyntree node to - * find a sub-child target. Returns 0 if it can be found. - * - * @param data - * @param target - * @return - */ -int recursive_search(dtree **direct_parent, dtree *data, dtree *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 == RECURSIVE || data->type == PAIR) { - int i; - for(i = 0; i < data->used; i++) { - res = recursive_search(direct_parent, data->payload.recursive[i], target); - if(res == 0) { - - /* Save the node that contains our child for later */ - (*direct_parent) = data; - return res; - } - } - } - - 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 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