home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / APPS / hl10osrc.lzh / Lib / vBTree.cc < prev    next >
Text File  |  1994-04-23  |  27KB  |  950 lines
  1. /* -*- Mode: C -*- */
  2. /* vBTree.cc - (virtual) BTree implementation
  3.  *        This code was heavily inspired by the BTree class
  4.  *        described in chapter 10 of "C++, a guide for C programmers",
  5.  *        by Sharam Hekmatpour, (c) 1990 by Prentice Hall of
  6.  *        Australia Pty Ltd.
  7.  * Created by Robert Heller on Sat Dec  7 20:59:18 1991
  8.  *
  9.  * ------------------------------------------------------------------
  10.  * Home Libarian by Deepwoods Software
  11.  * Common Class library implementation code
  12.  * ------------------------------------------------------------------
  13.  * Modification History:
  14.  * ------------------------------------------------------------------
  15.  * Contents:
  16.  * ------------------------------------------------------------------
  17.  * 
  18.  * 
  19.  * Copyright (c) 1991,1992 by Robert heller (D/B/A Deepwoods Software)
  20.  *        All Rights Reserved
  21.  * 
  22.  */
  23. #include <stream.h>
  24. #include <vBTree.h>
  25. #include <ctype.h>
  26.  
  27. // This function is for debugging.  It formats a page for inspection.
  28. // (Needed since g++ for OSK does not generate any usefull debugging
  29. // info for Microware's srcdbg.
  30. static void DumpPage (Page* page)
  31. {
  32.     cout << form("*** Page* at 0x%08x:\n",page);
  33.     cout << form("    ->size = %d\n",page->size);
  34.     cout << form("    ->left.record_address = %d\n",
  35.             page->left.record_address);
  36.     cout << form("    ->parent.record_address = %d\n",
  37.             page->parent.record_address);
  38.     cout << form("    ->parentidx = %d\n",page->parentidx);
  39.     for (int i = 0; i < page->size; i++) {
  40.         cout << form("    ->items[%d].key = %s\n",i,page->items[i].key);
  41.         cout << form("    ->items[%d].data = [%d:%d]\n",i,
  42.                 page->items[i].data.record_size,
  43.                 page->items[i].data.record_address);
  44.         cout << form("    ->items[%d].right.record_address = %d\n",i,
  45.                 page->items[i].right.record_address);
  46.     }
  47. }
  48.  
  49. static void dumphome(const HomeBlock* block,const char* message)
  50. {
  51.     cerr << "\nHomeBlock (" << message << "):\n\n";
  52.     unsigned char* p = (unsigned char*) block;
  53.     cerr <<
  54.     "  Addr     0 1  2 3  4 5  6 7  8 9  A B  C D  E F 0 2 4 6 8 A C E\n" <<
  55.     "--------  ---- ---- ---- ---- ---- ---- ---- ---- ----------------\n";
  56.     for (int i = 0; i < sizeof(HomeBlock); i += 16, p += 16) {
  57.         cerr << form("%08x ",i);
  58.         for (int j = 0; j < 16; j += 2) {
  59.             cerr << form(" %02.2x%02.2x",p[j] & 0x0FF,
  60.                              p[j+1] & 0x0FF);
  61.         }
  62.         cerr << " ";
  63.         for (j = 0; j < 16; j++) {
  64.             char c = p[j];
  65.             if (c >= ' ' && c <= '~') cerr << c;
  66.             else cerr << ".";
  67.         }
  68.         cerr << "\n";
  69.     }
  70. }
  71.  
  72. // Basic constructor.  Does not actually open the file, just sets things up.
  73. vBTree::vBTree() {
  74.     LastSearchType = none;
  75.     homedirty = false;
  76.     buf = new Item[2*Order + 2];
  77. }
  78.  
  79. // This constructor also opens the file.
  80. vBTree::vBTree(char *filename,OpenMode mode,int nfree) 
  81. {
  82.     LastSearchType = none;
  83.     homedirty = false;
  84.     buf = new Item[2*Order + 2];
  85.     open(filename,mode,nfree);
  86. }
  87.  
  88. // Open a vBTree file (library card catalog file)
  89. OpenStatus vBTree::open(char *filename, OpenMode mode,int nfree)
  90. {
  91.     // Figure type of access and whether we should try to create a
  92.     // new file, if the file does not exist.
  93.     if ((mode & ModeMask) == ReadWrite) {
  94.         openstat = PageFile::open(filename, inout, ReadWriteFlags,
  95.                       ReadWriteMode, 
  96.                       ((mode & Create) != 0) ?  true :
  97.                                     false);
  98.     } else {
  99.         openstat = PageFile::open(filename, in, ReadFlags, ReadMode,
  100.                       false);
  101.     }
  102.     // File might have been opened.  Fan out based on how PageFile::open
  103.     // fared.
  104.     switch (openstat) {
  105.         case openold :        // An existing file was opened.
  106.                     // Read in the home block and
  107.                     // set things up.
  108.             DiskRecord homerecord(sizeof(HomeBlock),0L);
  109.             if (PageFile::ReadRecord(homerecord,
  110.                          (char *) &homeblock,
  111.                          sizeof(HomeBlock)) <
  112.                 sizeof(HomeBlock)) {
  113.                     PageFile::close();
  114.                     return(openstat = failure);
  115.             }
  116.             // Is it really a library file??
  117.             if (strncmp(homeblock.magic,homeblock.Magic,8) != 0) {
  118.                 PageFile::close();
  119.                     return(openstat = failure);
  120.             }
  121.             // Home block is fresh and clean
  122.             homedirty = false;
  123.             // All set.
  124.             return(openstat);
  125.         case opennew :            // new file.  Initialize the
  126.                         // file with a specified
  127.                         // number of free pages
  128.                         // and a properly intialized
  129.                         // home block.
  130.             if (nfree > MaxNumFree) nfree = MaxNumFree;
  131.             else if (nfree < 0) nfree = 0;
  132.             strncpy(homeblock.magic,homeblock.Magic,8);
  133.             homeblock.IdRoot = 0L;
  134.             homeblock.TitleRoot = 0L;
  135.             homeblock.AuthorRoot = 0L;
  136.             homeblock.SubjRoot = 0L;
  137.             homeblock.numfree = 0;
  138.             // pre-write home block (tie up first "sector"
  139.             // so it won't get used as a page).
  140.             PageFile::WriteRecord((char *) &homeblock,
  141.                           sizeof(HomeBlock));
  142.             // get a bunch of free pages
  143.             for (int i = nfree-1; i >= 0; i--) {
  144.                 homeblock.freepages[i] = PageFile::NewPage();
  145.             }
  146.             // note the number of available pages
  147.             homeblock.numfree = nfree;
  148.             // the home block is already dirty...
  149.             homedirty = true;
  150.             //dumphome(&homeblock,"open (new file)");
  151.             // all set.
  152.             return(openstat);
  153.         case failure: return(openstat);    // PageFile::open() failed.
  154.     }
  155. }
  156.  
  157. // Destructor.  Close file and generally clean up
  158. vBTree::~vBTree()
  159. {
  160.     if (isopen) {        // if file is open...
  161.         if (homedirty == true) {    // home block needs writing??
  162.             //dumphome(&homeblock,"Closing, updating homeblock");
  163.             // yep.  rewrite it.
  164.             DiskRecord homerecord(sizeof(HomeBlock),0L);
  165.             PageFile::ReWriteRecord(homerecord,
  166.                         (char *) &homeblock,
  167.                         sizeof(HomeBlock));
  168.         }
  169.         // Close file.  (dirty pages will get written out)
  170.         PageFile::close();
  171.         //delete[2*Order + 2] buf;    // this crashes under OSK...
  172.     }
  173. }
  174.  
  175. // Free up a disk page.
  176. void vBTree::FreePage (DiskPage dpage)
  177. {
  178.     if (dpage != 0) {
  179.         if (homeblock.numfree == MaxNumFree) return;
  180.         for (int i = 0; i < homeblock.numfree; i++)
  181.             if (homeblock.freepages[i] == dpage) return;
  182.         homeblock.freepages[homeblock.numfree++] = dpage;
  183.         homedirty = true;
  184.         //dumphome(&homeblock,"FreePage");
  185.     }
  186. }
  187.  
  188. // allocate a new disk page.
  189. DiskPage vBTree::NewPage()
  190. {
  191.     if (homeblock.numfree > 0) {    // any reuseable pages??
  192.         homeblock.numfree--;
  193.         homedirty = true;
  194.         //dumphome(&homeblock,"NewPage");
  195.         return (homeblock.freepages[homeblock.numfree]);
  196.     } else return (PageFile::NewPage());    // nope, get a new one
  197. }
  198.  
  199. // Main searching function.  I've modified things to remember where we found
  200. // match. My key compare function matches proper prefixes and I've added a
  201. // search again function - allows the user to only give a prefix and find
  202. // all matches.
  203. Boolean vBTree::SearchAux(DiskPage dtree, Key key, register CoreItem* item)
  204. {
  205.     int idx;
  206.     Page *tree;
  207.  
  208.     if (dtree == 0) {            // fell through on exact match
  209.                         // maybe a prefix matched...
  210.         if (LastSearchIdx >= 0) {
  211.             // yep.  save state and return match.
  212.             strncpy(LastSearchKey,key,KeySize);
  213.             tree = (*this)[LastSearchPage];    // page in page
  214.             // copy actual key
  215.             strcpy(item->key,tree->items[LastSearchIdx].key);
  216.             // allocate a buffer and read in the data record
  217.             item->data.NewBuffer(tree->items[LastSearchIdx].data.record_size);
  218.             int bytesread =
  219.             PageFile::ReadRecord(tree->items[LastSearchIdx].data,
  220.                      item->data.buffer,item->data.size);
  221.             // I/O error?  report error and return empty buffer
  222.             if (bytesread < 0) {
  223.                 Error(sysErr,"PageFile::ReadRecord");
  224.                 item->data.NewBuffer(0);
  225.             }
  226.             // success
  227.             return true;
  228.         } else {    // nope.  search over.  
  229.             LastSearchType = none;
  230.             return false;
  231.         }
  232.     }
  233.     LastSearchPage = dtree;        // remember where er are
  234.     tree = (*this)[dtree];        // page in page
  235.     if (BinarySearch(tree,key,&idx)) {    // is key on this page??
  236.         // yep.  return key and data
  237.         strcpy(item->key,tree->items[idx].key);
  238.         item->data.NewBuffer(tree->items[idx].data.record_size);
  239.         int bytesread =
  240.         PageFile::ReadRecord(tree->items[idx].data,
  241.                  item->data.buffer,item->data.size);
  242.         if (bytesread < 0) {
  243.             Error(sysErr,"PageFile::ReadRecord");
  244.             item->data.NewBuffer(0);
  245.         }
  246.         // save state
  247.         strncpy(LastSearchKey,key,KeySize);
  248.         LastSearchIdx = idx;
  249.         // success
  250.         return true;
  251.     }
  252.     // not here.  descend down the tree.
  253.     return SearchAux((idx < 0 ? tree->left
  254.                   : tree->items[idx].right),key,item);
  255. }
  256.  
  257. // Binary search function
  258. Boolean vBTree::BinarySearch (Page *node, Key key, int *idx)
  259. {
  260.     int low = 0;
  261.     int up = node->size - 1;
  262.     register int mid, comp;
  263.     register Boolean found, exact;
  264.     do {                    // binary chop
  265.         mid = (low + up) / 2;
  266.         comp = CompareKeys(key,node->items[mid].key);
  267.         exact = comp==0 && strlen(key) == strlen(node->items[mid].key);
  268.         if (comp==0) LastSearchIdx = mid; // state preservation
  269.         if (comp==0 && !exact) comp = -1; // make sure we get
  270.                           // the leftmost match
  271.         if (comp <= 0) up = mid - 1;    // restrict to lower half
  272.         if (comp >= 0) low = mid + 1;    // restrict to upper half
  273.     } while (low <= up);
  274.     *idx = (found = low - up > 1) ? mid : up;
  275.     return (found);
  276. }
  277.  
  278. // Key comparison function.  Will return 0 if keypat is a proper prefix
  279. // of key.  Otherwise it behaves simularly to strcmp(), except it does
  280. // a case insensitive comparison.
  281. int vBTree::CompareKeys(Key keypat,Key key)
  282. {
  283.     char *p = keypat, *k = key;
  284.     int ch, comp;
  285.  
  286.     if (*p == '\0') return(0);
  287.     do {
  288.         ch = *p++;
  289.         if (isalpha(ch) && islower(ch)) ch = toupper(ch);
  290.         comp = ch - *k++;
  291.     } while (comp == 0 && *p != '\0');
  292.     return (comp);
  293. }
  294.  
  295. // This function continues the search (prefix string matching)
  296. Boolean vBTree::SearchAgain(register CoreItem* item)
  297. {
  298.     Page *tree;
  299.     int comp;
  300.     int idx, tidx;
  301.     DiskPage tpage;
  302.     LSType ttype;
  303.     
  304.     // remember place
  305.     //cerr << "*** Entering SearchAgain: LastSearchPage = " <<
  306.     //    LastSearchPage.record_address <<
  307.     //    "LastSearchIdx = " << LastSearchIdx << "\n";
  308.     tpage = LastSearchPage;
  309.     tidx = LastSearchIdx;
  310.     ttype = LastSearchType;
  311.     tree = (*this)[LastSearchPage];        // page in page
  312.     if (LastSearchIdx >= 0 &&        // a real index?
  313.         tree->items[LastSearchIdx].right != 0) {    // a child??
  314.         // decend the tree to the right
  315.         LastSearchPage = tree->items[LastSearchIdx].right;
  316.         LastSearchIdx  = -1;        // left most node
  317.         // recurse...
  318.         if (SearchAgain(item)) return(true);
  319.         // failed.  reset
  320.         LastSearchPage = tpage;
  321.         LastSearchIdx = tidx;
  322.         LastSearchType = ttype;
  323.     }
  324.     // next node to the right
  325.     idx = ++LastSearchIdx;
  326.     // nodes remaining??
  327.     if (idx < tree->size) {
  328.         // yep.  does this node match??
  329.         comp = CompareKeys(LastSearchKey,tree->items[idx].key);
  330.         if (comp < 0) {
  331.             // nope.  we are done...
  332.             LastSearchType = none;
  333.             return (false);
  334.         }
  335.         // yep.  return it.
  336.         strcpy(item->key,tree->items[LastSearchIdx].key);
  337.         item->data.NewBuffer(tree->items[LastSearchIdx].data.record_size);
  338.         int bytesread =
  339.         PageFile::ReadRecord(tree->items[LastSearchIdx].data,
  340.                  item->data.buffer,item->data.size);
  341.         if (bytesread < 0) {
  342.             Error(sysErr,"PageFile::ReadRecord");
  343.             item->data.NewBuffer(0);
  344.         }
  345.         // we are all set for next time
  346.         return (true);
  347.     } else {    // no more items here.  pop up and try next item
  348.             // in parent
  349.         if (tree->parent == 0) {    // if any...
  350.             // no parent.  end of the line..
  351.             LastSearchType = none;
  352.             return(false);
  353.         } else {
  354.             // up and to the right...
  355.             LastSearchPage = tree->parent;
  356.             LastSearchIdx  = tree->parentidx+1;
  357.             return (SearchAgain(item));
  358.         }
  359.     }
  360. }
  361.  
  362. // helper function for InsertXXX
  363. // copy a key, converting to uppercase and truncating to fit.
  364. static strucase(Key dest, Key source)
  365. {
  366.     char ch, *a, *b;
  367.     int i;
  368.  
  369.     for (a=source,b=dest,i=1; *a != '\0' && i < KeySize; a++,b++,i++) {
  370.         ch = *a;
  371.         if (isalpha(ch) && islower(ch)) ch = toupper(ch);
  372.         *b = ch;
  373.     }
  374.     *b = '\0';
  375. }    
  376.  
  377. // Insertion function for the Id tree
  378. DiskRecord vBTree::InsertId (Key key,Record* newdata)
  379. {
  380.     Item *receive, item;
  381.     Page *page, *root;
  382.     DiskPage dpage;
  383.     // copy the key
  384.     strucase(item.key,key);
  385.     // and write the data out
  386.     item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
  387.     item.right = 0;
  388.     if (homeblock.IdRoot == 0) {        // empty tree
  389.         homeblock.IdRoot = NewPage();
  390.         homedirty = true;
  391.         root = (*this)[homeblock.IdRoot];
  392.         root->left = 0;
  393.         root->parent = 0;
  394.         root->parentidx = -1;
  395.         root->items[0] = item;
  396.         root->size = 1;
  397.         (*this)(homeblock.IdRoot).isdirty = true;
  398.         //dumphome(&homeblock,"InsertId (new tree)");
  399.     } else if ((receive = InsertAux(&item,homeblock.IdRoot)) != 0) {
  400.         dpage = NewPage();        // new root
  401.         page = (*this)[dpage];
  402.         page->size = 1;
  403.         page->left = homeblock.IdRoot;
  404.         page->parent = 0;
  405.         page->parentidx = -1;
  406.         page->items[0] = *receive;
  407.         AdjustParent(dpage);        // fixup this node's offspring
  408.                         // to point back.
  409.         (*this)(dpage).isdirty = true;
  410.         root = (*this)[homeblock.IdRoot];
  411.         root->parent = dpage;
  412.         root->parentidx = -1;
  413.         (*this)(homeblock.IdRoot).isdirty = true;
  414.         homeblock.IdRoot = dpage;
  415.         homedirty = true;
  416.         //dumphome(&homeblock,"InsertId (new root)");
  417.     }
  418.     return(item.data);
  419. }
  420.  
  421. // Insertion for the Title tree
  422. DiskRecord vBTree::InsertTitle (Key key,Record* newdata)
  423. {
  424.     Item *receive, item;
  425.     Page *page, *root;
  426.     DiskPage dpage;
  427.     strucase(item.key,key);
  428.     item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
  429.     item.right = 0;
  430.     if (homeblock.TitleRoot == 0) {
  431.         homeblock.TitleRoot = NewPage();
  432.         homedirty = true;
  433.         root = (*this)[homeblock.TitleRoot];
  434.         root->left = 0;
  435.         root->parent = 0;
  436.         root->parentidx = -1;
  437.         root->items[0] = item;
  438.         root->size = 1;
  439.         (*this)(homeblock.TitleRoot).isdirty = true;
  440.         //dumphome(&homeblock,"InsertTitle (new tree)");
  441.     } else if ((receive = InsertAux(&item,homeblock.TitleRoot)) != 0) {
  442.         dpage = NewPage();
  443.         page = (*this)[dpage];
  444.         page->size = 1;
  445.         page->left = homeblock.TitleRoot;
  446.         page->parent = 0;
  447.         page->parentidx = -1;
  448.         page->items[0] = *receive;
  449.         AdjustParent(dpage);
  450.         (*this)(dpage).isdirty = true;
  451.         root = (*this)[homeblock.TitleRoot];
  452.         root->parent = dpage;
  453.         root->parentidx = -1;
  454.         (*this)(homeblock.TitleRoot).isdirty = true;
  455.         homeblock.TitleRoot = dpage;
  456.         homedirty = true;
  457.         //dumphome(&homeblock,"InsertTitle (new root)");
  458.     }
  459.     return(item.data);
  460. }
  461.  
  462. // Insertion for the Author tree
  463. DiskRecord vBTree::InsertAuthor (Key key,Record* newdata)
  464. {
  465.     Item *receive, item;
  466.     Page *page, *root;
  467.     DiskPage dpage;
  468.     strucase(item.key,key);
  469.     item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
  470.     item.right = 0;
  471.     if (homeblock.AuthorRoot == 0) {
  472.         homeblock.AuthorRoot = NewPage();
  473.         homedirty = true;
  474.         root = (*this)[homeblock.AuthorRoot];
  475.         root->left = 0;
  476.         root->parent = 0;
  477.         root->parentidx = -1;
  478.         root->items[0] = item;
  479.         root->size = 1;
  480.         (*this)(homeblock.AuthorRoot).isdirty = true;
  481.         //dumphome(&homeblock,"InsertAuthor (new tree)");
  482.     } else if ((receive = InsertAux(&item,homeblock.AuthorRoot)) != 0) {
  483.         dpage = NewPage();
  484.         page = (*this)[dpage];
  485.         page->size = 1;
  486.         page->left = homeblock.AuthorRoot;
  487.         page->parent = 0;
  488.         page->parentidx = -1;
  489.         page->items[0] = *receive;
  490.         AdjustParent(dpage);
  491.         (*this)(dpage).isdirty = true;
  492.         root = (*this)[homeblock.AuthorRoot];
  493.         root->parent = dpage;
  494.         root->parentidx = -1;
  495.         (*this)(homeblock.AuthorRoot).isdirty = true;
  496.         homeblock.AuthorRoot = dpage;
  497.         homedirty = true;
  498.         //dumphome(&homeblock,"InsertAuthor (new root)");
  499.     }
  500.     return(item.data);
  501. }
  502.  
  503. // Insertion for the Subject tree
  504. DiskRecord vBTree::InsertSubj (Key key,Record* newdata)
  505. {
  506.     Item *receive, item;
  507.     Page *page, *root;
  508.     DiskPage dpage;
  509.     strucase(item.key,key);
  510.     item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
  511.     item.right = 0;
  512.     if (homeblock.SubjRoot == 0) {
  513.         homeblock.SubjRoot = NewPage();
  514.         homedirty = true;
  515.         root = (*this)[homeblock.SubjRoot];
  516.         root->left = 0;
  517.         root->parent = 0;
  518.         root->parentidx = -1;
  519.         root->items[0] = item;
  520.         root->size = 1;
  521.         (*this)(homeblock.SubjRoot).isdirty = true;
  522.         //dumphome(&homeblock,"InsertSubj (new tree)");
  523.     } else if ((receive = InsertAux(&item,homeblock.SubjRoot)) != 0) {
  524.         dpage = NewPage();
  525.         page = (*this)[dpage];
  526.         page->size = 1;
  527.         page->left = homeblock.SubjRoot;
  528.         page->parent = 0;
  529.         page->parentidx = -1;
  530.         page->items[0] = *receive;
  531.         AdjustParent(dpage);
  532.         (*this)(dpage).isdirty = true;
  533.         root = (*this)[homeblock.SubjRoot];
  534.         root->parent = dpage;
  535.         root->parentidx = -1;
  536.         (*this)(homeblock.SubjRoot).isdirty = true;
  537.         homeblock.SubjRoot = dpage;
  538.         homedirty = true;
  539.         //dumphome(&homeblock,"InsertSubj (new root)");
  540.     }
  541.     return(item.data);
  542. }
  543.  
  544. // Common helper function for Inserting
  545. Item* vBTree::InsertAux (Item* item, DiskPage dnode)
  546. {
  547.     register Page* node = (*this)[dnode];
  548.     int idx, size, half;
  549.  
  550.     if (BinarySearch(node,item->key,&idx)) {
  551.         // Modified to allow replacement
  552.         node->items[idx].data = item->data;
  553.         (*this)(dnode).isdirty = true;
  554.         return(0);        // already in tree
  555.     }
  556.     DiskPage dchild = (idx < 0 ? node->left : node->items[idx].right);
  557.     if (dchild != 0) item = InsertAux(item,dchild);    // child is not e leaf
  558.     // node is a leaf or passed up
  559.     if (item != 0) {
  560.         node = (*this)[dnode];
  561.         if  (node->size < 2*Order) {    // insert in the node
  562.             node->size = InsertItem(item,node->items,idx+1,
  563.                         node->size);
  564.             AdjustParent(dnode);
  565.             (*this)(dnode).isdirty = true;
  566.         } else {        // node is full, split
  567.             DiskPage dpage =  NewPage();
  568.             register Page* page;
  569.             node = (*this)[dnode];
  570.             size = CopyItems(node->items, buf, node->size);
  571.             size = InsertItem(item,buf,idx+1,size);
  572.             node->size  = CopyItems(buf,node->items,half=size/2);
  573.             (*this)(dnode).isdirty = true;
  574.             page = (*this)[dpage];
  575.             page->size  = CopyItems(buf+half+1,page->items,size-half-1);
  576.             page->left =  buf[half].right;
  577.             (*this)(dpage).isdirty = true;
  578.             *item = buf[half];    // the mid item
  579.             item->right = dpage;
  580.             return(item);
  581.         }
  582.     }
  583.     return(0);
  584. }
  585.  
  586. // Deletion for Id tree...
  587. void vBTree::DeleteId (Key key)
  588. {
  589.     Boolean underflow;
  590.     DiskPage dtemp;
  591.     if (homeblock.IdRoot == 0) return;
  592.     DeleteAux1(key,homeblock.IdRoot,&underflow);
  593.     Page *root = (*this)[homeblock.IdRoot];
  594.     if (underflow && root->size == 0)  {    // dispose root
  595.         dtemp = homeblock.IdRoot;
  596.         homeblock.IdRoot = root->left;
  597.         homedirty = true;
  598.         FreePage(dtemp);
  599.         //dumphome(&homeblock,"DeleteId (new root)");
  600.         if (homeblock.IdRoot == 0) return;        
  601.         root = (*this)[homeblock.IdRoot];
  602.         root->parent = 0;
  603.         root->parentidx = 0;
  604.         (*this)(homeblock.IdRoot).isdirty = true;
  605.     }
  606. }
  607.  
  608. // Deletion for Title tree
  609. void vBTree::DeleteTitle (Key key)
  610. {
  611.     Boolean underflow;
  612.     DiskPage dtemp;
  613.     if (homeblock.TitleRoot == 0) return;
  614.     DeleteAux1(key,homeblock.TitleRoot,&underflow);
  615.     Page *root = (*this)[homeblock.TitleRoot];
  616.     if (underflow && root->size == 0)  {        // dispose root
  617.         dtemp = homeblock.TitleRoot;
  618.         homeblock.TitleRoot = root->left;
  619.         homedirty = true;
  620.         FreePage(dtemp);
  621.         //dumphome(&homeblock,"DeleteTitle (new root)");
  622.         if (homeblock.TitleRoot == 0) return;
  623.         root = (*this)[homeblock.TitleRoot];
  624.         root->parent = 0;
  625.         root->parentidx = 0;
  626.         (*this)(homeblock.TitleRoot).isdirty = true;
  627.     }
  628. }
  629.  
  630. // Deletion for Author tree...
  631. void vBTree::DeleteAuthor (Key key)
  632. {
  633.     Boolean underflow;
  634.     DiskPage dtemp;
  635.     if (homeblock.AuthorRoot == 0) return;
  636.     DeleteAux1(key,homeblock.AuthorRoot,&underflow);
  637.     Page *root = (*this)[homeblock.AuthorRoot];
  638.     if (underflow && root->size == 0)  {        // dispose root
  639.         dtemp = homeblock.AuthorRoot;
  640.         homeblock.AuthorRoot = root->left;
  641.         homedirty = true;
  642.         FreePage(dtemp);
  643.         //dumphome(&homeblock,"DeleteAuthor (new root)");
  644.         if (homeblock.AuthorRoot == 0) return;
  645.         root = (*this)[homeblock.AuthorRoot];
  646.         root->parent = 0;
  647.         root->parentidx = 0;
  648.         (*this)(homeblock.AuthorRoot).isdirty = true;
  649.     }
  650. }
  651.  
  652. // Deletion for Subject tree
  653. void vBTree::DeleteSubj (Key key)
  654. {
  655.     Boolean underflow;
  656.     DiskPage dtemp;
  657.     if (homeblock.SubjRoot == 0) return;
  658.     DeleteAux1(key,homeblock.SubjRoot,&underflow);
  659.     Page *root = (*this)[homeblock.SubjRoot];
  660.     if (underflow && root->size == 0)  {        // dispose root
  661.         dtemp = homeblock.SubjRoot;
  662.         homeblock.SubjRoot = root->left;
  663.         homedirty = true;
  664.         FreePage(dtemp);
  665.         //dumphome(&homeblock,"DeleteSubj (new root)");
  666.         if (homeblock.SubjRoot == 0) return;
  667.         root = (*this)[homeblock.SubjRoot];
  668.         root->parent = 0;
  669.         root->parentidx = 0;
  670.         (*this)(homeblock.SubjRoot).isdirty = true;
  671.     }
  672. }
  673.  
  674. // First helper function for deleting
  675. void vBTree::DeleteAux1(Key key, DiskPage dnode, Boolean* underflow)
  676. {
  677.     Page *node;
  678.     DiskPage dchild;
  679.     int idx;
  680.  
  681.     *underflow = false;
  682.     if (dnode == 0) return;
  683.     node = (*this)[dnode];
  684.     if (BinarySearch(node,key,&idx)) {
  685.         dchild = (idx - 1 < 0 ? node->left
  686.                       : node->items[idx-1].right);
  687.         if (dchild == 0) {
  688.             // node is a leaf
  689.             node->size = DeleteItem(node->items,idx,node->size);
  690.             (*this)(dnode).isdirty = true;
  691.             *underflow = node->size < Order;
  692.         } else {    // node is a subtree
  693.             // delete from subtree
  694.             DeleteAux2(dnode,dchild,idx,underflow);
  695.             if (*underflow)
  696.                 Underflow(dnode,dchild,idx-1,underflow);
  697.         }
  698.     } else {        // is not in this node
  699.         dchild = (idx < 0 ? node->left : node->items[idx].right);
  700.         DeleteAux1(key,dchild,underflow);    // should be in child
  701.         if (*underflow)
  702.             Underflow(dnode,dchild,idx,underflow);
  703.     }
  704. }
  705.  
  706. // Second helper function, subtree deletion
  707. void vBTree::DeleteAux2 (DiskPage dparent, DiskPage dnode, int idx, Boolean* underflow)
  708. {
  709.     Page* node = (*this)[dnode];
  710.     DiskPage dchild;
  711.     Page* child;
  712.  
  713.     dchild = node->items[node->size-1].right;
  714.     if (dchild != 0) {    // node is not is leaf
  715.         child = (*this)[dchild];
  716.         // go another level down
  717.         DeleteAux2(dparent,dchild,idx,underflow);
  718.         node = (*this)[dnode];
  719.         if (*underflow)
  720.             Underflow(dnode,dchild,node->size-1,underflow);
  721.     } else {        // node is a leaf
  722.         DiskPage dright;
  723.         Page* parent = (*this)[dparent];
  724.         node = (*this)[dnode];
  725.         dright = parent->items[idx].right;
  726.         parent->items[idx] = node->items[node->size-1];
  727.         parent->items[idx].right  = dright;
  728.         (*this)(dparent).isdirty = true;
  729.         node->size = DeleteItem(node->items,node->size-1,node->size);
  730.         (*this)(dnode).isdirty = true;
  731.         *underflow = node->size < Order;
  732.     }
  733. }
  734.  
  735. // Underflow handler...
  736. void vBTree::Underflow (DiskPage dnode, DiskPage dchild,int idx,Boolean* underflow)
  737. {
  738.     register Page* node = (*this)[dnode];
  739.     DiskPage dleft;
  740.     if (idx < ((node->size)-1))
  741.         dleft = dchild;
  742.     else {
  743.         if (idx == 0) dleft = node->left;
  744.         else {
  745.             int prev = idx-1;
  746.             //cout << "Taking prev = " << prev << "\n";
  747.             dleft = node->items[prev].right;
  748.         }
  749.     }
  750.     register Page* left;
  751.     DiskPage dright;
  752.     if (dleft == dchild) {
  753.         idx++;
  754.         node = (*this)[dnode];
  755.         dright = node->items[idx].right;
  756.     } else dright = dchild;
  757.     register Page* right;
  758.     register int size, half;
  759.     // copy contents of the left, parent, and right into buf
  760.     left = (*this)[dleft];
  761.     size = CopyItems(left->items,buf,left->size);
  762.     node = (*this)[dnode];
  763.     buf[size] =  node->items[idx];
  764.     right = (*this)[dright];
  765.     buf[size++].right = right->left;
  766.     size += CopyItems(right->items,buf+size,right->size);
  767.     if (size > 2*Order) {    // distribute buf between the left and right
  768.         left = (*this)[dleft];
  769.         left->size = CopyItems(buf,left->items,half = size/2);
  770.         AdjustParent(dleft);
  771.         (*this)(dleft).isdirty = true;
  772.         right = (*this)[dright];
  773.         right->size = CopyItems(buf+half+1,right->items,size-half-1);
  774.         right->left = buf[half].right;
  775.         AdjustParent(dright);
  776.         right = (*this)[dright];
  777.         right->parent = dnode;
  778.         right->parentidx = idx;
  779.         (*this)(dright).isdirty = true;
  780.         node = (*this)[dnode];
  781.         node->items[idx] = buf[half];
  782.         node->items[idx].right = dright;
  783.         (*this)(dnode).isdirty = true;
  784.         *underflow = false;
  785.     } else {    // merge, and free the right page.
  786.         left = (*this)[dleft];
  787.         left->size = CopyItems(buf,left->items,size);
  788.         AdjustParent(dleft);
  789.         (*this)(dleft).isdirty = true;
  790.         node = (*this)[dnode];
  791.         node->size = DeleteItem(node->items,idx,node->size);
  792.         (*this)(dnode).isdirty = true;
  793.         FreePage(dright);
  794.         *underflow = node->size < Order;
  795.     }
  796. }
  797.  
  798. // Parentage adjuster.  Makes sure the parent pointers are correct.
  799. void vBTree::AdjustParent (DiskPage dparent)
  800. {
  801.     int idx;
  802.     DiskPage dnode;
  803.     Page *node, *parent = (*this)[dparent];
  804.     int psize = parent->size;
  805.  
  806.     parent = (*this)[dparent];
  807.     dnode = parent->left;
  808.     if (dnode != 0) {
  809.         node = (*this)[dnode];
  810.         if (node->parent != dparent ||
  811.             node->parentidx != -1) {
  812.                 node->parent = dparent;
  813.                 node->parentidx = -1;
  814.                 (*this)(dnode).isdirty = true;
  815.         }
  816.     }
  817.     for (idx=0; idx < psize; idx++) {
  818.         parent = (*this)[dparent];
  819.         dnode = parent->items[idx].right;
  820.         if (dnode != 0) {
  821.             node = (*this)[dnode];
  822.             if (node->parent !=
  823.                 dparent ||
  824.                 node->parentidx != idx) {
  825.                 node->parent = dparent;
  826.                 node->parentidx = idx;
  827.                 (*this)(dnode).isdirty = true;
  828.             }
  829.         }
  830.     }
  831. }
  832.  
  833. // Item hacking code - copy items, insert an item and delete an item
  834. int vBTree::CopyItems (Item* src,Item* dest,int count)
  835. {
  836.     for (int i = 0; i < count;  ++i)    // straight copy
  837.         dest[i] = src[i];
  838.     return count;
  839. }
  840.  
  841. int vBTree::InsertItem (Item* item,Item* items,int idx,int size)
  842. {
  843.     for (int i = size; i > idx; --i)    // shift right
  844.         items[i] = items[i-1];
  845.     items[idx] = *item;            // insert
  846.     return size + 1;
  847. }
  848.  
  849. int vBTree::DeleteItem (Item* items,int idx,int size)
  850. {
  851.     for (int i = idx; i < size; ++i)    // shift left
  852.         items[i] = items[i+1];
  853.     return size - 1;
  854. }
  855.  
  856. // Raw printing function.  Much like in the book. The data is printed as
  857. // the size and offset of the disk record.
  858. void vBTree::PrintAux(DiskPage dnode, int margin)
  859. {
  860.     char  margBuf[128];
  861.     Page* node;
  862.  
  863.     if (dnode != 0) {
  864.         node = (*this)[dnode];
  865.         for (int i = 0; i < margin; ++i) margBuf[i] = ' ';
  866.         margBuf[i] = 0;
  867.         int nsize = node->size;
  868.         PrintAux(node->left,margin+8);
  869.         for (i = 0; i < nsize; ++i) {
  870.             node = (*this)[dnode];
  871.             cout << form("%s(%s [%d:%d])\n",
  872.                      margBuf,node->items[i].key,
  873.                      node->items[i].data.record_size,
  874.                      node->items[i].data.record_address);
  875.             PrintAux(node->items[i].right,margin+8);
  876.         }
  877.     }
  878. }
  879.  
  880. // page counting function.  Allows applications that need this info
  881. // do things smart (preallocating the pages for a compact output file)
  882. int vBTree::CountPagesAux(DiskPage dnode)
  883. {
  884.     int count = 0;
  885.     Page* node;
  886.  
  887.     if (dnode != 0) {
  888.         count++;
  889.         node = (*this)[dnode];
  890.         //cout << "*** dnode = " << dnode.record_address << "\n"; DumpPage(node);
  891.         count += CountPagesAux(node->left);
  892.         node = (*this)[dnode];
  893.         int nsize = node->size;
  894.         for (int i = 0; i < nsize; ++i) {
  895.             count += CountPagesAux(node->items[i].right);
  896.             node = (*this)[dnode];
  897.         }
  898.     }
  899.     return(count);
  900. }
  901.  
  902. // Tree traversal function.  Allows "sequential" access to a tree
  903. void vBTree::TravAux(DiskPage dnode,TravFunc tfun,int level)
  904. {
  905.     CoreItem item;
  906.     Page* node;
  907.  
  908.     if (dnode != 0) {
  909.         node = (*this)[dnode];
  910.         TravAux(node->left,tfun,level+1);
  911.         node = (*this)[dnode];
  912.         int nsize = node->size;
  913.         for (int i = 0; i < nsize; ++i) {
  914.             strcpy(item.key,node->items[i].key);
  915.             item.data.NewBuffer(node->items[i].data.record_size);
  916.             int bytesread = 
  917.             PageFile::ReadRecord(node->items[i].data,
  918.                          item.data.buffer,
  919.                          item.data.size);
  920.             if (bytesread < 0) {
  921.                 Error(sysErr,"PageFile::ReadRecord");
  922.                 item.data.NewBuffer(0);
  923.             }
  924.             (*tfun)(&item,level);
  925.             node = (*this)[dnode];
  926.             TravAux(node->items[i].right,tfun,level+1);
  927.         }
  928.     }
  929. }
  930.  
  931. // Generic error handler
  932. void vBTree::Error (ErrKind err,const char* msg)
  933. {
  934.     if (errFun != 0) (*errFun)(err,msg);
  935.     else {
  936.         if (err == sysErr) {
  937.             int error = errno;
  938.             cerr << form("Error: %s %s\n",strerror(error),msg);
  939.             exit(error);
  940.         } else {
  941.             cerr << form("Error: %s %s\n",
  942.                 (err == termErr ? "Terminal" : "Memory"),
  943.                 msg);
  944.             exit(1);
  945.         }
  946.     }
  947. }
  948.  
  949.  
  950.