tango.util.container.Container

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release Jan 2009: Added GCChunk allocator

Authors:

Kris, schveiguy

Since:

0.99.7
struct Container #
Utility functions and constants
size_t defaultInitialBuckets [static] #
default initial number of buckets of a non-empty hashmap
float defaultLoadFactor [static] #
default load factor for a non-empty hashmap. The hash table is resized when the proportion of elements per buckets exceeds this limit
void reap(V)(V v) [static] #
generic value reaper, which does nothing
void reap(K, V)(K k, V v) [static] #
generic key/value reaper, which does nothing
size_t hash(K)(K k, size_t length) [static] #
generic hash function, using the default hashing. Thanks to 'mwarning' for the optimization suggestion
struct Collect(T) #
generic GC allocation manager
T* allocate() #
allocate a T sized memory chunk
T*[] allocate(size_t count) #
allocate an array of T sized memory chunks
void collect(T* p) #
Invoked when a specific T[] is discarded
void collect(T*[] t) #
Invoked when a specific T[] is discarded
bool collect(bool all = true) #
Invoked when clear/reset is called on the host. This is a shortcut to clear everything allocated. Should return true if supported, or false otherwise. False return will cause a series of discrete collect calls
struct Malloc(T) #
Malloc allocation manager.
Note that, due to GC behaviour, you should not configure a custom allocator for containers holding anything managed by the GC. For example, you cannot use a MallocAllocator to manage a container of classes or strings where those were allocated by the GC. Once something is owned by a GC then it's lifetime must be managed by GC-managed entities (otherwise the GC may think there are no live references and prematurely collect container contents). You can explicity manage the collection of keys and values yourself by providing a reaper delegate. For example, if you use a MallocAllocator to manage key/value pairs which are themselves allocated via malloc, then you should also provide a reaper delegate to collect those as required.
T* allocate() #
allocate an array of T sized memory chunks
T*[] allocate(size_t count) #
allocate an array of T sized memory chunks
void collect(T*[] t) #
Invoked when a specific T[] is discarded
void collect(T* p) #
Invoked when a specific T[] is discarded
bool collect(bool all = true) #
Invoked when clear/reset is called on the host. This is a shortcut to clear everything allocated. Should return true if supported, or false otherwise. False return will cause a series of discrete collect calls
struct Chunk(T) #
Chunk allocator
Can save approximately 30% memory for small elements (tested with integer elements and a chunk size of 1000), and is at least twice as fast at adding elements when compared to the default allocator (approximately 50x faster with LinkedList) Note that, due to GC behaviour, you should not configure a custom allocator for containers holding anything managed by the GC. For example, you cannot use a MallocAllocator to manage a container of classes or strings where those were allocated by the GC. Once something is owned by a GC then it's lifetime must be managed by GC-managed entities (otherwise the GC may think there are no live references and prematurely collect container contents). You can explicity manage the collection of keys and values yourself by providing a reaper delegate. For example, if you use a MallocAllocator to manage key/value pairs which are themselves allocated via malloc, then you should also provide a reaper delegate to collect those as required.
void config(size_t chunks, size_t presize) #
set the chunk size and preallocate lists
T* allocate() #
allocate an array of T sized memory chunks
T*[] allocate(size_t count) #
allocate an array of T sized memory chunks
void collect(T*[] t) #
Invoked when a specific T[] is discarded
void collect(T* p) #
Invoked when a specific T is discarded
bool collect(bool all = true) #
Invoked when clear/reset is called on the host. This is a shortcut to clear everything allocated. Should return true if supported, or false otherwise. False return will cause a series of discrete collect calls
void newlist() [private] #
list manager
T[] block() [private] #
list allocator
struct GCChunk(T, uint chunkSize) #
GCChunk allocator
Like the Chunk allocator, this allocates elements in chunks, but allows you to allocate elements that can have GC pointers.

Tests have shown about a 60% speedup when using the GC chunk allocator for a Hashmap!(int, int).

struct element #
This is the form used to link recyclable elements together.
struct chunk #
A chunk of elements
chunk * next #
The next chunk in the chain
chunk * prev #
The previous chunk in the chain. Required for O(1) removal from the chain.
element * freeList #
The linked list of free elements in the chunk. This list is amended each time an element in this chunk is freed.
uint numFree #
The number of free elements in the freeList. Used to determine whether this chunk can be given back to the GC
T[chunkSize] elems #
The elements in the chunk.
T * allocateFromFree() #
Allocate a T* from the free list.
bool deallocate(T * t) #
deallocate a T*, send it to the free list
returns true if this chunk no longer has any used elements.
chunk * used #
The chain of used chunks. Used chunks have had all their elements allocated at least once.
chunk * fresh #
The fresh chunk. This is only used if no elements are available in the used chain.
uint nextFresh #
The next element in the fresh chunk. Because we don't worry about the free list in the fresh chunk, we need to keep track of the next fresh element to use.
T* allocate() #
Allocate a T*
void collect(T* t) #
free a T*
bool collect(bool all = true) #
Deallocate all chunks used by this allocator. Depends on the GC to do the actual collection
template DefaultCollect(T) #
aliases to the correct Default allocator depending on how big the type is. It makes less sense to use a GCChunk allocator if the type is going to be larger than a page (currently there is no way to get the page size from the GC, so we assume 4096 bytes). If not more than one unit can fit into a page, then we use the default GC allocator.