btreeupdate.c

b tree how to operate on b tr

/*JS*********************************************************************
*
*    Program : BTREE
*    Language: ANSI-C
*    Author  : Joerg Schoen
*    Purpose : Implement a B-Tree library.
*
*    Part    : Update function. Does also insertion and deletion.
*
*************************************************************************/

#ifndef lint
static const char rcsid[] = "$Id: btreeupdate.c,v 1.10 1998/05/22 08:41:32 joerg Stab joerg $";
#endif

/*********     INCLUDES                                         *********/
#include <jsalloca.h>

#include "btreeint.h"

/*********     DEFINES                                          *********/
#ifndef bayTreeInsert
/*  START-DEFINITIONS  */
/*  Some abbreviations for convencience  */
#define bayTreeUpdate(bt,number,oContent,nContent,mode) \
		bayTreeUpdate2(bt,number,number,oContent,nContent,mode)
#define bayTreeInsert(bt,number,content,mode) \
		bayTreeUpdate(bt,number,NULL,content,mode)
#define bayTreeDelete(bt,number,content,mode) \
		bayTreeUpdate(bt,number,content,NULL,mode)

/*  We do not include mode, since specifying uniqueness doesn't make
 *   sense when only the number is changed. Actually, it will fail,
 *   since content already exists in the tree.
 */
#define bayTreeChSetNr(bt,oNumber,nNumber,content) \
		bayTreeUpdate2(bt,oNumber,nNumber,content,content,0)
/*  END-DEFINITIONS  */
#endif

#define Prototype extern
/*********     PROTOTYPES                                       *********/
Prototype int            bayTreeUpdate2(BayerTree *bt,long oNumber,
					long nNumber,const char *oCont,
					const char *nCont,int mode);

/*JS*********************************************************************
*   Main routine to insert/delete/update fields. Updates the tree entry
*    'oCont' with set number 'oNumber' to 'nCont' with set number 'nNumber'.
*    If BAYTREEM_UNIQUE in mode is set, ensures that the new content is
*    unique in the tree.
*    This routine contains all the required stuff for page splitting and
*    concatenation, tree growth and shrinking due to root-page overflow
*    and underflow.
*************************************************************************/

int bayTreeUpdate2(BayerTree *bt,long oNumber,long nNumber,
		   const char *oCont,const char *nCont,int mode)

