?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
cleanup
[csql.git] / src / storage / TreeIndex.cxx
bloba334ecb73804ebe1f906ec18e7df5e112bc2e33d
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();
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_;
119
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)
124 {
125 printError(rc, "Unable to allocate tree node");
126 chunk->free(db, tnode);
127 delete info;
128 return rc;
129 }
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))
142 {
143 printError(ErrLockTimeOut, "Lock timeout..retry");
144 chunk->free(db, tnode);
145 chunk->free(db, ftnode);
146 delete info;
147 return ErrLockTimeOut;
148 }
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;
155 }
156 }
157 delete db;
158 delete info;
159 return rc;
160
161 }
162 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
163 {
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)
177 {
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)
182 {
183 printError(rc, "Unable to allocate tree node");
184 return rc;
185 }
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;
197
198 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
199 TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
200 if (NULL == ftnode)
201 {
202 printError(rc, "Unable to allocate tree node");
203 chunk->free(tbl->db_, tnode);
204 return rc;
205 }
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))
218 {
219 printError(ErrLockTimeOut, "Lock timeout..retry");
220 chunk->free(tbl->db_, tnode);
221 chunk->free(tbl->db_, ftnode);
222 return ErrLockTimeOut;
223 }
224
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;
230 }
231 }
232 //start->displayAll(offset);
233 if(!undoFlag){
234 rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
235 if (rc !=OK)
236 {
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)
242 {
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 )
253 {
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;
258 }
259 if(0 == iter->noElements_)
260 {
261 removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
262 }else
263 {
264 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
265 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
266 }
267
268 printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
269 return rc;
270
271 }
272 }
273 return rc;
274 }
275
276 long long TreeNode::getTotalElements()
277 {
278 DbRetVal rv=OK;
279 TreeNode *iter = (TreeNode *) this ;
280 TreeNode *tnode=NULL;
281 long long totalElement=0;
282 while(iter != NULL)
283 {
284 for(int i=0;i< iter->noElements_;i++)
285 {
286 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
287 totalElement += tnode->noElements_;
288 }
289 iter=iter->next_;
290 }
291 return totalElement;
292 }
293 void TreeNode::displayAll(int fldOffset)
294 {
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 while(iter != NULL)
302 {
303 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
304 char *record = ((char*)tnode->max_)+ fldOffset;
305 TreeNode *needremovetnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))));
306 printf(" <First level Max/Min> %d / %d </First level>\n",*(int*)record,*(int*)((char*)needremovetnode->min_)+ fldOffset);
307 for(int i=0;i< iter->noElements_;i++)
308 {
309 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
310 printf(" <Second Level Node> %d Min:%d Max:%d</Second Level Node>\n ",i, *(int*)tnode->min_, *(int*)tnode->max_);
311 char **rec= (char**)((char*)tnode + sizeof(TreeNode));
312 for(int j=0; j < tnode->noElements_; j++){
313 printf("%d,",*((int*)((char*) *(rec + j )+fldOffset)));
314 }
315 printf("\n");
316
317 }
318 iter=iter->next_;
319 }
320 printf("</TreeNode Info>\n");
321 }
322 void TreeNode::displayAll()
323 {
324 DbRetVal rv=OK;
325 TreeNode *iter = (TreeNode *) this ;
326 TreeNode *tnode=NULL;
327 long long totalElement=0;
328 int count=1;
329 printf("<TreeNode count>\n");
330 while(iter != NULL)
331 {
332 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());
333 for(int i=0;i< iter->noElements_;i++)
334 {
335 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
336 printf(" <Second Level Node %d> %d <Mutex> %x %d</Mutex> </Second Level Node>\n",i, tnode->noElements_, &tnode->mutex_, tnode->mutex_.getLockVal());
337 totalElement += tnode->noElements_;
338 }
339 iter=iter->next_;
340 count++;
341 }
342 printf(" <Total Records> %lld </Total Records>\n",totalElement);
343 printf("</TreeNode count>\n");
344 }
345
346 DbRetVal TreeNode::insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos)
347 {
348 DbRetVal rv=OK;
349 TreeNode *start = (TreeNode *) this;
350 HashIndexInfo *info = (HashIndexInfo*) indInfo;
351 CINDEX *iptr = (CINDEX*)indexPtr;
352 int offset = info->fldOffset;
353 DataType type = info->type;
354 int noOfBuckets = info->noOfBuckets;
355 char **node = NULL;
356 char *tmp = NULL;
357 char *tmpnode=NULL;
358 TreeNode *tempNode = start;
359 if(start->noElements_< noOfBuckets)
360 {
361 printDebug(DM_TreeIndex,"insertNodeIntoFirstLevel after node insert manage first level node");
362 if(start->noElements_<= nodepos)
363 {
364 node = (char **)((char*)start + sizeof(TreeNode) + (nodepos * sizeof(void *)));
365 start->noElements_++;
366 *node = (char*)newNode;
367 }else
368 {
369 node = (char**)((char*)start + sizeof(TreeNode));
370 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
371 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
372 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
373 free(tmp);
374 node = (char **)((char*)node + (nodepos * sizeof(void *)));
375 *node = (char*)newNode;
376 start->noElements_++;
377 }
378 }
379 else
380 {
381 node = (char**)((char*)start + sizeof(TreeNode));
382 if(start->noElements_ > nodepos)
383 {
384 tmpnode = *(char **)((char*)node+ ((start->noElements_-1) * sizeof(void *)));//store last one
385 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
386 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos-1));
387 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos-1));
388 free(tmp);
389 node = (char **)((char*)node + (nodepos * sizeof(void *)));
390 *node = (char*)newNode;
391 }else
392 {
393 tmpnode =(char*)newNode;
394 }
395 nodepos=0;
396 if( start->next_ != NULL && start->next_->noElements_< noOfBuckets)
397 {
398 start = start->next_;
399
400 node = (char**)((char*)start + sizeof(TreeNode));
401 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
402 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
403 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
404 free(tmp);
405 node = (char **)((char*)node + (nodepos * sizeof(void *)));
406 *node = (char*)tmpnode;
407 start->noElements_++;
408 start->mutex_.releaseShareLock(db->procSlot);
409 }else
410 {
411 printDebug(DM_TreeIndex, "Check if full and start->next_ ==NULL then create new one");
412 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
413 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
414 if (ftnode == NULL)
415 {
416 printError(rv, "Exit TreeNode firstlevel allocate fail");
417 tempNode->mutex_.releaseShareLock(db->procSlot);
418 return rv;
419 }
420 ftnode->mutex_.init();
421 strcpy(ftnode->mutex_.name, "I-Tree");
422 ftnode->min_= NULL;
423 ftnode->max_ = NULL;
424 ftnode->noElements_ =1;
425 ftnode->balance_ = 0;
426 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
427 *tn = (char*)tmpnode;
428 ftnode->next_ = start->next_;
429 ftnode->prev_ = start;
430 start->next_ = ftnode;
431 }
432 }
433 tempNode->mutex_.releaseShareLock(db->procSlot);
434 printDebug(DM_TreeIndex," Mutex Release on %x\n",tempNode);
435 return OK;
436 }
437
438
439
440 DbRetVal TreeNode::insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, void * tuple, TreeNode * fstLevel, int nodePos)
441 {
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;
458 }
459 if(iter->noElements_>= noOfBuckets)
460 {
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)
470 {
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)
475 {
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;
483 }
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);
497 }
498 else
499 {
500 //allocate new node here
501 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
502 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
503 if (tnode == NULL)
504 {
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;
510 }
511 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
512 {
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;
520 }
521 }
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))
534 {
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;
540 }
541 }
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);
548 }
549 }else
550 {
551 record = ((char*)iter->min_)+ info->fldOffset;
552 bool result = AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
553 if(result)
554 {
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)
559 {
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;
567 }
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
578 {
579 //allocate here
580 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
581 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
582 if (tnode == NULL)
583 {
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;
589 }
590 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
591 {
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;
599 }
600 }
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))
614 {
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;
620 }
621 }
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);
628 }
629 }else
630 {
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)
643 {
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)
650 {
651 end = middle - 1;
652 }
653 else
654 {
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;
667 }
668 break;
669 }
670 }
671 }
672
673 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
674 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
675 if (tnode == NULL)
676 {
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;
682 }
683 if( fstLevel->next_!=NULL && fstLevel->noElements_>= noOfBuckets && fstLevel->next_->noElements_< noOfBuckets)
684 {
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;
692 }
693 }
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;
702
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)
719 {
720 iter->min_ = tuple;
721 }
722 if(iter->next_!=NULL){
723 if( 0 !=Mutex::CASL((long*)&iter->next_->prev_, (long)iter->next_->prev_, (long)tnode))
724 {
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;
730 }
731 }
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);
741 }
742 }
743 return OK;
744 }
745 if(iter->noElements_< noOfBuckets)
746 {
747 fstLevel->mutex_.releaseShareLock(db->procSlot);
748 printDebug(DM_TreeIndex,"located Node not full insert in same node");
749
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)
754 {
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;
760 }
761 else
762 {
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)
771 {
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)
777 {
778 end = middle - 1;
779 }
780 else
781 {
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)
789 {
790 iter->mutex_.releaseShareLock(db->procSlot);
791 fstLevel->mutex_.releaseShareLock(db->procSlot);
792 printError(ErrUnique, "Unique constraint violation");
793 return ErrUnique;
794 }
795 break;
796 }
797 }
798 }
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)
806 {
807 iter->min_ = tuple;
808 }
809 iter->noElements_++;
810 rec = (char **)((char*)rec + (loc * sizeof(void *)));
811 *rec = (char*)tuple;
812 }
813 //first level mutex release
814 iter->mutex_.releaseShareLock(db->procSlot);
815 }
816 return OK;
817 }
818
819 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
820 {
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 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
831 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
832 return OK;
833 } //element not found
834 rc = removeElement(tbl->getDB(), iter, tuple, info);
835 if( rc != OK ){
836 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
837 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
838 printError(rc, "Romove from TreeNode Failed ");
839 return rc;
840 }
841 if(0 == iter->noElements_)
842 {
843 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
844 }else
845 {
846 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
847 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
848 }
849 TreeUndoLogInfo hInfo;
850 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
851 hInfo.tuple_ = tuple;
852 hInfo.cIndex_= indexPtr;
853 if (!undoFlag) {
854 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
855 if( rc != OK){
856 //Reverse back
857 //Currently nodes are not freed
858 rc = start->insert(tbl->db_, info, iptr, tuple);
859 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
860 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
861 return rc;
862 }
863 }
864 return rc;
865 }
866 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
867 {
868 CINDEX *iptr = (CINDEX*)indexPtr;
869 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
870 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
871 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
872 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
873 free(tmp);
874 fltnode->noElements_--;
875 if(node->prev_!=NULL) node->prev_->next_= node->next_;
876 if(node->next_!=NULL) node->next_->prev_= node->prev_;
877 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
878 chunk->free(db, node);
879 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
880 if(fltnode->noElements_== 0)
881 {
882 if(fltnode->prev_!=NULL) {
883 fltnode->prev_->next_= fltnode->next_;
884 }
885 else {
886 iptr->hashNodeChunk_ = fltnode->next_ ;
887 }
888 if(fltnode->next_!=NULL) {
889 fltnode->next_->prev_= fltnode->prev_;
890 }
891 //need discussion in the above situation to solve concureny
892 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
893 fltnode->mutex_.releaseShareLock(db->procSlot);
894 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
895 chunk->free(db, fltnode);
896 }else{
897 fltnode->mutex_.releaseShareLock(db->procSlot);
898 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
899 }
900 }
901
902 DbRetVal TreeNode::insert(Database *db,IndexInfo *indInfo,void *indexPtr,void *tuple)
903 {
904 DbRetVal rv=OK;
905 TreeNode *iter = (TreeNode *) this ;
906 HashIndexInfo *info = (HashIndexInfo*) indInfo;
907 CINDEX *iptr = (CINDEX*)indexPtr;
908 void *searchKey =(void*)((char*)tuple + info->fldOffset);
909 TreeNode *tnode=NULL;
910 TreeNode *prev = iter;
911 bool result = false;
912 int ret = iter->mutex_.getExclusiveLock(db->procSlot);
913 if (0 != ret) {
914 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
915 return ErrLockTimeOut;
916 }
917 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
918
919 while(iter != NULL )//&& iter->noElements_>= info->noOfBuckets )
920 {
921 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
922 char *record = ((char*)tnode->max_)+ info->fldOffset;
923 result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
924 if (result)
925 {
926 break;
927 }else
928 {
929 if(tnode->noElements_ >= info->noOfBuckets)
930 {
931 if(iter->next_!=NULL)
932 {
933 ret = iter->next_->mutex_.getExclusiveLock(db->procSlot);
934 if (0 != ret)
935 {
936 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
937 iter->mutex_.releaseShareLock(db->procSlot);
938 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
939 return ErrLockTimeOut;
940 }
941 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
942 prev = iter;
943 iter = iter->next_;
944 prev->mutex_.releaseShareLock(db->procSlot);
945 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
946 }else{
947 prev = iter;
948 iter = iter->next_;
949 }
950 }else
951 {
952 if(iter->next_!=NULL)
953 {
954 tnode = (TreeNode *)*((char**)((char*)((char*)iter->next_ + sizeof(TreeNode))));
955 char *record = ((char*)tnode->min_)+ info->fldOffset;
956 result = AllDataType::compareVal(searchKey, record,OpLessThan,info->type, info->compLength);
957 if (result)
958 {
959 break;
960 } else
961 {
962 if(iter->next_!=NULL)
963 {
964 ret = iter->next_->mutex_.getExclusiveLock(db->procSlot);
965 if (0 != ret)
966 {
967 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
968 iter->mutex_.releaseShareLock(db->procSlot);
969 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
970 return ErrLockTimeOut;
971 }
972 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
973 prev = iter;
974 iter = iter->next_;
975 prev->mutex_.releaseShareLock(db->procSlot);
976 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
977 }else
978 {
979 prev = iter;
980 iter = iter->next_;
981 }
982 }
983 }else{
984 break;
985 }
986 }
987 }
988 }
989 if( iter == NULL && prev->noElements_< info->noOfBuckets)
990 {
991 iter = prev ;
992 }
993 if(iter == NULL)
994 {
995 //create Ist level node then leaf node ,insert record and return
996 printDebug(DM_TreeIndex, "iter =NULL create Ist level node then leaf node ,insert record and return");
997 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
998 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rv);
999 if (tnode == NULL)
1000 {
1001 printError(rv, "Exit TreeNode allocate fail");
1002 return rv;
1003 }
1004 tnode->mutex_.init();
1005 strcpy(tnode->mutex_.name, "Tree");
1006 tnode->min_ = tuple;
1007 tnode->max_ = tuple;
1008 tnode->noElements_ =1;
1009 tnode->next_ = NULL;
1010 tnode->prev_ = NULL;
1011 tnode->balance_ = 0;
1012 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
1013 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
1014 *rec = (char*) tuple;
1015 TreeNode *prevNode = (TreeNode*)*(char**)((char*) prev +sizeof(TreeNode)+((prev->noElements_-1)* sizeof(void*)));
1016 prevNode->next_= tnode;
1017 tnode->prev_= prevNode;
1018 //fist levelnode
1019 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
1020 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
1021 if (ftnode == NULL)
1022 {
1023 printDebug(DM_TreeIndex, "Exit TreeNode firstlevel allocate fail");
1024 return rv;
1025 }
1026 ftnode->mutex_.init();
1027 strcpy(ftnode->mutex_.name, "I-Tree");
1028 ftnode->min_= NULL;
1029 ftnode->max_ = NULL;
1030 ftnode->noElements_ =1;
1031 ftnode->next_ = NULL;
1032 ftnode->balance_ = 0;
1033 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
1034 *tn = (char*)tnode;
1035 ftnode->prev_= prev;
1036 prev->next_=ftnode;
1037 prev->mutex_.releaseShareLock(db->procSlot);
1038 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
1039 return OK;
1040 }
1041 //Get leaf Node
1042 int nodepos=0;
1043 tnode = locateNodeFromFirstLevel(iter, indInfo, tuple, &nodepos);
1044 rv = tnode->insertRecordIntoNodeAndArrangeFirstLevel(db, indInfo, indexPtr, tuple, iter, nodepos);
1045 return rv;
1046 }
1047
1048 TreeNode* TreeNode::locateNode(Database *db, TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv)
1049 {
1050 if(iter == NULL) return NULL;
1051 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1052 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1053 TreeNode *tnode=NULL;
1054 int ret = iter->mutex_.getExclusiveLock(db->procSlot);
1055 if (0 != ret) {
1056 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1057 rv = ErrLockTimeOut;
1058 return NULL;
1059 }
1060 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
1061 TreeNode *tmpNode=NULL;
1062 while(iter->noElements_>= info->noOfBuckets && iter != NULL)
1063 {
1064 tnode = (TreeNode *)*((char**)((char*)iter + sizeof(TreeNode)+ ((iter->noElements_-1)*sizeof(void *))));
1065 char *record = ((char*)tnode->max_)+ info->fldOffset;
1066 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
1067 if (result)
1068 {
1069 break;
1070 }else
1071 {
1072 if(iter->next_!=NULL)
1073 {
1074 ret = iter->next_->mutex_.getExclusiveLock(db->procSlot);
1075 if (0 != ret)
1076 {
1077 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1078 iter->mutex_.releaseShareLock(db->procSlot);
1079 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1080 rv = ErrLockTimeOut;
1081 return NULL;
1082 }
1083 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
1084 tmpNode = iter;
1085 iter = iter->next_;
1086 tmpNode->mutex_.releaseShareLock(db->procSlot);
1087 printDebug(DM_TreeIndex," Mutex Release on %x\n",tmpNode);
1088 }else{
1089 iter->mutex_.releaseShareLock(db->procSlot);
1090 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1091 iter = iter->next_;
1092 }
1093 }
1094 }
1095 //Get leaf Node
1096 return iter;
1097
1098 }
1099 TreeNode *TreeNode::locateNodeFromFirstLevel(TreeNode *ftnode, IndexInfo *indInfo,void *tuple, int *pos)
1100 {
1101 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1102 int fldOffset = info->fldOffset;
1103 DataType type = info->type;
1104 int length = info->compLength;
1105 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1106 int loc=0, middle = 0, start = 0, end = ftnode->noElements_-1;
1107 char **node = (char**)((char*)ftnode + sizeof(TreeNode));
1108 TreeNode *tNode;
1109 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1110 {
1111 loc = middle;
1112 char *record =(char *)(((TreeNode *) *(char**)((char*)node + (loc * sizeof(void *))))->max_)+fldOffset;
1113
1114 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,type, length);
1115 if(res)
1116 {
1117 end = middle - 1;
1118 }
1119 else
1120 {
1121 res = AllDataType::compareVal(searchKey, record, OpGreaterThan, type, length);
1122 if (res) {
1123 start = middle + 1;
1124 if(start <= (ftnode->noElements_-1)) loc = start;
1125 }else {
1126 loc=middle;
1127 break;
1128 }
1129 }
1130 }
1131 printDebug(DM_TreeIndex, "inside locateNodeFromFirstLevel loc=%d",loc);
1132 *pos=loc;
1133 tNode = ((TreeNode *)*(char**)((char*)node + (loc * sizeof(void *))));
1134 return tNode;
1135 }
1136
1137 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
1138 {
1139 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1140 int loc=0, middle=0, start=0, end=iter->noElements_-1;
1141 char **rec = (char**)((char*)iter + sizeof(TreeNode));
1142 int ret = iter->mutex_.getExclusiveLock(db->procSlot,true,true);
1143 if (0 != ret) {
1144 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1145 return ErrLockTimeOut;
1146 }
1147 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1148 {
1149 loc = middle;
1150 char *record = ((char*)*(rec+middle)) + info->fldOffset;
1151 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
1152 info->type, info->compLength);
1153 if(res)
1154 {
1155 end = middle - 1;
1156 }
1157 else
1158 {
1159 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
1160 info->type, info->compLength);
1161 if (res) {
1162 start = middle + 1;
1163 loc = start;
1164 } else {
1165 loc = middle;
1166 break;
1167 }
1168 }
1169 }
1170 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
1171 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
1172 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
1173 free(tmp);
1174 if(loc==0)
1175 {
1176 iter->min_ = tuple;
1177 }
1178 iter->mutex_.releaseShareLock(db->procSlot);
1179 iter->noElements_--;
1180 return OK;
1181 }
1182
1183
1184 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
1185 {
1186 CINDEX *iptr = (CINDEX*)indexPtr;
1187
1188 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1189 //check whether the index key is updated or not
1190 //if it is not updated return from here
1191 bool keyNotUpdated = false;
1192 FieldIterator idxFldIter = info->idxFldList.getIterator();
1193 while (idxFldIter.hasElement())
1194 {
1195 FieldDef *idef = idxFldIter.nextElement();
1196 FieldIterator fldIter = tbl->fldList_.getIterator();
1197 while (fldIter.hasElement())
1198 {
1199 FieldDef *def = fldIter.nextElement();
1200 if (0 == strcmp(def->fldName_, idef->fldName_))
1201 {
1202 if (NULL != def->bindVal_)
1203 {
1204 //Not Implemented
1205 return ErrNotYet;
1206 }
1207 keyNotUpdated = true;
1208 break;
1209 }
1210 }
1211 }
1212 if (keyNotUpdated)
1213 {
1214 return OK;
1215 }
1216 return ErrNotYet;
1217 }
1218
Main memory database SQL engine (cvs import)