tree234.c

NullSofts criptable install system2.28源代码

/*
 * tree234.c: reasonably generic counted 2-3-4 tree routines.
 * 
 * This file is copyright 1999-2001 Simon Tatham.
 * 
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "tree234.h"

#define smalloc malloc
#define sfree free

#define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )

#ifdef TEST
#define LOG(x) (printf x)
#else
#define LOG(x)
#endif

typedef struct node234_Tag node234;

struct tree234_Tag {
  node234 *root;
  cmpfn234 cmp;
};

struct node234_Tag {
  node234 *parent;
  node234 *kids[4];
  int counts[4];
  void *elems[3];
};

/*
 * Create a 2-3-4 tree.
 */
tree234 *newtree234(cmpfn234 cmp)
{
  tree234 *ret = mknew(tree234);
  LOG(("created tree %p\n", ret));
  ret->root = NULL;
  ret->cmp = cmp;
  return ret;
}

/*
 * Free a 2-3-4 tree (not including freeing the elements).
 */
static void freenode234(node234 * n)
{
  if (!n)
    return;
  freenode234(n->kids[0]);
  freenode234(n->kids[1]);
  freenode234(n->kids[2]);
  freenode234(n->kids[3]);
  sfree(n);
}

void freetree234(tree234 * t)
{
  freenode234(t->root);
  sfree(t);
}

/*
 * Internal function to count a node.
 */
static int countnode234(node234 * n)
{
  int count = 0;
  int i;
  if (!n)
    return 0;
  for (i = 0; i < 4; i++)
    count += n->counts[i];
  for (i = 0; i < 3; i++)
    if (n->elems[i])
      count++;
  return count;
}

/*
 * Count the elements in a tree.
 */
int count234(tree234 * t)
{
  if (t->root)
    return countnode234(t->root);
  else
    return 0;
}

/*
 * Propagate a node overflow up a tree until it stops. Returns 0 or
 * 1, depending on whether the root had to be split or not.
 */
