Annotation of libelwix/example/rb.c, revision 1.2

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:        TAILQ_ENTRY(blah) node4;
                     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: TAILQ_HEAD(, blah) tqh;
                     21: 
                     22: static int
                     23: rb_cmp(struct blah *a, struct blah *b)
                     24: {
                     25:        int n = (a ? a->n : 0) - (b ? b->n : 0);
                     26: 
                     27:        if (!n)
                     28:                return 0;
                     29:        else if (n < 0)
                     30:                return -1;
                     31:        else
                     32:                return 1;
                     33: }
                     34: 
                     35: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
                     36: RB_GENERATE(rb_head, blah, node, rb_cmp);
                     37: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
                     38: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
                     39: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
                     40: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
                     41: 
                     42: 
                     43: int
                     44: main()
                     45: {
                     46:        struct blah *b, *b2;
                     47:        register int i;
                     48:        struct timeval before, after;
                     49: 
                     50:        RB_INIT(&rbh);
                     51:        SPLAY_INIT(&sph);
                     52:        AVL_INIT(&avlh);
                     53:        SLIST_INIT(&slh);
                     54:        TAILQ_INIT(&tqh);
                     55:        srandom(getpid());
                     56: 
                     57:        gettimeofday(&before, NULL);
                     58:        for (i = 0; i < 1000000; i++) {
1.2     ! misho      59:                b = e_malloc(sizeof(struct blah));
1.1       misho      60:                memset(b, 0, sizeof(struct blah));
                     61:                b->n = random();
                     62:                if (RB_INSERT(rb_head, &rbh, b))
1.2     ! misho      63:                        e_free(b);
1.1       misho      64:        }
                     65:        gettimeofday(&after, NULL);
                     66:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                     67:        gettimeofday(&before, NULL);
                     68:        for (i = 0; i < 1000000; i++) {
1.2     ! misho      69:                b = e_malloc(sizeof(struct blah));
1.1       misho      70:                memset(b, 0, sizeof(struct blah));
                     71:                b->n = random();
                     72:                if (SPLAY_INSERT(sp_head, &sph, b))
1.2     ! misho      73:                        e_free(b);
1.1       misho      74:        }
                     75:        gettimeofday(&after, NULL);
                     76:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                     77: 
                     78:        gettimeofday(&before, NULL);
                     79:        for (i = 0; i < 1000000; i++) {
1.2     ! misho      80:                b = e_malloc(sizeof(struct blah));
1.1       misho      81:                memset(b, 0, sizeof(struct blah));
                     82:                b->n = random();
                     83:                if (AVL_INSERT(avl_head, &avlh, b))
1.2     ! misho      84:                        e_free(b);
1.1       misho      85:        }
                     86:        gettimeofday(&after, NULL);
                     87:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                     88: 
                     89:        gettimeofday(&before, NULL);
                     90:        for (i = 0; i < 1000000; i++) {
1.2     ! misho      91:                b = e_malloc(sizeof(struct blah));
1.1       misho      92:                memset(b, 0, sizeof(struct blah));
                     93:                b->n = random();
                     94:                SLIST_INSERT_HEAD(&slh, b, node3);
                     95:        }
                     96:        gettimeofday(&after, NULL);
                     97:        printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                     98:        gettimeofday(&before, NULL);
                     99:        for (i = 0; i < 1000000; i++) {
1.2     ! misho     100:                b = e_malloc(sizeof(struct blah));
1.1       misho     101:                memset(b, 0, sizeof(struct blah));
                    102:                b->n = random();
                    103:                TAILQ_INSERT_HEAD(&tqh, b, node4);
                    104:        }
                    105:        gettimeofday(&after, NULL);
                    106:        printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    107: 
                    108:        printf("---\n");
                    109: 
1.2     ! misho     110:        b2 = e_malloc(sizeof(struct blah));
1.1       misho     111:        gettimeofday(&before, NULL);
                    112:        for (i = 0; i < 10000; i++) {
                    113:                memset(b2, 0, sizeof(struct blah));
                    114:                b2->n = random();
                    115:                b = SPLAY_FIND(sp_head, &sph, b2);
                    116:                if (b)
                    117:                        printf("SP::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
                    118:        }
                    119:        gettimeofday(&after, NULL);
                    120:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    121: 
                    122:        printf("---\n");
                    123: 
                    124:        gettimeofday(&before, NULL);
                    125:        for (i = 0; i < 10000; i++) {
                    126:                memset(b2, 0, sizeof(struct blah));
                    127:                b2->n = random();
                    128:                b = RB_FIND(rb_head, &rbh, b2);
                    129:                if (b)
                    130:                        printf("RB::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
                    131:        }
                    132:        gettimeofday(&after, NULL);
                    133:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    134: 
                    135:        printf("---\n");
                    136: 
                    137:        gettimeofday(&before, NULL);
                    138:        for (i = 0; i < 10000; i++) {
                    139:                memset(b2, 0, sizeof(struct blah));
                    140:                b2->n = random();
                    141:                b = AVL_FIND(avl_head, &avlh, b2);
                    142:                if (b)
                    143:                        printf("AVL::Found key %d %d-> %d next=%d prev=%d\n", i, b2->n, b->n, 
                    144:                                        AVL_NEXT(avl_head, &avlh, b) ? AVL_NEXT(avl_head, &avlh, b)->n : 0,
                    145:                                        AVL_PREV(avl_head, &avlh, b) ? AVL_PREV(avl_head, &avlh, b)->n : 0);
                    146:        }
                    147:        gettimeofday(&after, NULL);
                    148:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    149: 
                    150:        printf("---\n");
                    151: 
1.2     ! misho     152:        e_free(b2);
1.1       misho     153: 
                    154:        gettimeofday(&before, NULL);
                    155:        while ((b = TAILQ_FIRST(&tqh))) {
                    156:                TAILQ_REMOVE(&tqh, b, node4);
1.2     ! misho     157:                e_free(b);
1.1       misho     158:        }
                    159:        gettimeofday(&after, NULL);
                    160:        printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    161:        gettimeofday(&before, NULL);
                    162:        while ((b = SLIST_FIRST(&slh))) {
                    163:                SLIST_REMOVE(&slh, b, blah, node3);
1.2     ! misho     164:                e_free(b);
1.1       misho     165:        }
                    166:        gettimeofday(&after, NULL);
                    167:        printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    168: 
                    169:        gettimeofday(&before, NULL);
                    170:        AVL_FOREACH_SAFE(b, avl_head, &avlh, b2) {
                    171:                printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
                    172:                printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
                    173:                printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
                    174:                AVL_REMOVE(avl_head, &avlh, b);
1.2     ! misho     175:                e_free(b);
1.1       misho     176:        }
                    177:        gettimeofday(&after, NULL);
                    178:        printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    179: 
                    180:        gettimeofday(&before, NULL);
                    181:        for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
                    182:                b2 = SPLAY_NEXT(sp_head, &sph, b);
                    183:                SPLAY_REMOVE(sp_head, &sph, b);
                    184:        }
                    185:        gettimeofday(&after, NULL);
                    186:        printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    187: 
                    188:        gettimeofday(&before, NULL);
                    189:        RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
1.2     ! misho     190:                printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
        !           191:                printf("b:%p %p /// ", b ? RB_LEFT(b, node) : b, b ? RB_RIGHT(b, node) : b);
        !           192:                printf("b2:%p %p\n", b2 ? RB_LEFT(b2, node) : b2, b2 ? RB_RIGHT(b2, node) : b2); fflush(stdout);
1.1       misho     193:                RB_REMOVE(rb_head, &rbh, b);
1.2     ! misho     194:                e_free(b);
1.1       misho     195:        }
                    196:        gettimeofday(&after, NULL);
                    197:        printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
                    198:        return !AVL_EMPTY(&avlh);
                    199: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>