File:
[ELWIX - Embedded LightWeight unIX -] /
libelwix /
example /
rb2.c
Revision
1.1.1.1 (vendor branch):
download - view:
text,
annotated -
select for diffs -
revision graph
Thu Jan 17 10:05:35 2013 UTC (11 years, 7 months ago) by
misho
Branches:
misho,
MAIN
CVS tags:
elwix6_1,
elwix5_9,
elwix5_8,
elwix5_7,
elwix5_6,
elwix5_5,
elwix5_4,
elwix5_3,
elwix5_2,
elwix5_12,
elwix5_11,
elwix5_10,
elwix5_1,
elwix5_0,
elwix4_9,
elwix4_8,
elwix4_7,
elwix4_6,
elwix4_5,
elwix4_4,
elwix4_3,
elwix4_26,
elwix4_25,
elwix4_24,
elwix4_23,
elwix4_22,
elwix4_21,
elwix4_20,
elwix4_2,
elwix4_19,
elwix4_18,
elwix4_17,
elwix4_16,
elwix4_15,
elwix4_14,
elwix4_13,
elwix4_12,
elwix4_11,
elwix4_10,
elwix4_1,
elwix3_9,
elwix3_8,
elwix3_7,
elwix3_6,
elwix3_5,
elwix3_4,
elwix3_3,
elwix3_2,
elwix3_1,
elwix3_0,
elwix2_9,
elwix2_8,
elwix2_7,
elwix2_6,
elwix2_5,
elwix2_4,
elwix2_3,
elwix2_2,
elwix2_1,
elwix2_0,
elwix1_9,
elwix1_8,
elwix1_7,
elwix1_6,
elwix1_5,
elwix1_4,
elwix1_3,
elwix1_2,
elwix1_1,
HEAD,
ELWIX6_0,
ELWIX5_9,
ELWIX5_8,
ELWIX5_7,
ELWIX5_6,
ELWIX5_5,
ELWIX5_4,
ELWIX5_3,
ELWIX5_2,
ELWIX5_11,
ELWIX5_10,
ELWIX5_1,
ELWIX5_0,
ELWIX4_9,
ELWIX4_8,
ELWIX4_7,
ELWIX4_6,
ELWIX4_5,
ELWIX4_4,
ELWIX4_3,
ELWIX4_26,
ELWIX4_25,
ELWIX4_24,
ELWIX4_23,
ELWIX4_22,
ELWIX4_21,
ELWIX4_20,
ELWIX4_2,
ELWIX4_19,
ELWIX4_18,
ELWIX4_17,
ELWIX4_16,
ELWIX4_15,
ELWIX4_14,
ELWIX4_13,
ELWIX4_12,
ELWIX4_11,
ELWIX4_10,
ELWIX4_1,
ELWIX4_0,
ELWIX3_8,
ELWIX3_7,
ELWIX3_6,
ELWIX3_5,
ELWIX3_4,
ELWIX3_3,
ELWIX3_2,
ELWIX3_1,
ELWIX3_0,
ELWIX2_9,
ELWIX2_8,
ELWIX2_7,
ELWIX2_6,
ELWIX2_5,
ELWIX2_4,
ELWIX2_3,
ELWIX2_2,
ELWIX2_1,
ELWIX2_0,
ELWIX1_9,
ELWIX1_8,
ELWIX1_7,
ELWIX1_6,
ELWIX1_5,
ELWIX1_4,
ELWIX1_3,
ELWIX1_2,
ELWIX1_1,
ELWIX1_0
ELWIX core library
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <elwix.h>
#include <sys/time.h>
struct blah {
int n;
RB_ENTRY(blah) node;
SPLAY_ENTRY(blah) node1;
AVL_ENTRY(blah) node2;
SLIST_ENTRY(blah) node3;
};
RB_HEAD(rb_head, blah) rbh;
SPLAY_HEAD(sp_head, blah) sph;
AVL_HEAD(avl_head, blah) avlh;
SLIST_HEAD(, blah) slh;
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);
SLIST_INIT(&slh);
srandom(getpid());
for (i = 0; i < 100000; i++) {
b = malloc(sizeof(struct blah));
memset(b, 0, sizeof(struct blah));
b->n = random();
SLIST_INSERT_HEAD(&slh, b, node3);
}
gettimeofday(&before, NULL);
SLIST_FOREACH(b, &slh, node3)
RB_INSERT(rb_head, &rbh, 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);
SLIST_FOREACH(b, &slh, node3)
SPLAY_INSERT(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);
SLIST_FOREACH(b, &slh, node3)
AVL_INSERT(avl_head, &avlh, 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 < 20000; i++) {
memset(b2, 0, sizeof(struct blah));
b2->n = random();
b = SPLAY_FIND(sp_head, &sph, b2);
if (b)
printf("SP::Found key %d -> %d\n", i, 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 < 20000; i++) {
memset(b2, 0, sizeof(struct blah));
b2->n = random();
b = RB_FIND(rb_head, &rbh, b2);
if (b)
printf("RB::Found key %d -> %d\n", i, b->n);
}
gettimeofday(&after, NULL);
printf("RB::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 < 20000; 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\n", i, b->n);
}
gettimeofday(&after, NULL);
printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
printf("---\n");
free(b2);
gettimeofday(&before, NULL);
AVL_FOREACH_SAFE(b, avl_head, &avlh, b2)
AVL_REMOVE(avl_head, &avlh, 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);
SPLAY_FOREACH_SAFE(b, sp_head, &sph, b2)
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);
gettimeofday(&after, NULL);
printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
gettimeofday(&before, NULL);
while ((b = SLIST_FIRST(&slh))) {
SLIST_REMOVE(&slh, b, blah, node3);
free(b);
}
gettimeofday(&after, NULL);
printf("SLIST::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>