include/AD/memory/buddy.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 fibonacci_buddy_system_h
  26 #define fibonacci_buddy_system_h
  27
  28 #include <AD/memory/mem.h>
  29
  30 /////////////////////////////////////////////////////////////////////////////
  31 // Buddy system based memory manager\cite{LD-1991}.
  32 /////////////////////////////////////////////////////////////////////////////
  33
  34 class Buddy : public Mem {
  35
  36    Buddy(const Buddy&);             // No copy constructor
  37    void operator = (const Buddy&);  // No assignment
  38
  39 public:
  40
  41    //////////////////////////////////////////////////////////////////////////
  42    //  Type alias
  43    //////////////////////////////////////////////////////////////////////////
  44    typedef Mem Super;
  45
  46 protected:
  47
  48    //////////////////////////////////////////////////////////////////////////
  49    //  Internals
  50    //////////////////////////////////////////////////////////////////////////
  51    struct Block {
  52       long  allocated;        //
  53       short right_buddies;    // Number of merges with right buddies before
  54                               // becoming one.
  55       short fib_number;       // fibonacci number of block
  56       Block * next, * last;   // links to blocks of the same size
  57    };
  58
  59    void *  my_pool;           // the starting address of the user supplied pool
  60    size_t  my_pool_size;      // size of this pool
  61    Block * begin, * end;      // beginning and end of the arena
  62    Block ** free_lists;       // an array of free lists arranged in sizes
  63    enum { levels = 32 };      // number of free lists
  64
  65    virtual void init_pool(void *, size_t);
  66
  67 public:
  68
  69    //////////////////////////////////////////////////////////////////////////
  70    //  Constructor and destructor
  71    //////////////////////////////////////////////////////////////////////////
  72    Buddy(void * pool, size_t poolSize);
  73   ~Buddy();
  74
  75    //////////////////////////////////////////////////////////////////////////
  76    //  Methods to allocate/deallocate memory
  77    //////////////////////////////////////////////////////////////////////////
  78    void * operator [] (size_t n) { return m_alloc(n); }
  79
  80    //////////////////////////////////////////////////////////////////////////
  81    //  Virtual methods for the basic protocol
  82    //////////////////////////////////////////////////////////////////////////
  83    virtual void   clear   ();
  84    virtual void * m_alloc (size_t);
  85    virtual void * c_alloc (size_t);
  86    virtual void   free    (void *);
  87    virtual size_t size    (const void *) const;
  88 };
  89
  90 #endif