/************************************************************************/
{
  BayTreePos *oStack,*nStack;
  int oDepth,nDepth;
  BTreePage page1,subPage;
  char *temp;

  /*  Quick stop: If old and new contents are identical, we are done.
   *   This also prevents us from complaining about non-uniqueness of
   *   the tree node in case that oCont and nCont are identical.
   */
  if(oCont && nCont && (*(bt->BAT_Compare))(bt->BAT_User,nCont,oCont) == 0 &&
     oNumber == nNumber)
    return(0);

  temp = NULL;

  /* ***  Get position where to delete  *** */
  if(oCont == NULL) {
    /*  no old content, means insertion  */
    oDepth = -1;
  } else {
    char *p1,*p2;
    BTreePage page2;
    long pos1,pos2,fLen;
    int sMax;

    if((oDepth = bayTreeSeek(bt,oCont,oNumber,&oStack,bt->BAT_Compare,
			     bt->BAT_User,BAYSEEK_EXACT)) < 0) goto error;

    /*  To delete an element on a non-leaf page: Walk down the tree
     *   until we reach a leaf page, then exchange the element to
     *   delete with the last one on the leaf page. That means in
     *   effect that the actual insertion and deletion in the main
     *   loop below both take place on leaf pages.
     */

    /*  Load page with element to delete and lock it, so we won't loose it  */
    page1 = oStack[oDepth].BTP_PageNr;
    pos1  = oStack[oDepth].BTP_Position;
    if((p1 = bayGetPage(bt,page1,BFILEMODE_DIRTY | BFILEMODE_PROT)) == NULL)
      goto error;

    fLen = BTLEN_FIELD(bt);
    sMax = oDepth; /*  we might have to increase the stack  */
    for(p2 = p1, pos2 = pos1 ; ; ) {
      /*  Leaf page?  */
      if(BTPAGE_ISLEAF(bt,p2)) break;

      /*  Load left sub page  */
      memcpyl(&page2,p2 + (BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt)) +
	      pos2 * fLen,sizeof(page2));

      /*  Load sub page  */
      oDepth++;
      if(oDepth >= sMax) {
	sMax += 10;
	if((oStack = (BayTreePos *)realloc(oStack,sMax * sizeof(*oStack)))
	   == NULL) goto error1;
      }
      if((p2 = bayGetPage(bt,page2,BFILEMODE_DIRTY)) == NULL) goto error1;

      /*  Use last+1 position on intermediate pages  */
      oStack[oDepth].BTP_PageNr = page2;
      oStack[oDepth].BTP_Position = pos2 = BTPAGE_LENGTH(bt,p2);
#ifdef DEBUGD
      printf("  STEPPING down to page %d pos %d\n",page2,pos2);
#endif
    }

    /*  Check if start page wasn't already a leaf page  */
    if(p2 != p1) {
      /*  Adjust position to LAST element on leaf page and move
       *   this element to the one that must be deleted
       */
      oStack[oDepth].BTP_Position = --pos2;
      memcpy(p1 + BTOFF_START(bt) + BTOFF_USER(bt) + pos1 * fLen,
	     p2 + BTOFF_START(bt) + BTOFF_USER(bt) + pos2 * BTLEN_FIELDL(bt),
	     BTLEN_USER(bt));
    }

    /*  Release lock on the page we started with  */
    if(baySetPage(bt,page1,BFILEMODE_UNPROT) < 0) goto error;
  }

  /* ***  Get position where to insert  *** */
  if(nCont == NULL) {
    nDepth = -1;
  } else {
    /*  In finding the position where to insert we check for uniqueness  */
    if((nDepth = bayTreeSeek(bt,nCont,nNumber,&nStack,bt->BAT_Compare,
			     bt->BAT_User,(mode & BAYSEEK_UNIQUE))) < 0 ||
       (temp = (char *)
#ifdef CONFIG_USE_ALLOCA
	alloca(2 * bt->BAT_FieldLength)
#else
	malloc(2 * bt->BAT_FieldLength)
#endif
	) == NULL)
      goto error;

    /*  We use the temporary work space for passing elements up  */
    memcpy(temp,nCont,bt->BAT_FieldLength);
    nCont = temp;
  }

  /* ****  MAIN LOOP  **** */
  subPage = -1;
  while(oDepth >= 0 || nDepth >= 0) {
    /* ***  Handle deletion and insertion on same page  *** */
    if(nDepth == oDepth && nStack[nDepth].BTP_PageNr ==
       oStack[oDepth].BTP_PageNr) {
      char *p;
      long posD,posI,fLen;

      posD = oStack[oDepth].BTP_Position;
      posI = nStack[nDepth].BTP_Position;

#ifdef DEBUGU
      printf("  DEL/INS on same page %ld, posD %ld posI %ld\n",
	     nStack[nDepth].BTP_PageNr,posD,posI);
#endif

      if((p = bayGetPage(bt,nStack[nDepth].BTP_PageNr,BFILEMODE_DIRTY))
	 == NULL) goto error;

      fLen = BTPAGE_ISLEAF(bt,p) ? BTLEN_FIELDL(bt) : BTLEN_FIELD(bt);

      p += BTOFF_START(bt);
      if(posI < posD) {
	/*        | posI    | posD
	 *  ------++++++++++X-------
	 */
	p += posI * fLen;

	/*  Move intermediate elements one position up	*/
	memmove(p + fLen,p,(posD - posI) * fLen);
      } else if(posI > (posD + 1)) {
	long len;

	posI--;

	/*        | posD    | posI
	 *  ------X++++++++++-------
	 */
	p += posD * fLen;

	len = (posI - posD) * fLen;
	memmove(p,p + fLen,len);
	p += len; /*  adjust to position where to insert  */
      } else {
	/*        | posD                      | posD
	 *  ------X----------------- or  -----X-----------------
	 *        | posI                       | posI
	 */
	p += posD * fLen;
      }

      /*  Set up new entry  */
      memcpy(p + BTOFF_CONTENT(bt),nCont,bt->BAT_FieldLength);
      memcpyl(p + BTOFF_SETNR(bt),&nNumber,sizeof(nNumber));

#ifdef CONFIG_BTREE_EXTRALEAF
      if(fLen != BTLEN_FIELDL(bt))
#endif
	memcpyl(p + BTOFF_SUBPAGE(bt),&subPage,sizeof(subPage));

      break; /*  we are done!  */
    }

    /* ***  If on the same level, INSERTION comes first  *** */
    if(nDepth >= oDepth) {
      char *p1,*dest,*next;
      BTreePage nextSub;
      BTreeSetNr nextSetNr;
      long pos,n,fLen,currMax;
      int flag;

#define FLAG_RELEASELOCK   (1<<0)  /*  Release page lock at the end  */
#define FLAG_DIDPAGESPLIT  (1<<1)  /*  A page split occured  */
#define FLAG_DONTINSERT    (1<<2)  /*  Do not insert element on current page */
      flag = 0;
      page1 = nStack[nDepth].BTP_PageNr;
      pos = nStack[nDepth].BTP_Position;
      nextSub = -1; /*  next subpage element  */

      /*  Load page and get its length  */
      if((p1 = bayGetPage(bt,page1,BFILEMODE_DIRTY)) == NULL) goto error;
      n = BTPAGE_LENGTH(bt,p1);

      if(BTPAGE_ISLEAF(bt,p1)) {
	fLen = BTLEN_FIELDL(bt);
	currMax = bt->BAT_MaxElementLeaf;
      } else {
	fLen = BTLEN_FIELD(bt);
	currMax = bt->BAT_MaxElement;
      }

      /*  Check if page splitting is necessary  */
      if(n < currMax) { /* **  Insertion on non-filled pages  ** */
	dest = p1;
	nDepth = 0; /*  insertion finished  */
	next = NULL;
      } else { /* ***  PAGE SPLITTING  *** */
	BTreePage newPage;
	char *p2;

	/*  Lock old page first, otherwise it might get stolen
	 *   when allocating or accessing new pages.
	 */
	if(baySetPage(bt,page1,BFILEMODE_PROT) < 0) goto error;
	flag |= FLAG_RELEASELOCK | FLAG_DIDPAGESPLIT;

	if((newPage = (*(bt->BAT_PageAdmin))(bt,-1)) < 0 ||
	   (p2 = bayGetPage(bt,newPage,BFILEMODE_DIRTY)) == NULL)
	  goto error1;

#ifdef DEBUGI
	printf("  Page %ld split, new page %ld\n",page1,newPage);
#endif

	/*  Half size of old page and set up new one.
	 *  Central element on old page is put one level up, so
	 *   ensure pages will have same size afterwards.
	 */
	n /= 2;
	if(pos < n) {
	  /*  Insertion will be on old page, so decrease its length.
	   *   That ensures that finally both pages have the same
	   *   length.
	   */
	  n--;
	} else if(pos == n) {
	  /*  Special case: the element to insert is the central one
	   *   which is passed one level up.
	   */
	  flag |= FLAG_DONTINSERT;
	}

	/*  Set size of old page  */
	BTPAGE_LENGTH(bt,p1) = n;

	/*  Set up element to pass to next level  */
	if(!(flag & FLAG_DONTINSERT)) {
	  long n2;

	  /*  Central element of pages together is passed up  */
	  BTPAGE_LENGTH(bt,p2) = n2 = currMax - n - 1;

	  dest = p1 + BTOFF_START(bt) + n * fLen;

	  /*  Use second allocated work space for 'next' element
	   *   which will become the element to insert on the
	   *   next iteration.
	   */
	  next = temp + bt->BAT_FieldLength;
	  memcpy(next,dest + BTOFF_CONTENT(bt),bt->BAT_FieldLength);
	  memcpyl(&nextSetNr,dest + BTOFF_SETNR(bt),sizeof(nextSetNr));

	  /*  Set up new page with remaining elements. For the leftmost
	   *   subpage entry use the unused subpage entry of the element
	   *   passed up. Is also true for leaf pages.
	   */
#ifdef CONFIG_BTREE_EXTRALEAF
	  if(BTPAGE_ISLEAF(bt,p1)) {
	    BTPAGE_SUBPAGE0(bt,p2) = -1;
	    memcpy(p2 + BTOFF_START(bt),dest + fLen,n2 * fLen);
	  } else
#endif
	    memcpy(p2 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),dest +
		   BTOFF_SUBPAGEM1(bt) + fLen,n2 * fLen + sizeof(BTreePage));

	  if(pos <= n) {
	    dest = p1;
	  } else {
	    /*  Insert on new page, adjusting insertion position accordingly  */
	    pos -= n + 1; /*  account for lost central element  */
	    dest = p2;
	    n = n2;
	  }
	} else {
	  /*  New page gets all remaining elements from old page  */
	  BTPAGE_LENGTH(bt,p2) = currMax - n;

	  /*  Do not change inserted element, since it is passed up  */
	  next = NULL;

	  /*  Set up new page with remaining elements from old one,
	   *   use 'subPage' for leftmost subpage.
	   */
	  memcpyl(p2 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		  &subPage,sizeof(subPage));
	  memcpy(p2 + BTOFF_START(bt),p1 + BTOFF_START(bt) + n * fLen,
		 (currMax - n) * fLen);
	}

	/*  Subpage for next level  */
	nextSub = newPage;
      }