Main Page   Class Hierarchy   Compound List   File List   Compound Members  

btree.h

00001 //-< BTREE.H >-------------------------------------------------------*--------*
00002 // GigaBASE                  Version 1.0         (c) 1999  GARRET    *     ?  *
00003 // (Post Relational Database Management System)                      *   /\|  *
00004 //                                                                   *  /  \  *
00005 //                          Created:      1-Jan-99    K.A. Knizhnik  * / [] \ *
00006 //                          Last update: 25-Oct-99    K.A. Knizhnik  * GARRET *
00007 //-------------------------------------------------------------------*--------*
00008 // B-Tree interface
00009 //-------------------------------------------------------------------*--------*
00010 
00011 #ifndef __BTREE_H__
00012 #define __BTREE_H__
00013 
00014 
00015 BEGIN_GIGABASE_NAMESPACE
00016 
00017 class dbAnyCursor;
00018 
00019 #define MAX_BTREE_HEIGHT 8
00020 
00021 class dbBtreePage {
00022   public:
00023     nat4 nItems;
00024     nat4 size;
00025 
00026     struct str {
00027         oid_t oid;
00028         nat2  size;
00029         nat2  offs;
00030     };
00031 
00032     enum { dbMaxKeyLen = (dbPageSize - sizeof(str)*2) / sizeof(char_t) / 2 };
00033 
00034     struct item {
00035         oid_t oid;
00036         int   keyLen;
00037         union {
00038             int1    keyInt1;
00039             int2    keyInt2;
00040             int4    keyInt4;
00041             db_int8 keyInt8;
00042             oid_t   keyOid;
00043             real4   keyReal4;
00044             real8   keyReal8;
00045             char_t  keyChar[dbMaxKeyLen];
00046         };
00047     };
00048     enum {
00049         maxItems = (dbPageSize - 8) / sizeof(oid_t)
00050     };
00051 
00052 
00053     union {
00054         oid_t  record[maxItems];
00055         int1   keyInt1[(dbPageSize-8) / sizeof(int1)];
00056         int2   keyInt2[(dbPageSize-8) / sizeof(int2)];
00057         int4   keyInt4[(dbPageSize-8) / sizeof(int4)];
00058         db_int8   keyInt8[(dbPageSize-8) / sizeof(db_int8)];
00059         oid_t  keyOid[(dbPageSize-8)  / sizeof(oid_t)];
00060         real4  keyReal4[(dbPageSize-8) / sizeof(real4)];
00061         real8  keyReal8[(dbPageSize-8) / sizeof(real8)];
00062         char   keyChar[dbPageSize-8];
00063         str    keyStr[1];
00064     };
00065 
00066     static oid_t allocate(dbDatabase* db, oid_t root, int type, int sizeofType, item& ins);
00067 
00068     static int   insert(dbDatabase* db, oid_t pageId,
00069                         int type, int sizeofType, dbUDTComparator comparator, item& ins, int height, bool unique);
00070     static int   remove(dbDatabase* db, oid_t pageId,
00071                         int type, int sizeofType, dbUDTComparator comparator, item& rem, int height);
00072 
00073     static void  purge(dbDatabase* db, oid_t pageId, int type, int height);
00074 
00075     int          insertStrKey(dbDatabase* db, int r, item& ins, int height);
00076     int          replaceStrKey(dbDatabase* db, int r, item& ins, int height);
00077     int          removeStrKey(int r);
00078     void         compactify(dbDatabase* db, int m);
00079 
00080     int          handlePageUnderflow(dbDatabase* db, int r, int type, int sizeofType, item& rem,
00081                                      int height);
00082 
00083     bool         find(dbDatabase* db, dbSearchContext& sc, int type, int sizeofType,
00084                       dbUDTComparator comparator, int height);
00085 
00086     bool         traverseForward(dbDatabase* db, dbAnyCursor* cursor,
00087                                  dbExprNode* condition, int type, int height);
00088     bool         traverseBackward(dbDatabase* db, dbAnyCursor* cursor,
00089                                   dbExprNode* condition, int type, int height);
00090 };
00091 
00092 
00093 class GIGABASE_DLL_ENTRY dbBtree : public dbRecord {
00094     friend class dbBtreeIterator;
00095   protected:
00096     oid_t root;
00097     int4  height;
00098     int4  type;
00099     int4  sizeofType;
00100 
00101   public:
00102     enum { 
00103         FLAGS_CASE_INSENSITIVE = 1, 
00104         FLAGS_THICK = 2,
00105         FLAGS_UNIQUE = 4
00106     };
00107     int1  flags; 
00108 
00109     bool isCaseInsensitive() { 
00110         return (flags & FLAGS_CASE_INSENSITIVE) != 0;
00111     }
00112 
00113     bool isThick() { 
00114         return (flags & FLAGS_THICK) != 0;
00115     }
00116 
00117     bool isUnique() { 
00118         return (flags & FLAGS_UNIQUE) != 0;
00119     }
00120 
00121     enum OperationEffect {
00122         done,
00123         overflow,
00124         underflow,
00125         not_found,                              
00126         not_unique
00127     };
00128 
00129     static oid_t allocate(dbDatabase* db, int type, int sizeofType, int flags = 0);
00130     static void  find(dbDatabase* db, oid_t treeId, dbSearchContext& sc, dbUDTComparator comparator);
00131     static bool  insert(dbDatabase* db, oid_t treeId, oid_t recordId, byte* record, int offs, dbUDTComparator comparator);
00132     static bool  insert(dbDatabase* db, oid_t treeId, oid_t recordId, int offs, dbUDTComparator comparator);
00133     static bool  insert(dbDatabase* db, oid_t treeId, dbBtreePage::item& ins, dbUDTComparator comparator);
00134     static void  remove(dbDatabase* db, oid_t treeId, oid_t recordId, byte* record, int offs, dbUDTComparator comparator);
00135     static void  remove(dbDatabase* db, oid_t treeId, oid_t recordId, int offs, dbUDTComparator comparator);
00136     static void  drop(dbDatabase* db, oid_t treeId);
00137     static void  purge(dbDatabase* db, oid_t treeId);
00138 
00139     static void  traverseForward(dbDatabase* db, oid_t treeId,
00140                                  dbAnyCursor* cursor, dbExprNode* condition);
00141     static void  traverseBackward(dbDatabase* db, oid_t treeId,
00142                                   dbAnyCursor* cursor, dbExprNode* condition);
00143     static void  traverseForward(dbDatabase* db, oid_t treeId,
00144                                  dbAnyCursor* cursor)
00145     {
00146         traverseForward(db, treeId, cursor, NULL);
00147     }
00148     static void  traverseBackward(dbDatabase* db, oid_t treeId,
00149                                   dbAnyCursor* cursor)
00150     {
00151         traverseBackward(db, treeId, cursor, NULL);
00152     }
00153 };
00154 
00155 class GIGABASE_DLL_ENTRY dbBtreeIterator : public dbAbstractIterator { 
00156   public:
00157     void init(dbDatabase* db, oid_t treeId, dbSearchContext& sc, dbUDTComparator comparator);
00158     
00159     oid_t next();
00160     oid_t prev();
00161     oid_t first();
00162     oid_t last();
00163     
00164   private:
00165     oid_t reset(bool ascent); 
00166     oid_t gotoNextItem(byte* pg, int pos, bool forward);
00167     
00168     oid_t getStringBtreePageOid(byte* pg, int i);
00169     oid_t getScalarBtreePageOid(byte* pg, int i);
00170     oid_t getStringThickBtreePageOid(byte* pg, int i);
00171     oid_t getScalarThickBtreePageOid(byte* pg, int i);
00172     void* getStringBtreePageKey(byte* pg, int i);
00173     void* getScalarBtreePageKey(byte* pg, int i);
00174     void* getStringThickBtreePageKey(byte* pg, int i);
00175     void* getScalarThickBtreePageKey(byte* pg, int i);
00176     
00177     oid_t (dbBtreeIterator::*getOid)(byte* pg, int i);
00178     void* (dbBtreeIterator::*getKey)(byte* pg, int i);
00179     
00180     int nItems(byte* pg) { 
00181         return ((dbBtreePage*)pg)->nItems;
00182     }
00183 
00184     dbUDTComparator comparator;
00185     dbDatabase*     db;
00186     dbSearchContext sc;
00187     int             sizeofType;
00188     int             type;
00189     int             height;
00190     oid_t           treeId;
00191     oid_t           pageStack[MAX_BTREE_HEIGHT];
00192     int             posStack[MAX_BTREE_HEIGHT];
00193 };   
00194 
00195 class dbThickBtreePage {
00196   public:
00197     nat4 nItems;
00198     nat4 size;
00199 
00200     struct reference {
00201         oid_t oid;
00202         oid_t recId;
00203     };
00204 
00205     struct str : reference {
00206         nat2  size;
00207         nat2  offs;
00208     };
00209     
00210     enum { dbMaxKeyLen = (dbPageSize - sizeof(str)*2) / sizeof(char_t) / 2 };
00211 
00212     struct item : reference {
00213         int   keyLen;
00214         union {
00215             int1    keyInt1;
00216             int2    keyInt2;
00217             int4    keyInt4;
00218             db_int8 keyInt8;
00219             oid_t   keyOid;
00220             real4   keyReal4;
00221             real8   keyReal8;
00222             char_t  keyChar[dbMaxKeyLen];
00223         };
00224     };
00225     enum {
00226         maxItems = (dbPageSize - 8) / sizeof(reference)
00227     };
00228 
00229 
00230     union {
00231         reference ref[maxItems];
00232         int1   keyInt1[(dbPageSize-8) / sizeof(int1)];
00233         int2   keyInt2[(dbPageSize-8) / sizeof(int2)];
00234         int4   keyInt4[(dbPageSize-8) / sizeof(int4)];
00235         db_int8   keyInt8[(dbPageSize-8) / sizeof(db_int8)];
00236         oid_t  keyOid[(dbPageSize-8)  / sizeof(oid_t)];
00237         real4  keyReal4[(dbPageSize-8) / sizeof(real4)];
00238         real8  keyReal8[(dbPageSize-8) / sizeof(real8)];
00239         char   keyChar[dbPageSize-8];
00240         str    keyStr[1];
00241     };
00242 
00243     static oid_t allocate(dbDatabase* db, oid_t root, int type, int sizeofType, item& ins);
00244 
00245     static int   insert(dbDatabase* db, oid_t pageId,
00246                         int type, int sizeofType, dbUDTComparator comparator, item& ins, int height);
00247     static int   remove(dbDatabase* db, oid_t pageId,
00248                         int type, int sizeofType, dbUDTComparator comparator, item& rem, int height);
00249 
00250     static void  purge(dbDatabase* db, oid_t pageId, int type, int height);
00251 
00252     int          insertStrKey(dbDatabase* db, int r, item& ins, int height);
00253     int          replaceStrKey(dbDatabase* db, int r, item& ins, int height);
00254     int          removeStrKey(int r);
00255     void         compactify(dbDatabase* db, int m);
00256 
00257     int          handlePageUnderflow(dbDatabase* db, int r, int type, int sizeofType, item& rem,
00258                                      int height);
00259 
00260     bool         find(dbDatabase* db, dbSearchContext& sc, int type, int sizeofType,
00261                       dbUDTComparator comparator, int height);
00262 
00263     bool         traverseForward(dbDatabase* db, dbAnyCursor* cursor,
00264                                  dbExprNode* condition, int type, int height);
00265     bool         traverseBackward(dbDatabase* db, dbAnyCursor* cursor,
00266                                   dbExprNode* condition, int type, int height);
00267 };
00268 
00269 END_GIGABASE_NAMESPACE
00270 
00271 #endif

Generated on Thu Feb 14 21:46:02 2008 for GigaBASE by doxygen1.2.18