src/storage/TrieIndex.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 //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)
  28 {
  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
  33     return 9;
  34 }
  35
  36 void TrieIndex::computeHashValues(DataType type, void *key, char *in, int length)
  37 {
  38     if (typeInt == type ) {
  39         int val = *(int*)key;
  40         sprintf(in, "%d", val);
  41         int i=0;
  42         while (in[i] != '\0')
  43         {
  44             in[i] = hashString(in[i]);
  45             printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
  46             i++;
  47         }
  48         in[i] = -1;
  49     }else if (typeLongLong == type) {
  50         long val = *(long*)key;
  51         sprintf(in, "%lld", val);
  52         int i=0;
  53         while (in[i] != '\0')
  54         {
  55             in[i] = hashString(in[i]);
  56             printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
  57             i++;
  58         }
  59         in[i] = -1;
  60     }else if (typeString == type || typeVarchar == type) {
  61         char *val = (char*) key;
  62         int i=0;
  63         while (*val != '\0')
  64         {
  65             in[i] = hashString(*val);
  66             printDebug(DM_TrieIndex, "Hash Value Pos:%d Hash:%d\n", i, in[i]);
  67             val++;
  68             i++;
  69         }
  70         in[i] = (char)-1;
  71     }else
  72         printError(ErrSysFatal,"Type not supported for trie hashing\n");
  73     return ;
  74 }
  75
  76 bool TrieIndex::checkForUniqueKey(IndexNode *head, IndexInfo *info, void *tuple)
  77 {
  78     if (!head) return false;
  79     int offset = info->fldOffset;
  80     DataType type = info->type;
  81     BucketList list(head);
  82     BucketIter iter = list.getIterator();
  83     IndexNode *node;
  84     void *bucketTuple;
  85     printDebug(DM_TrieIndex, "TrieIndex insert Checking for unique");
  86     bool res = false;
  87     while((node = iter.next()) != NULL)
  88     {
  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);
  93         else
  94            res = AllDataType::compareVal((void*)*(long *)((char*)bucketTuple +offset),
  95                    (void*)*(long *)((char*)tuple +offset), OpEquals,type, info->compLength);
  96         if (res)
  97         {
  98             printError(ErrUnique, "Unique key violation");
  99             return true;
 100         }
 101     }
 102     return false;
 103 }
 104
 105
 106 DbRetVal TrieIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 107 {
 108     DbRetVal rv = OK;
 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);
 121     int cnt=0;
 122     if (NULL == start) {
 123         //first value is inserted into the trie index
 124         start = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
 125         if (NULL == start) {
 126             printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
 127             return rv;
 128         }
 129     }
 130     char **prev = NULL;
 131     while(-1 != hashValue[cnt+1]) {
 132         prev = (char**)&(start->next_[hashValue[cnt]]);
 133         if (*prev)
 134         {
 135             start = (TrieNode*) *prev;
 136             cnt++;
 137             continue;
 138         }
 139         //allocate trie node
 140         TrieNode *newNode = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
 141         if (NULL == newNode) {
 142             printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
 143             return rv;
 144         }
 145         //set the previous trie node ptr to this node
 146         *prev = (char*)newNode;
 147         start = newNode;
 148         cnt++;
 149     }
 150     void **ptr = (void**)&(start->head_[hashValue[cnt]]);
 151     rv = addToValueList(tbl->db_, ptr, hIdxNodeChunk, indInfo, tuple, keyPtr);
 152     if (OK != rv) return rv;
 153
 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;
 161
 162     if (!loadFlag) {
 163         rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, InsertTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
 164          //TODO:: if it fails need to remove the element from the bucket
 165     }
 166     return rv;
 167 }
 168 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk,
 169                                    IndexInfo *info, void *tuple, void *keyPtr)
 170 {
 171     IndexNode *head = (IndexNode*) *ptr;
 172     if (info->isUnique)
 173     {
 174         bool isKeyPresent = checkForUniqueKey(head, info, tuple);
 175         if (isKeyPresent) return ErrUnique;
 176     }
 177     printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
 178     DbRetVal rv = OK;
 179     if (!head)
 180     {
 181         printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
 182         IndexNode *firstNode= NULL;
 183         firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
 184         if (firstNode == NULL){
 185             printError(rv, "Unable to allocate index node for Trie index after retry");
 186             return rv;
 187         }
 188         firstNode->ptrToKey_ = keyPtr;
 189         firstNode->ptrToTuple_ = tuple;
 190         firstNode->next_ = NULL;
 191         if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
 192             printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
 193             hIdxNodeChunk->free(db, firstNode);
 194             return ErrLockTimeOut;
 195         }
 196         printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
 197     }
 198     else
 199     {
 200         BucketList list(head);
 201         rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
 202         if (rv !=OK) {
 203             printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
 204             return rv;
 205         }
 206     }
 207     return OK;
 208 }
 209
 210 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
 211 {
 212     IndexNode *head = (IndexNode*) *ptr;
 213     printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
 214     DbRetVal rv = OK;
 215     if (!head)
 216     {
 217         rv = ErrSysFatal;
 218         printError(rv, "Fatal:Trie value list head is empty");
 219         return rv;
 220     }
 221     else
 222     {
 223         BucketList list(head);
 224         rv = list.remove(hIdxNodeChunk, db, keyPtr);
 225         if (SplCase == rv)
 226         {
 227             rv = OK;
 228             printDebug(DM_TrieIndex, "Removing trie index node from head ");
 229             if (0 != Mutex::CASL((long*)ptr,
 230                 (long)head, (long)list.getBucketListHead())) {
 231                printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
 232                return ErrLockTimeOut;
 233              }
 234         }
 235         if (rv !=OK) {
 236             printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
 237             return rv;
 238         }
 239     }
 240     return OK;
 241
 242 }
 243
 244 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 245 {
 246     DbRetVal rv = OK;
 247     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 248     CINDEX *iptr = (CINDEX*)indexPtr;
 249     char hashValue[TRIE_MAX_LENGTH];
 250     void *keyPtr =(void*)((char*)tuple + info->fldOffset);
 251     Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
 252     //for varchar ptr to value is stored in tuple
 253     if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
 254     computeHashValues(info->type, keyPtr, hashValue, info->compLength);
 255     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 256     TrieNode* start = (TrieNode*)citer.nextElement();
 257     int cnt=0;
 258     if (NULL == start) {
 259         printError(ErrSysInternal, "No trie nodes found %d\n", rv);
 260         return rv;
 261     }
 262     char **iter = NULL;
 263     while(-1 != hashValue[cnt+1]) {
 264         iter = (char**)&(start->next_[hashValue[cnt]]);
 265         if (! *iter)
 266         {
 267             printError(ErrNotFound, "No trie node found %d\n", rv);
 268             return ErrNotFound;
 269         }
 270         //traverse till the end
 271         start = (TrieNode*) *iter;
 272         cnt++;
 273     }
 274     void **ptr = (void**)&(start->head_[hashValue[cnt]]);
 275     rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
 276     if (OK != rv) return rv;
 277
 278     //create logical undo log
 279     TrieUndoLogInfo hInfo;
 280     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 281     hInfo.bucketPtr_ = ptr;
 282     hInfo.tuple_ = tuple;
 283     hInfo.keyPtr_ = keyPtr;
 284     hInfo.hChunk_ = hIdxNodeChunk;
 285
 286     if (!loadFlag) {
 287         rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
 288          //TODO:: if it fails need to remove the element from the bucket
 289     }
 290     return rv;
 291 }
 292
 293 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 294 {
 295     DbRetVal rv = OK;
 296     printError(ErrNotYet, "Not Yet Implemented");
 297     return rv;
 298 }
 299
 300 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
 301 {
 302     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 303     Chunk *hChunk = (Chunk *) info->hChunk_;
 304     Database db;
 305     db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
 306     db.setProcSlot(sysdb->procSlot);
 307     void **bkt =  info->bucketPtr_;
 308     IndexNode *head = (IndexNode *)*bkt;
 309     BucketList list(head);
 310     DbRetVal rv = OK;
 311     if (!head)
 312     {
 313         printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
 314         IndexNode *firstNode= NULL;
 315         firstNode= (IndexNode*) hChunk->tryAllocate(sysdb, &rv);
 316         if (firstNode == NULL){
 317             printError(rv, "Unable to allocate index node for Trie index after retry");
 318             return rv;
 319         }
 320         firstNode->ptrToKey_ = info->keyPtr_;
 321         firstNode->ptrToTuple_ = info->tuple_;
 322         firstNode->next_ = NULL;
 323         if (0 != Mutex::CASL((long*)bkt, 0, (long)firstNode)) {
 324             printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
 325             hChunk->free(sysdb, firstNode);
 326             return ErrLockTimeOut;
 327         }
 328         printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
 329         return OK;
 330     }
 331
 332     rv = list.insert(hChunk, sysdb, info->keyPtr_, info->tuple_);
 333     if (rv != OK)
 334     {
 335         printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
 336         return ErrLockTimeOut;
 337     }
 338     return OK;
 339 }
 340
 341 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
 342 {
 343     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 344     Chunk *hChunk = (Chunk *) info->hChunk_;
 345     Database db;
 346     db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
 347     db.setProcSlot(sysdb->procSlot);
 348     void **bkt = info->bucketPtr_;
 349     IndexNode *head = (IndexNode *)*bkt;
 350     BucketList list(head);
 351     DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
 352     *bkt = list.getBucketListHead();
 353     if (SplCase == rc) {
 354         if (0 != Mutex::CASL((long*)bkt,
 355             (long)*bkt,
 356             (long)list.getBucketListHead()))
 357          {
 358              printError(ErrLockTimeOut, "Unable to set the head of trie index bucket\n");
 359              return ErrLockTimeOut;
 360          }
 361
 362     }else if (rc != OK) {
 363          printError(ErrLockTimeOut, "Unable to remove trie index node");
 364          return ErrLockTimeOut;
 365     }
 366     return OK;
 367 }
 368 void TrieIndex::displayAll(TrieNode *start, int level)
 369 {
 370    printTrieNode(start, level);
 371    level++;
 372    for (int i=0; i < TRIE_SIZE; i++)
 373    {
 374        if (start->next_[i]) displayAll(start->next_[i], level);
 375    }
 376 }
 377 void TrieIndex::printTrieNode(TrieNode *node, int level)
 378 {
 379     printf("Trie %x Level %d child:", node, level);
 380     for (int i=0; i < TRIE_SIZE; i++)
 381     {
 382         printf("%x ", node->next_[i]);
 383     }
 384     printf("bucket:", node);
 385     for (int i=0; i < TRIE_SIZE; i++)
 386     {
 387         printf("%x ", node->head_[i]);
 388         if ( node->head_[i]) {
 389             printf("{ ");
 390             BucketList list(node->head_[i]);
 391             list.print();
 392             printf("} ");
 393         }
 394     }
 395     printf("\n");
 396 }