Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / tree.c
blob5781588b65a75e31009f5ad2597516ed9b451a40
2 #include <string.h>
4 #include "WUtil.h"
6 typedef struct W_TreeNode {
7 void *data;
9 /*unsigned int uflags:16; */
11 WMArray *leaves;
13 int depth;
15 struct W_TreeNode *parent;
17 WMFreeDataProc *destructor;
18 } W_TreeNode;
20 void destroyNode(void *data)
21 {
22 WMTreeNode *aNode = (WMTreeNode *) data;
24 if (aNode->destructor) {
25 (*aNode->destructor) (aNode->data);
26 }
27 if (aNode->leaves) {
28 WMFreeArray(aNode->leaves);
29 }
30 wfree(aNode);
31 }
33 WMTreeNode *WMCreateTreeNode(void *data)
34 {
35 return WMCreateTreeNodeWithDestructor(data, NULL);
36 }
38 WMTreeNode *WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc * destructor)
39 {
40 WMTreeNode *aNode;
42 aNode = (WMTreeNode *) wmalloc(sizeof(W_TreeNode));
43 memset(aNode, 0, sizeof(W_TreeNode));
45 aNode->destructor = destructor;
47 aNode->data = data;
48 aNode->parent = NULL;
49 aNode->depth = 0;
50 aNode->leaves = NULL;
51 /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
53 return aNode;
54 }
56 WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
57 {
58 WMTreeNode *aNode;
60 wassertrv(parent != NULL, NULL);
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 }
74 return aNode;
75 }
77 static void updateNodeDepth(WMTreeNode * aNode, int depth)
78 {
79 int i;
81 aNode->depth = depth;
83 if (aNode->leaves) {
84 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
85 updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
86 }
87 }
88 }
90 WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
91 {
92 wassertrv(parent != NULL, NULL);
93 wassertrv(aNode != NULL, NULL);
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);
106 return aNode;
109 void WMDestroyTreeNode(WMTreeNode * aNode)
111 wassertr(aNode != NULL);
113 if (aNode->parent && aNode->parent->leaves) {
114 WMRemoveFromArray(aNode->parent->leaves, aNode);
115 } else {
116 destroyNode(aNode);
120 void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
122 wassertr(aNode != NULL);
123 wassertr(aNode->leaves != NULL);
125 WMDeleteFromArray(aNode->leaves, index);
128 static int sameData(void *item, void *data)
130 return (((WMTreeNode *) item)->data == data);
133 void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
135 int index;
137 wassertr(aNode != NULL);
138 wassertr(aNode->leaves != NULL);
140 index = WMFindInArray(aNode->leaves, sameData, leaf);
141 if (index != WANotFound) {
142 WMDeleteFromArray(aNode->leaves, index);
146 void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
148 void *old;
150 wassertrv(aNode != NULL, NULL);
152 old = aNode->data;
153 aNode->data = newData;
155 return old;
158 void *WMGetDataForTreeNode(WMTreeNode * aNode)
160 return aNode->data;
163 int WMGetTreeNodeDepth(WMTreeNode * aNode)
165 return aNode->depth;
168 WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
170 return aNode->parent;
173 void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
175 wassertr(aNode != NULL);
177 if (aNode->leaves) {
178 WMSortArray(aNode->leaves, comparer);
182 static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
184 int i;
186 if (!aNode->leaves)
187 return;
189 WMSortArray(aNode->leaves, comparer);
190 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
191 sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
195 void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
197 wassertr(aNode != NULL);
199 sortLeavesForNode(aNode, comparer);
202 static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
204 if (match == NULL) {
205 if (aNode->data == cdata) {
206 return aNode;
208 } else {
209 if ((*match) (aNode->data, cdata)) {
210 return aNode;
214 if (aNode->leaves) {
215 WMTreeNode *leaf;
216 int i;
218 for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
219 leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata);
220 if (leaf) {
221 return leaf;
226 return NULL;
229 WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
231 wassertrv(aTree != NULL, NULL);
233 return findNodeInTree(aTree, match, cdata);