?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fix for trie index
[csql.git] / src / storage / TreeIndex.cxx
blob07bfd67c4f5f6f278258477dfec68f4960f6d196
1 /***************************************************************************
2 * Copyright (C) 2007 by www.databasecache.com *
3 * Contact: praba_tuty@databasecache.com *
4 * *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
9 * *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
14 * *
15 ***************************************************************************/
16 #include<Index.h>
17 #include<CatalogTables.h>
18 #include<Lock.h>
19 #include<Debug.h>
20 #include<Table.h>
21 #include<TableImpl.h>
22 #include<Predicate.h>
23 #include<PredicateImpl.h>
24 DbRetVal TreeIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
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 int i=0;
302 while(iter != NULL)
303 {
304 i++;
305 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
306 char *record = ((char*)tnode->max_)+ fldOffset;
307 TreeNode *needremovetnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))));
308 printf(" <First level > node:%d noElements:%d </First level>\n",i, iter->noElements_);
309 for(int i=0;i< iter->noElements_;i++)
310 {
311 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
312 printf(" <Second Level Node> Node:%d Elements:%d Min:%d Max:%d </Second Level Node>\n ",i, tnode->noElements_, *(int*)((char*)tnode->min_+fldOffset), *(int*)((char*)tnode->max_ + fldOffset));
313 char **rec= (char**)((char*)tnode + sizeof(TreeNode));
314 for(int j=0; j < tnode->noElements_; j++){
315 printf("%d,",*((int*)((char*) *(rec + j )+fldOffset)));
316 }
317 printf("\n");
318
319 }
320 iter=iter->next_;
321 }
322 printf("</TreeNode Info>\n");
323 }
324 void TreeNode::displayAll()
325 {
326 DbRetVal rv=OK;
327 TreeNode *iter = (TreeNode *) this ;
328 TreeNode *tnode=NULL;
329 long long totalElement=0;
330 int count=1;
331 printf("<TreeNode count>\n");
332 while(iter != NULL)
333 {
334 printf(" <First Level Node> %d <Total Elements> %d </Total Elements> <Mutex> %x %d </Mutex></First Level Node>\n", count, iter->noElements_, &iter->mutex_, iter->mutex_.getLockVal());
335 for(int i=0;i< iter->noElements_;i++)
336 {
337 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((i)*sizeof(void *))));
338 printf(" <Second Level Node %d> %d <Mutex> %x %d</Mutex> </Second Level Node>\n",i, tnode->noElements_, &tnode->mutex_, tnode->mutex_.getLockVal());
339 totalElement += tnode->noElements_;
340 }
341 iter=iter->next_;
342 count++;
343 }
344 printf(" <Total Records> %lld </Total Records>\n",totalElement);
345 printf("</TreeNode count>\n");
346 }
347
348 DbRetVal TreeNode::insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos)
349 {
350 DbRetVal rv=OK;
351 TreeNode *start = (TreeNode *) this;
352 HashIndexInfo *info = (HashIndexInfo*) indInfo;
353 CINDEX *iptr = (CINDEX*)indexPtr;
354 int offset = info->fldOffset;
355 DataType type = info->type;
356 int noOfBuckets = info->noOfBuckets;
357 char **node = NULL;
358 char *tmp = NULL;
359 char *tmpnode=NULL;
360 TreeNode *tempNode = start;
361 if(start->noElements_< noOfBuckets)
362 {
363 printDebug(DM_TreeIndex,"insertNodeIntoFirstLevel after node insert manage first level node");
364 if(start->noElements_<= nodepos)
365 {
366 node = (char **)((char*)start + sizeof(TreeNode) + (nodepos * sizeof(void *)));
367 start->noElements_++;
368 *node = (char*)newNode;
369 }else
370 {
371 node = (char**)((char*)start + sizeof(TreeNode));
372 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
373 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
374 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
375 free(tmp);
376 node = (char **)((char*)node + (nodepos * sizeof(void *)));
377 *node = (char*)newNode;
378 start->noElements_++;
379 }
380 }
381 else
382 {
383 node = (char**)((char*)start + sizeof(TreeNode));
384 if(start->noElements_ > nodepos)
385 {
386 tmpnode = *(char **)((char*)node+ ((start->noElements_-1) * sizeof(void *)));//store last one
387 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
388 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos-1));
389 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos-1));
390 free(tmp);
391 node = (char **)((char*)node + (nodepos * sizeof(void *)));
392 *node = (char*)newNode;
393 }else
394 {
395 tmpnode =(char*)newNode;
396 }
397 nodepos=0;
398 if( start->next_ != NULL && start->next_->noElements_< noOfBuckets)
399 {
400 start = start->next_;
401
402 node = (char**)((char*)start + sizeof(TreeNode));
403 tmp = (char *)malloc(sizeof(void *) * (start->noElements_ - nodepos));
404 memcpy(tmp, (char*)node + (nodepos * sizeof(void *)), sizeof(void *) * (start->noElements_ - nodepos));
405 memcpy((char*)node + ((nodepos+1) * sizeof(void *)), tmp, sizeof(void *) * (start->noElements_ - nodepos));
406 free(tmp);
407 node = (char **)((char*)node + (nodepos * sizeof(void *)));
408 *node = (char*)tmpnode;
409 start->noElements_++;
410 start->mutex_.releaseShareLock(db->procSlot);
411 }else
412 {
413 printDebug(DM_TreeIndex, "Check if full and start->next_ ==NULL then create new one");
414 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
415 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
416 if (ftnode == NULL)
417 {
418 printError(rv, "Exit TreeNode firstlevel allocate fail");
419 tempNode->mutex_.releaseShareLock(db->procSlot);
420 return rv;
421 }
422 ftnode->mutex_.init();
423 strcpy(ftnode->mutex_.name, "I-Tree");
424 ftnode->min_= NULL;
425 ftnode->max_ = NULL;
426 ftnode->noElements_ =1;
427 ftnode->balance_ = 0;
428 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
429 *tn = (char*)tmpnode;
430 ftnode->next_ = start->next_;
431 ftnode->prev_ = start;
432 start->next_ = ftnode;
433 }
434 }
435 tempNode->mutex_.releaseShareLock(db->procSlot);
436 printDebug(DM_TreeIndex," Mutex Release on %x\n",tempNode);
437 return OK;
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 //element not found
831 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
832 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
833 return OK;
834 }
835 rc = removeElement(tbl->getDB(), iter, tuple, info);
836 if( rc != OK ){
837 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
838 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
839 printError(rc, "Remove from TreeNode Failed");
840 return rc;
841 }
842 if(0 == iter->noElements_)
843 {
844 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
845 }else
846 {
847 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
848 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
849 }
850 TreeUndoLogInfo hInfo;
851 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
852 hInfo.tuple_ = tuple;
853 hInfo.cIndex_= indexPtr;
854 if (!undoFlag) {
855 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
856 if( rc != OK){
857 //Reverse back
858 //Currently nodes are not freed
859 rc = start->insert(tbl->db_, info, iptr, tuple);
860 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
861 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
862 return rc;
863 }
864 }
865 return rc;
866 }
867 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
868 {
869 CINDEX *iptr = (CINDEX*)indexPtr;
870 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
871 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
872 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
873 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
874 free(tmp);
875 fltnode->noElements_--;
876 if(node->prev_!=NULL) node->prev_->next_= node->next_;
877 if(node->next_!=NULL) node->next_->prev_= node->prev_;
878 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
879 chunk->free(db, node);
880 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
881 if(fltnode->noElements_== 0)
882 {
883 if(fltnode->prev_!=NULL) {
884 fltnode->prev_->next_= fltnode->next_;
885 }
886 else {
887 iptr->hashNodeChunk_ = fltnode->next_ ;
888 }
889 if(fltnode->next_!=NULL) {
890 fltnode->next_->prev_= fltnode->prev_;
891 }
892 //need discussion in the above situation to solve concureny
893 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
894 fltnode->mutex_.releaseShareLock(db->procSlot);
895 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
896 chunk->free(db, fltnode);
897 }else{
898 fltnode->mutex_.releaseShareLock(db->procSlot);
899 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
900 }
901 }
902
903 DbRetVal TreeNode::insert(Database *db,IndexInfo *indInfo,void *indexPtr,void *tuple)
904 {
905 DbRetVal rv=OK;
906 TreeNode *iter = (TreeNode *) this ;
907 HashIndexInfo *info = (HashIndexInfo*) indInfo;
908 CINDEX *iptr = (CINDEX*)indexPtr;
909 void *searchKey =(void*)((char*)tuple + info->fldOffset);
910 TreeNode *tnode=NULL;
911 TreeNode *prev = iter;
912 bool result = false;
913 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
914 if (OK != ret) {
915 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
916 return ErrLockTimeOut;
917 }
918 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter);
919
920 while(iter != NULL )
921 {
922 //get the second level last node as min and max are not stored in first level tree node
923 tnode = (TreeNode *)*((char**)((char*)((char*)iter + sizeof(TreeNode))+ ((iter->noElements_-1)*sizeof(void *))));
924 char *record = ((char*)tnode->max_)+ info->fldOffset;
925 result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
926 if (result)
927 {
928 break;
929 }else
930 {
931 if(tnode->noElements_ >= info->noOfBuckets)
932 {
933 if(iter->next_!=NULL)
934 {
935 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
936 if (OK != ret)
937 {
938 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
939 iter->mutex_.releaseShareLock(db->procSlot);
940 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",iter);
941 return ErrLockTimeOut;
942 }
943 printDebug(DM_TreeIndex," Tree I Level Mutex Taken on %x\n",iter->next_);
944 prev = iter;
945 iter = iter->next_;
946 prev->mutex_.releaseShareLock(db->procSlot);
947 printDebug(DM_TreeIndex," Tree I Level Mutex Release on %x\n",prev);
948 }else{
949 prev = iter;
950 iter = iter->next_;
951 }
952 }else
953 {
954 if(iter->next_!=NULL)
955 {
956 tnode = (TreeNode *)*((char**)((char*)((char*)iter->next_ + sizeof(TreeNode))));
957 char *record = ((char*)tnode->min_)+ info->fldOffset;
958 result = AllDataType::compareVal(searchKey, record,OpLessThan,info->type, info->compLength);
959 if (result)
960 {
961 break;
962 } else
963 {
964 //if(iter->next_!=NULL)
965 {
966 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_,
967 db->procSlot, true);
968 if (OK != ret)
969 {
970 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
971 iter->mutex_.releaseShareLock(db->procSlot);
972 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
973 return ErrLockTimeOut;
974 }
975 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
976 prev = iter;
977 iter = iter->next_;
978 prev->mutex_.releaseShareLock(db->procSlot);
979 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
980 }
981 /*else
982 {
983 prev = iter;
984 iter = iter->next_;
985 }*/
986 }
987 }else{
988 break;
989 }
990 }
991 }
992 }
993 //iter will be null if the value being inserted is greater
994 //than the last I-level node's II-level last node's max
995 if( iter == NULL && prev->noElements_< info->noOfBuckets)
996 {
997 iter = prev ;
998 }
999 if(iter == NULL)
1000 {
1001 //TODO::Put this is another function and use the same from 1st record insert
1002 //create Ist level node then leaf node ,insert record and return
1003 printDebug(DM_TreeIndex, "iter =NULL create Ist level node then leaf node ,insert record and return");
1004 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
1005 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rv);
1006 if (tnode == NULL)
1007 {
1008 printError(rv, "Exit TreeNode allocate fail");
1009 return rv;
1010 }
1011 tnode->mutex_.init();
1012 strcpy(tnode->mutex_.name, "Tree");
1013 tnode->min_ = tuple;
1014 tnode->max_ = tuple;
1015 tnode->noElements_ =1;
1016 tnode->next_ = NULL;
1017 tnode->prev_ = NULL;
1018 tnode->balance_ = 0;
1019 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
1020 printDebug(DM_TreeIndex, "Storing first record at %x\n", rec);
1021 *rec = (char*) tuple;
1022 TreeNode *prevNode = (TreeNode*)*(char**)((char*) prev +sizeof(TreeNode)+((prev->noElements_-1)* sizeof(void*)));
1023 prevNode->next_= tnode;
1024 tnode->prev_= prevNode;
1025 //fist levelnode
1026 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
1027 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rv);
1028 if (ftnode == NULL)
1029 {
1030 printDebug(DM_TreeIndex, "Exit TreeNode firstlevel allocate fail");
1031 return rv;
1032 }
1033 ftnode->mutex_.init();
1034 strcpy(ftnode->mutex_.name, "I-Tree");
1035 ftnode->min_= NULL;
1036 ftnode->max_ = NULL;
1037 ftnode->noElements_ =1;
1038 ftnode->next_ = NULL;
1039 ftnode->balance_ = 0;
1040 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
1041 *tn = (char*)tnode;
1042 ftnode->prev_= prev;
1043 prev->next_=ftnode;
1044 prev->mutex_.releaseShareLock(db->procSlot);
1045 printDebug(DM_TreeIndex," Mutex Release on %x\n",prev);
1046 return OK;
1047 }
1048 //Get second level node and node position from the
1049 //first level node identified above as 'iter'
1050 int nodepos=0;
1051 tnode = locateNodeFromFirstLevel(iter, indInfo, tuple, &nodepos);
1052 //first level mutex is taken and it is released in the below function
1053 //This is because in case arrangement in first level node when it is full
1054 //then subsequent first level node mutex is taken and current first level node
1055 //mutex is released
1056 rv = tnode->insertRecordIntoNodeAndArrangeFirstLevel(db, indInfo, indexPtr, tuple, iter, nodepos);
1057 return rv;
1058 }
1059
1060 TreeNode* TreeNode::locateNode(Database *db, TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv)
1061 {
1062 if(iter == NULL) return NULL;
1063 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1064 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1065 TreeNode *tnode=NULL;
1066 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, db->procSlot, true);
1067 if (OK != ret) {
1068 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1069 rv = ErrLockTimeOut;
1070 return NULL;
1071 }
1072 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter);
1073 TreeNode *tmpNode=NULL;
1074 while(iter->noElements_>= info->noOfBuckets && iter != NULL)
1075 {
1076 tnode = (TreeNode *)*((char**)((char*)iter + sizeof(TreeNode)+ ((iter->noElements_-1)*sizeof(void *))));
1077 char *record = ((char*)tnode->max_)+ info->fldOffset;
1078 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,info->type, info->compLength);
1079 if (result)
1080 {
1081 break;
1082 }else
1083 {
1084 if(iter->next_!=NULL)
1085 {
1086 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter->next_, db->procSlot, true);
1087 if (OK != ret)
1088 {
1089 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1090 iter->mutex_.releaseShareLock(db->procSlot);
1091 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1092 rv = ErrLockTimeOut;
1093 return NULL;
1094 }
1095 printDebug(DM_TreeIndex," Mutex Taken on %x\n",iter->next_);
1096 tmpNode = iter;
1097 iter = iter->next_;
1098 tmpNode->mutex_.releaseShareLock(db->procSlot);
1099 printDebug(DM_TreeIndex," Mutex Release on %x\n",tmpNode);
1100 }else{
1101 iter->mutex_.releaseShareLock(db->procSlot);
1102 printDebug(DM_TreeIndex," Mutex Release on %x\n",iter);
1103 iter = iter->next_;
1104 }
1105 }
1106 }
1107 //Get leaf Node
1108 return iter;
1109
1110 }
1111 TreeNode *TreeNode::locateNodeFromFirstLevel(TreeNode *ftnode, IndexInfo *indInfo,void *tuple, int *pos)
1112 {
1113 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1114 int fldOffset = info->fldOffset;
1115 DataType type = info->type;
1116 int length = info->compLength;
1117 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1118 int loc=0, middle = 0, start = 0, end = ftnode->noElements_-1;
1119 char **node = (char**)((char*)ftnode + sizeof(TreeNode));
1120 TreeNode *tNode;
1121 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1122 {
1123 loc = middle;
1124 char *record =(char *)(((TreeNode *) *(char**)((char*)node + (loc * sizeof(void *))))->max_)+fldOffset;
1125
1126 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,type, length);
1127 if(res)
1128 {
1129 end = middle - 1;
1130 }
1131 else
1132 {
1133 res = AllDataType::compareVal(searchKey, record, OpGreaterThan, type, length);
1134 if (res) {
1135 start = middle + 1;
1136 if(start <= (ftnode->noElements_-1)) loc = start;
1137 }else {
1138 loc=middle;
1139 break;
1140 }
1141 }
1142 }
1143 printDebug(DM_TreeIndex, "inside locateNodeFromFirstLevel loc=%d",loc);
1144 *pos=loc;
1145 tNode = ((TreeNode *)*(char**)((char*)node + (loc * sizeof(void *))));
1146 return tNode;
1147 }
1148
1149 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
1150 {
1151 void *searchKey =(void*)((char*)tuple + info->fldOffset);
1152 int loc=0, middle=0, start=0, end=iter->noElements_-1;
1153 char **rec = (char**)((char*)iter + sizeof(TreeNode));
1154 DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
1155 if (OK != ret) {
1156 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
1157 return ErrLockTimeOut;
1158 }
1159 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
1160 {
1161 loc = middle;
1162 char *record = ((char*)*(rec+middle)) + info->fldOffset;
1163 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
1164 info->type, info->compLength);
1165 if(res)
1166 {
1167 end = middle - 1;
1168 }
1169 else
1170 {
1171 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
1172 info->type, info->compLength);
1173 if (res) {
1174 start = middle + 1;
1175 loc = start;
1176 } else {
1177 loc = middle;
1178 break;
1179 }
1180 }
1181 }
1182 if (loc == iter->noElements_-1)
1183 {
1184 iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
1185 }else {
1186 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
1187 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
1188 sizeof(void *) * (iter->noElements_ - loc));
1189 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
1190 sizeof(void *) * (iter->noElements_ - loc));
1191 free(tmp);
1192 }
1193 if(loc==0)
1194 {
1195 iter->min_ = *(char**)rec ;
1196 }
1197 iter->noElements_--;
1198 iter->mutex_.releaseShareLock(db->procSlot);
1199 return OK;
1200 }
1201
1202
1203 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
1204 {
1205 CINDEX *iptr = (CINDEX*)indexPtr;
1206
1207 HashIndexInfo *info = (HashIndexInfo*) indInfo;
1208 //check whether the index key is updated or not
1209 //if it is not updated return from here
1210 bool keyNotUpdated = false;
1211 FieldIterator idxFldIter = info->idxFldList.getIterator();
1212 while (idxFldIter.hasElement())
1213 {
1214 FieldDef *idef = idxFldIter.nextElement();
1215 FieldIterator fldIter = tbl->fldList_.getIterator();
1216 while (fldIter.hasElement())
1217 {
1218 FieldDef *def = fldIter.nextElement();
1219 if (0 == strcmp(def->fldName_, idef->fldName_))
1220 {
1221 if (NULL != def->bindVal_)
1222 {
1223 //Not Implemented
1224 return ErrNotYet;
1225 }
1226 keyNotUpdated = true;
1227 break;
1228 }
1229 }
1230 }
1231 if (keyNotUpdated)
1232 {
1233 return OK;
1234 }
1235 return ErrNotYet;
1236 }
1237
1238 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
1239 {
1240 struct timeval timeout, timeval;
1241 timeout.tv_sec = Conf::config.getMutexSecs();
1242 timeout.tv_usec = Conf::config.getMutexUSecs();
1243 int tries=0;
1244 int totalTries = Conf::config.getMutexRetries() *2;
1245 int ret =0;
1246 while (tries < totalTries)
1247 {
1248 ret = 0;
1249 if (isX)
1250 ret = node->mutex_.getExclusiveLock(procSlot,true);
1251 else
1252 ret = node->mutex_.getShareLock(procSlot,true);
1253 if (ret == 0) break;
1254 timeval.tv_sec = timeout.tv_sec;
1255 timeval.tv_usec = timeout.tv_usec;
1256 os::select(0, 0, 0, 0, &timeval);
1257 tries++;
1258 }
1259 if (tries >= totalTries) return ErrLockTimeOut;
1260 return OK;
1261
1262 }
1263 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
1264 {
1265 struct timeval timeout, timeval;
1266 timeout.tv_sec = Conf::config.getMutexSecs();
1267 timeout.tv_usec = Conf::config.getMutexUSecs();
1268 int tries=0;
1269 int totalTries = Conf::config.getMutexRetries() *2;
1270 int ret =0;
1271 while (tries < totalTries)
1272 {
1273 ret = 0;
1274 ret = node->mutex_.getExclusiveLock(procSlot,true, true);
1275 if (ret == 0) break;
1276 timeval.tv_sec = timeout.tv_sec;
1277 timeval.tv_usec = timeout.tv_usec;
1278 os::select(0, 0, 0, 0, &timeval);
1279 tries++;
1280 }
1281 if (tries >= totalTries) return ErrLockTimeOut;
1282 return OK;
1283 }
1284
Main memory database SQL engine (cvs import)