tree234.c

NullSofts criptable install system2.28源代码

  }

  add234_insert(NULL, e, NULL, &t->root, n, ki);

  return orig_e;
}

void *add234(tree234 * t, void *e)
{
  if (!t->cmp)                  /* tree is unsorted */
    return NULL;

  return add234_internal(t, e, -1);
}

void *addpos234(tree234 * t, void *e, int index)
{
  if (index < 0 ||              /* index out of range */
      t->cmp)                   /* tree is sorted */
    return NULL;                /* return failure */

  return add234_internal(t, e, index);  /* this checks the upper bound */
}

/*
 * Look up the element at a given numeric index in a 2-3-4 tree.
 * Returns NULL if the index is out of range.
 */
void *index234(tree234 * t, int index)
{
  node234 *n;

  if (!t->root)
    return NULL;                /* tree is empty */

  if (index < 0 || index >= countnode234(t->root))
    return NULL;                /* out of range */

  n = t->root;

  while (n)
  {
    if (index < n->counts[0])
      n = n->kids[0];
    else if (index -= n->counts[0] + 1, index < 0)
      return n->elems[0];
    else if (index < n->counts[1])
      n = n->kids[1];
    else if (index -= n->counts[1] + 1, index < 0)
      return n->elems[1];
    else if (index < n->counts[2])
      n = n->kids[2];
    else if (index -= n->counts[2] + 1, index < 0)
      return n->elems[2];
    else
      n = n->kids[3];
  }

  /* We shouldn't ever get here. I wonder how we did. */
  return NULL;
}

/*
 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
 * found. e is always passed as the first argument to cmp, so cmp
 * can be an asymmetric function if desired. cmp can also be passed
 * as NULL, in which case the compare function from the tree proper
 * will be used.
 */
