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::prev()
  20 {
  21    if (0 != nodeOffset )
  22    {
  23        nodeOffset--;
  24
  25    }else
  26    {
  27        iter=iter->prev_;
  28        if (NULL == iter) return NULL;
  29        nodeOffset = iter->noElements_;
  30    }
  31    char **rec = (char**)((char*)iter + sizeof(TreeNode));
  32    rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
  33    return *rec;
  34 }
  35 void* TreeIter::next()
  36 {
  37     int direction=0;
  38     if (recordsOver) return NULL;
  39     if (NULL== iter) return NULL;
  40     if (firstCall)
  41     {
  42         if (OpLessThan ==op || OpLessThanEquals == op)
  43         {
  44             while(iter->prev_)
  45             {
  46                 iter = iter->prev_;
  47             }
  48             firstCall = false;
  49             nodeOffset = 1;
  50             char **rec = (char**)((char*) iter + sizeof(TreeNode));
  51             //iter->displayAll(fldOffset);
  52             return *rec;
  53         }
  54         else if (OpGreaterThan == op || OpGreaterThanEquals == op ||
  55                  OpEquals == op)
  56         {
  57             void *rec = locateNode();
  58             firstCall = false;
  59             //iter->displayAll(fldOffset);
  60             return rec;
  61         }
  62         firstCall = false;
  63     }else
  64     {
  65         if (nodeOffset == iter->noElements_)
  66         {
  67             if (NULL == iter->next_) {recordsOver = true; return NULL;}
  68             char* record = ((char*)iter->next_->min_)+ fldOffset;
  69             bool result = AllDataType::compareVal(searchKey, record,
  70                                               OpGreaterThanEquals,
  71                                               type, length);
  72             if (!result && (OpLessThan ==op || OpLessThanEquals == op))
  73             {
  74                 recordsOver= true; return NULL;
  75             }else if (result && (OpGreaterThan == op ||
  76                       OpGreaterThanEquals == op))
  77             {
  78                 recordsOver= true; return NULL;
  79             }
  80             iter=iter->next_;
  81             if (NULL == iter) return NULL;
  82             nodeOffset=0;
  83         }
  84         char **rec = (char**)((char*)iter + sizeof(TreeNode));
  85         rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
  86         nodeOffset++;
  87         return *rec;
  88     }
  89     return NULL;
  90 }
  91 void* TreeIter::locateNode()
  92 {
  93     while(iter != NULL)
  94     {
  95         char *record = ((char*)iter->max_)+ fldOffset;
  96         bool result = AllDataType::compareVal(searchKey, record,
  97                                               OpGreaterThan,
  98                                               type, length);
  99         if (result)
 100         {
 101             //need to move right
 102             iter = iter->next_;
 103         }else
 104         {
 105             record = ((char*)iter->min_)+ fldOffset;
 106             result = AllDataType::compareVal(searchKey, record,
 107                                              OpGreaterThanEquals,
 108                                              type, length);
 109             if (result) {
 110                 //current node contains the key
 111                 void *rec = locateElement();
 112                 return rec;
 113             }
 114             else
 115             {
 116                //need to move left
 117                iter = iter->prev_;
 118             }
 119         }
 120     }
 121     return NULL;
 122 }
 123 void* TreeIter::locateElement()
 124 {
 125     //do binary search and locate the element
 126     int loc=0, middle=0, start=0, end=iter->noElements_-1;
 127     char **rec = (char**)((char*)iter + sizeof(TreeNode));
 128     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 129     {
 130         loc = middle;
 131         char *record = ((char*)*(rec+middle)) + fldOffset;
 132         bool res = AllDataType::compareVal(searchKey, record, OpEquals,
 133                                            type, length);
 134         if(res)
 135         {
 136             loc = middle;
 137             break;
 138         }
 139         res = AllDataType::compareVal(searchKey, record, OpLessThan,
 140                                           type, length);
 141         if(res)
 142         {
 143             end = middle - 1;
 144         }
 145         else
 146         {
 147             start = middle + 1;
 148             loc = start;
 149         }
 150     }
 151     nodeOffset=loc;
 152     char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
 153     nodeOffset++;
 154     return *tuple;
 155 }