|
PLearn 0.1
|
#include <ArrayAllocator.h>

Public Types | |
| typedef ArrayAllocator< T, SizeBits > | self_type |
| typedef T | value_type |
| typedef unsigned | index_base |
| typedef ArrayAllocatorIndex < index_base, SizeBits > | index_type |
| typedef size_t | size_type |
| typedef ptrdiff_t | difference_type |
| typedef T * | pointer |
| typedef const T * | const_pointer |
| typedef T & | reference |
| typedef const T & | const_reference |
Public Member Functions | |
| ArrayAllocator (const ArrayAllocatorOptions &) | |
| pointer | allocate (size_t n) |
| default copy constructor, destructor, assignment operator | |
| void | deallocate (pointer p, size_type n) |
| Deallocate given pointer/size, or given index only. | |
| void | deallocate (index_type) |
| void | resize (size_type NewMaxObjs) |
| size_type | max_size () const |
| index_type | toIndex (pointer p, size_type n) |
| Index/pointer conversion. | |
| pointer | toPointer (index_type) |
| void | swap (self_type &) |
Private Member Functions | |
| index_type & | derefIndex (index_type i) |
| Small utility. | |
| index_type & | derefIndex (unsigned i) |
Private Attributes | |
| vector< T > | arr |
| index_type | free_root |
| ArrayAllocatorOptions | options |
This class provides an allocator interface for objects of type T. A maximum of InitialObjs (specified upon construction) can be maintained by the allocator. Arrays of such objects are supported; the maximum length of an array of objects (in bits) is given by the SizeBits template argument.
Furthermore, the maximum number of objects that can be stored (in bits) is 8 * sizeof(index_base) - SizeBits, where 8*sizeof(index_base) is usually 32 for most computers. Hence, if arrays of a maximum size of 256 elements are to be stored (8 bits), then only 16777216 elements can be allocated.
Internally, index number 0 is reserved to denote a null pointer, and not otherwise used in the array.
The free list is represented as follows: the variable free_root represents the index of the first free block (the size field of free_root is not used). In the memory location at that index, we assume that we have an index_type structure (instead of a T), and this index_type contains two things: the index of the next free block (or zero if none), along with the size of the current free block.
Definition at line 137 of file ArrayAllocator.h.
| typedef const T* PLearn::ArrayAllocator< T, SizeBits >::const_pointer |
Definition at line 148 of file ArrayAllocator.h.
| typedef const T& PLearn::ArrayAllocator< T, SizeBits >::const_reference |
Definition at line 150 of file ArrayAllocator.h.
| typedef ptrdiff_t PLearn::ArrayAllocator< T, SizeBits >::difference_type |
Definition at line 145 of file ArrayAllocator.h.
| typedef unsigned PLearn::ArrayAllocator< T, SizeBits >::index_base |
Definition at line 142 of file ArrayAllocator.h.
| typedef ArrayAllocatorIndex<index_base, SizeBits> PLearn::ArrayAllocator< T, SizeBits >::index_type |
Definition at line 143 of file ArrayAllocator.h.
| typedef T* PLearn::ArrayAllocator< T, SizeBits >::pointer |
Definition at line 147 of file ArrayAllocator.h.
| typedef T& PLearn::ArrayAllocator< T, SizeBits >::reference |
Definition at line 149 of file ArrayAllocator.h.
| typedef ArrayAllocator<T,SizeBits> PLearn::ArrayAllocator< T, SizeBits >::self_type |
Definition at line 140 of file ArrayAllocator.h.
| typedef size_t PLearn::ArrayAllocator< T, SizeBits >::size_type |
Definition at line 144 of file ArrayAllocator.h.
| typedef T PLearn::ArrayAllocator< T, SizeBits >::value_type |
Definition at line 141 of file ArrayAllocator.h.
| PLearn::ArrayAllocator< T, SizeBits >::ArrayAllocator | ( | const ArrayAllocatorOptions & | opt | ) |
Definition at line 196 of file ArrayAllocator.h.
References PLearn::ArrayAllocatorOptions::numObjs, PLearn::ArrayAllocator< T, SizeBits >::options, and PLearn::ArrayAllocator< T, SizeBits >::resize().

| ArrayAllocator< T, SizeBits >::pointer PLearn::ArrayAllocator< T, SizeBits >::allocate | ( | size_t | n | ) |
default copy constructor, destructor, assignment operator
Allocate N objects of type T and return a (memory) pointer to it
Take a look at the block pointed to by free_pointer, and if it's big enough, take a chunk from the BEGINNING, and modify *free_pointer to point to the next correct free block
< could not allocate
Definition at line 237 of file ArrayAllocator.h.
References if(), PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::index, PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::isNull(), PLERROR, and PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::size.
{
index_type *free_pointer = &free_root;
while (free_pointer && !free_pointer->isNull()) {
unsigned size = derefIndex(*free_pointer).size;
if (size < n)
free_pointer = &derefIndex(*free_pointer);
else
if (size == n) {
pointer p = toPointer(*free_pointer);
*free_pointer = index_type(derefIndex(*free_pointer).index,
free_pointer->size);
return p;
}
else {
pointer p = toPointer(*free_pointer);
derefIndex(free_pointer->index + n) =
index_type(derefIndex(*free_pointer).index, size - n);
*free_pointer = index_type(free_pointer->index + n,
free_pointer->size);
return p;
}
}
PLERROR("Could not allocate; size of memory pool exhausted\n%s\n",
(typeid(*this).name()));
return 0;
}

