OSDN -- 開發和下載開源軟體
繁體中文翻譯狀態 translation status for zh-tw
  • R/O
  • SSH
  • HTTPS

bchan: 提交


Commit MetaInfo

修訂542 (tree)
時間2013-04-25 01:11:36
作者ornse01

Log Message

implement basic tree structure and functions.

Change Summary

差異

--- bchanf/trunk/src/coll/treebase.h (nonexistent)
+++ bchanf/trunk/src/coll/treebase.h (revision 542)
@@ -0,0 +1,92 @@
1+/*
2+ * treebase.h
3+ *
4+ * Copyright (c) 2013 project bchan
5+ *
6+ * This software is provided 'as-is', without any express or implied
7+ * warranty. In no event will the authors be held liable for any damages
8+ * arising from the use of this software.
9+ *
10+ * Permission is granted to anyone to use this software for any purpose,
11+ * including commercial applications, and to alter it and redistribute it
12+ * freely, subject to the following restrictions:
13+ *
14+ * 1. The origin of this software must not be misrepresented; you must not
15+ * claim that you wrote the original software. If you use this software
16+ * in a product, an acknowledgment in the product documentation would be
17+ * appreciated but is not required.
18+ *
19+ * 2. Altered source versions must be plainly marked as such, and must not be
20+ * misrepresented as being the original software.
21+ *
22+ * 3. This notice may not be removed or altered from any source
23+ * distribution.
24+ *
25+ */
26+
27+#include <basic.h>
28+#include <bsys/queue.h>
29+
30+/* Vendor name: */
31+/* Functionality name: treebase */
32+/* Detail name: */
33+
34+#ifndef __TREEBASE_H__
35+#define __TREEBASE_H__
36+
37+/* Functionality name: treebase */
38+/* Detail name: node */
39+struct treebase_node_t_ {
40+ QUEUE sibling;
41+ struct treebase_node_t_ *firstchild;
42+ struct treebase_node_t_ *parent;
43+};
44+typedef struct treebase_node_t_ treebase_node_t;
45+
46+IMPORT VOID treebase_node_initialize(treebase_node_t *node);
47+IMPORT VOID treebase_node_finalize(treebase_node_t *node);
48+IMPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child);
49+IMPORT VOID treebase_node_remove(treebase_node_t *node);
50+IMPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node);
51+IMPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node);
52+IMPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node);
53+IMPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node);
54+IMPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node);
55+IMPORT Bool treebase_node_haschild(treebase_node_t *node);
56+
57+/* Functionality name: treebase */
58+/* Detail name: traversal */
59+/* Data structure identifier: direction */
60+enum TREEBASE_TRAVERSAL_DIRECTION_ {
61+ TREEBASE_TRAVERSAL_DIRECTION_UP,
62+ TREEBASE_TRAVERSAL_DIRECTION_DOWN
63+};
64+typedef enum TREEBASE_TRAVERSAL_DIRECTION_ TREEBASE_TRAVERSAL_DIRECTION;
65+
66+/* Functionality name: treebase */
67+/* Detail name: preordertraversal */
68+struct treebase_preordertraversal_t_ {
69+ treebase_node_t *root;
70+ treebase_node_t *current;
71+ TREEBASE_TRAVERSAL_DIRECTION dir;
72+};
73+typedef struct treebase_preordertraversal_t_ treebase_preordertraversal_t;
74+
75+IMPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root);
76+IMPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal);
77+IMPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir);
78+
79+/* Functionality name: treebase */
80+/* Detail name: postordertraversal */
81+struct treebase_postordertraversal_t_ {
82+ treebase_node_t *root;
83+ treebase_node_t *current;
84+ TREEBASE_TRAVERSAL_DIRECTION dir;
85+};
86+typedef struct treebase_postordertraversal_t_ treebase_postordertraversal_t;
87+
88+IMPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root);
89+IMPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal);
90+IMPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir);
91+
92+#endif
Added: svn:eol-style
## -0,0 +1 ##
+LF
\ No newline at end of property
--- bchanf/trunk/src/coll/test_treebase.c (nonexistent)
+++ bchanf/trunk/src/coll/test_treebase.c (revision 542)
@@ -0,0 +1,321 @@
1+/*
2+ * test_treebase.c
3+ *
4+ * Copyright (c) 2013 project bchan
5+ *
6+ * This software is provided 'as-is', without any express or implied
7+ * warranty. In no event will the authors be held liable for any damages
8+ * arising from the use of this software.
9+ *
10+ * Permission is granted to anyone to use this software for any purpose,
11+ * including commercial applications, and to alter it and redistribute it
12+ * freely, subject to the following restrictions:
13+ *
14+ * 1. The origin of this software must not be misrepresented; you must not
15+ * claim that you wrote the original software. If you use this software
16+ * in a product, an acknowledgment in the product documentation would be
17+ * appreciated but is not required.
18+ *
19+ * 2. Altered source versions must be plainly marked as such, and must not be
20+ * misrepresented as being the original software.
21+ *
22+ * 3. This notice may not be removed or altered from any source
23+ * distribution.
24+ *
25+ */
26+
27+#include "test_coll.h"
28+
29+#include "treebase.h"
30+
31+#include <basic.h>
32+#include <bstdio.h>
33+
34+#include <unittest_driver.h>
35+
36+typedef struct {
37+ treebase_node_t *parent;
38+ treebase_node_t *next;
39+ treebase_node_t *prev;
40+ treebase_node_t *first;
41+ treebase_node_t *last;
42+ Bool has_child;
43+} test_treebase_node_expected_t;
44+
45+LOCAL Bool test_treebase_node_commoncheck(treebase_node_t *node, test_treebase_node_expected_t *expected, UB *msg)
46+{
47+ treebase_node_t *node1;
48+ Bool ret = True, ok;
49+
50+ node1 = treebase_node_getparent(node);
51+ if (node1 != expected->parent) {
52+ printf("%s: parent is not expected\n", msg);
53+ ret = False;
54+ }
55+ node1 = treebase_node_getnextsibling(node);
56+ if (node1 != expected->next) {
57+ printf("%s: next sibling is not expected\n", msg);
58+ ret = False;
59+ }
60+ node1 = treebase_node_getprevsibling(node);
61+ if (node1 != expected->prev) {
62+ printf("%s: prev sibling is not expected\n", msg);
63+ ret = False;
64+ }
65+ node1 = treebase_node_getfirstchild(node);
66+ if (node1 != expected->first) {
67+ printf("%s: first child is not expected\n", msg);
68+ ret = False;
69+ }
70+ node1 = treebase_node_getlastchild(node);
71+ if (node1 != expected->last) {
72+ printf("%s: last child is not expected\n", msg);
73+ ret = False;
74+ }
75+ ok = treebase_node_haschild(node);
76+ if (ok != expected->has_child) {
77+ printf("%s: has child is not expected\n", msg);
78+ ret = False;
79+ }
80+
81+ return ret;
82+}
83+
84+LOCAL UNITTEST_RESULT test_treebase_node_1()
85+{
86+ treebase_node_t node;
87+
88+ treebase_node_initialize(&node);
89+ treebase_node_finalize(&node);
90+
91+ return UNITTEST_RESULT_PASS;
92+}
93+
94+LOCAL UNITTEST_RESULT test_treebase_node_2()
95+{
96+ treebase_node_t node;
97+ test_treebase_node_expected_t expected;
98+ Bool ok;
99+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
100+
101+ treebase_node_initialize(&node);
102+
103+ expected.parent = NULL;
104+ expected.next = NULL;
105+ expected.prev = NULL;
106+ expected.first = NULL;
107+ expected.last = NULL;
108+ expected.has_child = False;
109+ ok = test_treebase_node_commoncheck(&node, &expected, "node");
110+ if (ok == False) {
111+ ret = UNITTEST_RESULT_FAIL;
112+ }
113+
114+ treebase_node_finalize(&node);
115+
116+ return ret;
117+}
118+
119+LOCAL UNITTEST_RESULT test_treebase_node_3()
120+{
121+ treebase_node_t node0, node1;
122+ test_treebase_node_expected_t expected;
123+ Bool ok;
124+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
125+
126+ treebase_node_initialize(&node0);
127+ treebase_node_initialize(&node1);
128+
129+ treebase_node_appendchild(&node0, &node1);
130+
131+ /**/
132+ expected.parent = NULL;
133+ expected.next = NULL;
134+ expected.prev = NULL;
135+ expected.first = &node1;
136+ expected.last = &node1;
137+ expected.has_child = True;
138+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
139+ if (ok == False) {
140+ ret = UNITTEST_RESULT_FAIL;
141+ }
142+ /**/
143+ expected.parent = &node0;
144+ expected.next = NULL;
145+ expected.prev = NULL;
146+ expected.first = NULL;
147+ expected.last = NULL;
148+ expected.has_child = False;
149+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
150+ if (ok == False) {
151+ ret = UNITTEST_RESULT_FAIL;
152+ }
153+
154+ treebase_node_finalize(&node1);
155+ treebase_node_finalize(&node0);
156+
157+ return ret;
158+}
159+
160+LOCAL UNITTEST_RESULT test_treebase_node_4()
161+{
162+ treebase_node_t node0, node1;
163+ test_treebase_node_expected_t expected;
164+ Bool ok;
165+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
166+
167+ treebase_node_initialize(&node0);
168+ treebase_node_initialize(&node1);
169+
170+ treebase_node_appendchild(&node0, &node1);
171+ treebase_node_remove(&node1);
172+
173+ /**/
174+ expected.parent = NULL;
175+ expected.next = NULL;
176+ expected.prev = NULL;
177+ expected.first = NULL;
178+ expected.last = NULL;
179+ expected.has_child = False;
180+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
181+ if (ok == False) {
182+ ret = UNITTEST_RESULT_FAIL;
183+ }
184+ /**/
185+ expected.parent = NULL;
186+ expected.next = NULL;
187+ expected.prev = NULL;
188+ expected.first = NULL;
189+ expected.last = NULL;
190+ expected.has_child = False;
191+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
192+ if (ok == False) {
193+ ret = UNITTEST_RESULT_FAIL;
194+ }
195+
196+ treebase_node_finalize(&node1);
197+ treebase_node_finalize(&node0);
198+
199+ return ret;
200+}
201+
202+LOCAL UNITTEST_RESULT test_treebase_node_5()
203+{
204+ treebase_node_t node0, node1, node2;
205+ test_treebase_node_expected_t expected;
206+ Bool ok;
207+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
208+
209+ treebase_node_initialize(&node0);
210+ treebase_node_initialize(&node1);
211+ treebase_node_initialize(&node2);
212+
213+ treebase_node_appendchild(&node0, &node1);
214+ treebase_node_appendchild(&node0, &node2);
215+
216+ /**/
217+ expected.parent = NULL;
218+ expected.next = NULL;
219+ expected.prev = NULL;
220+ expected.first = &node1;
221+ expected.last = &node2;
222+ expected.has_child = True;
223+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
224+ if (ok == False) {
225+ ret = UNITTEST_RESULT_FAIL;
226+ }
227+ /**/
228+ expected.parent = &node0;
229+ expected.next = &node2;
230+ expected.prev = NULL;
231+ expected.first = NULL;
232+ expected.last = NULL;
233+ expected.has_child = False;
234+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
235+ if (ok == False) {
236+ ret = UNITTEST_RESULT_FAIL;
237+ }
238+ /**/
239+ expected.parent = &node0;
240+ expected.next = NULL;
241+ expected.prev = &node1;
242+ expected.first = NULL;
243+ expected.last = NULL;
244+ expected.has_child = False;
245+ ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
246+ if (ok == False) {
247+ ret = UNITTEST_RESULT_FAIL;
248+ }
249+
250+ treebase_node_finalize(&node2);
251+ treebase_node_finalize(&node1);
252+ treebase_node_finalize(&node0);
253+
254+ return ret;
255+}
256+
257+LOCAL UNITTEST_RESULT test_treebase_node_6()
258+{
259+ treebase_node_t node0, node1, node2;
260+ test_treebase_node_expected_t expected;
261+ Bool ok;
262+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
263+
264+ treebase_node_initialize(&node0);
265+ treebase_node_initialize(&node1);
266+ treebase_node_initialize(&node2);
267+
268+ treebase_node_appendchild(&node0, &node1);
269+ treebase_node_appendchild(&node1, &node2);
270+
271+ /**/
272+ expected.parent = NULL;
273+ expected.next = NULL;
274+ expected.prev = NULL;
275+ expected.first = &node1;
276+ expected.last = &node1;
277+ expected.has_child = True;
278+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
279+ if (ok == False) {
280+ ret = UNITTEST_RESULT_FAIL;
281+ }
282+ /**/
283+ expected.parent = &node0;
284+ expected.next = NULL;
285+ expected.prev = NULL;
286+ expected.first = &node2;
287+ expected.last = &node2;
288+ expected.has_child = True;
289+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
290+ if (ok == False) {
291+ ret = UNITTEST_RESULT_FAIL;
292+ }
293+ /**/
294+ expected.parent = &node1;
295+ expected.next = NULL;
296+ expected.prev = NULL;
297+ expected.first = NULL;
298+ expected.last = NULL;
299+ expected.has_child = False;
300+ ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
301+ if (ok == False) {
302+ ret = UNITTEST_RESULT_FAIL;
303+ }
304+
305+ treebase_node_finalize(&node2);
306+ treebase_node_finalize(&node1);
307+ treebase_node_finalize(&node0);
308+
309+ return ret;
310+}
311+
312+
313+EXPORT VOID test_treebase_main(unittest_driver_t *driver)
314+{
315+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_1);
316+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_2);
317+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_3);
318+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_4);
319+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_5);
320+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_6);
321+}
Added: svn:eol-style
## -0,0 +1 ##
+LF
\ No newline at end of property
--- bchanf/trunk/src/coll/treebase.c (nonexistent)
+++ bchanf/trunk/src/coll/treebase.c (revision 542)
@@ -0,0 +1,225 @@
1+/*
2+ * treebase.c
3+ *
4+ * Copyright (c) 2013 project bchan
5+ *
6+ * This software is provided 'as-is', without any express or implied
7+ * warranty. In no event will the authors be held liable for any damages
8+ * arising from the use of this software.
9+ *
10+ * Permission is granted to anyone to use this software for any purpose,
11+ * including commercial applications, and to alter it and redistribute it
12+ * freely, subject to the following restrictions:
13+ *
14+ * 1. The origin of this software must not be misrepresented; you must not
15+ * claim that you wrote the original software. If you use this software
16+ * in a product, an acknowledgment in the product documentation would be
17+ * appreciated but is not required.
18+ *
19+ * 2. Altered source versions must be plainly marked as such, and must not be
20+ * misrepresented as being the original software.
21+ *
22+ * 3. This notice may not be removed or altered from any source
23+ * distribution.
24+ *
25+ */
26+
27+#include "treebase.h"
28+
29+#include <basic.h>
30+#include <bstdio.h>
31+#include <bsys/queue.h>
32+
33+EXPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child)
34+{
35+ Bool ok;
36+
37+ ok = treebase_node_haschild(node);
38+ if (ok == False) {
39+ node->firstchild = child;
40+ } else {
41+ QueInsert(&child->sibling, &node->firstchild->sibling);
42+ }
43+ child->parent = node;
44+}
45+
46+EXPORT VOID treebase_node_remove(treebase_node_t *node)
47+{
48+ if (node->parent == NULL) { /* root node */
49+ return;
50+ }
51+ if (node->parent->firstchild == node) {
52+ node->parent->firstchild = treebase_node_getnextsibling(node);
53+ }
54+ QueRemove(&node->sibling);
55+ node->parent = NULL;
56+}
57+
58+EXPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node)
59+{
60+ return node->parent;
61+}
62+
63+EXPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node)
64+{
65+ Bool empty;
66+ treebase_node_t *parent, *last;
67+ empty = isQueEmpty(&node->sibling);
68+ if (empty != False) {
69+ return NULL;
70+ }
71+ parent = treebase_node_getparent(node);
72+ if (parent == NULL) {
73+ return NULL;
74+ }
75+ last = treebase_node_getlastchild(parent);
76+ if (node == last) {
77+ return NULL;
78+ }
79+ return (treebase_node_t*)node->sibling.next;
80+}
81+
82+EXPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node)
83+{
84+ Bool empty;
85+ treebase_node_t *parent, *first;
86+ empty = isQueEmpty(&node->sibling);
87+ if (empty != False) {
88+ return NULL;
89+ }
90+ parent = treebase_node_getparent(node);
91+ if (parent == NULL) {
92+ return NULL;
93+ }
94+ first = treebase_node_getfirstchild(parent);
95+ if (node == first) {
96+ return NULL;
97+ }
98+ return (treebase_node_t*)node->sibling.prev;
99+}
100+
101+EXPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node)
102+{
103+ return node->firstchild;
104+}
105+
106+EXPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node)
107+{
108+ if (node->firstchild == NULL) {
109+ return NULL;
110+ }
111+ return (treebase_node_t*)node->firstchild->sibling.prev;
112+}
113+
114+EXPORT Bool treebase_node_haschild(treebase_node_t *node)
115+{
116+ if (node->firstchild == NULL) {
117+ return False;
118+ }
119+ return True;
120+}
121+
122+EXPORT VOID treebase_node_initialize(treebase_node_t *node)
123+{
124+ QueInit(&node->sibling);
125+ node->firstchild = NULL;
126+ node->parent = NULL;
127+}
128+
129+EXPORT VOID treebase_node_finalize(treebase_node_t *node)
130+{
131+}
132+
133+
134+EXPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
135+{
136+ treebase_node_t *child, *sibling;
137+
138+ if (traversal->current == NULL) {
139+ return False;
140+ }
141+
142+ *node = traversal->current;
143+ *dir = traversal->dir;
144+
145+ if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
146+ child = treebase_node_getfirstchild(traversal->current);
147+ if (child == NULL) {
148+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
149+ } else {
150+ traversal->current = child;
151+ }
152+ } else {
153+ sibling = treebase_node_getnextsibling(traversal->current);
154+ if (sibling == NULL) {
155+ if (traversal->current == traversal->root) {
156+ traversal->current = NULL;
157+ } else {
158+ traversal->current = treebase_node_getparent(traversal->current);
159+ }
160+ } else {
161+ traversal->current = sibling;
162+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
163+ }
164+ }
165+
166+ return True;
167+}
168+
169+EXPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root)
170+{
171+ traversal->root = root;
172+ traversal->current = root;
173+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
174+}
175+
176+EXPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal)
177+{
178+}
179+
180+
181+EXPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
182+{
183+ treebase_node_t *child, *sibling;
184+
185+ if (traversal->current == NULL) {
186+ return False;
187+ }
188+
189+ *node = traversal->current;
190+ *dir = traversal->dir;
191+
192+ if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
193+ child = treebase_node_getlastchild(traversal->current);
194+ if (child == NULL) {
195+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
196+ } else {
197+ traversal->current = child;
198+ }
199+ } else {
200+ sibling = treebase_node_getprevsibling(traversal->current);
201+ if (sibling == NULL) {
202+ if (traversal->current == traversal->root) {
203+ traversal->current = NULL;
204+ } else {
205+ traversal->current = treebase_node_getparent(traversal->current);
206+ }
207+ } else {
208+ traversal->current = sibling;
209+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
210+ }
211+ }
212+
213+ return True;
214+}
215+
216+EXPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root)
217+{
218+ traversal->root = root;
219+ traversal->current = root;
220+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
221+}
222+
223+EXPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal)
224+{
225+}
Added: svn:eol-style
## -0,0 +1 ##
+LF
\ No newline at end of property
Show on old repository browser