File:
[ELWIX - Embedded LightWeight unIX -] /
libaitio /
example /
Attic /
rb.c
Revision
1.2:
download - view:
text,
annotated -
select for diffs -
revision graph
Tue Jun 7 11:49:39 2011 UTC (13 years, 2 months ago) by
misho
Branches:
MAIN
CVS tags:
io3_6,
io3_5,
io3_4,
io3_3,
io3_2,
io3_1,
io2_8,
io2_7,
io2_6,
io2_5,
io2_4,
io2_3,
io2_2,
io2_1,
io2_0,
IO3_5,
IO3_4,
IO3_3,
IO3_2,
IO3_1,
IO3_0,
IO2_7,
IO2_6,
IO2_5,
IO2_4,
IO2_3,
IO2_2,
IO2_1,
IO2_0,
IO1_9,
HEAD
ver 1.9
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <atree.h>
#include <sys/time.h>
struct blah {
int n;
RB_ENTRY(blah) node;
SPLAY_ENTRY(blah) node1;
AVL_ENTRY(blah) node2;
};
RB_HEAD(rb_head, blah) rbh;
SPLAY_HEAD(sp_head, blah) sph;
AVL_HEAD(avl_head, blah) avlh;
static int
rb_cmp(struct blah *a, struct blah *b)
{
int n = (a ? a->n : 0) - (b ? b->n : 0);
if (!n)
return 0;
else if (n < 0)
return -1;
else
return 1;
}
RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
RB_GENERATE(rb_head, blah, node, rb_cmp);
SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
AVL_GENERATE(avl_head, blah, node2, rb_cmp)
int
main()
{
struct blah *b, *b2;
register int i;
struct timeval before, after;
RB_INIT(&rbh);
SPLAY_INIT(&sph);
AVL_INIT(&avlh, 0);
srandom(getpid());
gettimeofday(&before, NULL);
for (i = 0; i < 1000000; i++) {
b = malloc(sizeof(struct blah));
memset(b, 0, sizeof(struct blah));
b->n = random();
if (RB_INSERT(rb_head, &rbh, b))
free(b);
}
gettimeofday(&after, NULL);
printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
gettimeofday(&before, NULL);
for (i = 0; i < 1000000; i++) {
b = malloc(sizeof(struct blah));
memset(b, 0, sizeof(struct blah));
b->n = random();
if (SPLAY_INSERT(sp_head, &sph, b))
free(b);
}
gettimeofday(&after, NULL);
printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
gettimeofday(&before, NULL);
for (i = 0; i < 1000000; i++) {
b = malloc(sizeof(struct blah));
memset(b, 0, sizeof(struct blah));
b->n = random();
if (AVL_INSERT(avl_head, &avlh, b))
free(b);
}
gettimeofday(&after, NULL);
printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
printf("---\n");
b2 = malloc(sizeof(struct blah));
gettimeofday(&before, NULL);
for (i = 0; i < 10000; i++) {
memset(b2, 0, sizeof(struct blah));
b2->n = random();
b = SPLAY_FIND(sp_head, &sph, b2);
if (b)
printf("SP::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
}
gettimeofday(&after, NULL);
printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
printf("---\n");
gettimeofday(&before, NULL);
for (i = 0; i < 10000; i++) {
memset(b2, 0, sizeof(struct blah));
b2->n = random();
b = RB_FIND(rb_head, &rbh, b2);
if (b)
printf("RB::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
}
gettimeofday(&after, NULL);
printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
free(b2);
printf("---\n");
b2 = malloc(sizeof(struct blah));
gettimeofday(&before, NULL);
for (i = 0; i < 10000; i++) {
memset(b2, 0, sizeof(struct blah));
b2->n = random();
b = AVL_FIND(avl_head, &avlh, b2);
if (b)
printf("AVL::Found key %d %d-> %d next=%d prev=%d\n", i, b2->n, b->n,
AVL_NEXT(avl_head, &avlh, b) ? AVL_NEXT(avl_head, &avlh, b)->n : 0,
AVL_PREV(avl_head, &avlh, b) ? AVL_PREV(avl_head, &avlh, b)->n : 0);
}
gettimeofday(&after, NULL);
printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
printf("---\n");
gettimeofday(&before, NULL);
AVL_FOREACH_SAFE(b, avl_head, &avlh, b2) {
/*
printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
*/
AVL_REMOVE(avl_head, &avlh, b);
free(b);
}
gettimeofday(&after, NULL);
printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
gettimeofday(&before, NULL);
for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
b2 = SPLAY_NEXT(sp_head, &sph, b);
SPLAY_REMOVE(sp_head, &sph, b);
}
gettimeofday(&after, NULL);
printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
gettimeofday(&before, NULL);
RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
RB_REMOVE(rb_head, &rbh, b);
free(b);
}
gettimeofday(&after, NULL);
printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
return !AVL_EMPTY(&avlh);
}
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>