src/storage/TreeIndex.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 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
  26 {
  27     printDebug(DM_TreeIndex, "\nInside TreeNode::Insert - 1");
  28     HashIndexInfo *info = (HashIndexInfo*) indInfo;
  29     CINDEX *iptr = (CINDEX*)indexPtr;
  30     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
  31     DbRetVal rc = OK;
  32     int offset = info->fldOffset;
  33     DataType type = info->type;
  34     printDebug(DM_TreeIndex, "Inserting tree index node for  %s", iptr->indName_);
  35     void *keyPtr =(void*)((char*)tuple + offset);
  36     if (start == NULL)
  37     {
  38         //TODO::there is chance that two threads can insert first node at
  39         //same time causing the first tree node to leak.
  40         printDebug(DM_TreeIndex, "\nInside if - start=NULL");
  41         Chunk *chunk = (Chunk*) iptr->chunkPtr_;
  42         TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
  43         if (tnode == NULL)
  44         {
  45             printDebug(DM_TreeIndex, "\nExit TreeNode::Insert - 1 tnode=NULL");
  46             return rc;
  47         }
  48         tnode->mutex_.init();
  49         tnode->min_ = tuple;
  50         tnode->max_ = tuple;
  51         tnode->noElements_ =1;
  52         tnode->next_ = NULL;
  53         tnode->prev_ = NULL;
  54             tnode->balance_ = 0;
  55         char **rec = (char**)((char*) tnode + sizeof(TreeNode));
  56         printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
  57         *rec = (char*) tuple;
  58         iptr->hashNodeChunk_ = tnode;
  59     }else {
  60         rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
  61         if (rc != OK)
  62             printError(rc, "Error in tree node insertion\n");
  63     }
  64
  65     printDebug(DM_TreeIndex, "\nExit TreeNode::Insert - 1");
  66     return rc;
  67 }
  68 void TreeNode::displayAll(int fldOffset)
  69 {
  70     TreeNode *iter = this;
  71     int loc=0;
  72     while(iter->prev_)
  73     {
  74         printf("PRABA::ITERATING\n");
  75         iter = iter->prev_;
  76     }
  77     printf("\nDISPLAY NODES:START\n");
  78     while(iter != NULL)
  79     {
  80         char **rec = (char**)((char*) iter + sizeof(TreeNode));
  81         printf("\n>>>");
  82         for(loc=0;loc<iter->noElements_;loc++)
  83         {
  84             printf("%d,",*((int*)((char*) *(rec + loc )+fldOffset)));
  85         }
  86         iter = iter->next_;
  87     }
  88     printf("-----\n");
  89     printf("DISPLAY NODES:END\n");
  90 }
  91 void TreeNode::displayAll(IndexInfo *indInfo, void *indexPtr)
  92 {
  93     HashIndexInfo *info = (HashIndexInfo*) indInfo;
  94     CINDEX *iptr = (CINDEX*)indexPtr;
  95     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
  96     int offset = info->fldOffset;
  97     DataType type = info->type;
  98     int noOfBuckets = info->noOfBuckets;
  99     TreeNode *iter =start;
 100     int loc=0;
 101     while(iter->prev_)
 102     {
 103         iter = iter->prev_;
 104     }
 105     printf("\nDISPLAY NODES:START\n");
 106     while(iter != NULL)
 107     {
 108         char **rec = (char**)((char*) iter + sizeof(TreeNode));
 109         printf("\n>>>");
 110         for(loc=0;loc<iter->noElements_;loc++)
 111         {
 112             printf("%d,",*((int*)((char*) *(rec + loc )+info->fldOffset)));
 113         }
 114         iter = iter->next_;
 115     }
 116     printf("-----\n");
 117     printf("DISPLAY NODES:END\n");
 118 }
 119 DbRetVal TreeNode::insert(Database *db, IndexInfo *indInfo, void *indexPtr, void *tuple)
 120 {
 121     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 122     CINDEX *iptr = (CINDEX*)indexPtr;
 123     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
 124     int offset = info->fldOffset;
 125     DataType type = info->type;
 126     int noOfBuckets = info->noOfBuckets;
 127     TreeNode *iter =start; void *record = NULL;
 128     TreeNode *prev = start;
 129     char *keyVal = (char*) tuple + info->fldOffset;
 130     DbRetVal rc = OK;
 131     bool recordInserted = false;
 132     printDebug(DM_TreeIndex, "\nInside TreeNode::Insert - 2");
 133     int count =0;
 134     int direction = 0;  //0:current,1:right,2:rightLeft,-1:left,-2:leftRight
 135     DbRetVal rv = OK;
 136     while(iter != NULL)
 137     {
 138         record = ((char*)iter->max_)+ info->fldOffset;
 139         printDebug(DM_TreeIndex, "\n%d---%d", *((int*)keyVal), *((int*)record));
 140         bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan,
 141                                               info->type, info->compLength);
 142         if (result)
 143         {
 144             if(direction == -1)
 145             {
 146                 direction = -2;
 147                 break;
 148             }
 149             direction = 1;
 150             prev = iter;
 151             iter = iter->next_;
 152             printDebug(DM_TreeIndex, "\n2Insert- > ");
 153         }else
 154         {
 155             record = ((char*)iter->min_)+ info->fldOffset;
 156             result = AllDataType::compareVal(keyVal, record, OpLessThan,
 157                                              info->type, info->compLength);
 158             if (result) {
 159                 if(direction == 1)
 160                 {
 161                     direction = 2;
 162                     break;
 163                 }
 164                 direction = -1;
 165                 prev = iter;
 166                 iter = iter->prev_;
 167                 printDebug(DM_TreeIndex, "\n2Insert- < ");
 168             }
 169             else
 170             {
 171                 printDebug(DM_TreeIndex, "\n2Insert- = ");
 172                 direction=0;
 173                 break;
 174             }
 175         }
 176     }
 177
 178     if(direction == 2)
 179     {
 180         //Check the size of the prev node....
 181         //if not full then move the iter to prev and call insertLast()
 182         //else call insertFirst();
 183
 184         if((iter->prev_ != NULL) && (iter->prev_->noElements_ < noOfBuckets) )
 185         {
 186             printDebug(DM_TreeIndex, "\n2Insert- d=2 if ");
 187             iter = iter->prev_;
 188             rv  = insert(1, db, indInfo, iptr, tuple, iter);
 189         }
 190         else
 191         {
 192             printDebug(DM_TreeIndex, "\n2Insert- d=2 else ");
 193             rv  = insert(-1, db, indInfo, iptr, tuple, iter);
 194         }
 195     }
 196     else if(direction == 1)
 197     {
 198         iter = prev;
 199         if((iter->noElements_ >= noOfBuckets) && (iter->next_ != NULL)
 200              && (iter->next_->noElements_ < noOfBuckets) )
 201         {
 202             printDebug(DM_TreeIndex, "\n2Insert- d=1 if ");
 203             iter = iter->next_;
 204             rv  = insert(-1, db, indInfo, iptr, tuple, iter);
 205         }
 206         else
 207         {
 208             printDebug(DM_TreeIndex, "\n2Insert- d=1 else ");
 209             rv = insert(1, db, indInfo, iptr, tuple, iter);
 210         }
 211     }
 212     else if(direction == -2)
 213     {
 214        if(iter->next_ != NULL && iter->next_->noElements_ < noOfBuckets )
 215        {
 216             printDebug(DM_TreeIndex, "\n2Insert- d=-2 if ");
 217             iter = iter->next_;
 218             rv = insert(-1, db, indInfo, iptr, tuple, iter);
 219        }
 220        else
 221        {
 222            printDebug(DM_TreeIndex, "\n2Insert- d=-2 else ");
 223            rv = insert(1, db, indInfo, iptr, tuple, iter);
 224        }
 225     }
 226     else if(direction == -1)
 227     {
 228         iter = prev;
 229         if((iter->noElements_ >= noOfBuckets) && (iter->prev_ != NULL)
 230             && (iter->prev_->noElements_ < noOfBuckets) )
 231         {
 232             printDebug(DM_TreeIndex, "\n2Insert- d=-1 if ");
 233             iter = iter->prev_;
 234             rv = insert(1, db, indInfo, iptr, tuple, iter);
 235         }
 236        else
 237        {
 238            printDebug(DM_TreeIndex, "\n2Insert- d=-1 else ");
 239            rv = insert(-1, db, indInfo, iptr, tuple, iter);
 240        }
 241     }
 242     else
 243     {
 244         printDebug(DM_TreeIndex, "\n2Insert- d=0 ");
 245         rv = insert(0, db, indInfo, iptr, tuple, iter);
 246     }
 247     printDebug(DM_TreeIndex, "\n %d While  ..Exit TreeNode::Insert - 2",count);
 248     return rv;
 249 }
 250 DbRetVal TreeNode::insert(int position, Database * db, IndexInfo * indInfo,
 251                           CINDEX * iptr, void * tuple, TreeNode * iter)
 252 {
 253     //position---  -1:First,0:Middle,1:Last
 254
 255     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 256     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
 257     int offset = info->fldOffset;
 258     DataType type = info->type;
 259     int noOfBuckets = info->noOfBuckets;
 260     void *record = NULL;
 261     TreeNode *prev = start;
 262     TreeNode *next = start;
 263     char *keyVal = (char*) tuple + info->fldOffset;
 264     DbRetVal rc = OK;
 265     bool recordInserted = false;
 266     iter->mutex_.getLock(db->procSlot);
 267     if(position == -1)
 268     {
 269         if(iter->noElements_ >= noOfBuckets)
 270         {
 271             Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 272             TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 273             if (tnode == NULL)
 274             {
 275                 printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
 276                 iter->mutex_.releaseLock(db->procSlot);
 277                 return rc;
 278             }
 279             tnode->mutex_.init();
 280             tnode->min_ = tuple;
 281             tnode->max_ = tuple;
 282             tnode->noElements_ =1;
 283             tnode->next_ = iter;
 284             tnode->prev_ = iter->prev_;
 285             iter->prev_ = tnode;
 286             tnode->balance_ = 0;
 287             char **rec = (char**)((char*)tnode + sizeof(TreeNode));
 288             *rec = (char*) tuple;
 289         }
 290         else
 291         {
 292             printDebug(DM_TreeIndex, "\n3Insert- p=-1 else ");
 293             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 294             char *tmp = (char *)malloc(sizeof(void **) * iter->noElements_);
 295             memcpy(tmp, (char*)rec, sizeof(void **)* iter->noElements_);
 296             memcpy((char*)rec + sizeof(void **), tmp, sizeof(void **) * (iter->noElements_));
 297             free(tmp);
 298             iter->min_ = tuple;
 299             iter->noElements_++;
 300             *rec = (char*) tuple;
 301         }
 302     }
 303     else if(position == 1)
 304     {
 305         if(iter->noElements_ >= noOfBuckets)
 306         {
 307             printDebug(DM_TreeIndex, "\n3Insert- p=1 if ");
 308             Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 309             TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 310             if (tnode == NULL)
 311             {
 312                 printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
 313                 iter->mutex_.releaseLock(db->procSlot);
 314                 return rc;
 315             }
 316             tnode->mutex_.init();
 317             tnode->min_ = tuple;
 318             tnode->max_ = tuple;
 319             tnode->noElements_ =1;
 320             tnode->next_ = iter->next_;
 321             tnode->prev_ = iter;
 322             iter->next_ = tnode;
 323             if(tnode->next_)
 324             {
 325                 tnode->next_->prev_ = tnode;
 326             }
 327             tnode->balance_ = 0;
 328             char **rec = (char**)((char*)tnode + sizeof(TreeNode));
 329             *rec = (char*) tuple;
 330         }
 331         else
 332         {
 333             printDebug(DM_TreeIndex, "\n3Insert- p=1 else ");
 334             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 335             rec = (char **)((char *)rec + (iter->noElements_ * sizeof(void **)));
 336             iter->max_ = tuple;
 337             iter->noElements_++;
 338             *rec = (char*) tuple;
 339             rec = (char**)((char*)iter + sizeof(TreeNode));
 340             rec = (char**)((char *)rec + ((iter->noElements_-1) * sizeof(void **)));
 341         }
 342     }
 343     else
 344     {
 345         printDebug(DM_TreeIndex, "\n3Insert- p=0 ");
 346
 347         int start = 0;
 348         int end = iter->noElements_ - 1;
 349         int middle;
 350         int loc = 0;
 351         char **rec = (char**)((char*)iter + sizeof(TreeNode));
 352         char *tmp = NULL;
 353         loc=0;
 354         for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 355         {
 356             loc = middle;
 357             record = ((char*)*(rec+middle)) + info->fldOffset;
 358             printDebug(DM_TreeIndex, "\n3Insert- p=0 get record \n");
 359             printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
 360             bool res = AllDataType::compareVal(keyVal, record, OpEquals, info->type, info->compLength);
 361             if(res)
 362             {
 363                 loc = middle;
 364                 if (info->isUnique) {
 365                     iter->mutex_.releaseLock(db->procSlot);
 366                     printError(ErrUnique, "Unique constraint violation\n");
 367                     return ErrUnique;
 368                 }
 369                 break;
 370             }
 371             res = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
 372             if(res )
 373             {
 374                 end = middle - 1;
 375             }
 376             else
 377             {
 378                 start = middle + 1;
 379                 loc = start;
 380             }
 381         }
 382         if(iter->noElements_ >= noOfBuckets)
 383         {
 384             printDebug(DM_TreeIndex, "\n3Insert- p=0 if ");
 385                         Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 386             TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 387             if (tnode == NULL)
 388             {
 389                 printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
 390                 iter->mutex_.releaseLock(db->procSlot);
 391                 return rc;
 392             }
 393             tnode->mutex_.init();
 394             tnode->next_ = iter->next_;
 395             tnode->prev_ = iter;
 396             iter->next_ = tnode;
 397             if(tnode->next_)
 398             {
 399                 tnode->next_->prev_ = tnode;
 400             }
 401             tnode->balance_ = 0;
 402             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 403             char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 404             memcpy(tmp, (char*)rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));/////////  Check the type cast char *
 405             rec = (char**)((char *)rec + (loc * sizeof(void *)));
 406             *rec = (char*)tuple;
 407             tnode->noElements_ = iter->noElements_ - loc;
 408             iter->noElements_ = loc + 1;
 409             rec = (char**)((char*)iter + sizeof(TreeNode));
 410             iter->min_ = *rec;
 411             iter->max_ = tuple;
 412             rec = (char**)((char*)tnode + sizeof(TreeNode));
 413             memcpy((char*)rec, tmp, (tnode->noElements_) * sizeof(void *));
 414             tnode->min_ = *rec;
 415             rec = (char**)((char *)rec + ((tnode->noElements_ - 1) * sizeof(void *)));
 416             tnode->max_ = *rec ;
 417             free(tmp);
 418         }
 419         else
 420         {
 421             printDebug(DM_TreeIndex, "\n3Insert- p=0 else pos-%d",loc);
 422             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 423             char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 424             memcpy(tmp, (char*)rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));/////////  Check the type cast char *
 425             memcpy((char*)rec + ((loc+1) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
 426             free(tmp);
 427             if(loc==0)
 428             {
 429                 iter->min_ = tuple;
 430             }
 431             iter->noElements_++;
 432             rec = (char **)((char*)rec + (loc * sizeof(void *)));
 433             *rec = (char*)tuple;
 434         }
 435     }
 436     iter->mutex_.releaseLock(db->procSlot);
 437     return rc;
 438 }
 439
 440 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 441 {
 442     printf("Tree index remove called\n");
 443     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 444     CINDEX *iptr = (CINDEX*)indexPtr;
 445     TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
 446     TreeNode *iter = locateNode(start, tuple, indInfo);
 447     if (NULL == iter) return OK; //element not found
 448     removeElement(tbl->getDB(), iter, tuple, info);
 449     return OK;
 450 }
 451 TreeNode* TreeIndex::locateNode(TreeNode *iter, void *tuple, IndexInfo *indInfo)
 452 {
 453     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 454     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 455     while(iter != NULL)
 456     {
 457         char *record = ((char*)iter->max_)+ info->fldOffset;
 458         bool result = AllDataType::compareVal(searchKey, record,
 459                                               OpGreaterThan,
 460                                               info->type, info->compLength);
 461         if (result)
 462         {
 463             iter = iter->next_;
 464         }else
 465         {
 466             record = ((char*)iter->min_)+ info->fldOffset;
 467             result = AllDataType::compareVal(searchKey, record,
 468                                              OpGreaterThanEquals,
 469                                              info->type, info->compLength);
 470             if (result) {
 471                //current node contains the key
 472                return iter;
 473             }
 474             else
 475             {
 476                //need to move left
 477                iter = iter->prev_;
 478             }
 479         }
 480     }
 481     return NULL;
 482 }
 483 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
 484 {
 485     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 486     int loc=0, middle=0, start=0, end=iter->noElements_-1;
 487     char **rec = (char**)((char*)iter + sizeof(TreeNode));
 488     iter->mutex_.getLock(db->procSlot);
 489     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 490     {
 491         loc = middle;
 492         char *record = ((char*)*(rec+middle)) + info->fldOffset;
 493         bool res = AllDataType::compareVal(searchKey, record, OpEquals,
 494                                            info->type, info->compLength);
 495         if(res)
 496         {
 497             loc = middle;
 498             break;
 499         }
 500         res = AllDataType::compareVal(searchKey, record, OpLessThan,
 501                                           info->type, info->compLength);
 502         if(res)
 503         {
 504             end = middle - 1;
 505         }
 506         else
 507         {
 508             start = middle + 1;
 509             loc = start;
 510         }
 511     }
 512     char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 513     memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
 514     memcpy((char*)rec + ((loc) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
 515     free(tmp);
 516     if(loc==0)
 517     {
 518        iter->min_ = tuple;
 519     }
 520     iter->mutex_.releaseLock(db->procSlot);
 521     //TODO::if noElement is zero then deallocate the tree node
 522     iter->noElements_--;
 523     return OK;
 524 }
 525
 526
 527 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
 528 {
 529     return ErrNotYet;
 530 }
 531