include/Allocator.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 ALLOCATOR_H
  17 #define ALLOCATOR_H
  18 #include<os.h>
  19 #include<Mutex.h>
  20 #include<ErrorType.h>
  21 #include<Config.h>
  22
  23 typedef void Page;
  24
  25 enum AllocType
  26 {
  27     FixedSizeAllocator = 0,
  28     VariableSizeAllocator = 1,
  29     UnknownAllocator
  30 };
  31
  32 //Used to store the meta data information about the variable size data
  33 class VarSizeInfo
  34 {
  35     public:
  36     InUse size_;   /**< size of the allocated node */
  37     InUse isUsed_; /**< bit to represent whether this node is under use */
  38 };
  39 #define HAS_SPACE 1
  40 #define IS_DIRTY  2
  41
  42 /**
  43 * @brief Page Header Info
  44 *
  45 * Database is divided into equal size parts(PAGE_SIZE) called pages. Each page contains page header (PageInfo) to store information related to pages such as whether it is in use, next used page for chunk, etc
  46 *
  47 * If data size is more than PAGE_SIZE then contigous pages are merged and those pages wont have page header info(pageInfo) in them. Only the start page where that data is stored will have header information. This object is stored at the start of each page unless it is a merged page.
  48 */
  49
  50 class PageInfo
  51 {
  52      public:
  53      InUse isUsed_; /**< specifies whether this page is in use */
  54      InUse flags; /**< stores hasFreeSpace and isDirty flags */
  55
  56      Page *nextPageAfterMerge_; /**<used only in case of merged pages */
  57
  58      Page *nextPage_; /**<points to the next page in the same chunk */
  59
  60
  61     /**
  62     *  @brief set page used flag
  63     *
  64     *  @param offset size of chunk in case of fixed size. For size greater than PAGE_SIZE, it will be aligned by PAGE_SIZE. Default value zero
  65     *  @return void
  66     */
  67     void setPageAsUsed(size_t offset=0);
  68
  69     /**
  70     *  @brief set page as unused
  71     *
  72     *  @return void
  73     */
  74      void setPageAsFree();
  75
  76 };
  77 class Chunk;
  78
  79
  80 //Iterator for the data
  81 //Data is stored in chunks and this class gives
  82 //iterator for it.
  83 class ChunkIterator
  84 {
  85     int chunkID_;
  86     size_t allocSize_; // used if it is a fixed size allocator
  87     AllocType allocType_;
  88
  89     //current iterating page
  90     PageInfo *iterPage_;
  91
  92     //Each page is divided into nodes of size allocSize_
  93     //This gives the offset of the node in the page
  94     int nodeOffset_;
  95     char *data;
  96     char *iterPageEnd;
  97
  98     //Total number of nodes in the page
  99     //It is a constant value for this chunk
 100     //and it is cached for performance
 101     int noOfNodes_;
 102
 103
 104     public:
 105     int pageSize;
 106     ChunkIterator() { pageSize = PAGE_SIZE; allocSize_ =0; iterPage_ = NULL; nodeOffset_ =0;
 107                       chunkID_ = -1; noOfNodes_  =0; }
 108     int isLargeSize() { if (noOfNodes_ == 0) return true; else return false; }
 109     void* nextElement();
 110     void* nextElementIntMatch(int value, int offset);
 111     inline void* nextElementInt() {
 112         if (!data) {
 113             pageSize = PAGE_SIZE;
 114             data = ((char*)iterPage_) + sizeof(PageInfo);
 115             if ((*(InUse*)data) == 1) return data + sizeof(InUse);
 116         }
 117
 118         if(0 == noOfNodes_) return nextElement();
 119         data += allocSize_;
 120         while(data < iterPageEnd)
 121         {
 122             if (*((InUse*)data)) {
 123                 return data + sizeof(InUse);
 124             } else {
 125                data += allocSize_;
 126             }
 127         }
 128         while(iterPage_->nextPage_ != NULL)
 129         {
 130             iterPage_ = (PageInfo*)iterPage_->nextPage_;
 131             data = ((char*)iterPage_) + sizeof(PageInfo);
 132             iterPageEnd = ((char*)iterPage_) + pageSize;
 133             while(data < iterPageEnd)
 134             {
 135                 if (*((InUse*)data) == 0) {
 136                    data = data + allocSize_;
 137                    nodeOffset_++;
 138                 } else
 139                     return data +sizeof(InUse);
 140             }
 141         }
 142         return NULL;
 143     }
 144     friend class Chunk;
 145 };
 146
 147 class Database;
 148 class DatabaseManagerImpl;
 149
 150 class Chunk
 151 {
 152     int chunkID_;
 153
 154     // used if it is a fixed size allocator
 155     size_t allocSize_;
 156     AllocType allocType_;
 157
 158     //Current page where the last data allocation was made
 159     Page *curPage_;
 160
 161     //Page where data allocation was made for the first time
 162     //This is the start of the data
 163     //Iterator should start from this page
 164     Page *firstPage_;
 165     char chunkName[CHUNK_NAME_LEN];
 166     Mutex chunkMutex_;
 167
 168     public:
 169
 170     //sets the size of the allocator
 171     //for fixed size allocator
 172     void setSize(size_t size);
 173
 174     void setChunkNameForSystemDB(int id);
 175     void setChunkName(char const *name){strcpy(chunkName,name);}
 176     char *getChunkName(){return chunkName;}
 177
 178     size_t getSize()                  { return allocSize_; }
 179     void setChunkID(unsigned int id)           { chunkID_ = id; }
 180     int getChunkID()                  { return chunkID_; }
 181     void setAllocType(AllocType type) { allocType_ = type; }
 182     AllocType getAllocType()          { return allocType_; }
 183     Page* getFirstPage(){ return firstPage_; }
 184     Page* getCurrentPage(){ return curPage_; }
 185     void setFirstPage(void *fp) { firstPage_ = fp;}
 186     void setCurPage(void *cp) { curPage_ = cp;}
 187     PageInfo* getPageInfo(Database *db, void *ptr);
 188     void* tryAllocate(Database *db, DbRetVal *status, int totalTries=10);
 189     void* allocate(Database *db, DbRetVal *status);
 190
 191     void* allocate(Database *db, size_t size, DbRetVal *status);
 192
 193     void  free(Database *db, void* ptr);
 194     ChunkIterator getIterator();
 195     void print();
 196     void printMutexInfo() { chunkMutex_.print(); }
 197
 198     long getTotalDataNodes();
 199     long getVarTotalDataNodes();
 200     int totalPages();
 201     int totalDirtyPages();
 202     int compact(int procSlot);
 203     void varCompact();
 204
 205     private:
 206
 207     int initMutex(int i=-1);
 208     int getChunkMutex(int procSlot);
 209     int releaseChunkMutex(int procSlot);
 210     int destroyMutex();
 211
 212     void* allocateFromFirstPage(Database *db, int noOfDataNodes, DbRetVal *status);
 213     void* allocateFromNewPage(Database *db, DbRetVal *status);
 214
 215
 216     int createDataBucket(Page *page, size_t totalSize, size_t needSize, int pslot);
 217     int splitDataBucket(VarSizeInfo *varInfo, size_t needSize, int pslot, DbRetVal *status);
 218     void* varSizeFirstFitAllocate(size_t size, int pslot, DbRetVal *status);
 219     void freeForVarSizeAllocator(Database *db, void *ptr, int pslot);
 220     void* allocateForVarLargeSize(PageInfo *pInfo, size_t size, int offset);
 221     void* allocFromNewPageForVarSize(Database *db, size_t size, int pslot,
 222                                      DbRetVal *status);
 223     void* allocateFromCurPageForVarSize(size_t size, int pslot, DbRetVal *status);
 224
 225     void* allocateForLargeDataSize(Database *db);
 226     void* allocateForLargeDataSize(Database *db, size_t size);
 227     void freeForLargeAllocator(void *ptr, int pslot);
 228
 229     void setPageDirty(Database *db, void *ptr);
 230     void setPageDirty(PageInfo *pInfo);
 231
 232
 233     friend class Database;
 234     friend class DatabaseManagerImpl;
 235 };
 236 #endif