Logo Search packages:      
Sourcecode: w3mmee version File versions  Download package

btri.c

#include "btri.h"
#ifdef MAIN
#include <errno.h>
#include <setjmp.h>
#include <stdio.h>
#endif

#define BT_POS_LEN (5)
#define BT_POS_MASK ((1U << BT_POS_LEN) - 1U)
#define BT_POS_MAX (BT_POS_MASK)
#define BT_GET_POS(enc) ((enc) & BT_POS_MASK)

#define BT_LTYPE_POS (BT_POS_LEN)
#define BT_LTYPE_LEN (3)
#define BT_LTYPE_MASK ((1U << BT_LTYPE_LEN) - 1U)
#define BT_GET_LTYPE(enc) (((enc) >> BT_LTYPE_POS) & BT_LTYPE_MASK)

#define BT_RTYPE_POS (BT_LTYPE_POS + BT_LTYPE_LEN)
#define BT_RTYPE_LEN (BT_LTYPE_LEN)
#define BT_RTYPE_MASK ((1U << BT_RTYPE_LEN) - 1U)
#define BT_GET_RTYPE(enc) (((enc) >> BT_RTYPE_POS) & BT_RTYPE_MASK)

#define BT_MASKPOS_LEN (BT_POS_LEN)
#define BT_MASKPOS_MASK ((1U << BT_MASKPOS_LEN) - 1U)
#define BT_MASKPOS_MAX (BT_MASKPOS_MASK)

#define BT_RMASKPOS_POS (BT_RTYPE_POS + BT_RTYPE_LEN)
#define BT_GET_RMASKPOS(enc) (((enc) >> BT_RMASKPOS_POS) & BT_MASKPOS_MASK)

#define BT_LMASKPOS_POS (BT_RMASKPOS_POS + BT_MASKPOS_LEN)
#define BT_GET_LMASKPOS(enc) (((enc) >> BT_LMASKPOS_POS) & BT_MASKPOS_MASK)

#define BT_OFF_SHORT_POS (BT_RMASKPOS_POS + BT_MASKPOS_LEN)
#define BT_OFF_SHORT_LEN (32 - BT_OFF_SHORT_POS)
#define BT_OFF_SHORT_MASK ((1U << BT_OFF_SHORT_LEN) - 1U)
#define BT_OFF_SHORT_UPPER (BT_OFF_SHORT_MASK)
#define BT_GET_OFF_SHORT(enc) (((enc) >> BT_OFF_SHORT_POS) & BT_OFF_SHORT_MASK)

size_t
bt_enc(btri_uint_opt_tab_t *tab, unsigned int lcount, unsigned int *v)
{
  unsigned int enc;
  size_t n;

  enc = ((BT_POS_MASK - (tab->x.pos & BT_POS_MASK)) |
       ((tab->x.type[0] & BT_LTYPE_MASK) << BT_LTYPE_POS) |
       ((tab->x.type[1] & BT_RTYPE_MASK) << BT_RTYPE_POS) |
       ((BT_MASKPOS_MAX - ((tab->x.key_n[1] - 1) & BT_MASKPOS_MASK)) << BT_RMASKPOS_POS));

  if (tab->x.type[0] == bt_node) {
    if (1 + lcount < BT_OFF_SHORT_UPPER) {
      v[0] = enc | ((1 + lcount) << BT_OFF_SHORT_POS);
      n = 1;
    }
    else {
      v[0] = enc | (BT_OFF_SHORT_UPPER << BT_OFF_SHORT_POS);
      v[1] = 2 + lcount;
      n = 2;
    }
  }
  else {
    v[0] = enc | ((BT_MASKPOS_MAX - ((tab->x.key_n[0] - 1) & BT_MASKPOS_MASK)) << BT_LMASKPOS_POS);
    n = 1;
  }

  return n;
}

bt_result_t
bt_search(unsigned int key, unsigned int *node, unsigned int *p_value)
{
  bt_result_t res, last_res = bt_failure;
  size_t off, maskpos;
  unsigned int mask, last_mask = 0, *last_node = NULL;

search:
  switch ((res = BT_GET_LTYPE(*node))) {
  case bt_failure:
    goto check;
  case bt_node:
    if ((off = BT_GET_OFF_SHORT(*node)) < BT_OFF_SHORT_UPPER) {
      if (!(key & (1U << BT_GET_POS(*node)))) {
      ++node;
      goto search;
      }
    }
    else {
      if (!(key & (1U << BT_GET_POS(*node)))) {
      node += 2;
      goto search;
      }

      off = node[1];
    }

    break;
  default:
    maskpos = BT_GET_LMASKPOS(*node);
    mask = ~0U << maskpos;

    if (BT_GET_POS(*node) >= maskpos) {
      if (!(key & (1U << BT_GET_POS(*node)))) {
      if ((key & mask) == (node[1] & mask)) {
        node += 2;
        goto success;
      }
      else
        goto check;
      }
    }
    else if ((key & mask) == (node[1] & mask)) {
      last_res = res;
      last_mask = mask;
      last_node = node + 2;
    }
    else
      goto check;

    off = res == bt_v ? 1 + 2 + node[2] : 1 + 2;
    break;
  }

  switch ((res = BT_GET_RTYPE(*node))) {
  case bt_failure:
    goto check;
  case bt_node:
    node += off;
    goto search;
  default:
    mask = ~0U << BT_GET_RMASKPOS(*node);

    if ((key & mask) == (node[off] & mask)) {
      node += off + 1;
      goto success;
    }

    break;
  }
check:
  if ((res = last_res) == bt_failure)
    goto end;

  mask = last_mask;
  node = last_node;
success:
  if (p_value)
    switch (res) {
    case bt_n:
      *p_value = *node + (key & ~mask);
      break;
    case bt_v:
      if ((key & ~mask) >= node[0] || (*p_value = node[1 + (key & ~mask)]) == UINT_MAX)
      res = bt_failure;

      break;
    default:
      *p_value = *node;
      break;
    }
  else if (res == bt_v && ((key & ~mask) >= node[0] || node[1 + (key & ~mask)] == UINT_MAX))
    res = bt_failure;
end:
  return res;
}
  
void *
btri_new_node(btri_desc_t *desc)
{
  unsigned char *node;

  if ((node = desc->new_space(desc, desc->node_size))) {
    int i;

    for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i)
      *BTRI_O2P(bt_result_t *, node, desc->off_type[i]) = bt_failure;

    if (desc->init_node)
      node = desc->init_node(desc, node);
  }

  return node;
}

int
btri_cmp(btri_desc_t *desc, ptrdiff_t *p_b, btri_key_cursor_t *x, btri_key_cursor_t *y)
{
  const unsigned char *xp, *yp;
  ptrdiff_t b_alpha, e, e_alpha, e_bit;
  size_t alpha_bytes;
  unsigned int diff, xc;

  xp = x->base;
  yp = y->base;
  b_alpha = *p_b / desc->alpha_bit;
  e = x->n < y->n ? x->n : y->n;
  e_alpha = e / desc->alpha_bit;
  e_bit = e % desc->alpha_bit;
  alpha_bytes = desc->alpha_bit / CHAR_BIT;

  for (; b_alpha < e_alpha ; b_alpha += alpha_bytes) {
    xc = desc->alpha_filter(desc, &xp[b_alpha]);

    if ((diff = xc ^ desc->alpha_filter(desc, &yp[b_alpha]))) {
      e_bit = desc->alpha_bit;
      goto differ;
    }
  }

  if (e_bit) {
    xc = desc->alpha_filter(desc, &xp[b_alpha]) & (~0U << (desc->alpha_bit - e_bit));

    if (!(diff = xc ^ (desc->alpha_filter(desc, &yp[b_alpha]) & (~0U << (desc->alpha_bit - e_bit)))))
      goto same;
  }
  else
    goto same;
differ:
  {
    ptrdiff_t b, e, i;

    /* This search must not fail */
    for (b = desc->alpha_bit - e_bit, e = desc->alpha_bit ;;)
      if ((i = (b + e) / 2) == b)
      break;
      else if (diff & (~0U << i)) {
      if (i + 1 == e || !(diff & (~0U << (i + 1))))
        break;

      b = i + 1;
      }
      else
      e = i;

    *p_b = b_alpha * desc->alpha_bit + desc->alpha_bit - 1 - i;
    return (xc & (1U << i)) ? 1 : -1;
  }
same:
  *p_b = e;
  return x->n < y->n ? -1 : 0;
}

void
btri_key_fetch_cursor(btri_desc_t *desc, void *node, ptrdiff_t i, btri_key_cursor_t *y)
{
  *y = *BTRI_O2P(btri_key_cursor_t *, node, desc->off_key[i]);
}

void
btri_key_fetch_uint(btri_desc_t *desc, void *node, ptrdiff_t i, btri_key_cursor_t *y)
{
  y->base = BTRI_O2P(unsigned int *, node, desc->off_key[i]);
  y->n = *BTRI_O2P(char *, node, desc->off_key_n[i]);
}

