Return to rb2.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / example

Annotation of libelwix/example/rb2.c, revision 1.1

1.1     ! misho       1: #include <stdio.h>
        !             2: #include <stdlib.h>
        !             3: #include <string.h>
        !             4: #include <unistd.h>
        !             5: #include <elwix.h>
        !             6: #include <sys/time.h>
        !             7: 
        !             8: struct blah {
        !             9:        int n;
        !            10:        RB_ENTRY(blah) node;
        !            11:        SPLAY_ENTRY(blah) node1;
        !            12:        AVL_ENTRY(blah) node2;
        !            13:        SLIST_ENTRY(blah) node3;
        !            14: };
        !            15: RB_HEAD(rb_head, blah) rbh;
        !            16: SPLAY_HEAD(sp_head, blah) sph;
        !            17: AVL_HEAD(avl_head, blah) avlh;
        !            18: SLIST_HEAD(, blah) slh;
        !            19: 
        !            20: static int
        !            21: rb_cmp(struct blah *a, struct blah *b)
        !            22: {
        !            23:        int n = (a ? a->n : 0) - (b ? b->n : 0);
        !            24: 
        !            25:        if (!n)
        !            26:                return 0;
        !            27:        else if (n < 0)
        !            28:                return -1;
        !            29:        else
        !            30:                return 1;
        !            31: }
        !            32: 
        !            33: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
        !            34: RB_GENERATE(rb_head, blah, node, rb_cmp);
        !            35: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
        !            36: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
        !            37: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
        !            38: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
        !            39: 
        !            40: 
        !            41: int
        !            42: main()
        !            43: {
        !            44:        struct blah *b, *b2;
        !            45:        register int i;
        !            46:        struct timeval before, after;
        !            47: 
        !            48:        RB_INIT(&rbh);
        !            49:        SPLAY_INIT(&sph);
        !            50:        AVL_INIT(&avlh);
        !            51:        SLIST_INIT(&slh);
        !            52:        srandom(getpid());
        !            53: 
        !            54:        for (i = 0; i < 100000; i++) {
        !            55:                b = malloc(sizeof(struct blah));
        !            56:                memset(b, 0, sizeof(struct blah));
        !            57:                b->n = random();
        !            58:                SLIST_INSERT_HEAD(&slh, b, node3);
        !            59:        }
        !            60: 
        !            61:        gettimeofday(&before, NULL);
        !            62:        SLIST_FOREACH(b, &slh, node3)
        !            63:                RB_INSERT(rb_head, &rbh, b);
        !            64:        gettimeofday(&after, NULL);
        !            65:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !            66: 
        !            67:        gettimeofday(&before, NULL);
        !            68:        SLIST_FOREACH(b, &slh, node3)
        !            69:                SPLAY_INSERT(sp_head, &sph, b);
        !            70:        gettimeofday(&after, NULL);
        !            71:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !            72: 
        !            73:        gettimeofday(&before, NULL);
        !            74:        SLIST_FOREACH(b, &slh, node3)
        !            75:                AVL_INSERT(avl_head, &avlh, b);
        !            76:        gettimeofday(&after, NULL);
        !            77:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !            78: 
        !            79:        printf("---\n");
        !            80: 
        !            81:        b2 = malloc(sizeof(struct blah));
        !            82: 
        !            83:        gettimeofday(&before, NULL);
        !            84:        for (i = 0; i < 20000; i++) {
        !            85:                memset(b2, 0, sizeof(struct blah));
        !            86:                b2->n = random();
        !            87:                b = SPLAY_FIND(sp_head, &sph, b2);
        !            88:                if (b)
        !            89:                        printf("SP::Found key %d -> %d\n", i, b->n);
        !            90:        }
        !            91:        gettimeofday(&after, NULL);
        !            92:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !            93: 
        !            94:        printf("---\n");
        !            95: 
        !            96:        gettimeofday(&before, NULL);
        !            97:        for (i = 0; i < 20000; i++) {
        !            98:                memset(b2, 0, sizeof(struct blah));
        !            99:                b2->n = random();
        !           100:                b = RB_FIND(rb_head, &rbh, b2);
        !           101:                if (b)
        !           102:                        printf("RB::Found key %d -> %d\n", i, b->n);
        !           103:        }
        !           104:        gettimeofday(&after, NULL);
        !           105:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           106: 
        !           107:        printf("---\n");
        !           108: 
        !           109:        gettimeofday(&before, NULL);
        !           110:        for (i = 0; i < 20000; i++) {
        !           111:                memset(b2, 0, sizeof(struct blah));
        !           112:                b2->n = random();
        !           113:                b = AVL_FIND(avl_head, &avlh, b2);
        !           114:                if (b)
        !           115:                        printf("AVL::Found key %d -> %d\n", i, b->n);
        !           116:        }
        !           117:        gettimeofday(&after, NULL);
        !           118:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           119: 
        !           120:        printf("---\n");
        !           121: 
        !           122:        free(b2);
        !           123: 
        !           124:        gettimeofday(&before, NULL);
        !           125:        AVL_FOREACH_SAFE(b, avl_head, &avlh, b2)
        !           126:                AVL_REMOVE(avl_head, &avlh, b);
        !           127:        gettimeofday(&after, NULL);
        !           128:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           129: 
        !           130:        gettimeofday(&before, NULL);
        !           131:        SPLAY_FOREACH_SAFE(b, sp_head, &sph, b2)
        !           132:                SPLAY_REMOVE(sp_head, &sph, b);
        !           133:        gettimeofday(&after, NULL);
        !           134:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           135: 
        !           136:        gettimeofday(&before, NULL);
        !           137:        RB_FOREACH_SAFE(b, rb_head, &rbh, b2)
        !           138:                RB_REMOVE(rb_head, &rbh, b);
        !           139:        gettimeofday(&after, NULL);
        !           140:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           141: 
        !           142:        gettimeofday(&before, NULL);
        !           143:        while ((b = SLIST_FIRST(&slh))) {
        !           144:                SLIST_REMOVE(&slh, b, blah, node3);
        !           145:                free(b);
        !           146:        }
        !           147:        gettimeofday(&after, NULL);
        !           148:        printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
        !           149:        return !AVL_EMPTY(&avlh);
        !           150: }