dstats.alloc

T[] newVoid (T)(size_t length);

Returns a new array of type T w/o initializing elements.

void lengthVoid (T)(ref T[] input, size_t newLength);

Lengthens an array w/o initializing new elements.

void appendDelOld (T, U)(ref T[] to, U from);

Appends to an array, deleting the old array if it has to be realloced.

struct TempAlloc ;

A struct to allocate memory in a strictly first-in last-out order for things like scratch space. Technically, memory can safely escape the scope in which it was allocated. However, this is a very bad idea unless being done within the private API of a class, struct or nested function, where it can be guaranteed that LIFO will not be violated.

Under the hood, this works by allocating large blocks (currently 4 MB) from the GC, and sub-allocating these as a stack. Very large allocations (currently > 4MB) are simply performed on the heap. There are two ways to free memory: Calling TempAlloc .free() frees the last allocated block. Calling TempAlloc .frameFree() frees all memory allocated since the last call to TempAlloc .frameInit().

All allocations are aligned on 16-byte boundaries using padding, since on x86, 16-byte alignment is necessary to make SSE2 work. Note, however, that this is implemented based on the assumption that the GC allocates using 16-byte alignment (which appears to be true in druntime.)

static State getState ();

Allows caller to cache the state class on the stack and pass it in as a parameter. This is ugly, but results in a speed boost that can be significant in some cases because it avoids a thread-local storage lookup. Also used internally.

static State frameInit ();

Initializes a frame, i.e. marks the current allocation position. Memory past the position at which this was last called will be freed when frameFree() is called. Returns a reference to the State class in case the caller wants to cache it for speed.

static State frameInit (State stateCopy);

Same as frameInit () but uses stateCopy cached on stack by caller to avoid a thread-local storage lookup. Strictly a speed hack.

static void frameFree ();

Frees all memory allocated by TempAlloc since the last call to frameInit().

static void frameFree (State stateCopy);

Same as frameFree () but uses stateCopy cached on stack by caller to avoid a thread-local storage lookup. Strictly a speed hack.

void* opCall (T...)(T args);

Purely a convenience overload, forwards arguments to TempAlloc.malloc().

static void* malloc (size_t nbytes);

Allocates nbytes bytes on the TempAlloc stack. NOT safe for real-time programming, since if there's not enough space on the current block, a new one will automatically be created. Also, very large objects (currently over 4MB) will simply be heap-allocated.

BUGS:
Memory allocated by TempAlloc is not scanned by the GC. This is necessary for performance and to avoid false pointer issues. Do not store the only reference to a GC-allocated object in TempAlloc-allocated memory.

static void* malloc (size_t nbytes, State stateCopy);

Same as malloc () but uses stateCopy cached on stack by caller to avoid a thread-local storage lookup. Strictly a speed hack.

static void free ();

Frees the last piece of memory allocated by TempAlloc. Since all memory must be allocated and freed in strict LIFO order, there's no need to pass a pointer in. All bookkeeping for figuring out what to free is done internally.

static void free (State stateCopy);

Same as free () but uses stateCopy cached on stack by caller to avoid a thread-local storage lookup. Strictly a speed hack.

static @property size_t slack ();

Returns how many bytes are available in the current frame.

T[] newStack (T)(size_t size, TempAlloc.State state = null);

Allocates an array of type T and size size using TempAlloc. Note that appending to this array using the ~= operator, or enlarging it using the .length property, will result in undefined behavior. This is because, if the array is located at the beginning of a TempAlloc block, the GC will think the capacity is as large as a TempAlloc block, and will overwrite adjacent TempAlloc-allocated data, instead of reallocating it.

BUGS:
Do not store the only reference to a GC-allocated reference object in an array allocated by newStack because this memory is not scanned by the GC.

T[0] stackCat (T...)(T data);

**Same as newStack(size_t) but uses stateCopy cached on stack by caller Concatenate any number of arrays of the same type, placing results on the TempAlloc stack.

Unqual!(ElementType!(T))[] tempdup (T)(T data);

Creates a duplicate of a range for temporary use within a function in the best wsy that can be done safely. If ElementType!(T) is a value type or T is an array, the results can safely be placed in TempAlloc because either it doesn't need to be scanned by the GC or there's guaranteed to be another reference to the contents somewhere. Otherwise, the results are placed on the GC heap.

This function is much faster if T has a length, but works even if it doesn't.

immutable char[] newFrame ;

A string to mixin at the beginning of a scope, purely for convenience. Initializes a TempAlloc frame using frameInit(), and inserts a scope statement to delete this frame at the end of the current scope.

Slower than calling free() manually when only a few pieces of memory will be allocated in the current scope, due to the extra bookkeeping involved. Can be faster, however, when large amounts of allocations, such as arrays of arrays, are allocated, due to caching of data stored in thread-local storage.

struct HashRange (K,S,bool vals = false);

Forward range struct for iterating over the keys or values of a StackHash or StackSet. The lifetime of this object must not exceed that of the underlying StackHash or StackSet.

void popFront ();

Unqual!(K) front ();

bool empty ();

size_t length ();

typeof(this) save ();

struct StackHash (K,V);

A hash table that allocates its memory on TempAlloc. Good for building a temporary hash tables that will not escape the current scope.

To avoid TempAlloc memory leaks, use mixin(newFrame).

Examples:

 mixin(newFrame);  // To make sure all memory gets freed at end of scope.
 auto ss = StackHash!(uint)(5);
 foreach(i; 0..5) {
     ss[i]++;
 }
 assert(ss[3] == 1);

Warning:
This implementation places removed nodes on an internal free list and recycles them, since there is no way to delete TempAlloc-allocated data in a non-LIFO order. Therefore, you may not retain the address of a variable stored in a StackHash after deleting it from the StachHash. For example, DO NOT do this:

 SomeType* myPtr = &(myStackHash["foo"]);
 myStackHash.remove("foo");
 *myPtr = someValue;

