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 ***************************************************************************/
17 #include<CatalogTables.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
36 void TrieIndex::computeHashValues(DataType type
, void *key
, char *in
, int length
)
38 if (typeInt
== type
) {
40 sprintf(in
, "%d", val
);
44 in
[i
] = hashString(in
[i
]);
45 printDebug(DM_TrieIndex
, "Hash Value Pos:%d Hash:%d\n", i
, in
[i
]);
49 }else if (typeLongLong
== type
) {
50 long val
= *(long*)key
;
51 sprintf(in
, "%lld", val
);
55 in
[i
] = hashString(in
[i
]);
56 printDebug(DM_TrieIndex
, "Hash Value Pos:%d Hash:%d\n", i
, in
[i
]);
60 }else if (typeString
== type
|| typeVarchar
== type
) {
61 char *val
= (char*) key
;
65 in
[i
] = hashString(*val
);
66 printDebug(DM_TrieIndex
, "Hash Value Pos:%d Hash:%d\n", i
, in
[i
]);
72 printError(ErrSysFatal
,"Type not supported for trie hashing\n");
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();
85 printDebug(DM_TrieIndex
, "TrieIndex insert Checking for unique");
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
);
94 res
= AllDataType::compareVal((void*)*(long *)((char*)bucketTuple
+offset
),
95 (void*)*(long *)((char*)tuple
+offset
), OpEquals
,type
, info
->compLength
);
98 printError(ErrUnique
, "Unique key violation");
106 DbRetVal
TrieIndex::insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
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);
123 //first value is inserted into the trie index
124 start
= (TrieNode
*) chunk
->tryAllocate(tbl
->db_
, &rv
);
126 printError(ErrSysInternal
, "Could not allocate trie node %d\n", rv
);
131 while(-1 != hashValue
[cnt
+1]) {
132 prev
= (char**)&(start
->next_
[hashValue
[cnt
]]);
135 start
= (TrieNode
*) *prev
;
140 TrieNode
*newNode
= (TrieNode
*) chunk
->tryAllocate(tbl
->db_
, &rv
);
141 if (NULL
== newNode
) {
142 printError(ErrSysInternal
, "Could not allocate trie node %d\n", rv
);
145 //set the previous trie node ptr to this node
146 *prev
= (char*)newNode
;
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
;
163 rv
= tr
->appendLogicalTrieUndoLog(tbl
->sysDB_
, InsertTrieIndexOperation
, &hInfo
, sizeof(TrieUndoLogInfo
));
164 //TODO:: if it fails need to remove the element from the bucket
169 DbRetVal
TrieIndex::addToValueList(Database
*db
, void **ptr
, Chunk
*hIdxNodeChunk
,
170 IndexInfo
*info
, void *tuple
, void *keyPtr
)
172 IndexNode
*head
= (IndexNode
*) *ptr
;
175 bool isKeyPresent
= checkForUniqueKey(head
, info
, tuple
);
176 if (isKeyPresent
) return ErrUnique
;
178 printDebug(DM_TrieIndex
, "TrieIndex insert into bucket list");
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");
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
);
201 BucketList
list(head
);
202 rv
= list
.insert(hIdxNodeChunk
, db
, keyPtr
, tuple
);
204 printError(rv
, "unable to insert into Trie bucketlist rv:%d", rv
);
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");
219 printError(rv
, "Fatal:Trie value list head is empty");
224 BucketList
list(head
);
225 rv
= list
.remove(hIdxNodeChunk
, db
, keyPtr
);
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
;
237 printError(rv
, "unable to remove from Trie bucketlist rv:%d", rv
);
245 DbRetVal
TrieIndex::remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
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();
260 printError(ErrSysInternal
, "No trie nodes found %d\n", rv
);
264 while(-1 != hashValue
[cnt
+1]) {
265 iter
= (char**)&(start
->next_
[hashValue
[cnt
]]);
268 printError(ErrNotFound
, "No trie node found %d\n", rv
);
271 //traverse till the end
272 start
= (TrieNode
*) *iter
;
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
;
288 rv
= tr
->appendLogicalTrieUndoLog(tbl
->sysDB_
, DeleteTrieIndexOperation
, &hInfo
, sizeof(TrieUndoLogInfo
));
289 //TODO:: if it fails need to remove the element from the bucket
294 DbRetVal
TrieIndex::update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
297 printError(ErrNotYet
, "Not Yet Implemented");
301 DbRetVal
TrieIndex::insertLogicalUndoLog(Database
*sysdb
, void *data
)
303 TrieUndoLogInfo
*info
= (TrieUndoLogInfo
*) data
;
304 Chunk
*hChunk
= (Chunk
*) info
->hChunk_
;
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
);
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");
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
);
333 rv
= list
.insert(hChunk
, sysdb
, info
->keyPtr_
, info
->tuple_
);
336 printError(ErrLockTimeOut
, "Unable to add to bucket..retry\n");
337 return ErrLockTimeOut
;
342 DbRetVal
TrieIndex::deleteLogicalUndoLog(Database
*sysdb
, void *data
)
344 TrieUndoLogInfo
*info
= (TrieUndoLogInfo
*) data
;
345 Chunk
*hChunk
= (Chunk
*) info
->hChunk_
;
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();
355 if (0 != Mutex::CASL((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
;
370 void TrieIndex::displayAll(TrieNode
*start
, int level
)
372 printTrieNode(start
, 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
]) {
393 BucketList
list(node
->head_
[i
]);