src/storage/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 void TreeIter::nextNode()
  68 {
  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)
  76         {
  77              printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
  78              tmpIter->mutex_.releaseShareLock(procSlot);
  79              return ;
  80         }
  81     }
  82     tmpIter->mutex_.releaseShareLock(procSlot);
  83     nodeOffset=0;
  84 }
  85
  86 void TreeIter::reset()
  87 {
  88     if(iter && !firstCall) iter->mutex_.releaseShareLock(procSlot);
  89     firstCall = true;
  90     recordsOver=false;
  91     iter = head;
  92 }
  93
  94 void* TreeIter::next()
  95 {
  96     int direction=0;
  97     if (recordsOver){
  98        if(iter) iter->mutex_.releaseShareLock(procSlot);
  99        iter = NULL;
 100        return NULL;
 101     }
 102     if (NULL== iter) return NULL;
 103     if (firstCall)
 104     {
 105         if (OpLessThan ==op || OpLessThanEquals == op)
 106         {
 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)
 112             {
 113                printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 114                return NULL;
 115             }
 116             //iter->displayAll(fldOffset);
 117             return *rec;
 118         }
 119         else if (OpGreaterThan == op)
 120         {
 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();
 128             }
 129             return rec;
 130         }else if (OpGreaterThanEquals == op)
 131         {
 132             void *rec = locateNode();
 133             firstCall = false;
 134             return rec;
 135         }else if (OpEquals == op)
 136         {
 137             void *rec = locateNode();
 138             firstCall = false;
 139             if(isUnique) recordsOver = true;
 140             return rec;
 141         }
 142         //firstCall = false;
 143     }else
 144     {
 145         if (nodeOffset == iter->noElements_)
 146         {
 147             if (NULL == iter->next_) {
 148                 recordsOver = true;
 149                 iter->mutex_.releaseShareLock(procSlot);
 150                 iter = NULL;
 151                 return NULL;
 152             }
 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))
 158             {
 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))
 167             {
 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;
 174             }
 175             TreeNode *tmpIter = iter;
 176             iter = iter->next_;
 177             DbRetVal ret = TreeIndex::getTreeNodeMutex(iter, procSlot);
 178             if (OK != ret)
 179             {
 180                printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 181                tmpIter->mutex_.releaseShareLock(procSlot);
 182                iter = NULL;
 183                return NULL;
 184             }
 185             tmpIter->mutex_.releaseShareLock(procSlot);
 186             printDebug(DM_TreeIndex,"\n Moving Node next");
 187             nodeOffset=0;
 188         }
 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);
 195         */
 196         return *rec;
 197     }
 198     return NULL;
 199 }
 200 void* TreeIter::locateNode()
 201 {
 202     TreeNode *tnode=NULL;
 203     TreeNode *fiter= (TreeNode *)fstLTnode;
 204     DbRetVal  ret=OK;
 205     ret = TreeIndex::getTreeNodeMutex(fiter, procSlot);
 206     if (OK != ret)
 207     {
 208         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 209         return NULL;
 210     }
 211     while( fiter!= NULL)
 212     {
 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)
 218         {
 219             break;
 220         }else
 221         {
 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)
 228                {
 229                    printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 230                    tmpIter->mutex_.releaseShareLock(procSlot);
 231                    iter = NULL;
 232                    return NULL;
 233                }
 234                tmpIter->mutex_.releaseShareLock(procSlot);
 235             }else{
 236                tmpIter->mutex_.releaseShareLock(procSlot);
 237                fiter = NULL;
 238             }
 239         }
 240     }
 241     if(fiter == NULL)
 242     {
 243         iter = NULL;
 244         return NULL;
 245     }
 246     //Get leaf Node
 247
 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)
 252    {
 253         tNode = ((TreeNode *)*(char**)((char*)rec + (loc * sizeof(void *))));
 254         iter = tNode;
 255         fiter->mutex_.releaseShareLock(procSlot);
 256         void *rec1 = locateElement();
 257         return rec1;
 258    }
 259    for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 260     {
 261         loc = middle;
 262         tNode = (TreeNode *)*((char**)((char*)((char*)fiter + sizeof(TreeNode))+ (loc*sizeof(void *))));
 263         char *record = ((char*)tNode->max_)+ fldOffset;
 264
 265         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
 266                                            type, length);
 267         if(res)
 268         {
 269             end = middle - 1;
 270         }
 271         else
 272         {
 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;
 281             }
 282         }
 283     }
 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;
 290 }
 291
 292 void* TreeIter::locateElement()
 293 {
 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)
 299     {
 300         printError(ErrLockTimeOut,"Unable to lock the tree node. Retry...");
 301         return NULL;
 302     }
 303     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 304     {
 305         loc = middle;
 306         char *record = ((char*)*(rec+middle)) + fldOffset;
 307         bool res = AllDataType::compareVal(searchKey, record, OpLessThan,
 308                                            type, length);
 309         if(res)
 310         {
 311             end = middle - 1;
 312         }
 313         else
 314         {
 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;
 323             }
 324         }
 325     }
 326     nodeOffset=loc;
 327     char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
 328     nodeOffset++;
 329     //iter->mutex_.releaseShareLock(procSlot);
 330     return *tuple;
 331 }