| void PLearn::ArrayAllocator< T, SizeBits >::deallocate | ( | pointer | p, |
| size_type | n | ||
| ) |
Deallocate given pointer/size, or given index only.
Definition at line 273 of file ArrayAllocator.h.
{
deallocate(index_type(p,n));
}
| void PLearn::ArrayAllocator< T, SizeBits >::deallocate | ( | index_type | i | ) |
The current code is frankly not too object-oriented...
Null deallocator: do nothing
Unsorted deallocator: just add block to free list; don't collapse adjacent free blocks
Not implemented yet...
Definition at line 280 of file ArrayAllocator.h.
References PLearn::ArrayAllocatorOptions::DeallocatorNull, PLearn::ArrayAllocatorOptions::DeallocatorSorted, PLearn::ArrayAllocatorOptions::DeallocatorUnsorted, PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::index, PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::isNull(), PLERROR, and PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::size.
{
switch(options.deallocatorType()) {
case ArrayAllocatorOptions::DeallocatorNull :
break;
case ArrayAllocatorOptions::DeallocatorUnsorted :
if (! i.isNull()) {
derefIndex(i) = index_type(free_root.index, i.size);
free_root.index = i.index;
}
break;
case ArrayAllocatorOptions::DeallocatorSorted :
PLERROR("ArrayAllocator: the sorted deallocator is not currently "
"implemented");
break;
}
}

| index_type& PLearn::ArrayAllocator< T, SizeBits >::derefIndex | ( | index_type | i | ) | [inline, private] |
Small utility.
Definition at line 178 of file ArrayAllocator.h.
References PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::index.
{
return (index_type&)arr[i.index];
}
| index_type& PLearn::ArrayAllocator< T, SizeBits >::derefIndex | ( | unsigned | i | ) | [inline, private] |
| size_type PLearn::ArrayAllocator< T, SizeBits >::max_size | ( | ) | const [inline] |
Definition at line 164 of file ArrayAllocator.h.
{
return arr.size();
}
| void PLearn::ArrayAllocator< T, SizeBits >::resize | ( | size_type | NewMaxObjs | ) |
Since the maximum block size is limited to SizeBits, we cannot create a single big new free region with the new objects; instead, we must create several free regions of maximum size and link them together in the free list.
zero is not a valid starting index
Definition at line 204 of file ArrayAllocator.h.
References PLearn::max(), PLearn::min(), and PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::size.
Referenced by PLearn::ArrayAllocator< T, SizeBits >::ArrayAllocator().
{
size_t next_free_block = arr.size();
if (new_max_objs <= next_free_block)
return;
next_free_block = max(1,int(next_free_block));
arr.resize(new_max_objs);
index_type dummy(unsigned(-1), unsigned(-1));
size_t max_block_size = dummy.size;
while (next_free_block < new_max_objs) {
size_t block_size = min(max_block_size, new_max_objs - next_free_block);
index_type new_index(free_root.index, block_size);
derefIndex(next_free_block) = new_index;
free_root = index_type(next_free_block,0);
next_free_block += block_size;
}
}


| void PLearn::ArrayAllocator< T, SizeBits >::swap | ( | self_type & | other | ) |
Definition at line 329 of file ArrayAllocator.h.
References PLearn::ArrayAllocator< T, SizeBits >::arr, PLearn::ArrayAllocator< T, SizeBits >::free_root, and PLearn::swap().

| ArrayAllocator< T, SizeBits >::index_type PLearn::ArrayAllocator< T, SizeBits >::toIndex | ( | pointer | p, |
| size_type | n | ||
| ) | [inline] |
Index/pointer conversion.
Definition at line 308 of file ArrayAllocator.h.
{
if (p)
return index_type(p-&arr[0], n);
else
return index_type(0,0);
}
| ArrayAllocator< T, SizeBits >::pointer PLearn::ArrayAllocator< T, SizeBits >::toPointer | ( | index_type | i | ) | [inline] |
Definition at line 319 of file ArrayAllocator.h.
References PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::index, and PLearn::ArrayAllocatorIndex< IndexBase, SizeBits >::isNull().

vector<T> PLearn::ArrayAllocator< T, SizeBits >::arr [private] |
Definition at line 186 of file ArrayAllocator.h.
Referenced by PLearn::ArrayAllocator< T, SizeBits >::swap().
index_type PLearn::ArrayAllocator< T, SizeBits >::free_root [private] |
Definition at line 187 of file ArrayAllocator.h.
Referenced by PLearn::ArrayAllocator< T, SizeBits >::swap().
ArrayAllocatorOptions PLearn::ArrayAllocator< T, SizeBits >::options [private] |
Definition at line 188 of file ArrayAllocator.h.
Referenced by PLearn::ArrayAllocator< T, SizeBits >::ArrayAllocator().
1.7.4