taskrambler  v0.1.8
Web server and task management solution.
tree.h
Go to the documentation of this file.
1 /**
2  * \file
3  *
4  * \author Georg Hopp
5  *
6  * \copyright
7  * Copyright © 2012 Georg Hopp
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef __TREE_H__
24 #define __TREE_H__
25 
26 #include "class.h"
27 
28 #define TREE_RIGHT(node) (NULL!=(node)?(node)->right:NULL)
29 #define TREE_LEFT(node) (NULL!=(node)?(node)->left:NULL)
30 #define TREE_PARENT(node) (NULL!=(node)?(node)->parent:NULL)
31 
32 #define TREE_CHILD(node) \
33  (NULL==TREE_RIGHT((node))?TREE_LEFT((node)):TREE_RIGHT((node)))
34 
35 #define TREE_RIGHT_LEFT(node) \
36  (NULL!=TREE_RIGHT((node))?TREE_LEFT(TREE_RIGHT((node))):NULL)
37 
38 #define TREE_LEFT_RIGHT(node) \
39  (NULL!=TREE_LEFT((node))?TREE_RIGHT(TREE_LEFT((node))):NULL)
40 
41 #define TREE_SIBLING(node) \
42  (NULL!=TREE_PARENT((node))? \
43  ((node)==TREE_PARENT((node))->left? \
44  TREE_PARENT((node))->right: \
45  TREE_PARENT((node))->left): \
46  NULL)
47 
48 #define TREE_GRANDPARENT(node) \
49  (NULL!=TREE_PARENT((node))?TREE_PARENT((node))->parent:NULL)
50 
51 #define TREE_UNCLE(node) \
52  (NULL!=TREE_GRANDPARENT((node))? \
53  (TREE_PARENT((node))==TREE_GRANDPARENT((node))->left? \
54  TREE_GRANDPARENT((node))->right: \
55  TREE_GRANDPARENT((node))->left): \
56  NULL)
57 
58 #define TREE_ROTATE_LEFT(root, node) \
59  do { \
60  if (NULL != TREE_RIGHT_LEFT((node))) { \
61  TREE_RIGHT_LEFT((node))->parent = (node); \
62  } \
63  TREE_RIGHT((node))->left = (node); \
64  if (NULL != TREE_PARENT((node))) { \
65  if (TREE_PARENT((node))->left==(node)) { \
66  TREE_PARENT((node))->left = (node)->right; \
67  } else { \
68  TREE_PARENT((node))->right = (node)->right; \
69  } \
70  } else { \
71  *(root) = (node)->right; \
72  } \
73  (node)->right = TREE_RIGHT_LEFT((node)); \
74  (node)->parent = (node)->right; \
75  TREE_RIGHT((node))->parent = (node)->parent; \
76  } while(0)
77 
78 #define TREE_ROTATE_RIGHT(root, node) \
79  do { \
80  if (NULL != TREE_LEFT_RIGHT((node))) { \
81  TREE_LEFT_RIGHT((node))->parent = (node); \
82  } \
83  TREE_LEFT((node))->right = (node); \
84  if (NULL != TREE_PARENT((node))) { \
85  if (TREE_PARENT((node))->left==(node)) { \
86  TREE_PARENT((node))->left = (node)->left; \
87  } else { \
88  TREE_PARENT((node))->right = (node)->left; \
89  } \
90  } else { \
91  *(root) = (node)->left; \
92  } \
93  TREE_LEFT((node))->parent = (node)->parent; \
94  (node)->left = TREE_LEFT_RIGHT((node)); \
95  (node)->parent = (node)->right; \
96  } while(0)
97 
98 #define TREE_REPLACE_NODE(root, node1, node2) \
99  do { \
100  if (NULL != TREE_PARENT((node1))) { \
101  if ((node1) == TREE_PARENT((node1))->left) { \
102  TREE_PARENT((node1))->left = (node2); \
103  } else { \
104  TREE_PARENT((node1))->right = (node2); \
105  } \
106  } else { \
107  *(root) = (node2); \
108  } \
109  if (NULL != (node2)) { \
110  (node2)->parent = (node1)->parent; \
111  } \
112  } while(0)
113 
114 
115 enum rbColor {rbBlack=1, rbRed=2};
116 
117 CLASS(Tree) {
118  void * data;
119 
120  enum rbColor color;
121 
122  Tree parent;
123  Tree left;
124  Tree right;
125 };
126 
127 typedef int (*TreeComp)(const void *, const void *);
128 typedef void (*TreeAction)(const void *, const int);
129 
130 void * treeFind(Tree, const void *, TreeComp);
131 void * treeInsert(Tree *, const void *, TreeComp);
132 void * treeDelete(Tree *, const void *, TreeComp);
133 void treeWalk(Tree, TreeAction);
134 void treeDestroy(Tree *, TreeAction);
135 
136 #endif // __TREE_H__
137 
138 // vim: set ts=4 sw=4:
CLASS(Tree)
Definition: tree.h:117
rbColor
Definition: tree.h:115
void * treeInsert(Tree *, const void *, TreeComp)
Definition: insert.c:29
int(* TreeComp)(const void *, const void *)
Definition: tree.h:127
Definition: tree.h:115
void(* TreeAction)(const void *, const int)
Definition: tree.h:128
Definition: tree.h:115
void * treeFind(Tree, const void *, TreeComp)
Definition: find.c:26
void * treeDelete(Tree *, const void *, TreeComp)
Definition: tree/delete.c:31
void treeWalk(Tree, TreeAction)
Definition: walk.c:26
void treeDestroy(Tree *, TreeAction)
Definition: destroy.c:26