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 class TreeNode
  53 {
  54     public:
  55     Mutex mutex_;
  56     void *min_;
  57     void *max_;
  58     int noElements_;
  59     TreeNode *next_;
  60     TreeNode *prev_;
  61     int balance_;
  62     //Note::after this array of pointer to tuples are stored
  63     long long getTotalElements();
  64     TreeNode* locateNode(Database *db,TreeNode *iter, void *tuple, IndexInfo *indInfo,DbRetVal &rv);
  65     TreeNode *locateNodeFromFirstLevel(TreeNode *ftnode,IndexInfo *indInfo,void *tuple,int *nodepos);
  66     DbRetVal insertNodeIntoFirstLevel(Database * db, IndexInfo * indInfo, void* indexPtr, TreeNode * newNode,int nodepos);
  67     DbRetVal insert(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
  68     DbRetVal insertRecordIntoNodeAndArrangeFirstLevel(Database * db, IndexInfo * indInfo, void* iptr, void * tuple, TreeNode * fstLevel,int nodepos);
  69     DbRetVal remove(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
  70     DbRetVal update(Database *db, IndexInfo *info, void *indexPtr, void *tuple);
  71     void displayAll();
  72     void displayAll(int offset);
  73 };
  74
  75 class BucketIter
  76 {
  77     IndexNode *iter;
  78     IndexNode *head;
  79     bool isUnique;
  80     bool recordsOver;
  81     public:
  82     BucketIter(){iter = head = NULL;
  83                  isUnique=false; recordsOver = false;}
  84     void setHead(IndexNode *hd) { iter = head = hd; recordsOver=false;}
  85     BucketIter(IndexNode *head) { iter = head = head;
  86                  isUnique=false; recordsOver = false;}
  87     void setUnique() { isUnique = true; }
  88     bool getUnique() { return isUnique; }
  89     IndexNode* next();
  90     void reset() { iter = head; recordsOver=false;}
  91     friend class BucketList;
  92 };
  93 class BucketList
  94 {
  95     IndexNode *head;
  96     public:
  97     BucketList(){ head = NULL;}
  98     BucketList(IndexNode *h){ head = h; }
  99     void *getBucketListHead(){ return head;}
 100     DbRetVal insert(Chunk *chunk, Database *db, void *key, void *tuple);
 101     DbRetVal remove(Chunk *chunk, Database *db, void *key);
 102     void print();
 103     BucketIter getIterator()
 104     {
 105         BucketIter it;
 106         it.iter = head;
 107         return it;
 108     }
 109 };
 110 class HashIndex;
 111 class IndexInfo;
 112 class HashIndexInfo;
 113 class TreeIndex;
 114 class TrieIndex;
 115 class Index
 116 {
 117     // create (one) object for each indexing mechanisms here
 118     // Also need to make changes to getIndex() and destroy() methods
 119     // accordingly for new index machanism.
 120     static HashIndex *hIdx;
 121     static TreeIndex *tIdx;
 122     static TrieIndex *iIdx;
 123     static long usageCount;
 124     public:
 125     static Index* getIndex(IndexType type);
 126     static void init() { usageCount++; }
 127     static void destroy();
 128     virtual DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 129     virtual DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 130     virtual DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag)=0;
 131 };
 132 class HashIndex : public Index
 133 {
 134     //No members as it will be called by multiple threads
 135     public:
 136     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 137     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 138     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 139     bool checkForUniqueKey(IndexNode *head,HashIndexInfo *info, void *tuple);
 140     static unsigned int computeHashBucket(DataType type, void *key, int noOfBuckets, int length=0);
 141     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 142     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 143 };
 144
 145 class TreeIndex : public Index
 146 {
 147     //No members as it will be called by multiple threads
 148     DbRetVal removeElement(Database *db, TreeNode *iter, void *tuple, HashIndexInfo *info);
 149     void removeNode(Database *db,void *indexPtr,TreeNode *fltnode, TreeNode *node,int pos);
 150     public:
 151     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 152     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 153     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 154     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 155     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 156     static DbRetVal getTreeNodeMutex(TreeNode*, int procSlot, bool isX=false);
 157     static DbRetVal upgradeTreeNodeMutex(TreeNode*, int procSlot);
 158
 159 };
 160
 161 class TrieIndex: public Index
 162 {
 163     public:
 164     DbRetVal insert(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 165     DbRetVal remove(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 166     DbRetVal update(TableImpl *tbl, Transaction *tr, void *indexPtr, IndexInfo *info, void *tuple, bool undoFlag);
 167     //bool checkForUniqueKey(IndexNode *head, HashIndexInfo *info, void *tuple);
 168     static void computeHashValues(DataType type, void *key, char *in, int length=0);
 169     static DbRetVal insertLogicalUndoLog(Database *sysdb, void *info);
 170     static DbRetVal deleteLogicalUndoLog(Database *sysdb, void *info);
 171     void displayAll(TrieNode *node, int level =1);
 172     void printTrieNode(TrieNode *node, int level);
 173     private:
 174     DbRetVal addToValueList(Database*, void**, Chunk*, void*, void*);
 175     DbRetVal removeFromValueList(Database*, void**, Chunk*, void*, void*);
 176
 177 };
 178 class TreeIter
 179 {
 180     TreeNode *iter;
 181     TreeNode *head;
 182     int fldOffset;
 183     DataType type;
 184     int length;
 185     ComparisionOp op;
 186     bool asc;
 187     void *searchKey;
 188     bool firstCall;
 189     int nodeOffset;
 190     bool recordsOver;
 191     void *fstLTnode;
 192     void* locateNode();
 193     void* locateElement();
 194     int procSlot;
 195     bool isUnique;
 196
 197     public:
 198     TreeIter(){ iter=head=NULL; searchKey=fstLTnode=NULL;isUnique = false;}
 199     TreeIter(TreeNode *hd,void *fTnode, int slot ) { fstLTnode = fTnode; iter = head = hd; firstCall = true; recordsOver=false; procSlot=slot; isUnique=false;}
 200     void set(TreeNode *hd,void *fTnode, int slot ) { fstLTnode = fTnode; iter = head = hd; firstCall = true; recordsOver=false; procSlot=slot; isUnique=false;}
 201     void setSearchKey(void *key, ComparisionOp cop, bool ascending = true)
 202     {
 203         searchKey = key; op = cop; asc =ascending;
 204     }
 205     void setUnique() { isUnique = true; }
 206     bool getUnique() { return isUnique; }
 207     void setFldOffset(int off) { fldOffset = off; }
 208     void setTypeLength(DataType t, int l) { type =t ; length =l; }
 209     void* prev();
 210     void* next();
 211     void nextNode();
 212     void* getFirstElement();
 213     void* getLastElement();
 214     void reset();// { iter = head; firstCall = true; recordsOver=false; }
 215 };
 216
 217 enum IndexIntType
 218 {
 219         hashOneField = 1,
 220         hash = 2,
 221         tree = 3,
 222         trie = 4
 223
 224 };
 225 class IndexInfo
 226 {
 227     public:
 228     IndexType indType;
 229     virtual ~IndexInfo() {}
 230 };
 231
 232 //Used by TableImpl to cache information related to hash indexes on that table
 233 class HashIndexInfo :public IndexInfo
 234 {
 235     public:
 236     FieldList idxFldList;
 237     char *indexPtr;
 238     int noOfBuckets;
 239     Bucket* buckets;
 240     int fldOffset;
 241     bool isUnique;
 242     DataType type;
 243     int compLength;
 244     void print()
 245     {
 246         printf("HashIndexInfo indexPtr:%x noOfBuckets:%d buckets:%x \n",indexPtr, noOfBuckets, buckets);
 247     }
 248     ~HashIndexInfo() { idxFldList.removeAll(); }
 249 };
 250 #endif
 251