00001
00002
00003
00004
00005
00006
00007
00008
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