?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
code reorg
[csql.git] / src / storage / TreeIndex.cxx
blob3830fe8a59b8cd0cbf961ed9aca57c0bc7485e2b
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)
25 {
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;
65 }
66 if(0 == iter->noElements_)
67 {
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);
71 }
72 delete db;
73 delete info;
74 return rv;
75 }
76 DbRetVal TreeIndex::insertLogicalUndoLog(Database *sysdb, void *data)
77 {
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)
97 {
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)
103 {
104 printError(rc, "Exit TreeNode::Insert - 1 tnode=NULL");
105 delete info;
106 return rc;
107 }
108 tnode->mutex_.init("TNODE-R");
109 tnode->min_ = tUndoInfo->tuple_;
110 tnode->max_ = tUndoInfo->tuple_;
111 tnode->noElements_ =1;
112 tnode->next_ = NULL;
113 tnode->prev_ = NULL;
114 tnode->balance_ = 0;
115 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
116 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
117 *rec = (char*) tUndoInfo->tuple_;
118
119 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
120 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
121 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rc);
122 if (NULL == ftnode)
123 {
124 printError(rc, "Unable to allocate tree node");
125 chunk->free(db, tnode);
126 delete info;
127 return rc;
128 }
129 ftnode->mutex_.init("TNODE-I");
130 ftnode->min_= NULL;
131 ftnode->max_ = NULL;
132 ftnode->noElements_ =1;
133 ftnode->next_ = NULL;
134 ftnode->prev_ = NULL;
135 ftnode->balance_ = 0;
136 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
137 *tn = (char*)tnode;
138 //iptr->hashNodeChunk_ = ftnode;
139 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
140 {
141 printError(ErrLockTimeOut, "Lock timeout..retry");
142 chunk->free(db, tnode);
143 chunk->free(db, ftnode);
144 delete info;
145 return ErrLockTimeOut;
146 }
147 }else {
148 rc = start->insert(db, info, iptr, tUndoInfo->tuple_);
149 if (rc != OK){
150 delete db; delete info;
151 printError(rc, "Error in tree node insertion\n");
152 return rc;
153 }
154 }
155 delete db;
156 delete info;
157 return rc;
158
159 }
160 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
161 {
162 HashIndexInfo *info = (HashIndexInfo*) indInfo;
163 CINDEX *iptr = (CINDEX*)indexPtr;
164 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
165 DbRetVal rc = OK;
166 int offset = info->fldOffset;
167 DataType type = info->type;
168 void *keyPtr =(void*)((char*)tuple + offset);
169 //TreeUndoLogInfo Populated here
170 TreeUndoLogInfo hInfo;
171 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
172 hInfo.tuple_ = tuple;
173 hInfo.cIndex_= indexPtr;
174 if (start == NULL)
175 {
176 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
177 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
178 TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
179 if (tnode == NULL)
180 {
181 printError(rc, "Unable to allocate tree node");
182 return rc;
183 }
184 tnode->mutex_.init("TNODE-R");
185 tnode->min_ = tuple;
186 tnode->max_ = tuple;
187 tnode->noElements_ =1;
188 tnode->next_ = NULL;
189 tnode->prev_ = NULL;
190 tnode->balance_ = 0;
191 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
192 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
193 *rec = (char*) tuple;
194
195 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
196 TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
197 if (NULL == ftnode)
198 {
199 printError(rc, "Unable to allocate tree node");
200 chunk->free(tbl->db_, tnode);
201 return rc;
202 }
203 ftnode->mutex_.init("TNODE-I");
204 ftnode->min_= NULL;
205 ftnode->max_ = NULL;
206 ftnode->noElements_ =1;
207 ftnode->next_ = NULL;
208 ftnode->prev_ = NULL;
209 ftnode->balance_ = 0;
210 //TODO: Handle when two process try to allocate first node
211 char **tn=(char**)((char*) ftnode + sizeof(TreeNode));
212 *tn = (char*)tnode;
213 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
214 {
215 printError(ErrLockTimeOut, "Lock timeout..retry");
216 chunk->free(tbl->db_, tnode);
217 chunk->free(tbl->db_, ftnode);
218 return ErrLockTimeOut;
219 }
220
221 }else {
222 rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
223 if (rc != OK){
224 printError(rc, "Error in tree node insertion for tuple %x", tuple);
225 return rc;
226 }
227 }
228 //start->displayAll(offset);
229 if(!undoFlag){
230 rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
231 if (rc !=OK)
232 {
233 //Reverse back
234 int pos=0;
235 start = (TreeNode*) iptr->hashNodeChunk_;
236 TreeNode *fltnode = start->locateNode(tbl->sysDB_,start, tuple, indInfo,rc);
237 if (NULL == fltnode)
238 {
239 return rc;
240 } //First Level Node Not found
241 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
242 if (NULL == iter){
243 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
244 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
245 return OK;
246 } //element not found
247 rc = removeElement(tbl->getDB(), iter, tuple, info);
248 if( rc != OK )
249 {
250 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
251 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
252 printError(rc, "Romove from TreeNode Failed ");
253 return rc;
254 }
255 if(0 == iter->noElements_)
256 {
257 removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
258 }else
259 {
260 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
261 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
262 }
263
264 printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
265 return rc;
266
267 }
268 }
269 return rc;
270 }
271
272 long long TreeNode::getTotalElements()
273 {
274 DbRetVal rv=OK;
275 TreeNode *iter = (TreeNode *) this ;
276 TreeNode *tnode=NULL;
277 long long totalElement=0;
278 while(iter != NULL)
279 {
280 for(int i=0;i< iter->noElements_;i++)
281 {
282 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
283 totalElement += tnode->noElements_;
284 }
285 iter=iter->next_;
286 }
287 return totalElement;
288 }
289 void TreeNode::displayAll(int fldOffset)
290 {
291 DbRetVal rv=OK;
292 TreeNode *iter = (TreeNode *) this ;
293 TreeNode *tnode=NULL;
294 TreeNode *prev = iter;
295 bool result = false;
296 printf("<TreeNode Info>\n");
297 int i=0;
298 while(iter != NULL)
299 {
300 i++;
301 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
302 char *record = ((char*)tnode->max_)+ fldOffset;
303 TreeNode *needremovetnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))));
304 printf(" <First level > node:%d noElements:%d </First level>\n",i, iter->noElements_);
305 for(int i=0;i< iter->noElements_;i++)
306 {
307 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
308 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));
309 char **rec= (char**)((char*)tnode + sizeof(TreeNode));
310 for(int j=0; j < tnode->noElements_; j++){
311 printf("%d,",*((int*)((char*) *(rec + j )+fldOffset)));
312 }
313 printf("\n");
314
315 }
316 iter=iter->next_;
317 }
318 printf("</TreeNode Info>\n");
319 }
320 void TreeNode::displayAll()
321 {
322 DbRetVal rv=OK;
323 TreeNode *iter = (TreeNode *) this ;
324 TreeNode *tnode=NULL;
325 long long totalElement=0;
326 int count=1;
327 printf("<TreeNode count>\n");
328 while(iter != NULL)
329 {
330 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());
331 for(int i=0;i< iter->noElements_;i++)
332 {
333 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
334 printf(" <Second Level Node %d> %d <Mutex> %x %d</Mutex> </Second Level Node>\n",i, tnode->noElements_, &tnode->mutex_, tnode->mutex_.getLockVal());
335 totalElement += tnode->noElements_;
336 }
337 iter=iter->next_;
338 count++;
339 }
340 printf(" <Total Records> %lld </Total Records>\n",totalElement);
341 printf("</TreeNode count>\n");
342 }
343
344 DbRetVal TreeNode::insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos)
345 {
346 DbRetVal rv=OK;
347 TreeNode *start = (TreeNode *) this;
348 HashIndexInfo *info = (HashIndexInfo*) indInfo;
349 CINDEX *iptr = (CINDEX*)indexPtr;
350 int offset = info->fldOffset;
351 DataType type = info->type;
352 int noOfBuckets = info->noOfBuckets;
353 char **node = NULL;
354 char *tmp = NULL;
355 char *tmpnode=NULL;
356 TreeNode *tempNode = start;
357 if(start->noElements_< noOfBuckets)
358 {
359 printDebug(DM_TreeIndex,"insertNodeIntoFirstLevel after node insert manage first level node");
360 if(start->noElements_<= nodepos)
361 {
362 node = (char **)((char*)start + sizeof(TreeNode) + (nodepos * sizeof(void *)));
363 start->noElements_++;
364 *node = (char*)newNode;
365 }else
366 {
367 node = (char**)((char*)start + sizeof(TreeNode));
368 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
369 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
370 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
371 free(tmp);
372 node = (char **)((char*)node + (nodepos * sizeof(void *)));
373 *node = (char*)newNode;
374 start->noElements_++;
375 }
376 }
377 else
378 {
379 node = (char**)((char*)start + sizeof(TreeNode));
380 if(start->noElements_ > nodepos)
381 {
382 tmpnode = *(char **)((char*)node+ ((start->noElements_-1) * sizeof(void *)));//store last one
383 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
384 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos-1));
385 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos-1));
386 free(tmp);
387 node = (char **)((char*)node + (nodepos * sizeof(void *)));
388 *node = (char*)newNode;
389 }else
390 {
391 tmpnode =(char*)newNode;
392 }
393 nodepos=0;
394 if( start->next_ != NULL && start->next_->noElements_< noOfBuckets)
395 {
396 start = start->next_;
397
398 node = (char**)((char*)start + sizeof(TreeNode));
399 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
400 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
401 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
402 free(tmp);
403 node = (char **)((char*)node + (nodepos * sizeof(void *)));
404 *node = (char*)tmpnode;
405 start->noElements_++;
406 start->mutex_.releaseShareLock(db->procSlot);
407 }else
408 {
409 printDebug(DM_TreeIndex, "Check if full and start->next_ ==NULL then create new one");
410 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
411 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
412 if (ftnode == NULL)
413 {
414 printError(rv, "Exit TreeNode firstlevel allocate fail");
415 tempNode->mutex_.releaseShareLock(db->procSlot);
416 return rv;
417 }
418 ftnode->mutex_.init("TNODE-I");
419 ftnode->min_= NULL;
420 ftnode->max_ = NULL;
421 ftnode->noElements_ =1;
422 ftnode->balance_ = 0;
423 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
424 *tn = (char*)tmpnode;
425 ftnode->next_ = start->next_;
426 ftnode->prev_ = start;
427 start->next_ = ftnode;
428 }
429 }
430 tempNode->mutex_.releaseShareLock(db->procSlot);
431 printDebug(DM_TreeIndex," Mutex Release on %x\n",tempNode);
432 return OK;
433 }
434
435 DbRetVal TreeNode::insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, void * tuple, TreeNode * fstLevel, int nodePos)
436 {
437 TreeNode *iter = (TreeNode *) this;
438 HashIndexInfo *info = (HashIndexInfo*) indInfo;
439 CINDEX *iptr = (CINDEX*)indexPtr;
440 int offset = info->fldOffset;
441 DataType type = info->type;
442 int noOfBuckets = info->noOfBuckets;
443 void *record = NULL;
444 char *keyVal = (char*) tuple + info->fldOffset;
445 DbRetVal rc = OK;
446 bool recordInserted = false;
447 TreeNode *tmpNode=NULL;
448 int ret = iter->mutex_.getExclusiveLock(db->procSlot);
449 if (0 != ret) {
450 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
451 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
452 return ErrLockTimeOut;
453 }
454 if(iter->noElements_>= noOfBuckets)
455 {
456 //Ist level full
457 //Decide new record should go in left or right of second level
458 //if it is inside then create new memcpy all address from location to next node
459 //if left check prev_ node has free space or not if yes insert at end else create new
460 //if right check next_ node has free space or not if yes insert at Ist loc nad do memcpy else create new
461 //create node and link to prevous node and link to the Fistlevel
462 record = ((char*)iter->max_)+ info->fldOffset;
463 bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
464 if(result)
465 {
466 printDebug(DM_TreeIndex,"locateed Node full new node create at iright");
467 //check right for free space if not create node right
468 tmpNode = iter->next_;
469 if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
470 {
471 //insert at beginning
472 ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
473 if (0 != ret) {
474 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
475 iter->mutex_.releaseShareLock(db->procSlot);
476 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
477 return ErrLockTimeOut;
478 }
479 char *tmp = NULL;
480 char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
481 tmp = (char *)malloc(sizeof(void *) * (tmpNode->noElements_));
482 memcpy(tmp, (char*)rec , sizeof(void *) * (iter->noElements_));
483 memcpy((char*)rec + (1*sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_));
484 *rec = (char*)tuple;
485 tmpNode->min_=tuple;
486 tmpNode->noElements_++;
487 free(tmp);
488 iter->mutex_.releaseShareLock(db->procSlot);
489 tmpNode->mutex_.releaseShareLock(db->procSlot);
490 fstLevel->mutex_.releaseShareLock(db->procSlot);
491 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
492 }
493 else
494 {
495 //allocate new node here
496 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
497 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
498 if (tnode == NULL)
499 {
500 printError(rc, "Exit TreeNode create fail after node full");
501 iter->mutex_.releaseShareLock(db->procSlot);
502 fstLevel->mutex_.releaseShareLock(db->procSlot);
503 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
504 return rc;
505 }
506 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
507 {
508 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
509 if (0 != ret) {
510 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
511 chunk->free(db, tnode);
512 iter->mutex_.releaseShareLock(db->procSlot);
513 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
514 return ErrLockTimeOut;
515 }
516 }
517 tnode->mutex_.init();
518 strcpy(tnode->mutex_.name, "Tree");
519 tnode->min_ = tuple;
520 tnode->max_ = tuple;
521 tnode->noElements_ =1;
522 tnode->next_ = NULL;
523 tnode->prev_ = NULL;
524 tnode->balance_ = 0;
525 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
526 *rec = (char*) tuple;
527 if(iter->next_!=NULL){
528 if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
529 {
530 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
531 chunk->free(db, tnode);
532 iter->mutex_.releaseShareLock(db->procSlot);
533 fstLevel->mutex_.releaseShareLock(db->procSlot);
534 return ErrLockTimeOut;
535 }
536 }
537 tnode->next_= iter->next_;
538 tnode->prev_= iter;
539 iter->next_= tnode;
540 nodePos++;
541 iter->mutex_.releaseShareLock(db->procSlot);
542 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
543 }
544 }else
545 {
546 record = ((char*)iter->min_)+ info->fldOffset;
547 bool result = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
548 if(result)
549 {
550 printDebug(DM_TreeIndex,"\nlocateed Node full new node create at left");
551 //check left for free space if not create node left
552 tmpNode = iter->prev_;
553 if(tmpNode!=NULL && tmpNode->noElements_ < noOfBuckets)
554 {
555 //insert at End
556 ret = tmpNode->mutex_.getExclusiveLock(db->procSlot);
557 if (0 != ret) {
558 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
559 iter->mutex_.releaseShareLock(db->procSlot);
560 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
561 return ErrLockTimeOut;
562 }
563 char **rec = (char**)((char*)tmpNode + sizeof(TreeNode));
564 rec = (char **)((char *)rec + (tmpNode->noElements_ * sizeof(void *)));
565 *rec = (char*)tuple;
566 tmpNode->max_ = tuple;
567 tmpNode->noElements_++;
568 iter->mutex_.releaseShareLock(db->procSlot);
569 tmpNode->mutex_.releaseShareLock(db->procSlot);
570 fstLevel->mutex_.releaseShareLock(db->procSlot);
571 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
572 }else
573 {
574 //allocate here
575 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
576 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
577 if (tnode == NULL)
578 {
579 printError(rc, "Exit TreeNode create fail after node full");
580 iter->mutex_.releaseShareLock(db->procSlot);
581 fstLevel->mutex_.releaseShareLock(db->procSlot);
582 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
583 return rc;
584 }
585 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
586 {
587 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
588 if (0 != ret) {
589 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
590 chunk->free(db, tnode);
591 iter->mutex_.releaseShareLock(db->procSlot);
592 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
593 return ErrLockTimeOut;
594 }
595 }
596 tnode->mutex_.init();
597 strcpy(tnode->mutex_.name, "Tree");
598 tnode->min_ = tuple;
599 tnode->max_ = tuple;
600 tnode->noElements_ =1;
601 tnode->next_ = NULL;
602 tnode->prev_ = NULL;
603 tnode->balance_ = 0;
604 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
605 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
606 *rec = (char*) tuple;
607 if(iter->prev_!=NULL) {
608 if( 0 !=Mutex::CASL((long*)&iter->prev_->next_, (long)iter->prev_->next_, (long)tnode))
609 {
610 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
611 chunk->free(db, tnode);
612 iter->mutex_.releaseShareLock(db->procSlot);
613 fstLevel->mutex_.releaseShareLock(db->procSlot);
614 return ErrLockTimeOut;
615 }
616 }
617 tnode->prev_= iter->prev_;
618 tnode->next_= iter;
619 iter->prev_= tnode;
620 //manage First level
621 iter->mutex_.releaseShareLock(db->procSlot);
622 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
623 }
624 }else
625 {
626 //create right
627 //locate position shift node
628 void *tmprec=NULL;
629 char **rec = (char**)((char*) iter + sizeof(TreeNode));
630 tmprec = iter->max_;
631 int start = 0;
632 int end = iter->noElements_ - 1;
633 int middle;
634 int loc = 0;
635 char *tmp = NULL;
636 loc=0;
637 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
638 {
639 loc = middle;
640 record = ((char*)*(rec+middle)) + info->fldOffset;
641 printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
642 bool res = AllDataType::compareVal(keyVal, record,
643 OpLessThan, info->type, info->compLength);
644 if(res)
645 {
646 end = middle - 1;
647 }
648 else
649 {
650 res = AllDataType::compareVal(keyVal, record,
651 OpGreaterThan, info->type, info->compLength);
652 if (res) {
653 start = middle + 1;
654 loc = start;
655 }else {
656 loc = middle;
657 if (info->isUnique) {
658 iter->mutex_.releaseShareLock(db->procSlot);
659 fstLevel->mutex_.releaseShareLock(db->procSlot);
660 printError(ErrUnique, "Unique constraint violation");
661 return ErrUnique;
662 }
663 break;
664 }
665 }
666 }
667
668 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
669 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
670 if (tnode == NULL)
671 {
672 printError(rc, "Exit TreeNode create fail after node full");
673 iter->mutex_.releaseShareLock(db->procSlot);
674 fstLevel->mutex_.releaseShareLock(db->procSlot);
675 printDebug(DM_TreeIndex," Mutex Release on %x\n",fstLevel);
676 return rc;
677 }
678 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
679 {
680 ret = fstLevel->next_->mutex_.getExclusiveLock(db->procSlot);
681 if (0 != ret) {
682 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
683 chunk->free(db, tnode);
684 iter->mutex_.releaseShareLock(db->procSlot);
685 fstLevel->mutex_.releaseShareLock(db->procSlot); //release here 1st level
686 return ErrLockTimeOut;
687 }
688 }
689 tnode->mutex_.init();
690 strcpy(tnode->mutex_.name, "Tree");
691 tnode->min_ = tuple;
692 tnode->max_ = tuple;
693 tnode->noElements_ =1;
694 tnode->next_ = NULL;
695 tnode->prev_ = NULL;
696 tnode->balance_ = 0;
697
698 //shift all element from the location to next node
699 char **fstRec = (char**)((char*)iter + sizeof(TreeNode));
700 tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
701 memcpy(tmp, (char*)fstRec+ (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
702 rec = (char **)((char*)fstRec + (loc * sizeof(void *)));
703 *rec = (char*)tuple;
704 //copy to next node
705 fstRec = (char**)((char*) tnode + sizeof(TreeNode));
706 memcpy((char*)fstRec, tmp, sizeof(void *) * (iter->noElements_- loc));
707 free(tmp);
708 tnode->noElements_= iter->noElements_- loc;
709 tnode->max_= tmprec;
710 tnode->min_= *fstRec;
711 iter->noElements_= loc + 1;
712 iter->max_= tuple;
713 if(loc==0)
714 {
715 iter->min_ = tuple;
716 }
717 if(iter->next_!=NULL){
718 if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
719 {
720 printError(ErrLockTimeOut, "Lock timeout..retry Tree");
721 chunk->free(db, tnode);
722 iter->mutex_.releaseShareLock(db->procSlot);
723 fstLevel->mutex_.releaseShareLock(db->procSlot);
724 return ErrLockTimeOut;
725 }
726 }
727 tnode->next_= iter->next_;
728 tnode->prev_=iter;
729 iter->next_=tnode; //TODO::need here CASL
730 nodePos++;
731 //shift right done after this block
732 printDebug(DM_TreeIndex,"located Node full new node create at right position %d shift node",loc);
733 //manage First level
734 iter->mutex_.releaseShareLock(db->procSlot);
735 fstLevel->insertNodeIntoFirstLevel(db, indInfo, indexPtr, tnode, nodePos);
736 }
737 }
738 return OK;
739 }
740 if(iter->noElements_< noOfBuckets)
741 {
742 fstLevel->mutex_.releaseShareLock(db->procSlot);
743 printDebug(DM_TreeIndex,"located Node not full insert in same node");
744
745 record = ((char*)iter->max_)+ info->fldOffset;
746 printDebug(DM_TreeIndex, "\n%d---%d", *((int*)keyVal), *((int*)record));
747 bool result = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
748 if(result)
749 {
750 char **rec = (char**)((char*)iter + sizeof(TreeNode));
751 rec = (char **)((char *)rec + (iter->noElements_ * sizeof(void **)));
752 iter->max_ = tuple;
753 iter->noElements_++;
754 *rec = (char*) tuple;
755 }
756 else
757 {
758 int start = 0;
759 int end = iter->noElements_ - 1;
760 int middle;
761 int loc = 0;
762 char **rec = (char**)((char*)iter + sizeof(TreeNode));
763 char *tmp = NULL;
764 loc=0;
765 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
766 {
767 loc = middle;
768 record = ((char*)*(rec+middle)) + info->fldOffset;
769 printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
770 bool res = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
771 if(res)
772 {
773 end = middle - 1;
774 }
775 else
776 {
777 res = AllDataType::compareVal(keyVal, record, OpGreaterThan, info->type, info->compLength);
778 if (res) {
779 start = middle + 1;
780 loc = start;
781 }else {
782 loc = middle;
783 if (info->isUnique)
784 {
785 iter->mutex_.releaseShareLock(db->procSlot);
786 fstLevel->mutex_.releaseShareLock(db->procSlot);
787 printError(ErrUnique, "Unique constraint violation");
788 return ErrUnique;
789 }
790 break;
791 }
792 }
793 }
794 printDebug(DM_TreeIndex, "\nInsert pos-%d",loc);
795 rec = (char**)((char*)iter + sizeof(TreeNode));
796 tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
797 memcpy(tmp, (char*)rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));///////// Check the type cast char *
798 memcpy((char*)rec + ((loc+1) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
799 free(tmp);
800 if(loc==0)
801 {
802 iter->min_ = tuple;
803 }
804 iter->noElements_++;
805 rec = (char **)((char*)rec + (loc * sizeof(void *)));
806 *rec = (char*)tuple;
807 }
808 //first level mutex release
809 iter->mutex_.releaseShareLock(db->procSlot);
810 }
811 return OK;
812 }
813
814 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
815 {
816 DbRetVal rc = OK;
817 HashIndexInfo *info = (HashIndexInfo*) indInfo;
818 CINDEX *iptr = (CINDEX*)indexPtr;
819 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
820 int pos=0;
821 TreeNode *fltnode = start->locateNode(tbl->getDB(),start, tuple, indInfo,rc);
822 if (NULL == fltnode) return rc; //First Level Node Not found
823 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
824 if (NULL == iter) {
825 //element not found
826 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
827 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
828 return OK;
829 }
830 rc = removeElement(tbl->getDB(), iter, tuple, info);
831 if( rc != OK ){
832 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
833 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
834 printError(rc, "Remove from TreeNode Failed");
835 return rc;
836 }
837 if(0 == iter->noElements_)
838 {
839 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
840 }else
841 {
842 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
843 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
844 }
845 TreeUndoLogInfo hInfo;
846 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
847 hInfo.tuple_ = tuple;
848 hInfo.cIndex_= indexPtr;
849 if (!undoFlag) {
850 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
851 if( rc != OK){
852 //Reverse back
853 //Currently nodes are not freed
854 rc = start->insert(tbl->db_, info, iptr, tuple);
855 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
856 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
857 return rc;
858 }
859 }
860 return rc;
861 }
862 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
863 {
864 CINDEX *iptr = (CINDEX*)indexPtr;
865 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
866 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
867 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
868 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
869 free(tmp);
870 fltnode->noElements_--;
871 if(node->prev_!=NULL) node->prev_->next_= node->next_;
872 if(node->next_!=NULL) node->next_->prev_= node->prev_;
873 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
874 chunk->free(db, node);
875 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
876 if(fltnode->noElements_== 0)
877 {
878 if(fltnode->prev_!=NULL) {
879 fltnode->prev_->next_= fltnode->next_;
880 }
881 else {
882 iptr->hashNodeChunk_ = fltnode->next_ ;
883 }
884 if(fltnode->next_!=NULL) {
885 fltnode->next_->prev_= fltnode->prev_;
886 }
887 //need discussion in the above situation to solve concureny
888 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
889 fltnode->mutex_.releaseShareLock(db->procSlot);
890 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
891 chunk->free(db, fltnode);
892 }else{
893 fltnode->mutex_.releaseShareLock(db->procSlot);
894 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
895 }
896 }
897
898 DbRetVal TreeNode::insert(Database *db,IndexInfo *indInfo,void *indexPtr,void *tuple)
899 {
900 DbRetVal rv=OK;
901 TreeNode *iter = (TreeNode *) this ;
902 HashIndexInfo *info = (HashIndexInfo*) indInfo;
903 CINDEX *iptr = (CINDEX*)indexPtr;
904 void *searchKey =(void*)((char*)tuple + info->fldOffset);
905 TreeNode *tnode=NULL;
906 TreeNode *prev = iter;
907 bool result = false;
908 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
909 if (OK != ret) {
910 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
911 return ErrLockTimeOut;
912 }
913 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter);
914
915 while(iter != NULL )
916 {
917 //get the second level last node as min and max are not stored in first level tree node
918 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
919 char *record = ((char*)tnode->max_)+ info->fldOffset;
920 result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
921 if (result)
922 {
923 break;
924 }else
925 {
926 if(tnode->noElements_ >= info->noOfBuckets)
927 {
928 if(iter->next_!=NULL)
929 {
930 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
931 if (OK != ret)
932 {
933 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
934 iter->mutex_.releaseShareLock(db->procSlot);
935 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",iter);
936 return ErrLockTimeOut;
937 }
938 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter->next_);
939 prev = iter;
940 iter = iter->next_;
941 prev->mutex_.releaseShareLock(db->procSlot);
942 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",prev);
943 }else{
944 prev = iter;
945 iter = iter->next_;
946 }
947 }else
948 {
949 if(iter->next_!=NULL)
950 {
951 tnode = (TreeNode *)*((char**)((char*)((char*)iter->next_ + sizeof(TreeNode))));
952 char *record = ((char*)tnode->min_)+ info->fldOffset;
953 result = AllDataType::compareVal(searchKey, record,OpLessThan,info->type, info->compLength);
954 if (result)
955 {
956 break;
957 } else
958 {
959 //if(iter->next_!=NULL)
960 {
961 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_,
962 db->procSlot, true);
963 if (OK != ret)
964 {
965 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
966 iter->mutex_.releaseShareLock(db->procSlot);
967 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
968 return ErrLockTimeOut;
969 }
970 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
971 prev = iter;
972 iter = iter->next_;
973 prev->mutex_.releaseShareLock(db->procSlot);
974 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
975 }
976 /*else
977 {
978 prev = iter;
979 iter = iter->next_;
980 }*/
981 }
982 }else{
983 break;
984 }
985 }
986 }
987 }
988 //iter will be null if the value being inserted is greater
989 //than the last I-level node's II-level last node's max
990 if( iter == NULL && prev->noElements_< info->noOfBuckets)
991 {
992 iter = prev ;
993 }
994 if(iter == NULL)
995 {
996 //TODO::Put this is another function and use the same from 1st record insert
997 //create Ist level node then leaf node ,insert record and return
998 printDebug(DM_TreeIndex, "iter =NULL create Ist level node then leaf node ,insert record and return");
999 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
1000 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rv);
1001 if (tnode == NULL)
1002 {
1003 printError(rv, "Exit TreeNode allocate fail");
1004 return rv;
1005 }
1006 tnode->mutex_.init();
1007 strcpy(tnode->mutex_.name, "Tree");
1008 tnode->min_ = tuple;
1009 tnode->max_ = tuple;
1010 tnode->noElements_ =1;
1011 tnode->next_ = NULL;
1012 tnode->prev_ = NULL;
1013 tnode->balance_ = 0;
1014 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
1015 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
1016 *rec = (char*) tuple;
1017 TreeNode *prevNode = (TreeNode*)*(char**)((char*) prev +sizeof(TreeNode)+((prev->noElements_-1)* sizeof(void*)));
1018 prevNode->next_= tnode;
1019 tnode->prev_= prevNode;
1020 //fist levelnode
1021 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
1022 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
1023 if (ftnode == NULL)
1024 {
1025 printDebug(DM_TreeIndex, "Exit TreeNode firstlevel allocate fail");
1026 return rv;
1027 }
1028 ftnode->mutex_.init("TNODE-I");
1029 ftnode->min_= NULL;
1030 ftnode->max_ = NULL;
1031 ftnode->noElements_ =1;
1032 ftnode->next_ = NULL;
1033 ftnode->balance_ = 0;
1034 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
1035 *tn = (char*)tnode;
1036 ftnode->prev_= prev;
1037 prev->next_=ftnode;
1038 prev->mutex_.releaseShareLock(db->procSlot);
1039 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
1040 return OK;
1041 }
1042 //Get second level node and node position from the
1043 //first level node identified above as 'iter'
1044 int nodepos=0;
1045 tnode = locateNodeFromFirstLevel(iter, indInfo, tuple, &nodepos);
1046 //first level mutex is taken and it is released in the below function
1047 //This is because in case arrangement in first level node when it is full
1048 //then subsequent first level node mutex is taken and current first level node
1049 //mutex is released
1050 rv = tnode->insertRecordIntoNodeAndArrangeFirstLevel(db, indInfo, indexPtr, tuple, iter, nodepos);
1051 return rv;
1052 }
1053
1054 TreeNode* TreeNode::locateNode(Database *db, TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv)
1055 {
1056 if(iter == NULL) return NULL;
1057 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1058 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1059 TreeNode *tnode=NULL;
1060 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
1061 if (OK != ret) {
1062 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1063 rv = ErrLockTimeOut;
1064 return NULL;
1065 }
1066 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
1067 TreeNode *tmpNode=NULL;
1068 while(iter->noElements_>= info->noOfBuckets && iter != NULL)
1069 {
1070 tnode = (TreeNode *)*((char**)((char*)iter + sizeof(TreeNode)+ ((iter->noElements_-1)*sizeof(void *))));
1071 char *record = ((char*)tnode->max_)+ info->fldOffset;
1072 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
1073 if (result)
1074 {
1075 break;
1076 }else
1077 {
1078 if(iter->next_!=NULL)
1079 {
1080 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
1081 if (OK != ret)
1082 {
1083 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1084 iter->mutex_.releaseShareLock(db->procSlot);
1085 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1086 rv = ErrLockTimeOut;
1087 return NULL;
1088 }
1089 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
1090 tmpNode = iter;
1091 iter = iter->next_;
1092 tmpNode->mutex_.releaseShareLock(db->procSlot);
1093 printDebug(DM_TreeIndex," Mutex Release on %x\n",tmpNode);
1094 }else{
1095 iter->mutex_.releaseShareLock(db->procSlot);
1096 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1097 iter = iter->next_;
1098 }
1099 }
1100 }
1101 //Get leaf Node
1102 return iter;
1103
1104 }
1105 TreeNode *TreeNode::locateNodeFromFirstLevel(TreeNode *ftnode, IndexInfo *indInfo,void *tuple, int *pos)
1106 {
1107 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1108 int fldOffset = info->fldOffset;
1109 DataType type = info->type;
1110 int length = info->compLength;
1111 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1112 int loc=0, middle = 0, start = 0, end = ftnode->noElements_-1;
1113 char **node = (char**)((char*)ftnode + sizeof(TreeNode));
1114 TreeNode *tNode;
1115 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1116 {
1117 loc = middle;
1118 char *record =(char *)(((TreeNode *) *(char**)((char*)node + (loc * sizeof(void *))))->max_)+fldOffset;
1119
1120 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,type, length);
1121 if(res)
1122 {
1123 end = middle - 1;
1124 }
1125 else
1126 {
1127 res = AllDataType::compareVal(searchKey, record, OpGreaterThan, type, length);
1128 if (res) {
1129 start = middle + 1;
1130 if(start <= (ftnode->noElements_-1)) loc = start;
1131 }else {
1132 loc=middle;
1133 break;
1134 }
1135 }
1136 }
1137 printDebug(DM_TreeIndex, "inside locateNodeFromFirstLevel loc=%d",loc);
1138 *pos=loc;
1139 tNode = ((TreeNode *)*(char**)((char*)node + (loc * sizeof(void *))));
1140 return tNode;
1141 }
1142
1143 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
1144 {
1145 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1146 int loc=0, middle=0, start=0, end=iter->noElements_-1;
1147 char **rec = (char**)((char*)iter + sizeof(TreeNode));
1148 DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
1149 if (OK != ret) {
1150 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1151 return ErrLockTimeOut;
1152 }
1153 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1154 {
1155 loc = middle;
1156 char *record = ((char*)*(rec+middle)) + info->fldOffset;
1157 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
1158 info->type, info->compLength);
1159 if(res)
1160 {
1161 end = middle - 1;
1162 }
1163 else
1164 {
1165 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
1166 info->type, info->compLength);
1167 if (res) {
1168 start = middle + 1;
1169 loc = start;
1170 } else {
1171 loc = middle;
1172 break;
1173 }
1174 }
1175 }
1176 if (loc == iter->noElements_-1)
1177 {
1178 iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
1179 }else {
1180 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
1181 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
1182 sizeof(void *) * (iter->noElements_ - loc));
1183 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
1184 sizeof(void *) * (iter->noElements_ - loc));
1185 free(tmp);
1186 }
1187 if(loc==0)
1188 {
1189 iter->min_ = *(char**)rec ;
1190 }
1191 iter->noElements_--;
1192 iter->mutex_.releaseShareLock(db->procSlot);
1193 return OK;
1194 }
1195
1196
1197 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
1198 {
1199 CINDEX *iptr = (CINDEX*)indexPtr;
1200
1201 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1202 //check whether the index key is updated or not
1203 //if it is not updated return from here
1204 bool keyNotUpdated = false;
1205 FieldIterator idxFldIter = info->idxFldList.getIterator();
1206 while (idxFldIter.hasElement())
1207 {
1208 FieldDef *idef = idxFldIter.nextElement();
1209 FieldIterator fldIter = tbl->fldList_.getIterator();
1210 while (fldIter.hasElement())
1211 {
1212 FieldDef *def = fldIter.nextElement();
1213 if (0 == strcmp(def->fldName_, idef->fldName_))
1214 {
1215 if (NULL != def->bindVal_)
1216 {
1217 //Not Implemented
1218 return ErrNotYet;
1219 }
1220 keyNotUpdated = true;
1221 break;
1222 }
1223 }
1224 }
1225 if (keyNotUpdated)
1226 {
1227 return OK;
1228 }
1229 return ErrNotYet;
1230 }
1231
1232 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
1233 {
1234 struct timeval timeout, timeval;
1235 timeout.tv_sec = Conf::config.getMutexSecs();
1236 timeout.tv_usec = Conf::config.getMutexUSecs();
1237 int tries=0;
1238 int totalTries = Conf::config.getMutexRetries() *2;
1239 int ret =0;
1240 while (tries < totalTries)
1241 {
1242 ret = 0;
1243 if (isX)
1244 ret = node->mutex_.getExclusiveLock(procSlot,true);
1245 else
1246 ret = node->mutex_.getShareLock(procSlot,true);
1247 if (ret == 0) break;
1248 timeval.tv_sec = timeout.tv_sec;
1249 timeval.tv_usec = timeout.tv_usec;
1250 os::select(0, 0, 0, 0, &timeval);
1251 tries++;
1252 }
1253 if (tries >= totalTries) return ErrLockTimeOut;
1254 return OK;
1255
1256 }
1257 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
1258 {
1259 struct timeval timeout, timeval;
1260 timeout.tv_sec = Conf::config.getMutexSecs();
1261 timeout.tv_usec = Conf::config.getMutexUSecs();
1262 int tries=0;
1263 int totalTries = Conf::config.getMutexRetries() *2;
1264 int ret =0;
1265 while (tries < totalTries)
1266 {
1267 ret = 0;
1268 ret = node->mutex_.getExclusiveLock(procSlot,true, true);
1269 if (ret == 0) break;
1270 timeval.tv_sec = timeout.tv_sec;
1271 timeval.tv_usec = timeout.tv_usec;
1272 os::select(0, 0, 0, 0, &timeval);
1273 tries++;
1274 }
1275 if (tries >= totalTries) return ErrLockTimeOut;
1276 return OK;
1277 }
1278
Main memory database SQL engine (cvs import)