Panda3D
|
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