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

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: }