static int
add234_insert(node234 * left, void *e, node234 * right,
              node234 ** root, node234 * n, int ki)
{
  int lcount, rcount;
  /*
   * We need to insert the new left/element/right set in n at
   * child position ki.
   */
  lcount = countnode234(left);
  rcount = countnode234(right);
  while (n)
  {
    LOG(("  at %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(("  need to insert %p/%d \"%s\" %p/%d at position %d\n", left,
         lcount, e, right, rcount, ki));
    if (n->elems[1] == NULL)
    {
      /*
       * Insert in a 2-node; simple.
       */
      if (ki == 0)
      {
        LOG(("  inserting on left of 2-node\n"));
        n->kids[2] = n->kids[1];
        n->counts[2] = n->counts[1];
        n->elems[1] = n->elems[0];
        n->kids[1] = right;
        n->counts[1] = rcount;
        n->elems[0] = e;
        n->kids[0] = left;
        n->counts[0] = lcount;
      } else
      {                         /* ki == 1 */
        LOG(("  inserting on right of 2-node\n"));
        n->kids[2] = right;
        n->counts[2] = rcount;
        n->elems[1] = e;
        n->kids[1] = left;
        n->counts[1] = lcount;
      }
      if (n->kids[0])
        n->kids[0]->parent = n;
      if (n->kids[1])
        n->kids[1]->parent = n;
      if (n->kids[2])
        n->kids[2]->parent = n;
      LOG(("  done\n"));
      break;
    } else if (n->elems[2] == NULL)
    {
      /*
       * Insert in a 3-node; simple.
       */
      if (ki == 0)
      {
        LOG(("  inserting on left of 3-node\n"));
        n->kids[3] = n->kids[2];
        n->counts[3] = n->counts[2];
        n->elems[2] = n->elems[1];
        n->kids[2] = n->kids[1];
        n->counts[2] = n->counts[1];
        n->elems[1] = n->elems[0];
        n->kids[1] = right;
        n->counts[1] = rcount;
        n->elems[0] = e;
        n->kids[0] = left;
        n->counts[0] = lcount;
      } else if (ki == 1)
      {
        LOG(("  inserting in middle of 3-node\n"));
        n->kids[3] = n->kids[2];
        n->counts[3] = n->counts[2];
        n->elems[2] = n->elems[1];
        n->kids[2] = right;
        n->counts[2] = rcount;
        n->elems[1] = e;
        n->kids[1] = left;
        n->counts[1] = lcount;
      } else
      {                         /* ki == 2 */
        LOG(("  inserting on right of 3-node\n"));
        n->kids[3] = right;
        n->counts[3] = rcount;
        n->elems[2] = e;
        n->kids[2] = left;
        n->counts[2] = lcount;
      }
      if (n->kids[0])
        n->kids[0]->parent = n;
      if (n->kids[1])
        n->kids[1]->parent = n;
      if (n->kids[2])
        n->kids[2]->parent = n;
      if (n->kids[3])
        n->kids[3]->parent = n;
      LOG(("  done\n"));
      break;
    } else
    {
      node234 *m = mknew(node234);
      m->parent = n->parent;
      LOG(("  splitting a 4-node; created new node %p\n", m));
      /*
       * Insert in a 4-node; split into a 2-node and a
       * 3-node, and move focus up a level.
       * 
       * I don't think it matters which way round we put the
       * 2 and the 3. For simplicity, we'll put the 3 first
       * always.
       */
      if (ki == 0)
      {
        m->kids[0] = left;
        m->counts[0] = lcount;
        m->elems[0] = e;
        m->kids[1] = right;
        m->counts[1] = rcount;
        m->elems[1] = n->elems[0];
        m->kids[2] = n->kids[1];
        m->counts[2] = n->counts[1];
        e = n->elems[1];
        n->kids[0] = n->kids[2];
        n->counts[0] = n->counts[2];
        n->elems[0] = n->elems[2];
        n->kids[1] = n->kids[3];
        n->counts[1] = n->counts[3];
      } else if (ki == 1)
      {
        m->kids[0] = n->kids[0];
        m->counts[0] = n->counts[0];
        m->elems[0] = n->elems[0];
        m->kids[1] = left;
        m->counts[1] = lcount;
        m->elems[1] = e;
        m->kids[2] = right;
        m->counts[2] = rcount;
        e = n->elems[1];
        n->kids[0] = n->kids[2];
        n->counts[0] = n->counts[2];
        n->elems[0] = n->elems[2];
        n->kids[1] = n->kids[3];
        n->counts[1] = n->counts[3];
      } else if (ki == 2)
      {
        m->kids[0] = n->kids[0];
        m->counts[0] = n->counts[0];
        m->elems[0] = n->elems[0];
        m->kids[1] = n->kids[1];
        m->counts[1] = n->counts[1];
        m->elems[1] = n->elems[1];
        m->kids[2] = left;
        m->counts[2] = lcount;
        /* e = e; */
        n->kids[0] = right;
        n->counts[0] = rcount;
        n->elems[0] = n->elems[2];
        n->kids[1] = n->kids[3];
        n->counts[1] = n->counts[3];
      } else
      {                         /* ki == 3 */
        m->kids[0] = n->kids[0];
        m->counts[0] = n->counts[0];
        m->elems[0] = n->elems[0];
        m->kids[1] = n->kids[1];
        m->counts[1] = n->counts[1];
        m->elems[1] = n->elems[1];
        m->kids[2] = n->kids[2];
        m->counts[2] = n->counts[2];
        n->kids[0] = left;
        n->counts[0] = lcount;
        n->elems[0] = e;
        n->kids[1] = right;
        n->counts[1] = rcount;
        e = n->elems[2];
      }
      m->kids[3] = n->kids[3] = n->kids[2] = NULL;
      m->counts[3] = n->counts[3] = n->counts[2] = 0;
      m->elems[2] = n->elems[2] = n->elems[1] = NULL;
      if (m->kids[0])
        m->kids[0]->parent = m;
      if (m->kids[1])
        m->kids[1]->parent = m;
      if (m->kids[2])
        m->kids[2]->parent = m;
      if (n->kids[0])
        n->kids[0]->parent = n;
      if (n->kids[1])
        n->kids[1]->parent = n;
      LOG(("  left (%p): %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", m,
           m->kids[0], m->counts[0], m->elems[0],
           m->kids[1], m->counts[1], m->elems[1],
           m->kids[2], m->counts[2]));
      LOG(("  right (%p): %p/%d \"%s\" %p/%d\n", n,
           n->kids[0], n->counts[0], n->elems[0],
           n->kids[1], n->counts[1]));
      left = m;
      lcount = countnode234(left);
      right = n;
      rcount = countnode234(right);
    }
    if (n->parent)
      ki = (n->parent->kids[0] == n ? 0 :
            n->parent->kids[1] == n ? 1 : n->parent->kids[2] == n ? 2 : 3);
    n = n->parent;
  }

  /*
   * If we've come out of here by `break', n will still be
   * non-NULL and all we need to do is go back up the tree
   * updating counts. If we've come here because n is NULL, we
   * need to create a new root for the tree because the old one
   * has just split into two. */
  if (n)
  {
    while (n->parent)
    {
      int count = countnode234(n);
      int childnum;
      childnum = (n->parent->kids[0] == n ? 0 :
                  n->parent->kids[1] == n ? 1 :
                  n->parent->kids[2] == n ? 2 : 3);
      n->parent->counts[childnum] = count;
      n = n->parent;
    }
    return 0;                   /* root unchanged */
  } else
  {
    LOG(("  root is overloaded, split into two\n"));
    (*root) = mknew(node234);
    (*root)->kids[0] = left;
    (*root)->counts[0] = lcount;
    (*root)->elems[0] = e;
    (*root)->kids[1] = right;
    (*root)->counts[1] = rcount;
    (*root)->elems[1] = NULL;
    (*root)->kids[2] = NULL;
    (*root)->counts[2] = 0;
    (*root)->elems[2] = NULL;
    (*root)->kids[3] = NULL;
    (*root)->counts[3] = 0;
    (*root)->parent = NULL;
    if ((*root)->kids[0])
      (*root)->kids[0]->parent = (*root);
    if ((*root)->kids[1])
      (*root)->kids[1]->parent = (*root);
    LOG(("  new root is %p/%d \"%s\" %p/%d\n",
         (*root)->kids[0], (*root)->counts[0],
         (*root)->elems[0], (*root)->kids[1], (*root)->counts[1]));
    return 1;                   /* root moved */
  }
}

