code reorg
[csql.git] / src / relational / index / TreeIter.cxx
blobaea8be10fcb4b0b7f69ba4893a39330278485fcd
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;
68 void TreeIter::nextNode()
70 if (recordsOver) return ;
71 if (NULL == iter) return ;
72 TreeNode *tmpIter = iter;
73 iter = iter->next_;
74 if(iter){
75 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
76 if (OK != ret)
78 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
79 tmpIter->mutex_.releaseShareLock(procSlot);
80 return ;
83 tmpIter->mutex_.releaseShareLock(procSlot);
84 nodeOffset=0;
87 void TreeIter::reset()
89 if(iter && !firstCall) iter->mutex_.releaseShareLock(procSlot);
90 firstCall = true;
91 recordsOver=false;
92 iter = head;
95 void* TreeIter::next()
97 int direction=0;
98 if (recordsOver){
99 if(iter) iter->mutex_.releaseShareLock(procSlot);
100 iter = NULL;
101 return NULL;
103 if (NULL== iter) return NULL;
104 if (firstCall)
106 if (OpLessThan ==op || OpLessThanEquals == op)
108 nodeOffset = 1;
109 firstCall = false;
110 char **rec = (char**)((char*) iter + sizeof(TreeNode));
111 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
112 if (OK != ret)
114 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
115 return NULL;
117 //iter->displayAll(fldOffset);
118 return *rec;
120 else if (OpGreaterThan == op)
122 char *rec = (char*)locateNode();
123 firstCall = false;
124 if(rec){
125 bool result = AllDataType::compareVal(searchKey, rec+fldOffset,
126 OpEquals, type, length);
127 //equals comparision does not apply to float and double
128 if (result || type==typeFloat || type == typeDouble) return next();
130 return rec;
131 }else if (OpGreaterThanEquals == op)
133 void *rec = locateNode();
134 firstCall = false;
135 return rec;
136 }else if (OpEquals == op)
138 void *rec = locateNode();
139 firstCall = false;
140 if(isUnique) recordsOver = true;
141 return rec;
143 //firstCall = false;
144 }else
146 if (nodeOffset == iter->noElements_)
148 if (NULL == iter->next_) {
149 recordsOver = true;
150 iter->mutex_.releaseShareLock(procSlot);
151 iter = NULL;
152 return NULL;
154 char* record = ((char*)iter->next_->min_)+ fldOffset;
155 bool result = AllDataType::compareVal(searchKey, record,
156 OpGreaterThanEquals,
157 type, length);
158 if (!result && (OpLessThan ==op || OpLessThanEquals == op))
160 //Case: search key 10 , next node first record is 20
161 //condition is < or <=
162 recordsOver= true;
163 iter->mutex_.releaseShareLock(procSlot);
164 iter = NULL;
165 return NULL;
166 }else if (result && (OpGreaterThan == op ||
167 OpGreaterThanEquals == op))
169 //Case: search key 20 , next node first record is 10
170 //condition is > or >=
171 recordsOver= true;
172 iter->mutex_.releaseShareLock(procSlot);
173 iter = NULL;
174 return NULL;
176 TreeNode *tmpIter = iter;
177 iter = iter->next_;
178 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
179 if (OK != ret)
181 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
182 tmpIter->mutex_.releaseShareLock(procSlot);
183 iter = NULL;
184 return NULL;
186 tmpIter->mutex_.releaseShareLock(procSlot);
187 printDebug(DM_TreeIndex,"\n Moving Node next");
188 nodeOffset=0;
190 char **rec = (char**)((char*)iter + sizeof(TreeNode));
191 rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
192 nodeOffset++;
193 //TEMP::UNCOMMENT THIS if any issue
194 /*if(NULL==(*rec))
195 iter->mutex_.releaseShareLock(procSlot);
197 return *rec;
199 return NULL;
202 void* TreeIter::locateNode()
204 TreeNode *tnode=NULL;
205 TreeNode *fiter= (TreeNode *)fstLTnode;
206 DbRetVal ret=OK;
207 ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
208 if (OK != ret)
210 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
211 return NULL;
213 while( fiter!= NULL)
215 printDebug(DM_TreeIndex,"\n Search in first level start");
216 tnode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ ((fiter->noElements_-1)*sizeof(void *))));
217 char *record = ((char*)tnode->max_)+ fldOffset;
218 bool result = AllDataType::compareVal(searchKey, record,OpLessThanEquals,type, length);
219 if (result)
221 break;
222 }else
224 printDebug(DM_TreeIndex,"\n Search in first level next");
225 TreeNode* tmpIter = fiter;
226 if(fiter->next_!= NULL){
227 fiter = fiter->next_;
228 ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
229 if (OK != ret)
231 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
232 tmpIter->mutex_.releaseShareLock(procSlot);
233 iter = NULL;
234 return NULL;
236 tmpIter->mutex_.releaseShareLock(procSlot);
237 }else{
238 tmpIter->mutex_.releaseShareLock(procSlot);
239 fiter = NULL;
243 if(fiter == NULL)
245 iter = NULL;
246 return NULL;
248 //Get leaf Node
250 int loc=0, middle=0, start=0, end=fiter->noElements_-1;
251 char **rec = (char**)((char*)fiter + sizeof(TreeNode));
252 TreeNode *tNode;
253 if(fiter->noElements_==1)
255 tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
256 iter = tNode;
257 fiter->mutex_.releaseShareLock(procSlot);
258 void *rec1 = locateElement();
259 return rec1;
261 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
263 loc = middle;
264 tNode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ (loc*sizeof(void *))));
265 char *record = ((char*)tNode->max_)+ fldOffset;
267 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
268 type, length);
269 if(res)
271 end = middle - 1;
273 else
275 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
276 type, length);
277 if (res) {
278 start = middle + 1;
279 loc = start;
280 }else {
281 loc = middle;
282 break;
286 printDebug(DM_TreeIndex,"\n Search in fisrt level end loc =%d\n",loc);
287 tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
288 iter = tNode;
289 fiter->mutex_.releaseShareLock(procSlot);
290 void *rec1 = locateElement();
291 return rec1;
294 void* TreeIter::locateElement()
296 //do binary search and locate the element
297 int loc=0, middle=0, start=0, end=iter->noElements_-1;
298 char **rec = (char**)((char*)iter + sizeof(TreeNode));
299 DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
300 if (OK != ret)
302 printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
303 return NULL;
305 for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
307 loc = middle;
308 char *record = ((char*)*(rec+middle)) + fldOffset;
309 bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
310 type, length);
311 if(res)
313 end = middle - 1;
315 else
317 res = AllDataType::compareVal(searchKey, record, OpGreaterThan,
318 type, length);
319 if (res) {
320 start = middle + 1;
321 loc = start;
322 }else {
323 loc = middle;
324 break;
328 nodeOffset=loc;
329 char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
330 nodeOffset++;
331 //iter->mutex_.releaseShareLock(procSlot);
332 return *tuple;