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         //TODO::take node mutex here
  85         char **rec = (char**)((char*)iter + sizeof(TreeNode));
  86         rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
  87         nodeOffset++;
  88         //TODO::release node mutex here
  89         return *rec;
  90     }
  91     return NULL;
  92 }
  93 void* TreeIter::locateNode()
  94 {
  95     while(iter != NULL)
  96     {
  97         char *record = ((char*)iter->max_)+ fldOffset;
  98         bool result = AllDataType::compareVal(searchKey, record,
  99                                               OpGreaterThan,
 100                                               type, length);
 101         if (result)
 102         {
 103             //need to move right
 104             iter = iter->next_;
 105         }else
 106         {
 107             record = ((char*)iter->min_)+ fldOffset;
 108             result = AllDataType::compareVal(searchKey, record,
 109                                              OpGreaterThanEquals,
 110                                              type, length);
 111             if (result) {
 112                 //current node contains the key
 113                 void *rec = locateElement();
 114                 return rec;
 115             }
 116             else
 117             {
 118                //need to move left
 119                iter = iter->prev_;
 120             }
 121         }
 122     }
 123     return NULL;
 124 }
 125 void* TreeIter::locateElement()
 126 {
 127     //do binary search and locate the element
 128     int loc=0, middle=0, start=0, end=iter->noElements_-1;
 129     char **rec = (char**)((char*)iter + sizeof(TreeNode));
 130     //TODO::take node mutex
 131     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 132     {
 133         loc = middle;
 134         char *record = ((char*)*(rec+middle)) + fldOffset;
 135         bool res = AllDataType::compareVal(searchKey, record, OpEquals,
 136                                            type, length);
 137         if(res)
 138         {
 139             loc = middle;
 140             break;
 141         }
 142         res = AllDataType::compareVal(searchKey, record, OpLessThan,
 143                                           type, length);
 144         if(res)
 145         {
 146             end = middle - 1;
 147         }
 148         else
 149         {
 150             start = middle + 1;
 151             loc = start;
 152         }
 153     }
 154     nodeOffset=loc;
 155     char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
 156     nodeOffset++;
 157     //TODO::release node mutex here
 158     return *tuple;
 159 }