src/coll/treebase.c

   1 /*
   2  * treebase.c
   3  *
   4  * Copyright (c) 2013-2014 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 W treebase_node_insertbefore(treebase_node_t *node, treebase_node_t *child, treebase_node_t *ref)
  47 {
  48         if (ref == NULL) {
  49                 treebase_node_appendchild(node, child);
  50                 return 0;
  51         }
  52         if (ref->parent != node) {
  53                 return -1; /* TODO */
  54         }
  55
  56         QueInsert(&child->sibling, &ref->sibling);
  57         child->parent = node;
  58
  59         return 0;
  60 }
  61
  62 EXPORT VOID treebase_node_remove(treebase_node_t *node)
  63 {
  64         if (node->parent == NULL) { /* root node */
  65                 return;
  66         }
  67         if (node->parent->firstchild == node) {
  68                 node->parent->firstchild = treebase_node_getnextsibling(node);
  69         }
  70         QueRemove(&node->sibling);
  71         node->parent = NULL;
  72 }
  73
  74 EXPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node)
  75 {
  76         return node->parent;
  77 }
  78
  79 EXPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node)
  80 {
  81         Bool empty;
  82         treebase_node_t *parent, *last;
  83         empty = isQueEmpty(&node->sibling);
  84         if (empty != False) {
  85                 return NULL;
  86         }
  87         parent = treebase_node_getparent(node);
  88         if (parent == NULL) {
  89                 return NULL;
  90         }
  91         last = treebase_node_getlastchild(parent);
  92         if (node == last) {
  93                 return NULL;
  94         }
  95         return (treebase_node_t*)node->sibling.next;
  96 }
  97
  98 EXPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node)
  99 {
 100         Bool empty;
 101         treebase_node_t *parent, *first;
 102         empty = isQueEmpty(&node->sibling);
 103         if (empty != False) {
 104                 return NULL;
 105         }
 106         parent = treebase_node_getparent(node);
 107         if (parent == NULL) {
 108                 return NULL;
 109         }
 110         first = treebase_node_getfirstchild(parent);
 111         if (node == first) {
 112                 return NULL;
 113         }
 114         return (treebase_node_t*)node->sibling.prev;
 115 }
 116
 117 EXPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node)
 118 {
 119         return node->firstchild;
 120 }
 121
 122 EXPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node)
 123 {
 124         if (node->firstchild == NULL) {
 125                 return NULL;
 126         }
 127         return (treebase_node_t*)node->firstchild->sibling.prev;
 128 }
 129
 130 EXPORT Bool treebase_node_haschild(treebase_node_t *node)
 131 {
 132         if (node->firstchild == NULL) {
 133                 return False;
 134         }
 135         return True;
 136 }
 137
 138 EXPORT VOID treebase_node_initialize(treebase_node_t *node)
 139 {
 140         QueInit(&node->sibling);
 141         node->firstchild = NULL;
 142         node->parent = NULL;
 143 }
 144
 145 EXPORT VOID treebase_node_finalize(treebase_node_t *node)
 146 {
 147         treebase_node_remove(node);
 148 }
 149
 150
 151 EXPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
 152 {
 153         treebase_node_t *child, *sibling;
 154
 155         if (traversal->current == NULL) {
 156                 return False;
 157         }
 158
 159         *node = traversal->current;
 160         *dir = traversal->dir;
 161
 162         if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
 163                 child = treebase_node_getfirstchild(traversal->current);
 164                 if (child == NULL) {
 165                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
 166                 } else {
 167                         traversal->current = child;
 168                 }
 169         } else {
 170                 sibling = treebase_node_getnextsibling(traversal->current);
 171                 if (sibling == NULL) {
 172                         if (traversal->current == traversal->root) {
 173                                 traversal->current = NULL;
 174                         } else {
 175                                 traversal->current = treebase_node_getparent(traversal->current);
 176                         }
 177                 } else {
 178                         traversal->current = sibling;
 179                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 180                 }
 181         }
 182
 183         return True;
 184 }
 185
 186 EXPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root)
 187 {
 188         traversal->root = root;
 189         traversal->current = root;
 190         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 191 }
 192
 193 EXPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal)
 194 {
 195 }
 196
 197
 198 EXPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
 199 {
 200         treebase_node_t *child, *sibling;
 201
 202         if (traversal->current == NULL) {
 203                 return False;
 204         }
 205
 206         *node = traversal->current;
 207         *dir = traversal->dir;
 208
 209         if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
 210                 child = treebase_node_getlastchild(traversal->current);
 211                 if (child == NULL) {
 212                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
 213                 } else {
 214                         traversal->current = child;
 215                 }
 216         } else {
 217                 sibling = treebase_node_getprevsibling(traversal->current);
 218                 if (sibling == NULL) {
 219                         if (traversal->current == traversal->root) {
 220                                 traversal->current = NULL;
 221                         } else {
 222                                 traversal->current = treebase_node_getparent(traversal->current);
 223                         }
 224                 } else {
 225                         traversal->current = sibling;
 226                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 227                 }
 228         }
 229
 230         return True;
 231 }
 232
 233 EXPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root)
 234 {
 235         traversal->root = root;
 236         traversal->current = root;
 237         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 238 }
 239
 240 EXPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal)
 241 {
 242 }