util  map.c

File clib/map.c from the latest check-in

#include "map.h"
#include <stdlib.h>

map* mapNew(size_t init_sz) {
	map* m = malloc(
		sizeof(map) +
		sizeof(mapBox)*init_sz
	);
	m -> sz = init_sz;
	m -> dtor = nullptr;
	for (size_t i = 0; i < init_sz; ++i)
		m -> boxes[i] = (mapBox) {};
	//m -> weak = false;
	return m;
}

mapBox* mapBoxFor(map* m, strp key) {
	hash h = hashNew(key);
	return &m->boxes[h % (hash)m->sz];
}

void mapBoxInsert(mapBox* b, mapLink* l) {
	l -> next = nullptr;
	l -> prev = b -> tail;

	if (b -> tail == nullptr) {
		b -> head = b -> tail = l;
	} else {
		b -> tail -> next = l;
		b -> tail = l;
	}
}

mapLink* mapEnter(map* m, strp key, mapValue val) {
	mapResult r = mapFind(m, key);
	if (r.link) {
		return r.link;
	} else {
		mapBox* b = r.box;
		mapLink* l = malloc(sizeof(mapLink) + key.sz);
		l -> ref = val;
		strMov(&l -> key, key);
		mapBoxInsert(b, l);
		//if(!m->weak) vspRef(val);
		return nullptr;
	}
}

bool mapClobber(map* m, strp key, mapValue val, void (*dtor)(mapValue)) {
	mapLink* link = mapEnter(m, key, val);
	if (link) {
		if (!dtor) dtor = m -> dtor;
		if (dtor) (*dtor)(link -> ref);
		link -> ref = val;
		return true;
	}
	return false;
}

mapResult mapFind(map* m, strp key) {
	mapBox* b = mapBoxFor(m, key);
	for(mapLink* l = b -> head; l != nullptr;) {
		if(strEq(strRef(&l->key), key)) {
			return (mapResult) {
				.map = m,
				.box = b,
				.link = l,
			};
		}
	}
	return (mapResult){.map = m, .box = b};
}
mapValue mapRef(map* m, strp key) {
	mapResult r = mapFind(m, key);
	if (r.link == nullptr) return mapValue_null;
	return r.link -> ref;
}
void mapErase(map* m, strp key) {
	mapResult r = mapFind(m, key);
	if (r.link -> prev) r.link -> prev -> next = r.link -> next;
	if (r.link -> next) r.link -> next -> prev = r.link -> prev;
	if (r.box -> head == r.link) r.box -> head = r.link -> next;
	if (r.box -> tail == r.link) r.box -> tail = r.link -> prev;
	//if (!m -> weak) vspUnref(r.link -> ref);
	free(r.link);
}
map* mapDel(map* m) {
	for (size_t i = 0; i < m -> sz; ++i) {
		mapBox* b = &m->boxes[i];
		if (b -> head == nullptr) continue;
		for(mapLink* l = b -> head; l != nullptr;) {
			mapLink* next = l -> next;
			//if(!m->weak) vspUnref(l->ref);
			free(l);
			l = next;
		}
	}
	free(m);
}

map* mapResize(map* om, size_t newsz) {
	/* expensive!! */
	map* nm = mapNew(newsz);
	//nm -> weak = om -> weak;
	for (size_t i = 0; i < om -> sz; ++i) {
		mapBox* b = &om->boxes[i];
		if (b -> head == nullptr) continue;
		for(mapLink* l = b -> head; l != nullptr;) {
			mapBox* nb = mapBoxFor(nm, strRef(&l->key)); 
			mapBoxInsert(nb, l);
		}
	}
	free(om);
	return nm;
}

static bool mapEqPredicate(mapValue a, void* b) {
	return a.ip = ((mapValue*)b) -> ip; /* real fucky */
}

mapResult mapRFindPred(map* m, void* val, mapPredicate p) {
	for (size_t i = 0; i < m->sz; ++ i) {
		mapBox* b = &m -> boxes[i];
		if (b -> head == nullptr) continue;
		for (mapLink* l = b -> head; l != nullptr; l = l -> next) {
			if ((*p)(l->ref, val)) return (mapResult) {
				.map = m,
				.box = b,
				.link = l,
			};
		}
	}
	return (mapResult) {m};
}

mapResult mapRFind(map* m, mapValue val) {
	return mapRFindPred(m, &val, mapEqPredicate);
}

strp mapRRefPred(map* m, void* val, mapPredicate p) {
	mapResult r = mapRFindPred(m, val, p);
	if (r.link == nullptr) return (strp){};
	return strRef(&r.link -> key);
}

strp mapRRef(map* m, mapValue val) {
	return mapRRefPred(m, &val, mapEqPredicate);
}