1 /*
2 Copyright (C) 2002 Kevin Shanahan
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 */
19
20 /*
21 * This whole setup is butt-ugly. Proceed with caution.
22 */
23
24 #include <assert.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29 #include "console.h"
30 #include "cvar.h"
31 #include "mathlib.h"
32 #include "rb_tree.h"
33 #include "shell.h"
34 #include "sys.h"
35 #include "zone.h"
36
37 /*
38 * When we want to build up temporary trees of strings for completions, file
39 * listings, etc. we can use the "temp" hunk since we don't want to keep them
40 * around. These allocator functions attempt to make more efficient use of the
41 * hunk space by keeping the tree nodes together in blocks and allocating
42 * strings right next to each other.
43 */
44 static struct stree_node *st_node_next;
45 static int st_node_space;
46 static char *st_string_next;
47 static int st_string_space;
48
49 #define ST_NODE_CHUNK 2048 /* 2kB / 16B => 128 nodes */
50 #define ST_STRING_CHUNK 4096 /* 4k of strings together */
51
52 void
STree_AllocInit(void)53 STree_AllocInit(void)
54 {
55 /* Init the temp hunk */
56 st_node_next = (struct stree_node*)Hunk_TempAlloc(ST_NODE_CHUNK);
57 st_node_space = ST_NODE_CHUNK;
58
59 /* Allocate string space on demand */
60 st_string_space = 0;
61 }
62
63 static struct stree_node *
STree_AllocNode(void)64 STree_AllocNode(void)
65 {
66 struct stree_node *ret = NULL;
67
68 if (st_node_space < sizeof(struct stree_node)) {
69 st_node_next = (struct stree_node*)Hunk_TempAllocExtend(ST_NODE_CHUNK);
70 st_node_space = st_node_next ? ST_NODE_CHUNK : 0;
71 }
72 if (st_node_space >= sizeof(struct stree_node)) {
73 ret = st_node_next++;
74 st_node_space -= sizeof(struct stree_node);
75 }
76
77 return ret;
78 }
79
80 static void *
STree_AllocString(unsigned int length)81 STree_AllocString(unsigned int length)
82 {
83 char *ret = NULL;
84
85 if (st_string_space < length) {
86 /*
87 * Note: might want to consider different allocation scheme here if we
88 * end up wasting a lot of space. E.g. if space wasted > 16, may as
89 * well use another chunk. This may cause excessive calls to
90 * Cache_FreeHigh, so maybe only do it if wasting more than that
91 * (32/64/?).
92 */
93 st_string_next = (char*)Hunk_TempAllocExtend(ST_STRING_CHUNK);
94 st_string_space = st_string_next ? ST_STRING_CHUNK : 0;
95 }
96 if (st_string_space >= length) {
97 ret = st_string_next;
98 st_string_next += length;
99 st_string_space -= length;
100 }
101
102 return ret;
103 }
104
105 /*
106 * Insert string node "node" into rb_tree rooted at "root"
107 */
108 qboolean
STree_Insert(struct stree_root * root,struct stree_node * node)109 STree_Insert(struct stree_root *root, struct stree_node *node)
110 {
111 struct rb_node **p = &root->root.rb_node;
112 struct rb_node *parent = NULL;
113 unsigned int len;
114 int cmp;
115
116 while (*p) {
117 parent = *p;
118 cmp = strcasecmp(node->string, stree_entry(parent)->string);
119 if (cmp < 0)
120 p = &(*p)->rb_left;
121 else if (cmp > 0)
122 p = &(*p)->rb_right;
123 else
124 return false; /* string already present */
125 }
126 root->entries++;
127 len = strlen(node->string);
128 if (len > root->maxlen)
129 root->maxlen = len;
130 if (len < root->minlen)
131 root->minlen = len;
132 rb_link_node(&node->node, parent, p);
133 rb_insert_color(&node->node, &root->root);
134
135 return true;
136 }
137
138 /*
139 * Insert string into rb tree, allocating the node dynamically.
140 * If alloc_str != 0, allocate and copy the string as well.
141 * NOTE: These allocations are only on the Temp hunk.
142 */
143 qboolean
STree_InsertAlloc(struct stree_root * root,const char * s,qboolean alloc_str)144 STree_InsertAlloc(struct stree_root *root, const char *s, qboolean alloc_str)
145 {
146 qboolean ret = false;
147 struct stree_node *n;
148 char *tmp;
149
150 n = STree_AllocNode();
151 if (n) {
152 if (alloc_str) {
153 tmp = (char*)STree_AllocString(strlen(s) + 1);
154 if (tmp) {
155 strcpy(tmp, s);
156 n->string = tmp;
157 }
158 } else {
159 n->string = s;
160 }
161 ret = STree_Insert(root, n);
162 }
163
164 return ret;
165 }
166
167 void
STree_Remove(struct stree_root * root,struct stree_node * node)168 STree_Remove(struct stree_root *root, struct stree_node *node)
169 {
170 rb_erase(&node->node, &root->root);
171 }
172
173 /* STree_MaxMatch helper */
174 static int
ST_node_match(struct rb_node * n,const char * str,int min_match,int max_match)175 ST_node_match(struct rb_node *n, const char *str, int min_match, int max_match)
176 {
177 if (n) {
178 max_match = ST_node_match(n->rb_left, str, min_match, max_match);
179
180 /* How much does this node match */
181 while (max_match > min_match) {
182 if (!strncasecmp(str, stree_entry(n)->string, max_match))
183 break;
184 max_match--;
185 }
186 max_match = ST_node_match(n->rb_right, str, min_match, max_match);
187 }
188
189 return max_match;
190 }
191
192 /*
193 * Given a prefix, return the maximum common prefix of all other strings in
194 * the tree which match the given prefix.
195 */
196 char *
STree_MaxMatch(struct stree_root * root,const char * pfx)197 STree_MaxMatch(struct stree_root *root, const char *pfx)
198 {
199 int max_match, min_match, match;
200 struct rb_node *n;
201 struct stree_node *sn;
202 char *result = NULL;
203
204 /* Can't be more than the shortest string */
205 max_match = root->minlen;
206 min_match = strlen(pfx);
207
208 n = root->root.rb_node;
209 sn = stree_entry(n);
210
211 if (root->entries == 1) {
212 match = strlen(sn->string);
213 result = (char*)Z_Malloc(match + 2);
214 if (result) {
215 strncpy(result, sn->string, match);
216 result[match] = ' ';
217 result[match + 1] = 0;
218 }
219 } else if (root->entries > 1) {
220 match = ST_node_match(n, sn->string, min_match, max_match);
221 result = (char*)Z_Malloc(match + 1);
222 if (result) {
223 strncpy(result, sn->string, match);
224 result[match] = 0;
225 }
226 }
227
228 return result;
229 }
230
231 struct stree_node *
STree_Find(struct stree_root * root,const char * s)232 STree_Find(struct stree_root *root, const char *s)
233 {
234 struct rb_node *p = root->root.rb_node;
235 struct stree_node *ret = NULL;
236 struct stree_node *node;
237 int cmp;
238
239 while (p) {
240 node = stree_entry(p);
241 cmp = strcasecmp(s, node->string);
242 if (cmp < 0)
243 p = p->rb_left;
244 else if (cmp > 0)
245 p = p->rb_right;
246 else {
247 ret = node;
248 break;
249 }
250 }
251
252 return ret;
253 }
254
255 /* An R-B Tree with n entries has a maximum height of 2log(n +1) */
256 static int
STree_MaxDepth(struct stree_root * root)257 STree_MaxDepth(struct stree_root *root)
258 {
259 return 2 * Q_log2(root->entries + 1);
260 }
261
262 static void
STree_StackInit(struct stree_root * root)263 STree_StackInit(struct stree_root *root)
264 {
265 root->stack = (struct stree_stack*)Z_Malloc(sizeof(struct stree_stack));
266 if (root->stack) {
267 struct stree_stack *s = root->stack;
268 s->depth = 0;
269 s->max_depth = STree_MaxDepth(root);
270 s->stack = (struct rb_node**)Z_Malloc(s->max_depth * sizeof(struct rb_node *));
271 if (!s->stack) {
272 Z_Free(s);
273 root->stack = NULL;
274 }
275 }
276 /* Possibly this harsh failure is not suitable in all cases? */
277 #ifndef _WIN32
278 if (!root->stack)
279 Sys_Error("%s: not enough mem for stack! (%i)", __func__,
280 STree_MaxDepth(root));
281 #endif
282 }
283
284 void
STree_ForEach_Init__(struct stree_root * root,struct stree_node ** n)285 STree_ForEach_Init__(struct stree_root *root, struct stree_node **n)
286 {
287 /* Allocate the stack */
288 STree_StackInit(root);
289
290 /* Point to the first node */
291 if (root->root.rb_node)
292 *n = stree_entry(root->root.rb_node);
293 else
294 *n = NULL;
295 }
296
297 void
STree_ForEach_Cleanup__(struct stree_root * root)298 STree_ForEach_Cleanup__(struct stree_root *root)
299 {
300 if (root->stack) {
301 Z_Free(root->stack->stack);
302 Z_Free(root->stack);
303 root->stack = NULL;
304 }
305 }
306
307 static void
STree_StackPush(struct stree_root * root,struct rb_node * n)308 STree_StackPush(struct stree_root *root, struct rb_node *n)
309 {
310 struct stree_stack *s = root->stack;
311 assert(s->depth < s->max_depth);
312 s->stack[s->depth++] = n;
313 }
314
315 static struct rb_node *
STree_StackPop(struct stree_root * root)316 STree_StackPop(struct stree_root *root)
317 {
318 struct stree_stack *s = root->stack;
319 assert(s->depth > 0);
320 return s->stack[--s->depth];
321 }
322
323 /*
324 * STree_WalkLeft - Helper for STree_ForEach
325 *
326 * Explanation of implied semantics:
327 * 1. If *n is not null, we haven't looked at it at all yet
328 * - Check the left child.
329 * - If child is non-null, push *n onto the stack, *n = (*n)->left; Goto 1.
330 * - If left child is null, keep this *n and exit (true)
331 * 2. If *n is null, we need to grab the node from the top of the stack
332 * - If the stack is empty, we're finished
333 * - Free the stack and exit (false)
334 * - Otherwise, *n = <pop the top of the stack> and exit (true)
335 */
336 qboolean
STree_WalkLeft__(struct stree_root * root,struct stree_node ** n)337 STree_WalkLeft__(struct stree_root *root, struct stree_node **n)
338 {
339 struct rb_node *rb;
340
341 if (*n) {
342 rb = &(*n)->node;
343 while (rb->rb_left) {
344 STree_StackPush(root, rb);
345 rb = rb->rb_left;
346 }
347 *n = stree_entry(rb);
348 } else {
349 /* Null signifies that we need to pop from the stack */
350 if (root->stack->depth > 0) {
351 rb = STree_StackPop(root);
352 *n = stree_entry(rb);
353 } else
354 STree_ForEach_Cleanup__(root);
355 }
356
357 return *n != NULL;
358 }
359
360 /*
361 * STree_WalkRight__ - Helper for STree_ForEach
362 *
363 * Called at the end of a loop iteration. So, *n has been processed.
364 * - If *n has a right child, *n = right child. Exit.
365 * - Otherwise, *n = NULL (tells WalkLeft to grab parent next). Exit.
366 */
367 void
STree_WalkRight__(struct stree_node ** n)368 STree_WalkRight__(struct stree_node **n)
369 {
370 struct rb_node *rb;
371
372 rb = &(*n)->node;
373 if (rb->rb_right)
374 *n = stree_entry(rb->rb_right);
375 else
376 *n = NULL;
377 }
378
379 /*
380 * Skip through the tree to a specified entry, without iterating
381 * through everything. This is basically STree_Find, but with stack
382 * pushes so the iteration can be continued. We then move n to the
383 * next node.
384 */
385 void
STree_ForEach_After__(struct stree_root * root,struct stree_node ** n,const char * s)386 STree_ForEach_After__(struct stree_root *root, struct stree_node **n,
387 const char *s)
388 {
389 struct rb_node *p;
390 struct stree_node *node;
391 int cmp;
392
393 *n = NULL;
394 p = root->root.rb_node;
395 while (p) {
396 node = stree_entry(p);
397 cmp = strcasecmp(s, node->string);
398 if (cmp < 0) {
399 STree_StackPush(root, p);
400 p = p->rb_left;
401 } else if (cmp > 0) {
402 p = p->rb_right;
403 } else {
404 *n = node;
405 break;
406 }
407 }
408
409 if (*n) {
410 /* found the exact node; skip on to the next one */
411 if (p->rb_right)
412 *n = stree_entry(p->rb_right);
413 else
414 *n = NULL;
415 } else {
416 /* Didn't find str. Don't walk the tree at all! */
417 root->stack->depth = 0;
418 }
419 }
420
421 void
STree_Completions(struct stree_root * out,struct stree_root * in,const char * s)422 STree_Completions(struct stree_root *out, struct stree_root *in, const char *s)
423 {
424 struct stree_node *n;
425 struct rb_node *rb = NULL;
426 int cmp, len;
427
428 len = strlen(s);
429 rb = in->root.rb_node;
430
431 /* Work our way down to the subtree required */
432 while (rb) {
433 n = stree_entry(rb);
434 cmp = strncasecmp(s, n->string, len);
435 if (cmp < 0)
436 rb = rb->rb_left;
437 if (cmp > 0)
438 rb = rb->rb_right;
439 else
440 break;
441 }
442
443 STree_StackInit(in);
444
445 while (rb) {
446 n = stree_entry(rb);
447 cmp = strncasecmp(s, n->string, len);
448 if (!cmp) {
449 STree_InsertAlloc(out, n->string, false);
450 if (rb->rb_left) {
451 if (rb->rb_right)
452 STree_StackPush(in, rb->rb_right);
453 rb = rb->rb_left;
454 } else {
455 rb = rb->rb_right;
456 }
457 } else if (cmp < 0) {
458 rb = rb->rb_left;
459 } else {
460 rb = rb->rb_right;
461 }
462 if (!rb && in->stack->depth > 0)
463 rb = STree_StackPop(in);
464 }
465
466 STree_ForEach_Cleanup__(in);
467 }
468