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 /* Defines `hashpjw' function by P.J. Weinberger
26 [see Aho/Sethi/Ullman, COMPILERS: Principles, Techniques and Tools,
29 unsigned int hashString(char *strVal
)
37 hval
+= (unsigned int) *str
++;
38 g
= hval
& ((unsigned int) 0xf << (32 - 4));
41 hval
^= g
>> (32 - 8);
47 unsigned int hashBinary(char *strVal
, int length
)
53 while (iter
!= length
)
56 hval
+= (unsigned int) *str
++;
57 g
= hval
& ((unsigned int) 0xf << (32 - 4));
60 hval
^= g
>> (32 - 8);
68 unsigned int HashIndex::computeHashBucket(DataType type
, void *key
, int noOfBuckets
, int length
)
76 return val
% noOfBuckets
;
81 long val
= *(long*)key
;
82 return val
% noOfBuckets
;
87 unsigned long val
= *(unsigned long*)key
;
88 return val
% noOfBuckets
;
93 long long val
= *(long long*)key
;
94 return val
% noOfBuckets
;
99 short val
= *(short*)key
;
100 return val
% noOfBuckets
;
105 ByteInt val
= *(ByteInt
*)key
;
106 return val
% noOfBuckets
;
111 int val
= *(int*)key
;
112 return val
% noOfBuckets
;
117 int val
= *(int*)key
;
118 return val
% noOfBuckets
;
123 TimeStamp val
= *(TimeStamp
*)key
;
124 //TODO return val % noOfBuckets;
143 unsigned int val
= hashString((char*)key
);
144 return val
% noOfBuckets
;
149 unsigned int val
= hashBinary((char*)key
, length
);
150 return val
% noOfBuckets
;
160 DbRetVal
HashIndex::insert(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool undoFlag
)
162 HashIndexInfo
*info
= (HashIndexInfo
*) indInfo
;
163 INDEX
*iptr
= (INDEX
*)indexPtr
;
165 int noOfBuckets
= info
->noOfBuckets
;
166 int offset
= info
->fldOffset
;
167 DataType type
= info
->type
;
168 printDebug(DM_HashIndex
, "Inserting hash index node for %s", iptr
->indName_
);
169 ChunkIterator citer
= CatalogTableINDEX::getIterator(indexPtr
);
170 Bucket
* buckets
= (Bucket
*)citer
.nextElement();
171 void *keyPtr
=(void*)((char*)tuple
+ offset
);
173 int bucketNo
= computeHashBucket(type
,
174 keyPtr
, noOfBuckets
, info
->compLength
);
175 printDebug(DM_HashIndex
, "HashIndex insert bucketno %d", bucketNo
);
176 Bucket
*bucket
= &(buckets
[bucketNo
]);
178 int ret
= bucket
->mutex_
.getLock(tbl
->db_
->procSlot
);
181 printError(ErrLockTimeOut
,"Unable to acquire bucket Mutex for bucket %d",bucketNo
);
182 return ErrLockTimeOut
;
184 HashIndexNode
*head
= (HashIndexNode
*) bucket
->bucketList_
;
187 BucketList
list(head
);
188 BucketIter iter
= list
.getIterator();
191 printDebug(DM_HashIndex
, "HashIndex insert Checking for unique");
192 while((node
= iter
.next()) != NULL
)
194 bucketTuple
= node
->ptrToTuple_
;
195 if (AllDataType::compareVal((void*)((char*)bucketTuple
+offset
),
196 (void*)((char*)tuple
+offset
), OpEquals
,type
, info
->compLength
))
198 printError(ErrUnique
, "Unique key violation");
199 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
205 printDebug(DM_HashIndex
, "HashIndex insert into bucket list");
208 printDebug(DM_HashIndex
, "HashIndex insert head is empty");
210 HashIndexNode
*firstNode
= (HashIndexNode
*)(((Chunk
*)iptr
->hashNodeChunk_
)->allocate(tbl
->db_
, &rv
));
211 if (firstNode
== NULL
)
213 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
216 firstNode
->ptrToKey_
= keyPtr
;
217 firstNode
->ptrToTuple_
= tuple
;
218 firstNode
->next_
= NULL
;
219 bucket
->bucketList_
= (HashIndexNode
*)firstNode
;
220 printDebug(DM_HashIndex
, "HashIndex insert new node %x in empty bucket", bucket
->bucketList_
);
224 BucketList
list(head
);
225 rc
= list
.insert((Chunk
*)iptr
->hashNodeChunk_
, tbl
->db_
, keyPtr
, tuple
);
227 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
234 rc
= tr
->appendLogicalUndoLog(tbl
->sysDB_
, InsertHashIndexOperation
,
235 tuple
, sizeof(void*), indexPtr
);
238 BucketList
list(head
);
239 rc
= list
.remove((Chunk
*)iptr
->hashNodeChunk_
, tbl
->db_
, keyPtr
);
240 if (rc
!=OK
) printError(ErrSysFatal
, "double failure on undo log insert followed by hash bucket list remove\n");
244 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
249 DbRetVal
HashIndex::remove(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool undoFlag
)
251 INDEX
*iptr
= (INDEX
*)indexPtr
;
253 HashIndexInfo
*info
= (HashIndexInfo
*) indInfo
;
254 DataType type
= info
->type
;
255 int offset
= info
->fldOffset
;
256 int noOfBuckets
= info
->noOfBuckets
;
258 ChunkIterator citer
= CatalogTableINDEX::getIterator(indexPtr
);
259 Bucket
* buckets
= (Bucket
*)citer
.nextElement();
260 void *keyPtr
=(void*)((char*)tuple
+ offset
);
262 int bucket
= HashIndex::computeHashBucket(type
, keyPtr
, noOfBuckets
, info
->compLength
);
264 Bucket
*bucket1
= &buckets
[bucket
];
266 int ret
= bucket1
->mutex_
.getLock(tbl
->db_
->procSlot
);
269 printError(ErrLockTimeOut
,"Unable to acquire bucket Mutex for bucket %d",bucket
);
270 return ErrLockTimeOut
;
272 HashIndexNode
*head
= (HashIndexNode
*) bucket1
->bucketList_
;
274 if (!head
) { printError(ErrNotExists
, "Hash index does not exist:should never happen\n"); return ErrNotExists
; }
275 BucketList
list(head
);
276 printDebug(DM_HashIndex
, "Removing hash index node from head %x", head
);
278 DbRetVal rc
= list
.remove((Chunk
*)iptr
->hashNodeChunk_
, tbl
->db_
, keyPtr
);
281 printDebug(DM_HashIndex
, "Removing hash index node from head with only none node");
282 bucket1
->bucketList_
= 0;
286 rc
=tr
->appendLogicalUndoLog(tbl
->sysDB_
, DeleteHashIndexOperation
,
287 tuple
, sizeof(void*), indexPtr
);
290 //TODO::add it back to the bucketlist
293 bucket1
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
298 DbRetVal
HashIndex::update(TableImpl
*tbl
, Transaction
*tr
, void *indexPtr
, IndexInfo
*indInfo
, void *tuple
, bool undoFlag
)
300 INDEX
*iptr
= (INDEX
*)indexPtr
;
302 HashIndexInfo
*info
= (HashIndexInfo
*) indInfo
;
303 DataType type
= info
->type
;
304 int offset
= info
->fldOffset
;
305 int noOfBuckets
= info
->noOfBuckets
;
307 //check whether the index key is updated or not
308 //if it is not updated return from here
309 void *keyPtr
=(void*)((char*)tuple
+ offset
);
310 char *kPtr
= (char*)keyPtr
;
311 //Iterate through the bind list and check
312 FieldIterator idxFldIter
= info
->idxFldList
.getIterator();
313 char *keyBindBuffer
= (char*) malloc(info
->compLength
);
314 void *keyStartBuffer
= (void*) keyBindBuffer
;
315 bool keyUpdated
= false;
316 while (idxFldIter
.hasElement())
318 FieldDef idef
= idxFldIter
.nextElement();
319 FieldIterator fldIter
= tbl
->fldList_
.getIterator();
320 while (fldIter
.hasElement())
322 FieldDef def
= fldIter
.nextElement();
323 if (0 == strcmp(def
.fldName_
, idef
.fldName_
))
325 if (NULL
!= def
.bindVal_
) {
326 AllDataType::copyVal(keyBindBuffer
, def
.bindVal_
,
327 def
.type_
, def
.length_
);
328 keyBindBuffer
= keyBindBuffer
+ AllDataType::size(def
.type_
,
338 //printf("PRABA::key not updated\n");
339 free(keyStartBuffer
);
342 //printf("PRABA::it is wrong coming here\n");
343 bool result
= AllDataType::compareVal(kPtr
, keyStartBuffer
,
344 OpEquals
, info
->type
, info
->compLength
);
345 if (result
) return OK
;
347 printDebug(DM_HashIndex
, "Updating hash index node: Key value is updated");
349 ChunkIterator citer
= CatalogTableINDEX::getIterator(indexPtr
);
351 Bucket
* buckets
= (Bucket
*)citer
.nextElement();
353 //remove the node whose key is updated
354 int bucketNo
= computeHashBucket(type
,
355 keyPtr
, noOfBuckets
, info
->compLength
);
356 printDebug(DM_HashIndex
, "Updating hash index node: Bucket for old value is %d", bucketNo
);
357 Bucket
*bucket
= &buckets
[bucketNo
];
359 //it may run into deadlock, when two threads updates tuples which falls in
360 //same buckets.So take both the mutex one after another, which will reduce the
362 int ret
= bucket
->mutex_
.getLock(tbl
->db_
->procSlot
);
365 printError(ErrLockTimeOut
,"Unable to acquire bucket Mutex for bucket %d",bucketNo
);
366 return ErrLockTimeOut
;
368 //insert node for the updated key value
369 int newBucketNo
= computeHashBucket(type
,
370 keyStartBuffer
, noOfBuckets
);
371 printDebug(DM_HashIndex
, "Updating hash index node: Bucket for new value is %d", newBucketNo
);
373 Bucket
*bucket1
= &buckets
[newBucketNo
];
374 bucket1
->mutex_
.getLock(tbl
->db_
->procSlot
);
377 printError(ErrLockTimeOut
,"Unable to acquire bucket Mutex for bucket %d",newBucketNo
);
378 return ErrLockTimeOut
;
381 HashIndexNode
*head1
= (HashIndexNode
*) bucket
->bucketList_
;
384 BucketList
list1(head1
);
385 printDebug(DM_HashIndex
, "Updating hash index node: Removing node from list with head %x", head1
);
386 list1
.remove((Chunk
*)iptr
->hashNodeChunk_
, tbl
->db_
, keyPtr
);
390 printError(ErrSysInternal
,"Update: Bucket list is null");
391 return ErrSysInternal
;
395 rc
= tr
->appendLogicalUndoLog(tbl
->sysDB_
, DeleteHashIndexOperation
,
396 tuple
, sizeof(void*), indexPtr
);
399 //TODO::add it back to the bucket list
400 bucket1
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
401 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
405 HashIndexNode
*head2
= (HashIndexNode
*) bucket1
->bucketList_
;
406 //Note:: the tuple will be in the same address location
407 //so not changing the keyptr and tuple during append
408 //only bucket where this node resides will only change
409 //if the index key is updated.
413 HashIndexNode
*firstNode
= (HashIndexNode
*)(((Chunk
*)iptr
->hashNodeChunk_
)->allocate(tbl
->db_
, &rv
));
414 if (firstNode
== NULL
)
416 printError(rv
, "Error in allocating hash node");
417 bucket1
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
418 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
421 firstNode
->ptrToKey_
= keyPtr
;
422 firstNode
->ptrToTuple_
= tuple
;
423 firstNode
->next_
= NULL
;
424 bucket1
->bucketList_
= (HashIndexNode
*)firstNode
;
425 printDebug(DM_HashIndex
, "Updating hash index node: Adding new node %x:Head is empty", firstNode
);
429 BucketList
list2(head2
);
430 printDebug(DM_HashIndex
, "Updating hash index node: Adding node to list with head %x", head2
);
431 list2
.insert((Chunk
*)iptr
->hashNodeChunk_
, tbl
->db_
, keyPtr
, tuple
);
435 rc
= tr
->appendLogicalUndoLog(tbl
->sysDB_
, InsertHashIndexOperation
,
436 tuple
, sizeof(void*), indexPtr
);
439 //TODO::revert back the changes:delete and add the node + remove the logical undo log
440 //of the DeleteHashIndexOperation
443 bucket1
->mutex_
.releaseLock(tbl
->db_
->procSlot
);
444 bucket
->mutex_
.releaseLock(tbl
->db_
->procSlot
);