code reorg
[csql.git] / src / relational / index / TrieIndex.cxx
blob127c1a9754b4cf5effd3d84bef6cc16c6870c3bb
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 TrieIndex::checkForUniqueKey(IndexNode *head, IndexInfo *info, void *tuple)
78 if (!head) return false;
79 int offset = info->fldOffset;
80 DataType type = info->type;
81 BucketList list(head);
82 BucketIter iter = list.getIterator();
83 IndexNode *node;
84 void *bucketTuple;
85 printDebug(DM_TrieIndex, "TrieIndex insert Checking for unique");
86 bool res = false;
87 while((node = iter.next()) != NULL)
89 bucketTuple = node->ptrToTuple_;
90 if (type != typeVarchar)
91 res = AllDataType::compareVal((void*)((char*)bucketTuple +offset),
92 (void*)((char*)tuple +offset), OpEquals,type, info->compLength);
93 else
94 res = AllDataType::compareVal((void*)*(long *)((char*)bucketTuple +offset),
95 (void*)*(long *)((char*)tuple +offset), OpEquals,type, info->compLength);
96 if (res)
98 printError(ErrUnique, "Unique key violation");
99 return true;
102 return false;
106 DbRetVal TrieIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
108 DbRetVal rv = OK;
109 HashIndexInfo *info = (HashIndexInfo*) indInfo;
110 CINDEX *iptr = (CINDEX*)indexPtr;
111 char hashValue[TRIE_MAX_LENGTH];
112 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
113 //for varchar ptr to value is stored in tuple
114 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
115 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
116 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
117 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
118 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
119 TrieNode* start = (TrieNode*)citer.nextElement();
120 //if(start) displayAll(start);
121 int cnt=0;
122 if (NULL == start) {
123 //first value is inserted into the trie index
124 start = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
125 if (NULL == start) {
126 printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
127 return rv;
130 char **prev = NULL;
131 while(-1 != hashValue[cnt+1]) {
132 prev = (char**)&(start->next_[hashValue[cnt]]);
133 if (*prev)
135 start = (TrieNode*) *prev;
136 cnt++;
137 continue;
139 //allocate trie node
140 TrieNode *newNode = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
141 if (NULL == newNode) {
142 printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
143 return rv;
145 //set the previous trie node ptr to this node
146 *prev = (char*)newNode;
147 start = newNode;
148 cnt++;
150 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
151 rv = addToValueList(tbl->db_, ptr, hIdxNodeChunk, indInfo, tuple, keyPtr);
152 if (OK != rv) return rv;
154 //create logical undo log
155 TrieUndoLogInfo hInfo;
156 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
157 hInfo.bucketPtr_ = ptr;
158 hInfo.tuple_ = tuple;
159 hInfo.keyPtr_ = keyPtr;
160 hInfo.hChunk_ = hIdxNodeChunk;
162 if (!loadFlag) {
163 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, InsertTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
164 //TODO:: if it fails need to remove the element from the bucket
166 return rv;
169 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk,
170 IndexInfo *info, void *tuple, void *keyPtr)
172 IndexNode *head = (IndexNode*) *ptr;
173 if (info->isUnique)
175 bool isKeyPresent = checkForUniqueKey(head, info, tuple);
176 if (isKeyPresent) return ErrUnique;
178 printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
179 DbRetVal rv = OK;
180 if (!head)
182 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
183 IndexNode *firstNode= NULL;
184 firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
185 if (firstNode == NULL){
186 printError(rv, "Unable to allocate index node for Trie index after retry");
187 return rv;
189 firstNode->ptrToKey_ = keyPtr;
190 firstNode->ptrToTuple_ = tuple;
191 firstNode->next_ = NULL;
192 if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
193 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
194 hIdxNodeChunk->free(db, firstNode);
195 return ErrLockTimeOut;
197 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
199 else
201 BucketList list(head);
202 rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
203 if (rv !=OK) {
204 printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
205 return rv;
208 return OK;
211 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
213 IndexNode *head = (IndexNode*) *ptr;
214 printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
215 DbRetVal rv = OK;
216 if (!head)
218 rv = ErrSysFatal;
219 printError(rv, "Fatal:Trie value list head is empty");
220 return rv;
222 else
224 BucketList list(head);
225 rv = list.remove(hIdxNodeChunk, db, keyPtr);
226 if (SplCase == rv)
228 rv = OK;
229 printDebug(DM_TrieIndex, "Removing trie index node from head ");
230 if (0 != Mutex::CASL((long*)ptr,
231 (long)head, (long)list.getBucketListHead())) {
232 printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
233 return ErrLockTimeOut;
236 if (rv !=OK) {
237 printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
238 return rv;
241 return OK;
245 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
247 DbRetVal rv = OK;
248 HashIndexInfo *info = (HashIndexInfo*) indInfo;
249 CINDEX *iptr = (CINDEX*)indexPtr;
250 char hashValue[TRIE_MAX_LENGTH];
251 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
252 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
253 //for varchar ptr to value is stored in tuple
254 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
255 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
256 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
257 TrieNode* start = (TrieNode*)citer.nextElement();
258 int cnt=0;
259 if (NULL == start) {
260 printError(ErrSysInternal, "No trie nodes found %d\n", rv);
261 return rv;
263 char **iter = NULL;
264 while(-1 != hashValue[cnt+1]) {
265 iter = (char**)&(start->next_[hashValue[cnt]]);
266 if (! *iter)
268 printError(ErrNotFound, "No trie node found %d\n", rv);
269 return ErrNotFound;
271 //traverse till the end
272 start = (TrieNode*) *iter;
273 cnt++;
275 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
276 rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
277 if (OK != rv) return rv;
279 //create logical undo log
280 TrieUndoLogInfo hInfo;
281 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
282 hInfo.bucketPtr_ = ptr;
283 hInfo.tuple_ = tuple;
284 hInfo.keyPtr_ = keyPtr;
285 hInfo.hChunk_ = hIdxNodeChunk;
287 if (!loadFlag) {
288 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
289 //TODO:: if it fails need to remove the element from the bucket
291 return rv;
294 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
296 DbRetVal rv = OK;
297 printError(ErrNotYet, "Not Yet Implemented");
298 return rv;
301 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
303 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
304 Chunk *hChunk = (Chunk *) info->hChunk_;
305 Database db;
306 db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
307 db.setProcSlot(sysdb->procSlot);
308 void **bkt = info->bucketPtr_;
309 IndexNode *head = (IndexNode *)*bkt;
310 BucketList list(head);
311 DbRetVal rv = OK;
312 if (!head)
314 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
315 IndexNode *firstNode= NULL;
316 firstNode= (IndexNode*) hChunk->tryAllocate(sysdb, &rv);
317 if (firstNode == NULL){
318 printError(rv, "Unable to allocate index node for Trie index after retry");
319 return rv;
321 firstNode->ptrToKey_ = info->keyPtr_;
322 firstNode->ptrToTuple_ = info->tuple_;
323 firstNode->next_ = NULL;
324 if (0 != Mutex::CASL((long*)bkt, 0, (long)firstNode)) {
325 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
326 hChunk->free(sysdb, firstNode);
327 return ErrLockTimeOut;
329 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
330 return OK;
333 rv = list.insert(hChunk, sysdb, info->keyPtr_, info->tuple_);
334 if (rv != OK)
336 printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
337 return ErrLockTimeOut;
339 return OK;
342 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
344 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
345 Chunk *hChunk = (Chunk *) info->hChunk_;
346 Database db;
347 db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
348 db.setProcSlot(sysdb->procSlot);
349 void **bkt = info->bucketPtr_;
350 IndexNode *head = (IndexNode *)*bkt;
351 BucketList list(head);
352 DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
353 *bkt = list.getBucketListHead();
354 if (SplCase == rc) {
355 if (0 != Mutex::CASL((long*)bkt,
356 (long)*bkt,
357 (long)list.getBucketListHead()))
359 printError(ErrLockTimeOut, "Unable to set the head of trie index bucket\n");
360 return ErrLockTimeOut;
363 }else if (rc != OK) {
364 printError(ErrLockTimeOut, "Unable to remove trie index node");
365 return ErrLockTimeOut;
367 return OK;
370 void TrieIndex::displayAll(TrieNode *start, int level)
372 printTrieNode(start, level);
373 level++;
374 for (int i=0; i < TRIE_SIZE; i++)
376 if (start->next_[i]) displayAll(start->next_[i], level);
380 void TrieIndex::printTrieNode(TrieNode *node, int level)
382 printf("Trie %x Level %d child:", node, level);
383 for (int i=0; i < TRIE_SIZE; i++)
385 printf("%x ", node->next_[i]);
387 printf("bucket:", node);
388 for (int i=0; i < TRIE_SIZE; i++)
390 printf("%x ", node->head_[i]);
391 if ( node->head_[i]) {
392 printf("{ ");
393 BucketList list(node->head_[i]);
394 list.print();
395 printf("} ");
398 printf("\n");