inferno-os tree was separated from the inferno-os-android (separated from the Android driver)

1 files changed, 139 insertions, 0 deletions

diff --git a/liblogfs/map.c b/liblogfs/map.c
new file mode 100644
index 0000000..b2def4f
--- /dev/null
+++ b/liblogfs/map.c
@@ -0,0 +1,139 @@
+#include "logfsos.h"
+#include "logfs.h"
+#include "local.h"
+
+typedef struct MapNode MapNode;
+
+struct MapNode {
+	MapNode *next;
+	uchar e[1];	// entry goes here, inline
+};
+
+struct Map {
+	int size;
+	int (*hash)(void *key, int size);
+	int (*compare)(void *entry, void *key);
+	int (*allocsize)(void *key);
+	void (*free)(void *entry);
+	MapNode *head[1];
+};
+
+char *
+logfsmapnew(int size, int (*hash)(void *key, int size), int (*compare)(void *entry, void *key), int (*allocsize)(void *key), void (*free)(void *), Map **mapp)
+{
+	Map *p;
+	*mapp = p = logfsrealloc(nil, sizeof(Map) + (size - 1) * sizeof(MapNode *));
+	if(p == nil)
+		return Enomem;
+	p->size = size;
+	p->hash = hash;
+	p->compare = compare;
+	p->allocsize = allocsize;
+	p->free = free;
+	return nil;
+}
+
+void
+logfsmapfree(FidMap **mp)
+{
+	FidMap *m;
+	int i;
+
+	m = *mp;
+	if(m == nil)
+		return;
+
+	for(i = 0; i < m->size; i++) {
+		MapNode *n, *next;
+		n = m->head[i];
+		while(n) {
+			next = n->next;
+			if(m->free)
+				(*m->free)(n->e);
+			logfsfreemem(n);
+			n = next;
+		}
+	}
+	logfsfreemem(m);
+	*mp = nil;
+}
+
+static char *
+find(FidMap *m, void *key, int create, void **ep)
+{
+	MapNode *n;
+	int i;
+
+	i = (*m->hash)(key, m->size);
+	n = m->head[i];
+	while(n && !(*m->compare)(n->e, key))
+		n = n->next;
+	if(n) {
+		if(create) {
+			*ep = nil;
+			return nil;
+		}
+		*ep = n->e;
+		return nil;
+	}
+	if(!create) {
+		*ep = nil;
+		return nil;
+	}
+	n = logfsrealloc(nil, (*m->allocsize)(key) + sizeof(MapNode *));
+	if(n == nil) {
+		*ep = nil;
+		return Enomem;
+	}
+	n->next = m->head[i];
+	m->head[i] = n;
+	*ep = n->e;
+	return nil;
+}
+
+void *
+logfsmapfindentry(Map *m, void *key)
+{
+	void *rv;
+	find(m, key, 0, &rv);
+	return rv;
+}
+
+char *
+logfsmapnewentry(Map *m, void *key, void **entryp)
+{
+	return find(m, key, 1, entryp);
+}
+
+int
+logfsmapdeleteentry(Map *m, void *key)
+{
+	MapNode **np, *n;
+	np = &m->head[(*m->hash)(key, m->size)];
+	while((n = *np) && !(*m->compare)(n->e, key))
+		np = &n->next;
+	if(n) {
+		*np = n->next;
+		if(m->free)
+			(*m->free)(n->e);
+		logfsfreemem(n);
+		return 1;
+	}
+	return 0;		// not there
+}
+
+int
+logfsmapwalk(Map *m, int (*func)(void *magic, void *), void *magic)
+{
+	int x;
+	MapNode *n;
+
+	for(x = 0; x < m->size; x++)
+		for(n = m->head[x]; n; n = n->next) {
+			int rv = (*func)(magic, n->e);
+			if(rv <= 0)
+				return rv;
+		}
+	return 1;
+}
+