btreeupdate.c

b tree how to operate on b tr

      if(!(flag & FLAG_DONTINSERT)) {
	char *dest2;

	/* ***  Do actual insertion on a page  *** */
	/*  Set new page length  */
	BTPAGE_LENGTH(bt,dest) = n + 1;

	dest2 = dest + BTOFF_START(bt) + pos * fLen;

	/*  Move contents  */
	if(pos < n) memmove(dest2 + fLen,dest2,(n - pos) * fLen);

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

#ifdef CONFIG_BTREE_EXTRALEAF
	if(!BTPAGE_ISLEAF(bt,dest))
#endif
	  memcpyl(dest2 + BTOFF_SUBPAGE(bt),&subPage,sizeof(subPage));
      }

      subPage = nextSub;

      /*  If page was split, set up element to pass to upper level  */
      if(next) {
	memcpy((char *)nCont,next,bt->BAT_FieldLength);
	nNumber = nextSetNr;
      }

      /*  Finally check if root page was split  */
      if((flag & FLAG_DIDPAGESPLIT) && nDepth == 0) {
	BTreePage newPage;
	char *p2;

	if((newPage = (*(bt->BAT_PageAdmin))(bt,-1)) < 0 ||
	   (p2 = bayGetPage(bt,newPage,BFILEMODE_DIRTY)) == NULL) {
	  if(flag & FLAG_RELEASELOCK) goto error1;
	  goto error;
	}

#ifdef DEBUGI
	printf("  Root page %d split, newpage %d\n",nStack[nDepth].BTP_PageNr,
	       newPage);
#endif

	/*  Copy old root page to allocated one and set up new root page.
	 *   This procedure ensures that the location of the root page
	 *   never changes. The reserved fields are not copied.
	 */
	memcpy(p2,p1,BTPAGE_SIZE(bt) - bt->BAT_Reserved);

	/*  Clear root page, insertion in next iteration
	 *   will set it up correctly.
	 */
	BTPAGE_LENGTH(bt,p1) = 0;
	BTPAGE_SUBPAGE0(bt,p1) = newPage;
	nStack[nDepth].BTP_Position = 0;
      } else
	/*  Go to next level of insertion  */
	nDepth--;

      /*  Release lock for old page  */
      if((flag & FLAG_RELEASELOCK) && baySetPage(bt,page1,BFILEMODE_UNPROT) < 0)
	goto error;
    } else { /* ***  Do DELETION  *** */
      char *p1,*p2,*p3,*p;
      BTreePage page2,page3;
      long pos,fLen,fLen2,currMax,len,flag;

      /*  Load page and delete element  */
      page1 = oStack[oDepth].BTP_PageNr;
      pos  = oStack[oDepth].BTP_Position;
      if((p1 = bayGetPage(bt,page1,BFILEMODE_DIRTY)) == NULL) goto error;

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

#ifdef DEBUGD
      printf("  Delete page %d len %d at pos %d\n",page1,
	     BTPAGE_LENGTH(bt,p1),pos);
#endif

      /*  Decrease number of elements on this page
       *   and delete actual element. Must ensure
       *   that the subpage element of the one to
       *   delete has already been handled.
       */
      len = --BTPAGE_LENGTH(bt,p1);
      p = p1 + BTOFF_START(bt) + pos * fLen;
      if(pos < len) memmove(p,p + fLen,(len - pos) * fLen);

      /*  Does page have still enough elements?  */
      if(len >= (currMax / 2)) {
	oDepth = -1; /*  deletion finished  */
	continue; /*  continue loop, probably we still have to insert?  */
      }

      /*  Underflow on root page?  */
      if(oDepth == 0) {
	/*  If root page is non-empty, stop deleting  */
	if(len == 0) {
	  /* ***  Special case: Root page is empty  *** */
#ifdef DEBUGD
	  printf("  Root page empty!\n");
#endif
	  /*  Get the only remaining leftmost subpage element, which
	   *   is the page that will become the new root page.
	   */
	  memcpyl(&page2,p1 + (BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt)),
		  sizeof(page2));

	  /*  Empty tree reached?  */
	  if(page2 >= 0) {
	    /*  Copy the sub page to the root page and free sub page.
	     *   This again ensures that the position of the root page
	     *   never changes.
	     */
	    if(baySetPage(bt,page1,BFILEMODE_PROT) < 0) goto error;

	    if((p2 = bayGetPage(bt,page2,BFILEMODE_DIRTY)) == NULL)
	      goto error1;

	    memcpy(p1,p2,BTPAGE_SIZE(bt) - bt->BAT_Reserved);

	    /*  Unlock and free page  */
	    if(baySetPage(bt,page1,BFILEMODE_UNPROT) < 0 ||
	       (*(bt->BAT_PageAdmin))(bt,page2) < 0) goto error;
	  }
	}

	oDepth = -1; /*  deletion finished  */
	continue;
      }

      /* **  Handle page concatenation  **
       *
       *               page2
       *                /\
       *               /  \
       *              /    \
       *           page1  page3
       */
      /*  Get parent page  */
      page2 = oStack[oDepth - 1].BTP_PageNr;
      pos   = oStack[oDepth - 1].BTP_Position;

      if(baySetPage(bt,page1,BFILEMODE_PROT) < 0) goto error;
      if((p2 = bayGetPage(bt,page2,BFILEMODE_DIRTY | BFILEMODE_PROT)) == NULL)
	goto error1;

      fLen2 = BTLEN_FIELD(bt); /*  page2 cannot be a leaf page  */

      /*  Are we at the last position on the parent page?  */
      if(pos >= BTPAGE_LENGTH(bt,p2)) {
	/*  Exchange p1 and p3  */
	oStack[oDepth - 1].BTP_Position = --pos;
	flag = TRUE;
      } else {
	flag = FALSE;
      }

      /*  Get right hand side page  */
      if(flag && nDepth >= 0 && nStack[nDepth].BTP_PageNr == page2 &&
	 pos == nStack[nDepth].BTP_Position)
	/*  Special case: While inserting we just split the page left
	 *   to us, so the *real* left hand page is subPage instead
	 *   of the pointer on the page.
	 */
	page3 = subPage;
      else
	/*  Get left (flag==TRUE) or right (flag==FALSE) neighbouring page  */
	memcpyl(&page3,p2 + (BTOFF_START(bt) +
			     (flag ? BTOFF_SUBPAGEM1(bt) : BTOFF_SUBPAGE(bt))) +
		pos * fLen2,sizeof(page3));

      /*  Get neighbouring page  */
      if((p3 = bayGetPage(bt,page3,BFILEMODE_DIRTY)) == NULL) {
	(void)baySetPage(bt,page2,BFILEMODE_UNPROT);
	goto error1;
      }