void *findrelpos234(tree234 * t, void *e, cmpfn234 cmp, int relation,
                    int *index)
{
  node234 *n;
  void *ret;
  int c;
  int idx, ecount, kcount, cmpret;

  if (t->root == NULL)
    return NULL;

  if (cmp == NULL)
    cmp = t->cmp;

  n = t->root;
  /*
   * Attempt to find the element itself.
   */
  idx = 0;
  ecount = -1;
  /*
   * Prepare a fake `cmp' result if e is NULL.
   */
  cmpret = 0;
  if (e == NULL)
  {
    assert(relation == REL234_LT || relation == REL234_GT);
    if (relation == REL234_LT)
      cmpret = +1;              /* e is a max: always greater */
    else if (relation == REL234_GT)
      cmpret = -1;              /* e is a min: always smaller */
  }
  while (1)
  {
    for (kcount = 0; kcount < 4; kcount++)
    {
      if (kcount >= 3 || n->elems[kcount] == NULL ||
          (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0)
      {
        break;
      }
      if (n->kids[kcount])
        idx += n->counts[kcount];
      if (c == 0)
      {
        ecount = kcount;
        break;
      }
      idx++;
    }
    if (ecount >= 0)
      break;
    if (n->kids[kcount])
      n = n->kids[kcount];
    else
      break;
  }

  if (ecount >= 0)
  {
    /*
     * We have found the element we're looking for. It's
     * n->elems[ecount], at tree index idx. If our search
     * relation is EQ, LE or GE we can now go home.
     */
    if (relation != REL234_LT && relation != REL234_GT)
    {
      if (index)
        *index = idx;
      return n->elems[ecount];
    }

    /*
     * Otherwise, we'll do an indexed lookup for the previous
     * or next element. (It would be perfectly possible to
     * implement these search types in a non-counted tree by
     * going back up from where we are, but far more fiddly.)
     */
    if (relation == REL234_LT)
      idx--;
    else
      idx++;
  } else
  {
    /*
     * We've found our way to the bottom of the tree and we
     * know where we would insert this node if we wanted to:
     * we'd put it in in place of the (empty) subtree
     * n->kids[kcount], and it would have index idx
     * 
     * But the actual element isn't there. So if our search
     * relation is EQ, we're doomed.
     */
    if (relation == REL234_EQ)
      return NULL;

    /*
     * Otherwise, we must do an index lookup for index idx-1
     * (if we're going left - LE or LT) or index idx (if we're
     * going right - GE or GT).
     */
    if (relation == REL234_LT || relation == REL234_LE)
    {
      idx--;
    }
  }

  /*
   * We know the index of the element we want; just call index234
   * to do the rest. This will return NULL if the index is out of
   * bounds, which is exactly what we want.
   */
  ret = index234(t, idx);
  if (ret && index)
    *index = idx;
  return ret;
}

void *find234(tree234 * t, void *e, cmpfn234 cmp)
{
  return findrelpos234(t, e, cmp, REL234_EQ, NULL);
}

void *findrel234(tree234 * t, void *e, cmpfn234 cmp, int relation)
{
  return findrelpos234(t, e, cmp, relation, NULL);
}

void *findpos234(tree234 * t, void *e, cmpfn234 cmp, int *index)
{
  return findrelpos234(t, e, cmp, REL234_EQ, index);
}

/*
 * Tree transformation used in delete and split: move a subtree
 * right, from child ki of a node to the next child. Update k and
 * index so that they still point to the same place in the
 * transformed tree. Assumes the destination child is not full, and
 * that the source child does have a subtree to spare. Can cope if
 * the destination child is undersized.
 * 
 *                . C .                     . B .
 *               /     \     ->            /     \
 * [more] a A b B c   d D e      [more] a A b   c C d D e
 * 
 *                 . C .                     . B .
 *                /     \    ->             /     \
 *  [more] a A b B c     d        [more] a A b   c C d
 */
static void trans234_subtree_right(node234 * n, int ki, int *k, int *index)
{
  node234 *src, *dest;
  int i, srclen, adjust;

  src = n->kids[ki];
  dest = n->kids[ki + 1];

  LOG(("  trans234_subtree_right(%p, %d):\n", n, ki));
  LOG(("    parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       n,
       n->kids[0], n->counts[0], n->elems[0],
       n->kids[1], n->counts[1], n->elems[1],
       n->kids[2], n->counts[2], n->elems[2], n->kids[3], n->counts[3]));
  LOG(("    src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       src,
       src->kids[0], src->counts[0], src->elems[0],
       src->kids[1], src->counts[1], src->elems[1],
       src->kids[2], src->counts[2], src->elems[2],
       src->kids[3], src->counts[3]));
  LOG(("    dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       dest,
       dest->kids[0], dest->counts[0], dest->elems[0],
       dest->kids[1], dest->counts[1], dest->elems[1],
       dest->kids[2], dest->counts[2], dest->elems[2],
       dest->kids[3], dest->counts[3]));
  /*
   * Move over the rest of the destination node to make space.
   */
  dest->kids[3] = dest->kids[2];
  dest->counts[3] = dest->counts[2];
  dest->elems[2] = dest->elems[1];
  dest->kids[2] = dest->kids[1];
  dest->counts[2] = dest->counts[1];
  dest->elems[1] = dest->elems[0];
  dest->kids[1] = dest->kids[0];
  dest->counts[1] = dest->counts[0];

  /* which element to move over */
  i = (src->elems[2] ? 2 : src->elems[1] ? 1 : 0);

  dest->elems[0] = n->elems[ki];
  n->elems[ki] = src->elems[i];
  src->elems[i] = NULL;

  dest->kids[0] = src->kids[i + 1];
  dest->counts[0] = src->counts[i + 1];
  src->kids[i + 1] = NULL;
  src->counts[i + 1] = 0;

  if (dest->kids[0])
    dest->kids[0]->parent = dest;

  adjust = dest->counts[0] + 1;

  n->counts[ki] -= adjust;
  n->counts[ki + 1] += adjust;

  srclen = n->counts[ki];

  if (k)
  {
    LOG(("    before: k,index = %d,%d\n", (*k), (*index)));
    if ((*k) == ki && (*index) > srclen)
    {
      (*index) -= srclen + 1;
      (*k)++;
    } else if ((*k) == ki + 1)
    {
      (*index) += adjust;
    }
    LOG(("    after: k,index = %d,%d\n", (*k), (*index)));
  }

  LOG(("    parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       n,
       n->kids[0], n->counts[0], n->elems[0],
       n->kids[1], n->counts[1], n->elems[1],
       n->kids[2], n->counts[2], n->elems[2], n->kids[3], n->counts[3]));
  LOG(("    src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       src,
       src->kids[0], src->counts[0], src->elems[0],
       src->kids[1], src->counts[1], src->elems[1],
       src->kids[2], src->counts[2], src->elems[2],
       src->kids[3], src->counts[3]));
  LOG(("    dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       dest,
       dest->kids[0], dest->counts[0], dest->elems[0],
       dest->kids[1], dest->counts[1], dest->elems[1],
       dest->kids[2], dest->counts[2], dest->elems[2],
       dest->kids[3], dest->counts[3]));
}

/*
 * Tree transformation used in delete and split: move a subtree
 * left, from child ki of a node to the previous child. Update k
 * and index so that they still point to the same place in the
 * transformed tree. Assumes the destination child is not full, and
 * that the source child does have a subtree to spare. Can cope if
 * the destination child is undersized. 
 *
 *      . B .                             . C .
 *     /     \                ->         /     \
 *  a A b   c C d D e [more]      a A b B c   d D e [more]
 *
 *     . A .                             . B .
 *    /     \                 ->        /     \
 *   a   b B c C d [more]            a A b   c C d [more]
 */
static void trans234_subtree_left(node234 * n, int ki, int *k, int *index)
{
  node234 *src, *dest;
  int i, adjust;

  src = n->kids[ki];
  dest = n->kids[ki - 1];

  LOG(("  trans234_subtree_left(%p, %d):\n", n, ki));
  LOG(("    parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       n,
       n->kids[0], n->counts[0], n->elems[0],
       n->kids[1], n->counts[1], n->elems[1],
       n->kids[2], n->counts[2], n->elems[2], n->kids[3], n->counts[3]));
  LOG(("    dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       dest,
       dest->kids[0], dest->counts[0], dest->elems[0],
       dest->kids[1], dest->counts[1], dest->elems[1],
       dest->kids[2], dest->counts[2], dest->elems[2],
       dest->kids[3], dest->counts[3]));
  LOG(("    src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       src,
       src->kids[0], src->counts[0], src->elems[0],
       src->kids[1], src->counts[1], src->elems[1],
       src->kids[2], src->counts[2], src->elems[2],
       src->kids[3], src->counts[3]));

  /* where in dest to put it */
  i = (dest->elems[1] ? 2 : dest->elems[0] ? 1 : 0);
  dest->elems[i] = n->elems[ki - 1];
  n->elems[ki - 1] = src->elems[0];

  dest->kids[i + 1] = src->kids[0];
  dest->counts[i + 1] = src->counts[0];

  if (dest->kids[i + 1])
    dest->kids[i + 1]->parent = dest;

  /*
   * Move over the rest of the source node.
   */
  src->kids[0] = src->kids[1];
  src->counts[0] = src->counts[1];
  src->elems[0] = src->elems[1];
  src->kids[1] = src->kids[2];
  src->counts[1] = src->counts[2];
  src->elems[1] = src->elems[2];
  src->kids[2] = src->kids[3];
  src->counts[2] = src->counts[3];
  src->elems[2] = NULL;
  src->kids[3] = NULL;
  src->counts[3] = 0;

  adjust = dest->counts[i + 1] + 1;

  n->counts[ki] -= adjust;
  n->counts[ki - 1] += adjust;

  if (k)
  {
    LOG(("    before: k,index = %d,%d\n", (*k), (*index)));
    if ((*k) == ki)
    {
      (*index) -= adjust;
      if ((*index) < 0)
      {
        (*index) += n->counts[ki - 1] + 1;
        (*k)--;
      }
    }
    LOG(("    after: k,index = %d,%d\n", (*k), (*index)));
  }

  LOG(("    parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       n,
       n->kids[0], n->counts[0], n->elems[0],
       n->kids[1], n->counts[1], n->elems[1],
       n->kids[2], n->counts[2], n->elems[2], n->kids[3], n->counts[3]));
  LOG(("    dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       dest,
       dest->kids[0], dest->counts[0], dest->elems[0],
       dest->kids[1], dest->counts[1], dest->elems[1],
       dest->kids[2], dest->counts[2], dest->elems[2],
       dest->kids[3], dest->counts[3]));
  LOG(("    src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       src,
       src->kids[0], src->counts[0], src->elems[0],
       src->kids[1], src->counts[1], src->elems[1],
       src->kids[2], src->counts[2], src->elems[2],
       src->kids[3], src->counts[3]));
}

/*
 * Tree transformation used in delete and split: merge child nodes
 * ki and ki+1 of a node. Update k and index so that they still
 * point to the same place in the transformed tree. Assumes both
 * children _are_ sufficiently small.
 *
 *      . B .                .
 *     /     \     ->        |
 *  a A b   c C d      a A b B c C d
 * 
 * This routine can also cope with either child being undersized:
 * 
 *     . A .                 .
 *    /     \      ->        |
 *   a     b B c         a A b B c
 *
 *    . A .                  .
 *   /     \       ->        |
 *  a   b B c C d      a A b B c C d
 */
static void trans234_subtree_merge(node234 * n, int ki, int *k, int *index)
{
  node234 *left, *right;
  int i, leftlen, rightlen, lsize, rsize;

  left = n->kids[ki];
  leftlen = n->counts[ki];
  right = n->kids[ki + 1];
  rightlen = n->counts[ki + 1];

  LOG(("  trans234_subtree_merge(%p, %d):\n", n, ki));
  LOG(("    parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       n,
       n->kids[0], n->counts[0], n->elems[0],
       n->kids[1], n->counts[1], n->elems[1],
       n->kids[2], n->counts[2], n->elems[2], n->kids[3], n->counts[3]));
  LOG(("    left %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       left,
       left->kids[0], left->counts[0], left->elems[0],
       left->kids[1], left->counts[1], left->elems[1],
       left->kids[2], left->counts[2], left->elems[2],
       left->kids[3], left->counts[3]));
  LOG(("    right %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
       right,
       right->kids[0], right->counts[0], right->elems[0],
       right->kids[1], right->counts[1], right->elems[1],
       right->kids[2], right->counts[2], right->elems[2],
       right->kids[3], right->counts[3]));