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
 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         list.insert((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr, tuple);
 202     }
 203     DbRetVal rc = OK;
 204     if (undoFlag) {
 205
 206          rc = tr->appendLogicalUndoLog(tbl->sysDB_, InsertHashIndexOperation,
 207                                  tuple, sizeof(void*), indexPtr);
 208         if (rc !=OK)
 209         {
 210             //TODO::remove it from the bucketlist
 211         }
 212     }
 213
 214     bucket->mutex_.releaseLock(tbl->db_->procSlot);
 215     return rc;
 216 }
 217
 218
 219 //TODO::composite keys are not supported currently
 220 DbRetVal HashIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 221 {
 222     INDEX *iptr = (INDEX*)indexPtr;
 223
 224     SingleFieldHashIndexInfo *info = (SingleFieldHashIndexInfo*) indInfo;
 225     DataType type = info->type;
 226     char *name = info->fldName;
 227     int offset  = info->offset;
 228     int noOfBuckets = info->noOfBuckets;
 229
 230     printDebug(DM_HashIndex, "Removing hash index node for field %s", name);
 231     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 232     Bucket* buckets = (Bucket*)citer.nextElement();
 233     void *keyPtr =(void*)((char*)tuple + offset);
 234
 235     int bucket = HashIndex::computeHashBucket(type, keyPtr, noOfBuckets);
 236
 237     Bucket *bucket1 = &buckets[bucket];
 238
 239     int ret = bucket1->mutex_.getLock(tbl->db_->procSlot);
 240     if (ret != 0)
 241     {
 242         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",bucket);
 243         return ErrLockTimeOut;
 244     }
 245     HashIndexNode *head = (HashIndexNode*) bucket1->bucketList_;
 246
 247     if (!head) { printError(ErrNotExists, "Hash index does not exist:should never happen\n"); return ErrNotExists; }
 248     BucketList list(head);
 249     printDebug(DM_HashIndex, "Removing hash index node from head %x", head);
 250
 251     DbRetVal rc = list.remove((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr);
 252     if (SplCase == rc)
 253     {
 254        printDebug(DM_HashIndex, "Removing hash index node from head with only none node");
 255        bucket1->bucketList_ = 0;
 256        rc = OK;
 257     }
 258     if (undoFlag) {
 259         rc =tr->appendLogicalUndoLog(tbl->sysDB_, DeleteHashIndexOperation,
 260                                 tuple, sizeof(void*), indexPtr);
 261         if (rc !=OK)
 262         {
 263         //TODO::add it back to the bucketlist
 264         }
 265     }
 266     bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 267     return rc;
 268 }
 269
 270 //TODO::composite keys are not supported currently
 271 DbRetVal HashIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 272 {
 273     INDEX *iptr = (INDEX*)indexPtr;
 274
 275     SingleFieldHashIndexInfo *info = (SingleFieldHashIndexInfo*) indInfo;
 276     DataType type = info->type;
 277     char *name = info->fldName;
 278     int offset  = info->offset;
 279     int noOfBuckets = info->noOfBuckets;
 280
 281     printDebug(DM_HashIndex, "Updating hash index node for field %s", name);
 282
 283     //check whether the index key is updated or not
 284     //if it is not updated return from here
 285     void *keyPtr =(void*)((char*)tuple + offset);
 286     //Iterate through the bind list and check
 287     FieldIterator fldIter = tbl->fldList_.getIterator();
 288     void *newKey = NULL;
 289     while (fldIter.hasElement())
 290     {
 291         FieldDef def = fldIter.nextElement();
 292         if (0 == strcmp(def.fldName_, name))
 293         {
 294             if (NULL == def.bindVal_)
 295                 return OK;
 296             bool result = AllDataType::compareVal(keyPtr, def.bindVal_,
 297                                 OpEquals, def.type_, def.length_);
 298             if (result) return OK; else newKey = def.bindVal_;
 299         }
 300     }
 301     printDebug(DM_HashIndex, "Updating hash index node: Key value is updated");
 302
 303     if (newKey == NULL)
 304     {
 305         printError(ErrSysInternal,"Internal Error:: newKey is Null");
 306         return ErrSysInternal;
 307     }
 308     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 309
 310     Bucket* buckets = (Bucket*)citer.nextElement();
 311
 312     //remove the node whose key is updated
 313     int bucketNo = computeHashBucket(type,
 314                         keyPtr, noOfBuckets);
 315     printDebug(DM_HashIndex, "Updating hash index node: Bucket for old value is %d", bucketNo);
 316     Bucket *bucket = &buckets[bucketNo];
 317
 318     //it may run into deadlock, when two threads updates tuples which falls in
 319     //same buckets.So take both the mutex one after another, which will reduce the
 320     //deadlock window.
 321     int ret = bucket->mutex_.getLock(tbl->db_->procSlot);
 322     if (ret != 0)
 323     {
 324         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",bucketNo);
 325         return ErrLockTimeOut;
 326     }
 327     //insert node for the updated key value
 328     int newBucketNo = computeHashBucket(type,
 329                         newKey, noOfBuckets);
 330     printDebug(DM_HashIndex, "Updating hash index node: Bucket for new value is %d", newBucketNo);
 331
 332     Bucket *bucket1 = &buckets[newBucketNo];
 333     bucket1->mutex_.getLock(tbl->db_->procSlot);
 334     if (ret != 0)
 335     {
 336         printError(ErrLockTimeOut,"Unable to acquire bucket Mutex for bucket %d",newBucketNo);
 337         return ErrLockTimeOut;
 338     }
 339
 340     HashIndexNode *head1 = (HashIndexNode*) bucket->bucketList_;
 341     if (head1)
 342     {
 343         BucketList list1(head1);
 344         printDebug(DM_HashIndex, "Updating hash index node: Removing node from list with head %x", head1);
 345         list1.remove((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr);
 346     }
 347     else
 348     {
 349         printError(ErrSysInternal,"Update: Bucket list is null");
 350         return ErrSysInternal;
 351     }
 352     DbRetVal rc = OK;
 353     if (undoFlag) {
 354          rc = tr->appendLogicalUndoLog(tbl->sysDB_, DeleteHashIndexOperation,
 355                                 tuple, sizeof(void*), indexPtr);
 356         if (rc !=OK)
 357         {
 358             //TODO::add it back to the bucket list
 359             bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 360             bucket->mutex_.releaseLock(tbl->db_->procSlot);
 361             return rc;
 362         }
 363     }
 364     HashIndexNode *head2 = (HashIndexNode*) bucket1->bucketList_;
 365     //Note:: the tuple will be in the same address location
 366     //so not changing the keyptr and tuple during append
 367     //only bucket where this node resides will only change
 368     //if the index key is updated.
 369     if (!head2)
 370     {
 371         HashIndexNode *firstNode= (HashIndexNode*)(((Chunk*)iptr->hashNodeChunk_)->allocate(tbl->db_));
 372         firstNode->ptrToKey_ = keyPtr;
 373         firstNode->ptrToTuple_ = tuple;
 374         firstNode->next_ = NULL;
 375         bucket1->bucketList_ = (HashIndexNode*)firstNode;
 376         printDebug(DM_HashIndex, "Updating hash index node: Adding new node %x:Head is empty", firstNode);
 377     }
 378     else
 379     {
 380         BucketList list2(head2);
 381         printDebug(DM_HashIndex, "Updating hash index node: Adding node to list with head %x", head2);
 382         list2.insert((Chunk*)iptr->hashNodeChunk_, tbl->db_, keyPtr, tuple);
 383     }
 384     if (undoFlag) {
 385
 386         rc = tr->appendLogicalUndoLog(tbl->sysDB_, InsertHashIndexOperation,
 387                                 tuple, sizeof(void*), indexPtr);
 388         if (rc !=OK)
 389         {
 390             //TODO::revert back the changes:delete and add the node + remove the logical undo log
 391             //of the  DeleteHashIndexOperation
 392         }
 393     }
 394     bucket1->mutex_.releaseLock(tbl->db_->procSlot);
 395     bucket->mutex_.releaseLock(tbl->db_->procSlot);
 396     return rc;
 397 }