First attempt to build a generic tree structureHEADmaster

written in 2011

3 files changed, 157 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..58e1e3f
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,2 @@
+lib:
+        gcc -Wall -fPIC -shared -o tree.so tree.c
diff --git a/tree.c b/tree.c
new file mode 100755
index 0000000..2fd50d2
--- /dev/null
+++ b/tree.c
@@ -0,0 +1,101 @@
+#include "tree.h"
+
+Tree* tree_new(const void* const data)
+{
+  Tree* tree = (Tree*) malloc(sizeof(Tree));
+  /// puts("tree new");
+  tree->data  = data;
+  tree->next  = NULL;
+  tree->child = NULL;
+  return tree;
+}
+
+Tree* tree_add(Tree* tree, const void* const data)
+{
+  Tree* last = tree;
+  while(last->next != NULL)
+  { last = last->next; }
+
+  last->next = tree_new(data);
+  return last->next;
+}
+
+Tree* tree_addChildTop(Tree* tree, const void* const data)
+{
+  Tree* treenew = tree_new(data);
+  treenew->next = tree->child;
+  tree->child = treenew;
+  return treenew;
+}
+
+Tree* tree_addtop(Tree* tree, const void* const data)
+{
+  Tree* new_tree = tree_new(data);
+  if(tree->next == NULL)
+  {
+    tree->next = new_tree;
+  }
+  else
+  {
+    new_tree->next = tree->next;
+    tree->next = new_tree;
+  }
+  return new_tree;
+}
+
+
+Tree* tree_addChild(Tree* tree, const void* const data)
+{
+  /// printf("addChild to %s with '%s'\n", tree->data, data);
+  if(tree->child == NULL)
+  { tree->child = tree_new(data); }
+  else
+  { return tree_add(tree->child, data); }
+
+  return tree->child;
+}
+
+void tree_free(Tree* tree, void((*free_function)(const void*)))
+{
+  Tree* tmp;
+  do
+  {
+    if(tree->child != NULL)
+    { tree_free(tree->child, free_function); }
+
+    tmp = tree->next;
+    if(free_function)
+      free_function(tree->data);
+    free(tree);
+  } while((tree = tmp) != NULL);
+}
+
+Tree* tree_join(Tree* tree, Tree* subtree)
+{
+  if(!tree) { return subtree; }
+  while(tree->next)
+  { tree = tree->next; }
+  tree->next = subtree;
+  return tree->next;
+}
+
+Tree* tree_extend(Tree* tree, Tree* subtree)
+{
+  Tree* child;
+  if(!tree) { return subtree; }
+  child = tree_addChild(tree, subtree->data);
+  child->child = subtree->child;
+  return tree->next;
+}
+
+void tree_iterate(Tree* tree, void* (*fn)(const void* data))
+{
+  Tree* last = tree;
+  void* (*fn2)();
+  do
+  {
+    fn2 = fn(last->data);
+    if(last->child)
+      tree_iterate(last->child, fn2);
+  } while((last = last->next) != NULL);
+}
diff --git a/tree.h b/tree.h
new file mode 100755
index 0000000..7bc180f
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,54 @@
+#ifndef TREE_H
+#define TREE_H
+
+  #include <stdlib.h>
+
+  /** \file tree.h tree.c
+   *  most basic tree-implemenation: this is meant as base for all classes
+   *  and kept as simple as possible in order to prevent overheads.
+   *  relying classes should therefor be performant and easy to maintain.
+   */
+
+  /** \example ./tst/test.c
+   *  This example generates a new tree and adds elements.
+   *  and prints them on stdout.
+   */
+
+  /// basic structure of a tree- every node can have a child and is part of a
+  /// linked list, so it has a next-element
+  typedef struct Tree
+  {
+    const void* data;
+    struct Tree* next;
+    struct Tree* child;
+  } Tree;
+
+  /// creates a new Tree-structure with a dataentry...
+  extern Tree* tree_new(const void* const data);
+
+  /// appends the tree to the bottom (adds element to the list)
+  extern Tree* tree_add(Tree* tree, const void* const data);
+
+  /// appends the tree to the bottom (adds element to the list)
+  extern Tree* tree_addChildTop(Tree* tree, const void* const data);
+
+  /// appends the tree to the bottom (adds element to the list)
+  extern Tree* tree_addtop(Tree* tree, const void* const data);
+
+  /// adds a childnode. same as adding an element to the list of its child
+  extern Tree* tree_addChild(Tree* tree, const void* const data);
+
+  /// frees all nodes (data* has to be freed seperatly)
+  extern void tree_free(Tree* tree, void((*free_function)(const void*)));
+
+  /// adds another tree at the end of the tree-structure (last element addition)
+  extern Tree* tree_join(Tree* tree, Tree* subtree);
+
+  /// extends another tree as child of the given
+  extern Tree* tree_extend(Tree* tree, Tree* subtree);
+
+  /// iterates over all tree-elements, until return-value of fn is NULL
+  /// - uses the return void* from fn() as next function, so that you
+  ///   keep the order in deep structures.
+  extern void tree_iterate(Tree* tree, void* (*fn)(const void* data));
+#endif