btree.c

这是一个利用B+ Trees数据结构存储数据的源码,全部代码用C语言写的.

    removeEntry(B, curr, slot + (newMe != newNode));	/* removes one of two */

#ifdef DEBUG
  fprintf(stderr, "DELETE:  slot %d, node %d.\n", slot, getnodenumber(newMe));
  showNode(B, curr);
#endif

  if (getmergepath == NONODE)
    newNode = NONODE;
  else {		/* tree rebalancing rules for node merges and shifts */
    notleft = isntnode(left);
    notright = isntnode(right);
    fewleft = isfew(left);		/* only used when defined */
    fewright = isfew(right);

			/* CASE 1:  prepare root node (curr) for removal */
    if (notleft && notright) {
      test = isleaf(curr);		/* check if B+tree has become empty */
      newNode = test ? NONODE : getfirstnode(curr);
    }
			/* CASE 2:  the merging of two nodes is a must */
    else if ((notleft || fewleft) && (notright || fewright)) {
      test = !(lAnc == parent);
      newNode = test ? merge(B, curr, right, rAnc) : merge(B, left, curr, lAnc);
    }
			/* CASE 3: choose the better of a merge or a shift */
    else if (!notleft && fewleft && !notright && !fewright) {
      test = !(rAnc == parent) && (curr == getmergepath);
      newNode = test ? merge(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
    }
			/* CASE 4: also choose between a merge or a shift */
    else if (!notleft && !fewleft && !notright && fewright) {
      test = !(lAnc == parent) && (curr == getmergepath);
      newNode = test ? merge(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
    }
			/* CASE 5: choose the more effective of two shifts */
    else if (lAnc == rAnc) { 		/* => both anchors are the parent */
      test = (numentries(left) <= numentries(right));
      newNode = test ? shift(B, curr, right, rAnc) : shift(B, left, curr, lAnc);
    }
			/* CASE 6: choose the shift with more local effect */
    else {				/* if omitting cases 3,4,5 use below */
      test = (lAnc == parent);		/* test = (!notleft && !fewleft); */
      newNode = test ? shift(B, left, curr, lAnc) : shift(B, curr, right, rAnc);
    }
  }

  return newNode;
}


/*/*~~~~~~~~~~~~~~~   remove key and pointer from node   ~~~~~~~~~~~~~~~~*/
void removeEntry(Tree *B, Nptr curr, int slot)
{
  int x;

  putFreeNode(B, getnode(curr, slot));	/* return deleted node to free list */
  for (x = slot; x < numentries(curr); x++)
    pullentry(curr, x, 1);		/* adjust node with removed key */
  decentries(curr);
  clrflag(curr, isFULL);		/* keep flag information up to date */
  if (isroot(curr)) {
    if (numentries(curr) == 1)
      setflag(curr, FEWEST);
  }
  else if (numentries(curr) == getminfanout(curr))
    setflag(curr, FEWEST);
}


/*~~~~~~   merge a node pair & set emptied node up for removal   ~~~~~~*/
Nptr merge(Tree *B, Nptr left, Nptr right, Nptr anchor)
{
  int	x, y, z;

#ifdef DEBUG
  fprintf(stderr, "MERGE:  left %d, right %d.\n", getnodenumber(left), getnodenumber(right));
  showNode(B, left);
  showNode(B, right);
#endif

  if (isinternal(left)) {
    incentries(left);			/* copy key separating the nodes */
    setfunkey(getkey(right, 1));	/* defined but maybe just deleted */
    z = getSlot(B, anchor);		/* needs the just calculated key */
    setfunkey(getkey(anchor, z));	/* set slot to delete in anchor */
    setentry(left, numentries(left), getfunkey, getfirstnode(right));
  }
  else
    setnextnode(left, getnextnode(right));
  for (x = numentries(left) + 1, y = 1; y <= numentries(right); x++, y++) {
    incentries(left);
    xferentry(right, y, left, x);	/* transfer entries to left node */
  }
  if (numentries(left) > getminfanout(left))
    clrflag(left, FEWEST);
  if (numentries(left) == getfanout)
    setflag(left, isFULL);		/* never happens in even size nodes */

  if (getmergepath == left || getmergepath == right)
    setmergepath(NONODE);		/* indicate rebalancing is complete */

  return right;
}


/*/*~~~~~   shift entries in a node pair & adjust anchor key value   ~~~~*/
Nptr shift(Tree *B, Nptr left, Nptr right, Nptr anchor)
{
  int	i, x, y, z;

#ifdef DEBUG
  fprintf(stderr, "SHIFT:  left %d, right %d.\n", getnodenumber(left), getnodenumber(right));
  showNode(B, left);
  showNode(B, right);
#endif

  i = isinternal(left);
  if (numentries(left) < numentries(right)) {	/* shift entries to left */
    y = (numentries(right) - numentries(left)) >> 1;
    x = numentries(left) + y;
    setfunkey(getkey(right, y + 1 - i));	/* set new anchor key value */
    z = getSlot(B, anchor);			/* find slot in anchor node */
    if (i) {					/* move out old anchor value */
      decentries(right);			/* adjust for shifting anchor */
      incentries(left);
      setentry(left, numentries(left), getkey(anchor, z), getfirstnode(right));
      setfirstnode(right, getnode(right, y + 1 - i));
    }
    clrflag(right, isFULL);
    setkey(anchor, z, getfunkey);		/* set new anchor value */
    for (z = y, y -= i; y > 0; y--, x--) {
      decentries(right);			/* adjust entry count */
      incentries(left);
      xferentry(right, y, left, x);		/* transfer entries over */
    }

    for (x = 1; x <= numentries(right); x++)	/* adjust reduced node */
      pullentry(right, x, z);
  }
  else {					/* shift entries to right */
    y = (numentries(left) - numentries(right)) >> 1;
    x = numentries(left) - y + 1;

    for (z = numentries(right); z > 0; z--)	/* adjust increased node */
      pushentry(right, z, y);

    setfunkey(getkey(left, x));			/* set new anchor key value */
    z = getSlot(B, anchor) + 1;
    if (i) {
      decentries(left);
      incentries(right);
      setentry(right, y, getkey(anchor, z), getfirstnode(right));
      setfirstnode(right, getnode(left, x));
    }
    clrflag(left, isFULL);
    setkey(anchor, z, getfunkey);
    for (x = numentries(left) + i, y -= i; y > 0; y--, x--) {
      decentries(left);
      incentries(right);
      xferentry(left, x, right, y);		/* transfer entries over */
    }
  }
  if (numentries(left) == getminfanout(left))		/* adjust node flags */
    setflag(left, FEWEST);
  else
    clrflag(left, FEWEST);			/* never happens in 2-3+trees */
  if (numentries(right) == getminfanout(right))
    setflag(right, FEWEST);
  else
    clrflag(right, FEWEST);			/* never happens in 2-3+trees */
  setmergepath(NONODE);

#ifdef DEBUG
  showNode(B, left);
  showNode(B, right);
#endif

  return NONODE;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Empty Node Utilities						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~   Set up pool of free nodes   ~~~~~~~~~~~~~~~~~~*/
void initFreeNodePool(Tree *B, int quantity)
{
  int	i;
  Nptr	n;

  setpoolsize(quantity);
  setnodearray(malloc(quantity * sizeof(Node)));	/* node memory block */
  setfirstfreenode(nodearrayhead);	/* start a list of free nodes */
  for (n = getfirstfreenode, i = 0; i < quantity; n++, i++) {
    clearflags(n);
    clearentries(n);
    setnextnode(n, n + 1);		/* insert node into free node list */
  }
  setnextnode(--n, NONODE);		/* indicates end of free node list */
}


/*~~~~~~~~~~~~~   take a free B+tree node from the pool   ~~~~~~~~~~~~~*/
Nptr getFreeNode(Tree *B)
{
  Nptr newNode = getfirstfreenode;

  if (newNode != NONODE) {
    setfirstfreenode(getnextnode(newNode));	/* adjust free node list */
    setnextnode(newNode, NONODE);		/* remove node from list */
  }
  else {
    fprintf(stderr, "Out of tree nodes.");	/* can't recover from this */
    exit(0);
  }
  return newNode;
}


/*~~~~~~~~~~~~   return a deleted B+tree node to the pool   ~~~~~~~~~~~*/
void putFreeNode(Tree *B, Nptr self)
{
  clearflags(self);
  clearentries(self);
  setnextnode(self, getfirstfreenode);		/* add node to list */
  setfirstfreenode(self);			/* set it to be list head */
}


/*~~~~~~   fill a free data node with a key and associated data   ~~~~~*/
Nptr getDataNode(Tree *B, keyT key)		/* can add data parameter */
{
  Nptr	newNode = getFreeNode(B);
  keyT	*value;

  value = (keyT *) &nAdr(newNode).d;
  *value = key;					/* can add code to fill node */

  return newNode;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	B+tree Printing Utilities					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

#ifdef DEBUG
/*~~~~~~~~~~~~~~~~~~~~~~   B+tree node printer   ~~~~~~~~~~~~~~~~~~~~~~*/
void showNode(Tree *B, Nptr n)
{
  int x;

  fprintf(stderr, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
  fprintf(stderr, "| node %6d                 ", getnodenumber(n));
  fprintf(stderr, "  magic    %4x  |\n", getflags(n) & MASK);
  fprintf(stderr, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
  fprintf(stderr, "| flags   %1d%1d%1d%1d ", isfew(n), isfull(n), isroot(n), isleaf(n));
  fprintf(stderr, "| keys = %5d ", numentries(n));
  fprintf(stderr, "| node = %6d  |\n", getnodenumber(getfirstnode(n)));
  for (x = 1; x <= numentries(n); x++) {
    fprintf(stderr, "| entry %6d ", x);
    fprintf(stderr, "| key = %6d ", getkey(n, x) & 0xFFFF);
    fprintf(stderr, "| node = %6d  |\n", getnodenumber(getnode(n, x)));
  }
  fprintf(stderr, "-  --  --  --  --  --  --  --  --  --  --  --  -\n");
}

/*~~~~~~~~~~~~~~~~~   B+tree class variable printer   ~~~~~~~~~~~~~~~~~*/
void showBtree(Tree *B)
{
  fprintf(stderr, "-  --  --  --  --  --  -\n");
  fprintf(stderr, "|  B+tree  %10p  |\n", (void *) B);
  fprintf(stderr, "-  --  --  --  --  --  -\n");
  fprintf(stderr, "|  root        %6d  |\n", getnodenumber(getroot));
  fprintf(stderr, "|  leaf        %6d  |\n", getnodenumber(getleaf));
  fprintf(stderr, "|  fanout         %3d  |\n", getfanout + 1);
  fprintf(stderr, "|  minfanout      %3d  |\n", getminfanout(getroot) + 1);
  fprintf(stderr, "|  height         %3d  |\n", gettreeheight);
  fprintf(stderr, "|  freenode    %6d  |\n", getnodenumber(getfirstfreenode));
  fprintf(stderr, "|  theKey      %6d  |\n", getfunkey);
  fprintf(stderr, "|  theData     %6s  |\n", getfundata);
  fprintf(stderr, "-  --  --  --  --  --  -\n");
}
#endif

/*~~~~~~~~~~~~~~~~~~~~~~   B+tree data printer   ~~~~~~~~~~~~~~~~~~~~~~*/
void listBtreeValues(Tree *B, Nptr n, int num)
{
  int slot, prev = -1;

  for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
    if (getkey(n, slot) <= prev) fprintf(stderr, "BOMB");
    prev = getkey(n, slot);
    fprintf(stderr, "%8d%c", prev, (num & 7 ? ' ' : '\n'));
    if (++slot > numentries(n))
      n = getnextnode(n), slot = 1;
  }
  fprintf(stderr, "\n\n");
}

/*~~~~~~~~~~~~~~~~~~~   entire B+tree data printer   ~~~~~~~~~~~~~~~~~~*/
void listAllBtreeValues(Tree *B)
{
  listBtreeValues(B, getleaf, ERROR);
}