Panda3D
simpleAllocator.h
1 // Filename: simpleAllocator.h
2 // Created by: drose (12May07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #ifndef SIMPLEALLOCATOR_H
16 #define SIMPLEALLOCATOR_H
17 
18 #include "pandabase.h"
19 #include "linkedListNode.h"
20 #include "pmutex.h"
21 #include "mutexHolder.h"
22 
24 
25 ////////////////////////////////////////////////////////////////////
26 // Class : SimpleAllocator
27 // Description : An implementation of a very simple block allocator.
28 // This class can allocate ranges of nonnegative
29 // integers within a specified upper limit; it uses a
30 // simple first-fit algorithm to find the next available
31 // space.
32 ////////////////////////////////////////////////////////////////////
33 class EXPCL_PANDA_GOBJ SimpleAllocator : public LinkedListNode {
34 PUBLISHED:
35  INLINE SimpleAllocator(size_t max_size, Mutex &lock);
36  virtual ~SimpleAllocator();
37 
38  INLINE SimpleAllocatorBlock *alloc(size_t size);
39 
40  INLINE bool is_empty() const;
41  INLINE size_t get_total_size() const;
42  INLINE size_t get_max_size() const;
43  INLINE void set_max_size(size_t max_size);
44  INLINE size_t get_contiguous() const;
45 
46  INLINE SimpleAllocatorBlock *get_first_block() const;
47 
48  void output(ostream &out) const;
49  void write(ostream &out) const;
50 
51 protected:
52  SimpleAllocatorBlock *do_alloc(size_t size);
53  INLINE bool do_is_empty() const;
54 
55  virtual SimpleAllocatorBlock *make_block(size_t start, size_t size);
56  INLINE void mark_contiguous(const LinkedListNode *block);
57  virtual void changed_contiguous();
58 
59 protected:
60  // This is implemented as a linked-list chain of allocated blocks.
61  // Free blocks are implicit. Blocks are kept in sorted order from
62  // beginning to end. Allocating a block means creating a new entry
63  // in the chain wherever it may fit; freeing a block means simply
64  // removing the allocated block from the chain. With this simple
65  // approach, there is no need to merge adjacent free blocks to
66  // straighten out fragmentation, since free blocks are not stored.
67  // However, it does mean we have to walk through a list of adjacent
68  // allocated blocks in order to find the free blocks.
69  size_t _total_size;
70  size_t _max_size;
71 
72  // This is what we currently believe our max contiguous space to be.
73  // This guess might be larger than the actual available space, but
74  // it will not be smaller.
75  size_t _contiguous;
76 
77  // This mutex protects all operations within this class. The caller
78  // must pass the reference to a mutex in to the constructor, and the
79  // caller remains responsible for owning the mutex. This allows the
80  // mutex to be shared where appropriate.
81 
82  // A derived class may also use it to protect itself as well, but
83  // take care to call do_alloc() instead of alloc() etc. as
84  // necessary.
85  Mutex &_lock;
86 
87  friend class SimpleAllocatorBlock;
88 };
89 
90 ////////////////////////////////////////////////////////////////////
91 // Class : SimpleAllocatorBlock
92 // Description : A single block as returned from
93 // SimpleAllocator::alloc().
94 ////////////////////////////////////////////////////////////////////
95 class EXPCL_PANDA_GOBJ SimpleAllocatorBlock : public LinkedListNode {
96 protected:
98  size_t start, size_t size);
99 
100 PUBLISHED:
101  INLINE ~SimpleAllocatorBlock();
102  INLINE void free();
103 
104  INLINE SimpleAllocator *get_allocator() const;
105 
106  INLINE size_t get_start() const;
107  INLINE size_t get_size() const;
108  INLINE bool is_free() const;
109 
110  INLINE size_t get_max_size() const;
111  INLINE bool realloc(size_t size);
112 
113  INLINE SimpleAllocatorBlock *get_next_block() const;
114 
115  void output(ostream &out) const;
116 
117 protected:
118  INLINE void do_free();
119  INLINE size_t do_get_max_size() const;
120  INLINE bool do_realloc(size_t size);
121 
122 private:
123  SimpleAllocator *_allocator;
124  size_t _start;
125  size_t _size;
126 
127  friend class SimpleAllocator;
128 };
129 
130 INLINE ostream &operator << (ostream &out, const SimpleAllocator &obj) {
131  obj.output(out);
132  return out;
133 }
134 
135 INLINE ostream &operator << (ostream &out, const SimpleAllocatorBlock &obj) {
136  obj.output(out);
137  return out;
138 }
139 
140 #include "simpleAllocator.I"
141 
142 #endif
An implementation of a very simple block allocator.
A standard mutex, or mutual exclusion lock.
Definition: pmutex.h:44
This just stores the pointers to implement a doubly-linked list of some kind of object.
A single block as returned from SimpleAllocator::alloc().