Return to dict.c CVS log

Up to [Tom Morton FrontierVM] / frontvm / as68k

Annotation of frontvm/as68k/dict.c, revision 1.1

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.