1 /* HexChat
2 * Copyright (C) 1998-2010 Peter Zelezny.
3 * Copyright (C) 2009-2013 Berke Viktor.
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
18 */
19
20 /*
21 This is used for quick userlist insertion and lookup. It's not really
22 a tree, but it could be :)
23 */
24
25 #include <stdio.h>
26 #include <string.h>
27 #include <stdlib.h>
28
29 #include "tree.h"
30
31 #define ARRAY_GROW 32
32
33 struct _tree
34 {
35 int elements;
36 int array_size;
37 void **array;
38 tree_cmp_func *cmp;
39 void *data;
40 };
41
42 tree *
tree_new(tree_cmp_func * cmp,void * data)43 tree_new (tree_cmp_func *cmp, void *data)
44 {
45 tree *t = g_new0 (tree, 1);
46 t->cmp = cmp;
47 t->data = data;
48 return t;
49 }
50
51 void
tree_destroy(tree * t)52 tree_destroy (tree *t)
53 {
54 if (t)
55 {
56 g_free (t->array);
57 g_free (t);
58 }
59 }
60
61 static int
tree_find_insertion_pos(tree * t,void * key,int * done)62 tree_find_insertion_pos (tree *t, void *key, int *done)
63 {
64 int c, u, l, idx;
65
66 if (t->elements < 1)
67 {
68 *done = 1;
69 t->array[0] = key;
70 t->elements++;
71 return 0;
72 }
73
74 if (t->elements < 2)
75 {
76 *done = 1;
77 c = t->cmp (key, t->array[0], t->data);
78 if (c == 0)
79 return -1;
80 t->elements++;
81 if (c > 0)
82 {
83 t->array[1] = key;
84 return 1;
85 }
86 t->array[1] = t->array[0];
87 t->array[0] = key;
88 return 0;
89 }
90
91 *done = 0;
92
93 c = t->cmp (key, t->array[0], t->data);
94 if (c < 0)
95 return 0; /* prepend */
96
97 c = t->cmp (key, t->array[t->elements - 1], t->data);
98 if (c > 0)
99 return t->elements; /* append */
100
101 l = 0;
102 u = t->elements - 1;
103 while (1)
104 {
105 idx = (l + u) / 2;
106 c = t->cmp (key, t->array[idx], t->data);
107
108 if (0 > c)
109 u = idx;
110 else if (0 < c && 0 > t->cmp (key, t->array[idx+1], t->data))
111 return idx + 1;
112 else if (c == 0)
113 return -1;
114 else
115 l = idx + 1;
116 }
117 }
118
119 static void
tree_insert_at_pos(tree * t,void * key,int pos)120 tree_insert_at_pos (tree *t, void *key, int pos)
121 {
122 int post_bytes;
123
124 /* append is easy */
125 if (pos != t->elements)
126 {
127 post_bytes = (t->elements - pos) * sizeof (void *);
128 memmove (&t->array[pos + 1], &t->array[pos], post_bytes);
129 }
130
131 t->array[pos] = key;
132 t->elements++;
133 }
134
135 static void *
mybsearch(const void * key,void ** array,size_t nmemb,int (* compar)(const void *,const void *,void * data),void * data,int * pos)136 mybsearch (const void *key, void **array, size_t nmemb,
137 int (*compar) (const void *, const void *, void *data), void *data, int *pos)
138 {
139 int l, u, idx;
140 int comparison;
141
142 l = 0;
143 u = nmemb;
144 while (l < u)
145 {
146 idx = (l + u) / 2;
147 comparison = (*compar) (key, array[idx], data);
148 if (comparison < 0)
149 u = idx;
150 else if (comparison > 0)
151 l = idx + 1;
152 else
153 {
154 *pos = idx;
155 return array[idx];
156 }
157 }
158
159 return NULL;
160 }
161
162 void *
tree_find(tree * t,const void * key,tree_cmp_func * cmp,void * data,int * pos)163 tree_find (tree *t, const void *key, tree_cmp_func *cmp, void *data, int *pos)
164 {
165 if (!t || !t->array)
166 return NULL;
167
168 return mybsearch (key, &t->array[0], t->elements, cmp, data, pos);
169 }
170
171 void *
tree_remove_at_pos(tree * t,int pos)172 tree_remove_at_pos (tree *t, int pos)
173 {
174 int post_bytes;
175 void *ret = t->array[pos];
176
177 t->elements--;
178 if (pos != t->elements)
179 {
180 post_bytes = (t->elements - pos) * sizeof (void *);
181 memmove (&t->array[pos], &t->array[pos + 1], post_bytes);
182 }
183 return ret;
184 }
185
186 int
tree_remove(tree * t,void * key,int * pos)187 tree_remove (tree *t, void *key, int *pos)
188 {
189 void *data;
190
191 data = tree_find (t, key, t->cmp, t->data, pos);
192 if (!data)
193 return 0;
194
195 tree_remove_at_pos (t, *pos);
196 return 1;
197 }
198
199 void
tree_foreach(tree * t,tree_traverse_func * func,void * data)200 tree_foreach (tree *t, tree_traverse_func *func, void *data)
201 {
202 int j;
203
204 if (!t || !t->array)
205 return;
206
207 for (j = 0; j < t->elements; j++)
208 {
209 if (!func (t->array[j], data))
210 break;
211 }
212 }
213
214 static void
tree_grow(tree * t)215 tree_grow (tree *t)
216 {
217 if (t->array_size < t->elements + 1)
218 {
219 int new_size = t->array_size + ARRAY_GROW;
220
221 t->array = realloc (t->array, sizeof (void *) * new_size);
222 t->array_size = new_size;
223 }
224
225 }
226
227 int
tree_insert(tree * t,void * key)228 tree_insert (tree *t, void *key)
229 {
230 int pos, done;
231
232 if (!t)
233 return -1;
234
235 tree_grow (t);
236 pos = tree_find_insertion_pos (t, key, &done);
237 if (!done && pos != -1)
238 tree_insert_at_pos (t, key, pos);
239
240 return pos;
241 }
242
243 void
tree_append(tree * t,void * key)244 tree_append (tree *t, void *key)
245 {
246 tree_grow (t);
247 tree_insert_at_pos (t, key, t->elements);
248 }
249
tree_size(tree * t)250 int tree_size (tree *t)
251 {
252 return t->elements;
253 }
254
255