include/Index.h

   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 #ifndef INDEX_H
  17 #define INDEX_H
  18 #include<DataType.h>
  19 #include<Debug.h>
  20 #include<Info.h>
  21 #define TRIE_SIZE 10
  22 #define TRIE_MAX_LENGTH 64
  23
  24 class Database;
  25 class Chunk;
  26 class Transaction;
  27 class TableImpl;
  28 class CINDEX;
  29
  30 class Bucket
  31 {
  32     public:
  33     Mutex mutex_;
  34     void *bucketList_;
  35 };
  36 class IndexNode
  37 {
  38     public:
  39     void *ptrToKey_;
  40     void *ptrToTuple_;
  41     IndexNode *next_;
  42 };
  43
  44 class TrieNode
  45 {
  46     public:
  47     IndexNode *head_[TRIE_SIZE];
  48     TrieNode *next_[TRIE_SIZE];
  49 };
  50
  51 class IndexInfo;
  52
  53 /**
  54 * @class TreeNode
  55 * @brief Represents node in tree index.
  56 *        It is actually a doubly linked list node which contains information such as minimum key value pointer, maximum key value pointer and total number of elements.
  57 *
  58 * TreeNode represents node in tree index and it is guarded by a mutex.
  59 * Any modifications to tree node should be done only after acquiring
  60 * its associated mutex. At the end array of pointers to next level tree nodes(in case of intermediate node) / tuple is stored(in case of leaf nodes)
  61 * <br/>
  62 *
  63 */
  64
  65 class TreeNode
  66 {
  67     public:
  68     Mutex mutex_;       /**< Mutex guarding this node */
  69     void *min_;         /**< Ptr to node having minimum value in this node */
  70     void *max_;         /**< Ptr to node having maximum value in this node */
  71     int noElements_;    /**< total number of elements in this node */
  72     TreeNode *next_;    /**< ptr to next tree node in same level */
  73     TreeNode *prev_;    /**< ptr to previous tree node in same level */
  74     int balance_;       /**< Reserved. Not currently used */
  75     //Note::after this array of pointer to tuples are stored
  76
  77     long long getTotalElements();
  78
  79
  80     /**
  81     *  @brief insert node into the tree, by traversing and locating the right node
  82     *
  83     *  Detailed description comes here
  84     *  Detailed desc continues here
  85     *  @param db  pointer to Database
  86     *  @param info pointer to tuple under search
  87     *  @param indexPtr  ptr to INDEX structure
  88     *  @param tuple pointer to tuple under search
  89     *  @return DbRetVal error code when function returns
  90     */
  91     DbRetVal insert(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
  92
  93     /**
  94     *  @brief remove node from the tree, by traversing and locating the right node
  95     *
  96     *  @param db  pointer to Database
  97     *  @param info pointer to tuple under search
  98     *  @param indexPtr  ptr to INDEX structure
  99     *  @param tuple pointer to tuple to be removed
 100     *  @return DbRetVal error code when function returns
 101     */
 102     DbRetVal remove(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
 103
 104     /**
 105     *  @brief update node in the tree, by traversing and locating the right node
 106     *
 107     *  @param db  pointer to Database
 108     *  @param info pointer to tuple under search
 109     *  @param indexPtr  ptr to INDEX structure
 110     *  @param tuple pointer to tuple to be updated
 111     *  @return DbRetVal error code when function returns
 112     */
 113     DbRetVal update(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
 114
 115     void displayAll();
 116     void displayAll(int offset);
 117
 118     private:
 119
 120     /**
 121     *  @brief locate node where tuple resides by traversing the tree nodes
 122     *
 123     *  Detailed description comes here
 124     *  Detailed desc continues here
 125     *  @param db  pointer to Database
 126     *  @param iter  TreeNode pointer
 127     *  @param tuple pointer to tuple under search
 128     *  @param indInfo pointer to tuple under search
 129     *  @param rv OUT param which will contain error code when this function returns with any error
 130     *  @return TreeNode* pointer to TreeNode which contains the tuple under search
 131     */
 132     TreeNode* locateNode(Database *db,TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv);
 133     TreeNode *locateNodeFromFirstLevel(TreeNode *ftnode,IndexInfo *indInfo,void *tuple,int *nodepos);
 134     DbRetVal insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* iptr, void * tuple, TreeNode * fstLevel,int nodepos);
 135     DbRetVal insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos);
 136     friend class TreeIndex;
 137 };
 138
 139 class BucketIter
 140 {
 141     IndexNode *iter;
 142     IndexNode *head;
 143     bool isUnique;
 144     bool recordsOver;
 145     public:
 146     BucketIter(){iter = head = NULL;
 147                  isUnique=false; recordsOver = false;}
 148     void setHead(IndexNode *hd) { iter = head = hd; recordsOver=false;}
 149     BucketIter(IndexNode *head) { iter = head = head;
 150                  isUnique=false; recordsOver = false;}
 151     void setUnique() { isUnique = true; }
 152     bool getUnique() { return isUnique; }
 153     IndexNode* next();
 154     void reset() { iter = head; recordsOver=false;}
 155     friend class BucketList;
 156 };
 157 class BucketList
 158 {
 159     IndexNode *head;
 160     public:
 161     BucketList(){ head = NULL;}
 162     BucketList(IndexNode *h){ head = h; }
 163     void *getBucketListHead(){ return head;}
 164     DbRetVal insert(Chunk *chunk, Database *db, void *key, void *tuple);
 165     DbRetVal remove(Chunk *chunk, Database *db, void *key);
 166     void print();
 167     BucketIter getIterator()
 168     {
 169         BucketIter it;
 170         it.iter = head;
 171         return it;
 172     }
 173 };
 174 class HashIndex;
 175 class IndexInfo;
 176 class HashIndexInfo;
 177 class TreeIndex;
 178 class TrieIndex;
 179 class Index
 180 {
 181     // create (one) object for each indexing mechanisms here
 182     // Also need to make changes to getIndex() and destroy() methods
 183     // accordingly for new index machanism.
 184     static HashIndex *hIdx;
 185     static TreeIndex *tIdx;
 186     static TrieIndex *iIdx;
 187     static long usageCount;
 188     public:
 189     static Index* getIndex(IndexType type);
 190     static void init() { usageCount++; }
 191     static void destroy();
 192     virtual DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 193     virtual DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 194     virtual DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 195 };
 196 class HashIndex : public Index
 197 {
 198     //No members as it will be called by multiple threads
 199     public:
 200     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 201     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 202     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 203     bool checkForUniqueKey(IndexNode *head,HashIndexInfo *info, void *tuple);
 204     static unsigned int computeHashBucket(DataType type, void *key, int noOfBuckets, int length=0);
 205     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 206     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 207 };
 208
 209 class TreeIndex : public Index
 210 {
 211     //No members as it will be called by multiple threads
 212     DbRetVal removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info);
 213     void removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos);
 214     public:
 215     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 216     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 217     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 218     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 219     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 220     static DbRetVal getTreeNodeMutex(TreeNode*, int procSlot, bool isX=false);
 221     static DbRetVal upgradeTreeNodeMutex(TreeNode*, int procSlot);
 222
 223 };
 224
 225 class TrieIndex: public Index
 226 {
 227     public:
 228     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 229     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 230     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 231     bool checkForUniqueKey(IndexNode *head, IndexInfo *info, void *tuple);
 232     static void computeHashValues(DataType type, void *key, char *in, int length=0);
 233     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 234     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 235     static void displayAll(TrieNode *node, int level =1);
 236     static void printTrieNode(TrieNode *node, int level);
 237     private:
 238     DbRetVal addToValueList(Database*, void**, Chunk*, IndexInfo*, void*, void*);
 239     DbRetVal removeFromValueList(Database*, void**, Chunk*, void*, void*);
 240
 241 };
 242 class TreeIter
 243 {
 244     TreeNode *iter;
 245     TreeNode *head;
 246     int fldOffset;
 247     DataType type;
 248     int length;
 249     ComparisionOp op;
 250     bool asc;
 251     void *searchKey;
 252     bool firstCall;
 253     int nodeOffset;
 254     bool recordsOver;
 255     void *fstLTnode;
 256     void* locateNode();
 257     void* locateElement();
 258     int procSlot;
 259     bool isUnique;
 260
 261     public:
 262     TreeIter(){ iter=head=NULL; searchKey=fstLTnode=NULL;isUnique = false;}
 263     TreeIter(TreeNode *hd,void *fTnode, int slot ) { fstLTnode = fTnode; iter = head = hd; firstCall = true; recordsOver=false; procSlot=slot; isUnique=false;}
 264     void set(TreeNode *hd,void *fTnode, int slot ) { fstLTnode = fTnode; iter = head = hd; firstCall = true; recordsOver=false; procSlot=slot; isUnique=false;}
 265     void setSearchKey(void *key, ComparisionOp cop, bool ascending = true)
 266     {
 267         searchKey = key; op = cop; asc =ascending;
 268     }
 269     void setUnique() { isUnique = true; }
 270     bool getUnique() { return isUnique; }
 271     void setFldOffset(int off) { fldOffset = off; }
 272     void setTypeLength(DataType t, int l) { type =t ; length =l; }
 273     void* prev();
 274     void* next();
 275     void nextNode();
 276     void* getFirstElement();
 277     void* getLastElement();
 278     void reset();// { iter = head; firstCall = true; recordsOver=false; }
 279 };
 280
 281 enum IndexIntType
 282 {
 283         hashOneField = 1,
 284         hash = 2,
 285         tree = 3,
 286         trie = 4
 287
 288 };
 289 class IndexInfo
 290 {
 291     public:
 292     IndexType indType;
 293     int fldOffset;
 294     bool isUnique;
 295     DataType type;
 296     int compLength;
 297     virtual ~IndexInfo() {}
 298 };
 299
 300 //Used by TableImpl to cache information related to hash indexes on that table
 301 class HashIndexInfo :public IndexInfo
 302 {
 303     public:
 304     FieldList idxFldList;
 305     char *indexPtr;
 306     int noOfBuckets;
 307     Bucket* buckets;
 308     void print()
 309     {
 310         printf("HashIndexInfo indexPtr:%x noOfBuckets:%d buckets:%x \n",indexPtr, noOfBuckets, buckets);
 311     }
 312     ~HashIndexInfo() { idxFldList.removeAll(); }
 313 };
 314 #endif
 315