tree234.c

NullSofts criptable install system2.28源代码

  assert(!left->elems[2] && !right->elems[2]);  /* neither is large! */
  lsize = (left->elems[1] ? 2 : left->elems[0] ? 1 : 0);
  rsize = (right->elems[1] ? 2 : right->elems[0] ? 1 : 0);

  left->elems[lsize] = n->elems[ki];

  for (i = 0; i < rsize + 1; i++)
  {
    left->kids[lsize + 1 + i] = right->kids[i];
    left->counts[lsize + 1 + i] = right->counts[i];
    if (left->kids[lsize + 1 + i])
      left->kids[lsize + 1 + i]->parent = left;
    if (i < rsize)
      left->elems[lsize + 1 + i] = right->elems[i];
  }

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

  sfree(right);

  /*
   * Move the rest of n up by one.
   */
  for (i = ki + 1; i < 3; i++)
  {
    n->kids[i] = n->kids[i + 1];
    n->counts[i] = n->counts[i + 1];
  }
  for (i = ki; i < 2; i++)
  {
    n->elems[i] = n->elems[i + 1];
  }
  n->kids[3] = NULL;
  n->counts[3] = 0;
  n->elems[2] = NULL;

  if (k)
  {
    LOG(("    before: k,index = %d,%d\n", (*k), (*index)));
    if ((*k) == ki + 1)
    {
      (*k)--;
      (*index) += leftlen + 1;
    } else if ((*k) > ki + 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(("    merged %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]));

}

/*
 * Delete an element e in a 2-3-4 tree. Does not free the element,
 * merely removes all links to it from the tree nodes.
 */
static void *delpos234_internal(tree234 * t, int index)
{
  node234 *n;
  void *retval;
  int ki, i;

  retval = NULL;

  n = t->root;                  /* by assumption this is non-NULL */
  LOG(("deleting item %d from tree %p\n", index, t));
  while (1)
  {
    node234 *sub;

    LOG(("  node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%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], index));
    if (index <= n->counts[0])
    {
      ki = 0;
    } else if (index -= n->counts[0] + 1, index <= n->counts[1])
    {
      ki = 1;
    } else if (index -= n->counts[1] + 1, index <= n->counts[2])
    {
      ki = 2;
    } else if (index -= n->counts[2] + 1, index <= n->counts[3])
    {
      ki = 3;
    } else
    {
      assert(0);                /* can't happen */
    }

    if (!n->kids[0])
      break;                    /* n is a leaf node; we're here! */

    /*
     * Check to see if we've found our target element. If so,
     * we must choose a new target (we'll use the old target's
     * successor, which will be in a leaf), move it into the
     * place of the old one, continue down to the leaf and
     * delete the old copy of the new target.
     */
    if (index == n->counts[ki])
    {
      node234 *m;
      LOG(("  found element in internal node, index %d\n", ki));
      assert(n->elems[ki]);     /* must be a kid _before_ an element */
      ki++;
      index = 0;
      for (m = n->kids[ki]; m->kids[0]; m = m->kids[0])
        continue;
      LOG(("  replacing with element \"%s\" from leaf node %p\n",
           m->elems[0], m));
      retval = n->elems[ki - 1];
      n->elems[ki - 1] = m->elems[0];
    }

    /*
     * Recurse down to subtree ki. If it has only one element,
     * we have to do some transformation to start with.
     */
    LOG(("  moving to subtree %d\n", ki));
    sub = n->kids[ki];
    if (!sub->elems[1])
    {
      LOG(("  subtree has only one element!\n"));
      if (ki > 0 && n->kids[ki - 1]->elems[1])
      {
        /*
         * Child ki has only one element, but child
         * ki-1 has two or more. So we need to move a
         * subtree from ki-1 to ki.
         */
        trans234_subtree_right(n, ki - 1, &ki, &index);
      } else if (ki < 3 && n->kids[ki + 1] && n->kids[ki + 1]->elems[1])
      {
        /*
         * Child ki has only one element, but ki+1 has
         * two or more. Move a subtree from ki+1 to ki.
         */
        trans234_subtree_left(n, ki + 1, &ki, &index);
      } else
      {
        /*
         * ki is small with only small neighbours. Pick a
         * neighbour and merge with it.
         */
        trans234_subtree_merge(n, ki > 0 ? ki - 1 : ki, &ki, &index);
        sub = n->kids[ki];

        if (!n->elems[0])
        {
          /*
           * The root is empty and needs to be
           * removed.
           */
          LOG(("  shifting root!\n"));
          t->root = sub;
          sub->parent = NULL;
          sfree(n);
          n = NULL;
        }
      }
    }

    if (n)
      n->counts[ki]--;
    n = sub;
  }

  /*
   * Now n is a leaf node, and ki marks the element number we
   * want to delete. We've already arranged for the leaf to be
   * bigger than minimum size, so let's just go to it.
   */
  assert(!n->kids[0]);
  if (!retval)
    retval = n->elems[ki];

  for (i = ki; i < 2 && n->elems[i + 1]; i++)
    n->elems[i] = n->elems[i + 1];
  n->elems[i] = NULL;

  /*
   * It's just possible that we have reduced the leaf to zero
   * size. This can only happen if it was the root - so destroy
   * it and make the tree empty.
   */
  if (!n->elems[0])
  {
    LOG(("  removed last element in tree, destroying empty root\n"));
    assert(n == t->root);
    sfree(n);
    t->root = NULL;
  }

  return retval;                /* finished! */
}

void *delpos234(tree234 * t, int index)
{
  if (index < 0 || index >= countnode234(t->root))
    return NULL;
  return delpos234_internal(t, index);
}

void *del234(tree234 * t, void *e)
{
  int index;
  if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
    return NULL;                /* it wasn't in there anyway */
  return delpos234_internal(t, index);  /* it's there; delete it. */
}

/*
 * Join two subtrees together with a separator element between
 * them, given their relative height.
 * 
 * (Height<0 means the left tree is shorter, >0 means the right
 * tree is shorter, =0 means (duh) they're equal.)
 * 
 * It is assumed that any checks needed on the ordering criterion
 * have _already_ been done.
 * 
 * The value returned in `height' is 0 or 1 depending on whether the
 * resulting tree is the same height as the original larger one, or
 * one higher.
 */
static node234 *join234_internal(node234 * left, void *sep,
                                 node234 * right, int *height)
{
  node234 *root, *node;
  int relht = *height;
  int ki;

  LOG(("  join: joining %p \"%s\" %p, relative height is %d\n",
       left, sep, right, relht));
  if (relht == 0)
  {
    /*
     * The trees are the same height. Create a new one-element
     * root containing the separator and pointers to the two
     * nodes.
     */
    node234 *newroot;
    newroot = mknew(node234);
    newroot->kids[0] = left;
    newroot->counts[0] = countnode234(left);
    newroot->elems[0] = sep;
    newroot->kids[1] = right;
    newroot->counts[1] = countnode234(right);
    newroot->elems[1] = NULL;
    newroot->kids[2] = NULL;
    newroot->counts[2] = 0;
    newroot->elems[2] = NULL;
    newroot->kids[3] = NULL;
    newroot->counts[3] = 0;
    newroot->parent = NULL;
    if (left)
      left->parent = newroot;
    if (right)
      right->parent = newroot;
    *height = 1;
    LOG(("  join: same height, brand new root\n"));
    return newroot;
  }

  /*
   * This now works like the addition algorithm on the larger
   * tree. We're replacing a single kid pointer with two kid
   * pointers separated by an element; if that causes the node to
   * overload, we split it in two, move a separator element up to
   * the next node, and repeat.
   */
  if (relht < 0)
  {
    /*
     * Left tree is shorter. Search down the right tree to find
     * the pointer we're inserting at.
     */
    node = root = right;
    while (++relht < 0)
    {
      node = node->kids[0];
    }
    ki = 0;
    right = node->kids[ki];
  } else
  {
    /*
     * Right tree is shorter; search down the left to find the
     * pointer we're inserting at.
     */
    node = root = left;
    while (--relht > 0)
    {
      if (node->elems[2])
        node = node->kids[3];
      else if (node->elems[1])
        node = node->kids[2];
      else
        node = node->kids[1];
    }
    if (node->elems[2])
      ki = 3;
    else if (node->elems[1])
      ki = 2;
    else
      ki = 1;
    left = node->kids[ki];
  }

  /*
   * Now proceed as for addition.
   */
  *height = add234_insert(left, sep, right, &root, node, ki);

  return root;
}
static int height234(tree234 * t)
{
  int level = 0;
  node234 *n = t->root;
  while (n)
  {
    level++;
    n = n->kids[0];
  }
  return level;
}

tree234 *join234(tree234 * t1, tree234 * t2)
{
  int size2 = countnode234(t2->root);
  if (size2 > 0)
  {
    void *element;
    int relht;

    if (t1->cmp)
    {
      element = index234(t2, 0);
      element = findrelpos234(t1, element, NULL, REL234_GE, NULL);
      if (element)
        return NULL;
    }

    element = delpos234(t2, 0);
    relht = height234(t1) - height234(t2);
    t1->root = join234_internal(t1->root, element, t2->root, &relht);
    t2->root = NULL;
  }
  return t1;
}

tree234 *join234r(tree234 * t1, tree234 * t2)
{
  int size1 = countnode234(t1->root);
  if (size1 > 0)
  {
    void *element;
    int relht;

    if (t2->cmp)
    {
      element = index234(t1, size1 - 1);
      element = findrelpos234(t2, element, NULL, REL234_LE, NULL);
      if (element)
        return NULL;
    }

    element = delpos234(t1, size1 - 1);
    relht = height234(t1) - height234(t2);
    t2->root = join234_internal(t1->root, element, t2->root, &relht);
    t1->root = NULL;
  }
  return t2;
}

/*
 * Split out the first <index> elements in a tree and return a
 * pointer to the root node. Leave the root node of the remainder
 * in t.
 */
static node234 *split234_internal(tree234 * t, int index)
{
  node234 *halves[2], *n, *sib, *sub;
  node234 *lparent, *rparent;
  int ki, pki=0, i, half, lcount, rcount;

  n = t->root;
  LOG(("splitting tree %p at point %d\n", t, index));

  /*
   * Easy special cases. After this we have also dealt completely
   * with the empty-tree case and we can assume the root exists.
   */
  if (index == 0)               /* return nothing */
    return NULL;
  if (index == countnode234(t->root))
  {                             /* return the whole tree */
    node234 *ret = t->root;
    t->root = NULL;
    return ret;
  }

  /*
   * Search down the tree to find the split point.
   */
  lparent = rparent = NULL;
  while (n)
  {
    LOG(("  node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%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], index));
    lcount = index;
    rcount = countnode234(n) - lcount;
    if (index <= n->counts[0])
    {
      ki = 0;
    } else if (index -= n->counts[0] + 1, index <= n->counts[1])
    {
      ki = 1;
    } else if (index -= n->counts[1] + 1, index <= n->counts[2])
    {
      ki = 2;
    } else
    {
      index -= n->counts[2] + 1;
      ki = 3;
    }

    LOG(("  splitting at subtree %d\n", ki));
    sub = n->kids[ki];

    LOG(("  splitting at child index %d\n", ki));

    /*
     * Split the node, put halves[0] on the right of the left
     * one and halves[1] on the left of the right one, put the
     * new node pointers in halves[0] and halves[1], and go up
     * a level.
     */
    sib = mknew(node234);
    for (i = 0; i < 3; i++)
    {
      if (i + ki < 3 && n->elems[i + ki])
      {
        sib->elems[i] = n->elems[i + ki];
        sib->kids[i + 1] = n->kids[i + ki + 1];
        if (sib->kids[i + 1])
          sib->kids[i + 1]->parent = sib;
        sib->counts[i + 1] = n->counts[i + ki + 1];
        n->elems[i + ki] = NULL;
        n->kids[i + ki + 1] = NULL;
        n->counts[i + ki + 1] = 0;
      } else
      {
        sib->elems[i] = NULL;
        sib->kids[i + 1] = NULL;