fix for trie index
[csql.git] / src / storage / TreeIndex.cxx
blob07bfd67c4f5f6f278258477dfec68f4960f6d196
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 DbRetVal TreeIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
26 DbRetVal rv = OK;
27 TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
28 Database *db = new Database();
29 db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
30 db->setProcSlot(sysdb->procSlot);
31 CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;
32 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
33 //HashIndexInfo populated here
34 HashIndexInfo *info = new HashIndexInfo();
35 info->indexPtr = (char *)iptr;
36 info->noOfBuckets = iptr->noOfBuckets_;
37 info->isUnique = iptr->isUnique_;
38 info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
39 info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
40 info->indType = iptr->indexType_;
41 TreeIndex *treeInd = (TreeIndex*)Index::getIndex(iptr->indexType_);
42 int pos=0;
43 TreeNode *fltnode = start->locateNode(db, start, tUndoInfo->tuple_, info,rv);
44 if (NULL == fltnode){
45 delete db;
46 delete info;
47 return rv;
48 } //First Level Node Not found
49 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, info, tUndoInfo->tuple_, &pos);
50 if (NULL == iter){
51 fltnode->mutex_.releaseShareLock(db->procSlot);
52 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
53 delete db;
54 delete info;
55 return OK;
56 } //element not found
57 rv = treeInd->removeElement(db, iter, tUndoInfo->tuple_, info);
58 if( rv != OK ){
59 fltnode->mutex_.releaseShareLock(db->procSlot);
60 printError(rv, "Romove from TreeNode Failed ");
61 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
62 delete db;
63 delete info;
64 return rv;
66 if(0 == iter->noElements_)
68 treeInd->removeNode(db, tUndoInfo->cIndex_, fltnode,iter, pos);
69 }else { fltnode->mutex_.releaseShareLock(db->procSlot);
70 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
72 delete db;
73 delete info;
74 return rv;
76 DbRetVal TreeIndex::insertLogicalUndoLog(Database *sysdb, void *data)
78 DbRetVal rc = OK;
79 TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
80 Database *db = new Database();
81 db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
82 db->setProcSlot(sysdb->procSlot);
83 CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;//CINDEX
84 //HashIndexInfo populated here
85 HashIndexInfo *info = new HashIndexInfo();
86 info->indexPtr = (char *)iptr;
87 info->noOfBuckets = iptr->noOfBuckets_;
88 info->isUnique = iptr->isUnique_;
89 info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
90 info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
91 info->indType = iptr->indexType_;
92 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
93 int offset = info->fldOffset;
94 DataType type = info->type;
95 void *keyPtr =(void*)((char*)tUndoInfo->tuple_ + offset);
96 if (start == NULL)
98 //Currently Nodes are not deleted
99 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
100 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
101 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
102 if (tnode == NULL)
104 printError(rc, "Exit TreeNode::Insert - 1 tnode=NULL");
105 delete info;
106 return rc;
108 tnode->mutex_.init();
109 strcpy(tnode->mutex_.name, "Tree");
110 tnode->min_ = tUndoInfo->tuple_;
111 tnode->max_ = tUndoInfo->tuple_;
112 tnode->noElements_ =1;
113 tnode->next_ = NULL;
114 tnode->prev_ = NULL;
115 tnode->balance_ = 0;
116 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
117 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
118 *rec = (char*) tUndoInfo->tuple_;
120 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
121 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
122 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rc);
123 if (NULL == ftnode)
125 printError(rc, "Unable to allocate tree node");
126 chunk->free(db, tnode);
127 delete info;
128 return rc;
130 ftnode->mutex_.init();
131 strcpy(ftnode->mutex_.name, "I-Tree");
132 ftnode->min_= NULL;
133 ftnode->max_ = NULL;
134 ftnode->noElements_ =1;
135 ftnode->next_ = NULL;
136 ftnode->prev_ = NULL;
137 ftnode->balance_ = 0;
138 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
139 *tn = (char*)tnode;
140 //iptr->hashNodeChunk_ = ftnode;
141 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
143 printError(ErrLockTimeOut, "Lock timeout..retry");
144 chunk->free(db, tnode);
145 chunk->free(db, ftnode);
146 delete info;
147 return ErrLockTimeOut;
149 }else {
150 rc = start->insert(db, info, iptr, tUndoInfo->tuple_);
151 if (rc != OK){
152 delete db; delete info;
153 printError(rc, "Error in tree node insertion\n");
154 return rc;
157 delete db;
158 delete info;
159 return rc;
162 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
164 HashIndexInfo *info = (HashIndexInfo*) indInfo;
165 CINDEX *iptr = (CINDEX*)indexPtr;
166 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
167 DbRetVal rc = OK;
168 int offset = info->fldOffset;
169 DataType type = info->type;
170 void *keyPtr =(void*)((char*)tuple + offset);
171 //TreeUndoLogInfo Populated here
172 TreeUndoLogInfo hInfo;
173 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
174 hInfo.tuple_ = tuple;
175 hInfo.cIndex_= indexPtr;
176 if (start == NULL)
178 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
179 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
180 TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
181 if (tnode == NULL)
183 printError(rc, "Unable to allocate tree node");
184 return rc;
186 tnode->mutex_.init();
187 strcpy(tnode->mutex_.name, "Tree");
188 tnode->min_ = tuple;
189 tnode->max_ = tuple;
190 tnode->noElements_ =1;
191 tnode->next_ = NULL;
192 tnode->prev_ = NULL;
193 tnode->balance_ = 0;
194 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
195 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
196 *rec = (char*) tuple;
198 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
199 TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
200 if (NULL == ftnode)
202 printError(rc, "Unable to allocate tree node");
203 chunk->free(tbl->db_, tnode);
204 return rc;
206 ftnode->mutex_.init();
207 strcpy(ftnode->mutex_.name, "I-Tree");
208 ftnode->min_= NULL;
209 ftnode->max_ = NULL;
210 ftnode->noElements_ =1;
211 ftnode->next_ = NULL;
212 ftnode->prev_ = NULL;
213 ftnode->balance_ = 0;
214 //TODO: Handle when two process try to allocate first node
215 char **tn=(char**)((char*) ftnode + sizeof(TreeNode));
216 *tn = (char*)tnode;
217 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
219 printError(ErrLockTimeOut, "Lock timeout..retry");
220 chunk->free(tbl->db_, tnode);
221 chunk->free(tbl->db_, ftnode);
222 return ErrLockTimeOut;
225 }else {
226 rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
227 if (rc != OK){
228 printError(rc, "Error in tree node insertion for tuple %x", tuple);
229 return rc;
232 //start->displayAll(offset);
233 if(!undoFlag){
234 rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
235 if (rc !=OK)
237 //Reverse back
238 int pos=0;
239 start = (TreeNode*) iptr->hashNodeChunk_;
240 TreeNode *fltnode = start->locateNode(tbl->sysDB_,start, tuple, indInfo,rc);
241 if (NULL == fltnode)
243 return rc;
244 } //First Level Node Not found
245 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
246 if (NULL == iter){
247 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
248 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
249 return OK;
250 } //element not found
251 rc = removeElement(tbl->getDB(), iter, tuple, info);
252 if( rc != OK )
254 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
255 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
256 printError(rc, "Romove from TreeNode Failed ");
257 return rc;
259 if(0 == iter->noElements_)
261 removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
262 }else
264 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
265 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
268 printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
269 return rc;
273 return rc;
276 long long TreeNode::getTotalElements()
278 DbRetVal rv=OK;
279 TreeNode *iter = (TreeNode *) this ;
280 TreeNode *tnode=NULL;
281 long long totalElement=0;
282 while(iter != NULL)
284 for(int i=0;i< iter->noElements_;i++)
286 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
287 totalElement += tnode->noElements_;
289 iter=iter->next_;
291 return totalElement;
293 void TreeNode::displayAll(int fldOffset)
295 DbRetVal rv=OK;
296 TreeNode *iter = (TreeNode *) this ;
297 TreeNode *tnode=NULL;
298 TreeNode *prev = iter;
299 bool result = false;
300 printf("<TreeNode Info>\n");
301 int i=0;
302 while(iter != NULL)
304 i++;
305 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
306 char *record = ((char*)tnode->max_)+ fldOffset;
307 TreeNode *needremovetnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))));
308 printf(" <First level > node:%d noElements:%d </First level>\n",i, iter->noElements_);
309 for(int i=0;i< iter->noElements_;i++)
311 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
312 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));
313 char **rec= (char**)((char*)tnode + sizeof(TreeNode));
314 for(int j=0; j < tnode->noElements_; j++){
315 printf("%d,",*((int*)((char*) *(rec + j )+fldOffset)));
317 printf("\n");
320 iter=iter->next_;
322 printf("</TreeNode Info>\n");
324 void TreeNode::displayAll()
326 DbRetVal rv=OK;
327 TreeNode *iter = (TreeNode *) this ;
328 TreeNode *tnode=NULL;
329 long long totalElement=0;
330 int count=1;
331 printf("<TreeNode count>\n");
332 while(iter != NULL)
334 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());
335 for(int i=0;i< iter->noElements_;i++)
337 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
338 printf(" <Second Level Node %d> %d <Mutex> %x %d</Mutex> </Second Level Node>\n",i, tnode->noElements_, &tnode->mutex_, tnode->mutex_.getLockVal());
339 totalElement += tnode->noElements_;
341 iter=iter->next_;
342 count++;
344 printf(" <Total Records> %lld </Total Records>\n",totalElement);
345 printf("</TreeNode count>\n");
348 DbRetVal TreeNode::insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos)
350 DbRetVal rv=OK;
351 TreeNode *start = (TreeNode *) this;
352 HashIndexInfo *info = (HashIndexInfo*) indInfo;
353 CINDEX *iptr = (CINDEX*)indexPtr;
354 int offset = info->fldOffset;
355 DataType type = info->type;
356 int noOfBuckets = info->noOfBuckets;
357 char **node = NULL;
358 char *tmp = NULL;
359 char *tmpnode=NULL;
360 TreeNode *tempNode = start;
361 if(start->noElements_< noOfBuckets)
363 printDebug(DM_TreeIndex,"insertNodeIntoFirstLevel after node insert manage first level node");
364 if(start->noElements_<= nodepos)
366 node = (char **)((char*)start + sizeof(TreeNode) + (nodepos * sizeof(void *)));
367 start->noElements_++;
368 *node = (char*)newNode;
369 }else
371 node = (char**)((char*)start + sizeof(TreeNode));
372 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
373 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
374 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
375 free(tmp);
376 node = (char **)((char*)node + (nodepos * sizeof(void *)));
377 *node = (char*)newNode;
378 start->noElements_++;
381 else
383 node = (char**)((char*)start + sizeof(TreeNode));
384 if(start->noElements_ > nodepos)
386 tmpnode = *(char **)((char*)node+ ((start->noElements_-1) * sizeof(void *)));//store last one
387 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
388 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos-1));
389 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos-1));
390 free(tmp);
391 node = (char **)((char*)node + (nodepos * sizeof(void *)));
392 *node = (char*)newNode;
393 }else
395 tmpnode =(char*)newNode;
397 nodepos=0;
398 if( start->next_ != NULL && start->next_->noElements_< noOfBuckets)
400 start = start->next_;
402 node = (char**)((char*)start + sizeof(TreeNode));
403 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
404 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
405 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
406 free(tmp);
407 node = (char **)((char*)node + (nodepos * sizeof(void *)));
408 *node = (char*)tmpnode;
409 start->noElements_++;
410 start->mutex_.releaseShareLock(db->procSlot);
411 }else
413 printDebug(DM_TreeIndex, "Check if full and start->next_ ==NULL then create new one");
414 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
415 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
416 if (ftnode == NULL)
418 printError(rv, "Exit TreeNode firstlevel allocate fail");
419 tempNode->mutex_.releaseShareLock(db->procSlot);
420 return rv;
422 ftnode->mutex_.init();
423 strcpy(ftnode->mutex_.name, "I-Tree");
424 ftnode->min_= NULL;
425 ftnode->max_ = NULL;
426 ftnode->noElements_ =1;
427 ftnode->balance_ = 0;
428 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
429 *tn = (char*)tmpnode;
430 ftnode->next_ = start->next_;
431 ftnode->prev_ = start;
432 start->next_ = ftnode;
435 tempNode->mutex_.releaseShareLock(db->procSlot);
436 printDebug(DM_TreeIndex," Mutex Release on %x\n",tempNode);
437 return OK;
440 DbRetVal TreeNode::insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, void * tuple, TreeNode * fstLevel, int nodePos)
442 TreeNode *iter = (TreeNode *) this;
443 HashIndexInfo *info = (HashIndexInfo*) indInfo;
444 CINDEX *iptr = (CINDEX*)indexPtr;
445 int offset = info->fldOffset;
446 DataType type = info->type;
447 int noOfBuckets = info->noOfBuckets;
448 void *record = NULL;
449 char *keyVal = (char*) tuple + info->fldOffset;
450 DbRetVal rc = OK;
451 bool recordInserted = false;
452 TreeNode *tmpNode=NULL;
453 int ret = iter->mutex_.getExclusiveLock(db->procSlot);
454 if (0 != ret) {
455 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
456 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
457 return ErrLockTimeOut;
459 if(iter->noElements_>= noOfBuckets)
461 //Ist level full
462 //Decide new record should go in left or right of second level
463 //if it is inside then create new memcpy all address from location to next node
464 //if left check prev_ node has free space or not if yes insert at end else create new
465 //if right check next_ node has free space or not if yes insert at Ist loc nad do memcpy else create new
466 //create node and link to prevous node and link to the Fistlevel
467 record = ((char*)iter->max_)+ info->fldOffset;
468 bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
469 if(result)
471 printDebug(DM_TreeIndex,"locateed Node full new node create at iright");
472 //check right for free space if not create node right
473 tmpNode = iter->next_;
474 if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
476 //insert at beginning
477 ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
478 if (0 != ret) {
479 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
480 iter->mutex_.releaseShareLock(db->procSlot);
481 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
482 return ErrLockTimeOut;
484 char *tmp = NULL;
485 char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
486 tmp = (char *)malloc(sizeof(void *) * (tmpNode->noElements_));
487 memcpy(tmp, (char*)rec , sizeof(void *) * (iter->noElements_));
488 memcpy((char*)rec + (1*sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_));
489 *rec = (char*)tuple;
490 tmpNode->min_=tuple;
491 tmpNode->noElements_++;
492 free(tmp);
493 iter->mutex_.releaseShareLock(db->procSlot);
494 tmpNode->mutex_.releaseShareLock(db->procSlot);
495 fstLevel->mutex_.releaseShareLock(db->procSlot);
496 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
498 else
500 //allocate new node here
501 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
502 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
503 if (tnode == NULL)
505 printError(rc, "Exit TreeNode create fail after node full");
506 iter->mutex_.releaseShareLock(db->procSlot);
507 fstLevel->mutex_.releaseShareLock(db->procSlot);
508 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
509 return rc;
511 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
513 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
514 if (0 != ret) {
515 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
516 chunk->free(db, tnode);
517 iter->mutex_.releaseShareLock(db->procSlot);
518 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
519 return ErrLockTimeOut;
522 tnode->mutex_.init();
523 strcpy(tnode->mutex_.name, "Tree");
524 tnode->min_ = tuple;
525 tnode->max_ = tuple;
526 tnode->noElements_ =1;
527 tnode->next_ = NULL;
528 tnode->prev_ = NULL;
529 tnode->balance_ = 0;
530 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
531 *rec = (char*) tuple;
532 if(iter->next_!=NULL){
533 if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
535 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
536 chunk->free(db, tnode);
537 iter->mutex_.releaseShareLock(db->procSlot);
538 fstLevel->mutex_.releaseShareLock(db->procSlot);
539 return ErrLockTimeOut;
542 tnode->next_= iter->next_;
543 tnode->prev_= iter;
544 iter->next_= tnode;
545 nodePos++;
546 iter->mutex_.releaseShareLock(db->procSlot);
547 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
549 }else
551 record = ((char*)iter->min_)+ info->fldOffset;
552 bool result = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
553 if(result)
555 printDebug(DM_TreeIndex,"\nlocateed Node full new node create at left");
556 //check left for free space if not create node left
557 tmpNode = iter->prev_;
558 if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
560 //insert at End
561 ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
562 if (0 != ret) {
563 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
564 iter->mutex_.releaseShareLock(db->procSlot);
565 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
566 return ErrLockTimeOut;
568 char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
569 rec = (char **)((char *)rec + (tmpNode->noElements_ * sizeof(void *)));
570 *rec = (char*)tuple;
571 tmpNode->max_ = tuple;
572 tmpNode->noElements_++;
573 iter->mutex_.releaseShareLock(db->procSlot);
574 tmpNode->mutex_.releaseShareLock(db->procSlot);
575 fstLevel->mutex_.releaseShareLock(db->procSlot);
576 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
577 }else
579 //allocate here
580 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
581 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
582 if (tnode == NULL)
584 printError(rc, "Exit TreeNode create fail after node full");
585 iter->mutex_.releaseShareLock(db->procSlot);
586 fstLevel->mutex_.releaseShareLock(db->procSlot);
587 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
588 return rc;
590 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
592 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
593 if (0 != ret) {
594 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
595 chunk->free(db, tnode);
596 iter->mutex_.releaseShareLock(db->procSlot);
597 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
598 return ErrLockTimeOut;
601 tnode->mutex_.init();
602 strcpy(tnode->mutex_.name, "Tree");
603 tnode->min_ = tuple;
604 tnode->max_ = tuple;
605 tnode->noElements_ =1;
606 tnode->next_ = NULL;
607 tnode->prev_ = NULL;
608 tnode->balance_ = 0;
609 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
610 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
611 *rec = (char*) tuple;
612 if(iter->prev_!=NULL) {
613 if( 0 !=Mutex::CASL((long*)&iter->prev_->next_, (long)iter->prev_->next_, (long)tnode))
615 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
616 chunk->free(db, tnode);
617 iter->mutex_.releaseShareLock(db->procSlot);
618 fstLevel->mutex_.releaseShareLock(db->procSlot);
619 return ErrLockTimeOut;
622 tnode->prev_= iter->prev_;
623 tnode->next_= iter;
624 iter->prev_= tnode;
625 //manage First level
626 iter->mutex_.releaseShareLock(db->procSlot);
627 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
629 }else
631 //create right
632 //locate position shift node
633 void *tmprec=NULL;
634 char **rec = (char**)((char*) iter + sizeof(TreeNode));
635 tmprec = iter->max_;
636 int start = 0;
637 int end = iter->noElements_ - 1;
638 int middle;
639 int loc = 0;
640 char *tmp = NULL;
641 loc=0;
642 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
644 loc = middle;
645 record = ((char*)*(rec+middle)) + info->fldOffset;
646 printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
647 bool res = AllDataType::compareVal(keyVal, record,
648 OpLessThan, info->type, info->compLength);
649 if(res)
651 end = middle - 1;
653 else
655 res = AllDataType::compareVal(keyVal, record,
656 OpGreaterThan, info->type, info->compLength);
657 if (res) {
658 start = middle + 1;
659 loc = start;
660 }else {
661 loc = middle;
662 if (info->isUnique) {
663 iter->mutex_.releaseShareLock(db->procSlot);
664 fstLevel->mutex_.releaseShareLock(db->procSlot);
665 printError(ErrUnique, "Unique constraint violation");
666 return ErrUnique;
668 break;
673 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
674 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
675 if (tnode == NULL)
677 printError(rc, "Exit TreeNode create fail after node full");
678 iter->mutex_.releaseShareLock(db->procSlot);
679 fstLevel->mutex_.releaseShareLock(db->procSlot);
680 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
681 return rc;
683 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
685 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
686 if (0 != ret) {
687 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
688 chunk->free(db, tnode);
689 iter->mutex_.releaseShareLock(db->procSlot);
690 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
691 return ErrLockTimeOut;
694 tnode->mutex_.init();
695 strcpy(tnode->mutex_.name, "Tree");
696 tnode->min_ = tuple;
697 tnode->max_ = tuple;
698 tnode->noElements_ =1;
699 tnode->next_ = NULL;
700 tnode->prev_ = NULL;
701 tnode->balance_ = 0;
703 //shift all element from the location to next node
704 char **fstRec = (char**)((char*)iter + sizeof(TreeNode));
705 tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
706 memcpy(tmp, (char*)fstRec+ (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
707 rec = (char **)((char*)fstRec + (loc * sizeof(void *)));
708 *rec = (char*)tuple;
709 //copy to next node
710 fstRec = (char**)((char*) tnode + sizeof(TreeNode));
711 memcpy((char*)fstRec, tmp, sizeof(void *) * (iter->noElements_- loc));
712 free(tmp);
713 tnode->noElements_= iter->noElements_- loc;
714 tnode->max_= tmprec;
715 tnode->min_= *fstRec;
716 iter->noElements_= loc + 1;
717 iter->max_= tuple;
718 if(loc==0)
720 iter->min_ = tuple;
722 if(iter->next_!=NULL){
723 if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
725 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
726 chunk->free(db, tnode);
727 iter->mutex_.releaseShareLock(db->procSlot);
728 fstLevel->mutex_.releaseShareLock(db->procSlot);
729 return ErrLockTimeOut;
732 tnode->next_= iter->next_;
733 tnode->prev_=iter;
734 iter->next_=tnode; //TODO::need here CASL
735 nodePos++;
736 //shift right done after this block
737 printDebug(DM_TreeIndex,"located Node full new node create at right position %d shift node",loc);
738 //manage First level
739 iter->mutex_.releaseShareLock(db->procSlot);
740 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
743 return OK;
745 if(iter->noElements_< noOfBuckets)
747 fstLevel->mutex_.releaseShareLock(db->procSlot);
748 printDebug(DM_TreeIndex,"located Node not full insert in same node");
750 record = ((char*)iter->max_)+ info->fldOffset;
751 printDebug(DM_TreeIndex, "\n%d---%d", *((int*)keyVal), *((int*)record));
752 bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
753 if(result)
755 char **rec = (char**)((char*)iter + sizeof(TreeNode));
756 rec = (char **)((char *)rec + (iter->noElements_ * sizeof(void **)));
757 iter->max_ = tuple;
758 iter->noElements_++;
759 *rec = (char*) tuple;
761 else
763 int start = 0;
764 int end = iter->noElements_ - 1;
765 int middle;
766 int loc = 0;
767 char **rec = (char**)((char*)iter + sizeof(TreeNode));
768 char *tmp = NULL;
769 loc=0;
770 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
772 loc = middle;
773 record = ((char*)*(rec+middle)) + info->fldOffset;
774 printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
775 bool res = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
776 if(res)
778 end = middle - 1;
780 else
782 res = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
783 if (res) {
784 start = middle + 1;
785 loc = start;
786 }else {
787 loc = middle;
788 if (info->isUnique)
790 iter->mutex_.releaseShareLock(db->procSlot);
791 fstLevel->mutex_.releaseShareLock(db->procSlot);
792 printError(ErrUnique, "Unique constraint violation");
793 return ErrUnique;
795 break;
799 printDebug(DM_TreeIndex, "\nInsert pos-%d",loc);
800 rec = (char**)((char*)iter + sizeof(TreeNode));
801 tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
802 memcpy(tmp, (char*)rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));///////// Check the type cast char *
803 memcpy((char*)rec + ((loc+1) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
804 free(tmp);
805 if(loc==0)
807 iter->min_ = tuple;
809 iter->noElements_++;
810 rec = (char **)((char*)rec + (loc * sizeof(void *)));
811 *rec = (char*)tuple;
813 //first level mutex release
814 iter->mutex_.releaseShareLock(db->procSlot);
816 return OK;
819 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
821 DbRetVal rc = OK;
822 HashIndexInfo *info = (HashIndexInfo*) indInfo;
823 CINDEX *iptr = (CINDEX*)indexPtr;
824 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
825 int pos=0;
826 TreeNode *fltnode = start->locateNode(tbl->getDB(),start, tuple, indInfo,rc);
827 if (NULL == fltnode) return rc; //First Level Node Not found
828 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
829 if (NULL == iter) {
830 //element not found
831 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
832 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
833 return OK;
835 rc = removeElement(tbl->getDB(), iter, tuple, info);
836 if( rc != OK ){
837 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
838 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
839 printError(rc, "Remove from TreeNode Failed");
840 return rc;
842 if(0 == iter->noElements_)
844 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
845 }else
847 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
848 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
850 TreeUndoLogInfo hInfo;
851 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
852 hInfo.tuple_ = tuple;
853 hInfo.cIndex_= indexPtr;
854 if (!undoFlag) {
855 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
856 if( rc != OK){
857 //Reverse back
858 //Currently nodes are not freed
859 rc = start->insert(tbl->db_, info, iptr, tuple);
860 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
861 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
862 return rc;
865 return rc;
867 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
869 CINDEX *iptr = (CINDEX*)indexPtr;
870 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
871 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
872 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
873 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
874 free(tmp);
875 fltnode->noElements_--;
876 if(node->prev_!=NULL) node->prev_->next_= node->next_;
877 if(node->next_!=NULL) node->next_->prev_= node->prev_;
878 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
879 chunk->free(db, node);
880 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
881 if(fltnode->noElements_== 0)
883 if(fltnode->prev_!=NULL) {
884 fltnode->prev_->next_= fltnode->next_;
886 else {
887 iptr->hashNodeChunk_ = fltnode->next_ ;
889 if(fltnode->next_!=NULL) {
890 fltnode->next_->prev_= fltnode->prev_;
892 //need discussion in the above situation to solve concureny
893 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
894 fltnode->mutex_.releaseShareLock(db->procSlot);
895 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
896 chunk->free(db, fltnode);
897 }else{
898 fltnode->mutex_.releaseShareLock(db->procSlot);
899 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
903 DbRetVal TreeNode::insert(Database *db,IndexInfo *indInfo,void *indexPtr,void *tuple)
905 DbRetVal rv=OK;
906 TreeNode *iter = (TreeNode *) this ;
907 HashIndexInfo *info = (HashIndexInfo*) indInfo;
908 CINDEX *iptr = (CINDEX*)indexPtr;
909 void *searchKey =(void*)((char*)tuple + info->fldOffset);
910 TreeNode *tnode=NULL;
911 TreeNode *prev = iter;
912 bool result = false;
913 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
914 if (OK != ret) {
915 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
916 return ErrLockTimeOut;
918 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter);
920 while(iter != NULL )
922 //get the second level last node as min and max are not stored in first level tree node
923 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
924 char *record = ((char*)tnode->max_)+ info->fldOffset;
925 result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
926 if (result)
928 break;
929 }else
931 if(tnode->noElements_ >= info->noOfBuckets)
933 if(iter->next_!=NULL)
935 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
936 if (OK != ret)
938 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
939 iter->mutex_.releaseShareLock(db->procSlot);
940 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",iter);
941 return ErrLockTimeOut;
943 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter->next_);
944 prev = iter;
945 iter = iter->next_;
946 prev->mutex_.releaseShareLock(db->procSlot);
947 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",prev);
948 }else{
949 prev = iter;
950 iter = iter->next_;
952 }else
954 if(iter->next_!=NULL)
956 tnode = (TreeNode *)*((char**)((char*)((char*)iter->next_ + sizeof(TreeNode))));
957 char *record = ((char*)tnode->min_)+ info->fldOffset;
958 result = AllDataType::compareVal(searchKey, record,OpLessThan,info->type, info->compLength);
959 if (result)
961 break;
962 } else
964 //if(iter->next_!=NULL)
966 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_,
967 db->procSlot, true);
968 if (OK != ret)
970 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
971 iter->mutex_.releaseShareLock(db->procSlot);
972 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
973 return ErrLockTimeOut;
975 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
976 prev = iter;
977 iter = iter->next_;
978 prev->mutex_.releaseShareLock(db->procSlot);
979 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
981 /*else
983 prev = iter;
984 iter = iter->next_;
987 }else{
988 break;
993 //iter will be null if the value being inserted is greater
994 //than the last I-level node's II-level last node's max
995 if( iter == NULL && prev->noElements_< info->noOfBuckets)
997 iter = prev ;
999 if(iter == NULL)
1001 //TODO::Put this is another function and use the same from 1st record insert
1002 //create Ist level node then leaf node ,insert record and return
1003 printDebug(DM_TreeIndex, "iter =NULL create Ist level node then leaf node ,insert record and return");
1004 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
1005 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rv);
1006 if (tnode == NULL)
1008 printError(rv, "Exit TreeNode allocate fail");
1009 return rv;
1011 tnode->mutex_.init();
1012 strcpy(tnode->mutex_.name, "Tree");
1013 tnode->min_ = tuple;
1014 tnode->max_ = tuple;
1015 tnode->noElements_ =1;
1016 tnode->next_ = NULL;
1017 tnode->prev_ = NULL;
1018 tnode->balance_ = 0;
1019 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
1020 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
1021 *rec = (char*) tuple;
1022 TreeNode *prevNode = (TreeNode*)*(char**)((char*) prev +sizeof(TreeNode)+((prev->noElements_-1)* sizeof(void*)));
1023 prevNode->next_= tnode;
1024 tnode->prev_= prevNode;
1025 //fist levelnode
1026 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
1027 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
1028 if (ftnode == NULL)
1030 printDebug(DM_TreeIndex, "Exit TreeNode firstlevel allocate fail");
1031 return rv;
1033 ftnode->mutex_.init();
1034 strcpy(ftnode->mutex_.name, "I-Tree");
1035 ftnode->min_= NULL;
1036 ftnode->max_ = NULL;
1037 ftnode->noElements_ =1;
1038 ftnode->next_ = NULL;
1039 ftnode->balance_ = 0;
1040 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
1041 *tn = (char*)tnode;
1042 ftnode->prev_= prev;
1043 prev->next_=ftnode;
1044 prev->mutex_.releaseShareLock(db->procSlot);
1045 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
1046 return OK;
1048 //Get second level node and node position from the
1049 //first level node identified above as 'iter'
1050 int nodepos=0;
1051 tnode = locateNodeFromFirstLevel(iter, indInfo, tuple, &nodepos);
1052 //first level mutex is taken and it is released in the below function
1053 //This is because in case arrangement in first level node when it is full
1054 //then subsequent first level node mutex is taken and current first level node
1055 //mutex is released
1056 rv = tnode->insertRecordIntoNodeAndArrangeFirstLevel(db, indInfo, indexPtr, tuple, iter, nodepos);
1057 return rv;
1060 TreeNode* TreeNode::locateNode(Database *db, TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv)
1062 if(iter == NULL) return NULL;
1063 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1064 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1065 TreeNode *tnode=NULL;
1066 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
1067 if (OK != ret) {
1068 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1069 rv = ErrLockTimeOut;
1070 return NULL;
1072 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
1073 TreeNode *tmpNode=NULL;
1074 while(iter->noElements_>= info->noOfBuckets && iter != NULL)
1076 tnode = (TreeNode *)*((char**)((char*)iter + sizeof(TreeNode)+ ((iter->noElements_-1)*sizeof(void *))));
1077 char *record = ((char*)tnode->max_)+ info->fldOffset;
1078 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
1079 if (result)
1081 break;
1082 }else
1084 if(iter->next_!=NULL)
1086 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
1087 if (OK != ret)
1089 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1090 iter->mutex_.releaseShareLock(db->procSlot);
1091 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1092 rv = ErrLockTimeOut;
1093 return NULL;
1095 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
1096 tmpNode = iter;
1097 iter = iter->next_;
1098 tmpNode->mutex_.releaseShareLock(db->procSlot);
1099 printDebug(DM_TreeIndex," Mutex Release on %x\n",tmpNode);
1100 }else{
1101 iter->mutex_.releaseShareLock(db->procSlot);
1102 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1103 iter = iter->next_;
1107 //Get leaf Node
1108 return iter;
1111 TreeNode *TreeNode::locateNodeFromFirstLevel(TreeNode *ftnode, IndexInfo *indInfo,void *tuple, int *pos)
1113 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1114 int fldOffset = info->fldOffset;
1115 DataType type = info->type;
1116 int length = info->compLength;
1117 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1118 int loc=0, middle = 0, start = 0, end = ftnode->noElements_-1;
1119 char **node = (char**)((char*)ftnode + sizeof(TreeNode));
1120 TreeNode *tNode;
1121 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1123 loc = middle;
1124 char *record =(char *)(((TreeNode *) *(char**)((char*)node + (loc * sizeof(void *))))->max_)+fldOffset;
1126 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,type, length);
1127 if(res)
1129 end = middle - 1;
1131 else
1133 res = AllDataType::compareVal(searchKey, record, OpGreaterThan, type, length);
1134 if (res) {
1135 start = middle + 1;
1136 if(start <= (ftnode->noElements_-1)) loc = start;
1137 }else {
1138 loc=middle;
1139 break;
1143 printDebug(DM_TreeIndex, "inside locateNodeFromFirstLevel loc=%d",loc);
1144 *pos=loc;
1145 tNode = ((TreeNode *)*(char**)((char*)node + (loc * sizeof(void *))));
1146 return tNode;
1149 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
1151 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1152 int loc=0, middle=0, start=0, end=iter->noElements_-1;
1153 char **rec = (char**)((char*)iter + sizeof(TreeNode));
1154 DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
1155 if (OK != ret) {
1156 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1157 return ErrLockTimeOut;
1159 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1161 loc = middle;
1162 char *record = ((char*)*(rec+middle)) + info->fldOffset;
1163 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
1164 info->type, info->compLength);
1165 if(res)
1167 end = middle - 1;
1169 else
1171 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
1172 info->type, info->compLength);
1173 if (res) {
1174 start = middle + 1;
1175 loc = start;
1176 } else {
1177 loc = middle;
1178 break;
1182 if (loc == iter->noElements_-1)
1184 iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
1185 }else {
1186 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
1187 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
1188 sizeof(void *) * (iter->noElements_ - loc));
1189 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
1190 sizeof(void *) * (iter->noElements_ - loc));
1191 free(tmp);
1193 if(loc==0)
1195 iter->min_ = *(char**)rec ;
1197 iter->noElements_--;
1198 iter->mutex_.releaseShareLock(db->procSlot);
1199 return OK;
1203 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
1205 CINDEX *iptr = (CINDEX*)indexPtr;
1207 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1208 //check whether the index key is updated or not
1209 //if it is not updated return from here
1210 bool keyNotUpdated = false;
1211 FieldIterator idxFldIter = info->idxFldList.getIterator();
1212 while (idxFldIter.hasElement())
1214 FieldDef *idef = idxFldIter.nextElement();
1215 FieldIterator fldIter = tbl->fldList_.getIterator();
1216 while (fldIter.hasElement())
1218 FieldDef *def = fldIter.nextElement();
1219 if (0 == strcmp(def->fldName_, idef->fldName_))
1221 if (NULL != def->bindVal_)
1223 //Not Implemented
1224 return ErrNotYet;
1226 keyNotUpdated = true;
1227 break;
1231 if (keyNotUpdated)
1233 return OK;
1235 return ErrNotYet;
1238 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
1240 struct timeval timeout, timeval;
1241 timeout.tv_sec = Conf::config.getMutexSecs();
1242 timeout.tv_usec = Conf::config.getMutexUSecs();
1243 int tries=0;
1244 int totalTries = Conf::config.getMutexRetries() *2;
1245 int ret =0;
1246 while (tries < totalTries)
1248 ret = 0;
1249 if (isX)
1250 ret = node->mutex_.getExclusiveLock(procSlot,true);
1251 else
1252 ret = node->mutex_.getShareLock(procSlot,true);
1253 if (ret == 0) break;
1254 timeval.tv_sec = timeout.tv_sec;
1255 timeval.tv_usec = timeout.tv_usec;
1256 os::select(0, 0, 0, 0, &timeval);
1257 tries++;
1259 if (tries >= totalTries) return ErrLockTimeOut;
1260 return OK;
1263 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
1265 struct timeval timeout, timeval;
1266 timeout.tv_sec = Conf::config.getMutexSecs();
1267 timeout.tv_usec = Conf::config.getMutexUSecs();
1268 int tries=0;
1269 int totalTries = Conf::config.getMutexRetries() *2;
1270 int ret =0;
1271 while (tries < totalTries)
1273 ret = 0;
1274 ret = node->mutex_.getExclusiveLock(procSlot,true, true);
1275 if (ret == 0) break;
1276 timeval.tv_sec = timeout.tv_sec;
1277 timeval.tv_usec = timeout.tv_usec;
1278 os::select(0, 0, 0, 0, &timeval);
1279 tries++;
1281 if (tries >= totalTries) return ErrLockTimeOut;
1282 return OK;