taskrambler  0.1.8
Web server and task management solution.
tree.h File Reference
#include "class.h"
+ Include dependency graph for tree.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define TREE_RIGHT(node)   (NULL!=(node)?(node)->right:NULL)
 
#define TREE_LEFT(node)   (NULL!=(node)?(node)->left:NULL)
 
#define TREE_PARENT(node)   (NULL!=(node)?(node)->parent:NULL)
 
#define TREE_CHILD(node)   (NULL==TREE_RIGHT((node))?TREE_LEFT((node)):TREE_RIGHT((node)))
 
#define TREE_RIGHT_LEFT(node)   (NULL!=TREE_RIGHT((node))?TREE_LEFT(TREE_RIGHT((node))):NULL)
 
#define TREE_LEFT_RIGHT(node)   (NULL!=TREE_LEFT((node))?TREE_RIGHT(TREE_LEFT((node))):NULL)
 
#define TREE_SIBLING(node)
 
#define TREE_GRANDPARENT(node)   (NULL!=TREE_PARENT((node))?TREE_PARENT((node))->parent:NULL)
 
#define TREE_UNCLE(node)
 
#define TREE_ROTATE_LEFT(root, node)
 
#define TREE_ROTATE_RIGHT(root, node)
 
#define TREE_REPLACE_NODE(root, node1, node2)
 

Typedefs

typedef int(* TreeComp) (const void *, const void *)
 
typedef void(* TreeAction) (const void *, const int)
 

Enumerations

enum  rbColor { rbBlack =1, rbRed =2, rbBlack =1, rbRed =2 }
 

Functions

 CLASS (Tree)
 
void * treeFind (Tree, const void *, TreeComp)
 
void * treeInsert (Tree *, const void *, TreeComp)
 
void * treeDelete (Tree *, const void *, TreeComp)
 
void treeWalk (Tree, TreeAction)
 
void treeDestroy (Tree *, TreeAction)
 

Detailed Description

Author
Georg Hopp

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file tree.h.

Macro Definition Documentation

#define TREE_CHILD (   node)    (NULL==TREE_RIGHT((node))?TREE_LEFT((node)):TREE_RIGHT((node)))

Definition at line 32 of file tree.h.

Referenced by treeDelete().

#define TREE_GRANDPARENT (   node)    (NULL!=TREE_PARENT((node))?TREE_PARENT((node))->parent:NULL)

Definition at line 48 of file tree.h.

Referenced by treeInsert().

#define TREE_LEFT (   node)    (NULL!=(node)?(node)->left:NULL)
#define TREE_LEFT_RIGHT (   node)    (NULL!=TREE_LEFT((node))?TREE_RIGHT(TREE_LEFT((node))):NULL)

Definition at line 38 of file tree.h.

Referenced by treeRotateRight().

#define TREE_PARENT (   node)    (NULL!=(node)?(node)->parent:NULL)

Definition at line 30 of file tree.h.

Referenced by treeDelete(), treeDestroy(), treeInsert(), treeRotateLeft(), treeRotateRight(), and treeWalk().

#define TREE_REPLACE_NODE (   root,
  node1,
  node2 
)
Value:
do { \
if (NULL != TREE_PARENT((node1))) { \
if ((node1) == TREE_PARENT((node1))->left) { \
TREE_PARENT((node1))->left = (node2); \
} else { \
TREE_PARENT((node1))->right = (node2); \
} \
} else { \
*(root) = (node2); \
} \
if (NULL != (node2)) { \
(node2)->parent = (node1)->parent; \
} \
} while(0)
#define TREE_PARENT(node)
Definition: tree.h:30

Definition at line 98 of file tree.h.

Referenced by treeDelete().

#define TREE_RIGHT (   node)    (NULL!=(node)?(node)->right:NULL)
#define TREE_RIGHT_LEFT (   node)    (NULL!=TREE_RIGHT((node))?TREE_LEFT(TREE_RIGHT((node))):NULL)

Definition at line 35 of file tree.h.

Referenced by treeRotateLeft().

#define TREE_ROTATE_LEFT (   root,
  node 
)
Value:
do { \
if (NULL != TREE_RIGHT_LEFT((node))) { \
TREE_RIGHT_LEFT((node))->parent = (node); \
} \
TREE_RIGHT((node))->left = (node); \
if (NULL != TREE_PARENT((node))) { \
if (TREE_PARENT((node))->left==(node)) { \
TREE_PARENT((node))->left = (node)->right; \
} else { \
TREE_PARENT((node))->right = (node)->right; \
} \
} else { \
*(root) = (node)->right; \
} \
(node)->right = TREE_RIGHT_LEFT((node)); \
(node)->parent = (node)->right; \
TREE_RIGHT((node))->parent = (node)->parent; \
} while(0)
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_RIGHT_LEFT(node)
Definition: tree.h:35

