1 /* Copyright (C) 2010-2017 The RetroArch team
2 *
3 * ---------------------------------------------------------------------------------------
4 * The following license statement only applies to this file (bintree.c).
5 * ---------------------------------------------------------------------------------------
6 *
7 * Permission is hereby granted, free of charge,
8 * to any person obtaining a copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation the rights to
10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
11 * and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
16 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
19 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <errno.h>
26
27 #include <retro_inline.h>
28
29 #include "bintree.h"
30
31 struct bintree_node
32 {
33 void *value;
34 struct bintree_node *parent;
35 struct bintree_node *left;
36 struct bintree_node *right;
37 };
38
39 struct bintree
40 {
41 struct bintree_node *root;
42 void *ctx;
43 bintree_cmp_func cmp;
44 };
45
46 static void * const NIL_NODE = (void*)&NIL_NODE;
47
bintree_new_nil_node(struct bintree_node * parent)48 static struct bintree_node *bintree_new_nil_node(
49 struct bintree_node *parent)
50 {
51 struct bintree_node *node = (struct bintree_node *)
52 malloc(sizeof(struct bintree_node));
53
54 if (!node)
55 return NULL;
56
57 node->value = NIL_NODE;
58 node->parent = parent;
59 node->left = NULL;
60 node->right = NULL;
61
62 return node;
63 }
64
bintree_insert_internal(bintree_t * t,struct bintree_node * root,void * value)65 static int bintree_insert_internal(bintree_t *t,
66 struct bintree_node *root, void *value)
67 {
68 int cmp_res = 0;
69
70 if (!root || (root->value == NIL_NODE))
71 {
72 root->left = bintree_new_nil_node(root);
73 root->right = bintree_new_nil_node(root);
74 root->value = value;
75
76 return 0;
77 }
78
79 cmp_res = t->cmp(root->value, value, t->ctx);
80
81 if (cmp_res > 0)
82 return bintree_insert_internal(t, root->left, value);
83 else if (cmp_res < 0)
84 return bintree_insert_internal(t, root->right, value);
85 return -EINVAL;
86 }
87
bintree_iterate_internal(struct bintree_node * n,bintree_iter_cb cb,void * ctx)88 static int bintree_iterate_internal(struct bintree_node *n,
89 bintree_iter_cb cb, void *ctx)
90 {
91 int rv;
92
93 if (!n || (n->value == NIL_NODE))
94 return 0;
95
96 if ((rv = bintree_iterate_internal(n->left, cb, ctx)) != 0)
97 return rv;
98 if ((rv = cb(n->value, ctx)) != 0)
99 return rv;
100 if ((rv = bintree_iterate_internal(n->right, cb, ctx)) != 0)
101 return rv;
102
103 return 0;
104 }
105
bintree_free_node(struct bintree_node * n)106 static void bintree_free_node(struct bintree_node *n)
107 {
108 if (!n)
109 return;
110
111 if (n->value == NIL_NODE)
112 {
113 free(n);
114 return;
115 }
116
117 n->value = NULL;
118 bintree_free_node(n->left);
119 bintree_free_node(n->right);
120 free(n);
121 }
122
bintree_insert(bintree_t * t,void * value)123 int bintree_insert(bintree_t *t, void *value)
124 {
125 return bintree_insert_internal(t, t->root, value);
126 }
127
bintree_iterate(const bintree_t * t,bintree_iter_cb cb,void * ctx)128 int bintree_iterate(const bintree_t *t, bintree_iter_cb cb,
129 void *ctx)
130 {
131 return bintree_iterate_internal(t->root, cb, ctx);
132 }
133
bintree_new(bintree_cmp_func cmp,void * ctx)134 bintree_t *bintree_new(bintree_cmp_func cmp, void *ctx)
135 {
136 bintree_t *t = (bintree_t*)malloc(sizeof(*t));
137
138 if (!t)
139 return NULL;
140
141 t->root = bintree_new_nil_node(NULL);
142 t->cmp = cmp;
143 t->ctx = ctx;
144
145 return t;
146 }
147
bintree_free(bintree_t * t)148 void bintree_free(bintree_t *t)
149 {
150 if (!t)
151 return;
152 bintree_free_node(t->root);
153 }
154