Return to rb2.c CVS log

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

Annotation of libaitio/example/rb2.c, revision 1.2

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