src/storage/TreeNode.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 long long TreeNode::getTotalElements()
  26 {
  27     DbRetVal rv=OK;
  28     TreeNode *iter = (TreeNode *) this ;
  29     TreeNode *tnode=NULL;
  30     long long totalElement=0;
  31     while(iter != NULL)
  32     {
  33         for(int i=0;i< iter->noElements_;i++)
  34         {
  35              tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
  36              totalElement += tnode->noElements_;
  37         }
  38         iter=iter->next_;
  39     }
  40     return totalElement;
  41 }
  42
  43 void TreeNode::displayAll(int fldOffset)
  44 {
  45     DbRetVal rv=OK;
  46     TreeNode *iter = (TreeNode *) this ;
  47     TreeNode *tnode=NULL;
  48     TreeNode *prev = iter;
  49     bool result = false;
  50     printf("<TreeNode Info>\n");
  51     int i=0;
  52     while(iter != NULL)
  53     {
  54         i++;
  55         tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
  56         char *record = ((char*)tnode->max_)+ fldOffset;
  57         TreeNode *needremovetnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))));
  58         printf("  <First level > node:%d noElements:%d </First level>\n",i, iter->noElements_);
  59         for(int i=0;i< iter->noElements_;i++)
  60         {
  61              tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
  62              printf("    <Second Level Node> Node:%d Elements:%d Min:%d Max:%d </Second Level Node>\n ",i, tnode->noElements_, *(int*)((char*)tnode->min_+fldOffset),  *(int*)((char*)tnode->max_ + fldOffset));
  63              char **rec= (char**)((char*)tnode + sizeof(TreeNode));
  64              for(int j=0; j < tnode->noElements_; j++){
  65                  printf("%d,",*((int*)((char*) *(rec + j )+fldOffset)));
  66              }
  67              printf("\n");
  68
  69         }
  70         iter=iter->next_;
  71     }
  72     printf("</TreeNode Info>\n");
  73 }
  74
  75 void TreeNode::displayAll()
  76 {
  77     DbRetVal rv=OK;
  78     TreeNode *iter = (TreeNode *) this ;
  79     TreeNode *tnode=NULL;
  80     long long totalElement=0;
  81     int count=1;
  82     printf("<TreeNode count>\n");
  83     while(iter != NULL)
  84     {
  85         printf("    <First Level Node> %d <Total Elements> %d </Total Elements> <Mutex> %x %d </Mutex></First Level Node>\n", count, iter->noElements_, &iter->mutex_, iter->mutex_.getLockVal());
  86         for(int i=0;i< iter->noElements_;i++)
  87         {
  88              tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
  89              printf("      <Second Level Node %d> %d <Mutex> %x %d</Mutex> </Second Level Node>\n",i, tnode->noElements_, &tnode->mutex_, tnode->mutex_.getLockVal());
  90              totalElement += tnode->noElements_;
  91         }
  92         iter=iter->next_;
  93         count++;
  94     }
  95     printf("  <Total Records> %lld </Total Records>\n",totalElement);
  96     printf("</TreeNode count>\n");
  97 }
  98
  99 DbRetVal TreeNode::insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos)
 100 {
 101     DbRetVal rv=OK;
 102     TreeNode *start = (TreeNode *) this;
 103     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 104     CINDEX *iptr = (CINDEX*)indexPtr;
 105     int offset = info->fldOffset;
 106     DataType type = info->type;
 107     int noOfBuckets = info->noOfBuckets;
 108     char **node = NULL;
 109     char *tmp = NULL;
 110     char *tmpnode=NULL;
 111     TreeNode *tempNode = start;
 112     if(start->noElements_< noOfBuckets)
 113     {
 114         printDebug(DM_TreeIndex,"insertNodeIntoFirstLevel after node insert manage first level node");
 115         if(start->noElements_<= nodepos)
 116         {
 117             node = (char **)((char*)start + sizeof(TreeNode) + (nodepos * sizeof(void *)));
 118             start->noElements_++;
 119             *node = (char*)newNode;
 120         }else
 121         {
 122             node = (char**)((char*)start + sizeof(TreeNode));
 123             tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
 124             memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
 125             memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
 126             free(tmp);
 127             node = (char **)((char*)node + (nodepos * sizeof(void *)));
 128             *node = (char*)newNode;
 129             start->noElements_++;
 130         }
 131     }
 132     else
 133     {
 134         node = (char**)((char*)start + sizeof(TreeNode));
 135         if(start->noElements_ > nodepos)
 136         {
 137             tmpnode = *(char **)((char*)node+ ((start->noElements_-1) * sizeof(void *)));//store last one
 138             tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
 139             memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos-1));
 140             memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos-1));
 141             free(tmp);
 142             node = (char **)((char*)node + (nodepos * sizeof(void *)));
 143             *node = (char*)newNode;
 144         }else
 145         {
 146             tmpnode =(char*)newNode;
 147         }
 148         nodepos=0;
 149         if( start->next_ != NULL && start->next_->noElements_< noOfBuckets)
 150         {
 151             start = start->next_;
 152
 153             node = (char**)((char*)start + sizeof(TreeNode));
 154             tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
 155             memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
 156             memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
 157             free(tmp);
 158             node = (char **)((char*)node + (nodepos * sizeof(void *)));
 159             *node = (char*)tmpnode;
 160             start->noElements_++;
 161             start->mutex_.releaseShareLock(db->procSlot);
 162         }else
 163         {
 164             printDebug(DM_TreeIndex, "Check if full and start->next_ ==NULL then create new one");
 165             Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
 166             TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
 167             if (ftnode == NULL)
 168             {
 169                  printError(rv, "Exit TreeNode firstlevel allocate fail");
 170                  tempNode->mutex_.releaseShareLock(db->procSlot);
 171                  return rv;
 172             }
 173             ftnode->mutex_.init("TNODE-I");
 174             ftnode->min_= NULL;
 175             ftnode->max_ = NULL;
 176             ftnode->noElements_ =1;
 177             ftnode->balance_ = 0;
 178             char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
 179             *tn = (char*)tmpnode;
 180             ftnode->next_ = start->next_;
 181             ftnode->prev_ = start;
 182             start->next_ = ftnode;
 183         }
 184     }
 185     tempNode->mutex_.releaseShareLock(db->procSlot);
 186     printDebug(DM_TreeIndex," Mutex Release on %x\n",tempNode);
 187     return OK;
 188 }
 189
 190 DbRetVal TreeNode::insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, void * tuple, TreeNode * fstLevel, int nodePos)
 191 {
 192     TreeNode *iter = (TreeNode *) this;
 193     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 194     CINDEX *iptr = (CINDEX*)indexPtr;
 195     int offset = info->fldOffset;
 196     DataType type = info->type;
 197     int noOfBuckets = info->noOfBuckets;
 198     void *record = NULL;
 199     char *keyVal = (char*) tuple + info->fldOffset;
 200     DbRetVal rc = OK;
 201     bool recordInserted = false;
 202     TreeNode *tmpNode=NULL;
 203     int ret = iter->mutex_.getExclusiveLock(db->procSlot);
 204     if (0 != ret) {
 205          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 206          fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 207          return ErrLockTimeOut;
 208     }
 209     if(iter->noElements_>= noOfBuckets)
 210     {
 211         //Ist level full
 212         //Decide new record should go in  left or right of second level
 213         //if it is inside then create new memcpy all address from location to next node
 214         //if left check prev_ node has free space or not if yes insert at end else create new
 215         //if right check next_ node has free space or not if yes insert at Ist loc nad do memcpy else create new
 216         //create node and link to prevous node and link to the Fistlevel
 217         record = ((char*)iter->max_)+ info->fldOffset;
 218         bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
 219         if(result)
 220         {
 221             printDebug(DM_TreeIndex,"locateed Node full new node create at iright");
 222             //check right for free space if not create node right
 223             tmpNode = iter->next_;
 224             if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
 225             {
 226                 //insert at beginning
 227                 ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
 228                 if (0 != ret) {
 229                     printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 230                     iter->mutex_.releaseShareLock(db->procSlot);
 231                     fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 232                     return ErrLockTimeOut;
 233                 }
 234                 char *tmp = NULL;
 235                 char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
 236                 tmp = (char *)malloc(sizeof(void *) * (tmpNode->noElements_));
 237                 memcpy(tmp, (char*)rec , sizeof(void *) * (iter->noElements_));
 238                 memcpy((char*)rec + (1*sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_));
 239                 *rec = (char*)tuple;
 240                 tmpNode->min_=tuple;
 241                 tmpNode->noElements_++;
 242                 free(tmp);
 243                 iter->mutex_.releaseShareLock(db->procSlot);
 244                 tmpNode->mutex_.releaseShareLock(db->procSlot);
 245                 fstLevel->mutex_.releaseShareLock(db->procSlot);
 246                 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
 247             }
 248             else
 249             {
 250                 //allocate new node here
 251                 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 252                 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 253                 if (tnode == NULL)
 254                 {
 255                     printError(rc, "Exit TreeNode create fail after node full");
 256                     iter->mutex_.releaseShareLock(db->procSlot);
 257                     fstLevel->mutex_.releaseShareLock(db->procSlot);
 258                     printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
 259                     return rc;
 260                 }
 261                if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
 262                {
 263                     ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
 264                     if (0 != ret) {
 265                         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 266                         chunk->free(db, tnode);
 267                         iter->mutex_.releaseShareLock(db->procSlot);
 268                         fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 269                         return ErrLockTimeOut;
 270                     }
 271                }
 272                 tnode->mutex_.init();
 273                 strcpy(tnode->mutex_.name, "Tree");
 274                 tnode->min_ = tuple;
 275                 tnode->max_ = tuple;
 276                 tnode->noElements_ =1;
 277                 tnode->next_ = NULL;
 278                 tnode->prev_ = NULL;
 279                 tnode->balance_ = 0;
 280                 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
 281                 *rec = (char*) tuple;
 282                 if(iter->next_!=NULL){
 283                      if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
 284                      {
 285                           printError(ErrLockTimeOut, "Lock timeout..retry Tree");
 286                           chunk->free(db, tnode);
 287                           iter->mutex_.releaseShareLock(db->procSlot);
 288                           fstLevel->mutex_.releaseShareLock(db->procSlot);
 289                           return ErrLockTimeOut;
 290                      }
 291                 }
 292                 tnode->next_= iter->next_;
 293                 tnode->prev_= iter;
 294                 iter->next_= tnode;
 295                 nodePos++;
 296                 iter->mutex_.releaseShareLock(db->procSlot);
 297                 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
 298             }
 299         }else
 300         {
 301             record = ((char*)iter->min_)+ info->fldOffset;
 302             bool result = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
 303             if(result)
 304             {
 305                 printDebug(DM_TreeIndex,"\nlocateed Node full new node create at left");
 306                 //check left for free space if not create node left
 307                 tmpNode = iter->prev_;
 308                 if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
 309                 {
 310                     //insert at End
 311                     ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
 312                     if (0 != ret) {
 313                         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 314                         iter->mutex_.releaseShareLock(db->procSlot);
 315                         fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 316                         return ErrLockTimeOut;
 317                     }
 318                     char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
 319                     rec = (char **)((char *)rec + (tmpNode->noElements_ * sizeof(void *)));
 320                     *rec = (char*)tuple;
 321                     tmpNode->max_ = tuple;
 322                     tmpNode->noElements_++;
 323                     iter->mutex_.releaseShareLock(db->procSlot);
 324                     tmpNode->mutex_.releaseShareLock(db->procSlot);
 325                     fstLevel->mutex_.releaseShareLock(db->procSlot);
 326                     printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
 327                 }else
 328                 {
 329                     //allocate here
 330                     Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 331                     TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 332                     if (tnode == NULL)
 333                     {
 334                          printError(rc, "Exit TreeNode create fail after node full");
 335                          iter->mutex_.releaseShareLock(db->procSlot);
 336                          fstLevel->mutex_.releaseShareLock(db->procSlot);
 337                          printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
 338                          return rc;
 339                     }
 340                     if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
 341                     {
 342                          ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
 343                          if (0 != ret) {
 344                              printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 345                              chunk->free(db, tnode);
 346                              iter->mutex_.releaseShareLock(db->procSlot);
 347                              fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 348                              return ErrLockTimeOut;
 349                          }
 350                     }
 351                     tnode->mutex_.init();
 352                     strcpy(tnode->mutex_.name, "Tree");
 353                     tnode->min_ = tuple;
 354                     tnode->max_ = tuple;
 355                     tnode->noElements_ =1;
 356                     tnode->next_ = NULL;
 357                     tnode->prev_ = NULL;
 358                     tnode->balance_ = 0;
 359                     char **rec = (char**)((char*) tnode + sizeof(TreeNode));
 360                     printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
 361                     *rec = (char*) tuple;
 362                     if(iter->prev_!=NULL) {
 363                         if( 0 !=Mutex::CASL((long*)&iter->prev_->next_, (long)iter->prev_->next_, (long)tnode))
 364                         {
 365                             printError(ErrLockTimeOut, "Lock timeout..retry Tree");
 366                             chunk->free(db, tnode);
 367                             iter->mutex_.releaseShareLock(db->procSlot);
 368                             fstLevel->mutex_.releaseShareLock(db->procSlot);
 369                             return ErrLockTimeOut;
 370                          }
 371                     }
 372                     tnode->prev_= iter->prev_;
 373                     tnode->next_= iter;
 374                     iter->prev_= tnode;
 375                     //manage First level
 376                     iter->mutex_.releaseShareLock(db->procSlot);
 377                     fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
 378                 }
 379             }else
 380             {
 381                //create right
 382                //locate position shift node
 383                 void *tmprec=NULL;
 384                 char **rec = (char**)((char*) iter + sizeof(TreeNode));
 385                 tmprec = iter->max_;
 386                 int start = 0;
 387                 int end = iter->noElements_ - 1;
 388                 int middle;
 389                 int loc = 0;
 390                 char *tmp = NULL;
 391                 loc=0;
 392                 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 393                 {
 394                     loc = middle;
 395                     record = ((char*)*(rec+middle)) + info->fldOffset;
 396                     printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
 397                     bool res = AllDataType::compareVal(keyVal, record,
 398                                       OpLessThan, info->type, info->compLength);
 399                     if(res)
 400                     {
 401                         end = middle - 1;
 402                     }
 403                     else
 404                     {
 405                         res = AllDataType::compareVal(keyVal, record,
 406                                       OpGreaterThan, info->type, info->compLength);
 407                          if (res) {
 408                             start = middle + 1;
 409                             loc = start;
 410                          }else {
 411                             loc = middle;
 412                             if (info->isUnique) {
 413                                iter->mutex_.releaseShareLock(db->procSlot);
 414                                fstLevel->mutex_.releaseShareLock(db->procSlot);
 415                                printError(ErrUnique, "Unique constraint violation");
 416                                return ErrUnique;
 417                             }
 418                             break;
 419                          }
 420                     }
 421                 }
 422
 423                 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 424                 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
 425                 if (tnode == NULL)
 426                 {
 427                     printError(rc, "Exit TreeNode create fail after node full");
 428                     iter->mutex_.releaseShareLock(db->procSlot);
 429                     fstLevel->mutex_.releaseShareLock(db->procSlot);
 430                     printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
 431                     return rc;
 432                 }
 433                 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
 434                 {
 435                      ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
 436                      if (0 != ret) {
 437                          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 438                          chunk->free(db, tnode);
 439                          iter->mutex_.releaseShareLock(db->procSlot);
 440                          fstLevel->mutex_.releaseShareLock(db->procSlot);  //release here 1st level
 441                          return ErrLockTimeOut;
 442                      }
 443                 }
 444                 tnode->mutex_.init();
 445                 strcpy(tnode->mutex_.name, "Tree");
 446                 tnode->min_ = tuple;
 447                 tnode->max_ = tuple;
 448                 tnode->noElements_ =1;
 449                 tnode->next_ = NULL;
 450                 tnode->prev_ = NULL;
 451                 tnode->balance_ = 0;
 452
 453                 //shift all element from the location to next node
 454                 char **fstRec = (char**)((char*)iter + sizeof(TreeNode));
 455                 tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 456                 memcpy(tmp, (char*)fstRec+ (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
 457                 rec = (char **)((char*)fstRec + (loc * sizeof(void *)));
 458                 *rec = (char*)tuple;
 459                 //copy to next node
 460                 fstRec = (char**)((char*) tnode + sizeof(TreeNode));
 461                 memcpy((char*)fstRec, tmp, sizeof(void *) * (iter->noElements_- loc));
 462                 free(tmp);
 463                 tnode->noElements_= iter->noElements_- loc;
 464                 tnode->max_= tmprec;
 465                 tnode->min_= *fstRec;
 466                 iter->noElements_= loc + 1;
 467                 iter->max_= tuple;
 468                 if(loc==0)
 469                 {
 470                     iter->min_ = tuple;
 471                 }
 472                 if(iter->next_!=NULL){
 473                      if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
 474                      {
 475                           printError(ErrLockTimeOut, "Lock timeout..retry Tree");
 476                           chunk->free(db, tnode);
 477                           iter->mutex_.releaseShareLock(db->procSlot);
 478                           fstLevel->mutex_.releaseShareLock(db->procSlot);
 479                           return ErrLockTimeOut;
 480                      }
 481                 }
 482                 tnode->next_= iter->next_;
 483                 tnode->prev_=iter;
 484                 iter->next_=tnode; //TODO::need here CASL
 485                 nodePos++;
 486                 //shift right done after this block
 487                 printDebug(DM_TreeIndex,"located Node full new node create at right position %d shift node",loc);
 488                 //manage First level
 489                 iter->mutex_.releaseShareLock(db->procSlot);
 490                 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
 491             }
 492          }
 493          return OK;
 494     }
 495     if(iter->noElements_< noOfBuckets)
 496     {
 497         fstLevel->mutex_.releaseShareLock(db->procSlot);
 498         printDebug(DM_TreeIndex,"located Node not full insert in same node");
 499
 500         record = ((char*)iter->max_)+ info->fldOffset;
 501         printDebug(DM_TreeIndex, "\n%d---%d", *((int*)keyVal), *((int*)record));
 502         bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
 503         if(result)
 504         {
 505             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 506             rec = (char **)((char *)rec + (iter->noElements_ * sizeof(void **)));
 507             iter->max_ = tuple;
 508             iter->noElements_++;
 509             *rec = (char*) tuple;
 510         }
 511         else
 512         {
 513             int start = 0;
 514             int end = iter->noElements_ - 1;
 515             int middle;
 516             int loc = 0;
 517             char **rec = (char**)((char*)iter + sizeof(TreeNode));
 518             char *tmp = NULL;
 519             loc=0;
 520             for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 521             {
 522                 loc = middle;
 523                 record = ((char*)*(rec+middle)) + info->fldOffset;
 524                 printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
 525                 bool res = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
 526                 if(res)
 527                 {
 528                     end = middle - 1;
 529                 }
 530                 else
 531                 {
 532                     res = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
 533                     if (res) {
 534                        start = middle + 1;
 535                        loc = start;
 536                     }else {
 537                        loc = middle;
 538                        if (info->isUnique)
 539                        {
 540                           iter->mutex_.releaseShareLock(db->procSlot);
 541                           //fstLevel->mutex_.releaseShareLock(db->procSlot);
 542                           printError(ErrUnique, "Unique constraint violation");
 543                           return ErrUnique;
 544                        }
 545                        break;
 546                     }
 547                 }
 548             }
 549             printDebug(DM_TreeIndex, "\nInsert pos-%d",loc);
 550             rec = (char**)((char*)iter + sizeof(TreeNode));
 551             tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
 552             memcpy(tmp, (char*)rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));/////////  Check the type cast char *
 553             memcpy((char*)rec + ((loc+1) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
 554             free(tmp);
 555             if(loc==0)
 556             {
 557                  iter->min_ = tuple;
 558             }
 559             iter->noElements_++;
 560             rec = (char **)((char*)rec + (loc * sizeof(void *)));
 561             *rec = (char*)tuple;
 562         }
 563        //first level mutex release
 564        iter->mutex_.releaseShareLock(db->procSlot);
 565     }
 566     return OK;
 567 }
 568
 569 DbRetVal TreeNode::insert(Database *db,IndexInfo *indInfo,void *indexPtr,void *tuple)
 570 {
 571     DbRetVal rv=OK;
 572     TreeNode *iter = (TreeNode *) this ;
 573     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 574     CINDEX *iptr = (CINDEX*)indexPtr;
 575     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 576     TreeNode *tnode=NULL;
 577     TreeNode *prev = iter;
 578     bool result = false;
 579     DbRetVal  ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
 580     if (OK != ret) {
 581          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 582          return ErrLockTimeOut;
 583     }
 584     printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter);
 585
 586     while(iter != NULL )
 587     {
 588         //get the second level last node as min and max are not stored in first level tree node
 589         tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
 590         char *record = ((char*)tnode->max_)+ info->fldOffset;
 591         result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
 592          if (result)
 593          {
 594              break;
 595          }else
 596          {
 597              if(tnode->noElements_ >= info->noOfBuckets)
 598              {
 599                  if(iter->next_!=NULL)
 600                  {
 601                      DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
 602                      if (OK != ret)
 603                      {
 604                          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 605                          iter->mutex_.releaseShareLock(db->procSlot);
 606                          printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",iter);
 607                          return ErrLockTimeOut;
 608                      }
 609                      printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter->next_);
 610                      prev = iter;
 611                      iter = iter->next_;
 612                      prev->mutex_.releaseShareLock(db->procSlot);
 613                      printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",prev);
 614                  }else{
 615                      prev = iter;
 616                      iter = iter->next_;
 617                  }
 618              }else
 619              {
 620                  if(iter->next_!=NULL)
 621                  {
 622                      tnode = (TreeNode *)*((char**)((char*)((char*)iter->next_ + sizeof(TreeNode))));
 623                      char *record = ((char*)tnode->min_)+ info->fldOffset;
 624                      result = AllDataType::compareVal(searchKey, record,OpLessThan,info->type, info->compLength);
 625                      if (result)
 626                      {
 627                          break;
 628                      } else
 629                      {
 630                          //if(iter->next_!=NULL)
 631                          {
 632                              DbRetVal  ret = TreeIndex::getTreeNodeMutex(iter->next_,
 633                                                                           db->procSlot, true);
 634                              if (OK != ret)
 635                              {
 636                                  printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 637                                  iter->mutex_.releaseShareLock(db->procSlot);
 638                                  printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
 639                                  return ErrLockTimeOut;
 640                              }
 641                              printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
 642                              prev = iter;
 643                              iter = iter->next_;
 644                              prev->mutex_.releaseShareLock(db->procSlot);
 645                              printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
 646                          }
 647                          /*else
 648                          {
 649                              prev = iter;
 650                              iter = iter->next_;
 651                          }*/
 652                      }
 653                  }else{
 654                       break;
 655                  }
 656              }
 657          }
 658     }
 659     //iter will be null if the value being inserted is greater
 660     //than the last I-level node's II-level last node's max
 661     if( iter == NULL && prev->noElements_< info->noOfBuckets)
 662     {
 663         iter = prev ;
 664     }
 665     if(iter == NULL)
 666     {
 667         //TODO::Put this is another function and use the same from 1st record insert
 668         //create Ist level node  then leaf node ,insert record and return
 669         printDebug(DM_TreeIndex, "iter =NULL create Ist level node  then leaf node ,insert record and return");
 670         Chunk *chunk = (Chunk*) iptr->chunkPtr_;
 671         TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rv);
 672         if (tnode == NULL)
 673         {
 674            printError(rv, "Exit TreeNode allocate fail");
 675            return rv;
 676         }
 677         tnode->mutex_.init();
 678         strcpy(tnode->mutex_.name, "Tree");
 679         tnode->min_ = tuple;
 680         tnode->max_ = tuple;
 681         tnode->noElements_ =1;
 682         tnode->next_ = NULL;
 683         tnode->prev_ = NULL;
 684         tnode->balance_ = 0;
 685         char **rec = (char**)((char*) tnode + sizeof(TreeNode));
 686         printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
 687         *rec = (char*) tuple;
 688         TreeNode *prevNode = (TreeNode*)*(char**)((char*) prev +sizeof(TreeNode)+((prev->noElements_-1)* sizeof(void*)));
 689         prevNode->next_= tnode;
 690         tnode->prev_= prevNode;
 691      //fist levelnode
 692         Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
 693         TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
 694         if (ftnode == NULL)
 695         {
 696             printDebug(DM_TreeIndex, "Exit TreeNode firstlevel allocate fail");
 697             return rv;
 698         }
 699         ftnode->mutex_.init("TNODE-I");
 700         ftnode->min_= NULL;
 701         ftnode->max_ = NULL;
 702         ftnode->noElements_ =1;
 703         ftnode->next_ = NULL;
 704         ftnode->balance_ = 0;
 705         char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
 706         *tn = (char*)tnode;
 707         ftnode->prev_= prev;
 708         prev->next_=ftnode;
 709         prev->mutex_.releaseShareLock(db->procSlot);
 710         printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
 711         return OK;
 712     }
 713     //Get second level node and node position from the
 714     //first level node identified above as 'iter'
 715     int nodepos=0;
 716     tnode = locateNodeFromFirstLevel(iter, indInfo, tuple, &nodepos);
 717     //first level mutex is taken and it is released in the below function
 718     //This is because in case arrangement in first level node when it is full
 719     //then subsequent first level node mutex is taken and current first level node
 720     //mutex is released
 721     rv = tnode->insertRecordIntoNodeAndArrangeFirstLevel(db, indInfo, indexPtr, tuple, iter, nodepos);
 722     return rv;
 723 }
 724
 725 TreeNode* TreeNode::locateNode(Database *db, TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv)
 726 {
 727     if(iter == NULL) return NULL;
 728     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 729     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 730     TreeNode *tnode=NULL;
 731     DbRetVal  ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
 732     if (OK != ret) {
 733          printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 734          rv = ErrLockTimeOut;
 735          return NULL;
 736     }
 737     printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
 738     TreeNode *tmpNode=NULL;
 739     while(iter->noElements_>= info->noOfBuckets && iter != NULL)
 740     {
 741         tnode = (TreeNode *)*((char**)((char*)iter + sizeof(TreeNode)+ ((iter->noElements_-1)*sizeof(void *))));
 742         char *record = ((char*)tnode->max_)+ info->fldOffset;
 743         bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
 744         if (result)
 745         {
 746             break;
 747         }else
 748         {
 749             if(iter->next_!=NULL)
 750             {
 751                 DbRetVal  ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
 752                 if (OK != ret)
 753                 {
 754                     printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 755                     iter->mutex_.releaseShareLock(db->procSlot);
 756                     printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
 757                     rv = ErrLockTimeOut;
 758                     return NULL;
 759                 }
 760                 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
 761                 tmpNode = iter;
 762                 iter = iter->next_;
 763                 tmpNode->mutex_.releaseShareLock(db->procSlot);
 764                 printDebug(DM_TreeIndex," Mutex Release on %x\n",tmpNode);
 765             }else{
 766                 iter->mutex_.releaseShareLock(db->procSlot);
 767                 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
 768                 iter = iter->next_;
 769             }
 770         }
 771     }
 772     //Get leaf Node
 773     return iter;
 774
 775 }
 776
 777 TreeNode *TreeNode::locateNodeFromFirstLevel(TreeNode *ftnode, IndexInfo *indInfo,void *tuple, int *pos)
 778 {
 779     HashIndexInfo *info = (HashIndexInfo*) indInfo;
 780     int fldOffset = info->fldOffset;
 781     DataType type = info->type;
 782     int length = info->compLength;
 783     void *searchKey =(void*)((char*)tuple + info->fldOffset);
 784     int loc=0, middle = 0, start = 0, end = ftnode->noElements_-1;
 785     char **node = (char**)((char*)ftnode + sizeof(TreeNode));
 786    TreeNode *tNode;
 787    for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 788     {
 789         loc = middle;
 790         char *record =(char *)(((TreeNode *) *(char**)((char*)node + (loc * sizeof(void *))))->max_)+fldOffset;
 791
 792         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,type, length);
 793         if(res)
 794         {
 795             end = middle - 1;
 796         }
 797         else
 798         {
 799             res = AllDataType::compareVal(searchKey, record, OpGreaterThan, type, length);
 800             if (res) {
 801                 start = middle + 1;
 802                 if(start <= (ftnode->noElements_-1)) loc = start;
 803             }else {
 804                 loc=middle;
 805                 break;
 806             }
 807         }
 808     }
 809     printDebug(DM_TreeIndex, "inside locateNodeFromFirstLevel loc=%d",loc);
 810     *pos=loc;
 811     tNode = ((TreeNode *)*(char**)((char*)node + (loc * sizeof(void *))));
 812     return  tNode;
 813 }