From a3022f0ba3dc26409eac2d9811dd94375346eb53 Mon Sep 17 00:00:00 2001
From: Katharina Fey <kookie@spacekookie.de>
Date: Sun, 21 Aug 2016 15:23:52 +0200
Subject: Adding split and merge features

---
 include/dtree/dyn_tree.h |  10 +++--
 lib/dyn_tree.c           | 112 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 118 insertions(+), 4 deletions(-)

diff --git a/include/dtree/dyn_tree.h b/include/dtree/dyn_tree.h
index c91f48b..d08d261 100644
--- a/include/dtree/dyn_tree.h
+++ b/include/dtree/dyn_tree.h
@@ -44,6 +44,7 @@ typedef enum {
 
 typedef struct dtree {
     dt_uni_t        type;
+    short           encset;
     size_t          size, used;
     union {
         char                *literal;
@@ -51,7 +52,6 @@ typedef struct dtree {
         struct dtree        *(*recursive);
         void                *pointer;
     } payload;
-    short           encset;
 } dtree;
 
 
@@ -59,12 +59,14 @@ typedef struct dtree {
 typedef enum dt_err {
 
     /* General purpose error codes */
-            FAILURE = -1,
+    FAILURE = -1,
     SUCCESS = 0,
 
     INVALID_PARAMS,
     MALLOC_FAILED,
-    INVALID_PAYLOAD
+    INVALID_PAYLOAD,
+    DATA_NOT_RELATED,
+    NODE_NOT_FOUND,
 
 } dt_err;
 
@@ -278,7 +280,7 @@ dt_err dtree_encode_json(dtree *data, char *(*json_data));
  * @param json_data Input json string
  * @return
  */
-dt_err dtree_decode_json(d_tree *(*data), const char *json_data);
+dt_err dtree_decode_json(dtree *(*data), const char *json_data);
 
 
 #ifdef __cplusplus
diff --git a/lib/dyn_tree.c b/lib/dyn_tree.c
index 6cb456b..d72d1d5 100644
--- a/lib/dyn_tree.c
+++ b/lib/dyn_tree.c
@@ -10,6 +10,13 @@
 #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));
@@ -102,6 +109,7 @@ dt_err dtree_addnumeral(dtree *data, int numeral)
     return SUCCESS;
 }
 
+
 dt_err dtree_addrecursive(dtree *data, dtree *(*new_data))
 {
     /* Make sure we are a literal or unset data object */
@@ -186,6 +194,73 @@ dt_err dtree_addpair(dtree *data, dtree *(*key), dtree *(*value))
     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 ||
+            !(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;
+}
+
+
 void recursive_print(dtree *data, const char *offset)
 {
     dt_uni_t type = data->type;
@@ -260,6 +335,7 @@ void recursive_print(dtree *data, const char *offset)
     }
 }
 
+
 void dtree_print(dtree *data)
 {
     recursive_print(data, "");
@@ -275,6 +351,7 @@ dt_err dtree_get(dtree *data, void *(*val))
     return SUCCESS;
 }
 
+
 dt_err dtree_free(dtree *data)
 {
     if(data == NULL) return SUCCESS;
@@ -300,6 +377,7 @@ dt_err dtree_free(dtree *data)
     return SUCCESS;
 }
 
+
 dt_err dtree_free_shallow(dtree *data)
 {
     if(data == NULL) return SUCCESS;
@@ -321,6 +399,7 @@ dt_err dtree_free_shallow(dtree *data)
     return SUCCESS;
 }
 
+
 const char *dtree_dtype(dtree *data)
 {
     switch(data->type) {
@@ -335,6 +414,39 @@ const char *dtree_dtype(dtree *data)
 
 /**************** 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.
-- 
cgit v1.2.3