From 98a9a31789203e051404b9bcf2faa29bafd9e4bf Mon Sep 17 00:00:00 2001
From: Katharina Fey <kookie@spacekookie.de>
Date: Sun, 21 Aug 2016 16:57:32 +0200
Subject: Adding recursive search function

---
 include/dtree/dyn_tree.h | 18 ++++++++++++++++--
 lib/dyn_tree.c           | 45 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 61 insertions(+), 2 deletions(-)

diff --git a/include/dtree/dyn_tree.h b/include/dtree/dyn_tree.h
index d08d261..64b463b 100644
--- a/include/dtree/dyn_tree.h
+++ b/include/dtree/dyn_tree.h
@@ -37,7 +37,7 @@ extern "C" {
 
 
 /* Type that determines what data is stored inside a tree-node */
-typedef enum {
+typedef enum dt_uni_t {
     UNSET, LITERAL, NUMERAL, RECURSIVE, PAIR, POINTER
 } dt_uni_t;
 
@@ -48,7 +48,7 @@ typedef struct dtree {
     size_t          size, used;
     union {
         char                *literal;
-        int                 numeral;
+        long                numeral;
         struct dtree        *(*recursive);
         void                *pointer;
     } payload;
@@ -182,6 +182,20 @@ dt_err dtree_split_trees(dtree *data, dtree *sp);
  */
 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.
diff --git a/lib/dyn_tree.c b/lib/dyn_tree.c
index 2cf100d..5035849 100644
--- a/lib/dyn_tree.c
+++ b/lib/dyn_tree.c
@@ -261,6 +261,51 @@ dt_err dtree_merge_trees(dtree *data, dtree *merge)
 }
 
 
+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;
-- 
cgit v1.2.3