PLearn 0.1
Public Types | Public Member Functions | Private Member Functions | Private Attributes
PLearn::ArrayAllocator< T, SizeBits > Class Template Reference

#include <ArrayAllocator.h>

Collaboration diagram for PLearn::ArrayAllocator< T, SizeBits >:
Collaboration graph
[legend]

List of all members.

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_typederefIndex (index_type i)
 Small utility.
index_typederefIndex (unsigned i)

Private Attributes

vector< T > arr
index_type free_root
ArrayAllocatorOptions options

Detailed Description

template<class T, unsigned SizeBits>
class PLearn::ArrayAllocator< T, SizeBits >

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.


Member Typedef Documentation

template<class T, unsigned SizeBits>
typedef const T* PLearn::ArrayAllocator< T, SizeBits >::const_pointer

Definition at line 148 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef const T& PLearn::ArrayAllocator< T, SizeBits >::const_reference

Definition at line 150 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef ptrdiff_t PLearn::ArrayAllocator< T, SizeBits >::difference_type

Definition at line 145 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef unsigned PLearn::ArrayAllocator< T, SizeBits >::index_base

Definition at line 142 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef ArrayAllocatorIndex<index_base, SizeBits> PLearn::ArrayAllocator< T, SizeBits >::index_type

Definition at line 143 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef T* PLearn::ArrayAllocator< T, SizeBits >::pointer

Definition at line 147 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef T& PLearn::ArrayAllocator< T, SizeBits >::reference

Definition at line 149 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef ArrayAllocator<T,SizeBits> PLearn::ArrayAllocator< T, SizeBits >::self_type

Definition at line 140 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef size_t PLearn::ArrayAllocator< T, SizeBits >::size_type

Definition at line 144 of file ArrayAllocator.h.

template<class T, unsigned SizeBits>
typedef T PLearn::ArrayAllocator< T, SizeBits >::value_type

Definition at line 141 of file ArrayAllocator.h.


Constructor & Destructor Documentation

template<class T , unsigned SizeBits>
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().

    : arr(0), free_root(0,0), options(opt)
{
    resize(options.numObjs());
}

Here is the call graph for this function:


Member Function Documentation

template<class T , unsigned SizeBits>
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;                                
}

Here is the call graph for this function:

template<class T , unsigned SizeBits>
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.

template<class T , unsigned SizeBits>
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;
    }
}

Here is the call graph for this function:

template<class T, unsigned SizeBits>
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];
    }
template<class T, unsigned SizeBits>
index_type& PLearn::ArrayAllocator< T, SizeBits >::derefIndex ( unsigned  i) [inline, private]

Definition at line 181 of file ArrayAllocator.h.

References i.

                                       {
        return (index_type&)arr[i];
    }
template<class T, unsigned SizeBits>
size_type PLearn::ArrayAllocator< T, SizeBits >::max_size ( ) const [inline]

Definition at line 164 of file ArrayAllocator.h.

                               {
        return arr.size();
    }
template<class T , unsigned SizeBits>
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;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T , unsigned SizeBits>
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().

{
    swap(arr, other.arr);
    swap(free_root, other.free_root);
}

Here is the call graph for this function:

template<class T , unsigned SizeBits>
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);
}
template<class T , unsigned SizeBits>
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().

{
    if (i.isNull())
        return 0;
    else
        return &arr[0] + i.index;
}

Here is the call graph for this function:


Member Data Documentation

template<class T, unsigned SizeBits>
vector<T> PLearn::ArrayAllocator< T, SizeBits >::arr [private]

Definition at line 186 of file ArrayAllocator.h.

Referenced by PLearn::ArrayAllocator< T, SizeBits >::swap().

template<class T, unsigned SizeBits>
index_type PLearn::ArrayAllocator< T, SizeBits >::free_root [private]

Definition at line 187 of file ArrayAllocator.h.

Referenced by PLearn::ArrayAllocator< T, SizeBits >::swap().

template<class T, unsigned SizeBits>
ArrayAllocatorOptions PLearn::ArrayAllocator< T, SizeBits >::options [private]

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines