Handle-based Map

dumb_handle_map.odin

package dumb_handle_map

// NOTE: ONLY TO SHOW WHAT A GENERATION IS DOING 
// BUT DOES NO INSERTION WHATSOEVER

Handle_Map :: struct($T: typeid) {
	entries: [dynamic]Entry(T),
}

Entry :: struct($T: typeid) {
	generation: u32,
	value:      T,
}

Handle :: struct {
	generation: u32,
	index:      u32,
}

@(require_results)
get :: proc(m: ^$M/Handle_Map($T), h: Handle) -> (^T, bool) {
	if h.index < u32(len(m.entries)) {
		entry := &m.entries[h.index]
		if entry.generation == h.generation {
			return &entry.value, true
		}
	}
	return nil, false
}

handle_map.odin

package handle_map

import "base:builtin"

Handle_Map :: struct($T: typeid) {
	handles:        [dynamic]Handle,
	values:         [dynamic]T,
	sparse_indices: [dynamic]Sparse_Index,
	next:           u32,

}

Handle :: struct {
	generation: u32,
	index:      u32,
}

Sparse_Index :: struct {
	generation:    u32,
	index_or_next: u32,
}

init :: proc(m: ^$M/Handle_Map($T), allocator := context.allocator) {
	m.handles.allocator        = allocator
	m.values.allocator         = allocator
	m.sparse_indices.allocator = allocator
	m.next = 0
}

destroy :: proc(m: ^$M/Handle_Map($T)) {
	clear(m)
	delete(m.handles)
	delete(m.values)
	delete(m.sparse_indices)
}

clear :: proc(m: ^$M/Handle_Map($T)) {
	builtin.clear(&m.handles)
	builtin.clear(&m.values)
	builtin.clear(&m.sparse_indices)
	m.next = 0
}

@(require_results)
has_handle :: proc(m: $M/Handle_Map($T), h: Handle) -> bool {
	if h.index < u32(len(m.sparse_indices)) {
		return m.sparse_indices[h.index].generation == h.generation
	}
	return false
}

@(require_results)
get :: proc(m: ^$M/Handle_Map($T), h: Handle) -> (^T, bool) {
	if h.index < u32(len(m.sparse_indices)) {
		entry := m.sparse_indices[h.index]
		if entry.generation == h.generation {
			return &m.values[entry.index_or_next], true
		}
	}
	return nil, false
}

@(require_results)
insert :: proc(m: ^$M/Handle_Map($T), value: T) -> (handle: Handle) {
	if m.next < u32(len(m.sparse_indices)) {
		entry := &m.sparse_indices[m.next]
		assert(entry.generation < max(u32), "Generation sparse indices overflow")

		entry.generation += 1
		handle = Handle{
			generation = entry.generation,
			index = m.next,
		}
		m.next = entry.index_or_next
		entry.index_or_next = u32(len(m.handles))
		append(&m.handles, handle)
		append(&m.values,  value)
	} else {
		assert(m.next < max(u32), "Index sparse indices overflow")

		handle = Handle{
			index = u32(len(m.sparse_indices)),
		}
		append(&m.sparse_indices, Sparse_Index{
			index_or_next = u32(len(m.handles)),
		})
		append(&m.handles, handle)
		append(&m.values,  value)
		m.next += 1
	}
	return
}

remove :: proc(m: ^$M/Handle_Map($T), h: Handle) -> (value: Maybe(T)) {
	if h.index < u32(len(m.sparse_indices)) {
		entry := &m.sparse_indices[h.index]
		if entry.generation != h.generation {
			return
		}
		index := entry.index_or_next
		entry.generation += 1
		entry.index_or_next = m.next
		m.next = h.index
		value = m.values[index]
		unordered_remove(&m.handles, int(index))
		unordered_remove(&m.values,  int(index))
		if index < u32(len(m.handles)) {
			m.sparse_indices[m.handles[index].index].index_or_next = index
		}
	}
	return
}


main :: proc() {
	m: Handle_Map(f32)
	init(&m)
	defer destroy(&m)

	value := f32(123.456)
	h := insert(&m, value)

	ptr, _ := get(&m, h)
	assert(ptr^ == value)
	assert(has_handle(m, h))
	remove(&m, h)
	assert(!has_handle(m, h))
}