![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dict.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Tom Morton FrontierVM] / frontvm / as68k|
Return to dict.c CVS log | Up to [Tom Morton FrontierVM] / frontvm / as68k |
1.1 root 1:
2: #include <stdio.h>
3: #include <string.h>
4: #include <stdlib.h>
5: #include <assert.h>
6: #include "dict.h"
7:
8: /*#define DEBUG*/
9:
10: #ifndef MIN
11: # define MIN(a,b) ((a)<(b) ? (a) : (b))
12: #endif
13: #ifndef MAX
14: # define MAX(a,b) ((a)>(b) ? (a) : (b))
15: #endif
16:
17: #define _NONE -1
18: #define LEFT 0
19: #define RIGHT 1
20: #define _ERR 2
21:
22: static int parent_side (const struct Node *node)
23: {
24: if (node->parent == NULL)
25: return _NONE;
26: else if (node->parent->child[LEFT] == node)
27: return LEFT;
28: else if (node->parent->child[RIGHT] == node)
29: return RIGHT;
30: else
31: return _ERR;
32: }
33:
34: static void print_tree (const struct Node *node, int depth)
35: {
36: int i;
37: //assert (depth < 10);
38: if (depth==0) printf ("Tree printout:\n");
39: if (!node) return;
40: for (i=0; i<depth; i++) {
41: printf ("\t");
42: }
43:
44: switch (parent_side (node)) {
45: case _NONE: printf ("+ "); break;
46: case LEFT: printf ("L "); break;
47: case RIGHT: printf ("R "); break;
48: default: printf ("? "); break;
49: }
50: printf ("\"%s\" bal %d: obj %x\n", node->key, node->balance, (int)node->obj);
51:
52: if (node->child[LEFT]) print_tree (node->child[LEFT], depth+1);
53: if (node->child[RIGHT]) print_tree (node->child[RIGHT], depth+1);
54: }
55:
56: static struct Node *alloc_node ()
57: {
58: struct Node *node = (struct Node *) malloc (sizeof (struct Node));
59: memset (node, 0, sizeof (struct Node));
60: return node;
61: }
62:
63: static void free_node (struct Node *node)
64: {
65: if (node->key) free (node->key);
66: free (node);
67: }
68:
69: static void set_node (struct Node *node, const char *key, void *obj)
70: {
71: node->key = (char *) malloc (strlen(key)+1);
72: strcpy (node->key, key);
73: node->obj = obj;
74: }
75:
76: /*
77: * This node is unbalanced :-o
78: * Returns new top node.
79: */
80: static struct Node *balance_node (struct Dict *tree, struct Node *high)
81: {
82: struct Node *mid = NULL;
83: struct Node *low = NULL;
84:
85: /* Single, rightwards */
86: if ((high->balance == +2) && (high->child[RIGHT]->balance >= 0)) {
87: mid = high->child[RIGHT];
88: low = mid->child[RIGHT];
89:
90: /* this one ends at top */
91: mid->parent = high->parent;
92: switch (parent_side (high)) {
93: case _NONE: tree->root = mid; break;
94: case LEFT: mid->parent->child[LEFT] = mid; break;
95: case RIGHT: mid->parent->child[RIGHT] = mid; break;
96: }
97:
98: high->child[RIGHT] = mid->child[LEFT];
99: if (mid->child[LEFT]) mid->child[LEFT]->parent = high;
100:
101: mid->child[LEFT] = high;
102: high->parent = mid;
103:
104: high->balance = high->balance - 1 - MAX (mid->balance, 0);
105: mid->balance = mid->balance - 1 + MIN (high->balance, 0);
106:
107: return mid;
108: }
109: /* Single, leftwards */
110: else if ((high->balance == -2) && (high->child[LEFT]->balance <= 0)) {
111: mid = high->child[LEFT];
112: low = mid->child[LEFT];
113:
114: /* this one ends at top */
115: mid->parent = high->parent;
116: switch (parent_side (high)) {
117: case _NONE: tree->root = mid; break;
118: case LEFT: mid->parent->child[LEFT] = mid; break;
119: case RIGHT: mid->parent->child[RIGHT] = mid; break;
120: }
121:
122: high->child[LEFT] = mid->child[RIGHT];
123: if (mid->child[RIGHT]) mid->child[RIGHT]->parent = high;
124:
125: mid->child[RIGHT] = high;
126: high->parent = mid;
127:
128: high->balance = high->balance + 1 - MIN (mid->balance, 0);
129: mid->balance = mid->balance + 1 + MAX (high->balance, 0);
130:
131: return mid;
132: }
133: /* Double, rightwards */
134: else if ((high->balance == +2) && (high->child[RIGHT]->balance == -1)) {
135: mid = high->child[RIGHT];
136: low = mid->child[LEFT];
137: /* this one ends at top */
138: low->parent = high->parent;
139: switch (parent_side (high)) {
140: case _NONE: tree->root = low; break;
141: case LEFT: low->parent->child[LEFT] = low; break;
142: case RIGHT: low->parent->child[RIGHT] = low; break;
143: }
144:
145: high->child[RIGHT] = low->child[LEFT];
146: if (low->child[LEFT]) low->child[LEFT]->parent = high;
147:
148: mid->child[LEFT] = low->child[RIGHT];
149: if (low->child[RIGHT]) low->child[RIGHT]->parent = mid;
150:
151: low->child[LEFT] = high;
152: high->parent = low;
153:
154: low->child[RIGHT] = mid;
155: mid->parent = low;
156:
157: high->balance = -MAX (low->balance, 0);
158: mid->balance = -MIN (low->balance, 0);
159: low->balance = 0;
160:
161: return low;
162: }
163: /* Double, leftwards */
164: else if ((high->balance == -2) && (high->child[LEFT]->balance == +1)) {
165: mid = high->child[LEFT];
166: low = mid->child[RIGHT];
167:
168: /* this one ends at top */
169: low->parent = high->parent;
170: switch (parent_side (high)) {
171: case _NONE: tree->root = low; break;
172: case LEFT: low->parent->child[LEFT] = low; break;
173: case RIGHT: low->parent->child[RIGHT] = low; break;
174: }
175:
176: high->child[LEFT] = low->child[RIGHT];
177: if (low->child[RIGHT]) low->child[RIGHT]->parent = high;
178:
179: mid->child[RIGHT] = low->child[LEFT];
180: if (low->child[LEFT]) low->child[LEFT]->parent = mid;
181:
182: low->child[RIGHT] = high;
183: high->parent = low;
184:
185: low->child[LEFT] = mid;
186: mid->parent = low;
187:
188: high->balance = -MIN (low->balance, 0);
189: mid->balance = -MAX (low->balance, 0);
190: low->balance = 0;
191:
192: return low;
193: } else {
194: assert ("This shouldn't happen in balance_node()");
195: return NULL;
196: }
197: }
198:
199: void dict_init (struct Dict *tree)
200: {
201: tree->root = NULL;
202: tree->len = 0;
203: }
204:
205: static void node_recurse_free (struct Node *node)
206: {
207: if (node->child[LEFT]) {
208: node_recurse_free (node->child[LEFT]);
209: }
210: if (node->child[RIGHT]) {
211: node_recurse_free (node->child[RIGHT]);
212: }
213: free_node (node);
214: }
215:
216: void dict_free (struct Dict *tree)
217: {
218: node_recurse_free (tree->root);
219: }
220:
221: void dict_remove (struct Dict *tree, const char *key)
222: {
223: int side;
224: struct Node *to_remove;
225: struct Node *iter;
226: struct Node *rem_pos;
227: int rem_dir;
228:
229: to_remove = dict_get (tree, key);
230:
231: if (to_remove == NULL) return;
232:
233: side = parent_side (to_remove);
234:
235: /* easy. no children */
236: if ((to_remove->child[LEFT] == NULL) && (to_remove->child[RIGHT] == NULL)) {
237: if (side == _NONE) {
238: tree->root = NULL;
239: } else {
240: to_remove->parent->child[side] = NULL;
241: }
242: rem_pos = to_remove->parent;
243: rem_dir = side;
244: } else if (to_remove->child[LEFT] == NULL) {
245: /* only righthand child. give it to parent */
246: if (side == _NONE) {
247: tree->root = to_remove->child[RIGHT];
248: } else {
249: to_remove->parent->child[side] = to_remove->child[RIGHT];
250: }
251: to_remove->child[RIGHT]->parent = to_remove->parent;
252:
253: rem_pos = to_remove->parent;
254: rem_dir = side;
255: } else if (to_remove->child[RIGHT] == NULL) {
256: /* only lefthand child. give it to parent... */
257: if (side == _NONE) {
258: tree->root = to_remove->child[LEFT];
259: } else {
260: to_remove->parent->child[side] = to_remove->child[LEFT];
261: }
262: to_remove->child[LEFT]->parent = to_remove->parent;
263:
264: rem_pos = to_remove->parent;
265: rem_dir = side;
266: } else {
267: /* 2 children.. more complex. we give the parent the
268: * rightmost child of the left child :-) */
269: iter = to_remove->child[LEFT];
270: while (iter->child[RIGHT]) {
271: iter = iter->child[RIGHT];
272: }
273:
274: /* maybe it has a left child. reparent it if so */
275: if (iter->child[LEFT]) {
276: iter->child[LEFT]->parent = iter->parent;
277: iter->parent->child[parent_side (iter)] = iter->child[LEFT];
278: iter->child[LEFT] = NULL;
279: } else {
280: iter->parent->child[parent_side (iter)] = NULL;
281: }
282: rem_pos = iter->parent;
283: rem_dir = RIGHT;
284: if (rem_pos == to_remove) {
285: rem_pos = iter;
286: rem_dir = LEFT;
287: }
288:
289: switch (parent_side (to_remove)) {
290: case _NONE:
291: tree->root = iter;
292: iter->parent = NULL;
293: break;
294: case LEFT:
295: iter->parent = to_remove->parent;
296: iter->parent->child[LEFT] = iter;
297: break;
298: case RIGHT:
299: iter->parent = to_remove->parent;
300: iter->parent->child[RIGHT] = iter;
301: break;
302: }
303:
304: if ((to_remove->child[LEFT] != NULL) &&
305: (to_remove->child[LEFT] != iter)) {
306: iter->child[LEFT] = to_remove->child[LEFT];
307: iter->child[LEFT]->parent = iter;
308: } else {
309: iter->child[LEFT] = NULL;
310: }
311: if ((to_remove->child[RIGHT] != NULL) &&
312: (to_remove->child[RIGHT] != iter)) {
313: iter->child[RIGHT] = to_remove->child[RIGHT];
314: iter->child[RIGHT]->parent = iter;
315: } else {
316: iter->child[RIGHT] = NULL;
317: }
318: iter->balance = to_remove->balance;
319: }
320: /* Iter should now be parent of [re]moved node.
321: * we need to recalculate balance */
322: iter = rem_pos;
323: assert (iter != to_remove);
324: /* AVL rotate if required */
325: /* Go back through parents seeing if some cunt is fucked */
326: while (iter) {
327: switch (rem_dir) {
328: case LEFT: side = -1; break;
329: case RIGHT: side = 1; break;
330: }
331: iter->balance -= side;
332:
333: /* unbalanced node */
334: if (abs (iter->balance) >= 2) {
335: iter = balance_node (tree, iter);
336: if (iter->balance != 0) return;
337: } else if (abs (iter->balance) == 1) {
338: break;
339: }
340: rem_dir = parent_side (iter);
341: iter = iter->parent;
342: }
343: free_node (to_remove);
344: }
345:
346: struct Node *dict_get (struct Dict *tree, const char *key)
347: {
348: int cmp;
349: struct Node *parent = NULL;
350: struct Node *node;
351:
352: if (tree->root == NULL) {
353: return NULL;
354: }
355:
356: node = tree->root;
357: while (1) {
358: /* Not found */
359: if ((parent) && (node == NULL))
360: return NULL;
361:
362: cmp = strcmp (node->key, key);
363:
364: if (cmp < 0) {
365: parent = node;
366: node = node->child[LEFT];
367: } else if (cmp > 0) {
368: parent = node;
369: node = node->child[RIGHT];
370: } else {
371: /* match */
372: return node;
373: }
374: }
375:
376:
377: }
378:
379: /*
380: * Returns 1 if key is new, otherwise zero.
381: */
382: int dict_set (struct Dict *tree, const char *key, void *obj)
383: {
384: int cmp = 0;
385: int side;
386: struct Node *parent = NULL;
387: struct Node *node;
388:
389: if (tree->root == NULL) {
390: tree->root = alloc_node ();
391: set_node (tree->root, key, obj);
392: tree->len++;
393: return 1;
394: }
395:
396: node = tree->root;
397: while (1) {
398: /* Found adding position */
399: if ((parent) && (node == NULL))
400: break;
401: cmp = strcmp (node->key, key);
402:
403: if (cmp < 0) {
404: parent = node;
405: node = node->child[LEFT];
406: } else if (cmp > 0) {
407: parent = node;
408: node = node->child[RIGHT];
409: } else {
410: /* match */
411: node->obj = obj;
412: return 0;
413: }
414: }
415:
416: /* add new */
417: node = alloc_node ();
418: set_node (node, key, obj);
419: tree->len++;
420: if (cmp < 0) {
421: parent->child[LEFT] = node;
422: } else {
423: parent->child[RIGHT] = node;
424: }
425: node->parent = parent;
426:
427: /* AVL rotate if required */
428: /* Go back through parents seeing if some cunt is fucked */
429: while (parent) {
430: if (parent->child[LEFT] == node) {
431: side = -1;
432: } else {
433: side = +1;
434: }
435:
436: parent->balance += side;
437:
438: /* unbalanced node */
439: if (abs (parent->balance) >= 2) {
440: parent = balance_node (tree, parent);
441: if (parent->balance == 0) return 1;
442: } else if (parent->balance == 0) {
443: break;
444: }
445: node = parent;
446: parent = node->parent;
447: }
448: /* nothing unbalanced */
449: return 1;
450: }
451:
452: #ifdef DEBUG
453: /*
454: * Asserts if the tree's balance is fucked in some way.
455: */
456: static int node_isbalanced (struct Node *node)
457: {
458: /* heights of trees */
459: int left = 0;
460: int right = 0;
461:
462: if (node->child[LEFT]) {
463: left += 1 + abs (node_isbalanced (node->child[LEFT]));
464: }
465: if (node->child[RIGHT]) {
466: right += 1 + abs (node_isbalanced (node->child[RIGHT]));
467: }
468:
469: //printf ("Node '%s' has height %d, balance %d (claims %d)\n", node->key, MAX (left, right), right-left, node->balance);
470:
471: assert ((right-left) == node->balance);
472: assert (abs (right-left) < 2);
473:
474: return MAX (left, right);
475: }
476:
477: #define TEST_SIZE 40
478:
479: int main (void)
480: {
481: int i;
482: int errs;
483: char buf[20];
484: char *keys[TEST_SIZE];
485: void *objs[TEST_SIZE];
486: struct Dict t;
487: struct Node *n;
488:
489: srand (4);
490: dict_init (&t);
491:
492: for (i=0; i<TEST_SIZE; i++) {
493: /* Make key */
494: sprintf(buf, "Node%d:%02d", rand(), i);
495: keys[i] = (char *) malloc (strlen(buf)+1);
496: strcpy (keys[i], buf);
497: /* Data */
498: objs[i] = (void *) rand();
499:
500: dict_set (&t, keys[i], objs[i]);
501: }
502:
503: print_tree (t.root, 0);
504: node_isbalanced (t.root);
505:
506: for (i=0, errs=0; i<TEST_SIZE; i++) {
507: /* Check if returned keys are correct */
508: n = dict_get (&t, keys[i]);
509: if ((n == NULL) || (n->obj != objs[i])) {
510: errs++;
511: }
512: }
513: printf ("%d incorrect gets.\n", errs);
514:
515: printf ("Removing half the keys...\n");
516: /* now remove half of them */
517: for (i=0; i<6*TEST_SIZE/8; i++) {
518: dict_remove (&t, keys[i]);
519: }
520: print_tree (t.root, 0);
521:
522: for (i=6*TEST_SIZE/8, errs=0; i<TEST_SIZE; i++) {
523: /* Check if returned keys are correct */
524: n = dict_get (&t, keys[i]);
525: if ((n == NULL) || (n->obj != objs[i])) {
526: errs++;
527: }
528: }
529: printf ("%d incorrect gets.\n", errs);
530: node_isbalanced (t.root);
531:
532: dict_free (&t);
533:
534: return 0;
535: }
536: #endif /* DEBUG */
537:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.