urlmap.c

Sofia SIP is an open-source SIP User-Agent library, compliant with the IETF RFC3261 specification.

  END();
}

int test_insert(void)
{
  su_home_t *home;
  UrlMap *tree = NULL, *o, *old;
  UrlMap *one, *three, *five, *six, *seven;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);
  one = url_map_new(home, (void*)"/1", sizeof (UrlMap));
  three = url_map_new(home, (void*)"/3", sizeof (UrlMap));
  five = url_map_new(home, (void*)"/5", sizeof (UrlMap));
  six = url_map_new(home, (void*)"/6", sizeof (UrlMap));
  seven = url_map_new(home, (void*)"/7", sizeof (UrlMap));

  TEST_1(one); 
  TEST_1(three);
  TEST_1(five);
  TEST_1(six);
  TEST_1(seven);

  /* Check single node */
  TEST(url_map_insert(&tree, five, &o), 0); TEST_P(o, NULL);
  TEST_P(tree, five);
  TEST_P(five->um_left, NULL); TEST_P(five->um_right, NULL);
  TEST_P(five->um_dad, NULL); TEST(five->um_black, 1);

  /* Check after another node: 
   *
   *         5b
   *        / 
   *       3r
   */
  TEST(url_map_insert(&tree, three, &o), 0); TEST_P(o, NULL);
  TEST_P(tree->um_left, three); TEST(tree->um_black, 1);
  TEST_P(three->um_left, NULL); TEST_P(three->um_right, NULL);
  TEST_P(three->um_dad, tree); TEST(three->um_black, 0); 

  /* Check third node
   *         5b
   *        / \
   *       3r  7r
   */
  TEST(url_map_insert(&tree, seven, &o), 0); TEST_P(o, NULL);
  TEST_P(tree->um_right, seven); TEST(tree->um_black, 1);
  TEST_P(seven->um_left, NULL); TEST_P(seven->um_right, NULL);
  TEST_P(seven->um_dad, tree); TEST(seven->um_black, 0); 

  /* Check after fourth node:
   *         5b
   *        / \
   *       3b  7b
   *      /
   *     1r  
   */
  TEST(url_map_insert(&tree, one, &o), 0); TEST_P(o, NULL);
  TEST_P(tree->um_left->um_left, one); 
  TEST(tree->um_black, 1); 
  TEST(tree->um_left->um_black, 1); TEST(tree->um_right->um_black, 1);
  TEST_P(one->um_left, NULL); TEST_P(one->um_right, NULL);
  TEST_P(one->um_dad, tree->um_left); TEST(one->um_black, 0); 

  /* Checks that we got after fifth node:
   *         5b
   *        / \
   *       3b  7b
   *      /   /
   *     1r  6r
   */
  TEST(url_map_insert(&tree, six, &o), 0); TEST_P(o, NULL);
  TEST_P(tree, five); TEST(five->um_black, 1);
  TEST_P(tree->um_left, three); TEST(three->um_black, 1);
  TEST_P(tree->um_left->um_left, one); TEST(one->um_black, 0);
  TEST_P(tree->um_right, seven); TEST(seven->um_black, 1);
  TEST_P(tree->um_right->um_left, six); TEST(six->um_black, 0);

  /* Insert five second time */
  old = five;
  five = url_map_new(home, (void*)"/5", sizeof (UrlMap));
  TEST(url_map_insert(&tree, five, &o), 0); TEST_P(o, old);
  TEST_P(tree, five); TEST(five->um_black, 1);
  TEST_P(tree->um_left, three); TEST(three->um_black, 1);
  TEST_P(three->um_dad, five);
  TEST_P(tree->um_left->um_left, one); TEST(one->um_black, 0);
  TEST_P(tree->um_right, seven); TEST(seven->um_black, 1);
  TEST_P(seven->um_dad, five);
  TEST_P(tree->um_right->um_left, six); TEST(six->um_black, 0);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_rotate(void)
{
  su_home_t *home;
  UrlMap *tree = NULL;
  UrlMap *x, *y, *o;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);

  x = url_map_new(home, (void*)"/x", sizeof *x);
  y = url_map_new(home, (void*)"/y", sizeof *y);

  TEST_1(x);
  TEST_1(y); 

  /*
   *              x                   y               x
   * Checks that   \  transforms to  /   and back to   \
   *                y               x                   y
   */
  TEST(url_map_insert(&tree, x, &o), 0); TEST_P(o, NULL);
  TEST(url_map_insert(&tree, y, &o), 0); TEST_P(o, NULL);

  TEST_P(tree, x); TEST_P(x->um_right, y);
  left_rotate(&tree, x);
  TEST_P(tree, y); TEST_P(y->um_left, x);
  right_rotate(&tree, y);
  TEST_P(tree, x); TEST_P(x->um_right, y);

  su_home_check(home);
  su_home_zap(home);

  END();
}

