/***********************************************************************\
|									|
|	B+tree function implementation			C++		|
|									|
|									|
|	Jan Jannink	created 5/27/94		revised 6/15/95		|
|									|
\***********************************************************************/

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include "b++tree.h"

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Implementation Hiding Macro Definitions				|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
			/* low level definition of Nptr value usage */
#ifdef POINTER
#define nAdr(b) (b)->X
#define nodearrayhead tree
#else
#define nAdr(b) tree[(b)].X
#define nodearrayhead 0
#endif

			/* access keys and pointers in a node */
#define getkey(j, q) nAdr(j).e[(q)].key
#define getnode(j, q) nAdr(j).e[(q)].downNode
#define setkey(j, q, v) (nAdr(j).e[(q)].key = (v))
#define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))

			/* access node flag values */
#define setflag(j, v) (nAdr(j).i.info.flags |= (v))
#define clrflag(j, v) (nAdr(j).i.info.flags &= ~(v))
#define getflags(j) nAdr(j).i.info.flags
#define clearflags(j) (nAdr(j).i.info.flags = (short) MAGIC)

			/* check that a node is in fact a node */
#define isnode(j) (((j) != NONODE) && ((nAdr(j).i.info.flags & MASK) == MAGIC))
#define isntnode(j) ((j) == NONODE)

			/* test individual flag values */
#define isinternal(j) ((nAdr(j).i.info.flags & isLEAF) == 0)
#define isleaf(j) ((nAdr(j).i.info.flags & isLEAF) == isLEAF)
#define isroot(j) ((nAdr(j).i.info.flags & isROOT) == isROOT)
#define isfull(j) ((nAdr(j).i.info.flags & isFULL) == isFULL)
#define isfew(j) ((nAdr(j).i.info.flags & FEWEST) == FEWEST)

			/* manage number of keys in a node */
#define numentries(j) nAdr(j).i.info.pairs
#define clearentries(j) (nAdr(j).i.info.pairs = 0)
#define incentries(j) (nAdr(j).i.info.pairs++)
#define decentries(j) (nAdr(j).i.info.pairs--)

			/* manage first/last node pointers in internal nodes */
#define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
#define getfirstnode(j) nAdr(j).i.firstNode
#define getlastnode(j) nAdr(j).e[nAdr(j).i.info.pairs].downNode

			/* manage pointers to next nodes in leaf nodes */
#define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
#define getnextnode(j) nAdr(j).l.nextNode

			/* shift/transfer entries for insertion/deletion */
#define pushentry(j, q, v) (nAdr(j).e[(q) + (v)] = nAdr(j).e[(q)])
#define pullentry(j, q, v) (nAdr(j).e[(q)] = nAdr(j).e[(q) + (v)])
#define xferentry(j, q, v, z) (nAdr(v).e[(z)] = nAdr(j).e[(q)])
#define setentry(j, q, v, z) (nAdr(j).e[(q)].key = (v), nAdr(j).e[(q)].downNode = (z))

			/* access key and data values for B+tree methods */
			/* pass values to getSlot(), descend...() */
#define getfunkey theKey
#define getfundata theData
#define setfunkey(v) (theKey = (v))
#define setfundata(v) (theData = (v))

			/* define number of B+tree nodes for free node pool */
#define getpoolsize poolsize
#define setpoolsize(v) (poolsize = (v))

			/* access memory region containing B+tree nodes */
#define getnodearray tree
#define setnodearray(v) (tree = (Node *)(v))

			/* locations from which tree access begins */
#define getroot root
#define getleaf leaf
#define setroot(v) (root = (v))
#define setleaf(v) (leaf = (v))

			/* define max/min number of pointers per node */
#define getfanout fanout
#define getminfanout(j) ((nAdr(j).i.info.flags & isLEAF) ? fanout - minfanout: minfanout)
#define setfanout(v) (fanout = (v) - 1)
#define setminfanout(v) (minfanout = (v) - 1)

			/* manage B+tree height */
#define inittreeheight (height = 0)
#define inctreeheight height++
#define dectreeheight height--
#define gettreeheight height

			/* access pool of free nodes */
#define getfirstfreenode pool
#define setfirstfreenode(v) (pool = (v))

			/* handle split/merge points during insert/delete */
#define getsplitpath branch.split
#define getmergepath branch.merge
#define setsplitpath(v) (branch.split = (v))
#define setmergepath(v) (branch.merge = (v))

			/* exploit function to compare two B+tree keys */
#define comparekeys (keycmp)
#define setcomparekeys(v) (keycmp = (v))

			/* representation independent node numbering */
#define getnodeno(v) ((v) - nodearrayhead)


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Sample Key Comparison Function					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

int compareKeys(keyT key1, keyT key2)
{
  return key1 - key2;		/* this is the case when keys are integer */
}


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

