Allocators in Phobos

[David Simcha]

I've massively improved my RegionAllocator (formerly TempAlloc) module thanks
to the excellent suggestions from Andrei and from Dimitri Olshansky (the GSoC
student working on regexes).

For the curious:

http://cis.jhu.edu/~dsimcha/d/phobos/std_regionallocator.html
https://github.com/dsimcha/TempAlloc/blob/master/regionallocator.d

The main point of this massive overhaul was Andrei's suggestion that
TempAlloc/RegionAllocator be converted from something fairly ad-hoc to an
implementation of the more general allocator interface that he proposed.  I
also think that three high-level functions were missing from Andrei's
proposal.  All of these will be included in RegionAllocator even if we decide
they're not "standard" allocator functions:

newArray:  Creates a new array.  Can be syntactic sugar for (cast(T*)
allocate(T.sizeof * nElements))[0..nElements] or can do something more
complicated based on knowing what type T is.

uninitializedArray:  Same as newArray but doesn't initialize elements.

array:  Converts a range into an array.

While I'm waiting in the review queue, I'm thinking of broadening the
allocator proposal to include a few more low-hanging fruit allocators:

GCAllocator:  An allocator wrapper over the garbage collector.  Question:
Should GCAllocator.free() call core.memory.GC.free() or be a no-op?

CAllocator:  An allocator wrapper over C's malloc and free.

FreeListAllocator:  A meta-allocator that allocates blocks of some fixed,
user-specified size off of some other base allocator and makes them available
via the allocate() function.  All allocation requests larger than the block
size throw.  All allocations smaller than the blolck size use whatever
fraction of a block they need and waste the rest.  Freeing memory via free()
puts it on a free list maintained by the FreeListAllocator object.
FreeListAllocator attempts to satisfy allocation requests from its free list
before allocating off the base allocator.  I'd probably make each
FreeListAllocator instance reference counted, and when the the last copy of an
instance goes out of scope, all blocks on the free list get freed.

Are there any other allocators that might be useful and could reasonably be
implemented as Phobos modules without major modifications to druntime or the
compiler?