1 //-< TTREE.CPP >-----------------------------------------------------*--------*
2 // FastDB                    Version 1.0         (c) 1999  GARRET    *     ?  *
3 // (Main Memory Database Management System)                          *   /\|  *
4 //                                                                   *  /  \  *
5 //                          Created:     20-Nov-98    K.A. Knizhnik  * / [] \ *
6 //                          Last update: 10-Dec-98    K.A. Knizhnik  * GARRET *
7 //-------------------------------------------------------------------*--------*
8 // T-Tree interface
9 //-------------------------------------------------------------------*--------*
10 
11 #ifndef __TTREE_H__
12 #define __TTREE_H__
13 
14 BEGIN_FASTDB_NAMESPACE
15 
16 class FASTDB_DLL_ENTRY dbTtreeNode {
17     enum {
18         pageSize = 125,
19         minItems = pageSize - 2 // minimal number of items in internal node
20     };
21 
22   public:
23     oid_t left;
24     oid_t right;
25     int1  balance;
26     nat2  nItems;
27     oid_t item[pageSize];
28 
29     static oid_t allocate(dbDatabase* db, oid_t recordId);
30 
31     static bool  insert(dbDatabase* db, oid_t& nodeId, oid_t recordId,
32                         void* key, int type, int sizeofType, dbUDTComparator comparator, int offs);
33     static int   remove(dbDatabase* db, oid_t& nodeId, oid_t recordId,
34                         void* key, int type, int sizeofType, dbUDTComparator comparator, int offs);
35     static int   balanceRightBranch(dbDatabase* db, oid_t& nodeId);
36     static int   balanceLeftBranch(dbDatabase* db, oid_t& nodeId);
37 
38     static void  purge(dbDatabase* db, oid_t nodeId);
39 
40     bool find(dbDatabase* db, dbSearchContext& sc);
41     bool prefixSearch(dbDatabase* db, dbSearchContext& sc);
42 
43     bool traverseForward(dbDatabase* db,dbAnyCursor* cursor);
44     bool traverseBackward(dbDatabase* db, dbAnyCursor* cursor);
45     bool traverseForward(dbDatabase* db,dbAnyCursor* cursor,dbExprNode* cond);
46     bool traverseBackward(dbDatabase* db,dbAnyCursor* cursor,dbExprNode* cond);
47 };
48 
49 class FASTDB_DLL_ENTRY dbTtree {
50   protected:
51     oid_t root;
52 
53   public:
54     static oid_t allocate(dbDatabase* db);
55     static void  find(dbDatabase* db, oid_t treeId, dbSearchContext& sc);
56     static void  prefixSearch(dbDatabase* db, oid_t treeId, dbSearchContext& sc);
57     static void  insert(dbDatabase* db, oid_t treeId, oid_t recordId,
58                         int type, int sizeofType, dbUDTComparator comparator, int offs);
59     static void  remove(dbDatabase* db, oid_t treeId, oid_t recordId,
60                         int type, int sizeofType, dbUDTComparator comparator, int offs);
61     static void  drop(dbDatabase* db, oid_t treeId);
62     static void  purge(dbDatabase* db, oid_t treeId);
63 
64     static void  traverseForward(dbDatabase* db, oid_t treeId,
65                                  dbAnyCursor* cursor);
66     static void  traverseBackward(dbDatabase* db, oid_t treeId,
67                                   dbAnyCursor* cursor);
68     static void  traverseForward(dbDatabase* db, oid_t treeId,
69                                  dbAnyCursor* cursor, dbExprNode* condition);
70     static void  traverseBackward(dbDatabase* db, oid_t treeId,
71                                   dbAnyCursor* cursor, dbExprNode* condition);
72 };
73 
74 END_FASTDB_NAMESPACE
75 
76 #endif
77