lazymemory.h

#ifndef lazy_memory_h
#define lazy_memory_h

#include <stdint.h>
#include <string.h>

#define CacheLine 64
#define WordSize (sizeof(uint64_t) * 8)	// 64 (bits)

#define AlignN(s, n) (( s + n - 1) / n * n)
#define AlignCacheLine(s) AlignN(s, CacheLine)
#define LazyMemorySize AlignCacheLine(LazyMemoryCount * sizeof(LazyMemoryType))
#define LazyMemorySegment (LazyMemorySize / CacheLine)

#define LazyMemoryCacheSize ((LazyMemorySegment + WordSize - 1) / WordSize)
#define LazyMemoryCacheSegment ((LazyMemoryCacheSize + WordSize - 1)/ WordSize)

struct LazyMemoryCache {
	uint64_t buffer[AlignN(LazyMemoryCacheSize, LazyMemoryCacheSegment)];
	uint64_t cache;
};

struct LazyMemory {
	uint8_t buffer[LazyMemorySize];
	struct LazyMemoryCache cache;
};

static inline void
LazyMemoryCacheInit(struct LazyMemoryCache *c) {
	c->cache = 0;
}

static inline uint64_t
LazyMemoryCacheIndex(struct LazyMemoryCache *c, unsigned int index) {
	unsigned int segment = index / LazyMemoryCacheSegment;
	uint64_t mask = (uint64_t)1 << segment;
	if (c->cache & mask) {
		return c->buffer[index];
	} else {
		memset(c->buffer + segment * LazyMemoryCacheSegment, 0, LazyMemoryCacheSegment * sizeof(uint64_t));
		c->cache |= mask;
		return 0;
	}
}

static inline void
LazyMemoryInit(struct LazyMemory *m) {
	LazyMemoryCacheInit(&m->cache);
}

static inline LazyMemoryType*
LazyMemoryIndex(struct LazyMemory *m, unsigned int object_index) {
	unsigned int index = object_index * sizeof(LazyMemoryType);
	unsigned int segment_index = index / CacheLine;
	unsigned int cache_index = segment_index / WordSize;
	uint64_t cache = LazyMemoryCacheIndex(&m->cache, cache_index);
	uint64_t mask = (uint64_t)1 << (segment_index - cache_index * WordSize);
	if ((cache & mask) == 0) {
		memset(m->buffer + segment_index * CacheLine, 0, CacheLine);
		m->cache.buffer[cache_index] = cache | mask;
	}
	return (LazyMemoryType*)&m->buffer[index];
}

#endif

test.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct SPathSearchValue
{
	int32_t m_f;
	int32_t m_g;
};

#define MAX_PATH_SEARCH_GRID_RANGE 200
#define MAX_LAYER_COUNT 16

#define LazyMemoryType struct SPathSearchValue
#define LazyMemoryCount (MAX_PATH_SEARCH_GRID_RANGE*MAX_PATH_SEARCH_GRID_RANGE*MAX_LAYER_COUNT)

#include "lazymemory.h"

struct SPathSearchValue *
get(struct LazyMemory *m, unsigned int x, unsigned int y, unsigned int layer) {
	unsigned int index = (x * MAX_PATH_SEARCH_GRID_RANGE + y) * MAX_LAYER_COUNT + layer;
	return LazyMemoryIndex(m, index);
}

// sizeof struct LazyMemory is huge, don't use it on stack
struct LazyMemory *
init() {
	struct LazyMemory * mem = (struct LazyMemory *)malloc(sizeof(struct LazyMemory));
	LazyMemoryInit(mem);
	return mem;
}

void
test(struct LazyMemory *mem) {
	struct SPathSearchValue *v;
	int i,j,layer;
	for (i=0;i<MAX_PATH_SEARCH_GRID_RANGE;i++) {
		for (j=0;j<MAX_PATH_SEARCH_GRID_RANGE;j++) {
			for (layer=0;layer<MAX_LAYER_COUNT;layer++) {
				v = get(mem, i,j,layer);
				if (v->m_f != 0 || v->m_g != 0) {
					printf("Invalid %d %d %d %u %u\n", i,j,layer, v->m_f, v->m_g);
					exit(1);
				}
				v->m_f = i;
				v->m_g = j;
			}
		}
	}
	for (i=0;i<MAX_PATH_SEARCH_GRID_RANGE;i++) {
		for (j=0;j<MAX_PATH_SEARCH_GRID_RANGE;j++) {
			for (layer=0;layer<MAX_LAYER_COUNT;layer++) {
				v = get(mem, i,j,layer);
				if (v->m_f != i || v->m_g != j) {
					printf("Invalid2 %d %d %d %u %u\n", i,j,layer, v->m_f, v->m_g);
					exit(1);
				}
			}
		}
	}
}

int
main() {
	// sizeof struct LazyMemory is huge, don't use it on stack
	struct LazyMemory *mem = (struct LazyMemory *)malloc(sizeof(*mem));
	memset(mem, 1, sizeof(*mem));
	LazyMemoryInit(mem);
	free(mem);
	return 0;
}