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 HashIndex::checkForUniqueKey(IndexNode *head, HashIndexInfo *info, void *tuple)
  77 {
  78     return false;
  79 }
  80 */
  81
  82 DbRetVal TrieIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
  83 {
  84     DbRetVal rv = OK;
  85     HashIndexInfo *info = (HashIndexInfo*) indInfo;
  86     CINDEX *iptr = (CINDEX*)indexPtr;
  87     char hashValue[TRIE_MAX_LENGTH];
  88     void *keyPtr =(void*)((char*)tuple + info->fldOffset);
  89     //for varchar ptr to value is stored in tuple
  90     if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
  91     computeHashValues(info->type, keyPtr, hashValue, info->compLength);
  92     Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
  93     Chunk *chunk = (Chunk*) iptr->chunkPtr_;
  94     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
  95     TrieNode* start = (TrieNode*)citer.nextElement();
  96     //if(start) displayAll(start);
  97     int cnt=0;
  98     if (NULL == start) {
  99         //first value is inserted into the trie index
 100         start = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
 101         if (NULL == start) {
 102             printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
 103             return rv;
 104         }
 105     }
 106     char **prev = NULL;
 107     while(-1 != hashValue[cnt+1]) {
 108         prev = (char**)&(start->next_[hashValue[cnt]]);
 109         if (*prev)
 110         {
 111             start = (TrieNode*) *prev;
 112             cnt++;
 113             continue;
 114         }
 115         //allocate trie node
 116         TrieNode *newNode = (TrieNode*) chunk->tryAllocate(tbl->db_, &rv);
 117         if (NULL == newNode) {
 118             printError(ErrSysInternal, "Could not allocate trie node %d\n", rv);
 119             return rv;
 120         }
 121         //set the previous trie node ptr to this node
 122         *prev = (char*)newNode;
 123         start = newNode;
 124         cnt++;
 125     }
 126     void **ptr = (void**)&(start->head_[hashValue[cnt]]);
 127     rv = addToValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
 128     if (OK != rv) return rv;
 129
 130     //create logical undo log
 131     TrieUndoLogInfo hInfo;
 132     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 133     hInfo.bucket_ = NULL;
 134     hInfo.tuple_ = tuple;
 135     hInfo.keyPtr_ = keyPtr;
 136
 137     if (!loadFlag) {
 138         rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, InsertTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
 139          //TODO:: if it fails need to remove the element from the bucket
 140     }
 141     return rv;
 142 }
 143 DbRetVal TrieIndex::addToValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
 144 {
 145     IndexNode *head = (IndexNode*) *ptr;
 146     printDebug(DM_TrieIndex, "TrieIndex insert into bucket list");
 147     DbRetVal rv = OK;
 148     if (!head)
 149     {
 150         printDebug(DM_TrieIndex, "TrieIndex insert head is empty");
 151         IndexNode *firstNode= NULL;
 152         firstNode= (IndexNode*) hIdxNodeChunk->tryAllocate(db, &rv);
 153         if (firstNode == NULL){
 154             printError(rv, "Unable to allocate index node for Trie index after retry");
 155             return rv;
 156         }
 157         firstNode->ptrToKey_ = keyPtr;
 158         firstNode->ptrToTuple_ = tuple;
 159         firstNode->next_ = NULL;
 160         if (0 != Mutex::CASL((long*)ptr, 0, (long)firstNode)) {
 161             printError(ErrLockTimeOut, "Trie Index bucket lock timeout.. retry");
 162             hIdxNodeChunk->free(db, firstNode);
 163             return ErrLockTimeOut;
 164         }
 165         printDebug(DM_TrieIndex, "TrieIndex insert new node %x in empty bucket", head);
 166     }
 167     else
 168     {
 169         BucketList list(head);
 170         rv = list.insert(hIdxNodeChunk, db, keyPtr, tuple);
 171         if (rv !=OK) {
 172             printError(rv, "unable to insert into Trie bucketlist rv:%d", rv);
 173             return rv;
 174         }
 175     }
 176     return OK;
 177 }
 178
 179 DbRetVal TrieIndex::removeFromValueList(Database *db, void **ptr, Chunk *hIdxNodeChunk, void *tuple, void *keyPtr)
 180 {
 181     IndexNode *head = (IndexNode*) *ptr;
 182     printDebug(DM_TrieIndex, "TrieIndex remove from bucket list");
 183     DbRetVal rv = OK;
 184     if (!head)
 185     {
 186         printError(rv, "Trie value list head is empty");
 187         return rv;
 188     }
 189     else
 190     {
 191         BucketList list(head);
 192         rv = list.remove(hIdxNodeChunk, db, keyPtr);
 193         if (SplCase == rv)
 194         {
 195             rv = OK;
 196             printDebug(DM_TrieIndex, "Removing trie index node from head ");
 197             if (0 != Mutex::CASL((long*)ptr,
 198                 (long)head, (long)list.getBucketListHead())) {
 199                printError(ErrSysFatal, "Lock time out for trie bucket. retry\n");
 200                return ErrLockTimeOut;
 201              }
 202         }
 203         if (rv !=OK) {
 204             printError(rv, "unable to remove from Trie bucketlist rv:%d", rv);
 205             return rv;
 206         }
 207     }
 208     return OK;
 209
 210 }
 211
 212 DbRetVal TrieIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 213 {
 214     DbRetVal rv = OK;
 215     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 216     CINDEX *iptr = (CINDEX*)indexPtr;
 217     char hashValue[TRIE_MAX_LENGTH];
 218     void *keyPtr =(void*)((char*)tuple + info->fldOffset);
 219     Chunk *hIdxNodeChunk = (Chunk*)iptr->hashNodeChunk_;
 220     //for varchar ptr to value is stored in tuple
 221     if (info->type == typeVarchar) keyPtr = (void *) *(long *) keyPtr;
 222     computeHashValues(info->type, keyPtr, hashValue, info->compLength);
 223     ChunkIterator citer = CatalogTableINDEX::getIterator(indexPtr);
 224     TrieNode* start = (TrieNode*)citer.nextElement();
 225     int cnt=0;
 226     if (NULL == start) {
 227         printError(ErrSysInternal, "No trie nodes found %d\n", rv);
 228         return rv;
 229     }
 230     char **iter = NULL;
 231     while(-1 != hashValue[cnt+1]) {
 232         iter = (char**)&(start->next_[hashValue[cnt]]);
 233         if (! *iter)
 234         {
 235             printError(ErrNotFound, "No trie node found %d\n", rv);
 236             return ErrNotFound;
 237         }
 238         //traverse till the end
 239         start = (TrieNode*) *iter;
 240         cnt++;
 241     }
 242     void **ptr = (void**)&(start->head_[hashValue[cnt]]);
 243     rv = removeFromValueList(tbl->db_, ptr, hIdxNodeChunk, tuple, keyPtr);
 244     if (OK != rv) return rv;
 245
 246     //create logical undo log
 247     TrieUndoLogInfo hInfo;
 248     hInfo.metaData_ = tbl->db_->getMetaDataPtr();
 249     hInfo.bucket_ = NULL;
 250     hInfo.tuple_ = tuple;
 251     hInfo.keyPtr_ = keyPtr;
 252
 253     if (!loadFlag) {
 254         rv = tr->appendLogicalTrieUndoLog(tbl->sysDB_, DeleteTrieIndexOperation, &hInfo, sizeof(TrieUndoLogInfo));
 255          //TODO:: if it fails need to remove the element from the bucket
 256     }
 257     return rv;
 258 }
 259
 260 DbRetVal TrieIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool loadFlag)
 261 {
 262     DbRetVal rv = OK;
 263     return rv;
 264 }
 265
 266 DbRetVal TrieIndex::insertLogicalUndoLog(Database *sysdb, void *data)
 267 {
 268     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 269     Chunk *hChunk = (Chunk *) info->hChunk_;
 270     Database db;
 271     db.setMetaDataPtr((DatabaseMetaData *) info->metaData_);
 272     db.setProcSlot(sysdb->procSlot);
 273     IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
 274     BucketList list(head);
 275     DbRetVal rv = list.insert(hChunk, &db, info->keyPtr_, info->tuple_);
 276     if (rv != OK)
 277     {
 278         printError(ErrLockTimeOut, "Unable to add to bucket..retry\n");
 279         return ErrLockTimeOut;
 280     }
 281     return OK;
 282 }
 283
 284 DbRetVal TrieIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
 285 {
 286     TrieUndoLogInfo *info = (TrieUndoLogInfo *) data;
 287     Chunk *hChunk = (Chunk *) info->hChunk_;
 288     Database db;
 289     db.setMetaDataPtr((DatabaseMetaData *)info->metaData_);
 290     db.setProcSlot(sysdb->procSlot);
 291     IndexNode *head = (IndexNode *)((Bucket *)info->bucket_)->bucketList_;
 292     BucketList list(head);
 293     DbRetVal rc = list.remove(hChunk, &db, info->keyPtr_);
 294     if (SplCase == rc) {
 295      ;//TODO
 296     }else if (rc != OK) {
 297          printError(ErrLockTimeOut, "Unable to remove hash index node");
 298          return ErrLockTimeOut;
 299     }
 300     return OK;
 301 }
 302 void TrieIndex::displayAll(TrieNode *start, int level)
 303 {
 304    printTrieNode(start, level);
 305    level++;
 306    for (int i=0; i < TRIE_SIZE; i++)
 307    {
 308        if (start->next_[i]) displayAll(start->next_[i], level);
 309    }
 310 }
 311 void TrieIndex::printTrieNode(TrieNode *node, int level)
 312 {
 313     printf("Trie %x Level %d child:", node, level);
 314     for (int i=0; i < TRIE_SIZE; i++)
 315     {
 316         printf("%x ", node->next_[i]);
 317     }
 318     printf("bucket:", node);
 319     for (int i=0; i < TRIE_SIZE; i++)
 320     {
 321         printf("%x ", node->head_[i]);
 322         if ( node->head_[i]) {
 323             printf("{ ");
 324             BucketList list(node->head_[i]);
 325             list.print();
 326             printf("} ");
 327         }
 328     }
 329     printf("\n");
 330 }