Panda3D
 All Classes Functions Variables Enumerations
simpleAllocator.h
00001 // Filename: simpleAllocator.h
00002 // Created by:  drose (12May07)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #ifndef SIMPLEALLOCATOR_H
00016 #define SIMPLEALLOCATOR_H
00017 
00018 #include "pandabase.h"
00019 #include "linkedListNode.h"
00020 #include "pmutex.h"
00021 #include "mutexHolder.h"
00022 
00023 class SimpleAllocatorBlock;
00024 
00025 ////////////////////////////////////////////////////////////////////
00026 //       Class : SimpleAllocator
00027 // Description : An implementation of a very simple block allocator.
00028 //               This class can allocate ranges of nonnegative
00029 //               integers within a specified upper limit; it uses a
00030 //               simple first-fit algorithm to find the next available
00031 //               space.
00032 ////////////////////////////////////////////////////////////////////
00033 class EXPCL_PANDA_GOBJ SimpleAllocator : public LinkedListNode {
00034 PUBLISHED:
00035   INLINE SimpleAllocator(size_t max_size, Mutex &lock);
00036   virtual ~SimpleAllocator();
00037 
00038   INLINE SimpleAllocatorBlock *alloc(size_t size);
00039 
00040   INLINE bool is_empty() const;
00041   INLINE size_t get_total_size() const;
00042   INLINE size_t get_max_size() const;
00043   INLINE void set_max_size(size_t max_size);
00044   INLINE size_t get_contiguous() const;
00045 
00046   INLINE SimpleAllocatorBlock *get_first_block() const;
00047 
00048   void output(ostream &out) const;
00049   void write(ostream &out) const;
00050 
00051 protected:
00052   SimpleAllocatorBlock *do_alloc(size_t size);
00053   INLINE bool do_is_empty() const;
00054 
00055   virtual SimpleAllocatorBlock *make_block(size_t start, size_t size);
00056   INLINE void mark_contiguous(const LinkedListNode *block);
00057   virtual void changed_contiguous();
00058 
00059 protected:
00060   // This is implemented as a linked-list chain of allocated blocks.
00061   // Free blocks are implicit.  Blocks are kept in sorted order from
00062   // beginning to end.  Allocating a block means creating a new entry
00063   // in the chain wherever it may fit; freeing a block means simply
00064   // removing the allocated block from the chain.  With this simple
00065   // approach, there is no need to merge adjacent free blocks to
00066   // straighten out fragmentation, since free blocks are not stored.
00067   // However, it does mean we have to walk through a list of adjacent
00068   // allocated blocks in order to find the free blocks.
00069   size_t _total_size;
00070   size_t _max_size;
00071 
00072   // This is what we currently believe our max contiguous space to be.
00073   // This guess might be larger than the actual available space, but
00074   // it will not be smaller.
00075   size_t _contiguous;
00076 
00077   // This mutex protects all operations within this class.  The caller
00078   // must pass the reference to a mutex in to the constructor, and the
00079   // caller remains responsible for owning the mutex.  This allows the
00080   // mutex to be shared where appropriate.
00081 
00082   // A derived class may also use it to protect itself as well, but
00083   // take care to call do_alloc() instead of alloc() etc. as
00084   // necessary.
00085   Mutex &_lock;
00086 
00087   friend class SimpleAllocatorBlock;
00088 };
00089 
00090 ////////////////////////////////////////////////////////////////////
00091 //       Class : SimpleAllocatorBlock
00092 // Description : A single block as returned from
00093 //               SimpleAllocator::alloc().
00094 ////////////////////////////////////////////////////////////////////
00095 class EXPCL_PANDA_GOBJ SimpleAllocatorBlock : public LinkedListNode {
00096 protected:
00097   INLINE SimpleAllocatorBlock(SimpleAllocator *alloc,
00098                               size_t start, size_t size);
00099 
00100 PUBLISHED:
00101   INLINE ~SimpleAllocatorBlock();
00102   INLINE void free();
00103 
00104   INLINE SimpleAllocator *get_allocator() const;
00105 
00106   INLINE size_t get_start() const;
00107   INLINE size_t get_size() const;
00108   INLINE bool is_free() const;
00109 
00110   INLINE size_t get_max_size() const;
00111   INLINE bool realloc(size_t size);
00112 
00113   INLINE SimpleAllocatorBlock *get_next_block() const;
00114 
00115   void output(ostream &out) const;
00116 
00117 protected:
00118   INLINE void do_free();
00119   INLINE size_t do_get_max_size() const;
00120   INLINE bool do_realloc(size_t size);
00121 
00122 private:
00123   SimpleAllocator *_allocator;
00124   size_t _start;
00125   size_t _size;
00126 
00127   friend class SimpleAllocator;
00128 };
00129 
00130 INLINE ostream &operator << (ostream &out, const SimpleAllocator &obj) {
00131   obj.output(out);
00132   return out;
00133 }
00134 
00135 INLINE ostream &operator << (ostream &out, const SimpleAllocatorBlock &obj) {
00136   obj.output(out);
00137   return out;
00138 }
00139 
00140 #include "simpleAllocator.I"
00141 
00142 #endif
 All Classes Functions Variables Enumerations