virtual_array.c

/*
Dynamically resizable array in constant virtual address space.
This will require a 64-bit system (or >32-bit system) for most
purposes. The idea is to reserve a huge chunk of address
space at program startup, but request actual memory backing
only when that address space is actually needed.

The big advantage of this approach is that we get stable
pointers.

Win32 implementation using VirtualAlloc(). Can probably be made
to work on Linux, too (using mmap()).
*/


typedef struct _VirtualArray VirtualArray;
struct _VirtualArray {
        void **pptr;
        size_t elemSize;
        size_t numElemsReserved;
        size_t numElemsCommitted;
};

static void _virtual_array_init(VirtualArray *array, size_t numElems, size_t elemSize)
{
        ENSURE(!*array->pptr);
        void *ptr = VirtualAlloc(NULL, numElems * elemSize, MEM_RESERVE, PAGE_READWRITE);
        ENSURE(ptr);
        *array->pptr = ptr;
        array->elemSize = elemSize;
        array->numElemsReserved = numElems;
        array->numElemsCommitted = 0;
}

static void _virtual_array_grow(VirtualArray *array, size_t minElems)
{
        if (array->numElemsCommitted < minElems) {
                /* maybe we should commit in bigger chunks? */
                size_t numBytes = (minElems * array->elemSize + 4095) & 4095;
                size_t numElems = numBytes / array->elemSize;

                ENSURE(*array->pptr);
                void *ptr = VirtualAlloc(*array->pptr, numBytes, MEM_COMMIT, PAGE_READWRITE);
                ENSURE(ptr == *array->pptr);  /* we expect stable pointers */
                array->numElemsCommitted = numElems;
        }
}

#define DEFINE_VIRTUAL_ARRAY(qualifiers, type, name) \
        qualifiers type *name; \
        qualifiers VirtualArray VIRTUAL_ARRAY_##name = { .pptr = &name };

#define virtual_array_init(name, numElems) _virtual_array_init(&VIRTUAL_ARRAY_##name, (numElems), sizeof *(name))
#define virtual_array_grow(name, minElems) _virtual_array_grow(&VIRTUAL_ARRAY_##name, (minElems))