int
btri_key_fetch_cursor_and_cmp(btri_desc_t *desc, ptrdiff_t *b, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  return desc->key_cmp(desc, b, x, BTRI_O2P(btri_key_cursor_t *, node, desc->off_key[i]));
}

static unsigned char msb_tab[1 << CHAR_BIT];
static unsigned char msbpos_tab[1 << CHAR_BIT];

static void
setup_msb_tab(void)
{
  ptrdiff_t i;

  for (i = 0 ; i < CHAR_BIT ; ++i) {
    unsigned char msb = 1U << i;
    ptrdiff_t j;

    for (j = 0 ; j < msb ; ++j) {
      msb_tab[msb | j] = msb;
      msbpos_tab[msb | j] = CHAR_BIT - 1 - i;
    }
  }
}

int
btri_fetch_uchar_and_ci_cmp(btri_desc_t *desc, ptrdiff_t *p_b, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  ptrdiff_t b_alpha, e, e_alpha, e_bit;
  const unsigned char *xp, *yp;
  btri_key_cursor_t *y;
  unsigned int diff, xc;

  b_alpha = *p_b / CHAR_BIT;
  xp = x->base;
  y = BTRI_O2P(btri_key_cursor_t *, node, desc->off_key[i]);
  yp = y->base;
  e = x->n < y->n ? x->n : y->n;
  e_alpha = e / CHAR_BIT;
  e_bit = e % CHAR_BIT;

  for (; b_alpha < e_alpha ; ++b_alpha) {
    xc = tolower(xp[b_alpha]);

    if ((diff = xc ^ tolower(yp[b_alpha])))
      goto differ;
  }

  if (e_bit) {
    xc = tolower(xp[b_alpha]) & (~0U << (CHAR_BIT - e_bit));

    if (!(diff = xc ^ (tolower(yp[b_alpha]) & (~0U << (CHAR_BIT - e_bit)))))
      goto same;
  }
  else
    goto same;
differ:
  if (!msb_tab[diff])
    setup_msb_tab();

  *p_b = b_alpha * CHAR_BIT + msbpos_tab[diff];
  return xc & msb_tab[diff] ? 1 : -1;
same:
  *p_b = e;
  return x->n < y->n ? -1 : 0;
}

int
btri_fetch_uchar_and_cmp(btri_desc_t *desc, ptrdiff_t *p_b, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  ptrdiff_t b_alpha, e, e_alpha, e_bit;
  const unsigned char *xp, *yp;
  btri_key_cursor_t *y;
  unsigned int diff, xc;

  b_alpha = *p_b / CHAR_BIT;
  xp = x->base;
  y = BTRI_O2P(btri_key_cursor_t *, node, desc->off_key[i]);
  yp = y->base;
  e = x->n < y->n ? x->n : y->n;
  e_alpha = e / CHAR_BIT;
  e_bit = e % CHAR_BIT;

  for (; b_alpha < e_alpha ; ++b_alpha) {
    xc = xp[b_alpha];

    if ((diff = xc ^ yp[b_alpha]))
      goto differ;
  }

  if (e_bit) {
    xc = xp[b_alpha] & (~0U << (CHAR_BIT - e_bit));

    if (!(diff = xc ^ (yp[b_alpha] & (~0U << (CHAR_BIT - e_bit)))))
      goto same;
  }
  else
    goto same;
differ:
  if (!msb_tab[diff])
    setup_msb_tab();

  *p_b = b_alpha * CHAR_BIT + msbpos_tab[diff];
  return xc & msb_tab[diff] ? 1 : -1;
same:
  *p_b = e;
  return x->n < y->n ? -1 : 0;
}

#define UINT_BIT (sizeof(unsigned int) * CHAR_BIT)

int
btri_fetch_uint_and_cmp(btri_desc_t *desc, ptrdiff_t *p_b, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  ptrdiff_t e_bit, b, yn;
  unsigned int xc, diff;

  yn = *BTRI_O2P(char *, node, desc->off_key_n[i]);
  e_bit = x->n < yn ? x->n : yn;
  b = UINT_BIT - e_bit;
  xc = *(unsigned int *)x->base;
  diff = (xc ^ *BTRI_O2P(unsigned int *, node, desc->off_key[i])) & (~0U << b);

  if (diff) {
    ptrdiff_t e, j;

    /* This search must not fail */
    for (e = UINT_BIT - *p_b ;;)
      if ((j = (b + e) / 2) == b)
      break;
      else if (diff & (~0U << j)) {
      if (j + 1 == e || !(diff & (~0U << (j + 1))))
        break;

      b = j + 1;
      }
      else
      e = j;

    *p_b = UINT_BIT - 1 - j;
    return (xc & (1U << j)) ? 1 : -1;
  }
  else {
    *p_b = e_bit;
    return x->n < yn ? -1 : 0;
  }
}

void *
btri_key_store_cursor(btri_desc_t *desc, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  btri_key_cursor_t *p;

  p = BTRI_O2P(btri_key_cursor_t *, node, desc->off_key[i]);
  *p = *x;
  return p;
}

void *
btri_key_store_uint(btri_desc_t *desc, btri_key_cursor_t *x, void *node, ptrdiff_t i)
{
  unsigned int *yk;
  char *yn;

  *(yk = BTRI_O2P(unsigned int *, node, desc->off_key[i])) = *(unsigned int *)x->base;
  *(yn = BTRI_O2P(char *, node, desc->off_key_n[i])) = x->n % (CHAR_BIT * sizeof(unsigned int));
  if (!*yn && x->n) *yn = CHAR_BIT * sizeof(unsigned int);
  return yk;
}

