fix for trie index
[csql.git] / src / storage / TreeIter.cxx
blobcea11481cd421897bf17bb02663b7112766bd226
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<Debug.h>
19 void* TreeIter::getFirstElement()
21 if (NULL == iter) return NULL;
22 TreeNode *node = iter;
23 while(node != NULL) {
24 if(NULL == node->prev_) break;
25 node = node->prev_;
27 if (node == NULL) printf("Node returned is NULL\n");
28 if (0 == node->noElements_) return NULL;
29 char **rec = (char**)((char*)node + sizeof(TreeNode));
30 int loc = 0; //first element
31 char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
32 return *tuple;
35 void* TreeIter::getLastElement()
37 if (NULL == iter) return NULL;
38 TreeNode *node = iter;
39 while(node != NULL ) {
40 if(NULL == node->next_) break;
41 node = node->next_;
43 if (node == NULL) printf("Node returned is NULL\n");
44 if (0 == node->noElements_) return NULL;
45 char **rec = (char**)((char*)node + sizeof(TreeNode));
46 int loc = node->noElements_-1; //last element
47 char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
48 return *tuple;
51 void* TreeIter::prev()
53 if (0 != nodeOffset )
55 nodeOffset--;
57 }else
59 iter=iter->prev_;
60 if (NULL == iter) return NULL;
61 nodeOffset = iter->noElements_;
63 char **rec = (char**)((char*)iter + sizeof(TreeNode));
64 rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
65 return *rec;
67 void TreeIter::nextNode()
69 if (recordsOver) return ;
70 if (NULL == iter) return ;
71 TreeNode *tmpIter = iter;
72 iter = iter->next_;
73 if(iter){
74 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
75 if (OK != ret)
77 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
78 tmpIter->mutex_.releaseShareLock(procSlot);
79 return ;
82 tmpIter->mutex_.releaseShareLock(procSlot);
83 nodeOffset=0;
86 void TreeIter::reset()
88 if(iter && !firstCall) iter->mutex_.releaseShareLock(procSlot);
89 firstCall = true;
90 recordsOver=false;
91 iter = head;
94 void* TreeIter::next()
96 int direction=0;
97 if (recordsOver){
98 if(iter) iter->mutex_.releaseShareLock(procSlot);
99 iter = NULL;
100 return NULL;
102 if (NULL== iter) return NULL;
103 if (firstCall)
105 if (OpLessThan ==op || OpLessThanEquals == op)
107 nodeOffset = 1;
108 firstCall = false;
109 char **rec = (char**)((char*) iter + sizeof(TreeNode));
110 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
111 if (OK != ret)
113 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
114 return NULL;
116 //iter->displayAll(fldOffset);
117 return *rec;
119 else if (OpGreaterThan == op)
121 char *rec = (char*)locateNode();
122 firstCall = false;
123 if(rec){
124 bool result = AllDataType::compareVal(searchKey, rec+fldOffset,
125 OpEquals, type, length);
126 //equals comparision does not apply to float and double
127 if (result || type==typeFloat || type == typeDouble) return next();
129 return rec;
130 }else if (OpGreaterThanEquals == op)
132 void *rec = locateNode();
133 firstCall = false;
134 return rec;
135 }else if (OpEquals == op)
137 void *rec = locateNode();
138 firstCall = false;
139 if(isUnique) recordsOver = true;
140 return rec;
142 //firstCall = false;
143 }else
145 if (nodeOffset == iter->noElements_)
147 if (NULL == iter->next_) {
148 recordsOver = true;
149 iter->mutex_.releaseShareLock(procSlot);
150 iter = NULL;
151 return NULL;
153 char* record = ((char*)iter->next_->min_)+ fldOffset;
154 bool result = AllDataType::compareVal(searchKey, record,
155 OpGreaterThanEquals,
156 type, length);
157 if (!result && (OpLessThan ==op || OpLessThanEquals == op))
159 //Case: search key 10 , next node first record is 20
160 //condition is < or <=
161 recordsOver= true;
162 iter->mutex_.releaseShareLock(procSlot);
163 iter = NULL;
164 return NULL;
165 }else if (result && (OpGreaterThan == op ||
166 OpGreaterThanEquals == op))
168 //Case: search key 20 , next node first record is 10
169 //condition is > or >=
170 recordsOver= true;
171 iter->mutex_.releaseShareLock(procSlot);
172 iter = NULL;
173 return NULL;
175 TreeNode *tmpIter = iter;
176 iter = iter->next_;
177 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
178 if (OK != ret)
180 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
181 tmpIter->mutex_.releaseShareLock(procSlot);
182 iter = NULL;
183 return NULL;
185 tmpIter->mutex_.releaseShareLock(procSlot);
186 printDebug(DM_TreeIndex,"\n Moving Node next");
187 nodeOffset=0;
189 char **rec = (char**)((char*)iter + sizeof(TreeNode));
190 rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
191 nodeOffset++;
192 //TEMP::UNCOMMENT THIS if any issue
193 /*if(NULL==(*rec))
194 iter->mutex_.releaseShareLock(procSlot);
196 return *rec;
198 return NULL;
200 void* TreeIter::locateNode()
202 TreeNode *tnode=NULL;
203 TreeNode *fiter= (TreeNode *)fstLTnode;
204 DbRetVal ret=OK;
205 ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
206 if (OK != ret)
208 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
209 return NULL;
211 while( fiter!= NULL)
213 printDebug(DM_TreeIndex,"\n Search in first level start");
214 tnode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ ((fiter->noElements_-1)*sizeof(void *))));
215 char *record = ((char*)tnode->max_)+ fldOffset;
216 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,type, length);
217 if (result)
219 break;
220 }else
222 printDebug(DM_TreeIndex,"\n Search in first level next");
223 TreeNode* tmpIter = fiter;
224 if(fiter->next_!= NULL){
225 fiter = fiter->next_;
226 ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
227 if (OK != ret)
229 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
230 tmpIter->mutex_.releaseShareLock(procSlot);
231 iter = NULL;
232 return NULL;
234 tmpIter->mutex_.releaseShareLock(procSlot);
235 }else{
236 tmpIter->mutex_.releaseShareLock(procSlot);
237 fiter = NULL;
241 if(fiter == NULL)
243 iter = NULL;
244 return NULL;
246 //Get leaf Node
248 int loc=0, middle=0, start=0, end=fiter->noElements_-1;
249 char **rec = (char**)((char*)fiter + sizeof(TreeNode));
250 TreeNode *tNode;
251 if(fiter->noElements_==1)
253 tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
254 iter = tNode;
255 fiter->mutex_.releaseShareLock(procSlot);
256 void *rec1 = locateElement();
257 return rec1;
259 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
261 loc = middle;
262 tNode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ (loc*sizeof(void *))));
263 char *record = ((char*)tNode->max_)+ fldOffset;
265 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
266 type, length);
267 if(res)
269 end = middle - 1;
271 else
273 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
274 type, length);
275 if (res) {
276 start = middle + 1;
277 loc = start;
278 }else {
279 loc = middle;
280 break;
284 printDebug(DM_TreeIndex,"\n Search in fisrt level end loc =%d\n",loc);
285 tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
286 iter = tNode;
287 fiter->mutex_.releaseShareLock(procSlot);
288 void *rec1 = locateElement();
289 return rec1;
292 void* TreeIter::locateElement()
294 //do binary search and locate the element
295 int loc=0, middle=0, start=0, end=iter->noElements_-1;
296 char **rec = (char**)((char*)iter + sizeof(TreeNode));
297 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
298 if (OK != ret)
300 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
301 return NULL;
303 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
305 loc = middle;
306 char *record = ((char*)*(rec+middle)) + fldOffset;
307 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
308 type, length);
309 if(res)
311 end = middle - 1;
313 else
315 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
316 type, length);
317 if (res) {
318 start = middle + 1;
319 loc = start;
320 }else {
321 loc = middle;
322 break;
326 nodeOffset=loc;
327 char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
328 nodeOffset++;
329 //iter->mutex_.releaseShareLock(procSlot);
330 return *tuple;