Initialize Tizen 2.3
[adaptation/xorg/driver/xserver-xorg-module-xdbg.git] / 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
52     tree->size = size;
53     tree->head = NULL;
54
55     return tree;
56 }
57
58 BINARY_TREE_NODE bintree_create_node (BINARY_TREE tree)
59 {
60     BINARY_TREE_NODE node = calloc (sizeof (struct _BINARY_TREE_NODE) + tree->size, 1);
61
62     node->left = NULL;
63     node->right = NULL;
64
65     return node;
66 }
67
68 BINARY_TREE_NODE bintree_get_head (BINARY_TREE tree)
69 {
70     return tree->head;
71 }
72
73 void bintree_set_head (BINARY_TREE tree, BINARY_TREE_NODE head)
74 {
75     tree->head = head;
76 }
77
78 void bintree_set_left_child (BINARY_TREE_NODE node, BINARY_TREE_NODE child)
79 {
80     node->left = child;
81 }
82
83 void bintree_set_right_child (BINARY_TREE_NODE node, BINARY_TREE_NODE child)
84 {
85     node->right = child;
86 }
87
88 BINARY_TREE_NODE bintree_get_left_child (BINARY_TREE_NODE node)
89 {
90     return node->left;
91 }
92
93 BINARY_TREE_NODE bintree_get_right_child (BINARY_TREE_NODE node)
94 {
95     return node->right;
96 }
97
98 void * bintree_get_node_data (BINARY_TREE_NODE node)
99 {
100     return (void*)(node + 1);
101 }
102
103 void bintree_remove_node (BINARY_TREE_NODE node)
104 {
105     free (node);
106 }
107
108 void bintree_remove_node_recursive (BINARY_TREE_NODE node)
109 {
110     if (node->left)
111         bintree_remove_node_recursive (node->left);
112     if (node->right)
113         bintree_remove_node_recursive (node->right);
114
115     bintree_remove_node (node);
116 }
117
118 void bintree_destroy_tree (BINARY_TREE tree)
119 {
120     if (tree->head)
121         bintree_remove_node_recursive (tree->head);
122
123     free (tree);
124 }
125
126 static int bintree_inorder_traverse_recursive (BINARY_TREE tree, BINARY_TREE_NODE node, BINARY_TREE_NODE parent, BINTREE_TRAVERSE_FUNC func, void * arg)
127 {
128     if (node->left)
129         if (bintree_inorder_traverse_recursive (tree, node->left, node, func, arg) != 0)
130             return 1;
131
132     if (func (tree, node, parent, arg))
133         return 1;
134
135     if (node->right)
136         if (bintree_inorder_traverse_recursive (tree, node->right, node, func, arg) != 0)
137             return 1;
138
139     return 0;
140 }
141
142 void bintree_inorder_traverse (BINARY_TREE tree, BINTREE_TRAVERSE_FUNC func, void * arg)
143 {
144     if (tree->head)
145         bintree_inorder_traverse_recursive (tree, tree->head, tree->head, func, arg);
146 }
147
148 static int bintree_postorder_traverse_recursive (BINARY_TREE tree, BINARY_TREE_NODE node, BINARY_TREE_NODE parent, BINTREE_TRAVERSE_FUNC func, void * arg)
149 {
150     if (node->left)
151         if (bintree_postorder_traverse_recursive (tree, node->left, node, func, arg) != 0)
152             return 1;
153     if (node->right)
154         if (bintree_postorder_traverse_recursive (tree, node->right, node, func, arg) != 0)
155             return 1;
156
157     return func (tree, node, parent, arg);
158 }
159
160 void bintree_postorder_traverse (BINARY_TREE tree, BINTREE_TRAVERSE_FUNC func, void * arg)
161 {
162     if (tree->head)
163         bintree_postorder_traverse_recursive (tree, tree->head, tree->head, func, arg);
164 }