bt_result_t
btri_search(btri_desc_t *desc, int op, btri_key_cursor_t *key, void *node, void **p_value)
{
  bt_result_t *t[2], res, newtype;

  newtype = (op & BTRI_OP_N2N) ? bt_n : bt_1;
  t[0] = BTRI_O2P(bt_result_t *, node, desc->off_type[0]);

  if (*t[0] == bt_failure) {
    if (op & BTRI_OP_ADD) {
      res = *t[0] = newtype;
      *BTRI_O2P(ptrdiff_t *, node, desc->off_pos) = key->n;
      desc->key_store(desc, key, node, 0);
      *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
      *BTRI_O2P(bt_result_t *, node, desc->off_type[1]) = bt_failure;
    }
    else
      res = bt_failure;
  }
  else {
    ptrdiff_t b, match[2];
    int cmp[2];
    void *newnode;
    btri_key_cursor_t tempkey;

    b = 0;
  descend:
    match[0] = match[1] = b;

    if ((cmp[0] = desc->key_fetch_and_cmp(desc, &match[0], key, node, 0)) ||
      (*t[0] != bt_node && match[0] < key->n)) {
      t[1] = BTRI_O2P(bt_result_t *, node, desc->off_type[1]);

      if (*t[1] == bt_failure) {
      if (!cmp[0]) {
        if (op & BTRI_OP_SUB) {
          if (op & BTRI_OP_WR)
            *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
          else if (p_value)
            *p_value = *BTRI_O2P(void **, node, desc->off_value[0]);

          res = *t[0];
          goto end;
        }
        else
          cmp[0] = 1;
      }

      if (op & BTRI_OP_ADD) {
        int i = 1;

        if (cmp[0] < 0) {
          *t[1] = *t[0];
          desc->key_fetch(desc, node, 0, &tempkey);
          desc->key_store(desc, &tempkey, node, 1);
          *BTRI_O2P(void **, node, desc->off_value[1]) = *BTRI_O2P(void **, node, desc->off_value[0]);
          i = 0;
        }

        res = *t[i] = newtype;
        desc->key_store(desc, key, node, i);
        *BTRI_O2P(void **, node, desc->off_value[i]) = *p_value;
        *BTRI_O2P(ptrdiff_t *, node, desc->off_pos) = match[0];
      }
      else
        res = bt_failure;
      }
      else if ((cmp[1] = desc->key_fetch_and_cmp(desc, &match[1], key, node, 1)) ||
             (*t[1] != bt_node && match[1] < key->n)) {
      if (!cmp[1]) {
        if (op & BTRI_OP_SUB) {
          if (op & BTRI_OP_WR)
            *BTRI_O2P(void **, node, desc->off_value[1]) = *p_value;
          else if (p_value)
            *p_value = *BTRI_O2P(void **, node, desc->off_value[1]);

          res = *t[1];
          goto end;
        }
        else
          cmp[1] = 1;
      }

      if (!cmp[0]) {
        if (op & BTRI_OP_SUB) {
          if (op & BTRI_OP_WR)
            *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
          else if (p_value)
            *p_value = *BTRI_O2P(void **, node, desc->off_value[0]);

          res = *t[0];
          goto end;
        }
        else
          cmp[0] = 1;
      }

      if (op & BTRI_OP_ADD) {
        int new;
        ptrdiff_t pos = *BTRI_O2P(ptrdiff_t *, node, desc->off_pos);

        if (match[1] == match[0] && pos == match[0]) {
          if ((newnode = btri_new_node(desc))) {
            if (cmp[0] < 0) {
            *BTRI_O2P(ptrdiff_t *, newnode, desc->off_pos) = match[0];
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[0]) = *t[0];
            desc->key_fetch(desc, node, 0, &tempkey);
            desc->key_store(desc, &tempkey, newnode, 0);
            *BTRI_O2P(void **, newnode, desc->off_value[0]) = *BTRI_O2P(void **, node, desc->off_value[0]);
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[1]) = *t[1];
            desc->key_fetch(desc, node, 1, &tempkey);
            desc->key_store(desc, &tempkey, newnode, 1);
            *BTRI_O2P(void **, newnode, desc->off_value[1]) = *BTRI_O2P(void **, node, desc->off_value[1]);
            *t[1] = bt_node;
            tempkey.n = match[0];
            desc->key_store(desc, &tempkey, node, 1);
            *BTRI_O2P(void **, node, desc->off_value[1]) = newnode;
            res = *t[0] = newtype;
            desc->key_store(desc, key, node, 0);
            *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
            }
            else {
            new = cmp[1] < 0 ? 0 : 1;
            *BTRI_O2P(ptrdiff_t *, newnode, desc->off_pos) = match[0];
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[1 - new]) = *t[1];
            desc->key_fetch(desc, node, 1, &tempkey);
            desc->key_store(desc, &tempkey, newnode, 1 - new);
            *BTRI_O2P(void **, newnode, desc->off_value[1 - new]) = *BTRI_O2P(void **, node, desc->off_value[1]);
            *t[1] = bt_node;
            tempkey.n = match[0];
            desc->key_store(desc, &tempkey, node, 1);
            *BTRI_O2P(void **, node, desc->off_value[1]) = newnode;
            res = *BTRI_O2P(bt_result_t *, newnode, desc->off_type[new]) = newtype;
            desc->key_store(desc, key, newnode, new);
            *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
            }
          }
          else
            res = bt_failure;
        }
        else if ((newnode = btri_new_node(desc))) {
          int hit = match[0] > match[1] ? 0 : 1;

          if (pos > match[1 - hit]) {
            new = cmp[1 - hit] < 0 ? 0 : 1;
            *BTRI_O2P(ptrdiff_t *, newnode, desc->off_pos) = pos;
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[hit]) = *t[hit];
            desc->key_fetch(desc, node, hit, &tempkey);
            desc->key_store(desc, &tempkey, newnode, hit);
            *BTRI_O2P(void **, newnode, desc->off_value[hit]) = *BTRI_O2P(void **, node, desc->off_value[hit]);
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[1 - hit]) = *t[1 - hit];
            desc->key_fetch(desc, node, 1 - hit, &tempkey);
            desc->key_store(desc, &tempkey, newnode, 1 - hit);
            *BTRI_O2P(void **, newnode, desc->off_value[1 - hit]) = *BTRI_O2P(void **, node, desc->off_value[1 - hit]);
            *BTRI_O2P(ptrdiff_t *, node, desc->off_pos) = match[1 - hit];
            *BTRI_O2P(bt_result_t *, node, desc->off_type[1 - new]) = bt_node;
            tempkey.n = pos;
            desc->key_store(desc, &tempkey, node, 1 - new);
            *BTRI_O2P(void **, node, desc->off_value[1 - new]) = newnode;
            res = *BTRI_O2P(bt_result_t *, node, desc->off_type[new]) = newtype;
            desc->key_store(desc, key, node, new);
            *BTRI_O2P(void **, node, desc->off_value[new]) = *p_value;
          }
          else {
            new = cmp[hit] < 0 ? 0 : 1;
            *BTRI_O2P(ptrdiff_t *, newnode, desc->off_pos) = match[hit];
            *BTRI_O2P(bt_result_t *, newnode, desc->off_type[1 - new]) = *t[hit];
            desc->key_fetch(desc, node, hit, &tempkey);
            desc->key_store(desc, &tempkey, newnode, 1 - new);
            *BTRI_O2P(void **, newnode, desc->off_value[1 - new]) = *BTRI_O2P(void **, node, desc->off_value[hit]);
            *t[hit] = bt_node;
            tempkey.n = match[hit];
            desc->key_store(desc, &tempkey, node, hit);
            *BTRI_O2P(void **, node, desc->off_value[hit]) = newnode;
            res = *BTRI_O2P(bt_result_t *, newnode, desc->off_type[new]) = newtype;
            desc->key_store(desc, key, newnode, new);
            *BTRI_O2P(void **, newnode, desc->off_value[new]) = *p_value;
          }
        }
        else
          res = bt_failure;
      }
      else
        res = bt_failure;
      }
      else if (*t[1] == bt_node) {
      node = *BTRI_O2P(void **, node, desc->off_value[1]);
      t[0] = BTRI_O2P(bt_result_t *, node, desc->off_type[0]);
      b = match[1];
      goto descend;
      }
      else {
      if (op & BTRI_OP_WR)
        *BTRI_O2P(void **, node, desc->off_value[1]) = *p_value;
      else if (p_value)
        *p_value = *BTRI_O2P(void **, node, desc->off_value[1]);

      res = *t[1];
      }
    }
    else if (*t[0] == bt_node) {
      node = *BTRI_O2P(void **, node, desc->off_value[0]);
      t[0] = BTRI_O2P(bt_result_t *, node, desc->off_type[0]);
      b = match[0];
      goto descend;
    }
    else {
      if (op & BTRI_OP_WR)
      *BTRI_O2P(void **, node, desc->off_value[0]) = *p_value;
      else if (p_value)
      *p_value = *BTRI_O2P(void **, node, desc->off_value[0]);

      res = *t[0];
    }
  }
end:
  return res;
}

bt_result_t
btri_fast_search_mem(const char *key, ptrdiff_t bytes, btri_string_tab_t *node, void **p_value)
{
  bt_result_t res;
  ptrdiff_t bits;

  bits = bytes * CHAR_BIT;
search:
  if (bits < node->pos) {
    res = bt_failure;
    goto end;
  }

  switch (res = node->type[0]) {
  case bt_failure:
    goto end;
  case bt_node:
    if (!(((unsigned char *)key)[node->pos / CHAR_BIT] & (1U << (CHAR_BIT - 1 - node->pos % CHAR_BIT)))) {
      node = node->value[0];
      goto search;
    }

    break;
  default:
    if (node->pos < node->key[0].n) {
      if (((unsigned char *)key)[node->pos / CHAR_BIT] & (1U << (CHAR_BIT - 1 - node->pos % CHAR_BIT)))
      break;
    }
    else if (bits > node->pos)
      break;

    if (bits == node->key[0].n && !memcmp(key, node->key[0].base, bytes)) {
      if (p_value)
      *p_value = node->value[0];
    }
    else
      res = bt_failure;

    goto end;
  }

  switch (res = node->type[1]) {
  case bt_failure:
    goto end;
  case bt_node:
    node = node->value[1];
    goto search;
  default:
    if (bits == node->key[1].n && !memcmp(key, node->key[1].base, bytes)) {
      if (p_value)
      *p_value = node->value[1];
    }
    else
      res = bt_failure;

    break;
  }
end:
  return res;
}

static int
mem_ci_cmp(const char *x, const char *y, size_t n)
{
  int z, xc, yc;

  for (; n > 0 ; --n) {
    xc = (unsigned char)*x++;
    yc = (unsigned char)*y++;

    if ((z = tolower(xc) - tolower(yc)))
      return z;
  }

  return 0;
}

bt_result_t
btri_fast_ci_search_mem(const char *key, ptrdiff_t bytes, btri_string_tab_t *node, void **p_value)
{
  bt_result_t res;
  ptrdiff_t bits;

  bits = bytes * CHAR_BIT;
search:
  if (bits < node->pos) {
    res = bt_failure;
    goto end;
  }

  switch (res = node->type[0]) {
  case bt_failure:
    goto end;
  case bt_node:
    if (!(tolower(((unsigned char *)key)[node->pos / CHAR_BIT]) & (1U << (CHAR_BIT - 1 - node->pos % CHAR_BIT)))) {
      node = node->value[0];
      goto search;
    }

    break;
  default:
    if (node->pos < node->key[0].n) {
      if (tolower(((unsigned char *)key)[node->pos / CHAR_BIT]) & (1U << (CHAR_BIT - 1 - node->pos % CHAR_BIT)))
      break;
    }
    else if (bits > node->pos)
      break;

    if (bits == node->key[0].n && !mem_ci_cmp(key, node->key[0].base, bytes)) {
      if (p_value)
      *p_value = node->value[0];
    }
    else
      res = bt_failure;

    goto end;
  }

  switch (res = node->type[1]) {
  case bt_failure:
    goto end;
  case bt_node:
    node = node->value[1];
    goto search;
  default:
    if (bits == node->key[1].n && !mem_ci_cmp(key, node->key[1].base, bytes)) {
      if (p_value)
      *p_value = node->value[1];
    }
    else
      res = bt_failure;

    break;
  }
end:
  return res;
}