#ifdef DEBUGD
      printf("  Underflow on page2 %d at pos %d flag %s page3 %d\n",
	     page2,pos,flag ? "YES" : "NO",page3);
#endif

      if(flag) { /*  Exchange left and right page  */
	long tp = page1; page1 = page3; page3 = tp;
	p = p1; p1 = p3; p3 = p;
      }

      /*  Go to position of element on page2  */
      p = p2 + BTOFF_START(bt) + pos * fLen2;

      /*  Check if we can lend elements from the neighbouring page, or if
       *   we can unite them to yield a new one.
       */
      len = BTPAGE_LENGTH(bt,p1) + BTPAGE_LENGTH(bt,p3);
      if(len >= currMax) {
	long newLen,diff;

	newLen = len / 2; /*  page1 will have length newLen afterwards  */

	/*  Redistribute elements  */
	if(BTPAGE_LENGTH(bt,p1) < newLen) {
	  diff = newLen - BTPAGE_LENGTH(bt,p1) - 1;

	  /*  Move the parent element from page2 and some elements from
	   *   page3 to page1. The subpage entry for the single element
	   *   from page2 is taken from the leftmost subpage from page3.
	   */
	  memcpy(p1 + BTOFF_START(bt) + BTOFF_USER(bt) +
		 BTPAGE_LENGTH(bt,p1) * fLen,p + BTOFF_USER(bt),BTLEN_USER(bt));

	  /*  Need to copy at least leftmost subpage element  */
#ifdef CONFIG_BTREE_EXTRALEAF
	  if(BTPAGE_ISLEAF(bt,p1))
	    memcpy(p1 + BTOFF_START(bt) + (BTPAGE_LENGTH(bt,p1) + 1) * fLen,
		   p3 + BTOFF_START(bt),diff * fLen);
	  else
#endif
	    memcpy(p1 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt) +
		   (BTPAGE_LENGTH(bt,p1) + 1) * fLen,
		   p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		   diff * fLen + sizeof(BTreePage));

	  /*  Set new element on page2 and move contents of page3  */
	  memcpy(p + BTOFF_USER(bt),
		 p3 + BTOFF_START(bt) + BTOFF_USER(bt) + diff * fLen,
		 BTLEN_USER(bt));

#ifdef CONFIG_BTREE_EXTRALEAF
	  if(BTPAGE_ISLEAF(bt,p3))
	    memmove(p3 + BTOFF_START(bt),p3 + BTOFF_START(bt) +
		    (diff + 1) * fLen,(BTPAGE_LENGTH(bt,p3) - diff - 1) * fLen);
	  else
#endif
	    memmove(p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		    p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt) +
		    (diff + 1) * fLen,(BTPAGE_LENGTH(bt,p3) - diff - 1) *
		    fLen + sizeof(BTreePage));

	  BTPAGE_LENGTH(bt,p1) += diff + 1;
	  BTPAGE_LENGTH(bt,p3) -= diff + 1;
	} else if(BTPAGE_LENGTH(bt,p3) < newLen) {
	  /*  Move parent element from page2 and some from page1 to page3
	   *   The subpage entry for the single element from page2 is
	   *   taken from the leftmost subpage from page3.
	   */
	  diff = newLen - BTPAGE_LENGTH(bt,p3) - 1;

#ifdef CONFIG_BTREE_EXTRALEAF
	  if(BTPAGE_ISLEAF(bt,p3))
	    memmove(p3 + BTOFF_START(bt) + (diff + 1) * fLen,
		    p3 + BTOFF_START(bt),BTPAGE_LENGTH(bt,p3) * fLen);
	  else
#endif
	    memmove(p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt) +
		    (diff + 1) * fLen,
		    p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		    BTPAGE_LENGTH(bt,p3) * fLen + sizeof(BTreePage));

	  memcpy(p3 + BTOFF_START(bt) + BTOFF_USER(bt) + diff * fLen,
		 p + BTOFF_USER(bt),BTLEN_USER(bt));

	  /*  Need to copy at least leftmost subpage element  */
