trie index changes
[csql.git] / src / storage / TrieIndex.cxx
blobec2e6de76d3abedef9fb7bc58bbfbb51e4c37220
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.bucket_ = NULL;
158 hInfo.tuple_ = tuple;
159 hInfo.keyPtr_ = keyPtr;
161 if (!loadFlag) {
162 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, InsertTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
163 //TODO:: if it fails need to remove the element from the bucket
165 return rv;
167 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk,
168 IndexInfo *info, void *tuple, void *keyPtr)
170 IndexNode *head = (IndexNode*) *ptr;
171 if (info->isUnique)
173 bool isKeyPresent = checkForUniqueKey(head, info, tuple);
174 if (isKeyPresent) return ErrUnique;
176 printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
177 DbRetVal rv = OK;
178 if (!head)
180 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
181 IndexNode *firstNode= NULL;
182 firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
183 if (firstNode == NULL){
184 printError(rv, "Unable to allocate index node for Trie index after retry");
185 return rv;
187 firstNode->ptrToKey_ = keyPtr;
188 firstNode->ptrToTuple_ = tuple;
189 firstNode->next_ = NULL;
190 if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
191 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
192 hIdxNodeChunk->free(db, firstNode);
193 return ErrLockTimeOut;
195 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
197 else
199 BucketList list(head);
200 rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
201 if (rv !=OK) {
202 printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
203 return rv;
206 return OK;
209 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
211 IndexNode *head = (IndexNode*) *ptr;
212 printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
213 DbRetVal rv = OK;
214 if (!head)
216 printError(rv, "Trie value list head is empty");
217 return rv;
219 else
221 BucketList list(head);
222 rv = list.remove(hIdxNodeChunk, db, keyPtr);
223 if (SplCase == rv)
225 rv = OK;
226 printDebug(DM_TrieIndex, "Removing trie index node from head ");
227 if (0 != Mutex::CASL((long*)ptr,
228 (long)head, (long)list.getBucketListHead())) {
229 printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
230 return ErrLockTimeOut;
233 if (rv !=OK) {
234 printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
235 return rv;
238 return OK;
242 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
244 DbRetVal rv = OK;
245 HashIndexInfo *info = (HashIndexInfo*) indInfo;
246 CINDEX *iptr = (CINDEX*)indexPtr;
247 char hashValue[TRIE_MAX_LENGTH];
248 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
249 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
250 //for varchar ptr to value is stored in tuple
251 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
252 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
253 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
254 TrieNode* start = (TrieNode*)citer.nextElement();
255 int cnt=0;
256 if (NULL == start) {
257 printError(ErrSysInternal, "No trie nodes found %d\n", rv);
258 return rv;
260 char **iter = NULL;
261 while(-1 != hashValue[cnt+1]) {
262 iter = (char**)&(start->next_[hashValue[cnt]]);
263 if (! *iter)
265 printError(ErrNotFound, "No trie node found %d\n", rv);
266 return ErrNotFound;
268 //traverse till the end
269 start = (TrieNode*) *iter;
270 cnt++;
272 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
273 rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
274 if (OK != rv) return rv;
276 //create logical undo log
277 TrieUndoLogInfo hInfo;
278 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
279 hInfo.bucket_ = NULL;
280 hInfo.tuple_ = tuple;
281 hInfo.keyPtr_ = keyPtr;
283 if (!loadFlag) {
284 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
285 //TODO:: if it fails need to remove the element from the bucket
287 return rv;
290 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
292 DbRetVal rv = OK;
293 return rv;
296 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
298 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
299 Chunk *hChunk = (Chunk *) info->hChunk_;
300 Database db;
301 db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
302 db.setProcSlot(sysdb->procSlot);
303 IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
304 BucketList list(head);
305 DbRetVal rv = list.insert(hChunk, &db, info->keyPtr_, info->tuple_);
306 if (rv != OK)
308 printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
309 return ErrLockTimeOut;
311 return OK;
314 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
316 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
317 Chunk *hChunk = (Chunk *) info->hChunk_;
318 Database db;
319 db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
320 db.setProcSlot(sysdb->procSlot);
321 IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
322 BucketList list(head);
323 DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
324 if (SplCase == rc) {
325 if (0 != Mutex::CASL((long*)& (((Bucket *)info->bucket_)->bucketList_),
326 (long)(((Bucket *)info->bucket_)->bucketList_),
327 (long)list.getBucketListHead()))
329 printError(ErrLockTimeOut, "Unable to set the head of trie index bucket\n");
330 return ErrLockTimeOut;
333 }else if (rc != OK) {
334 printError(ErrLockTimeOut, "Unable to remove hash index node");
335 return ErrLockTimeOut;
337 return OK;
339 void TrieIndex::displayAll(TrieNode *start, int level)
341 printTrieNode(start, level);
342 level++;
343 for (int i=0; i < TRIE_SIZE; i++)
345 if (start->next_[i]) displayAll(start->next_[i], level);
348 void TrieIndex::printTrieNode(TrieNode *node, int level)
350 printf("Trie %x Level %d child:", node, level);
351 for (int i=0; i < TRIE_SIZE; i++)
353 printf("%x ", node->next_[i]);
355 printf("bucket:", node);
356 for (int i=0; i < TRIE_SIZE; i++)
358 printf("%x ", node->head_[i]);
359 if ( node->head_[i]) {
360 printf("{ ");
361 BucketList list(node->head_[i]);
362 list.print();
363 printf("} ");
366 printf("\n");