common/ds/bintree.c

   1 /**************************************************************************
   2
   3 xserver-xorg-video-exynos
   4
   5 Copyright 2010 - 2011 Samsung Electronics co., Ltd. All Rights Reserved.
   6
   7 Contact: Boram Park <boram1288.park@samsung.com>
   8
   9 Permission is hereby granted, free of charge, to any person obtaining a
  10 copy of this software and associated documentation files (the
  11 "Software"), to deal in the Software without restriction, including
  12 without limitation the rights to use, copy, modify, merge, publish,
  13 distribute, sub license, and/or sell copies of the Software, and to
  14 permit persons to whom the Software is furnished to do so, subject to
  15 the following conditions:
  16
  17 The above copyright notice and this permission notice (including the
  18 next paragraph) shall be included in all copies or substantial portions
  19 of the Software.
  20
  21 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  22 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  24 IN NO EVENT SHALL PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR
  25 ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  26 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  27 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  28
  29 **************************************************************************/
  30
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33
  34 #include "bintree.h"
  35
  36 struct _BINARY_TREE_NODE
  37 {
  38     BINARY_TREE_NODE left;
  39     BINARY_TREE_NODE right;
  40 };
  41
  42 struct _BINARY_TREE
  43 {
  44     int size;
  45     BINARY_TREE_NODE head;
  46 };
  47
  48 BINARY_TREE bintree_create_tree (int size)
  49 {
  50     BINARY_TREE tree = calloc (sizeof (struct _BINARY_TREE) + size, 1);
  51     if (!tree) return NULL;
  52
  53     tree->size = size;
  54     tree->head = NULL;
  55
  56     return tree;
  57 }
  58
  59 BINARY_TREE_NODE bintree_create_node (BINARY_TREE tree)
  60 {
  61     BINARY_TREE_NODE node = calloc (sizeof (struct _BINARY_TREE_NODE) + tree->size, 1);
  62     if (!node) return NULL;
  63
  64     node->left = NULL;
  65     node->right = NULL;
  66
  67     return node;
  68 }
  69
  70 BINARY_TREE_NODE bintree_get_head (BINARY_TREE tree)
  71 {
  72     return tree->head;
  73 }
  74
  75 void bintree_set_head (BINARY_TREE tree, BINARY_TREE_NODE head)
  76 {
  77     tree->head = head;
  78 }
  79
  80 void bintree_set_left_child (BINARY_TREE_NODE node, BINARY_TREE_NODE child)
  81 {
  82     node->left = child;
  83 }
  84
  85 void bintree_set_right_child (BINARY_TREE_NODE node, BINARY_TREE_NODE child)
  86 {
  87     node->right = child;
  88 }
  89
  90 BINARY_TREE_NODE bintree_get_left_child (BINARY_TREE_NODE node)
  91 {
  92     return node->left;
  93 }
  94
  95 BINARY_TREE_NODE bintree_get_right_child (BINARY_TREE_NODE node)
  96 {
  97     return node->right;
  98 }
  99
 100 void * bintree_get_node_data (BINARY_TREE_NODE node)
 101 {
 102     return (void*)(node + 1);
 103 }
 104
 105 void bintree_remove_node (BINARY_TREE_NODE node)
 106 {
 107     free (node);
 108 }
 109
 110 void bintree_remove_node_recursive (BINARY_TREE_NODE node)
 111 {
 112     if (node->left)
 113         bintree_remove_node_recursive (node->left);
 114     if (node->right)
 115         bintree_remove_node_recursive (node->right);
 116
 117     bintree_remove_node (node);
 118 }
 119
 120 void bintree_destroy_tree (BINARY_TREE tree)
 121 {
 122     if (tree->head)
 123         bintree_remove_node_recursive (tree->head);
 124
 125     free (tree);
 126 }
 127
 128 static int bintree_inorder_traverse_recursive (BINARY_TREE tree, BINARY_TREE_NODE node, BINARY_TREE_NODE parent, BINTREE_TRAVERSE_FUNC func, void * arg)
 129 {
 130     if (node->left)
 131         if (bintree_inorder_traverse_recursive (tree, node->left, node, func, arg) != 0)
 132             return 1;
 133
 134     if (func (tree, node, parent, arg))
 135         return 1;
 136
 137     if (node->right)
 138         if (bintree_inorder_traverse_recursive (tree, node->right, node, func, arg) != 0)
 139             return 1;
 140
 141     return 0;
 142 }
 143
 144 void bintree_inorder_traverse (BINARY_TREE tree, BINTREE_TRAVERSE_FUNC func, void * arg)
 145 {
 146     if (tree->head)
 147         bintree_inorder_traverse_recursive (tree, tree->head, tree->head, func, arg);
 148 }
 149
 150 static int bintree_postorder_traverse_recursive (BINARY_TREE tree, BINARY_TREE_NODE node, BINARY_TREE_NODE parent, BINTREE_TRAVERSE_FUNC func, void * arg)
 151 {
 152     if (node->left)
 153         if (bintree_postorder_traverse_recursive (tree, node->left, node, func, arg) != 0)
 154             return 1;
 155     if (node->right)
 156         if (bintree_postorder_traverse_recursive (tree, node->right, node, func, arg) != 0)
 157             return 1;
 158
 159     return func (tree, node, parent, arg);
 160 }
 161
 162 void bintree_postorder_traverse (BINARY_TREE tree, BINTREE_TRAVERSE_FUNC func, void * arg)
 163 {
 164     if (tree->head)
 165         bintree_postorder_traverse_recursive (tree, tree->head, tree->head, func, arg);
 166 }