Panda3D
 All Classes Functions Variables Enumerations
simpleAllocator.cxx
1 // Filename: simpleAllocator.cxx
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 #include "simpleAllocator.h"
16 
17 ////////////////////////////////////////////////////////////////////
18 // Function: SimpleAllocator::Destructor
19 // Access: Published, Virtual
20 // Description:
21 ////////////////////////////////////////////////////////////////////
22 SimpleAllocator::
23 ~SimpleAllocator() {
24  // We're shutting down. Force-free everything remaining.
25  if (_next != (LinkedListNode *)this) {
26  MutexHolder holder(_lock);
27  while (_next != (LinkedListNode *)this) {
28  nassertv(_next != (LinkedListNode *)NULL);
29  ((SimpleAllocatorBlock *)_next)->do_free();
30  }
31  }
32 }
33 
34 ////////////////////////////////////////////////////////////////////
35 // Function: SimpleAllocator::output
36 // Access: Published
37 // Description:
38 ////////////////////////////////////////////////////////////////////
39 void SimpleAllocator::
40 output(ostream &out) const {
41  MutexHolder holder(_lock);
42  out << "SimpleAllocator, " << _total_size << " of " << _max_size
43  << " allocated";
44 }
45 
46 ////////////////////////////////////////////////////////////////////
47 // Function: SimpleAllocator::write
48 // Access: Published
49 // Description:
50 ////////////////////////////////////////////////////////////////////
51 void SimpleAllocator::
52 write(ostream &out) const {
53  MutexHolder holder(_lock);
54  out << "SimpleAllocator, " << _total_size << " of " << _max_size
55  << " allocated";
56 
58  while (block->_next != this) {
59  SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next;
60 
61  out << " " << *block << "\n";
62  block = next;
63  }
64 }
65 
66 ////////////////////////////////////////////////////////////////////
67 // Function: SimpleAllocator::do_alloc
68 // Access: Protected
69 // Description: Allocates a new block. Returns NULL if a block of the
70 // requested size cannot be allocated.
71 //
72 // To free the allocated block, call block->free(), or
73 // simply delete the block pointer.
74 //
75 // Assumes the lock is already held.
76 ////////////////////////////////////////////////////////////////////
77 SimpleAllocatorBlock *SimpleAllocator::
78 do_alloc(size_t size) {
79  if (size > _contiguous) {
80  // Don't even bother.
81  return NULL;
82  }
83 
84  // First fit algorithm: walk through all the empty blocks until we
85  // find one that has enough room.
86 
87  SimpleAllocatorBlock *block = NULL;
88  size_t end = 0;
89  size_t best = 0;
90  if (_next != this) {
91  // We have at least one allocated block.
92  block = (SimpleAllocatorBlock *)_next;
93  end = block->_start + block->_size;
94 
95  // Scan until we have reached the last allocated block.
96  while (block->_next != this) {
97  SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next;
98  size_t free_size = next->_start - end;
99  if (size <= free_size) {
100  SimpleAllocatorBlock *new_block = make_block(end, size);
101  nassertr(new_block->get_allocator() == this, NULL);
102 
103  new_block->insert_before(next);
104  _total_size += size;
105 
106  if (_max_size - _total_size < _contiguous) {
107  // Since we only have (_max_size - _total_size) bytes
108  // remaining, it follows that our largest contiguous block
109  // must be no larger than this.
110  _contiguous = _max_size - _total_size;
111  changed_contiguous();
112  }
113  return new_block;
114  }
115  if (free_size > best) {
116  best = free_size;
117  }
118 
119  block = next;
120  end = block->_start + block->_size;
121  }
122  }
123 
124  // No free blocks; check for room at the end.
125  size_t free_size = _max_size - end;
126  if (size <= free_size) {
127  SimpleAllocatorBlock *new_block = make_block(end, size);
128  nassertr(new_block->get_allocator() == this, NULL);
129 
130  new_block->insert_before(this);
131  _total_size += size;
132 
133  if (_max_size - _total_size < _contiguous) {
134  // Since we only have (_max_size - _total_size) bytes
135  // remaining, it follows that our largest contiguous block
136  // must be no larger than this.
137  _contiguous = _max_size - _total_size;
138  changed_contiguous();
139  }
140  return new_block;
141  }
142 
143  if (free_size > best) {
144  best = free_size;
145  }
146 
147  // Now that we've walked through the entire list of blocks, we
148  // really do know accurately what the largest contiguous block is.
149  if (_contiguous != best) {
150  _contiguous = best;
151  changed_contiguous();
152  }
153 
154  // No room for this block.
155  return NULL;
156 }
157 
158 ////////////////////////////////////////////////////////////////////
159 // Function: SimpleAllocator::make_block
160 // Access: Protected, Virtual
161 // Description: Creates a new SimpleAllocatorBlock object. Override
162 // this function to specialize the block type returned.
163 ////////////////////////////////////////////////////////////////////
164 SimpleAllocatorBlock *SimpleAllocator::
165 make_block(size_t start, size_t size) {
166  return new SimpleAllocatorBlock(this, start, size);
167 }
168 
169 ////////////////////////////////////////////////////////////////////
170 // Function: SimpleAllocator::changed_contiguous
171 // Access: Protected, Virtual
172 // Description: This callback function is made whenever the estimate
173 // of contiguous available space changes, either through
174 // an alloc or free. The lock will be held.
175 ////////////////////////////////////////////////////////////////////
176 void SimpleAllocator::
177 changed_contiguous() {
178 }
179 
180 ////////////////////////////////////////////////////////////////////
181 // Function: SimpleAllocatorBlock::output
182 // Access: Published
183 // Description:
184 ////////////////////////////////////////////////////////////////////
185 void SimpleAllocatorBlock::
186 output(ostream &out) const {
187  if (_allocator == (SimpleAllocator *)NULL) {
188  out << "free block\n";
189  } else {
190  MutexHolder holder(_allocator->_lock);
191  out << "block of size " << _size << " at " << _start;
192  }
193 }
An implementation of a very simple block allocator.
A lightweight C++ object whose constructor calls acquire() and whose destructor calls release() on a ...
Definition: mutexHolder.h:29
This just stores the pointers to implement a doubly-linked list of some kind of object.
A single block as returned from SimpleAllocator::alloc().
SimpleAllocator * get_allocator() const
Returns the SimpleAllocator object that owns this block.