include/Allocator.h

   1 /***************************************************************************
   2  *   Copyright (C) 2007 by Prabakaran Thirumalai   *
   3  *   praba_tuty@yahoo.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
  21 typedef void Page;
  22
  23 enum AllocType
  24 {
  25     FixedSizeAllocator = 0,
  26     VariableSizeAllocator = 1,
  27     UnknownAllocator
  28 };
  29
  30 //Used to store the meta data information about the variable size data
  31 class VarSizeInfo
  32 {
  33     public:
  34     size_t size_;
  35     int isUsed_;
  36 };
  37
  38 //Each Page has this info.
  39 //pages are of size PAGE_SIZE normally.
  40 //If data size is more than PAGE_SIZE then
  41 //contigous pages are merged and those pages wont
  42 //have this info in them.Only the start page where that
  43 //data is stored will have this info
  44 //This object is stored at the start of each page
  45 class PageInfo
  46 {
  47      public:
  48      int isUsed_;
  49      int hasFreeSpace_;
  50
  51      Page *nextPageAfterMerge_; //used only in case of
  52      //where pages are merged to store data which are more than
  53      //PAGE_SIZE.
  54      //More detail about how it is used is found in Database::getFreePage
  55
  56      Page *nextPage_; //next page in the same chunk
  57      void setPageAsUsed(size_t offset);
  58
  59
  60 };
  61 class Chunk;
  62
  63
  64 //Iterator for the data
  65 //Data is stored in chunks and this class gives
  66 //iterator for it.
  67 class ChunkIterator
  68 {
  69     int chunkID_;
  70     size_t allocSize_; // used if it is a fixed size allocator
  71     AllocType allocType_;
  72
  73     //current iterating page
  74     Page *iterPage_;
  75
  76     //Each page is divided into nodes of size allocSize_
  77     //This gives the offset of the node in the page
  78     int nodeOffset_;
  79
  80     //Total number of nodes in the page
  81     //It is a constant value for this chunk
  82     //and it is cached for performance
  83     int noOfNodes_;
  84
  85     public:
  86     void* nextElement();
  87     friend class Chunk;
  88 };
  89
  90 class Database;
  91 class DatabaseManagerImpl;
  92
  93 class Chunk
  94 {
  95     int chunkID_;
  96
  97     // used if it is a fixed size allocator
  98     size_t allocSize_;
  99     AllocType allocType_;
 100
 101     //Current page where the last data allocation was made
 102     Page *curPage_;
 103
 104     //Page where data allocation was made for the first time
 105     //This is the start of the data
 106     //Iterator should start from this page
 107     Page *firstPage_;
 108
 109     Mutex chunkMutex_;
 110
 111     public:
 112
 113     //sets the size of the allocator
 114     //for fixed size allocator
 115     void setSize(size_t size);
 116
 117     size_t getSize()                  { return allocSize_; }
 118     void setChunkID(unsigned int id)           { chunkID_ = id; }
 119     int getChunkID()                  { return chunkID_; }
 120     void setAllocType(AllocType type) { allocType_ = type; }
 121     AllocType getAllocType()          { return allocType_; }
 122
 123
 124     PageInfo* getPageInfo(Database *db, void *ptr);
 125     void* allocate(Database *db);
 126
 127     void* allocate(Database *db, size_t size);
 128
 129     void  free(Database *db, void* ptr);
 130     ChunkIterator getIterator();
 131     void print(){}
 132
 133     private:
 134
 135     int initMutex();
 136     int getChunkMutex();
 137     int releaseChunkMutex();
 138     int destroyMutex();
 139     void createDataBucket(Page *page, size_t totalSize, size_t needSize);
 140     void splitDataBucket(VarSizeInfo *varInfo, size_t needSize);
 141     void* varSizeFirstFitAllocate(size_t size);
 142
 143     friend class Database;
 144     friend class DatabaseManagerImpl;
 145 };
 146 #endif