include/AD/memory/boundtag.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef boundary_tag_memory_manager_h
  26 #define boundary_tag_memory_manager_h
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 // Class |BoundaryTag| is a generic purpose memory manager based
  30 // on the boundary tag algorithm.  In this algorithm, a free list
  31 // of free memory blocks are kept.  The list is {\em not} sorted
  32 // by address order, but rather, two {\bf tags} are kept in the
  33 // the header of each allocated block, one denoting the size of
  34 // the current block, and one denoting the size of the last block
  35 // in address order.  Notice that the size of each block is actually
  36 // duplicated within this scheme: one in the current header, and one
  37 // in the header of the last block in the address order.  This way,
  38 // it is possible to free a block and merge adjacent blocks in contant
  39 // time.  Allocation, however, is accomplished using a roving first fit
  40 // strategy.  Simulation results have shown that this algorithm
  41 // performs efficiently if the pool of memory is not close to being
  42 // exhausted\cite{LD-1991}
  43 //////////////////////////////////////////////////////////////////////////////
  44
  45 #include <AD/memory/mem.h>
  46
  47 class BoundaryTag : public Mem {
  48
  49    BoundaryTag(const BoundaryTag&);      // no copy constructor
  50    void operator = (const BoundaryTag&); // no assignment
  51
  52 public:
  53
  54    ///////////////////////////////////////////////////////////////////////////
  55    // Type alias
  56    ///////////////////////////////////////////////////////////////////////////
  57    typedef Mem Super;
  58
  59 protected:
  60
  61    ///////////////////////////////////////////////////////////////////////////
  62    // Internals
  63    ///////////////////////////////////////////////////////////////////////////
  64
  65    //
  66    // A block header.
  67    //
  68    struct Block {
  69       LongWord last_size;    // Size of last block
  70       LongWord size;         // Size of current block
  71       Block * next, * last;  // Link to next and last block on the free list
  72
  73       enum Block_constant {
  74          USED_BIT = 0xF0000000
  75       };
  76    };
  77
  78    Block * freeList;        // Doubly linked circular free list
  79    Block stub;              // A dummy free block, not allocatable.
  80
  81    struct Page {
  82       Page * next;                   // next page in the linked list of pages
  83       BoundaryTag::Block blocks[1];  // actual storage
  84    } * pages;                        // A linked list of pages allocated
  85
  86    long pageSize;           // default size of a page
  87    long allocated;          // bytes allocated
  88
  89    virtual void grow(long size);
  90
  91    enum BoundaryTag_constant {
  92      MY_PAGE_SIZE = 1024  // Default page size is 1K bytes
  93    };
  94
  95 public:
  96
  97    struct Statistics {
  98       long bytes_allocated;    // bytes allocated from system
  99       long bytes_available;    // bytes available in manager
 100       long free_block_count;   // number of free blocks within free list
 101       long page_count;         // number of pages allocated
 102    };
 103
 104 public:
 105
 106    ///////////////////////////////////////////////////////////////////////////
 107    // Constructor and destructor
 108    ///////////////////////////////////////////////////////////////////////////
 109    BoundaryTag(long defaultPageSize = MY_PAGE_SIZE);
 110    BoundaryTag(Mem&, long defaultPageSize = MY_PAGE_SIZE);
 111   ~BoundaryTag();
 112
 113    ///////////////////////////////////////////////////////////////////////////
 114    //  Methods for allocation
 115    ///////////////////////////////////////////////////////////////////////////
 116    inline void * operator [] (long size) { return m_alloc(size); }
 117    char * operator [] (const char *);
 118
 119    ///////////////////////////////////////////////////////////////////////////
 120    //  Get statistics
 121    ///////////////////////////////////////////////////////////////////////////
 122    Statistics statistics() const;
 123
 124    ///////////////////////////////////////////////////////////////////////////
 125    //  Virtual methods for the Mem protocol
 126    ///////////////////////////////////////////////////////////////////////////
 127    virtual void   clear  ();
 128    virtual void * m_alloc (size_t);
 129    virtual void   free   (void *);
 130    virtual size_t size   (const void *) const;
 131 };
 132
 133 #endif