bt_result_t
btri_fast_search_uint(unsigned int key, btri_uint_tab_t *node, void **p_value)
{
  bt_result_t res, last_res = bt_failure;
  void *value = NULL;
  unsigned int mask, last_mask = 0U;

search:
  switch (res = node->type[0]) {
  case bt_failure:
    goto check;
  case bt_node:
    if (!(key & (1U << (UINT_BIT - 1 - node->pos)))) {
      node = node->value[0];
      goto search;
    }

    break;
  default:
    if (node->pos < node->key_n[0]) {
      if (!(key & (1U << (UINT_BIT - 1 - node->pos)))) {
      mask = ~0U << (UINT_BIT - node->key_n[0]);

      if ((key & mask) == (node->key[0] & mask)) {
        value = node->value[0];
        goto success;
      }
      else
        goto check;
      }
    }
    else {
      mask = ~0U << (UINT_BIT - node->key_n[0]);

      if ((key & mask) == (node->key[0] & mask)) {
      last_res = res;
      last_mask = mask;
      value = node->value[0];
      }
      else
      goto check;
    }

    break;
  }

  switch (res = node->type[1]) {
  case bt_failure:
    goto check;
  case bt_node:
    node = node->value[1];
    goto search;
  default:
    mask = ~0U << (UINT_BIT - node->key_n[1]);

    if ((key & mask) == (node->key[1] & mask)) {
      value = node->value[1];
      goto success;
    }

    break;
  }
check:
  if ((res = last_res) == bt_failure)
    goto end;

  mask = last_mask;
success:
  if (p_value)
    *p_value = res == bt_n ? (void *)(((unsigned int)value & mask) | (key & ~mask)) : value;
end:
  return res;
}

void
btri_free_recursively(btri_desc_t *desc, void *node)
{
  alt_freer_t freer = alt_set_freer(NULL);

  alt_set_freer(freer);

  if (freer) {
    size_t i;

    for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i)
      switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[i])) {
      case bt_node:
      btri_free_recursively(desc, *BTRI_O2P(void **, node, desc->off_value[i]));
      break;
      case bt_v:
      if (desc->free_space)
        desc->free_space(desc, *BTRI_O2P(void **, node, desc->off_value[i]));
      default:
      break;
      }

    if (desc->free_node)
      desc->free_node(desc, node);
  }
}

void *
btri_copy(btri_desc_t *desc, void *old)
{
  void *new;

  if ((new = btri_new_node(desc))) {
    btri_key_cursor_t key;
    void *sub;
    size_t i;

    *BTRI_O2P(ptrdiff_t *, new, desc->off_pos) = *BTRI_O2P(ptrdiff_t *, old, desc->off_pos);

    for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i) {
      bt_result_t *t;
      void *value;

      t = BTRI_O2P(bt_result_t *, old, desc->off_type[i]);
      value = *BTRI_O2P(void **, old, desc->off_value[i]);

      switch (*BTRI_O2P(bt_result_t *, new, desc->off_type[i]) = *t) {
      case bt_node:
      if (!(sub = btri_copy(desc, value)))
        goto failure;
      break;
      case bt_failure:
      continue;
      default:
      sub = value;
      }

      desc->key_fetch(desc, old, i, &key);
      desc->key_store(desc, &key, new, i);
      *BTRI_O2P(void **, new, desc->off_value[i]) = sub;
    }
  }

  return new;
failure:
  btri_free_recursively(desc, new);
  return NULL;
}

static void *
btri_merge_loop(btri_desc_t *desc, void *new, void *old)
{
  btri_key_cursor_t key;
  void *value;
  size_t i;

  for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i) {
    value = *BTRI_O2P(void **, old, desc->off_value[i]);

    switch (*BTRI_O2P(bt_result_t *, old, desc->off_type[i])) {
    case bt_node:
      if (!(new = btri_merge_loop(desc, new, value)))
      goto end;

      break;
    case bt_failure:
      continue;
    default:
      desc->key_fetch(desc, old, i, &key);

      if (btri_search(desc, BTRI_OP_ADD|BTRI_OP_WR, &key, new, &value) == bt_failure) {
      new = NULL;
      goto end;
      }

      break;
    }
  }
end:
  return new;
}

void *
btri_merge(btri_desc_t *desc, void *x, void *y)
{
  void *new;

  if (!x)
    new = y;
  else if (!y)
    new = x;
  else if ((new = btri_copy(desc, x))) {
    if (!btri_merge_loop(desc, new, y)) {
      btri_free_recursively(desc, new);
      new = NULL;
    }
  }

  return new;
}

int
btri_map(btri_desc_t *desc, void *node, int (*func)(btri_desc_t *desc, void **p_value, void *arg), void *arg)
{
  if (node) {
    ptrdiff_t i;

  loop:
    for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i)
      switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[i])) {
      case bt_failure:
      return 1;
      case bt_node:
      if (i) {
        node = *BTRI_O2P(void **, node, desc->off_value[i]);
        goto loop;
      }

      if (!btri_map(desc, *BTRI_O2P(void **, node, desc->off_value[i]), func, arg))
        return 0;

      break;
      default:
      if (!func(desc, BTRI_O2P(void **, node, desc->off_value[i]), arg))
        return 0;

      break;
      }
  }

  return 1;
}

int
btri_map_max_smaller(btri_desc_t *desc, ptrdiff_t b, btri_key_cursor_t *key, void *node,
                 int (*func)(btri_desc_t *desc, void **p_value, void *arg), void *arg)
{
  if (node) {
    ptrdiff_t save;

  loop:
    save = b;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[1])) {
    case bt_failure:
      break;
    case bt_node:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 1) >= 0 &&
        btri_map_max_smaller(desc, b, key, *BTRI_O2P(void **, node, desc->off_value[1]), func, arg))
      return 1;

      break;
    default:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 1) > 0 &&
        func(desc, BTRI_O2P(void **, node, desc->off_value[1]), arg))
      return 1;

      break;
    }

    b = save;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[0])) {
    case bt_failure:
      break;
    case bt_node:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 0) >= 0) {
      node = *BTRI_O2P(void **, node, desc->off_value[0]);
      save = b;
      goto loop;
      }

      break;
    default:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 0) > 0)
      return func(desc, BTRI_O2P(void **, node, desc->off_value[0]), arg);

      break;
    }
  }

  return 0;
}

int
btri_map_min_larger(btri_desc_t *desc, ptrdiff_t b, btri_key_cursor_t *key, void *node,
                int (*func)(btri_desc_t *desc, void **p_value, void *arg), void *arg)
{
  if (node) {
    ptrdiff_t save;

  loop:
    save = b;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[0])) {
    case bt_failure:
      return 0;
    case bt_node:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 0) <= 0 &&
        btri_map_min_larger(desc, b, key, *BTRI_O2P(void **, node, desc->off_value[0]), func, arg))
      return 1;

      break;
    default:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 0) < 0 &&
        func(desc, BTRI_O2P(void **, node, desc->off_value[0]), arg))
      return 1;

      break;
    }

    b = save;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[1])) {
    case bt_failure:
      break;
    case bt_node:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 1) <= 0) {
      node = *BTRI_O2P(void **, node, desc->off_value[1]);
      goto loop;
      }

      break;
    default:
      if (desc->key_fetch_and_cmp(desc, &b, key, node, 1) < 0)
      return func(desc, BTRI_O2P(void **, node, desc->off_value[1]), arg);

      break;
    }
  }

  return 0;
}

