1 /***************************************************************************
2 * Copyright (C) 2007 by www.databasecache.com *
3 * Contact: praba_tuty@databasecache.com *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
15 ***************************************************************************/
22 #define TRIE_MAX_LENGTH 64
47 IndexNode
*head_
[TRIE_SIZE
];
48 TrieNode
*next_
[TRIE_SIZE
];
55 * @brief Represents node in tree index.
56 * It is actually a doubly linked list node which contains information such as minimum key value pointer, maximum key value pointer and total number of elements.
58 * TreeNode represents node in tree index and it is guarded by a mutex.
59 * Any modifications to tree node should be done only after acquiring
60 * its associated mutex. At the end array of pointers to next level tree nodes(in case of intermediate node) / tuple is stored(in case of leaf nodes)
68 Mutex mutex_
; /**< Mutex guarding this node */
69 void *min_
; /**< Ptr to node having minimum value in this node */
70 void *max_
; /**< Ptr to node having maximum value in this node */
71 int noElements_
; /**< total number of elements in this node */
72 TreeNode
*next_
; /**< ptr to next tree node in same level */
73 TreeNode
*prev_
; /**< ptr to previous tree node in same level */
74 int balance_
; /**< Reserved. Not currently used */
75 //Note::after this array of pointer to tuples are stored
77 long long getTotalElements();
81 * @brief insert node into the tree, by traversing and locating the right node
83 * Detailed description comes here
84 * Detailed desc continues here
85 * @param db pointer to Database
86 * @param info pointer to tuple under search
87 * @param indexPtr ptr to INDEX structure
88 * @param tuple pointer to tuple under search
89 * @return DbRetVal error code when function returns
91 DbRetVal
insert(Database
*db
, IndexInfo
*info
, void *indexPtr
, void *tuple
);
94 * @brief remove node from the tree, by traversing and locating the right node
96 * @param db pointer to Database
97 * @param info pointer to tuple under search
98 * @param indexPtr ptr to INDEX structure
99 * @param tuple pointer to tuple to be removed
100 * @return DbRetVal error code when function returns
102 DbRetVal
remove(Database
*db
, IndexInfo
*info
, void *indexPtr
, void *tuple
);
105 * @brief update node in the tree, by traversing and locating the right node
107 * @param db pointer to Database
108 * @param info pointer to tuple under search
109 * @param indexPtr ptr to INDEX structure
110 * @param tuple pointer to tuple to be updated
111 * @return DbRetVal error code when function returns
113 DbRetVal
update(Database
*db
, IndexInfo
*info
, void *indexPtr
, void *tuple
);
116 void displayAll(int offset
);
121 * @brief locate node where tuple resides by traversing the tree nodes
123 * Detailed description comes here
124 * Detailed desc continues here
125 * @param db pointer to Database
126 * @param iter TreeNode pointer
127 * @param tuple pointer to tuple under search
128 * @param indInfo pointer to tuple under search
129 * @param rv OUT param which will contain error code when this function returns with any error
130 * @return TreeNode* pointer to TreeNode which contains the tuple under search
132 TreeNode
* locateNode(Database
*db
,TreeNode
*iter
, void *tuple
, IndexInfo
*indInfo
,DbRetVal
&rv
);
133 TreeNode
*locateNodeFromFirstLevel(TreeNode
*ftnode
,IndexInfo
*indInfo
,void *tuple
,int *nodepos
);
134 DbRetVal
insertRecordIntoNodeAndArrangeFirstLevel(Database
* db
, IndexInfo
* indInfo
, void* iptr
, void * tuple
, TreeNode
* fstLevel
,int nodepos
);
135 DbRetVal
insertNodeIntoFirstLevel(Database
* db
, IndexInfo
* indInfo
, void* indexPtr
, TreeNode
* newNode
,int nodepos
);
145 BucketIter(){iter
= head
= NULL
;
146 isUnique
=false; recordsOver
= false;}
147 void setHead(IndexNode
*hd
) { iter
= head
= hd
; recordsOver
=false;}
148 BucketIter(IndexNode
*head
) { iter
= head
= head
;
149 isUnique
=false; recordsOver
= false;}
150 void setUnique() { isUnique
= true; }
151 bool getUnique() { return isUnique
; }
153 void reset() { iter
= head
; recordsOver
=false;}
154 friend class BucketList
;
160 BucketList(){ head
= NULL
;}
161 BucketList(IndexNode
*h
){ head
= h
; }
162 void *getBucketListHead(){ return head
;}
163 DbRetVal
insert(Chunk
*chunk
, Database
*db
, void *key
, void *tuple
);
164 DbRetVal
remove(Chunk
*chunk
, Database
*db
, void *key
);
166 BucketIter
getIterator()
180 // create (one) object for each indexing mechanisms here
181 // Also need to make changes to getIndex() and destroy() methods
182 // accordingly for new index machanism.
183 static HashIndex
*hIdx
;
184 static TreeIndex
*tIdx
;
185 static TrieIndex
*iIdx
;
186 static long usageCount
;
188 static Index
* getIndex(IndexType type
);
189 static void init() { usageCount
++; }
190 static void destroy();
191 virtual DbRetVal
insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
)=0;
192 virtual DbRetVal
remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
)=0;
193 virtual DbRetVal
update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
)=0;
195 class HashIndex
: public Index
197 //No members as it will be called by multiple threads
199 DbRetVal
insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
200 DbRetVal
remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
201 DbRetVal
update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
202 bool checkForUniqueKey(IndexNode
*head
,HashIndexInfo
*info
, void *tuple
);
203 static unsigned int computeHashBucket(DataType type
, void *key
, int noOfBuckets
, int length
=0);
204 static DbRetVal
insertLogicalUndoLog(Database
*sysdb
, void *info
);
205 static DbRetVal
deleteLogicalUndoLog(Database
*sysdb
, void *info
);
208 class TreeIndex
: public Index
210 //No members as it will be called by multiple threads
211 DbRetVal
removeElement(Database
*db
, TreeNode
*iter
, void *tuple
, HashIndexInfo
*info
);
212 void removeNode(Database
*db
,void *indexPtr
,TreeNode
*fltnode
, TreeNode
*node
,int pos
);
214 DbRetVal
insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
215 DbRetVal
remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
216 DbRetVal
update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
217 static DbRetVal
insertLogicalUndoLog(Database
*sysdb
, void *info
);
218 static DbRetVal
deleteLogicalUndoLog(Database
*sysdb
, void *info
);
219 static DbRetVal
getTreeNodeMutex(TreeNode
*, int procSlot
, bool isX
=false);
220 static DbRetVal
upgradeTreeNodeMutex(TreeNode
*, int procSlot
);
224 class TrieIndex
: public Index
227 DbRetVal
insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
228 DbRetVal
remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
229 DbRetVal
update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*info
, void *tuple
, bool undoFlag
);
230 bool checkForUniqueKey(IndexNode
*head
, IndexInfo
*info
, void *tuple
);
231 static void computeHashValues(DataType type
, void *key
, char *in
, int length
=0);
232 static DbRetVal
insertLogicalUndoLog(Database
*sysdb
, void *info
);
233 static DbRetVal
deleteLogicalUndoLog(Database
*sysdb
, void *info
);
234 static void displayAll(TrieNode
*node
, int level
=1);
235 static void printTrieNode(TrieNode
*node
, int level
);
237 DbRetVal
addToValueList(Database
*, void**, Chunk
*, IndexInfo
*, void*, void*);
238 DbRetVal
removeFromValueList(Database
*, void**, Chunk
*, void*, void*);
256 void* locateElement();
261 TreeIter(){ iter
=head
=NULL
; searchKey
=fstLTnode
=NULL
;isUnique
= false;}
262 TreeIter(TreeNode
*hd
,void *fTnode
, int slot
) { fstLTnode
= fTnode
; iter
= head
= hd
; firstCall
= true; recordsOver
=false; procSlot
=slot
; isUnique
=false;}
263 void set(TreeNode
*hd
,void *fTnode
, int slot
) { fstLTnode
= fTnode
; iter
= head
= hd
; firstCall
= true; recordsOver
=false; procSlot
=slot
; isUnique
=false;}
264 void setSearchKey(void *key
, ComparisionOp cop
, bool ascending
= true)
266 searchKey
= key
; op
= cop
; asc
=ascending
;
268 void setUnique() { isUnique
= true; }
269 bool getUnique() { return isUnique
; }
270 void setFldOffset(int off
) { fldOffset
= off
; }
271 void setTypeLength(DataType t
, int l
) { type
=t
; length
=l
; }
275 void* getFirstElement();
276 void* getLastElement();
277 void reset();// { iter = head; firstCall = true; recordsOver=false; }
296 virtual ~IndexInfo() {}
299 //Used by TableImpl to cache information related to hash indexes on that table
300 class HashIndexInfo
:public IndexInfo
303 FieldList idxFldList
;
309 printf("HashIndexInfo indexPtr:%x noOfBuckets:%d buckets:%x \n",indexPtr
, noOfBuckets
, buckets
);
311 ~HashIndexInfo() { idxFldList
.removeAll(); }