summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rwxr-xr-xtree.c101
-rwxr-xr-xtree.h54
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 @@
1lib:
2 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 @@
1#include "tree.h"
2
3Tree* tree_new(const void* const data)
4{
5 Tree* tree = (Tree*) malloc(sizeof(Tree));
6 /// puts("tree new");
7 tree->data = data;
8 tree->next = NULL;
9 tree->child = NULL;
10 return tree;
11}
12
13Tree* tree_add(Tree* tree, const void* const data)
14{
15 Tree* last = tree;
16 while(last->next != NULL)
17 { last = last->next; }
18
19 last->next = tree_new(data);
20 return last->next;
21}
22
23Tree* tree_addChildTop(Tree* tree, const void* const data)
24{
25 Tree* treenew = tree_new(data);
26 treenew->next = tree->child;
27 tree->child = treenew;
28 return treenew;
29}
30
31Tree* tree_addtop(Tree* tree, const void* const data)
32{
33 Tree* new_tree = tree_new(data);
34 if(tree->next == NULL)
35 {
36 tree->next = new_tree;
37 }
38 else
39 {
40 new_tree->next = tree->next;
41 tree->next = new_tree;
42 }
43 return new_tree;
44}
45
46
47Tree* tree_addChild(Tree* tree, const void* const data)
48{
49 /// printf("addChild to %s with '%s'\n", tree->data, data);
50 if(tree->child == NULL)
51 { tree->child = tree_new(data); }
52 else
53 { return tree_add(tree->child, data); }
54
55 return tree->child;
56}
57
58void tree_free(Tree* tree, void((*free_function)(const void*)))
59{
60 Tree* tmp;
61 do
62 {
63 if(tree->child != NULL)
64 { tree_free(tree->child, free_function); }
65
66 tmp = tree->next;
67 if(free_function)
68 free_function(tree->data);
69 free(tree);
70 } while((tree = tmp) != NULL);
71}
72
73Tree* tree_join(Tree* tree, Tree* subtree)
74{
75 if(!tree) { return subtree; }
76 while(tree->next)
77 { tree = tree->next; }
78 tree->next = subtree;
79 return tree->next;
80}
81
82Tree* tree_extend(Tree* tree, Tree* subtree)
83{
84 Tree* child;
85 if(!tree) { return subtree; }
86 child = tree_addChild(tree, subtree->data);
87 child->child = subtree->child;
88 return tree->next;
89}
90
91void tree_iterate(Tree* tree, void* (*fn)(const void* data))
92{
93 Tree* last = tree;
94 void* (*fn2)();
95 do
96 {
97 fn2 = fn(last->data);
98 if(last->child)
99 tree_iterate(last->child, fn2);
100 } while((last = last->next) != NULL);
101}
diff --git a/tree.h b/tree.h
new file mode 100755
index 0000000..7bc180f
--- /dev/null
+++ b/tree.h
@@ -0,0 +1,54 @@
1#ifndef TREE_H
2#define TREE_H
3
4 #include <stdlib.h>
5
6 /** \file tree.h tree.c
7 * most basic tree-implemenation: this is meant as base for all classes
8 * and kept as simple as possible in order to prevent overheads.
9 * relying classes should therefor be performant and easy to maintain.
10 */
11
12 /** \example ./tst/test.c
13 * This example generates a new tree and adds elements.
14 * and prints them on stdout.
15 */
16
17 /// basic structure of a tree- every node can have a child and is part of a
18 /// linked list, so it has a next-element
19 typedef struct Tree
20 {
21 const void* data;
22 struct Tree* next;
23 struct Tree* child;
24 } Tree;
25
26 /// creates a new Tree-structure with a dataentry...
27 extern Tree* tree_new(const void* const data);
28
29 /// appends the tree to the bottom (adds element to the list)
30 extern Tree* tree_add(Tree* tree, const void* const data);
31
32 /// appends the tree to the bottom (adds element to the list)
33 extern Tree* tree_addChildTop(Tree* tree, const void* const data);
34
35 /// appends the tree to the bottom (adds element to the list)
36 extern Tree* tree_addtop(Tree* tree, const void* const data);
37
38 /// adds a childnode. same as adding an element to the list of its child
39 extern Tree* tree_addChild(Tree* tree, const void* const data);
40
41 /// frees all nodes (data* has to be freed seperatly)
42 extern void tree_free(Tree* tree, void((*free_function)(const void*)));
43
44 /// adds another tree at the end of the tree-structure (last element addition)
45 extern Tree* tree_join(Tree* tree, Tree* subtree);
46
47 /// extends another tree as child of the given
48 extern Tree* tree_extend(Tree* tree, Tree* subtree);
49
50 /// iterates over all tree-elements, until return-value of fn is NULL
51 /// - uses the return void* from fn() as next function, so that you
52 /// keep the order in deep structures.
53 extern void tree_iterate(Tree* tree, void* (*fn)(const void* data));
54#endif
..