Trie Index changes for retreiving metadata through catalog tool and
[csql.git] / src / storage / TrieIndex.cxx
blob688f9a8db4072b6f886e4e8b5e72f4c3af55ac79
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;
168 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk,
169 IndexInfo *info, void *tuple, void *keyPtr)
171 IndexNode *head = (IndexNode*) *ptr;
172 if (info->isUnique)
174 bool isKeyPresent = checkForUniqueKey(head, info, tuple);
175 if (isKeyPresent) return ErrUnique;
177 printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
178 DbRetVal rv = OK;
179 if (!head)
181 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
182 IndexNode *firstNode= NULL;
183 firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
184 if (firstNode == NULL){
185 printError(rv, "Unable to allocate index node for Trie index after retry");
186 return rv;
188 firstNode->ptrToKey_ = keyPtr;
189 firstNode->ptrToTuple_ = tuple;
190 firstNode->next_ = NULL;
191 if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
192 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
193 hIdxNodeChunk->free(db, firstNode);
194 return ErrLockTimeOut;
196 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
198 else
200 BucketList list(head);
201 rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
202 if (rv !=OK) {
203 printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
204 return rv;
207 return OK;
210 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
212 IndexNode *head = (IndexNode*) *ptr;
213 printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
214 DbRetVal rv = OK;
215 if (!head)
217 rv = ErrSysFatal;
218 printError(rv, "Fatal:Trie value list head is empty");
219 return rv;
221 else
223 BucketList list(head);
224 rv = list.remove(hIdxNodeChunk, db, keyPtr);
225 if (SplCase == rv)
227 rv = OK;
228 printDebug(DM_TrieIndex, "Removing trie index node from head ");
229 if (0 != Mutex::CASL((long*)ptr,
230 (long)head, (long)list.getBucketListHead())) {
231 printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
232 return ErrLockTimeOut;
235 if (rv !=OK) {
236 printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
237 return rv;
240 return OK;
244 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
246 DbRetVal rv = OK;
247 HashIndexInfo *info = (HashIndexInfo*) indInfo;
248 CINDEX *iptr = (CINDEX*)indexPtr;
249 char hashValue[TRIE_MAX_LENGTH];
250 void *keyPtr =(void*)((char*)tuple + info->fldOffset);
251 Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
252 //for varchar ptr to value is stored in tuple
253 if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
254 computeHashValues(info->type, keyPtr, hashValue, info->compLength);
255 ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
256 TrieNode* start = (TrieNode*)citer.nextElement();
257 int cnt=0;
258 if (NULL == start) {
259 printError(ErrSysInternal, "No trie nodes found %d\n", rv);
260 return rv;
262 char **iter = NULL;
263 while(-1 != hashValue[cnt+1]) {
264 iter = (char**)&(start->next_[hashValue[cnt]]);
265 if (! *iter)
267 printError(ErrNotFound, "No trie node found %d\n", rv);
268 return ErrNotFound;
270 //traverse till the end
271 start = (TrieNode*) *iter;
272 cnt++;
274 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
275 rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
276 if (OK != rv) return rv;
278 //create logical undo log
279 TrieUndoLogInfo hInfo;
280 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
281 hInfo.bucketPtr_ = ptr;
282 hInfo.tuple_ = tuple;
283 hInfo.keyPtr_ = keyPtr;
284 hInfo.hChunk_ = hIdxNodeChunk;
286 if (!loadFlag) {
287 rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
288 //TODO:: if it fails need to remove the element from the bucket
290 return rv;
293 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
295 DbRetVal rv = OK;
296 printError(ErrNotYet, "Not Yet Implemented");
297 return rv;
300 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
302 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
303 Chunk *hChunk = (Chunk *) info->hChunk_;
304 Database db;
305 db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
306 db.setProcSlot(sysdb->procSlot);
307 void **bkt = info->bucketPtr_;
308 IndexNode *head = (IndexNode *)*bkt;
309 BucketList list(head);
310 DbRetVal rv = OK;
311 if (!head)
313 printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
314 IndexNode *firstNode= NULL;
315 firstNode= (IndexNode*) hChunk->tryAllocate(sysdb, &rv);
316 if (firstNode == NULL){
317 printError(rv, "Unable to allocate index node for Trie index after retry");
318 return rv;
320 firstNode->ptrToKey_ = info->keyPtr_;
321 firstNode->ptrToTuple_ = info->tuple_;
322 firstNode->next_ = NULL;
323 if (0 != Mutex::CASL((long*)bkt, 0, (long)firstNode)) {
324 printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
325 hChunk->free(sysdb, firstNode);
326 return ErrLockTimeOut;
328 printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
329 return OK;
332 rv = list.insert(hChunk, sysdb, info->keyPtr_, info->tuple_);
333 if (rv != OK)
335 printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
336 return ErrLockTimeOut;
338 return OK;
341 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
343 TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
344 Chunk *hChunk = (Chunk *) info->hChunk_;
345 Database db;
346 db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
347 db.setProcSlot(sysdb->procSlot);
348 void **bkt = info->bucketPtr_;
349 IndexNode *head = (IndexNode *)*bkt;
350 BucketList list(head);
351 DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
352 *bkt = list.getBucketListHead();
353 if (SplCase == rc) {
354 if (0 != Mutex::CASL((long*)bkt,
355 (long)*bkt,
356 (long)list.getBucketListHead()))
358 printError(ErrLockTimeOut, "Unable to set the head of trie index bucket\n");
359 return ErrLockTimeOut;
362 }else if (rc != OK) {
363 printError(ErrLockTimeOut, "Unable to remove trie index node");
364 return ErrLockTimeOut;
366 return OK;
368 void TrieIndex::displayAll(TrieNode *start, int level)
370 printTrieNode(start, level);
371 level++;
372 for (int i=0; i < TRIE_SIZE; i++)
374 if (start->next_[i]) displayAll(start->next_[i], level);
377 void TrieIndex::printTrieNode(TrieNode *node, int level)
379 printf("Trie %x Level %d child:", node, level);
380 for (int i=0; i < TRIE_SIZE; i++)
382 printf("%x ", node->next_[i]);
384 printf("bucket:", node);
385 for (int i=0; i < TRIE_SIZE; i++)
387 printf("%x ", node->head_[i]);
388 if ( node->head_[i]) {
389 printf("{ ");
390 BucketList list(node->head_[i]);
391 list.print();
392 printf("} ");
395 printf("\n");