int
btri_map_region(btri_desc_t *desc,
            ptrdiff_t beg_b, btri_key_cursor_t *beg, ptrdiff_t end_b, btri_key_cursor_t *end, void *node,
            int (*func)(btri_desc_t *desc, void **p_value, void *arg), void *arg)
{
  if (node) {
    ptrdiff_t beg_save, end_save;
    int beg_cmp, end_cmp;

  loop:
    beg_save = beg_b;
    end_save = end_b;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[0])) {
    case bt_failure:
      return 0;
    case bt_node:
      if ((end_cmp = desc->key_fetch_and_cmp(desc, &end_b, end, node, 0)) < 0)
      return 0;
      else if ((beg_cmp = desc->key_fetch_and_cmp(desc, &beg_b, beg, node, 0)) > 0)
      break;
      else if (!end_cmp) {
      node = *BTRI_O2P(void **, node, desc->off_value[0]);
      goto loop;
      }
      else if (beg_cmp) {
      btri_map(desc, *BTRI_O2P(void **, node, desc->off_value[0]), func, arg);
      break;
      }
      else if (!btri_map_region(desc, beg_b, beg, end_b, end, *BTRI_O2P(void **, node, desc->off_value[0]), func, arg))
      return 0;
      else
      break;
    default:
      if ((end_cmp = desc->key_fetch_and_cmp(desc, &end_b, end, node, 0)) < 0)
      return 0;
      else if ((beg_cmp = desc->key_fetch_and_cmp(desc, &beg_b, beg, node, 0)) > 0)
      break;
      else if (!end_cmp) {
      btri_key_cursor_t key;

      desc->key_fetch(desc, node, 0, &key);

      if (*BTRI_O2P(ptrdiff_t *, node, desc->off_pos) < key.n)
        return end_b < end->n ? func(desc, BTRI_O2P(void **, node, desc->off_value[0]), arg) : 0;
      else if (end_b < end->n) {
        if (!func(desc, BTRI_O2P(void **, node, desc->off_value[0]), arg))
          return 0;
      }

      break;
      }
      else if (!func(desc, BTRI_O2P(void **, node, desc->off_value[0]), arg))
      return 0;
      else
      break;
    }

    beg_b = beg_save;
    end_b = end_save;

    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[1])) {
    case bt_failure:
      return 0;
    case bt_node:
      if ((end_cmp = desc->key_fetch_and_cmp(desc, &end_b, end, node, 1)) < 0)
      return 0;
      else if ((beg_cmp = desc->key_fetch_and_cmp(desc, &beg_b, beg, node, 1)) > 0)
      return 1;
      else {
      node = *BTRI_O2P(void **, node, desc->off_value[1]);
      goto loop;
      }
    default:
      if ((end_cmp = desc->key_fetch_and_cmp(desc, &end_b, end, node, 1)) < 0)
      return 0;
      else if ((beg_cmp = desc->key_fetch_and_cmp(desc, &beg_b, beg, node, 1)) > 0)
      return 1;
      else
      return (end_cmp || end_b < end->n) ? func(desc, BTRI_O2P(void **, node, desc->off_value[1]), arg) : 0;
    }
  }

  return 0;
}

bt_result_t
btri_search_str(btri_desc_t *desc, int op, const char *key, void *node, void **p_value)
{
  btri_key_cursor_t cursor;

  cursor.base = key;
  cursor.n = strlen(key) * CHAR_BIT;
  return btri_search(desc, op, &cursor, node, p_value);
}

bt_result_t
btri_search_mem(btri_desc_t *desc, int op, const void *key, size_t len, void *node, void **p_value)
{
  btri_key_cursor_t cursor;

  cursor.base = key;
  cursor.n = len * CHAR_BIT;
  return btri_search(desc, op, &cursor, node, p_value);
}

bt_result_t
btri_search_uint(btri_desc_t *desc, int op, unsigned int key, void *node, void **p_value)
{
  btri_key_cursor_t cursor;

  cursor.base = &key;
  cursor.n = sizeof(unsigned int) * CHAR_BIT;
  return btri_search(desc, op, &cursor, node, p_value);
}

bt_result_t
btri_add_uint_n_to_1(btri_desc_t *desc, unsigned int beg, unsigned int end, void *node, void *value)
{
  btri_key_cursor_t cursor;
  unsigned int mask, len;
  bt_result_t res = bt_failure;

  while (beg <= end) {
    for (len = 0, mask = 1U ; !(beg & mask) && beg + mask + mask - 1 <= end ;) {
      ++len;
      mask <<= 1;
    }

    cursor.base = &beg;
    cursor.n = sizeof(unsigned int) * CHAR_BIT - len;

    if ((res = btri_search(desc, BTRI_OP_ADD | BTRI_OP_WR, &cursor, node, &value)) == bt_failure)
      break;

    if ((beg + mask) <= beg)
      break;

    beg += mask;
  }

  return res;
}

bt_result_t
btri_add_uint_n_to_n(btri_desc_t *desc, unsigned int beg, unsigned int end, void *node, unsigned int value)
{
  btri_key_cursor_t cursor;
  unsigned int mask, len;
  bt_result_t res = bt_failure;

  while (beg <= end) {
    for (len = 0, mask = 1U ; !(beg & mask) && beg + mask + mask - 1 <= end ;) {
      ++len;
      mask <<= 1;
    }

    cursor.base = &beg;
    cursor.n = sizeof(unsigned int) * CHAR_BIT - len;

    if ((res = btri_search(desc, BTRI_OP_ADD | BTRI_OP_WR | BTRI_OP_N2N, &cursor, node, (void **)&value))
      == bt_failure)
      break;

    if ((beg + mask) <= beg)
      break;

    beg += mask;
    value += mask;
  }

  return res;
}

static void
btri_uint_tab_to_vector_loop(btri_desc_t *desc, unsigned int mask, void *node, unsigned int *v)
{
  unsigned int i, key, b, e, val, *v1;
  char key_n;

loop:
  for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i)
    switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[i])) {
    case bt_node:
      if (i) {
      node = *BTRI_O2P(void **, node, desc->off_value[i]);
      goto loop;
      }

      btri_uint_tab_to_vector_loop(desc, mask, *BTRI_O2P(void **, node, desc->off_value[i]), v);
      break;
    case bt_1:
      key = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);
      key_n = *BTRI_O2P(char *, node, desc->off_key_n[i]);
      b = key & (~0U << (desc->alpha_bit - key_n)) & mask;
      e = b + (1U << (desc->alpha_bit - key_n));

      while (v[0] < b)
      v[++(v[0])] = UINT_MAX;

      val = (unsigned int)*BTRI_O2P(void **, node, desc->off_value[i]);

      while (b < e)
      v[++b] = val;

      v[0] = e;
      break;
    case bt_n:
      key = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);
      key_n = *BTRI_O2P(char *, node, desc->off_key_n[i]);
      b = key & (~0U << (desc->alpha_bit - key_n)) & mask;
      e = b + (1U << (desc->alpha_bit - key_n));

      while (v[0] < b)
      v[++(v[0])] = UINT_MAX;

      val = (unsigned int)*BTRI_O2P(void **, node, desc->off_value[i]);

      while (b < e)
      v[++b] = val++;

      v[0] = e;
      break;
    case bt_v:
      key = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);
      key_n = *BTRI_O2P(char *, node, desc->off_key_n[i]);
      b = key & (~0U << (desc->alpha_bit - key_n)) & mask;

      while (v[0] < b)
      v[++(v[0])] = UINT_MAX;

      v1 = *BTRI_O2P(void **, node, desc->off_value[i]);
      memcpy(&v[1 + b], &v1[1], sizeof(unsigned int) * v1[0]);
      v[0] = b + v1[0];
      break;
    default:
      break;
    }
}
  
unsigned int *
btri_uint_tab_to_vector(btri_desc_t *desc, unsigned int mask, unsigned int nvals, void *node)
{
  unsigned int *v;

  if ((v = desc->new_space(desc, sizeof(unsigned int) * (1 + nvals)))) {
    v[0] = 0;
    btri_uint_tab_to_vector_loop(desc, mask, node, v);
  }

  return v;
}

void *
btri_uint_optimize(btri_desc_t *desc, void *node, bt_result_t *p_t, char *p_e,
               unsigned int *p_count, unsigned int *p_max, int uint_value)
{
  bt_result_t *t[2];
  unsigned int key[2], i, delta, count[2], *mymax, *mycount, tmax;
  char *key_n[2];
  void **sub[2];

  mymax = BTRI_O2P(unsigned int *, node, desc->off_max);
  *mymax = 0U;

  for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i) {
    t[i] = BTRI_O2P(bt_result_t *, node, desc->off_type[i]);
    key[i] = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);
    key_n[i] = BTRI_O2P(char *, node, desc->off_key_n[i]);
    sub[i] = BTRI_O2P(void **, node, desc->off_value[i]);

    if (*t[i] == bt_node) {
      void *new = btri_uint_optimize(desc, *sub[i], t[i], key_n[i], &count[i], mymax, uint_value);

      if (*sub[i] != new) {
      btri_free_recursively(desc, *sub[i]);
      *sub[i] = new;
      }

      if (*p_max < *mymax)
      *p_max = *mymax;
    }
    else if (*t[i] == bt_failure)
      count[i] = 0;
    else {
      count[i] = 2;
      tmax = key[i] | ~(~0U << (desc->alpha_bit - *key_n[i]));

      if (*mymax < tmax)
      *mymax = tmax;

      if (*p_max < tmax)
      *p_max = tmax;
    }
  }

  mycount = BTRI_O2P(unsigned int *, node, desc->off_count);
  *mycount = ((1 + count[0] < BT_OFF_SHORT_UPPER) ? 1 : 2) + count[0] + count[1];
  delta = 1U << (desc->alpha_bit - *key_n[0]);

  if (*t[0] != bt_failure && *t[0] == *t[1] && *key_n[0] == *key_n[1] &&
      !(key[0] & delta) &&
      (key[1] & ~(delta - 1U)) == (key[0] & ~(delta - 1U)) + delta &&
      ((*t[0] == bt_1 && (*sub[1] == *sub[0] ||
                    (uint_value && delta == 1U && *(unsigned int *)sub[1] == *(unsigned int *)sub[0] + 1U))) ||
       (*t[0] == bt_n && *(unsigned int *)sub[1] == *(unsigned int *)sub[0] + delta))) {
    *p_t = *sub[1] == *sub[0] ? bt_1 : bt_n;
    *p_e = *key_n[0] - 1;

    if (*p_max < (tmax = key[0] | ~(~0U << (desc->alpha_bit - *p_e))))
      *p_max = tmax;

    *p_count = 2;
    return *sub[0];
  }

  if (uint_value > 1) {
    for (i = 0 ; i < sizeof(desc->off_type) / sizeof(desc->off_type[0]) ; ++i)
      if (*t[i] == bt_node) {
      unsigned int mask, subkeys, *subcount;

      mask = ~0U << (desc->alpha_bit - *key_n[i]);
      subkeys = *BTRI_O2P(unsigned int *, *sub[i], desc->off_max) - (key[i] & mask) + 1U;
      subcount = BTRI_O2P(unsigned int *, *sub[i], desc->off_count);

      if (2U + subkeys <= *subcount / 4 * 5) {
        unsigned int *v;

        if ((v = btri_uint_tab_to_vector(desc, ~mask, subkeys, *sub[i]))) {
          *t[i] = bt_v;
          *sub[i] = v;
          count[i] = *subcount = 2U + subkeys;
        }
      }
      }

    *mycount = ((1U + count[0] < BT_OFF_SHORT_UPPER) ? 1U : 2U) + count[0] + count[1];
  }

  *p_count = *mycount;
  return node;
}

