--- /dev/null
+/*
+ * test_treebase.c
+ *
+ * Copyright (c) 2013 project bchan
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ *
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ *
+ * 3. This notice may not be removed or altered from any source
+ * distribution.
+ *
+ */
+
+#include "test_coll.h"
+
+#include "treebase.h"
+
+#include <basic.h>
+#include <bstdio.h>
+
+#include <unittest_driver.h>
+
+typedef struct {
+ treebase_node_t *parent;
+ treebase_node_t *next;
+ treebase_node_t *prev;
+ treebase_node_t *first;
+ treebase_node_t *last;
+ Bool has_child;
+} test_treebase_node_expected_t;
+
+LOCAL Bool test_treebase_node_commoncheck(treebase_node_t *node, test_treebase_node_expected_t *expected, UB *msg)
+{
+ treebase_node_t *node1;
+ Bool ret = True, ok;
+
+ node1 = treebase_node_getparent(node);
+ if (node1 != expected->parent) {
+ printf("%s: parent is not expected\n", msg);
+ ret = False;
+ }
+ node1 = treebase_node_getnextsibling(node);
+ if (node1 != expected->next) {
+ printf("%s: next sibling is not expected\n", msg);
+ ret = False;
+ }
+ node1 = treebase_node_getprevsibling(node);
+ if (node1 != expected->prev) {
+ printf("%s: prev sibling is not expected\n", msg);
+ ret = False;
+ }
+ node1 = treebase_node_getfirstchild(node);
+ if (node1 != expected->first) {
+ printf("%s: first child is not expected\n", msg);
+ ret = False;
+ }
+ node1 = treebase_node_getlastchild(node);
+ if (node1 != expected->last) {
+ printf("%s: last child is not expected\n", msg);
+ ret = False;
+ }
+ ok = treebase_node_haschild(node);
+ if (ok != expected->has_child) {
+ printf("%s: has child is not expected\n", msg);
+ ret = False;
+ }
+
+ return ret;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_1()
+{
+ treebase_node_t node;
+
+ treebase_node_initialize(&node);
+ treebase_node_finalize(&node);
+
+ return UNITTEST_RESULT_PASS;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_2()
+{
+ treebase_node_t node;
+ test_treebase_node_expected_t expected;
+ Bool ok;
+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
+
+ treebase_node_initialize(&node);
+
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node, &expected, "node");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+
+ treebase_node_finalize(&node);
+
+ return ret;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_3()
+{
+ treebase_node_t node0, node1;
+ test_treebase_node_expected_t expected;
+ Bool ok;
+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
+
+ treebase_node_initialize(&node0);
+ treebase_node_initialize(&node1);
+
+ treebase_node_appendchild(&node0, &node1);
+
+ /**/
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = &node1;
+ expected.last = &node1;
+ expected.has_child = True;
+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = &node0;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+
+ treebase_node_finalize(&node1);
+ treebase_node_finalize(&node0);
+
+ return ret;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_4()
+{
+ treebase_node_t node0, node1;
+ test_treebase_node_expected_t expected;
+ Bool ok;
+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
+
+ treebase_node_initialize(&node0);
+ treebase_node_initialize(&node1);
+
+ treebase_node_appendchild(&node0, &node1);
+ treebase_node_remove(&node1);
+
+ /**/
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+
+ treebase_node_finalize(&node1);
+ treebase_node_finalize(&node0);
+
+ return ret;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_5()
+{
+ treebase_node_t node0, node1, node2;
+ test_treebase_node_expected_t expected;
+ Bool ok;
+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
+
+ treebase_node_initialize(&node0);
+ treebase_node_initialize(&node1);
+ treebase_node_initialize(&node2);
+
+ treebase_node_appendchild(&node0, &node1);
+ treebase_node_appendchild(&node0, &node2);
+
+ /**/
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = &node1;
+ expected.last = &node2;
+ expected.has_child = True;
+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = &node0;
+ expected.next = &node2;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = &node0;
+ expected.next = NULL;
+ expected.prev = &node1;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+
+ treebase_node_finalize(&node2);
+ treebase_node_finalize(&node1);
+ treebase_node_finalize(&node0);
+
+ return ret;
+}
+
+LOCAL UNITTEST_RESULT test_treebase_node_6()
+{
+ treebase_node_t node0, node1, node2;
+ test_treebase_node_expected_t expected;
+ Bool ok;
+ UNITTEST_RESULT ret = UNITTEST_RESULT_PASS;
+
+ treebase_node_initialize(&node0);
+ treebase_node_initialize(&node1);
+ treebase_node_initialize(&node2);
+
+ treebase_node_appendchild(&node0, &node1);
+ treebase_node_appendchild(&node1, &node2);
+
+ /**/
+ expected.parent = NULL;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = &node1;
+ expected.last = &node1;
+ expected.has_child = True;
+ ok = test_treebase_node_commoncheck(&node0, &expected, "node0");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = &node0;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = &node2;
+ expected.last = &node2;
+ expected.has_child = True;
+ ok = test_treebase_node_commoncheck(&node1, &expected, "node1");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+ /**/
+ expected.parent = &node1;
+ expected.next = NULL;
+ expected.prev = NULL;
+ expected.first = NULL;
+ expected.last = NULL;
+ expected.has_child = False;
+ ok = test_treebase_node_commoncheck(&node2, &expected, "node2");
+ if (ok == False) {
+ ret = UNITTEST_RESULT_FAIL;
+ }
+
+ treebase_node_finalize(&node2);
+ treebase_node_finalize(&node1);
+ treebase_node_finalize(&node0);
+
+ return ret;
+}
+
+
+EXPORT VOID test_treebase_main(unittest_driver_t *driver)
+{
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_1);
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_2);
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_3);
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_4);
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_5);
+ UNITTEST_DRIVER_REGIST(driver, test_treebase_node_6);
+}
--- /dev/null
+/*
+ * treebase.c
+ *
+ * Copyright (c) 2013 project bchan
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ *
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ *
+ * 3. This notice may not be removed or altered from any source
+ * distribution.
+ *
+ */
+
+#include "treebase.h"
+
+#include <basic.h>
+#include <bstdio.h>
+#include <bsys/queue.h>
+
+EXPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child)
+{
+ Bool ok;
+
+ ok = treebase_node_haschild(node);
+ if (ok == False) {
+ node->firstchild = child;
+ } else {
+ QueInsert(&child->sibling, &node->firstchild->sibling);
+ }
+ child->parent = node;
+}
+
+EXPORT VOID treebase_node_remove(treebase_node_t *node)
+{
+ if (node->parent == NULL) { /* root node */
+ return;
+ }
+ if (node->parent->firstchild == node) {
+ node->parent->firstchild = treebase_node_getnextsibling(node);
+ }
+ QueRemove(&node->sibling);
+ node->parent = NULL;
+}
+
+EXPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node)
+{
+ return node->parent;
+}
+
+EXPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node)
+{
+ Bool empty;
+ treebase_node_t *parent, *last;
+ empty = isQueEmpty(&node->sibling);
+ if (empty != False) {
+ return NULL;
+ }
+ parent = treebase_node_getparent(node);
+ if (parent == NULL) {
+ return NULL;
+ }
+ last = treebase_node_getlastchild(parent);
+ if (node == last) {
+ return NULL;
+ }
+ return (treebase_node_t*)node->sibling.next;
+}
+
+EXPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node)
+{
+ Bool empty;
+ treebase_node_t *parent, *first;
+ empty = isQueEmpty(&node->sibling);
+ if (empty != False) {
+ return NULL;
+ }
+ parent = treebase_node_getparent(node);
+ if (parent == NULL) {
+ return NULL;
+ }
+ first = treebase_node_getfirstchild(parent);
+ if (node == first) {
+ return NULL;
+ }
+ return (treebase_node_t*)node->sibling.prev;
+}
+
+EXPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node)
+{
+ return node->firstchild;
+}
+
+EXPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node)
+{
+ if (node->firstchild == NULL) {
+ return NULL;
+ }
+ return (treebase_node_t*)node->firstchild->sibling.prev;
+}
+
+EXPORT Bool treebase_node_haschild(treebase_node_t *node)
+{
+ if (node->firstchild == NULL) {
+ return False;
+ }
+ return True;
+}
+
+EXPORT VOID treebase_node_initialize(treebase_node_t *node)
+{
+ QueInit(&node->sibling);
+ node->firstchild = NULL;
+ node->parent = NULL;
+}
+
+EXPORT VOID treebase_node_finalize(treebase_node_t *node)
+{
+}
+
+
+EXPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
+{
+ treebase_node_t *child, *sibling;
+
+ if (traversal->current == NULL) {
+ return False;
+ }
+
+ *node = traversal->current;
+ *dir = traversal->dir;
+
+ if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
+ child = treebase_node_getfirstchild(traversal->current);
+ if (child == NULL) {
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
+ } else {
+ traversal->current = child;
+ }
+ } else {
+ sibling = treebase_node_getnextsibling(traversal->current);
+ if (sibling == NULL) {
+ if (traversal->current == traversal->root) {
+ traversal->current = NULL;
+ } else {
+ traversal->current = treebase_node_getparent(traversal->current);
+ }
+ } else {
+ traversal->current = sibling;
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
+ }
+ }
+
+ return True;
+}
+
+EXPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root)
+{
+ traversal->root = root;
+ traversal->current = root;
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
+}
+
+EXPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal)
+{
+}
+
+
+EXPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
+{
+ treebase_node_t *child, *sibling;
+
+ if (traversal->current == NULL) {
+ return False;
+ }
+
+ *node = traversal->current;
+ *dir = traversal->dir;
+
+ if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
+ child = treebase_node_getlastchild(traversal->current);
+ if (child == NULL) {
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
+ } else {
+ traversal->current = child;
+ }
+ } else {
+ sibling = treebase_node_getprevsibling(traversal->current);
+ if (sibling == NULL) {
+ if (traversal->current == traversal->root) {
+ traversal->current = NULL;
+ } else {
+ traversal->current = treebase_node_getparent(traversal->current);
+ }
+ } else {
+ traversal->current = sibling;
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
+ }
+ }
+
+ return True;
+}
+
+EXPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root)
+{
+ traversal->root = root;
+ traversal->current = root;
+ traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
+}
+
+EXPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal)
+{
+}
--- /dev/null
+/*
+ * treebase.h
+ *
+ * Copyright (c) 2013 project bchan
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ *
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ *
+ * 3. This notice may not be removed or altered from any source
+ * distribution.
+ *
+ */
+
+#include <basic.h>
+#include <bsys/queue.h>
+
+/* Vendor name: */
+/* Functionality name: treebase */
+/* Detail name: */
+
+#ifndef __TREEBASE_H__
+#define __TREEBASE_H__
+
+/* Functionality name: treebase */
+/* Detail name: node */
+struct treebase_node_t_ {
+ QUEUE sibling;
+ struct treebase_node_t_ *firstchild;
+ struct treebase_node_t_ *parent;
+};
+typedef struct treebase_node_t_ treebase_node_t;
+
+IMPORT VOID treebase_node_initialize(treebase_node_t *node);
+IMPORT VOID treebase_node_finalize(treebase_node_t *node);
+IMPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child);
+IMPORT VOID treebase_node_remove(treebase_node_t *node);
+IMPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node);
+IMPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node);
+IMPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node);
+IMPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node);
+IMPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node);
+IMPORT Bool treebase_node_haschild(treebase_node_t *node);
+
+/* Functionality name: treebase */
+/* Detail name: traversal */
+/* Data structure identifier: direction */
+enum TREEBASE_TRAVERSAL_DIRECTION_ {
+ TREEBASE_TRAVERSAL_DIRECTION_UP,
+ TREEBASE_TRAVERSAL_DIRECTION_DOWN
+};
+typedef enum TREEBASE_TRAVERSAL_DIRECTION_ TREEBASE_TRAVERSAL_DIRECTION;
+
+/* Functionality name: treebase */
+/* Detail name: preordertraversal */
+struct treebase_preordertraversal_t_ {
+ treebase_node_t *root;
+ treebase_node_t *current;
+ TREEBASE_TRAVERSAL_DIRECTION dir;
+};
+typedef struct treebase_preordertraversal_t_ treebase_preordertraversal_t;
+
+IMPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root);
+IMPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal);
+IMPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir);
+
+/* Functionality name: treebase */
+/* Detail name: postordertraversal */
+struct treebase_postordertraversal_t_ {
+ treebase_node_t *root;
+ treebase_node_t *current;
+ TREEBASE_TRAVERSAL_DIRECTION dir;
+};
+typedef struct treebase_postordertraversal_t_ treebase_postordertraversal_t;
+
+IMPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root);
+IMPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal);
+IMPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir);
+
+#endif
OSDN Git Service
