Trie Implementation
[csql.git] / src / storage / TrieIndex.cxx
blob555c76fe2864a896c961a38affcaba96eacf3933
1 /***************************************************************************
2 * Copyright (C) 2007 by www.databasecache.com *
3 * Contact: praba_tuty@databasecache.com *
4 * *
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. *
9 * *
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. *
14 * *
15 ***************************************************************************/
16 #include<Index.h>
17 #include<CatalogTables.h>
18 #include<Lock.h>
19 #include<Debug.h>
20 #include<Table.h>
21 #include<TableImpl.h>
22 #include<Predicate.h>
23 #include<PredicateImpl.h>
25 //converts the given value into 0 to TRIE_SIZE
26 //value could be 0-9, A-Z, a-z and special chars
27 char hashString(char value)
29 if (value > 47 && value <58) return value - 48;
30 else if (value > 64 && value <91 ) return (value - 64)/3;
31 else if (value > 96 && value <123) return (value - 96)/3;
32 //for all special and other chars return 9
33 return 9;
36 void TrieIndex::computeHashValues(DataType type, void *key, char *in, int length)
38 if (typeInt == type) {
39 int val = *(int*)key;
40 sprintf(in, "%d", val);
41 int i=0;
42 while (in[i] != '\0')
44 in[i] = hashString(in[i]);
45 printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
46 i++;
48 in[i] = -1;
49 }else if (typeLongLong == type) {
50 long val = *(long*)key;
51 sprintf(in, "%lld", val);
52 int i=0;
53 while (in[i] != '\0')
55 in[i] = hashString(in[i]);
56 printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
57 i++;
59 in[i] = -1;
60 }else if (typeString == type || typeVarchar == type) {
61 char *val = (char*) key;
62 int i=0;
63 while (*val != '\0')
65 in[i] = hashString(*val);
66 printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
67 val++;
68 i++;
70 in[i] = (char)-1;
71 }else
72 printError(ErrSysFatal,"Type not supported for trie hashing\n");
73 return ;
76 bool HashIndex::checkForUniqueKey(IndexNode *head, HashIndexInfo *info, void *tuple)
78 return false;
82 DbRetVal TrieIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
84 DbRetVal rv = OK;
85 HashIndexInfo *info = (HashIndexInfo*) indInfo;
86 CINDEX *iptr = (CINDEX*)indexPtr;
87 char hashValue[TRIE_MAX_LENGTH];
88 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
89 //for varchar ptr to value is stored in tuple
90 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
91 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
92 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
93 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
94 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
95 TrieNode* start = (TrieNode*)citer.nextElement();
96 if(start) displayAll(start);
97 int cnt=0;
98 if (NULL == start) {
99 //first value is inserted into the trie index
100 start = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
101 if (NULL == start) {
102 printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
103 return rv;
106 char **prev = NULL;
107 while(-1 != hashValue[cnt+1]) {
108 prev = (char**)&(start->next_[hashValue[cnt]]);
109 if (*prev)
111 start = (TrieNode*) *prev;
112 cnt++;
113 continue;
115 //allocate trie node
116 TrieNode *newNode = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
117 if (NULL == newNode) {
118 printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
119 return rv;
121 //set the previous trie node ptr to this node
122 *prev = (char*)newNode;
123 start = newNode;
124 cnt++;
126 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
127 rv = addToValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
128 if (OK != rv) return rv;
130 //create logical undo log
131 TrieUndoLogInfo hInfo;
132 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
133 hInfo.bucket_ = NULL;
134 hInfo.tuple_ = tuple;
135 hInfo.keyPtr_ = keyPtr;
137 if (!loadFlag) {
138 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, InsertTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
139 //TODO:: if it fails need to remove the element from the bucket
141 return rv;
143 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
145 IndexNode *head = (IndexNode*) *ptr;
146 printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
147 DbRetVal rv = OK;
148 if (!head)
150 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
151 IndexNode *firstNode= NULL;
152 firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
153 if (firstNode == NULL){
154 printError(rv, "Unable to allocate index node for Trie index after retry");
155 return rv;
157 firstNode->ptrToKey_ = keyPtr;
158 firstNode->ptrToTuple_ = tuple;
159 firstNode->next_ = NULL;
160 if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
161 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
162 hIdxNodeChunk->free(db, firstNode);
163 return ErrLockTimeOut;
165 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
167 else
169 BucketList list(head);
170 rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
171 if (rv !=OK) {
172 printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
173 return rv;
176 return OK;
179 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
181 IndexNode *head = (IndexNode*) *ptr;
182 printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
183 DbRetVal rv = OK;
184 if (!head)
186 printError(rv, "Trie value list head is empty");
187 return rv;
189 else
191 BucketList list(head);
192 rv = list.remove(hIdxNodeChunk, db, keyPtr);
193 if (SplCase == rv)
195 rv = OK;
196 printDebug(DM_TrieIndex, "Removing trie index node from head ");
197 if (0 != Mutex::CASL((long*)ptr,
198 (long)head, (long)list.getBucketListHead())) {
199 printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
200 return ErrLockTimeOut;
203 if (rv !=OK) {
204 printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
205 return rv;
208 return OK;
212 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
214 DbRetVal rv = OK;
215 HashIndexInfo *info = (HashIndexInfo*) indInfo;
216 CINDEX *iptr = (CINDEX*)indexPtr;
217 char hashValue[TRIE_MAX_LENGTH];
218 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
219 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
220 //for varchar ptr to value is stored in tuple
221 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
222 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
223 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
224 TrieNode* start = (TrieNode*)citer.nextElement();
225 int cnt=0;
226 if (NULL == start) {
227 printError(ErrSysInternal, "No trie nodes found %d\n", rv);
228 return rv;
230 char **iter = NULL;
231 while(-1 != hashValue[cnt+1]) {
232 iter = (char**)&(start->next_[hashValue[cnt]]);
233 if (! *iter)
235 printError(ErrNotFound, "No trie node found %d\n", rv);
236 return ErrNotFound;
238 //traverse till the end
239 start = (TrieNode*) *iter;
240 cnt++;
242 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
243 rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
244 if (OK != rv) return rv;
246 //create logical undo log
247 TrieUndoLogInfo hInfo;
248 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
249 hInfo.bucket_ = NULL;
250 hInfo.tuple_ = tuple;
251 hInfo.keyPtr_ = keyPtr;
253 if (!loadFlag) {
254 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
255 //TODO:: if it fails need to remove the element from the bucket
257 return rv;
260 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
262 DbRetVal rv = OK;
263 return rv;
266 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
268 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
269 Chunk *hChunk = (Chunk *) info->hChunk_;
270 Database db;
271 db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
272 db.setProcSlot(sysdb->procSlot);
273 IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
274 BucketList list(head);
275 DbRetVal rv = list.insert(hChunk, &db, info->keyPtr_, info->tuple_);
276 if (rv != OK)
278 printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
279 return ErrLockTimeOut;
281 return OK;
284 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
286 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
287 Chunk *hChunk = (Chunk *) info->hChunk_;
288 Database db;
289 db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
290 db.setProcSlot(sysdb->procSlot);
291 IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
292 BucketList list(head);
293 DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
294 if (SplCase == rc) {
295 ;//TODO
296 }else if (rc != OK) {
297 printError(ErrLockTimeOut, "Unable to remove hash index node");
298 return ErrLockTimeOut;
300 return OK;
302 void TrieIndex::displayAll(TrieNode *start, int level)
304 printTrieNode(start, level);
305 level++;
306 for (int i=0; i < TRIE_SIZE; i++)
308 if (start->next_[i]) displayAll(start->next_[i], level);
311 void TrieIndex::printTrieNode(TrieNode *node, int level)
313 printf("Trie %x Level %d child:", node, level);
314 for (int i=0; i < TRIE_SIZE; i++)
316 printf("%x ", node->next_[i]);
318 printf("bucket:", node);
319 for (int i=0; i < TRIE_SIZE; i++)
321 printf("%x ", node->head_[i]);
322 if ( node->head_[i]) {
323 printf("{ ");
324 BucketList list(node->head_[i]);
325 list.print();
326 printf("} ");
329 printf("\n");