size_t
btri_pack_uint_tab(btri_desc_t *desc, void *node, unsigned int *dest)
{
  bt_result_t t[2];
  size_t gen = 0;
loop:
  if ((t[0] = *BTRI_O2P(bt_result_t *, node, desc->off_type[0])) != bt_failure) {
    void *subv[2];
    unsigned int lcount = 0;
    int i;

    subv[0] = *BTRI_O2P(void **, node, desc->off_value[0]);
    subv[1] = *BTRI_O2P(void **, node, desc->off_value[1]);
    t[1] = *BTRI_O2P(bt_result_t *, node, desc->off_type[1]);

    if (t[0] == bt_node)
      lcount = *BTRI_O2P(unsigned int *, subv[0], desc->off_count);

    gen += bt_enc(node, lcount, &dest[gen]);

    for (i = 0 ; i < sizeof(t) / sizeof(t[0]) ; ++i) {
      unsigned int key = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);

      switch (t[i]) {
      case bt_node:
      if (i) {
        node = subv[i];
        goto loop;
      }

      gen += btri_pack_uint_tab(desc, subv[i], &dest[gen]);
      break;
      case bt_1:
      case bt_n:
      dest[gen++] = key;
      dest[gen++] = (unsigned int)subv[i];
      break;
      case bt_v:
      dest[gen++] = key;
      memcpy(&dest[gen], subv[i], sizeof(unsigned int) * (1 + *(unsigned int *)subv[i]));
      gen += 1 + *(unsigned int *)subv[i];
      break;
      default:
      break;
      }
    }
  }

  return gen;
}

unsigned int
btri_uint_filter(btri_desc_t *desc, const void *p)
{
  return *(int *)p;
}

unsigned int
btri_uint_lower_filter(btri_desc_t *desc, const void *p)
{
  return tolower(*(int *)p);
}

unsigned int
btri_uchar_filter(btri_desc_t *desc, const void *p)
{
  return *(unsigned char *)p;
}

unsigned int
btri_uchar_lower_filter(btri_desc_t *desc, const void *p)
{
  return tolower(*(unsigned char *)p);
}

void *
btri_malloc(btri_desc_t *desc, size_t size)
{
  return alt_call_malloc(size);
}

void *
btri_realloc(btri_desc_t *desc, void *old, size_t size)
{
  return alt_call_realloc(old, size);
}

void
btri_free_key(btri_desc_t *desc, void *key, ptrdiff_t size)
{
  alt_call_free(key);
}

void
btri_free_node(btri_desc_t *desc, void *node)
{
  alt_call_free(node);
}