Definition at line 58 of file tree.h.

#define TREE_ROTATE_RIGHT (   root,
  node 
)
Value:
do { \
if (NULL != TREE_LEFT_RIGHT((node))) { \
TREE_LEFT_RIGHT((node))->parent = (node); \
} \
TREE_LEFT((node))->right = (node); \
if (NULL != TREE_PARENT((node))) { \
if (TREE_PARENT((node))->left==(node)) { \
TREE_PARENT((node))->left = (node)->left; \
} else { \
TREE_PARENT((node))->right = (node)->left; \
} \
} else { \
*(root) = (node)->left; \
} \
TREE_LEFT((node))->parent = (node)->parent; \
(node)->left = TREE_LEFT_RIGHT((node)); \
(node)->parent = (node)->right; \
} while(0)
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_LEFT_RIGHT(node)
Definition: tree.h:38
#define TREE_LEFT(node)
Definition: tree.h:29

Definition at line 78 of file tree.h.

#define TREE_SIBLING (   node)
Value:
(NULL!=TREE_PARENT((node))? \
((node)==TREE_PARENT((node))->left? \
TREE_PARENT((node))->right: \
TREE_PARENT((node))->left): \
NULL)
#define TREE_PARENT(node)
Definition: tree.h:30

Definition at line 41 of file tree.h.

Referenced by treeDelete().

#define TREE_UNCLE (   node)
Value:
(NULL!=TREE_GRANDPARENT((node))? \
(TREE_PARENT((node))==TREE_GRANDPARENT((node))->left? \
TREE_GRANDPARENT((node))->right: \
TREE_GRANDPARENT((node))->left): \
NULL)
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_GRANDPARENT(node)
Definition: tree.h:48

Definition at line 51 of file tree.h.

Referenced by treeInsert().

Typedef Documentation

typedef void(* TreeAction) (const void *, const int)

Definition at line 128 of file tree.h.

typedef int(* TreeComp) (const void *, const void *)

Definition at line 127 of file tree.h.

Enumeration Type Documentation

enum rbColor
Enumerator
rbBlack 
rbRed 
rbBlack 
rbRed 

Definition at line 115 of file tree.h.

115 {rbBlack=1, rbRed=2};
Definition: tree.h:115
Definition: tree.h:115

Function Documentation

CLASS ( Tree  )

Definition at line 117 of file tree.h.

117  {
118  void * data;
119 
120  enum rbColor color;
121 
122  Tree parent;
123  Tree left;
124  Tree right;
125 };
rbColor
Definition: tree.h:115
void* treeDelete ( Tree *  ,
const void *  ,
TreeComp   
)

Definition at line 31 of file tree/delete.c.

References comp(), inOrderSuccessor(), rbBlack, rbRed, TREE_CHILD, TREE_LEFT, TREE_PARENT, TREE_REPLACE_NODE, TREE_RIGHT, TREE_SIBLING, treeRotateLeft(), and treeRotateRight().

Referenced by hashDelete(), hashDeleteByVal(), and main().

