Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / tree.c
1
2 #include <string.h>
3
4 #include "WUtil.h"
5
6 typedef struct W_TreeNode {
7 void *data;
8
9 /*unsigned int uflags:16; */
10
11 WMArray *leaves;
12
13 int depth;
14
15 struct W_TreeNode *parent;
16
17 WMFreeDataProc *destructor;
18 } W_TreeNode;
19
20 void destroyNode(void *data)
21 {
22 WMTreeNode *aNode = (WMTreeNode *) data;
23
24 if (aNode->destructor) {
25 (*aNode->destructor) (aNode->data);
26 }
27 if (aNode->leaves) {
28 WMFreeArray(aNode->leaves);
29 }
30 wfree(aNode);
31 }
32
33 WMTreeNode *WMCreateTreeNode(void *data)
34 {
35 return WMCreateTreeNodeWithDestructor(data, NULL);
36 }
37
38 WMTreeNode *WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc * destructor)
39 {
40 WMTreeNode *aNode;
41
42 aNode = (WMTreeNode *) wmalloc(sizeof(W_TreeNode));
43 memset(aNode, 0, sizeof(W_TreeNode));
44
45 aNode->destructor = destructor;
46
47 aNode->data = data;
48 aNode->parent = NULL;
49 aNode->depth = 0;
50 aNode->leaves = NULL;
51 /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
52
53 return aNode;
54 }
55
56 WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
57 {
58 WMTreeNode *aNode;
59
60 wassertrv(parent != NULL, NULL);
61
62 aNode = WMCreateTreeNodeWithDestructor(item, parent->destructor);
63 aNode->parent = parent;
64 aNode->depth = parent->depth + 1;
65 if (!parent->leaves) {
66 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
67 }
68 if (index < 0) {
69 WMAddToArray(parent->leaves, aNode);
70 } else {
71 WMInsertInArray(parent->leaves, index, aNode);
72 }
73
74 return aNode;
75 }
76
77 static void updateNodeDepth(WMTreeNode * aNode, int depth)
78 {
79 int i;
80
81 aNode->depth = depth;
82
83 if (aNode->leaves) {
84 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
85 updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
86 }
87 }
88 }
89
90 WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
91 {
92 wassertrv(parent != NULL, NULL);
93 wassertrv(aNode != NULL, NULL);
94
95 aNode->parent = parent;
96 updateNodeDepth(aNode, parent->depth + 1);
97 if (!parent->leaves) {
98 parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
99 }
100 if (index < 0) {
101 WMAddToArray(parent->leaves, aNode);
102 } else {
103 WMInsertInArray(parent->leaves, index, aNode);
104 }
105
106 return aNode;
107 }
108
109 void WMDestroyTreeNode(WMTreeNode * aNode)
110 {
111 wassertr(aNode != NULL);
112
113 if (aNode->parent && aNode->parent->leaves) {
114 WMRemoveFromArray(aNode->parent->leaves, aNode);
115 } else {
116 destroyNode(aNode);
117 }
118 }
119
120 void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
121 {
122 wassertr(aNode != NULL);
123 wassertr(aNode->leaves != NULL);
124
125 WMDeleteFromArray(aNode->leaves, index);
126 }
127
128 static int sameData(void *item, void *data)
129 {
130 return (((WMTreeNode *) item)->data == data);
131 }
132
133 void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
134 {
135 int index;
136
137 wassertr(aNode != NULL);
138 wassertr(aNode->leaves != NULL);
139
140 index = WMFindInArray(aNode->leaves, sameData, leaf);
141 if (index != WANotFound) {
142 WMDeleteFromArray(aNode->leaves, index);
143 }
144 }
145
146 void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
147 {
148 void *old;
149
150 wassertrv(aNode != NULL, NULL);
151
152 old = aNode->data;
153 aNode->data = newData;
154
155 return old;
156 }
157
158 void *WMGetDataForTreeNode(WMTreeNode * aNode)
159 {
160 return aNode->data;
161 }
162
163 int WMGetTreeNodeDepth(WMTreeNode * aNode)
164 {
165 return aNode->depth;
166 }
167
168 WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
169 {
170 return aNode->parent;
171 }
172
173 void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
174 {
175 wassertr(aNode != NULL);
176
177 if (aNode->leaves) {
178 WMSortArray(aNode->leaves, comparer);
179 }
180 }
181
182 static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
183 {
184 int i;
185
186 if (!aNode->leaves)
187 return;
188
189 WMSortArray(aNode->leaves, comparer);
190 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
191 sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
192 }
193 }
194
195 void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
196 {
197 wassertr(aNode != NULL);
198
199 sortLeavesForNode(aNode, comparer);
200 }
201
202 static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
203 {
204 if (match == NULL) {
205 if (aNode->data == cdata) {
206 return aNode;
207 }
208 } else {
209 if ((*match) (aNode->data, cdata)) {
210 return aNode;
211 }
212 }
213
214 if (aNode->leaves) {
215 WMTreeNode *leaf;
216 int i;
217
218 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
219 leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata);
220 if (leaf) {
221 return leaf;
222 }
223 }
224 }
225
226 return NULL;
227 }
228
229 WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
230 {
231 wassertrv(aTree != NULL, NULL);
232
233 return findNodeInTree(aTree, match, cdata);
234 }