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().