4 * Copyright (c) 2013-2014 project bchan
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.
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:
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.
19 * 2. Altered source versions must be plainly marked as such, and must not be
20 * misrepresented as being the original software.
22 * 3. This notice may not be removed or altered from any source
31 #include <bsys/queue.h>
33 EXPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child)
37 ok = treebase_node_haschild(node);
39 node->firstchild = child;
41 QueInsert(&child->sibling, &node->firstchild->sibling);
46 EXPORT W treebase_node_insertbefore(treebase_node_t *node, treebase_node_t *child, treebase_node_t *ref)
49 treebase_node_appendchild(node, child);
52 if (ref->parent != node) {
56 QueInsert(&child->sibling, &ref->sibling);
62 EXPORT VOID treebase_node_remove(treebase_node_t *node)
64 if (node->parent == NULL) { /* root node */
67 if (node->parent->firstchild == node) {
68 node->parent->firstchild = treebase_node_getnextsibling(node);
70 QueRemove(&node->sibling);
74 EXPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node)
79 EXPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node)
82 treebase_node_t *parent, *last;
83 empty = isQueEmpty(&node->sibling);
87 parent = treebase_node_getparent(node);
91 last = treebase_node_getlastchild(parent);
95 return (treebase_node_t*)node->sibling.next;
98 EXPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node)
101 treebase_node_t *parent, *first;
102 empty = isQueEmpty(&node->sibling);
103 if (empty != False) {
106 parent = treebase_node_getparent(node);
107 if (parent == NULL) {
110 first = treebase_node_getfirstchild(parent);
114 return (treebase_node_t*)node->sibling.prev;
117 EXPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node)
119 return node->firstchild;
122 EXPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node)
124 if (node->firstchild == NULL) {
127 return (treebase_node_t*)node->firstchild->sibling.prev;
130 EXPORT Bool treebase_node_haschild(treebase_node_t *node)
132 if (node->firstchild == NULL) {
138 EXPORT VOID treebase_node_initialize(treebase_node_t *node)
140 QueInit(&node->sibling);
141 node->firstchild = NULL;
145 EXPORT VOID treebase_node_finalize(treebase_node_t *node)
147 treebase_node_remove(node);
151 EXPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
153 treebase_node_t *child, *sibling;
155 if (traversal->current == NULL) {
159 *node = traversal->current;
160 *dir = traversal->dir;
162 if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
163 child = treebase_node_getfirstchild(traversal->current);
165 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
167 traversal->current = child;
170 sibling = treebase_node_getnextsibling(traversal->current);
171 if (sibling == NULL) {
172 if (traversal->current == traversal->root) {
173 traversal->current = NULL;
175 traversal->current = treebase_node_getparent(traversal->current);
178 traversal->current = sibling;
179 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
186 EXPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root)
188 traversal->root = root;
189 traversal->current = root;
190 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
193 EXPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal)
198 EXPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
200 treebase_node_t *child, *sibling;
202 if (traversal->current == NULL) {
206 *node = traversal->current;
207 *dir = traversal->dir;
209 if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
210 child = treebase_node_getlastchild(traversal->current);
212 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
214 traversal->current = child;
217 sibling = treebase_node_getprevsibling(traversal->current);
218 if (sibling == NULL) {
219 if (traversal->current == traversal->root) {
220 traversal->current = NULL;
222 traversal->current = treebase_node_getparent(traversal->current);
225 traversal->current = sibling;
226 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
233 EXPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root)
235 traversal->root = root;
236 traversal->current = root;
237 traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
240 EXPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal)