Initial commit of the library

6 files changed, 471 insertions, 0 deletions

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 <memory.h>
+
+
+/* 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 <dtree/dyn_tree.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 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;
+}