__ctor ;

Due to the nature of TempAlloc, you must specify on object creation the approximate number of elements your table will have. Too large a number will waste space and incur poor cache performance. Too low a number will make this struct perform like a linked list. Generally, if you're building a table from some other range, some fraction of the size of that range is a good guess.

V opIndex (K key);

Index an element of the range. If it does not exist, it will be created and initialized to V.init.

V opIndexAssign (V val, K key);

V* opIn_r (K key);

void remove (K key);

HashRange!(K,StackHash!(K,V)) keys ();

Returns a forward range to iterate over the keys of this table. The lifetime of the HashRange must not exceed the lifetime of this StackHash.

HashRange!(V,StackHash!(K,V),true) values ();

Returns a forward range to iterate over the values of this table. The lifetime of the HashRange must not exceed the lifetime of this StackHash.

const size_t length ();

V get (K key, lazy V defaultValue);

Attempt to look up a key and return a default value if the key is not present.

struct StackSet (K);

A hash set that allocates its memory on TempAlloc. Good for building a temporary set that will not escape the current scope.

To avoid TempAlloc memory leaks, use mixin(newFrame).

Examples:

 mixin(newFrame);  // To make sure all memory gets freed at end of scope.
 auto ss = StackSet!(uint)(5);
 foreach(i; 0..5) {
     ss.insert(i);
 }
 assert(3 in ss);

__ctor ;

Due to the nature of TempAlloc, you must specify on object creation the approximate number of elements your set will have. Too large a number will waste space and incur poor cache performance. Too low a number will make this struct perform like a linked list. Generally, if you're building a set from some other range, some fraction of the size of that range is a good guess.

void insert (K key);

HashRange!(K,typeof(this)) elems ();

Returns a forward range of the elements of this struct. The range's lifetime must not exceed the lifetime of this object.

bool opIn_r (K key);

void remove (K key);

size_t length ();

struct StackTree (T,alias key = "a",alias compFun = "a < b");

An AVL tree implementation on top of TempAlloc. If elements are removed, they are stored on an internal free list and recycled when new elements are added to the tree.

Template paramters:

T = The type to be stored in the tree.

key = Function to access the key that what you're storing is to be compared on.

compFun = The function for comparing keys.

Examples:

 struct StringNum {
     string someString;
     uint num;
 }

 // Create a StackTree of StringNums, sorted in descending order, using
 // someString for comparison.
 auto myTree = StackTree!(StringNum, "a.someString", "a > b")();

 // Add some elements.
 myTree.insert( StringNum("foo", 1));
 myTree.insert( StringNum("bar", 2));
 myTree.insert( StringNum("foo", 3));

 assert(myTree.find("foo") == StringNum("foo", 3));
 assert(myTree.find("bar") == StringNum("bar", 2));

Note:
This tree supports a compile-time interface similar to StackSet and can be used as a finite set implementation.

Warning:
This implementation places removed nodes on an internal free list and recycles them, since there is no way to delete TempAlloc-allocated data in a non-LIFO order. Therefore, you may not retain the address of a variable stored in a StackTree after deleting it from the StackTree . For example, DO NOT do this:

 SomeType* myPtr = "foo" in myTree;
 myTree.remove("foo");
 *myPtr = someValue;

typeof(this) opCall ();

De facto constructor. Not using a "real" c'tor only because structs don't support default c'tors yet. This must be called, or else you will get an access violation when you try to insert an element.

void insert (T toInsert);

Insert an element.

template remove (U)

Remove an element from this tree. The type of U is expected to be the type of the key that this tree is sorted on.

void remove (U whatToRemove);

Remove an element from this tree. The type of U is expected to be the type of the key that this tree is sorted on.

template find (U)

Find an element and return it. Throw an exception if it is not present. U is expected to be the type of the key that this tree is sorted on.

T find (U whatToFind);

Find an element and return it. Throw an exception if it is not present. U is expected to be the type of the key that this tree is sorted on.

template opIn_r (U)

Find an element and return a pointer to it, or null if not present.

T* opIn_r (U whatToFind);

Find an element and return a pointer to it, or null if not present.

int opApply (int delegate(ref T) dg);

Iterate over the elements of this tree in sorted order.

const pure nothrow @property size_t length ();

Number of elements in the tree.

struct TreeAaIter (T,alias mapFun);

Struct that iterates over keys or values of a StackTreeAA.

BUGS:
Uses opApply instead of the more flexible ranges, because I haven't figured out how to iterate efficiently and in sorted order over a tree without control of the stack.

int opApply (int delegate(ref IterType) dg);

const pure nothrow size_t length ();

struct StackTreeAA (K,V);

An associative array implementation based on StackTree. Lookups and insertions are O(log N). This is significantly slower in both theory and practice than StackHash, but you may want to use it if:

1. You don't know the approximate size of the table you will be creating in advance. Unlike StackHash, this AA implementation does not need to pre-allocate anything.

2. You care more about worst-case performance than average-case performance.

3. You have a good comparison function for your type, but not a good hash function.

V opIndex (K key);

Looks up key in the table, returns it by reference. If it does not exist, it will be created and initialized to V.init. This is handy, for example, when counting things with integer types.

V opIndexAssign (V val, K key);

V* opIn_r (K key);

void remove (K key);

const pure nothrow size_t length ();

@property TreeAaIter!(typeof(tree),"a.key") keys ();

@property TreeAaIter!(typeof(tree),getVal) values ();

int opApply (int delegate(ref Unqual!(K), ref Unqual!(V)) dg);

Iterate over both the keys and values of this associative array.