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