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 void* TreeIter::getLastElement()
  35 {
  36    if (NULL == iter) return NULL;
  37    TreeNode *node = iter;
  38    while(node != NULL ) {
  39       if(NULL == node->next_)  break;
  40       node = node->next_;
  41    }
  42    if (node == NULL) printf("Node returned is NULL\n");
  43    if (0 == node->noElements_)  return NULL;
  44    char **rec = (char**)((char*)node + sizeof(TreeNode));
  45    int loc = node->noElements_-1; //last element
  46    char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
  47    return *tuple;
  48 }
  49 void* TreeIter::prev()
  50 {
  51    if (0 != nodeOffset )
  52    {
  53        nodeOffset--;
  54
  55    }else
  56    {
  57        iter=iter->prev_;
  58        if (NULL == iter) return NULL;
  59        nodeOffset = iter->noElements_;
  60    }
  61    char **rec = (char**)((char*)iter + sizeof(TreeNode));
  62    rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
  63    return *rec;
  64 }
  65 void TreeIter::nextNode()
  66 {
  67     if (recordsOver) return ;
  68     if (NULL== iter) return ;
  69     iter=iter->next_;
  70     nodeOffset=0;
  71 }
  72 void* TreeIter::next()
  73 {
  74     int direction=0;
  75     if (recordsOver) return NULL;
  76     if (NULL== iter) return NULL;
  77     if (firstCall)
  78     {
  79         if (OpLessThan ==op || OpLessThanEquals == op)
  80         {
  81             while(iter->prev_)
  82             {
  83                 iter = iter->prev_;
  84             }
  85             firstCall = false;
  86             nodeOffset = 1;
  87             char **rec = (char**)((char*) iter + sizeof(TreeNode));
  88             //iter->displayAll(fldOffset);
  89             return *rec;
  90         }
  91         else if (OpGreaterThan == op || OpGreaterThanEquals == op ||
  92                  OpEquals == op)
  93         {
  94             void *rec = locateNode();
  95             firstCall = false;
  96             //iter->displayAll(fldOffset);
  97             return rec;
  98         }
  99         firstCall = false;
 100     }else
 101     {
 102         if (nodeOffset == iter->noElements_)
 103         {
 104             if (NULL == iter->next_) {recordsOver = true; return NULL;}
 105             char* record = ((char*)iter->next_->min_)+ fldOffset;
 106             bool result = AllDataType::compareVal(searchKey, record,
 107                                               OpGreaterThanEquals,
 108                                               type, length);
 109             if (!result && (OpLessThan ==op || OpLessThanEquals == op))
 110             {
 111                 recordsOver= true; return NULL;
 112             }else if (result && (OpGreaterThan == op ||
 113                       OpGreaterThanEquals == op))
 114             {
 115                 recordsOver= true; return NULL;
 116             }
 117             iter=iter->next_;
 118             if (NULL == iter) return NULL;
 119             nodeOffset=0;
 120         }
 121         //TODO::take node mutex here
 122         char **rec = (char**)((char*)iter + sizeof(TreeNode));
 123         rec = (char**)((char *)rec + ((nodeOffset) * sizeof(void **)));
 124         nodeOffset++;
 125         //TODO::release node mutex here
 126         return *rec;
 127     }
 128     return NULL;
 129 }
 130 void* TreeIter::locateNode()
 131 {
 132     while(iter != NULL)
 133     {
 134         char *record = ((char*)iter->max_)+ fldOffset;
 135         bool result = AllDataType::compareVal(searchKey, record,
 136                                               OpGreaterThan,
 137                                               type, length);
 138         if (result)
 139         {
 140             //need to move right
 141             iter = iter->next_;
 142         }else
 143         {
 144             record = ((char*)iter->min_)+ fldOffset;
 145             result = AllDataType::compareVal(searchKey, record,
 146                                              OpGreaterThanEquals,
 147                                              type, length);
 148             if (result) {
 149                 //current node contains the key
 150                 void *rec = locateElement();
 151                 return rec;
 152             }
 153             else
 154             {
 155                //need to move left
 156                if(NULL==iter->prev_)
 157                {
 158                    void *rec = locateElement();
 159                    return rec;
 160                }
 161                iter = iter->prev_;
 162             }
 163         }
 164     }
 165     return NULL;
 166 }
 167 void* TreeIter::locateElement()
 168 {
 169     //do binary search and locate the element
 170     int loc=0, middle=0, start=0, end=iter->noElements_-1;
 171     char **rec = (char**)((char*)iter + sizeof(TreeNode));
 172     //TODO::take node mutex
 173     for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
 174     {
 175         loc = middle;
 176         char *record = ((char*)*(rec+middle)) + fldOffset;
 177         bool res = AllDataType::compareVal(searchKey, record, OpEquals,
 178                                            type, length);
 179         if(res)
 180         {
 181             loc = middle;
 182             break;
 183         }
 184         res = AllDataType::compareVal(searchKey, record, OpLessThan,
 185                                           type, length);
 186         if(res)
 187         {
 188             end = middle - 1;
 189         }
 190         else
 191         {
 192             start = middle + 1;
 193             loc = start;
 194         }
 195     }
 196     nodeOffset=loc;
 197     char **tuple = (char**)((char*)rec + (loc * sizeof(void *)));
 198     nodeOffset++;
 199     //TODO::release node mutex here
 200     return *tuple;
 201 }