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 HashIndex::checkForUniqueKey(IndexNode *head, HashIndexInfo *info, void *tuple)
82 DbRetVal
TrieIndex::insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
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
);
99 //first value is inserted into the trie index
100 start
= (TrieNode
*) chunk
->tryAllocate(tbl
->db_
, &rv
);
102 printError(ErrSysInternal
, "Could not allocate trie node %d\n", rv
);
107 while(-1 != hashValue
[cnt
+1]) {
108 prev
= (char**)&(start
->next_
[hashValue
[cnt
]]);
111 start
= (TrieNode
*) *prev
;
116 TrieNode
*newNode
= (TrieNode
*) chunk
->tryAllocate(tbl
->db_
, &rv
);
117 if (NULL
== newNode
) {
118 printError(ErrSysInternal
, "Could not allocate trie node %d\n", rv
);
121 //set the previous trie node ptr to this node
122 *prev
= (char*)newNode
;
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
;
138 rv
= tr
->appendLogicalTrieUndoLog(tbl
->sysDB_
, InsertTrieIndexOperation
, &hInfo
, sizeof(TrieUndoLogInfo
));
139 //TODO:: if it fails need to remove the element from the bucket
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");
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");
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
);
169 BucketList
list(head
);
170 rv
= list
.insert(hIdxNodeChunk
, db
, keyPtr
, tuple
);
172 printError(rv
, "unable to insert into Trie bucketlist rv:%d", rv
);
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");
186 printError(rv
, "Trie value list head is empty");
191 BucketList
list(head
);
192 rv
= list
.remove(hIdxNodeChunk
, db
, keyPtr
);
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
;
204 printError(rv
, "unable to remove from Trie bucketlist rv:%d", rv
);
212 DbRetVal
TrieIndex::remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
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();
227 printError(ErrSysInternal
, "No trie nodes found %d\n", rv
);
231 while(-1 != hashValue
[cnt
+1]) {
232 iter
= (char**)&(start
->next_
[hashValue
[cnt
]]);
235 printError(ErrNotFound
, "No trie node found %d\n", rv
);
238 //traverse till the end
239 start
= (TrieNode
*) *iter
;
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
;
254 rv
= tr
->appendLogicalTrieUndoLog(tbl
->sysDB_
, DeleteTrieIndexOperation
, &hInfo
, sizeof(TrieUndoLogInfo
));
255 //TODO:: if it fails need to remove the element from the bucket
260 DbRetVal
TrieIndex::update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool loadFlag
)
266 DbRetVal
TrieIndex::insertLogicalUndoLog(Database
*sysdb
, void *data
)
268 TrieUndoLogInfo
*info
= (TrieUndoLogInfo
*) data
;
269 Chunk
*hChunk
= (Chunk
*) info
->hChunk_
;
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_
);
278 printError(ErrLockTimeOut
, "Unable to add to bucket..retry\n");
279 return ErrLockTimeOut
;
284 DbRetVal
TrieIndex::deleteLogicalUndoLog(Database
*sysdb
, void *data
)
286 TrieUndoLogInfo
*info
= (TrieUndoLogInfo
*) data
;
287 Chunk
*hChunk
= (Chunk
*) info
->hChunk_
;
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_
);
296 }else if (rc
!= OK
) {
297 printError(ErrLockTimeOut
, "Unable to remove hash index node");
298 return ErrLockTimeOut
;
302 void TrieIndex::displayAll(TrieNode
*start
, int level
)
304 printTrieNode(start
, 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
]) {
324 BucketList
list(node
->head_
[i
]);