CPP   41

public

Guest on 22nd August 2022 01:44:42 PM

  1.  
  2. B+ TREE HEADER FILE
  3. -------------------
  4.  
  5. #ifndef _BTFILE_H
  6. #define _BTFILE_H
  7.  
  8. /*
  9.  * This is the main definition of class BTreeFile, which derives from
  10.  * abstract base class IndexFile.
  11.  *
  12.  * class BTreeFileScan is defined in btreefilescan.h; this class provides
  13.  * a search/iterate interface to a BTreeFile.
  14.  */
  15.  
  16.  
  17. #define BT_TRACE
  18.   /* When #defined, BT_TRACE causes a structured trace to be written to the
  19.      ostream pointed to by the class variable BTreeFile::Trace.  This output is
  20.      used to drive a visualization tool that shows the inner workings of the
  21.      b-tree during its operations.  You must set BTreeFile::Trace to the
  22.      ostream of your choice before creating your BTreeFile. */
  23.  
  24. #include "btindex_page.h"
  25. #include "btleaf_page.h"
  26. #include "index.h"
  27. #include "btreefilescan.h"
  28. #include "bt.h"
  29.  
  30.  
  31. #define NAIVE_DELETE 0
  32. #define FULL_DELETE  1
  33.  
  34. class BTreeFile: public IndexFile {
  35.  
  36.   friend class BTreeFileScan;
  37.   friend class BTreeTest;
  38.  
  39.   private:
  40.  
  41.   /*
  42.    * Structure of a B+ tree index header page.  There is quite a bit
  43.    * of wasted space here...
  44.    */
  45.  
  46.   public:
  47.  
  48.     enum ErrorTypes {
  49.  
  50.       // our interface for the erroneous error protocol.
  51.  
  52.       _OK = 0,                // 0 is always OK
  53.       CANT_FIND_HEADER,       // tried to open index but db said no header
  54.       CANT_PIN_HEADER,        // buffer manager failed to pin header page
  55.       CANT_ALLOC_HEADER,      // failed to allocate block for header page
  56.       CANT_ADD_FILE_ENTRY,    // couldn't register new index file w/ db
  57.       CANT_UNPIN_HEADER,      // can't unpin header page
  58.       CANT_PIN_PAGE,          // can't pin some index/leaf page
  59.       CANT_UNPIN_PAGE,        // can't unpin some index/leaf page
  60.       INVALID_SCAN,           // attempt to use bad Scan object
  61.       DELETE_CURRENT_FAILED,  // failed to delete current rid in scan
  62.       CANT_DELETE_FILE_ENTRY, // db failed to delete file entry
  63.       CANT_FREE_PAGE,         // buffer manager failed to free a page
  64.       CANT_DELETE_SUBTREE,    // _destroyFile failed on a subtree
  65.       KEY_TOO_LONG,           // the key given in BTreeFile::insert is too long
  66.       INSERT_FAILED,          // BTreeFile::insert not successful
  67.       COULD_NOT_CREATE_ROOT,  // BtreeFile::insert could not create new root
  68.       DELETE_DATAENTRY_FAILED,// could not delete a data entry
  69.       DATA_ENTRY_NOT_FOUND,   // could not find data entry to delete
  70.       CANT_GET_PAGE_NO,       // get_page_no on BTIndexPage failed
  71.       CANT_ALLOCATE_NEW_PAGE, // bm::newPage failed
  72.       CANT_SPLIT_LEAF_PAGE,   // could not split leaf page
  73.       CANT_SPLIT_INDEX_PAGE,  // could not split index page
  74.  
  75.       NR_ERRORS               // and this is the number of them
  76.     };
  77.  
  78.     static const char *Errors[NR_ERRORS];
  79.  
  80.     // an index with given filename should already exist; this opens it.
  81.     BTreeFile(Status& status, const char *filename);
  82.  
  83.     // if index exists, open it; else create it.
  84.     BTreeFile(Status& status, const char *filename, const AttrType keytype,
  85.               const int keysize, int delete_fashion = FULL_DELETE);
  86.    
  87.     // closes index
  88.    ~BTreeFile();
  89.    
  90.     // destroy entire index file
  91.     Status destroyFile();
  92.    
  93.     // insert recid with the key key
  94.     Status insert(const void *key, const RID rid);
  95.    
  96.     // delete leaf entry recid given its key
  97.     // (`rid' is IN the data entry; it is not the id of the data entry)
  98.     Status Delete(const void *key, const RID rid);
  99.    
  100.     // create a scan with given keys
  101.     // Cases:
  102.     //      (1) lo_key = NULL, hi_key = NULL
  103.     //              scan the whole index
  104.     //      (2) lo_key = NULL, hi_key!= NULL
  105.     //              range scan from min to the hi_key
  106.     //      (3) lo_key!= NULL, hi_key = NULL
  107.     //              range scan from the lo_key to max
  108.     //      (4) lo_key!= NULL, hi_key!= NULL, lo_key = hi_key
  109.     //              exact match ( might not unique)
  110.     //      (5) lo_key!= NULL, hi_key!= NULL, lo_key < hi_key
  111.     //              range scan from lo_key to hi_key
  112.     IndexFileScan *new_scan(const void *lo_key = NULL,
  113.                             const void *hi_key = NULL);
  114.  
  115.     int keysize();
  116.    
  117.  
  118.     void PrintHeader();            // print the header info
  119.     void PrintRoot();              // print the root page
  120.     void PrintLeafPages();         // print all the leaf pages
  121.     void PrintPage(PageId id);     // print page with id
  122.  
  123. #if defined(BT_TRACE)
  124.     static class ostream *Trace;   // Set this to your stream to get a trace.
  125. #endif
  126.  
  127.   private:
  128.  
  129. };
  130.  
  131. #endif // _BTFILE_H

Raw Paste


Login or Register to edit or fork this paste. It's free.