Trie Implementation
[csql.git] / src / storage / TupleIterator.cxx
blob4f84eb069f13278d43c845a475f7323ffc4a96c6
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<Table.h>
17 #include<Index.h>
18 #include<CatalogTables.h>
19 #include<Lock.h>
20 #include<Debug.h>
21 #include<TableImpl.h>
22 #include<PredicateImpl.h>
23 DbRetVal TupleIterator::setPlan()
25 PredicateImpl *predImpl = (PredicateImpl*) pred_;
26 if (treeIndexScan == scanType_)
28 HashIndexInfo *hIdxInfo = (HashIndexInfo*)info;
29 FieldIterator iter = hIdxInfo->idxFldList.getIterator();
30 if(iter.hasElement())
32 FieldDef *def = iter.nextElement();
33 // keyPtr = (char*)predImpl->valPtrForIndexField(def->fldName_, hIdxInfo->isUnique);
34 // op = predImpl->opForIndexField(def->fldName_);
35 keyPtr = (char*)predImpl->opAndValPtrForIndexField(def->fldName_, hIdxInfo->isUnique,op);
37 CINDEX *iptr = (CINDEX*) hIdxInfo->indexPtr;
38 TreeNode *fstNode=(TreeNode *)iptr->hashNodeChunk_;
39 if(fstNode!=NULL){
40 TreeNode *start = (TreeNode *)*((char**)((char*)fstNode + sizeof(TreeNode)));
41 tIter->set(start,(TreeNode*)iptr->hashNodeChunk_,procSlot);
42 }else{
43 tIter->set(NULL,(TreeNode*)iptr->hashNodeChunk_,procSlot);
45 tIter->setSearchKey(keyPtr, op);
46 if (hIdxInfo->isUnique) tIter->setUnique();
47 tIter->setFldOffset(hIdxInfo->fldOffset);
48 tIter->setTypeLength(hIdxInfo->type, hIdxInfo->compLength);
50 if(predImpl) predImpl->setIfNoLeftRight();
51 return OK;
53 DbRetVal TupleIterator::open()
55 PredicateImpl *predImpl = (PredicateImpl*) pred_;
56 if (fullTableScan == scanType_)
58 *cIter = ((Chunk*)chunkPtr_)->getIterator();
59 }else if (hashIndexScan == scanType_)
61 HashIndexInfo *hIdxInfo = (HashIndexInfo*)info;
62 FieldIterator iter = hIdxInfo->idxFldList.getIterator();
63 int offset = hIdxInfo->fldOffset;
64 if(!keyBuffer) keyBuffer = (char*) malloc(hIdxInfo->compLength);
65 void *keyPtr = NULL;
66 char *keyBufferIter = keyBuffer;
67 while(iter.hasElement())
69 FieldDef *def = iter.nextElement();
70 //keyPtr = (void*)predImpl->valPtrForIndexField(def->fldName_,hIdxInfo->isUnique);
71 //TODO::PRABA::the below opt should be done for hash also
72 keyPtr = (void*)predImpl->valPtrForIndexField(def->fldName_,false);
73 if (NULL == keyPtr) {
74 printError(ErrSysFatal, "Fatal: Should not come here");
75 continue;
77 AllDataType::copyVal(keyBufferIter, keyPtr, def->type_, def->length_);
78 keyBufferIter = keyBufferIter + def->length_;
80 int bucketNo = HashIndex::computeHashBucket(hIdxInfo->type,
81 keyBuffer, hIdxInfo->noOfBuckets, hIdxInfo->compLength);
82 Bucket *bucket = &(hIdxInfo->buckets[bucketNo]);
83 IndexNode *head = (IndexNode*) bucket->bucketList_;
84 if (!head)
86 bIter->setHead(head);
87 return OK;
89 printDebug(DM_HashIndex, "open:head for bucket %x is :%x", bucket, head);
90 bIter->setHead(head);
91 }else if (trieIndexScan == scanType_)
93 HashIndexInfo *indInfo = (HashIndexInfo*)info;
94 char hashValue[TRIE_MAX_LENGTH];
95 FieldIterator iter = indInfo->idxFldList.getIterator();
96 FieldDef *def = iter.nextElement();
97 void* keyPtr = (void*)predImpl->valPtrForIndexField(def->fldName_,false);
98 if (NULL == keyPtr) {
99 printError(ErrSysFatal, "Fatal: Should not come here");
101 TrieIndex::computeHashValues(indInfo->type, keyPtr, hashValue, indInfo->compLength);
102 TrieNode* start = (TrieNode*)indInfo->buckets;
103 if (NULL == start)
105 bIter->setHead(NULL);
106 return OK;
108 char **next = NULL;
109 int cnt = 0;
110 while(-1 != hashValue[cnt+1]) {
111 next = (char**)&(start->next_[hashValue[cnt]]);
112 if (! *next)
114 printError(ErrNotFound, "No trie node found \n");
115 return ErrNotFound;
117 //traverse till the end
118 start = (TrieNode*) *next;
119 cnt++;
121 void **ptr = (void**)&(start->head_[hashValue[cnt]]);
122 IndexNode *head = (IndexNode*) *ptr;
123 if (!head)
125 bIter->setHead(head);
126 return OK;
128 bIter->setHead(head);
130 }else if (treeIndexScan == scanType_)
132 HashIndexInfo *hIdxInfo = (HashIndexInfo*)info;
133 CINDEX *iptr = (CINDEX*) hIdxInfo->indexPtr;
134 TreeNode *fstNode=(TreeNode *)iptr->hashNodeChunk_;
135 if(fstNode!=NULL){
136 TreeNode *start = (TreeNode *)*((char**)((char*)fstNode + sizeof(TreeNode)));
137 tIter->set(start,(TreeNode*)iptr->hashNodeChunk_,procSlot);
138 }else{
139 tIter->set(NULL,(TreeNode*)iptr->hashNodeChunk_,procSlot);
141 if (hIdxInfo->isUnique) tIter->setUnique();
143 isClosed = false;
144 return OK;
147 //not returing previous tuple for all iterators and for tree iterator.
148 //it just decrements the nodeOffset for tree iterator.
149 void* TupleIterator::prev()
151 PredicateImpl *predImpl = (PredicateImpl*) pred_;
152 void *tuple = NULL;
153 if (treeIndexScan == scanType_)
155 if (NULL == tIter) return NULL;
156 tuple = tIter->prev();
157 predImpl->setTuple(tuple);
158 if(NULL == tuple) {
159 printDebug(DM_HashIndex, "prev::tuple is null");
161 //TODO::evaluate as it is done in next() before returning
163 return tuple;
166 void* TupleIterator::next()
168 PredicateImpl *predImpl = (PredicateImpl*) pred_;
169 void *tuple = NULL;
170 DbRetVal rv = OK;
171 if (fullTableScan == scanType_)
173 if (NULL == pred_)
175 //no predicates
176 return cIter->nextElement();
178 else
180 int offset=0;
181 bool isLargeSizeAllocator = cIter->isLargeSize();
182 void *val = predImpl->getValIfPointLookupOnInt(offset);
183 char *tup = NULL;
184 if (val != NULL) {
185 int value = *(int*)val;
186 if (isLargeSizeAllocator) {
187 while (true)
189 tup = (char*)cIter->nextElement();
190 if(NULL == tup) return NULL;
191 if (value == *((int*)(tup+offset))) break;
193 return tup;
194 }else {
195 tup = (char*)cIter->nextElementIntMatch(value, offset);
196 return tup;
199 val = predImpl->getVal1IfBetweenOnInt(offset);
200 if (val != NULL) {
201 void *val2 = predImpl->getVal2IfBetweenOnInt(offset);
202 int value1 = *(int*)val;
203 int value2 = *(int*)val2;
204 while (true)
206 if(isLargeSizeAllocator)
207 tup = (char*)cIter->nextElement();
208 else
209 tup = (char*)cIter->nextElementInt();
210 if(NULL == tup) return NULL;
211 if (*((int*)(tup+offset)) >= value1 &&
212 *((int*)(tup+offset)) <= value2) break;
214 return tup;
217 //evaluate till it succeeds
218 bool result = false;
219 while (!result)
221 if(isLargeSizeAllocator)
222 tuple = cIter->nextElement();
223 else
224 tuple = cIter->nextElementInt();
225 if(NULL == tuple) return NULL;
226 //predImpl->setTuple(tuple);
227 printDebug(DM_Table, "Evaluating the predicate from fullTableScan");
228 predImpl->evaluateForTable(result, (char*)tuple);
231 }else if (hashIndexScan == scanType_ || trieIndexScan == scanType_)
233 //evaluate till it succeeds
234 bool result = false;
235 while (!result)
237 IndexNode *node = bIter->next();
238 if (node == NULL) return NULL;
239 printDebug(DM_HashIndex, "next: returned IndexNode: %x", node);
240 tuple = node->ptrToTuple_;
241 if(NULL == tuple) {
242 printDebug(DM_HashIndex, "next::tuple is null");
243 return NULL;
246 //if (!predImpl->isSingleTerm()) {
247 printDebug(DM_HashIndex, "next: predicate has more than single term");
248 //predImpl->setTuple(tuple);
249 printDebug(DM_Table, "Evaluating the predicate from hashIndexScan: has more than one term");
250 predImpl->evaluateForTable(result, (char*)tuple);
251 //}
252 //else
253 // return tuple;
256 }else if (treeIndexScan == scanType_)
258 if (NULL == tIter) return NULL;
259 bool result = false;
260 while (!result)
262 tuple = tIter->next();
263 if(NULL == tuple) {
264 printDebug(DM_HashIndex, "next::tuple is null");
265 return NULL;
267 //predImpl->setTuple(tuple);
268 predImpl->evaluateForTable(result, (char*)tuple);
269 if(!result && (isBetween || isPointLook)) tIter->nextNode();
272 return tuple;
275 DbRetVal TupleIterator::close()
277 if (isClosed) return OK;
278 reset();
279 isClosed = true;
280 return OK;
283 void TupleIterator::reset()
285 DbRetVal rv = OK;
286 if (scanType_ == fullTableScan) {
287 if (cIter) *cIter = ((Chunk*)chunkPtr_)->getIterator();
289 else if (scanType_ == hashIndexScan) {
290 if(bIter) bIter->reset();
292 else if (scanType_ == treeIndexScan) { if(tIter) tIter->reset(); }