tree234.c

NullSofts criptable install system2.28源代码

        sib->counts[i + 1] = 0;
      }
    }
    if (lparent)
    {
      lparent->kids[pki] = n;
      lparent->counts[pki] = lcount;
      n->parent = lparent;
      rparent->kids[0] = sib;
      rparent->counts[0] = rcount;
      sib->parent = rparent;
    } else
    {
      halves[0] = n;
      n->parent = NULL;
      halves[1] = sib;
      sib->parent = NULL;
    }
    lparent = n;
    rparent = sib;
    pki = ki;
    LOG(("  left node %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(("  right node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
         sib, sib->kids[0], sib->counts[0], sib->elems[0], sib->kids[1],
         sib->counts[1], sib->elems[1], sib->kids[2], sib->counts[2],
         sib->elems[2], sib->kids[3], sib->counts[3]));

    n = sub;
  }

  /*
   * We've come off the bottom here, so we've successfully split
   * the tree into two equally high subtrees. The only problem is
   * that some of the nodes down the fault line will be smaller
   * than the minimum permitted size. (Since this is a 2-3-4
   * tree, that means they'll be zero-element one-child nodes.)
   */
  LOG(("  fell off bottom, lroot is %p, rroot is %p\n",
       halves[0], halves[1]));
  lparent->counts[pki] = rparent->counts[0] = 0;
  lparent->kids[pki] = rparent->kids[0] = NULL;

  /*
   * So now we go back down the tree from each of the two roots,
   * fixing up undersize nodes.
   */
  for (half = 0; half < 2; half++)
  {
    /*
     * Remove the root if it's undersize (it will contain only
     * one child pointer, so just throw it away and replace it
     * with its child). This might happen several times.
     */
    while (halves[half] && !halves[half]->elems[0])
    {
      LOG(("  root %p is undersize, throwing away\n", halves[half]));
      halves[half] = halves[half]->kids[0];
      sfree(halves[half]->parent);
      halves[half]->parent = NULL;
      LOG(("  new root is %p\n", halves[half]));
    }

    n = halves[half];
    while (n)
    {
      void (*toward) (node234 * n, int ki, int *k, int *index);
      int ni, merge;

      /*
       * Now we have a potentially undersize node on the
       * right (if half==0) or left (if half==1). Sort it
       * out, by merging with a neighbour or by transferring
       * subtrees over. At this time we must also ensure that
       * nodes are bigger than minimum, in case we need an
       * element to merge two nodes below.
       */
      LOG(("  node %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]));
      if (half == 1)
      {
        ki = 0;                 /* the kid we're interested in */
        ni = 1;                 /* the neighbour */
        merge = 0;              /* for merge: leftmost of the two */
        toward = trans234_subtree_left;
      } else
      {
        ki = (n->kids[3] ? 3 : n->kids[2] ? 2 : 1);
        ni = ki - 1;
        merge = ni;
        toward = trans234_subtree_right;
      }

      sub = n->kids[ki];
      if (sub && !sub->elems[1])
      {
        /*
         * This node is undersized or minimum-size. If we
         * can merge it with its neighbour, we do so;
         * otherwise we must be able to transfer subtrees
         * over to it until it is greater than minimum
         * size.
         */
        int undersized = (!sub->elems[0]);
        LOG(("  child %d is %ssize\n", ki,
             undersized ? "under" : "minimum-"));
        LOG(("  neighbour is %s\n",
             n->kids[ni]->elems[2] ? "large" :
             n->kids[ni]->elems[1] ? "medium" : "small"));
        if (!n->kids[ni]->elems[1] ||
            (undersized && !n->kids[ni]->elems[2]))
        {
          /*
           * Neighbour is small, or possibly neighbour is
           * medium and we are undersize.
           */
          trans234_subtree_merge(n, merge, NULL, NULL);
          sub = n->kids[merge];
          if (!n->elems[0])
          {
            /*
             * n is empty, and hence must have been the
             * root and needs to be removed.
             */
            assert(!n->parent);
            LOG(("  shifting root!\n"));
            halves[half] = sub;
            halves[half]->parent = NULL;
            sfree(n);
          }
        } else
        {
          /* Neighbour is big enough to move trees over. */
          toward(n, ni, NULL, NULL);
          if (undersized)
            toward(n, ni, NULL, NULL);
        }
      }
      n = sub;
    }
  }

  t->root = halves[1];
  return halves[0];
}

tree234 *splitpos234(tree234 * t, int index, int before)
{
  tree234 *ret;
  node234 *n;
  int count;

  count = countnode234(t->root);
  if (index < 0 || index > count)
    return NULL;                /* error */
  ret = newtree234(t->cmp);
  n = split234_internal(t, index);
  if (before)
  {
    /* We want to return the ones before the index. */
    ret->root = n;
  } else
  {
    /*
     * We want to keep the ones before the index and return the
     * ones after.
     */
    ret->root = t->root;
    t->root = n;
  }
  return ret;
}

tree234 *split234(tree234 * t, void *e, cmpfn234 cmp, int rel)
{
  int before;
  int index;

  assert(rel != REL234_EQ);

  if (rel == REL234_GT || rel == REL234_GE)
  {
    before = 1;
    rel = (rel == REL234_GT ? REL234_LE : REL234_LT);
  } else
  {
    before = 0;
  }
  if (!findrelpos234(t, e, cmp, rel, &index))
    index = 0;

  return splitpos234(t, index + 1, before);
}

static node234 *copynode234(node234 * n, copyfn234 copyfn,
                            void *copyfnstate)
{
  int i;
  node234 *n2 = mknew(node234);

  for (i = 0; i < 3; i++)
  {
    if (n->elems[i] && copyfn)
      n2->elems[i] = copyfn(copyfnstate, n->elems[i]);
    else
      n2->elems[i] = n->elems[i];
  }

  for (i = 0; i < 4; i++)
  {
    if (n->kids[i])
    {
      n2->kids[i] = copynode234(n->kids[i], copyfn, copyfnstate);
      n2->kids[i]->parent = n2;
    } else
    {
      n2->kids[i] = NULL;
    }
    n2->counts[i] = n->counts[i];
  }

  return n2;
}

tree234 *copytree234(tree234 * t, copyfn234 copyfn, void *copyfnstate)
{
  tree234 *t2;

  t2 = newtree234(t->cmp);
  t2->root = copynode234(t->root, copyfn, copyfnstate);
  t2->root->parent = NULL;

  return t2;
}

#ifdef TEST

/*
 * Test code for the 2-3-4 tree. This code maintains an alternative
 * representation of the data in the tree, in an array (using the
 * obvious and slow insert and delete functions). After each tree
 * operation, the verify() function is called, which ensures all
 * the tree properties are preserved:
 *  - node->child->parent always equals node
 *  - tree->root->parent always equals NULL
 *  - number of kids == 0 or number of elements + 1;
 *  - tree has the same depth everywhere
 *  - every node has at least one element
 *  - subtree element counts are accurate
 *  - any NULL kid pointer is accompanied by a zero count
 *  - in a sorted tree: ordering property between elements of a
 *    node and elements of its children is preserved
 * and also ensures the list represented by the tree is the same
 * list it should be. (This last check also doubly verifies the
 * ordering properties, because the `same list it should be' is by
 * definition correctly ordered. It also ensures all nodes are
 * distinct, because the enum functions would get caught in a loop
 * if not.)
 */

#include <stdarg.h>

#define srealloc realloc

/*
 * Error reporting function.
 */
void error(char *fmt, ...)
{
  va_list ap;
  printf("ERROR: ");
  va_start(ap, fmt);
  vfprintf(stdout, fmt, ap);
  va_end(ap);
  printf("\n");
}

/* The array representation of the data. */
void **array;
int arraylen, arraysize;
cmpfn234 cmp;

/* The tree representation of the same data. */
tree234 *tree;

/*
 * Routines to provide a diagnostic printout of a tree. Currently
 * relies on every element in the tree being a one-character string
 * :-)
 */
typedef struct {
  char **levels;
} dispctx;

int dispnode(node234 * n, int level, dispctx * ctx)
{
  if (level == 0)
  {
    int xpos = strlen(ctx->levels[0]);
    int len;

    if (n->elems[2])
      len = sprintf(ctx->levels[0] + xpos, " %s%s%s",
                    n->elems[0], n->elems[1], n->elems[2]);
    else if (n->elems[1])
      len = sprintf(ctx->levels[0] + xpos, " %s%s",
                    n->elems[0], n->elems[1]);
    else
      len = sprintf(ctx->levels[0] + xpos, " %s", n->elems[0]);
    return xpos + 1 + (len - 1) / 2;
  } else
  {
    int xpos[4], nkids;
    int nodelen, mypos, myleft, x, i;

    xpos[0] = dispnode(n->kids[0], level - 3, ctx);
    xpos[1] = dispnode(n->kids[1], level - 3, ctx);
    nkids = 2;
    if (n->kids[2])
    {
      xpos[2] = dispnode(n->kids[2], level - 3, ctx);
      nkids = 3;
    }
    if (n->kids[3])
    {
      xpos[3] = dispnode(n->kids[3], level - 3, ctx);
      nkids = 4;
    }

    if (nkids == 4)
      mypos = (xpos[1] + xpos[2]) / 2;
    else if (nkids == 3)
      mypos = xpos[1];
    else
      mypos = (xpos[0] + xpos[1]) / 2;
    nodelen = nkids * 2 - 1;
    myleft = mypos - ((nodelen - 1) / 2);
    assert(myleft >= xpos[0]);
    assert(myleft + nodelen - 1 <= xpos[nkids - 1]);

    x = strlen(ctx->levels[level]);
    while (x <= xpos[0] && x < myleft)
      ctx->levels[level][x++] = ' ';
    while (x < myleft)
      ctx->levels[level][x++] = '_';
    if (nkids == 4)
      x += sprintf(ctx->levels[level] + x, ".%s.%s.%s.",
                   n->elems[0], n->elems[1], n->elems[2]);
    else if (nkids == 3)
      x += sprintf(ctx->levels[level] + x, ".%s.%s.",
                   n->elems[0], n->elems[1]);
    else
      x += sprintf(ctx->levels[level] + x, ".%s.", n->elems[0]);
    while (x < xpos[nkids - 1])
      ctx->levels[level][x++] = '_';
    ctx->levels[level][x] = '\0';

    x = strlen(ctx->levels[level - 1]);
    for (i = 0; i < nkids; i++)
    {
      int rpos, pos;
      rpos = xpos[i];
      if (i > 0 && i < nkids - 1)
        pos = myleft + 2 * i;
      else
        pos = rpos;
      if (rpos < pos)
        rpos++;
      while (x < pos && x < rpos)
        ctx->levels[level - 1][x++] = ' ';
      if (x == pos)
        ctx->levels[level - 1][x++] = '|';
      while (x < pos || x < rpos)
        ctx->levels[level - 1][x++] = '_';
      if (x == pos)
        ctx->levels[level - 1][x++] = '|';
    }
    ctx->levels[level - 1][x] = '\0';

    x = strlen(ctx->levels[level - 2]);
    for (i = 0; i < nkids; i++)
    {
      int rpos = xpos[i];

      while (x < rpos)
        ctx->levels[level - 2][x++] = ' ';
      ctx->levels[level - 2][x++] = '|';
    }
    ctx->levels[level - 2][x] = '\0';

    return mypos;
  }
}

void disptree(tree234 * t)
{
  dispctx ctx;
  char *leveldata;
  int width = count234(t);
  int ht = height234(t) * 3 - 2;
  int i;

  if (!t->root)
  {
    printf("[empty tree]\n");
  }

  leveldata = smalloc(ht * (width + 2));
  ctx.levels = smalloc(ht * sizeof(char *));
  for (i = 0; i < ht; i++)
  {
    ctx.levels[i] = leveldata + i * (width + 2);
    ctx.levels[i][0] = '\0';
  }

  (void) dispnode(t->root, ht - 1, &ctx);

  for (i = ht; i--;)
    printf("%s\n", ctx.levels[i]);

  sfree(ctx.levels);
  sfree(leveldata);
}

typedef struct {
  int treedepth;
  int elemcount;
} chkctx;

int
chknode(chkctx * ctx, int level, node234 * node,
        void *lowbound, void *highbound)
{
  int nkids, nelems;
  int i;
  int count;

  /* Count the non-NULL kids. */
  for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
  /* Ensure no kids beyond the first NULL are non-NULL. */
  for (i = nkids; i < 4; i++)
    if (node->kids[i])
    {
      error("node %p: nkids=%d but kids[%d] non-NULL", node, nkids, i);
    } else if (node->counts[i])
    {
      error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
            node, i, i, node->counts[i]);
    }

  /* Count the non-NULL elements. */
  for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
  /* Ensure no elements beyond the first NULL are non-NULL. */
  for (i = nelems; i < 3; i++)
    if (node->elems[i])
    {
      error("node %p: nelems=%d but elems[%d] non-NULL", node, nelems, i);
    }

  if (nkids == 0)
  {
    /*
     * If nkids==0, this is a leaf node; verify that the tree