btri_desc_t btri_string_ci_tab_desc = {
  offsetof(btri_string_tab_t, pos),
  0, 0,
  {offsetof(btri_string_tab_t, type[0]), offsetof(btri_string_tab_t, type[1])},
  {offsetof(btri_string_tab_t, key[0].base), offsetof(btri_string_tab_t, key[1].base)},
  {offsetof(btri_string_tab_t, key[0].n), offsetof(btri_string_tab_t, key[1].n)},
  {offsetof(btri_string_tab_t, value[0]), offsetof(btri_string_tab_t, value[1])},
  CHAR_BIT,
  btri_uchar_lower_filter,
  sizeof(btri_string_tab_t),
  btri_cmp,
  btri_key_fetch_cursor,
  btri_fetch_uchar_and_ci_cmp,
  btri_key_store_cursor,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

btri_desc_t btri_string_tab_desc = {
  offsetof(btri_string_tab_t, pos),
  0, 0,
  {offsetof(btri_string_tab_t, type[0]), offsetof(btri_string_tab_t, type[1])},
  {offsetof(btri_string_tab_t, key[0].base), offsetof(btri_string_tab_t, key[1].base)},
  {offsetof(btri_string_tab_t, key[0].n), offsetof(btri_string_tab_t, key[1].n)},
  {offsetof(btri_string_tab_t, value[0]), offsetof(btri_string_tab_t, value[1])},
  CHAR_BIT,
  btri_uchar_filter,
  sizeof(btri_string_tab_t),
  btri_cmp,
  btri_key_fetch_cursor,
  btri_fetch_uchar_and_cmp,
  btri_key_store_cursor,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

btri_desc_t btri_uint_tab_desc = {
  offsetof(btri_uint_tab_t, pos),
  0, 0,
  {offsetof(btri_uint_tab_t, type[0]), offsetof(btri_uint_tab_t, type[1])},
  {offsetof(btri_uint_tab_t, key[0]), offsetof(btri_uint_tab_t, key[1])},
  {offsetof(btri_uint_tab_t, key_n[0]), offsetof(btri_uint_tab_t, key_n[1])},
  {offsetof(btri_uint_tab_t, value[0]), offsetof(btri_uint_tab_t, value[1])},
  UINT_BIT,
  btri_uint_filter,
  sizeof(btri_uint_tab_t),
  btri_cmp,
  btri_key_fetch_uint,
  btri_fetch_uint_and_cmp,
  btri_key_store_uint,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

btri_desc_t btri_uint_opt_tab_desc = {
  offsetof(btri_uint_opt_tab_t, x.pos),
  offsetof(btri_uint_opt_tab_t, count),
  offsetof(btri_uint_opt_tab_t, max),
  {offsetof(btri_uint_opt_tab_t, x.type[0]), offsetof(btri_uint_opt_tab_t, x.type[1])},
  {offsetof(btri_uint_opt_tab_t, x.key[0]), offsetof(btri_uint_opt_tab_t, x.key[1])},
  {offsetof(btri_uint_opt_tab_t, x.key_n[0]), offsetof(btri_uint_opt_tab_t, x.key_n[1])},
  {offsetof(btri_uint_opt_tab_t, x.value[0]), offsetof(btri_uint_opt_tab_t, x.value[1])},
  UINT_BIT,
  btri_uint_filter,
  sizeof(btri_uint_opt_tab_t),
  btri_cmp,
  btri_key_fetch_uint,
  btri_fetch_uint_and_cmp,
  btri_key_store_uint,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

#ifdef MAIN

char *
skip_space(char *s)
{
  while (*s && isspace(*s))
    ++s;

  return s;
}

char *
read_string(char **p_s, char *d)
{
  char *s, *ep;
  const char *delim;
  size_t n;

  s = skip_space(*p_s);

  if (*s == '"') {
    delim = "\"";
    n = sizeof("\"") - 1;
    ++s;
  }
  else {
    delim = " \t\r\n\v\f";
    n = sizeof(" \t\r\n\v\f");
  }

  for (; !memchr(delim, *s, n) && *s ; ++s)
    if (*s == '\\')
      switch (*++s) {
      case '\0':
      return NULL;
      case 'a':
      *d++ = '\a';
      break;
      case 'b':
      *d++ = '\b';
      break;
      case 'f':
      *d++ = '\f';
      break;
      case 'n':
      *d++ = '\n';
      break;
      case 'r':
      *d++ = '\r';
      break;
      case 't':
      *d++ = '\t';
      break;
      case 'v':
      *d++ = '\v';
      break;
      case 'x':
      *d++ = strtoul(++s, &ep, 16);
      s = ep;
      break;
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      *d++ = strtoul(s, &ep, 8);
      s = ep;
      break;
      default:
      *d++ = *s;
      break;
      }
    else
      *d++ = *s;

  if (!memchr(delim, *s, n))
    return NULL;

  *p_s = *s ? s + 1 : s;
  *d = '\0';
  return d;
}

typedef struct output_context_st {
  jmp_buf *env;
  btri_desc_t *desc;
  ptrdiff_t off_count;
  const char *message_tag;
  const char *nodename;
  const char *format;
  char *(*str2key)(char *, btri_key_cursor_t *);
  void *(*str2val)(char **);
  void (*mkkeystr)(void *, int, const char *, FILE *);
  void *(*add_pair)(struct output_context_st *, char *, void *);
  FILE *fp;
} output_context_t;

enum {
  btri_error_nomem = 2,
  btri_error_bad_result,
  btri_error_syserror,
};

static char *bt_result_namev[] = {
  "bt_node",
  "bt_1",
  "bt_n",
  "bt_failure",
};

volatile void
ethrow(output_context_t *context, char *v[], int i, int err)
{
  if (context->env) {
    while (i > 0)
      if (v[--i])
      free(v[i]);

    longjmp(*context->env, err);
  }
  else {
    static char unknown_error[sizeof("unknown error ( == )") + sizeof(int) * CHAR_BIT / 3 + sizeof(int) * CHAR_BIT / 4]
      = "unknown error ";
    char *message = unknown_error;

    switch (err) {
    default:
      sprintf(&unknown_error[sizeof("unknown error ") - sizeof("")], "(%d == 0x%X)", err, err);
      break;
    case btri_error_nomem:
      message = "no memory";
      break;
    case btri_error_bad_result:
      message = "unknown node type";
      break;
    case btri_error_syserror:
      message = strerror(errno);
      break;
    }

    fprintf(stderr, "%s: %s\n", context->message_tag, message);
    exit(1);
  }
}

void *
add_one_pair(output_context_t *context, char *s, void *root)
{
  btri_key_cursor_t cursor;

  if (!root && !(root = btri_new_node(context->desc)))
    ethrow(context, NULL, 0, btri_error_nomem);

  if ((s = context->str2key(s, &cursor)) &&
      *(s = skip_space(s)) && *s == ',' && *(s = skip_space(s + 1))) {
    void *value;

    value = context->str2val ? context->str2val(&s) : s;

    if (btri_search(context->desc, BTRI_OP_ADD | BTRI_OP_WR, &cursor, root, &value) == bt_failure)
      ethrow(context, NULL, 0, btri_error_nomem);
  }

  return root;
}

char *
str2uintkey(char *s, btri_key_cursor_t *p)
{
  static unsigned int i;
  char *e;

  i = strtoul(s, &e, 0);

  if (s == e && *s == '\'') {
    if ((e = strchr(s + 1, '\'')))
      ++e;
    else
      e = s + strlen(s);

    i = (unsigned char)s[1];
  }

  p->base = &i;
  p->n = sizeof(unsigned int) * CHAR_BIT;
  return e;
}

void
mk_uint_keystr(void *p, int which, const char *f, FILE *fp)
{
  switch (which) {
  case 'n':
    fprintf(fp, f, *(char *)p);
    break;
  default:
    fprintf(fp, f, *(unsigned int *)p);
    break;
  }
}

void *
str2uintval(char **p_s)
{
  return (void *)strtoul(*p_s, p_s, 0);
}

void *
add_uint_pairs(output_context_t *context, char *s, void *root)
{
  char *ep;
  unsigned int b, e;

  if (!root && !(root = btri_new_node(context->desc)))
    ethrow(context, NULL, 0, btri_error_nomem);

  b = e = strtoul(s, &ep, 0);

  switch (*(s = skip_space(ep))) {
  case '-':
    e = strtoul(++s, &ep, 0);

    if (s == ep)
      e = UINT_MAX;

    if (*(s = skip_space(ep)) != ',')
      break;
  case ',':
    if (*(s = skip_space(s + 1))) {
      bt_result_t res;

      if (context->str2val) {
      void *value = context->str2val(&s);

      res = (*s == '-' ?
             btri_add_uint_n_to_n(context->desc, b, e, root, (unsigned int)value) :
             btri_add_uint_n_to_1(context->desc, b, e, root, value));
      }
      else
      res = btri_add_uint_n_to_1(context->desc, b, e, root, s);

      if (res == bt_failure)
      ethrow(context, NULL, 0, btri_error_nomem);
    }
  default:
    break;
  }

  return root;
}

typedef struct str_map_st {
  btri_string_tab_t tab;
  int count;
} str_map_t;

char *
str2strkey(char *s, btri_key_cursor_t *p)
{
  char *b, *e;

  b = s;
  e = read_string(&s, b);

  if (!e)
    return NULL;

  p->base = b;
  p->n = (e - b) * CHAR_BIT;
  return s;
}

void
mk_str_keystr(void *p, int which, const char *f, FILE *fp)
{
  switch (which) {
  case 'n':
    fprintf(fp, f, *(ptrdiff_t *)p);
    break;
  default:
    fprintf(fp, f, *(char **)p ? *(char **)p : "");
    break;
  }
}

static btri_desc_t str_ci_map = {
  offsetof(str_map_t, tab.pos),
  0,0,
  {offsetof(str_map_t, tab.type[0]), offsetof(str_map_t, tab.type[1])},
  {offsetof(str_map_t, tab.key[0].base), offsetof(str_map_t, tab.key[1].base)},
  {offsetof(str_map_t, tab.key[0].n), offsetof(str_map_t, tab.key[1].n)},
  {offsetof(str_map_t, tab.value[0]), offsetof(str_map_t, tab.value[1])},
  CHAR_BIT,
  btri_uchar_lower_filter,
  sizeof(str_map_t),
  btri_cmp,
  btri_key_fetch_cursor,
  btri_fetch_uchar_and_ci_cmp,
  btri_key_store_cursor,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

static btri_desc_t str_map = {
  offsetof(str_map_t, tab.pos),
  0,0,
  {offsetof(str_map_t, tab.type[0]), offsetof(str_map_t, tab.type[1])},
  {offsetof(str_map_t, tab.key[0].base), offsetof(str_map_t, tab.key[1].base)},
  {offsetof(str_map_t, tab.key[0].n), offsetof(str_map_t, tab.key[1].n)},
  {offsetof(str_map_t, tab.value[0]), offsetof(str_map_t, tab.value[1])},
  CHAR_BIT,
  btri_uchar_filter,
  sizeof(str_map_t),
  btri_cmp,
  btri_key_fetch_cursor,
  btri_fetch_uchar_and_cmp,
  btri_key_store_cursor,
  btri_malloc,
  btri_free_node,
  NULL,
  NULL,
  btri_free_key,
  btri_free_node,
};

#define EXPAND (256)

int
count_sub(output_context_t *context, void *node)
{
  btri_desc_t *desc;
  int count = 0;

  desc = context->desc;

  switch (*BTRI_O2P(bt_result_t *, node, desc->off_type[0])) {
  case bt_failure:
    goto end;
  case bt_node:
    count += count_sub(context, *BTRI_O2P(void **, node, desc->off_value[0])) + 1;
    break;
  default:
    ++count;
    break;
  }

  if (*BTRI_O2P(bt_result_t *, node, desc->off_type[1]) == bt_node)
    count += count_sub(context, *BTRI_O2P(void **, node, desc->off_value[1]));

  *BTRI_O2P(int *, node, context->off_count) = count;
end:
  return count;
}

void
output_btri(output_context_t *context, void *node, int count)
{
  btri_desc_t *desc;
  bt_result_t t[2];

  desc = context->desc;

  if ((t[0] = *BTRI_O2P(bt_result_t *, node, desc->off_type[0])) != bt_failure) {
    const char *nodename;
    const char *format;
    const char *s;
    const char *e;
    char *tobefreed[2] = {NULL, NULL}, *val[2], *tname[2];
    int nn_len, i, cv[2] = {0, 0};
    void *subv[2] = {NULL, NULL};

    nodename = context->nodename;
    format = context->format;
    nn_len = strlen(nodename);
    t[1] = *BTRI_O2P(bt_result_t *, node, desc->off_type[1]);
    ++count;

    for (i = 0 ; i < sizeof(val) / sizeof(val[0]) ; ++i) {
      if (t[i] <= sizeof(bt_result_namev) / sizeof(bt_result_namev[0]))
      tname[i] = bt_result_namev[t[i]];
      else
      ethrow(context, tobefreed, i, btri_error_bad_result);

      if (t[i] == bt_node) {
      char index[(sizeof(int) * CHAR_BIT) / 3 + sizeof("[]")];
      int n = sprintf(index, "[%d]", count);

      subv[i] = *BTRI_O2P(void **, node, desc->off_value[i]);

      if ((val[i] = malloc(sizeof("&") + nn_len + n))) {
        memcpy(val[i], "&", sizeof("&") - 1);
        memcpy(val[i] + sizeof("&") - 1, nodename, nn_len);
        memcpy(val[i] + sizeof("&") - 1 + nn_len, index, n + 1);
        tobefreed[i] = val[i];
        cv[i] = count;
        count += *BTRI_O2P(int *, subv[i], context->off_count);
      }
      else
        ethrow(context, tobefreed, i, btri_error_nomem);
      }
      else {
      val[i] = *BTRI_O2P(char **, node, desc->off_value[i]);
      if (!val[i]) val[i] = "NULL";
      }
    }

    for (; (s = strchr(format, '%')) ;) {
      if (format < s)
      fwrite(format, 1, s - format, context->fp);

      if ((e = strchr(++s, '%'))) {
      int i = 0;
      static char *f = NULL;
      static int size = 0;

      switch (*s) {
      case 'r':
        i = 1;
      case 'l':
        ++s;
        break;
      default:
        break;
      }

      if (size < e - s) {
        int nsize;
        char *nf;

        nsize = ((e - s + 1) / EXPAND + 1) * EXPAND;
        nf = f ? realloc(f, nsize) : malloc(nsize);

        if (!nf) {
          free(f);
          ethrow(context, tobefreed, 2, btri_error_nomem);
        }

        f = nf;
        size = nsize;
      }

      *f = '%';
      memcpy(f + 1, s + 1, e - s - 1);
      f[e - s] = '\0';

      switch (*s) {
      case 'p':
        fprintf(context->fp, f, (int)*BTRI_O2P(ptrdiff_t *, node, desc->off_pos));
        break;
      case 't':
        fprintf(context->fp, f, tname[i]);
        break;
      case 'k':
        context->mkkeystr(BTRI_O2P(void *, node, desc->off_key[i]), *s, f, context->fp);
        break;
      case 'n':
        context->mkkeystr(BTRI_O2P(void *, node, desc->off_key_n[i]), *s, f, context->fp);
        break;
      case 'v':
        fprintf(context->fp, f, val[i]);
      default:
        break;
      }

      format = e + 1;
      }
      else {
      putc('%', context->fp);
      ++format;
      }
    }

    if (*format)
      fputs(format, context->fp);

    for (i = 0 ; i < sizeof(subv) / sizeof(subv[0]) ; ++i)
      if (subv[i])
      output_btri(context, subv[i], cv[i]);

    for (i = 0 ; i < sizeof(tobefreed) / sizeof(tobefreed[0]) ; ++i)
      if (tobefreed[i])
      free(tobefreed[i]);
  }
}

void
output_bt(output_context_t *context, void *node, unsigned int id)
{
  btri_desc_t *desc;
  bt_result_t t[2];

  desc = context->desc;
loop:
  if ((t[0] = *BTRI_O2P(bt_result_t *, node, desc->off_type[0])) != bt_failure) {
    FILE *fp;
    void *subv[2];
    unsigned int uibuf[2], lcount = 0, *v, k;
    int i, n;

    fp = context->fp;
    subv[0] = *BTRI_O2P(void **, node, desc->off_value[0]);
    subv[1] = *BTRI_O2P(void **, node, desc->off_value[1]);
    t[1] = *BTRI_O2P(bt_result_t *, node, desc->off_type[1]);

    if (t[0] == bt_node)
      lcount = *BTRI_O2P(unsigned int *, subv[0], desc->off_count);

    n = bt_enc(node, lcount, uibuf);

    for (i = 0 ; i < n ; ++i)
      fprintf(fp, "0x%X,/*N%x*/\n", uibuf[i], id);

    for (i = 0 ; i < sizeof(t) / sizeof(t[0]) ; ++i) {
      unsigned int key = *BTRI_O2P(unsigned int *, node, desc->off_key[i]);

      switch (t[i]) {
      case bt_node:
      if (i) {
        node = subv[i];
        id = id * 2 + i;
        goto loop;
      }

      output_bt(context, subv[i], id * 2 + i);
      break;
      case bt_1:
      case bt_n:
      fprintf(fp, "0x%X,/*K%x*/\n%uU,\n", key, id * 2 + i, (unsigned int)subv[i]);
      break;
      case bt_v:
      fprintf(fp, "0x%X,/*K%x*/\n", key, id * 2 + i);
      v = subv[i];
      n = *v++;
      fprintf(fp, "%uU,/*V%x-n*/\n", n, id * 2 + i);

      for (k = 0 ; k < n ;)
        fprintf(fp, "%uU,/*V%x-%d*/\n", *v++, id * 2 + i, k++);

      break;
      default:
      break;
      }
    }
  }
}

void
close_btri(output_context_t *context, void **root)
{
  if (*context->nodename) {
    count_sub(context, *root);
    output_btri(context, *root, 0);
  }
  else {
    bt_result_t t;
    char e;
    unsigned int count, max = 0U;

    btri_uint_optimize(context->desc, *root, &t, &e, &count, &max, 2);
    output_bt(context, *root, 1U);
  }

  *root = NULL;
  context->desc = &str_ci_map;
  context->off_count = offsetof(str_map_t, count);
  context->format = context->nodename = NULL;
  context->str2key = str2strkey;
  context->str2val = NULL;
  context->mkkeystr = mk_str_keystr;
  context->add_pair = add_one_pair;
}

#define CASE_SENSITIVE (1U << 0)

int
main(int argc, char *argv[])
{
  output_context_t context = {
    NULL,
    &str_ci_map,
    offsetof(str_map_t, count),
    NULL,
    NULL,
    NULL,
    str2strkey,
    NULL,
    mk_str_keystr,
    add_one_pair,
    NULL,
  };
  char *buf = NULL, *s, *e;
  int n, eol = 0, sob = 0, sensitive;
  void *root = NULL;

  context.message_tag = argv[0];
  context.fp = stdout;

  if (argc > 1 && !strcmp(argv[1], "-?")) {
    printf("%d\n", CASE_SENSITIVE);
    exit(0);
  }

  for (;;) {
    if (sob - eol < EXPAND) {
      int newsize;
      char *new;

      newsize = (eol / EXPAND + 1) * EXPAND;

      if (!(new = buf ? realloc(buf, newsize) : malloc(newsize)))
      ethrow(&context, NULL, 0, btri_error_nomem);

      buf = new;
      sob = newsize;
    }

    if (!fgets(&buf[eol], sob - eol, stdin))
      break;

    n = strcspn(&buf[eol], "\n");
    eol += n;

    if (buf[eol] == '\n')
      buf[eol] = '\0';
    else if (n > 0)
      continue;
    else
      break;

    eol = sensitive = 0;

    if (!*(s = skip_space(buf)))
      continue;
    else if (*s == '#')
      fprintf(context.fp, "%s\n", buf);
    else if (!context.nodename &&
           (!strncmp(s, "%%BEGIN", sizeof("%%BEGIN") - 1) ||
            (sensitive = !strncmp(s, "%%begin", sizeof("%%begin") - 1)))) {
      s += sizeof("%%BEGIN") - 1;
      if (*s && !isspace(*s)) continue;
      if (root) close_btri(&context, &root);
      if (sensitive) context.desc = &str_map;

      if (*s) {
      s = skip_space(s);
      if (!(e = read_string(&s, buf))) continue;
      context.nodename = buf;

      if (*(s = skip_space(s)) && read_string(&s, ++e))
        context.format = e;
      else if (*context.nodename)
        context.format = "{%pd%,{%lts%,%rts%},{{\"%lks%\",%lnd%},{\"%rks%\",%rnd%}},{%lvs%,%rvs%}},\n";
      else
        context.format = "";
      }
      else
      context.nodename = context.format = "";

      if (!*context.nodename) {
      context.str2val = str2uintval;
      context.format = "";
      }

      buf = NULL;
      sob = 0;
    }
    else if (context.nodename) {
      if ((!strncmp(s, "%%END", sizeof("%%END") - 1) || !strncmp(s, "%%end", sizeof("%%end") - 1))
        && !*skip_space(s + sizeof("%%END") - 1)) {
      if (root) close_btri(&context, &root);
      }
      else {
      root = context.add_pair(&context, s, root);
      buf = NULL;
      sob = 0;
      }
    }
    else if (!strncmp(s, "%%TYPE", sizeof("%%TYPE") - 1)) {
      s += sizeof("%%TYPE") - 1;
      if (!*s || !isspace(*s)) continue;
      if (!(e = read_string(&s, buf))) continue;

      switch (tolower(*buf)) {
      case 'n':
      case 'i':
      context.desc = &btri_uint_opt_tab_desc;
      context.str2key = str2uintkey;
      context.mkkeystr = mk_uint_keystr;
      context.add_pair = add_uint_pairs;
      break;
      case 'u':
      context.desc = &btri_uint_tab_desc;
      context.str2key = str2uintkey;
      context.mkkeystr = mk_uint_keystr;
      context.add_pair = add_one_pair;
      break;
      default:
      break;
      }

      buf = NULL;
      sob = 0;
    }
    else
      fprintf(context.fp, "%s\n", buf);
  }

  if (root)
    close_btri(&context, &root);

  return 0;
}

#endif

Generated by  Doxygen 1.6.0   Back to index