dummynet/test_radix.c

   1 /*
   2  * Test the radix tree net
   3  */
   4
   5 #include <sys/param.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <sys/time.h>
   9 #include <netinet/in.h> /* htonl */
  10 #include "include/net/radix.h"
  11
  12 struct d {
  13         uint8_t len[4];
  14         uint32_t data;
  15 };
  16
  17 struct table_entry {
  18         struct radix_node       rn[2];
  19         struct d x, mask;
  20         int               value;
  21 };
  22
  23 static int
  24 del(struct radix_node *rn, void *arg)
  25 {
  26         struct radix_node_head * const rnh = arg;
  27         struct table_entry *ent;
  28
  29         ent = (struct table_entry *)
  30             rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);
  31         fprintf(stderr, "del returns %p\n", ent);
  32         if (0 && ent != NULL)
  33                 free(ent);
  34         return (0);
  35 }
  36
  37 int
  38 list(struct radix_node *rn, void *arg)
  39 {
  40         struct table_entry *ent = (struct table_entry *)rn;
  41
  42         fprintf(stderr, "walking on node %d\n", ent->value);
  43         return (0);
  44 }
  45
  46 static void
  47 print_dt(struct timeval *start, struct timeval *end, int n, const char *msg)
  48 {
  49         int ds = 0, du, l;
  50         du = end->tv_usec - start->tv_usec;
  51         if (du < 0) {
  52                 ds = -1;
  53                 du += 1000000;
  54         }
  55         ds += end->tv_sec - start->tv_sec;
  56         if (n <= 1)
  57                 n = 1;
  58         l = (ds * 1000000+ du)/n;
  59         fprintf(stderr, "%d tries in %d.%06ds, %dus each\n",
  60                 n, ds, du, l);
  61 }
  62
  63 static void
  64 test1(struct radix_node_head *h, int n)
  65 {
  66         struct table_entry *p;
  67         struct timeval start, end;
  68         int i;
  69
  70         p = calloc(n, sizeof(*p));
  71         if (!p)
  72                 return;
  73         for (i=0; i < n; i++) {
  74                 p->value = i;
  75                 p->x.len[0] = p->mask.len[0] = 8;
  76                 p->mask.data = 0xffffffff;
  77                 p->x.data = htonl(i);
  78         }
  79         gettimeofday(&start, NULL);
  80         for (i=0; i < n; i++) {
  81                 h->rnh_addaddr(&(p->x), &(p->mask), h, (void *)p);
  82         }
  83         gettimeofday(&end, NULL);
  84         print_dt(&start, &end, n, NULL);
  85         h->rnh_walktree(h, del, h);
  86 }
  87
  88 int
  89 main(int argc, char *argv[])
  90 {
  91         struct radix_node_head *h = NULL;
  92
  93         rn_init(64); // XXX bits or bytes ?
  94         rn_inithead((void **)&h, 32); /* data offset in bits */
  95         test1(h, 1000000);
  96         return 0;
  97 }