/** ceil of log2 */
static
unsigned log2ceil(unsigned k)
{
  unsigned result = 0;

#if 0
  if (k > (1 << 32))
    result += 32, k = (k >> 32) + ((k & ((1 << 32) - 1)) != 0);
#endif
  if (k > (1 << 16)) 
    result += 16, k = (k >> 16) + ((k & ((1 << 16) - 1)) != 0);
  if (k > (1 << 8)) 
    result += 8, k = (k >> 8) + ((k & ((1 << 8) - 1)) != 0);
  if (k > (1 << 4))
    result += 4, k = (k >> 4) + ((k & 15) != 0);
  if (k > (1 << 2))
    result += 2, k = (k >> 2) + ((k & 3) != 0);
  if (k > (1 << 1))
    result += 1, k = (k >> 1) + (k & 1);
  if (k > 1)
    result += 1;
  
  return result;
}

typedef struct {
  UrlMap te_urlmap[1];
  int      te_value;
  int      te_inserted;
} TEntry;

int test_balance(void)
{
  su_home_t *home;
  UrlMap *tree = NULL, *o = NULL;
  url_t *u;
  TEntry *te, **nodes;
  char path[16];
  int i, j;
  int const N = 1000;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);
  nodes = su_zalloc(home, (N + 2) * (sizeof *nodes)); TEST_1(nodes);
  nodes++;

  u = url_hdup(home, (url_t *)"http://host");
  u->url_path = path;

  for (i = 0; i < N; i++) {
    snprintf(path, (sizeof path), "p%07u", i);
    te = (TEntry *)url_map_new(home, (void *)u, sizeof *te);
    te->te_value = i;
    nodes[i] = te;
    TEST(url_map_insert(&tree, te->te_urlmap, &o), 0);
    TEST_P(o, NULL);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    snprintf(path, (sizeof path), "p%07u", i);
    te = (TEntry *)url_map_find(tree, (void*)u, 1);
    TEST_1(te); TEST(te->te_value, i);
  }

  snprintf(path, (sizeof path), "p%07u", 0);

  te = (TEntry *)url_map_find(tree, (void*)u, 1);

  for (i = 0; i < N; i++) {
    TEST_1(te); TEST(te->te_value, i);
    te = (TEntry *)url_map_succ(te->te_urlmap);
  }
  TEST_1(te == NULL);

  for (i = 0; i < N; i++) {
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    snprintf(path, (sizeof path), "p%07u", i);
    te = (TEntry *)url_map_find(tree, (void*)u, 1);
    TEST_1(te); TEST(te->te_value, i);
    url_map_remove(&tree, te->te_urlmap);
    TEST_1(te->te_urlmap->um_dad == NULL && 
	   te->te_urlmap->um_left == NULL && 
	   te->te_urlmap->um_right == NULL); 
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  for (i = N - 1; i >= 0; i--) {
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[i]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    url_map_remove(&tree, nodes[i]->te_urlmap);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 57) % N;
    o = (void *)-1;
    TEST(nodes[sn]->te_inserted, 0);
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    nodes[sn]->te_inserted = 1;
    TEST_P(o, NULL);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 23) % N;	/* 23 is relative prime to N */
    TEST(nodes[sn]->te_inserted, 1);
    url_map_remove(&tree, nodes[sn]->te_urlmap);
    nodes[sn]->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 517) % N;	/* relative prime to N */
    o = (void *)-1;
    TEST(nodes[sn]->te_inserted, 0);
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    nodes[sn]->te_inserted = 1;
    TEST_P(o, NULL);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 497) % N;	/* relative prime to N */
    TEST(nodes[sn]->te_inserted, 1);
    url_map_remove(&tree, nodes[sn]->te_urlmap);
    nodes[sn]->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  for (i = 0; i < N; i++) {
    int sn = (i * 1957) % N;	/* relative prime to N */
    o = (void *)-1;
    TEST(nodes[sn]->te_inserted, 0);
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    nodes[sn]->te_inserted = 1;
    TEST_P(o, NULL);
    TEST_1(url_map_height(tree) <= 2 * log2ceil(i + 1 + 1));
    TEST_1(redblack_check(tree));
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    int sn = (i * 1519) % N;	/* relative prime to N */
    TEST(nodes[sn]->te_inserted, 1);
    url_map_remove(&tree, nodes[sn]->te_urlmap);
    nodes[sn]->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N - i - 1;
    TEST(nodes[i]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[i]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[i]->te_inserted = 1;

    TEST(nodes[sn]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[sn]->te_inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  for (i = 0; i < N; i++) {
    te = (TEntry *)((i & 1) ? url_map_succ(tree) : url_map_prec(tree));
    if (te == NULL)
      te = (TEntry *)tree;
    TEST(te->te_inserted, 1);
    url_map_remove(&tree, te->te_urlmap);
    te->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N - i - 1;
    TEST(nodes[i]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[i]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[i]->te_inserted = 1;

    TEST(nodes[sn]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[sn]->te_inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  /* Remove last, first, last, first, ... */
  for (i = 0; i < N; i++) {
    te = (TEntry *)((i & 1) ? url_map_first(tree) : url_map_last(tree));
    TEST_1(te);
    TEST(te->te_inserted, 1);
    url_map_remove(&tree, te->te_urlmap);
    te->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  /* Insert small, big, small, big ... */

  for (i = 0; i < N / 2; i++) {
    int sn = N / 2 + i;
    TEST(nodes[i]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[i]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[i]->te_inserted = 1;

    TEST(nodes[sn]->te_inserted, 0);
    o = (void *)-1;
    TEST(url_map_insert(&tree, nodes[sn]->te_urlmap, &o), 0); 
    TEST_P(o, NULL);
    nodes[sn]->te_inserted = 1;
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  /* Remove last, first, last, first, ... */
  for (i = 0; i < N; i++) {
    te = (TEntry *)((i & 1) ? url_map_first(tree) : url_map_last(tree));
    TEST_1(te);
    TEST(te->te_inserted, 1);
    url_map_remove(&tree, te->te_urlmap);
    te->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  /* Insert in perfect order ... */
  
  for (j = N / 2; j > 0; j /= 2) {
    for (i = N - j; i >= 0; i -= j) {
      if (nodes[i]->te_inserted)
	continue;
      o = (void *)-1;
      TEST(url_map_insert(&tree, nodes[i]->te_urlmap, &o), 0); 
      TEST_P(o, NULL);
      nodes[i]->te_inserted = 1;
    }
  }

  for (i = 0; i < N; i++) {
    TEST(nodes[i]->te_inserted, 1);
    TEST_P(url_map_succ(nodes[i]->te_urlmap), nodes[i + 1]->te_urlmap);
    TEST_P(url_map_prec(nodes[i]->te_urlmap), nodes[i - 1]->te_urlmap);
  }

  /* Remove such nodes that insert red uncles into tree */
  for (i = 0; i < N; i++) {
    te = (TEntry *)url_map_last(tree);
    for (o = te->te_urlmap; o; o = url_map_prec(o)) {
      UrlMap *dad, *granddad, *uncle, *to_be_removed;
      /* We must have a node with black dad, no brother, red granddad and uncle */
      if (!(dad = o->um_dad) || !dad->um_black)
	continue;
      if (dad->um_left && dad->um_right)
	continue;
      if (!(granddad = dad->um_dad) || granddad->um_black)
	continue;
      if (granddad->um_left == dad)
	uncle = granddad->um_right;
      else
	uncle = granddad->um_left;
      if (!uncle || uncle->um_black)
	continue;
      to_be_removed = url_map_prec(o->um_dad);
      if (to_be_removed == granddad || to_be_removed == uncle)
	continue;
      if (!to_be_removed->um_left || !to_be_removed->um_right)
	continue;
      te = (TEntry *)to_be_removed;
      break;
    }
    TEST(te->te_inserted, 1);
    url_map_remove(&tree, te->te_urlmap);
    te->te_inserted = 0;
    TEST_1(url_map_height(tree) <= 2 * log2ceil(N - i + 1));
    TEST_1(redblack_check(tree));
  }

  TEST_P(tree, NULL);

  su_home_check(home);
  su_home_zap(home);

  END();
}

int test_speed(void)
{
  su_home_t *home;
  UrlMap *tree = NULL, *o = NULL;
  url_t *u;
  TEntry *te;
  unsigned i;
  char path[16];
  int const N = 1000000;

  BEGIN();

  home = su_home_clone(NULL, sizeof(*home)); TEST_1(home);

  u = url_hdup(home, (url_t *)"http://host");
  u->url_path = path;

  for (i = 0; i < N; i++) {
    snprintf(path, (sizeof path), "p%07u", i);
    te = (TEntry *)url_map_new(home, (void *)u, sizeof *te);
    te->te_value = i;
    TEST(url_map_insert(&tree, te->te_urlmap, &o), 0);
    TEST_P(o, NULL);
  }

  TEST_1(url_map_height(tree) <= 2 * log2ceil(i + 1));

  for (i = 0; i < N; i++) {
    snprintf(path, (sizeof path), "p%07u", i);
    te = (TEntry *)url_map_find(tree, (void*)u, 1);
    TEST_1(te); TEST(te->te_value, i);
  }

  snprintf(path, (sizeof path), "p%07u", 0);

  te = (TEntry *)url_map_find(tree, (void*)u, 1);

  for (i = 0; i < N; i++) {
    TEST_1(te); TEST(te->te_value, i);
    te = (TEntry *)url_map_succ(te->te_urlmap);
  }
  TEST_1(te == NULL);

  su_home_check(home);
  su_home_zap(home);

  END();
}



void usage(void)
{
  fprintf(stderr,
	  "usage: %s [-v]\n",
	  name);
}

int main(int argc, char *argv[])
{
  int retval = 0;
  int i;

  for (i = 1; argv[i]; i++) {
    if (strcmp(argv[i], "-v") == 0)
      tstflags |= tst_verbatim;
    else
      usage();
  }

  retval |= test_insert(); fflush(stdout);
  retval |= test_rotate(); fflush(stdout);
  retval |= test_path(); fflush(stdout);
  retval |= test_balance(); fflush(stdout);

  return retval;
}

#endif