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