src/relational/index/TreeIter.cxx

   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>
  18
  19 void* TreeIter::getFirstElement()
  20 {
  21    if (NULL == iter) return NULL;
  22    TreeNode *node = iter;
  23    while(node != NULL) {
  24       if(NULL == node->prev_)  break;
  25       node = node->prev_;
  26    }
  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;
  33 }
  34
  35 void* TreeIter::getLastElement()
  36 {
  37    if (NULL == iter) return NULL;
  38    TreeNode *node = iter;
  39    while(node != NULL ) {
  40       if(NULL == node->next_)  break;
  41       node = node->next_;
  42    }
  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;
  49 }
  50
  51 void* TreeIter::prev()
  52 {
  53    if (0 != nodeOffset )
  54    {
  55        nodeOffset--;
  56
  57    }else
  58    {
  59        iter=iter->prev_;
  60        if (NULL == iter) return NULL;
  61        nodeOffset = iter->noElements_;
  62    }
  63    char **rec = (char**)((char*)iter + sizeof(TreeNode));
  64    rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
  65    return *rec;
  66 }
  67
  68 void TreeIter::nextNode()
  69 {
  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)
  77         {
  78              printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
  79              tmpIter->mutex_.releaseShareLock(procSlot);
  80              return ;
  81         }
  82     }
  83     tmpIter->mutex_.releaseShareLock(procSlot);
  84     nodeOffset=0;
  85 }
  86
  87 void TreeIter::reset()
  88 {
  89     if(iter && !firstCall) iter->mutex_.releaseShareLock(procSlot);
  90     firstCall = true;
  91     recordsOver=false;
  92     iter = head;
  93 }
  94
  95 void* TreeIter::next()
  96 {
  97     int direction=0;
  98     if (recordsOver){
  99        if(iter) iter->mutex_.releaseShareLock(procSlot);
 100        iter = NULL;
 101        return NULL;
 102     }
 103     if (NULL== iter) return NULL;
 104     if (firstCall)
 105     {
 106         if (OpLessThan ==op || OpLessThanEquals == op)
 107         {
 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)
 113             {
 114                printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 115                return NULL;
 116             }
 117             //iter->displayAll(fldOffset);
 118             return *rec;
 119         }
 120         else if (OpGreaterThan == op)
 121         {
 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();
 129             }
 130             return rec;
 131         }else if (OpGreaterThanEquals == op)
 132         {
 133             void *rec = locateNode();
 134             firstCall = false;
 135             return rec;
 136         }else if (OpEquals == op)
 137         {
 138             void *rec = locateNode();
 139             firstCall = false;
 140             if(isUnique) recordsOver = true;
 141             return rec;
 142         }
 143         //firstCall = false;
 144     }else
 145     {
 146         if (nodeOffset == iter->noElements_)
 147         {
 148             if (NULL == iter->next_) {
 149                 recordsOver = true;
 150                 iter->mutex_.releaseShareLock(procSlot);
 151                 iter = NULL;
 152                 return NULL;
 153             }
 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))
 159             {
 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))
 168             {
 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;
 175             }
 176             TreeNode *tmpIter = iter;
 177             iter = iter->next_;
 178             DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
 179             if (OK != ret)
 180             {
 181                printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 182                tmpIter->mutex_.releaseShareLock(procSlot);
 183                iter = NULL;
 184                return NULL;
 185             }
 186             tmpIter->mutex_.releaseShareLock(procSlot);
 187             printDebug(DM_TreeIndex,"\n Moving Node next");
 188             nodeOffset=0;
 189         }
 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);
 196         */
 197         return *rec;
 198     }
 199     return NULL;
 200 }
 201
 202 void* TreeIter::locateNode()
 203 {
 204     TreeNode *tnode=NULL;
 205     TreeNode *fiter= (TreeNode *)fstLTnode;
 206     DbRetVal  ret=OK;
 207     ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
 208     if (OK != ret)
 209     {
 210         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 211         return NULL;
 212     }
 213     while( fiter!= NULL)
 214     {
 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)
 220         {
 221             break;
 222         }else
 223         {
 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)
 230                {
 231                    printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 232                    tmpIter->mutex_.releaseShareLock(procSlot);
 233                    iter = NULL;
 234                    return NULL;
 235                }
 236                tmpIter->mutex_.releaseShareLock(procSlot);
 237             }else{
 238                tmpIter->mutex_.releaseShareLock(procSlot);
 239                fiter = NULL;
 240             }
 241         }
 242     }
 243     if(fiter == NULL)
 244     {
 245         iter = NULL;
 246         return NULL;
 247     }
 248     //Get leaf Node
 249
 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)
 254    {
 255         tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
 256         iter = tNode;
 257         fiter->mutex_.releaseShareLock(procSlot);
 258         void *rec1 = locateElement();
 259         return rec1;
 260    }
 261    for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 262     {
 263         loc = middle;
 264         tNode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ (loc*sizeof(void *))));
 265         char *record = ((char*)tNode->max_)+ fldOffset;
 266
 267         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
 268                                            type, length);
 269         if(res)
 270         {
 271             end = middle - 1;
 272         }
 273         else
 274         {
 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;
 283             }
 284         }
 285     }
 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;
 292 }
 293
 294 void* TreeIter::locateElement()
 295 {
 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)
 301     {
 302         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 303         return NULL;
 304     }
 305     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 306     {
 307         loc = middle;
 308         char *record = ((char*)*(rec+middle)) + fldOffset;
 309         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
 310                                            type, length);
 311         if(res)
 312         {
 313             end = middle - 1;
 314         }
 315         else
 316         {
 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;
 325             }
 326         }
 327     }
 328     nodeOffset=loc;
 329     char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
 330     nodeOffset++;
 331     //iter->mutex_.releaseShareLock(procSlot);
 332     return *tuple;
 333 }