code reorg
[csql.git] / src / relational / index / TreeIndex.cxx
blob97e12cd8743d5d6b5d2ddd6aa2ec2ca6abe555f9
1 /***************************************************************************
2 * Copyright (C) 2007 by www.databasecache.com *
3 * Contact: praba_tuty@databasecache.com *
4 * *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
9 * *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
14 * *
15 ***************************************************************************/
16 #include<Index.h>
17 #include<CatalogTables.h>
18 #include<Lock.h>
19 #include<Debug.h>
20 #include<Table.h>
21 #include<TableImpl.h>
22 #include<Predicate.h>
23 #include<PredicateImpl.h>
24 DbRetVal TreeIndex::deleteLogicalUndoLog(Database *sysdb, void *data)
26 DbRetVal rv = OK;
27 TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
28 Database *db = new Database();
29 db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
30 db->setProcSlot(sysdb->procSlot);
31 CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;
32 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
33 //HashIndexInfo populated here
34 HashIndexInfo *info = new HashIndexInfo();
35 info->indexPtr = (char *)iptr;
36 info->noOfBuckets = iptr->noOfBuckets_;
37 info->isUnique = iptr->isUnique_;
38 info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
39 info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
40 info->indType = iptr->indexType_;
41 TreeIndex *treeInd = (TreeIndex*)Index::getIndex(iptr->indexType_);
42 int pos=0;
43 TreeNode *fltnode = start->locateNode(db, start, tUndoInfo->tuple_, info,rv);
44 if (NULL == fltnode){
45 delete db;
46 delete info;
47 return rv;
48 } //First Level Node Not found
49 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, info, tUndoInfo->tuple_, &pos);
50 if (NULL == iter){
51 fltnode->mutex_.releaseShareLock(db->procSlot);
52 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
53 delete db;
54 delete info;
55 return OK;
56 } //element not found
57 rv = treeInd->removeElement(db, iter, tUndoInfo->tuple_, info);
58 if( rv != OK ){
59 fltnode->mutex_.releaseShareLock(db->procSlot);
60 printError(rv, "Romove from TreeNode Failed ");
61 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
62 delete db;
63 delete info;
64 return rv;
66 if(0 == iter->noElements_)
68 treeInd->removeNode(db, tUndoInfo->cIndex_, fltnode,iter, pos);
69 }else { fltnode->mutex_.releaseShareLock(db->procSlot);
70 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
72 delete db;
73 delete info;
74 return rv;
77 DbRetVal TreeIndex::insertLogicalUndoLog(Database *sysdb, void *data)
79 DbRetVal rc = OK;
80 TreeUndoLogInfo *tUndoInfo = (TreeUndoLogInfo *) data;
81 Database *db = new Database();
82 db->setMetaDataPtr((DatabaseMetaData*) tUndoInfo->metaData_);
83 db->setProcSlot(sysdb->procSlot);
84 CINDEX *iptr = (CINDEX*) tUndoInfo->cIndex_;//CINDEX
85 //HashIndexInfo populated here
86 HashIndexInfo *info = new HashIndexInfo();
87 info->indexPtr = (char *)iptr;
88 info->noOfBuckets = iptr->noOfBuckets_;
89 info->isUnique = iptr->isUnique_;
90 info->type = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->type_;
91 info->fldOffset = ((CFIELD*)(((CINDEXFIELD*)(iptr->fstIndFld_))->fieldPtr))->offset_;
92 info->indType = iptr->indexType_;
93 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
94 int offset = info->fldOffset;
95 DataType type = info->type;
96 void *keyPtr =(void*)((char*)tUndoInfo->tuple_ + offset);
97 if (start == NULL)
99 //Currently Nodes are not deleted
100 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
101 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
102 TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
103 if (tnode == NULL)
105 printError(rc, "Exit TreeNode::Insert - 1 tnode=NULL");
106 delete info;
107 return rc;
109 tnode->mutex_.init("TNODE-R");
110 tnode->min_ = tUndoInfo->tuple_;
111 tnode->max_ = tUndoInfo->tuple_;
112 tnode->noElements_ =1;
113 tnode->next_ = NULL;
114 tnode->prev_ = NULL;
115 tnode->balance_ = 0;
116 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
117 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
118 *rec = (char*) tUndoInfo->tuple_;
120 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
121 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
122 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rc);
123 if (NULL == ftnode)
125 printError(rc, "Unable to allocate tree node");
126 chunk->free(db, tnode);
127 delete info;
128 return rc;
130 ftnode->mutex_.init("TNODE-I");
131 ftnode->min_= NULL;
132 ftnode->max_ = NULL;
133 ftnode->noElements_ =1;
134 ftnode->next_ = NULL;
135 ftnode->prev_ = NULL;
136 ftnode->balance_ = 0;
137 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
138 *tn = (char*)tnode;
139 //iptr->hashNodeChunk_ = ftnode;
140 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
142 printError(ErrLockTimeOut, "Lock timeout..retry");
143 chunk->free(db, tnode);
144 chunk->free(db, ftnode);
145 delete info;
146 return ErrLockTimeOut;
148 }else {
149 rc = start->insert(db, info, iptr, tUndoInfo->tuple_);
150 if (rc != OK){
151 delete db; delete info;
152 printError(rc, "Error in tree node insertion\n");
153 return rc;
156 delete db;
157 delete info;
158 return rc;
162 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
164 HashIndexInfo *info = (HashIndexInfo*) indInfo;
165 CINDEX *iptr = (CINDEX*)indexPtr;
166 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
167 DbRetVal rc = OK;
168 int offset = info->fldOffset;
169 DataType type = info->type;
170 void *keyPtr =(void*)((char*)tuple + offset);
171 //TreeUndoLogInfo Populated here
172 TreeUndoLogInfo hInfo;
173 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
174 hInfo.tuple_ = tuple;
175 hInfo.cIndex_= indexPtr;
176 if (start == NULL)
178 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
179 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
180 TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
181 if (tnode == NULL)
183 printError(rc, "Unable to allocate tree node");
184 return rc;
186 tnode->mutex_.init("TNODE-R");
187 tnode->min_ = tuple;
188 tnode->max_ = tuple;
189 tnode->noElements_ =1;
190 tnode->next_ = NULL;
191 tnode->prev_ = NULL;
192 tnode->balance_ = 0;
193 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
194 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
195 *rec = (char*) tuple;
197 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
198 TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
199 if (NULL == ftnode)
201 printError(rc, "Unable to allocate tree node");
202 chunk->free(tbl->db_, tnode);
203 return rc;
205 ftnode->mutex_.init("TNODE-I");
206 ftnode->min_= NULL;
207 ftnode->max_ = NULL;
208 ftnode->noElements_ =1;
209 ftnode->next_ = NULL;
210 ftnode->prev_ = NULL;
211 ftnode->balance_ = 0;
212 //TODO: Handle when two process try to allocate first node
213 char **tn=(char**)((char*) ftnode + sizeof(TreeNode));
214 *tn = (char*)tnode;
215 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
217 printError(ErrLockTimeOut, "Lock timeout..retry");
218 chunk->free(tbl->db_, tnode);
219 chunk->free(tbl->db_, ftnode);
220 return ErrLockTimeOut;
223 }else {
224 rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
225 if (rc != OK){
226 printError(rc, "Error in tree node insertion for tuple %x", tuple);
227 return rc;
230 //start->displayAll(offset);
231 if(!undoFlag){
232 rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
233 if (rc !=OK)
235 //Reverse back
236 int pos=0;
237 start = (TreeNode*) iptr->hashNodeChunk_;
238 TreeNode *fltnode = start->locateNode(tbl->sysDB_,start, tuple, indInfo,rc);
239 if (NULL == fltnode)
241 return rc;
242 } //First Level Node Not found
243 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
244 if (NULL == iter){
245 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
246 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
247 return OK;
248 } //element not found
249 rc = removeElement(tbl->getDB(), iter, tuple, info);
250 if( rc != OK )
252 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
253 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
254 printError(rc, "Romove from TreeNode Failed ");
255 return rc;
257 if(0 == iter->noElements_)
259 removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
260 }else
262 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
263 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
266 printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
267 return rc;
271 return rc;
275 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
277 DbRetVal rc = OK;
278 HashIndexInfo *info = (HashIndexInfo*) indInfo;
279 CINDEX *iptr = (CINDEX*)indexPtr;
280 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
281 int pos=0;
282 TreeNode *fltnode = start->locateNode(tbl->getDB(),start, tuple, indInfo,rc);
283 if (NULL == fltnode) return rc; //First Level Node Not found
284 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
285 if (NULL == iter) {
286 //element not found
287 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
288 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
289 return OK;
291 rc = removeElement(tbl->getDB(), iter, tuple, info);
292 if( rc != OK ){
293 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
294 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
295 printError(rc, "Remove from TreeNode Failed");
296 return rc;
298 if(0 == iter->noElements_)
300 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
301 }else
303 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
304 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
306 TreeUndoLogInfo hInfo;
307 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
308 hInfo.tuple_ = tuple;
309 hInfo.cIndex_= indexPtr;
310 if (!undoFlag) {
311 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
312 if( rc != OK){
313 //Reverse back
314 //Currently nodes are not freed
315 rc = start->insert(tbl->db_, info, iptr, tuple);
316 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
317 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
318 return rc;
321 return rc;
324 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
326 CINDEX *iptr = (CINDEX*)indexPtr;
327 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
328 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
329 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
330 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
331 free(tmp);
332 fltnode->noElements_--;
333 if(node->prev_!=NULL) node->prev_->next_= node->next_;
334 if(node->next_!=NULL) node->next_->prev_= node->prev_;
335 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
336 chunk->free(db, node);
337 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
338 if(fltnode->noElements_== 0)
340 if(fltnode->prev_!=NULL) {
341 fltnode->prev_->next_= fltnode->next_;
343 else {
344 iptr->hashNodeChunk_ = fltnode->next_ ;
346 if(fltnode->next_!=NULL) {
347 fltnode->next_->prev_= fltnode->prev_;
349 //need discussion in the above situation to solve concureny
350 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
351 fltnode->mutex_.releaseShareLock(db->procSlot);
352 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
353 chunk->free(db, fltnode);
354 }else{
355 fltnode->mutex_.releaseShareLock(db->procSlot);
356 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
360 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
362 void *searchKey =(void*)((char*)tuple + info->fldOffset);
363 int loc=0, middle=0, start=0, end=iter->noElements_-1;
364 char **rec = (char**)((char*)iter + sizeof(TreeNode));
365 DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
366 if (OK != ret) {
367 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
368 return ErrLockTimeOut;
370 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
372 loc = middle;
373 char *record = ((char*)*(rec+middle)) + info->fldOffset;
374 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
375 info->type, info->compLength);
376 if(res)
378 end = middle - 1;
380 else
382 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
383 info->type, info->compLength);
384 if (res) {
385 start = middle + 1;
386 loc = start;
387 } else {
388 loc = middle;
389 break;
393 if (loc == iter->noElements_-1)
395 iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
396 }else {
397 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
398 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
399 sizeof(void *) * (iter->noElements_ - loc));
400 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
401 sizeof(void *) * (iter->noElements_ - loc));
402 free(tmp);
404 if(loc==0)
406 iter->min_ = *(char**)rec ;
408 iter->noElements_--;
409 iter->mutex_.releaseShareLock(db->procSlot);
410 return OK;
414 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
416 CINDEX *iptr = (CINDEX*)indexPtr;
418 HashIndexInfo *info = (HashIndexInfo*) indInfo;
419 //check whether the index key is updated or not
420 //if it is not updated return from here
421 bool keyNotUpdated = false;
422 FieldIterator idxFldIter = info->idxFldList.getIterator();
423 while (idxFldIter.hasElement())
425 FieldDef *idef = idxFldIter.nextElement();
426 FieldIterator fldIter = tbl->fldList_.getIterator();
427 while (fldIter.hasElement())
429 FieldDef *def = fldIter.nextElement();
430 if (0 == strcmp(def->fldName_, idef->fldName_))
432 if (NULL != def->bindVal_)
434 //Not Implemented
435 return ErrNotYet;
437 keyNotUpdated = true;
438 break;
442 if (keyNotUpdated)
444 return OK;
446 return ErrNotYet;
449 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
451 struct timeval timeout, timeval;
452 timeout.tv_sec = Conf::config.getMutexSecs();
453 timeout.tv_usec = Conf::config.getMutexUSecs();
454 int tries=0;
455 int totalTries = Conf::config.getMutexRetries() *2;
456 int ret =0;
457 while (tries < totalTries)
459 ret = 0;
460 if (isX)
461 ret = node->mutex_.getExclusiveLock(procSlot,true);
462 else
463 ret = node->mutex_.getShareLock(procSlot,true);
464 if (ret == 0) break;
465 timeval.tv_sec = timeout.tv_sec;
466 timeval.tv_usec = timeout.tv_usec;
467 os::select(0, 0, 0, 0, &timeval);
468 tries++;
470 if (tries >= totalTries) return ErrLockTimeOut;
471 return OK;
475 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
477 struct timeval timeout, timeval;
478 timeout.tv_sec = Conf::config.getMutexSecs();
479 timeout.tv_usec = Conf::config.getMutexUSecs();
480 int tries=0;
481 int totalTries = Conf::config.getMutexRetries() *2;
482 int ret =0;
483 while (tries < totalTries)
485 ret = 0;
486 ret = node->mutex_.getExclusiveLock(procSlot,true, true);
487 if (ret == 0) break;
488 timeval.tv_sec = timeout.tv_sec;
489 timeval.tv_usec = timeout.tv_usec;
490 os::select(0, 0, 0, 0, &timeval);
491 tries++;
493 if (tries >= totalTries) return ErrLockTimeOut;
494 return OK;