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 --- lib/dtree.c | 581 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/dyn_tree.c | 520 --------------------------------------------------- 2 files changed, 581 insertions(+), 520 deletions(-) create mode 100644 lib/dtree.c delete mode 100644 lib/dyn_tree.c (limited to 'lib') 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