src/relational/index/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
 169 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk,
 170                                    IndexInfo *info, void *tuple, void *keyPtr)
 171 {
 172     IndexNode *head = (IndexNode*) *ptr;
 173     if (info->isUnique)
 174     {
 175         bool isKeyPresent = checkForUniqueKey(head, info, tuple);
 176         if (isKeyPresent) return ErrUnique;
 177     }
 178     printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
 179     DbRetVal rv = OK;
 180     if (!head)
 181     {
 182         printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
 183         IndexNode *firstNode= NULL;
 184         firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
 185         if (firstNode == NULL){
 186             printError(rv, "Unable to allocate index node for Trie index after retry");
 187             return rv;
 188         }
 189         firstNode->ptrToKey_ = keyPtr;
 190         firstNode->ptrToTuple_ = tuple;
 191         firstNode->next_ = NULL;
 192         if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
 193             printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
 194             hIdxNodeChunk->free(db, firstNode);
 195             return ErrLockTimeOut;
 196         }
 197         printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
 198     }
 199     else
 200     {
 201         BucketList list(head);
 202         rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
 203         if (rv !=OK) {
 204             printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
 205             return rv;
 206         }
 207     }
 208     return OK;
 209 }
 210
 211 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
 212 {
 213     IndexNode *head = (IndexNode*) *ptr;
 214     printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
 215     DbRetVal rv = OK;
 216     if (!head)
 217     {
 218         rv = ErrSysFatal;
 219         printError(rv, "Fatal:Trie value list head is empty");
 220         return rv;
 221     }
 222     else
 223     {
 224         BucketList list(head);
 225         rv = list.remove(hIdxNodeChunk, db, keyPtr);
 226         if (SplCase == rv)
 227         {
 228             rv = OK;
 229             printDebug(DM_TrieIndex, "Removing trie index node from head ");
 230             if (0 != Mutex::CASL((long*)ptr,
 231                 (long)head, (long)list.getBucketListHead())) {
 232                printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
 233                return ErrLockTimeOut;
 234              }
 235         }
 236         if (rv !=OK) {
 237             printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
 238             return rv;
 239         }
 240     }
 241     return OK;
 242
 243 }
 244
 245 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 246 {
 247     DbRetVal rv = OK;
 248     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 249     CINDEX *iptr = (CINDEX*)indexPtr;
 250     char hashValue[TRIE_MAX_LENGTH];
 251     void *keyPtr =(void*)((char*)tuple + info->fldOffset);
 252     Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
 253     //for varchar ptr to value is stored in tuple
 254     if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
 255     computeHashValues(info->type, keyPtr, hashValue, info->compLength);
 256     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 257     TrieNode* start = (TrieNode*)citer.nextElement();
 258     int cnt=0;
 259     if (NULL == start) {
 260         printError(ErrSysInternal, "No trie nodes found %d\n", rv);
 261         return rv;
 262     }
 263     char **iter = NULL;
 264     while(-1 != hashValue[cnt+1]) {
 265         iter = (char**)&(start->next_[hashValue[cnt]]);
 266         if (! *iter)
 267         {
 268             printError(ErrNotFound, "No trie node found %d\n", rv);
 269             return ErrNotFound;
 270         }
 271         //traverse till the end
 272         start = (TrieNode*) *iter;
 273         cnt++;
 274     }
 275     void **ptr = (void**)&(start->head_[hashValue[cnt]]);
 276     rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
 277     if (OK != rv) return rv;
 278
 279     //create logical undo log
 280     TrieUndoLogInfo hInfo;
 281     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 282     hInfo.bucketPtr_ = ptr;
 283     hInfo.tuple_ = tuple;
 284     hInfo.keyPtr_ = keyPtr;
 285     hInfo.hChunk_ = hIdxNodeChunk;
 286
 287     if (!loadFlag) {
 288         rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
 289          //TODO:: if it fails need to remove the element from the bucket
 290     }
 291     return rv;
 292 }
 293
 294 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 295 {
 296     DbRetVal rv = OK;
 297     printError(ErrNotYet, "Not Yet Implemented");
 298     return rv;
 299 }
 300
 301 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
 302 {
 303     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 304     Chunk *hChunk = (Chunk *) info->hChunk_;
 305     Database db;
 306     db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
 307     db.setProcSlot(sysdb->procSlot);
 308     void **bkt =  info->bucketPtr_;
 309     IndexNode *head = (IndexNode *)*bkt;
 310     BucketList list(head);
 311     DbRetVal rv = OK;
 312     if (!head)
 313     {
 314         printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
 315         IndexNode *firstNode= NULL;
 316         firstNode= (IndexNode*) hChunk->tryAllocate(sysdb, &rv);
 317         if (firstNode == NULL){
 318             printError(rv, "Unable to allocate index node for Trie index after retry");
 319             return rv;
 320         }
 321         firstNode->ptrToKey_ = info->keyPtr_;
 322         firstNode->ptrToTuple_ = info->tuple_;
 323         firstNode->next_ = NULL;
 324         if (0 != Mutex::CASL((long*)bkt, 0, (long)firstNode)) {
 325             printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
 326             hChunk->free(sysdb, firstNode);
 327             return ErrLockTimeOut;
 328         }
 329         printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
 330         return OK;
 331     }
 332
 333     rv = list.insert(hChunk, sysdb, info->keyPtr_, info->tuple_);
 334     if (rv != OK)
 335     {
 336         printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
 337         return ErrLockTimeOut;
 338     }
 339     return OK;
 340 }
 341
 342 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
 343 {
 344     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 345     Chunk *hChunk = (Chunk *) info->hChunk_;
 346     Database db;
 347     db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
 348     db.setProcSlot(sysdb->procSlot);
 349     void **bkt = info->bucketPtr_;
 350     IndexNode *head = (IndexNode *)*bkt;
 351     BucketList list(head);
 352     DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
 353     *bkt = list.getBucketListHead();
 354     if (SplCase == rc) {
 355         if (0 != Mutex::CASL((long*)bkt,
 356             (long)*bkt,
 357             (long)list.getBucketListHead()))
 358          {
 359              printError(ErrLockTimeOut, "Unable to set the head of trie index bucket\n");
 360              return ErrLockTimeOut;
 361          }
 362
 363     }else if (rc != OK) {
 364          printError(ErrLockTimeOut, "Unable to remove trie index node");
 365          return ErrLockTimeOut;
 366     }
 367     return OK;
 368 }
 369
 370 void TrieIndex::displayAll(TrieNode *start, int level)
 371 {
 372    printTrieNode(start, level);
 373    level++;
 374    for (int i=0; i < TRIE_SIZE; i++)
 375    {
 376        if (start->next_[i]) displayAll(start->next_[i], level);
 377    }
 378 }
 379
 380 void TrieIndex::printTrieNode(TrieNode *node, int level)
 381 {
 382     printf("Trie %x Level %d child:", node, level);
 383     for (int i=0; i < TRIE_SIZE; i++)
 384     {
 385         printf("%x ", node->next_[i]);
 386     }
 387     printf("bucket:", node);
 388     for (int i=0; i < TRIE_SIZE; i++)
 389     {
 390         printf("%x ", node->head_[i]);
 391         if ( node->head_[i]) {
 392             printf("{ ");
 393             BucketList list(node->head_[i]);
 394             list.print();
 395             printf("} ");
 396         }
 397     }
 398     printf("\n");
 399 }