32 {
33  Tree node = *this;
34  Tree del_node;
35 
36  void * data;
37 
38  /*
39  * first search for it and if its found return the data
40  * and we are done...
41  */
42  while (NULL != node) {
43  int comparison = comp(node->data, search);
44 
45  if (0 < comparison) {
46  node = TREE_LEFT(node);
47  continue;
48  }
49 
50  if (0 > comparison) {
51  node = TREE_RIGHT(node);
52  continue;
53  }
54 
55  if (0 == comparison) {
56  break;
57  }
58  }
59 
60  /*
61  * nothing was found...return NULL to indicate this.
62  */
63  if (NULL == node) {
64  return NULL;
65  }
66 
67  /*
68  * we found an element, store its data pointer as we are
69  * up to delete it.
70  */
71  data = node->data;
72 
73  /*
74  * now remove the element.
75  */
76 
77  /*
78  * if we have two children replace data with the one from
79  * out inOrderSuccessor and remove the inOrderSuccessor.
80  */
81  if (NULL != TREE_LEFT(node) && NULL != TREE_RIGHT(node)) {
82  Tree successor = inOrderSuccessor(node);
83 
84  node->data = successor->data;
85  node = successor;
86  }
87 
88  {
89  Tree child = TREE_CHILD(node);
90 
91  /*
92  * if we still have one child replace ourself with it.
93  */
94  TREE_REPLACE_NODE(this, node, child);
95 
96  /*
97  * and finally delete the node...and prepare ourselfs
98  * for rebalancing.
99  */
100  if (rbBlack == node->color) {
101  if (NULL != child && rbRed == child->color) {
102  child->color = rbBlack;
103  delete(node);
104  return data;
105  } else {
106  del_node = node;
107  if (NULL != child) {
108  node = child;
109  } else {
110  node->color = rbBlack;
111  node->left = NULL;
112  node->right = NULL;
113  }
114  }
115  } else {
116  delete(node);
117  return data;
118  }
119  }
120 
121  /*
122  * now comes rebalancing...note that if we came to this point
123  * the node is still not deleted.
124  * This is because I am not sure if it is needed during the
125  * rebalancing process...(this does not make much sense, but
126  * to be honest I don't know now.)
127  */
128  while(1) {
129  // case 1
130  if (NULL == TREE_PARENT(node)) {
131  break;
132  }
133 
134  // case 2
135  if (NULL != TREE_SIBLING(node)
136  && rbRed == TREE_SIBLING(node)->color) {
137 
138  TREE_PARENT(node)->color = rbRed;
139  TREE_SIBLING(node)->color = rbBlack;
140 
141  if (NULL != TREE_PARENT(node)->right &&
142  node != TREE_PARENT(node)->right) {
143 
144  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
145  treeRotateLeft(this, TREE_PARENT(node));
146 
147  } else {
148 
149  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
150  treeRotateRight(this, TREE_PARENT(node));
151 
152  }
153  }
154 
155  // case 3 / 4
156  if (NULL == TREE_SIBLING(node)
157  || (rbBlack == TREE_SIBLING(node)->color
158  && (NULL == TREE_SIBLING(node)->left
159  || rbBlack == TREE_SIBLING(node)->left->color)
160  && (NULL == TREE_SIBLING(node)->right
161  || rbBlack == TREE_SIBLING(node)->right->color))) {
162 
163  if (NULL != TREE_SIBLING(node)) {
164  TREE_SIBLING(node)->color = rbRed;
165  }
166 
167 
168  /*
169  * this is the point where during the balancing our tree
170  * node can be finally deleted.
171  */
172  if (rbBlack == TREE_PARENT(node)->color) {
173  // case 3
174  Tree parent = node->parent;
175  node = parent;
176  continue;
177  } else {
178  // case 4
179  TREE_PARENT(node)->color = rbBlack;
180  break;
181  }
182  }
183 
184  // case 5
185  if (NULL != TREE_SIBLING(node)
186  && rbBlack == TREE_SIBLING(node)->color) {
187 
188  if (node == TREE_PARENT(node)->left
189  && (NULL == TREE_SIBLING(node)->right
190  || rbBlack == TREE_SIBLING(node)->right->color)
191  && (NULL != TREE_SIBLING(node)->left
192  && rbRed == TREE_SIBLING(node)->left->color)) {
193 
194  TREE_SIBLING(node)->color = rbRed;
195  TREE_SIBLING(node)->left->color = rbBlack;
196 
197  //TREE_ROTATE_RIGHT(this, TREE_SIBLING(node));
198  treeRotateRight(this, TREE_SIBLING(node));
199 
200  } else if (node == TREE_PARENT(node)->right
201  && (NULL == TREE_SIBLING(node)->left
202  || rbBlack == TREE_SIBLING(node)->left->color)
203  && (NULL != TREE_SIBLING(node)->right
204  && rbRed == TREE_SIBLING(node)->right->color)) {
205 
206  TREE_SIBLING(node)->color = rbRed;
207  TREE_SIBLING(node)->right->color = rbBlack;
208 
209  //TREE_ROTATE_LEFT(this, TREE_SIBLING(node));
210  treeRotateLeft(this, TREE_SIBLING(node));
211  }
212  }
213 
214  // case 6
215  if (NULL != TREE_SIBLING(node)) {
216  TREE_SIBLING(node)->color = TREE_PARENT(node)->color;
217  }
218 
219  if (NULL != node && NULL != TREE_PARENT(node)) {
220  TREE_PARENT(node)->color = rbBlack;
221 
222  if (NULL != TREE_PARENT(node)->right
223  && node != TREE_PARENT(node)->right) {
224 
225  if (NULL != TREE_SIBLING(node)->right) {
226  TREE_SIBLING(node)->right->color = rbBlack;
227  }
228  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
229  treeRotateLeft(this, TREE_PARENT(node));
230  } else {
231  if (NULL != TREE_SIBLING(node)->left) {
232  TREE_SIBLING(node)->left->color = rbBlack;
233  }
234  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
235  treeRotateRight(this, TREE_PARENT(node));
236  }
237  }
238 
239  break;
240  }
241 
242  delete(del_node);
243  /*
244  * not sure if deleting here is correct.
245  */
246  return data;
247 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_CHILD(node)
Definition: tree.h:32
#define TREE_PARENT(node)
Definition: tree.h:30
static int comp(const void *_a, const void *_b)
Definition: interface.c:32
Tree inOrderSuccessor(Tree)
void treeRotateRight(Tree *, Tree)
Definition: rotateRight.c:26
Definition: tree.h:115
#define TREE_LEFT(node)
Definition: tree.h:29
void treeRotateLeft(Tree *, Tree)
Definition: rotateLeft.c:26
#define TREE_REPLACE_NODE(root, node1, node2)
Definition: tree.h:98
Definition: tree.h:115
#define TREE_SIBLING(node)
Definition: tree.h:41

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void treeDestroy ( Tree *  ,
TreeAction   
)

Definition at line 26 of file destroy.c.

References TREE_LEFT, TREE_PARENT, and TREE_RIGHT.

Referenced by hashCleanup(), and main().

27 {
28  Tree previous = * this;
29  Tree node = * this;
30  int depth = 1;
31 
32  /*
33  * I think this has something like O(n+log(n)) on a ballanced
34  * tree because I have to traverse back the rightmost leaf to
35  * the root to get a break condition.
36  */
37  while (NULL != node) {
38  /*
39  * If we come from the right so nothing and go to our
40  * next parent.
41  */
42  if (((NULL == TREE_LEFT(node)
43  || previous == TREE_LEFT(node)) && NULL == TREE_RIGHT(node))
44  || previous == TREE_RIGHT(node)) {
45 
46  Tree parent = TREE_PARENT(node);
47 
48  action(node->data, depth);
49 
50  previous = node;
51  delete(node);
52  node = parent;
53  depth--;
54 
55  continue;
56  }
57 
58  if ((NULL == TREE_LEFT(node) || previous == TREE_LEFT(node))) {
59  /*
60  * If there are no more elements to the left or we
61  * came from the left, process data.
62  */
63  previous = node;
64 
65  if (NULL != TREE_RIGHT(node)) {
66  node = TREE_RIGHT(node);
67  depth++;
68  } else {
69  node = TREE_PARENT(node);
70  depth--;
71  }
72  } else {
73  /*
74  * if there are more elements to the left go there.
75  */
76  previous = node;
77  node = TREE_LEFT(node);
78  depth++;
79  }
80  }
81 
82  *this = NULL;
83 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the caller graph for this function:

void* treeFind ( Tree  ,
const void *  ,
TreeComp   
)

Definition at line 26 of file find.c.

References comp(), TREE_LEFT, and TREE_RIGHT.

Referenced by hashGet(), hashGetByVal(), and main().

27 {
28  while (NULL != this) {
29  int comparison = comp(this->data, search);
30 
31  if (0 < comparison) {
32  this = TREE_LEFT(this);
33  continue;
34  }
35 
36  if (0 > comparison) {
37  this = TREE_RIGHT(this);
38  continue;
39  }
40 
41  if (0 == comparison) {
42  break;
43  }
44  }
45 
46  return NULL != this ? this->data : NULL;
47 }
#define TREE_RIGHT(node)
Definition: tree.h:28
static int comp(const void *_a, const void *_b)
Definition: interface.c:32
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void* treeInsert ( Tree *  ,
const void *  ,
TreeComp   
)

Definition at line 29 of file insert.c.

References comp(), rbBlack, rbRed, TREE_GRANDPARENT, TREE_LEFT, TREE_PARENT, TREE_RIGHT, TREE_UNCLE, treeRotateLeft(), and treeRotateRight().

Referenced by hashAdd(), and main().

30 {
31  Tree node = *this;
32  Tree new_node = NULL;
33 
34  /*
35  * insert the node or return the one in tree if comparison
36  * succeeds.
37  */
38  if (NULL == node) {
39  /*
40  * if the root is NULL we simple add the element and set
41  * node to it.
42  */
43  *this = node = new_node = new(Tree, search);
44  } else {
45  /*
46  * first search for it and if its found return the data
47  * and we are done...
48  */
49  int comparison;
50 
51  while (NULL != node) {
52  comparison = comp(node->data, search);
53 
54  if (0 < comparison) {
55  if (NULL != TREE_LEFT(node)) {
56  node = TREE_LEFT(node);
57  continue;
58  } else {
59  break;
60  }
61  }
62 
63  if (0 > comparison) {
64  if (NULL != TREE_RIGHT(node)) {
65  node = TREE_RIGHT(node);
66  continue;
67  } else {
68  break;
69  }
70  }
71 
72  if (0 == comparison) {
73  return node->data;
74  }
75  }
76 
77  /*
78  * as we have not found it now add a new element.
79  */
80  if (0 < comparison) {
81  node->left = new(Tree, search);
82  TREE_LEFT(node)->parent = node;
83  node = new_node = TREE_LEFT(node);
84  } else {
85  node->right = new(Tree, search);
86  TREE_RIGHT(node)->parent = node;
87  node = new_node = TREE_RIGHT(node);
88  }
89  }
90 
91  /*
92  * we expect node not to be NULL and pointing to our
93  * new node at this point...now rabalance the tree
94  */
95  while (1) {
96  // case 1
97  if (NULL == TREE_PARENT(node)) {
98  node->color = rbBlack;
99  break;
100  }
101 
102  // case 2
103  if (rbBlack == TREE_PARENT(node)->color) {
104  break;
105  }
106 
107  // case 3
108  if (NULL != TREE_UNCLE(node) && rbRed == TREE_UNCLE(node)->color) {
109  TREE_PARENT(node)->color = rbBlack;
110  TREE_UNCLE(node)->color = rbBlack;
111  TREE_GRANDPARENT(node)->color = rbRed;
112 
113  node = TREE_GRANDPARENT(node);
114  continue;
115  }
116 
117  // case 4
118  if (node == TREE_PARENT(node)->right
119  && TREE_PARENT(node) == TREE_GRANDPARENT(node)->left) {
120 
121  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
122  treeRotateLeft(this, TREE_PARENT(node));
123  node = TREE_LEFT(node);
124 
125  } else if (node == TREE_PARENT(node)->left
126  && TREE_PARENT(node) == TREE_GRANDPARENT(node)->right) {
127 
128  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
129  treeRotateRight(this, TREE_PARENT(node));
130  node = TREE_RIGHT(node);
131 
132  }
133 
134  // case 5
135  TREE_PARENT(node)->color = rbBlack;
136  TREE_GRANDPARENT(node)->color = rbRed;
137 
138  if (node == TREE_PARENT(node)->left) {
139  //TREE_ROTATE_RIGHT(this, TREE_GRANDPARENT(node));
140  treeRotateRight(this, TREE_GRANDPARENT(node));
141  } else {
142  //TREE_ROTATE_LEFT(this, TREE_GRANDPARENT(node));
143  treeRotateLeft(this, TREE_GRANDPARENT(node));
144  }
145 
146  break;
147  }
148 
149  return new_node->data;
150 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
static int comp(const void *_a, const void *_b)
Definition: interface.c:32
void treeRotateRight(Tree *, Tree)
Definition: rotateRight.c:26
void treeRotateLeft(Tree *, Tree)
Definition: rotateLeft.c:26
#define TREE_GRANDPARENT(node)
Definition: tree.h:48
Definition: tree.h:115
#define TREE_LEFT(node)
Definition: tree.h:29
#define TREE_UNCLE(node)
Definition: tree.h:51
Definition: tree.h:115

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void treeWalk ( Tree  ,
TreeAction   
)

Definition at line 26 of file walk.c.

References TREE_LEFT, TREE_PARENT, and TREE_RIGHT.

Referenced by hashEach(), and main().

27 {
28  Tree previous = this;
29  Tree node = this;
30  int depth = 1;
31 
32  while (NULL != node) {
33  if (previous == TREE_RIGHT(node)) {
34  previous = node;
35  node = node->parent;
36  depth--;
37  continue;
38  }
39 
40  if (NULL == TREE_LEFT(node) || previous == TREE_LEFT(node)) {
41  action(node->data, depth);
42  previous = node;
43 
44  if (NULL != TREE_RIGHT(node)) {
45  node = TREE_RIGHT(node);
46  depth++;
47  } else {
48  node = TREE_PARENT(node);
49  depth--;
50  }
51  } else {
52  previous = node;
53  node = TREE_LEFT(node);
54  depth++;
55  }
56  }
57 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the caller graph for this function: