Panda3D
Loading...
Searching...
No Matches
simpleAllocator.cxx
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file simpleAllocator.cxx
10 * @author drose
11 * @date 2007-05-12
12 */
13
14#include "simpleAllocator.h"
15
16/**
17 * Move constructor.
18 */
19SimpleAllocator::
20SimpleAllocator(SimpleAllocator &&from) noexcept :
21 LinkedListNode(std::move(from)),
22 _total_size(from._total_size),
23 _max_size(from._max_size),
24 _contiguous(from._contiguous),
25 _lock(from._lock)
26{
27 MutexHolder holder(_lock);
28 from._total_size = 0;
29 from._max_size = 0;
30 from._contiguous = 0;
31
32 // We still need to leave the list in a valid state.
33 from._prev = &from;
34 from._next = &from;
35
36 // Change all the blocks to point to the new allocator.
37 LinkedListNode *next = _next;
38 while (next != this) {
40 nassertv(block->_allocator == &from);
41 block->_allocator = this;
42
43 next = block->_next;
44 }
45}
46
47/**
48 *
49 */
50SimpleAllocator::
51~SimpleAllocator() {
52 // We're shutting down. Force-free everything remaining.
53 if (_next != (LinkedListNode *)this) {
54 MutexHolder holder(_lock);
55 while (_next != (LinkedListNode *)this) {
56 nassertv(_next != nullptr);
57 ((SimpleAllocatorBlock *)_next)->do_free();
58 }
59 }
60}
61
62/**
63 *
64 */
65void SimpleAllocator::
66output(std::ostream &out) const {
67 MutexHolder holder(_lock);
68 out << "SimpleAllocator, " << _total_size << " of " << _max_size
69 << " allocated";
70}
71
72/**
73 *
74 */
75void SimpleAllocator::
76write(std::ostream &out) const {
77 MutexHolder holder(_lock);
78 out << "SimpleAllocator, " << _total_size << " of " << _max_size
79 << " allocated";
80
82 while (block->_next != this) {
83 SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next;
84
85 out << " " << *block << "\n";
86 block = next;
87 }
88}
89
90/**
91 * Allocates a new block. Returns NULL if a block of the requested size
92 * cannot be allocated.
93 *
94 * To free the allocated block, call block->free(), or simply delete the block
95 * pointer.
96 *
97 * Assumes the lock is already held.
98 */
99SimpleAllocatorBlock *SimpleAllocator::
100do_alloc(size_t size, size_t alignment) {
101 if (size > _contiguous) {
102 // Don't even bother.
103 return nullptr;
104 }
105
106 // First fit algorithm: walk through all the empty blocks until we find one
107 // that has enough room.
108
109 SimpleAllocatorBlock *block = nullptr;
110 size_t end = 0;
111 size_t best = 0;
112 if (_next != this) {
113 // We have at least one allocated block.
114 block = (SimpleAllocatorBlock *)_next;
115 end = block->_start + block->_size;
116
117 // Scan until we have reached the last allocated block.
118 while (block->_next != this) {
119 SimpleAllocatorBlock *next = (SimpleAllocatorBlock *)block->_next;
120 size_t start = end + ((alignment - end) % alignment);
121 if (start + size <= next->_start) {
122 SimpleAllocatorBlock *new_block = make_block(start, size);
123 nassertr(new_block->get_allocator() == this, nullptr);
124
125 new_block->insert_before(next);
126 _total_size += size;
127
128 if (_max_size - _total_size < _contiguous) {
129 // Since we only have (_max_size - _total_size) bytes remaining, it
130 // follows that our largest contiguous block must be no larger than
131 // this.
132 _contiguous = _max_size - _total_size;
133 changed_contiguous();
134 }
135 return new_block;
136 }
137 size_t free_size = next->_start - end;
138 if (free_size > best) {
139 best = free_size;
140 }
141
142 block = next;
143 end = block->_start + block->_size;
144 }
145 }
146
147 // No free blocks; check for room at the end.
148 size_t start = end + ((alignment - end) % alignment);
149 if (start + size <= _max_size) {
150 SimpleAllocatorBlock *new_block = make_block(start, size);
151 nassertr(new_block->get_allocator() == this, nullptr);
152
153 new_block->insert_before(this);
154 _total_size += size;
155
156 if (_max_size - _total_size < _contiguous) {
157 // Since we only have (_max_size - _total_size) bytes remaining, it
158 // follows that our largest contiguous block must be no larger than
159 // this.
160 _contiguous = _max_size - _total_size;
161 changed_contiguous();
162 }
163 return new_block;
164 }
165
166 size_t free_size = _max_size - end;
167 if (free_size > best) {
168 best = free_size;
169 }
170
171 // Now that we've walked through the entire list of blocks, we really do
172 // know accurately what the largest contiguous block is.
173 if (_contiguous != best) {
174 _contiguous = best;
175 changed_contiguous();
176 }
177
178 // No room for this block.
179 return nullptr;
180}
181
182/**
183 * Creates a new SimpleAllocatorBlock object. Override this function to
184 * specialize the block type returned.
185 */
186SimpleAllocatorBlock *SimpleAllocator::
187make_block(size_t start, size_t size) {
188 return new SimpleAllocatorBlock(this, start, size);
189}
190
191/**
192 * This callback function is made whenever the estimate of contiguous
193 * available space changes, either through an alloc or free. The lock will be
194 * held.
195 */
196void SimpleAllocator::
197changed_contiguous() {
198}
199
200/**
201 *
202 */
203void SimpleAllocatorBlock::
204output(std::ostream &out) const {
205 if (_allocator == nullptr) {
206 out << "free block\n";
207 } else {
208 MutexHolder holder(_allocator->_lock);
209 out << "block of size " << _size << " at " << _start;
210 }
211}
This just stores the pointers to implement a doubly-linked list of some kind of object.
A lightweight C++ object whose constructor calls acquire() and whose destructor calls release() on a ...
Definition mutexHolder.h:25
A single block as returned from SimpleAllocator::alloc().
SimpleAllocator * get_allocator() const
Returns the SimpleAllocator object that owns this block.
An implementation of a very simple block allocator.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.