code reorg
[csql.git] / src / storage / TreeIndex.cxx
blob140dfdc1fd67d8659c235b28dd2a9d69645c4edb
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;
76 DbRetVal TreeIndex::insertLogicalUndoLog(Database *sysdb, void *data)
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)
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)
104 printError(rc, "Exit TreeNode::Insert - 1 tnode=NULL");
105 delete info;
106 return rc;
108 tnode->mutex_.init("TNODE-R");
109 tnode->min_ = tUndoInfo->tuple_;
110 tnode->max_ = tUndoInfo->tuple_;
111 tnode->noElements_ =1;
112 tnode->next_ = NULL;
113 tnode->prev_ = NULL;
114 tnode->balance_ = 0;
115 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
116 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
117 *rec = (char*) tUndoInfo->tuple_;
119 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
120 Chunk *ftchunk = (Chunk*) iptr->chunkPtr_;
121 TreeNode *ftnode = (TreeNode*) ftchunk->allocate(db, &rc);
122 if (NULL == ftnode)
124 printError(rc, "Unable to allocate tree node");
125 chunk->free(db, tnode);
126 delete info;
127 return rc;
129 ftnode->mutex_.init("TNODE-I");
130 ftnode->min_= NULL;
131 ftnode->max_ = NULL;
132 ftnode->noElements_ =1;
133 ftnode->next_ = NULL;
134 ftnode->prev_ = NULL;
135 ftnode->balance_ = 0;
136 char **tn=(char**)((char*) ftnode+sizeof(TreeNode));
137 *tn = (char*)tnode;
138 //iptr->hashNodeChunk_ = ftnode;
139 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
141 printError(ErrLockTimeOut, "Lock timeout..retry");
142 chunk->free(db, tnode);
143 chunk->free(db, ftnode);
144 delete info;
145 return ErrLockTimeOut;
147 }else {
148 rc = start->insert(db, info, iptr, tUndoInfo->tuple_);
149 if (rc != OK){
150 delete db; delete info;
151 printError(rc, "Error in tree node insertion\n");
152 return rc;
155 delete db;
156 delete info;
157 return rc;
160 DbRetVal TreeIndex::insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
162 HashIndexInfo *info = (HashIndexInfo*) indInfo;
163 CINDEX *iptr = (CINDEX*)indexPtr;
164 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
165 DbRetVal rc = OK;
166 int offset = info->fldOffset;
167 DataType type = info->type;
168 void *keyPtr =(void*)((char*)tuple + offset);
169 //TreeUndoLogInfo Populated here
170 TreeUndoLogInfo hInfo;
171 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
172 hInfo.tuple_ = tuple;
173 hInfo.cIndex_= indexPtr;
174 if (start == NULL)
176 printDebug(DM_TreeIndex, "Inside if - start=NULL create First level ");
177 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
178 TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
179 if (tnode == NULL)
181 printError(rc, "Unable to allocate tree node");
182 return rc;
184 tnode->mutex_.init("TNODE-R");
185 tnode->min_ = tuple;
186 tnode->max_ = tuple;
187 tnode->noElements_ =1;
188 tnode->next_ = NULL;
189 tnode->prev_ = NULL;
190 tnode->balance_ = 0;
191 char **rec = (char**)((char*) tnode + sizeof(TreeNode));
192 //printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
193 *rec = (char*) tuple;
195 printDebug(DM_TreeIndex, "Inside if - start=NULL create second level ");
196 TreeNode *ftnode = (TreeNode*) chunk->allocate(tbl->db_, &rc);
197 if (NULL == ftnode)
199 printError(rc, "Unable to allocate tree node");
200 chunk->free(tbl->db_, tnode);
201 return rc;
203 ftnode->mutex_.init("TNODE-I");
204 ftnode->min_= NULL;
205 ftnode->max_ = NULL;
206 ftnode->noElements_ =1;
207 ftnode->next_ = NULL;
208 ftnode->prev_ = NULL;
209 ftnode->balance_ = 0;
210 //TODO: Handle when two process try to allocate first node
211 char **tn=(char**)((char*) ftnode + sizeof(TreeNode));
212 *tn = (char*)tnode;
213 if( 0 !=Mutex::CASL((long*)&iptr->hashNodeChunk_, 0, (long)ftnode))
215 printError(ErrLockTimeOut, "Lock timeout..retry");
216 chunk->free(tbl->db_, tnode);
217 chunk->free(tbl->db_, ftnode);
218 return ErrLockTimeOut;
221 }else {
222 rc = start->insert(tbl->db_, indInfo, indexPtr, tuple);
223 if (rc != OK){
224 printError(rc, "Error in tree node insertion for tuple %x", tuple);
225 return rc;
228 //start->displayAll(offset);
229 if(!undoFlag){
230 rc = tr->appendLogicalTreeUndoLog(tbl->sysDB_, InsertTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
231 if (rc !=OK)
233 //Reverse back
234 int pos=0;
235 start = (TreeNode*) iptr->hashNodeChunk_;
236 TreeNode *fltnode = start->locateNode(tbl->sysDB_,start, tuple, indInfo,rc);
237 if (NULL == fltnode)
239 return rc;
240 } //First Level Node Not found
241 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
242 if (NULL == iter){
243 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
244 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
245 return OK;
246 } //element not found
247 rc = removeElement(tbl->getDB(), iter, tuple, info);
248 if( rc != OK )
250 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
251 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
252 printError(rc, "Romove from TreeNode Failed ");
253 return rc;
255 if(0 == iter->noElements_)
257 removeNode(tbl->getDB(), indexPtr, fltnode,iter, pos);
258 }else
260 fltnode->mutex_.releaseShareLock(tbl->sysDB_->procSlot);
261 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
264 printError(ErrSysFatal, "Unable to append undo lock for TreeInsert\n");
265 return rc;
269 return rc;
273 DbRetVal TreeIndex::remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
275 DbRetVal rc = OK;
276 HashIndexInfo *info = (HashIndexInfo*) indInfo;
277 CINDEX *iptr = (CINDEX*)indexPtr;
278 TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
279 int pos=0;
280 TreeNode *fltnode = start->locateNode(tbl->getDB(),start, tuple, indInfo,rc);
281 if (NULL == fltnode) return rc; //First Level Node Not found
282 TreeNode *iter = start->locateNodeFromFirstLevel(fltnode, indInfo, tuple, &pos);
283 if (NULL == iter) {
284 //element not found
285 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
286 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
287 return OK;
289 rc = removeElement(tbl->getDB(), iter, tuple, info);
290 if( rc != OK ){
291 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
292 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
293 printError(rc, "Remove from TreeNode Failed");
294 return rc;
296 if(0 == iter->noElements_)
298 removeNode(tbl->getDB(), indexPtr, fltnode, iter, pos);
299 }else
301 fltnode->mutex_.releaseShareLock((tbl->getDB())->procSlot);
302 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
304 TreeUndoLogInfo hInfo;
305 hInfo.metaData_ = tbl->db_->getMetaDataPtr();
306 hInfo.tuple_ = tuple;
307 hInfo.cIndex_= indexPtr;
308 if (!undoFlag) {
309 rc =tr->appendLogicalTreeUndoLog(tbl->sysDB_, DeleteTreeIndexOperation, &hInfo, sizeof(TreeUndoLogInfo));
310 if( rc != OK){
311 //Reverse back
312 //Currently nodes are not freed
313 rc = start->insert(tbl->db_, info, iptr, tuple);
314 if (rc != OK){ printError(ErrSysFatal, "double failure on undo log remove followed by tree insert\n");}
315 printError(ErrSysFatal, "Unable to append undo lock for TreeRemove\n");
316 return rc;
319 return rc;
321 void TreeIndex::removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos)
323 CINDEX *iptr = (CINDEX*)indexPtr;
324 char **nod = (char**)((char*)fltnode + sizeof(TreeNode));
325 char *tmp = (char *)malloc(sizeof(void *) * (fltnode->noElements_ - pos));
326 memcpy(tmp, (char*)nod + ((pos+1) * sizeof(void *)), sizeof(void *) * (fltnode->noElements_ - pos));
327 memcpy((char*)nod + ((pos) * sizeof(void *)), tmp, sizeof(void *) * (fltnode->noElements_ - pos));
328 free(tmp);
329 fltnode->noElements_--;
330 if(node->prev_!=NULL) node->prev_->next_= node->next_;
331 if(node->next_!=NULL) node->next_->prev_= node->prev_;
332 Chunk *chunk = (Chunk*) iptr->chunkPtr_;
333 chunk->free(db, node);
334 printDebug(DM_TreeIndex,"TreeNode at postion %d Freed",pos);
335 if(fltnode->noElements_== 0)
337 if(fltnode->prev_!=NULL) {
338 fltnode->prev_->next_= fltnode->next_;
340 else {
341 iptr->hashNodeChunk_ = fltnode->next_ ;
343 if(fltnode->next_!=NULL) {
344 fltnode->next_->prev_= fltnode->prev_;
346 //need discussion in the above situation to solve concureny
347 printDebug(DM_TreeIndex,"TreeNode from first level Freed");
348 fltnode->mutex_.releaseShareLock(db->procSlot);
349 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
350 chunk->free(db, fltnode);
351 }else{
352 fltnode->mutex_.releaseShareLock(db->procSlot);
353 printDebug(DM_TreeIndex," Mutex Release on %x\n",fltnode);
357 DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info)
359 void *searchKey =(void*)((char*)tuple + info->fldOffset);
360 int loc=0, middle=0, start=0, end=iter->noElements_-1;
361 char **rec = (char**)((char*)iter + sizeof(TreeNode));
362 DbRetVal ret = TreeIndex::upgradeTreeNodeMutex(iter, db->procSlot);
363 if (OK != ret) {
364 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
365 return ErrLockTimeOut;
367 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
369 loc = middle;
370 char *record = ((char*)*(rec+middle)) + info->fldOffset;
371 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
372 info->type, info->compLength);
373 if(res)
375 end = middle - 1;
377 else
379 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
380 info->type, info->compLength);
381 if (res) {
382 start = middle + 1;
383 loc = start;
384 } else {
385 loc = middle;
386 break;
390 if (loc == iter->noElements_-1)
392 iter->max_ = *(char**)((char*)rec + ((loc-1) * sizeof(void *)));
393 }else {
394 char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
395 memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)),
396 sizeof(void *) * (iter->noElements_ - loc));
397 memcpy((char*)rec + ((loc) * sizeof(void *)), tmp,
398 sizeof(void *) * (iter->noElements_ - loc));
399 free(tmp);
401 if(loc==0)
403 iter->min_ = *(char**)rec ;
405 iter->noElements_--;
406 iter->mutex_.releaseShareLock(db->procSlot);
407 return OK;
411 DbRetVal TreeIndex::update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *indInfo, void *tuple, bool undoFlag)
413 CINDEX *iptr = (CINDEX*)indexPtr;
415 HashIndexInfo *info = (HashIndexInfo*) indInfo;
416 //check whether the index key is updated or not
417 //if it is not updated return from here
418 bool keyNotUpdated = false;
419 FieldIterator idxFldIter = info->idxFldList.getIterator();
420 while (idxFldIter.hasElement())
422 FieldDef *idef = idxFldIter.nextElement();
423 FieldIterator fldIter = tbl->fldList_.getIterator();
424 while (fldIter.hasElement())
426 FieldDef *def = fldIter.nextElement();
427 if (0 == strcmp(def->fldName_, idef->fldName_))
429 if (NULL != def->bindVal_)
431 //Not Implemented
432 return ErrNotYet;
434 keyNotUpdated = true;
435 break;
439 if (keyNotUpdated)
441 return OK;
443 return ErrNotYet;
446 DbRetVal TreeIndex::getTreeNodeMutex(TreeNode *node, int procSlot, bool isX)
448 struct timeval timeout, timeval;
449 timeout.tv_sec = Conf::config.getMutexSecs();
450 timeout.tv_usec = Conf::config.getMutexUSecs();
451 int tries=0;
452 int totalTries = Conf::config.getMutexRetries() *2;
453 int ret =0;
454 while (tries < totalTries)
456 ret = 0;
457 if (isX)
458 ret = node->mutex_.getExclusiveLock(procSlot,true);
459 else
460 ret = node->mutex_.getShareLock(procSlot,true);
461 if (ret == 0) break;
462 timeval.tv_sec = timeout.tv_sec;
463 timeval.tv_usec = timeout.tv_usec;
464 os::select(0, 0, 0, 0, &timeval);
465 tries++;
467 if (tries >= totalTries) return ErrLockTimeOut;
468 return OK;
471 DbRetVal TreeIndex::upgradeTreeNodeMutex(TreeNode *node, int procSlot)
473 struct timeval timeout, timeval;
474 timeout.tv_sec = Conf::config.getMutexSecs();
475 timeout.tv_usec = Conf::config.getMutexUSecs();
476 int tries=0;
477 int totalTries = Conf::config.getMutexRetries() *2;
478 int ret =0;
479 while (tries < totalTries)
481 ret = 0;
482 ret = node->mutex_.getExclusiveLock(procSlot,true, true);
483 if (ret == 0) break;
484 timeval.tv_sec = timeout.tv_sec;
485 timeval.tv_usec = timeout.tv_usec;
486 os::select(0, 0, 0, 0, &timeval);
487 tries++;
489 if (tries >= totalTries) return ErrLockTimeOut;
490 return OK;