/*
 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
 * an existing element compares equal, returns that.
 */
static void *add234_internal(tree234 * t, void *e, int index)
{
  node234 *n;
  int ki;
  void *orig_e = e;
  int c;

  LOG(("adding element \"%s\" to tree %p\n", e, t));
  if (t->root == NULL)
  {
    t->root = mknew(node234);
    t->root->elems[1] = t->root->elems[2] = NULL;
    t->root->kids[0] = t->root->kids[1] = NULL;
    t->root->kids[2] = t->root->kids[3] = NULL;
    t->root->counts[0] = t->root->counts[1] = 0;
    t->root->counts[2] = t->root->counts[3] = 0;
    t->root->parent = NULL;
    t->root->elems[0] = e;
    LOG(("  created root %p\n", t->root));
    return orig_e;
  }

  n = t->root;
  while (n)
  {
    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 (index >= 0)
    {
      if (!n->kids[0])
      {
        /*
         * Leaf node. We want to insert at kid position
         * equal to the index:
         * 
         *   0 A 1 B 2 C 3
         */
        ki = index;
      } else
      {
        /*
         * Internal node. We always descend through it (add
         * always starts at the bottom, never in the
         * middle).
         */
        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
          return NULL;          /* error: index out of range */
      }
    } else
    {
      if ((c = t->cmp(e, n->elems[0])) < 0)
        ki = 0;
      else if (c == 0)
        return n->elems[0];     /* already exists */
      else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
        ki = 1;
      else if (c == 0)
        return n->elems[1];     /* already exists */
      else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
        ki = 2;
      else if (c == 0)
        return n->elems[2];     /* already exists */
      else
        ki = 3;
    }
    LOG(("  moving to child %d (%p)\n", ki, n->kids[ki]));
    if (!n->kids[ki])
      break;
    n = n->kids[ki];