#ifdef CONFIG_BTREE_EXTRALEAF
	  if(BTPAGE_ISLEAF(bt,p1))
	    memcpy(p3 + BTOFF_START(bt),p1 + BTOFF_START(bt) +
		   (BTPAGE_LENGTH(bt,p1) - diff) * fLen,diff * fLen);
	  else
#endif
	    memcpy(p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		   p1 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt) +
		   (BTPAGE_LENGTH(bt,p1) - diff) * fLen,
		   diff * fLen + sizeof(BTreePage));

	  /*  Set new element on page2 and move contents of page3  */
	  memcpy(p + BTOFF_USER(bt),
		 p1 + BTOFF_START(bt) + BTOFF_USER(bt) +
		 (BTPAGE_LENGTH(bt,p1) - diff - 1) * fLen,BTLEN_USER(bt));

	  BTPAGE_LENGTH(bt,p1) -= diff + 1;
	  BTPAGE_LENGTH(bt,p3) += diff + 1;
	}

	oDepth = -1; /*  stop deleting  */
      } else {
	/* **  We can decrease the number of pages  ** */
#ifdef DEBUGD
	printf("  CONCAT PAGES %d: %d %d , %d\n",page1,
	       BTPAGE_LENGTH(bt,p1),BTPAGE_LENGTH(bt,p3),len + 1);
#endif

	/*
	 *  Move single parent element from page2 and all elements
	 *   from page3 to page1. The subpage entry for the element
	 *   from page2 is taken from the leftmost subpage from page3.
	 */
	memcpy(p1 + BTOFF_START(bt) + BTOFF_USER(bt) +
	       BTPAGE_LENGTH(bt,p1) * fLen,
	       p + BTOFF_USER(bt),BTLEN_USER(bt));
#ifdef CONFIG_BTREE_EXTRALEAF
	if(BTPAGE_ISLEAF(bt,p1))
	  memcpy(p1 + BTOFF_START(bt) + (BTPAGE_LENGTH(bt,p1) + 1) * fLen,
		 p3 + BTOFF_START(bt),BTPAGE_LENGTH(bt,p3) * fLen);
	else
#endif
	  memcpy(p1 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt) +
		 (BTPAGE_LENGTH(bt,p1) + 1) * fLen,
		 p3 + BTOFF_START(bt) + BTOFF_SUBPAGEM1(bt),
		 BTPAGE_LENGTH(bt,p3) * fLen + sizeof(BTreePage));

	/*  Concatenated page now contains all elements.  */
	BTPAGE_LENGTH(bt,p1) = len + 1;

	/*  Free the neighbouring page and unlock other one  */
	if((*(bt->BAT_PageAdmin))(bt,page3) < 0) {
	  (void)baySetPage(bt,page2,BFILEMODE_UNPROT);
	  if(flag) page1 = page3;
	  goto error1;
	}

	/*  Go to next level  */
	oDepth--;
      }

      /*  Remove all page locks  */
      if(baySetPage(bt,flag ? page3 : page1,BFILEMODE_UNPROT) < 0 ||
	 baySetPage(bt,page2,BFILEMODE_UNPROT) < 0) goto error;
    }
  }
  /* ****  END MAIN LOOP  **** */

  if(oCont) free(oStack);
  if(nCont) free(nStack);

#ifndef CONFIG_USE_ALLOCA
  if(temp) free(temp);
#endif

  return(0);
error1:
  /*  Clean up: Unlock page1 before return  */
  (void)baySetPage(bt,page1,BFILEMODE_UNPROT);
error:
#ifndef CONFIG_USE_ALLOCA
  free(temp);
#endif
  return(-1);
}