/*~~~~~~~~~~~~~~~~~~~   Set up B+tree structure   ~~~~~~~~~~~~~~~~~~~~~*/
Tree::Tree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp)
{
  setfanout(fan);
  setminfanout((fan + 1) >> 1);
  initFreeNodePool(poolsz);

  setleaf(getFreeNode());		/* set up the first leaf node */
  setroot(getleaf);			/* the root is initially the leaf */
  setflag(getroot, isLEAF);
  setflag(getroot, isROOT);
  setflag(getroot, FEWEST);
  inittreeheight;

  setfunkey(0);
  setfundata("0");
  setcomparekeys(keyCmp);

#ifdef DEBUG
  cerr << "INIT:  B+tree of fanout " << fan << '.' << endl;
  showBtree();
  showNode(getroot);
#endif
}


/*~~~~~~~~~~~~~~~~~~~   Clean up B+tree structure   ~~~~~~~~~~~~~~~~~~~*/
Tree::~Tree()
{
#ifdef DEBUG
  cerr << "FREE:  B+tree at " << setw(10) << (void *) this << '.' << endl;
#endif

  delete[] getnodearray;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Find location for data						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~   top level search call   ~~~~~~~~~~~~~~~~~~~~~*/
Nptr
Tree::Search(keyT key)
{
  Nptr	findNode;

#ifdef DEBUG
  cerr << "SEARCH:  key " << key << '.' << endl;
#endif

  setfunkey(key);			/* set search key */
  findNode = descendToLeaf(getroot);	/* start search from root node */

#ifdef DEBUG
  cerr << "SEARCH:  found on page " << getnodeno(findNode) << '.' << endl;
#endif

  return findNode;
}

/*~~~~~~~~~~~~~~~~~~~~~   `recurse' down B+tree   ~~~~~~~~~~~~~~~~~~~~~*/
Nptr
Tree::descendToLeaf(Nptr curr)
{
  int	slot;
  Nptr	findNode;

  for (slot = getSlot(curr); isinternal(curr); slot = getSlot(curr))
    curr = getnode(curr, slot);
  if ((slot > 0) && !comparekeys(getfunkey, getkey(curr, slot)))
    findNode = curr;			/* correct key value found */
  else
    findNode = NONODE;			/* key value not in tree */

  return findNode;
}

/*~~~~~~~~~~~~~~~~~~~   find slot for search key   ~~~~~~~~~~~~~~~~~~~~*/
int
Tree::getSlot(Nptr curr)
{
  int slot, entries;

  entries = numentries(curr);		/* need this if root is ever empty */
  slot = !entries ? 0 : findKey(curr, 1, entries);

#ifdef DEBUG
  cerr << "GETSLOT:  slot " << slot << '.' << endl;
#endif

  return slot;
}


/*/*~~~~~~~~~~~~~~~~~~~   recursive binary search   ~~~~~~~~~~~~~~~~~~~~~*/
int
Tree::findKey(Nptr curr, int lo, int hi)
{
  int mid, findslot;

#ifdef DEBUG
  cerr << "GETSLOT:  lo " << lo << ", hi " << hi << '.' << endl;
  showNode(curr);
#endif

  if (hi == lo) {
    findslot = bestMatch(curr, lo);		/* recursion base case */

#ifdef DEBUG
    if (findslot == ERROR)
      cerr << "Bad key ordering on node " << getnodeno(curr) << '.' << endl;
#endif

  }
  else {
    mid = (lo + hi) >> 1;
    switch (findslot = bestMatch(curr, mid)) {
    case LOWER:				/* check lower half of range */
      findslot = findKey(curr, lo, mid - 1);		/* never in 2-3+trees */
    break;
    case UPPER:				/* check upper half of range */
      findslot = findKey(curr, mid + 1, hi);
    break;

#ifdef DEBUG
    case ERROR:
      cerr << "Bad key ordering on node " << getnodeno(curr) << '.' << endl;
#endif

    }
  }
  return findslot;
}


/*~~~~~~~~~~~   comparison of key with a target key slot   ~~~~~~~~~~~~*/
int
Tree::bestMatch(Nptr curr, int slot)
{
  int diff, comp, findslot;

  diff = comparekeys(getfunkey, getkey(curr, slot));
  if (diff < 0) {		/* also check previous slot */
    if ((slot == 1) ||
		((comp = comparekeys(getfunkey, getkey(curr, slot - 1))) >= 0))
      findslot = slot - 1;

#ifdef DEBUG
    else if (comp < diff)
      findslot = ERROR;		/* inconsistent ordering of keys */
#endif

    else
      findslot = LOWER;		/* key must be below in node ordering */
  }
  else {			/* or check following slot */
    if ((slot == numentries(curr)) ||
		((comp = comparekeys(getfunkey, getkey(curr, slot + 1))) < 0))
      findslot = slot;
    else if (comp == 0)
      findslot = slot + 1;

#ifdef DEBUG
    else if (comp > diff)
      findslot = ERROR;		/* inconsistent ordering of keys */
#endif

    else
      findslot = UPPER;		/* key must be above in node ordering */
  }
  return findslot;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Insert new data into tree					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~   top level insert call   ~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::Insert(keyT key)
{
  Nptr newNode;

#ifdef DEBUG
  cerr << "INSERT:  key " << key << '.' << endl;
#endif

  setfunkey(key);			/* set insertion key */
  setfundata("data");			/* a node containing data */
  setsplitpath(NONODE);
  newNode = descendSplit(getroot);	/* insertion point search from root */
  if (newNode != getsplitpath)		/* indicates the root node has split */
    makeNewRoot(getroot, newNode);
}


/*~~~~~~~~~~~~~~~~   recurse down and split back up   ~~~~~~~~~~~~~~~~~*/
Nptr
Tree::descendSplit(Nptr curr)
{
  Nptr	newMe, newNode;
  int	slot;

  if (!isfull(curr))
    setsplitpath(NONODE);
  else if (getsplitpath == NONODE)
    setsplitpath(curr);			/* indicates where nodes must split */

  slot = getSlot(curr);			/* is null only if the root is empty */
  if (isinternal(curr))			/* continue recursion to leaves */
    newMe = descendSplit(getnode(curr, slot));
  else if ((slot > 0) && !comparekeys(getfunkey, getkey(curr, slot))) {
    newMe = NONODE;			/* this code discards duplicates */
    setsplitpath(NONODE);
  }
  else
    newMe = getDataNode(getfunkey);	/* an insertion takes place */

  newNode = NONODE;			/* assume no node splitting necessary */

  if (newMe != NONODE) {		/* insert only where necessary */
    if (getsplitpath != NONODE)
      newNode = split(curr);		/* a sibling node is prepared */
    insertEntry(curr, slot, newNode, newMe);
  }

  return newNode;
}


/*/*~~~~~~~~~~~~~~   determine location of inserted key   ~~~~~~~~~~~~~~~*/
void
Tree::insertEntry(Nptr newNode, int slot, Nptr sibling, Nptr downPtr)
{
  int split, i, j, k, x, y;

  if (sibling == NONODE) {		/* no split occurred */
    placeEntry(newNode, slot + 1, downPtr);
    clrflag(newNode, FEWEST);
  }
  else {				/* split entries between the two */
    i = isinternal(newNode);		/* adjustment values */
    split = i ? getfanout - getminfanout(newNode): getminfanout(newNode);
    j = (slot != split);
    k = (slot >= split);

    for (x = split + k + j * i, y = 1; x <= getfanout; x++, y++) {
      xferentry(newNode, x, sibling, y);	/* copy entries to sibling */
      decentries(newNode);
      incentries(sibling);
    }
    if (numentries(sibling) == getfanout)
      setflag(sibling, isFULL);		/* only ever happens in 2-3+trees */

    if (i) {				/* set first pointer of internal node */
      if (j) {
        setfirstnode(sibling, getnode(newNode, split + k));
        decentries(newNode);
      }
      else
        setfirstnode(sibling, downPtr);
    }

    if (j) {				/* insert new entry into correct spot */
      x = getkey(newNode, split + k);
      if (k)
	placeEntry(sibling, slot - split + 1 - i, downPtr);
      else
	placeEntry(newNode, slot + 1, downPtr);
      setfunkey(x);			/* set key separating nodes */
    }
    else if (!i)
      placeEntry(sibling, 1, downPtr);

    clrflag(newNode, isFULL);		/* adjust node flags */
    if (numentries(newNode) == getminfanout(newNode))
      setflag(newNode, FEWEST);
    if (numentries(sibling) > getminfanout(sibling))
      clrflag(sibling, FEWEST);

#ifdef DEBUG
  cerr << "INSERT:  slot " << slot << ", node " << getnodeno(downPtr)
								<< '.' << endl;
  showNode(newNode);
  showNode(sibling);
#endif

  }
}

/*/*~~~~~~~~~~~   place key into appropriate node & slot   ~~~~~~~~~~~~~~*/
void
Tree::placeEntry(Nptr newNode, int slot, Nptr downPtr)
{
  int x;

  for (x = numentries(newNode); x >= slot; x--)	/* make room for new entry */
    pushentry(newNode, x, 1);
  setentry(newNode, slot, getfunkey, downPtr);	/* place it in correct slot */

  incentries(newNode);				/* adjust entry counter */
  if (numentries(newNode) == getfanout)
    setflag(newNode, isFULL);
}


/*~~~~~~~~~~~~~~~~   split full node and set flags   ~~~~~~~~~~~~~~~~~~*/
Nptr
Tree::split(Nptr newNode)
{
  Nptr sibling;

  sibling = getFreeNode();

  setflag(sibling, FEWEST);			/* set up node flags */

  if (isleaf(newNode)) {
    setflag(sibling, isLEAF);
    setnextnode(sibling, getnextnode(newNode));	/* adjust leaf pointers */
    setnextnode(newNode, sibling);
  }
  if (getsplitpath == newNode)
    setsplitpath(NONODE);			/* no more splitting needed */

  return sibling;
}