src/server/HashIndex.cxx

   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>
  24
  25 /* Defines `hashpjw' function by P.J. Weinberger
  26    [see Aho/Sethi/Ullman, COMPILERS: Principles, Techniques and Tools,
  27    */
  28
  29 unsigned int hashString(char *strVal)
  30 {
  31     unsigned int hval, g;
  32     hval = 0;
  33     char *str =strVal;
  34     while (*str != '\0')
  35     {
  36         hval <<= 4;
  37         hval += (unsigned int) *str++;
  38         g = hval & ((unsigned int) 0xf << (32 - 4));
  39         if (g != 0)
  40         {
  41             hval ^= g >> (32 - 8);
  42             hval ^= g;
  43         }
  44     }
  45     return hval;
  46 }
  47
  48 unsigned int HashIndex::computeHashBucket(DataType type, void *key, int noOfBuckets)
  49
  50 {
  51     switch(type)
  52     {
  53         case typeInt:
  54         {
  55             int val = *(int*)key;
  56             return val % noOfBuckets;
  57             break;
  58         }
  59         case typeLong:
  60         {
  61             long val = *(long*)key;
  62             return val % noOfBuckets;
  63             break;
  64         }
  65         case typeULong:
  66         {
  67             unsigned long val = *(unsigned long*)key;
  68             return val % noOfBuckets;
  69             break;
  70         }
  71         case typeLongLong:
  72         {
  73             long long val = *(long long*)key;
  74             return val % noOfBuckets;
  75             break;
  76         }
  77         case typeShort:
  78         {
  79             short val = *(short*)key;
  80             return val % noOfBuckets;
  81             break;
  82         }
  83         case typeByteInt:
  84         {
  85             ByteInt val = *(ByteInt*)key;
  86             return val % noOfBuckets;
  87             break;
  88         }
  89         case typeDate:
  90         {
  91             int val = *(int*)key;
  92             return val % noOfBuckets;
  93             break;
  94         }
  95         case typeTime:
  96         {
  97             int val = *(int*)key;
  98             return val % noOfBuckets;
  99             break;
 100         }
 101         case typeTimeStamp:
 102         {
 103             TimeStamp val = *(TimeStamp*)key;
 104             //TODO return val % noOfBuckets;
 105             break;
 106         }
 107         case typeDouble:
 108         {
 109             //TODO
 110             break;
 111         }
 112         case typeFloat:
 113         {
 114             //TODO
 115             break;
 116         }
 117         case typeDecimal:
 118         {
 119             //TODO::for porting
 120         }
 121         case typeString:
 122         {
 123             unsigned int val = hashString((char*)key);
 124             return val % noOfBuckets;
 125         }
 126         case typeBinary:
 127         {
 128             //TODO
 129         }
 130         default:
 131         {
 132             break;
 133         }
 134     }
 135     return -1;
 136 }
 137
 138 //TODO::composite keys are not supported currently
 139 DbRetVal HashIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 140 {
 141     SingleFieldHashIndexInfo *info = (SingleFieldHashIndexInfo*) indInfo;
 142     INDEX *iptr = (INDEX*)indexPtr;
 143     DbRetVal rc = OK;
 144     DataType type = info->type;
 145     char *name = info->fldName;
 146     int offset  = info->offset;
 147     int noOfBuckets = info->noOfBuckets;
 148     int length = info->length;
 149
 150     printDebug(DM_HashIndex, "Inserting hash index node for field %s", name);
 151     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 152     Bucket* buckets = (Bucket*)citer.nextElement();
 153     void *keyPtr =(void*)((char*)tuple + offset);
 154
 155     int bucketNo = computeHashBucket(type,
 156                         keyPtr, noOfBuckets);
 157     printDebug(DM_HashIndex, "HashIndex insert bucketno %d", bucketNo);
 158     Bucket *bucket =  &(buckets[bucketNo]);
 159
 160     int ret = bucket->mutex_.getLock(tbl->db_->procSlot);
 161     if (ret != 0)
 162     {
 163         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",bucketNo);
 164         return ErrLockTimeOut;
 165     }
 166     HashIndexNode *head = (HashIndexNode*) bucket->bucketList_;
 167     if (info->isUnique)
 168     {
 169         BucketList list(head);
 170         BucketIter iter = list.getIterator();
 171         HashIndexNode *node;
 172         void *bucketTuple;
 173         printDebug(DM_HashIndex, "HashIndex insert Checking for unique");
 174         while((node = iter.next()) != NULL)
 175         {
 176             bucketTuple = node->ptrToTuple_;
 177             if (AllDataType::compareVal((void*)((char*)bucketTuple +offset),
 178                    (void*)((char*)tuple +offset), OpEquals,type, length))
 179             {
 180                 printError(ErrUnique, "Unique key violation");
 181                 bucket->mutex_.releaseLock(tbl->db_->procSlot);
 182                 return ErrUnique;
 183             }
 184         }
 185     }
 186
 187     printDebug(DM_HashIndex, "HashIndex insert into bucket list");
 188     if (!head)
 189     {
 190         printDebug(DM_HashIndex, "HashIndex insert head is empty");
 191         HashIndexNode *firstNode= (HashIndexNode*)(((Chunk*)iptr->hashNodeChunk_)->allocate(tbl->db_));
 192         firstNode->ptrToKey_ = keyPtr;
 193         firstNode->ptrToTuple_ = tuple;
 194         firstNode->next_ = NULL;
 195         bucket->bucketList_ = (HashIndexNode*)firstNode;
 196         printDebug(DM_HashIndex, "HashIndex insert new node %x in empty bucket", bucket->bucketList_);
 197     }
 198     else
 199     {
 200         BucketList list(head);
 201         rc = list.insert((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr, tuple);
 202         if (rc !=OK) {
 203             bucket->mutex_.releaseLock(tbl->db_->procSlot);
 204             return rc;
 205         }
 206
 207     }
 208     if (undoFlag) {
 209
 210          rc = tr->appendLogicalUndoLog(tbl->sysDB_, InsertHashIndexOperation,
 211                                  tuple, sizeof(void*), indexPtr);
 212         if (rc !=OK)
 213         {
 214             BucketList list(head);
 215             rc = list.remove((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr);
 216             if (rc !=OK) printError(ErrSysFatal, "double failure on undo log insert followed by hash bucket list remove\n");
 217         }
 218     }
 219
 220     bucket->mutex_.releaseLock(tbl->db_->procSlot);
 221     return rc;
 222 }
 223
 224
 225 //TODO::composite keys are not supported currently
 226 DbRetVal HashIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 227 {
 228     INDEX *iptr = (INDEX*)indexPtr;
 229
 230     SingleFieldHashIndexInfo *info = (SingleFieldHashIndexInfo*) indInfo;
 231     DataType type = info->type;
 232     char *name = info->fldName;
 233     int offset  = info->offset;
 234     int noOfBuckets = info->noOfBuckets;
 235
 236     printDebug(DM_HashIndex, "Removing hash index node for field %s", name);
 237     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 238     Bucket* buckets = (Bucket*)citer.nextElement();
 239     void *keyPtr =(void*)((char*)tuple + offset);
 240
 241     int bucket = HashIndex::computeHashBucket(type, keyPtr, noOfBuckets);
 242
 243     Bucket *bucket1 = &buckets[bucket];
 244
 245     int ret = bucket1->mutex_.getLock(tbl->db_->procSlot);
 246     if (ret != 0)
 247     {
 248         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",bucket);
 249         return ErrLockTimeOut;
 250     }
 251     HashIndexNode *head = (HashIndexNode*) bucket1->bucketList_;
 252
 253     if (!head) { printError(ErrNotExists, "Hash index does not exist:should never happen\n"); return ErrNotExists; }
 254     BucketList list(head);
 255     printDebug(DM_HashIndex, "Removing hash index node from head %x", head);
 256
 257     DbRetVal rc = list.remove((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr);
 258     if (SplCase == rc)
 259     {
 260        printDebug(DM_HashIndex, "Removing hash index node from head with only none node");
 261        bucket1->bucketList_ = 0;
 262        rc = OK;
 263     }
 264     if (undoFlag) {
 265         rc =tr->appendLogicalUndoLog(tbl->sysDB_, DeleteHashIndexOperation,
 266                                 tuple, sizeof(void*), indexPtr);
 267         if (rc !=OK)
 268         {
 269         //TODO::add it back to the bucketlist
 270         }
 271     }
 272     bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 273     return rc;
 274 }
 275
 276 //TODO::composite keys are not supported currently
 277 DbRetVal HashIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 278 {
 279     INDEX *iptr = (INDEX*)indexPtr;
 280
 281     SingleFieldHashIndexInfo *info = (SingleFieldHashIndexInfo*) indInfo;
 282     DataType type = info->type;
 283     char *name = info->fldName;
 284     int offset  = info->offset;
 285     int noOfBuckets = info->noOfBuckets;
 286
 287     printDebug(DM_HashIndex, "Updating hash index node for field %s", name);
 288
 289     //check whether the index key is updated or not
 290     //if it is not updated return from here
 291     void *keyPtr =(void*)((char*)tuple + offset);
 292     //Iterate through the bind list and check
 293     FieldIterator fldIter = tbl->fldList_.getIterator();
 294     void *newKey = NULL;
 295     while (fldIter.hasElement())
 296     {
 297         FieldDef def = fldIter.nextElement();
 298         if (0 == strcmp(def.fldName_, name))
 299         {
 300             if (NULL == def.bindVal_)
 301                 return OK;
 302             bool result = AllDataType::compareVal(keyPtr, def.bindVal_,
 303                                 OpEquals, def.type_, def.length_);
 304             if (result) return OK; else newKey = def.bindVal_;
 305         }
 306     }
 307     printDebug(DM_HashIndex, "Updating hash index node: Key value is updated");
 308
 309     if (newKey == NULL)
 310     {
 311         printError(ErrSysInternal,"Internal Error:: newKey is Null");
 312         return ErrSysInternal;
 313     }
 314     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 315
 316     Bucket* buckets = (Bucket*)citer.nextElement();
 317
 318     //remove the node whose key is updated
 319     int bucketNo = computeHashBucket(type,
 320                         keyPtr, noOfBuckets);
 321     printDebug(DM_HashIndex, "Updating hash index node: Bucket for old value is %d", bucketNo);
 322     Bucket *bucket = &buckets[bucketNo];
 323
 324     //it may run into deadlock, when two threads updates tuples which falls in
 325     //same buckets.So take both the mutex one after another, which will reduce the
 326     //deadlock window.
 327     int ret = bucket->mutex_.getLock(tbl->db_->procSlot);
 328     if (ret != 0)
 329     {
 330         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",bucketNo);
 331         return ErrLockTimeOut;
 332     }
 333     //insert node for the updated key value
 334     int newBucketNo = computeHashBucket(type,
 335                         newKey, noOfBuckets);
 336     printDebug(DM_HashIndex, "Updating hash index node: Bucket for new value is %d", newBucketNo);
 337
 338     Bucket *bucket1 = &buckets[newBucketNo];
 339     bucket1->mutex_.getLock(tbl->db_->procSlot);
 340     if (ret != 0)
 341     {
 342         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",newBucketNo);
 343         return ErrLockTimeOut;
 344     }
 345
 346     HashIndexNode *head1 = (HashIndexNode*) bucket->bucketList_;
 347     if (head1)
 348     {
 349         BucketList list1(head1);
 350         printDebug(DM_HashIndex, "Updating hash index node: Removing node from list with head %x", head1);
 351         list1.remove((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr);
 352     }
 353     else
 354     {
 355         printError(ErrSysInternal,"Update: Bucket list is null");
 356         return ErrSysInternal;
 357     }
 358     DbRetVal rc = OK;
 359     if (undoFlag) {
 360          rc = tr->appendLogicalUndoLog(tbl->sysDB_, DeleteHashIndexOperation,
 361                                 tuple, sizeof(void*), indexPtr);
 362         if (rc !=OK)
 363         {
 364             //TODO::add it back to the bucket list
 365             bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 366             bucket->mutex_.releaseLock(tbl->db_->procSlot);
 367             return rc;
 368         }
 369     }
 370     HashIndexNode *head2 = (HashIndexNode*) bucket1->bucketList_;
 371     //Note:: the tuple will be in the same address location
 372     //so not changing the keyptr and tuple during append
 373     //only bucket where this node resides will only change
 374     //if the index key is updated.
 375     if (!head2)
 376     {
 377         HashIndexNode *firstNode= (HashIndexNode*)(((Chunk*)iptr->hashNodeChunk_)->allocate(tbl->db_));
 378         firstNode->ptrToKey_ = keyPtr;
 379         firstNode->ptrToTuple_ = tuple;
 380         firstNode->next_ = NULL;
 381         bucket1->bucketList_ = (HashIndexNode*)firstNode;
 382         printDebug(DM_HashIndex, "Updating hash index node: Adding new node %x:Head is empty", firstNode);
 383     }
 384     else
 385     {
 386         BucketList list2(head2);
 387         printDebug(DM_HashIndex, "Updating hash index node: Adding node to list with head %x", head2);
 388         list2.insert((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr, tuple);
 389     }
 390     if (undoFlag) {
 391
 392         rc = tr->appendLogicalUndoLog(tbl->sysDB_, InsertHashIndexOperation,
 393                                 tuple, sizeof(void*), indexPtr);
 394         if (rc !=OK)
 395         {
 396             //TODO::revert back the changes:delete and add the node + remove the logical undo log
 397             //of the  DeleteHashIndexOperation
 398         }
 399     }
 400     bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 401     bucket->mutex_.releaseLock(tbl->db_->procSlot);
 402     return rc;
 403 }