#include <u.h>#include <libc.h> #include "map.h" #define DBG if(0) #define isdeleted(x) ((x>>31) != 0)#define setentry(e, key, value) (e->key = key, e->value = value)#define mapdistance(m, hash, slot) ((slot + m->size - (hash % m->size)) % m->size) static voidjenkinshash(const void *k, uintptr len, u32int *h){ u32int hash, i; const u8int *key; key = k; /* for(hash = i = 0; i < len; i++){ hash = hash * 33 ^ key[i]; } assert(key); assert(h);*/ for(hash = i = 0; i < len; ++i){ hash += key[i]; hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); /* XXX: drop top and bottom bits */ hash &= 0x7FFFFFFF; hash |= (hash == 0); *h = hash;} void (*maphash)(const void*, uintptr, u32int*) = jenkinshash; typedef struct Entry Entry;struct Entry { char *key; u32int hash; void *value; Entry *next;}; #define HASHSIZE 13 struct Map { Entry *tab[HASHSIZE]; void (*free)(void*);}; static voidnopfree(void *v){ USED(v);} Map*mapnew(void (*fr)(void*)){ Map *m; m = mallocz(sizeof(Map), 1); if(m == nil) return nil; if(fr != nil) m->free = fr; else m->free = nopfree; return m;} voidmapfree(Map *m){ int i; Entry *e, *next; for(i = 0; i < HASHSIZE; i++){ e = m->tab[i]; while(e != nil){ next = e->next; free(e->key); m->free(e->value); free(e); e = next; } } free(m);} static Entry*mapgete(Map *m, char *key){ Entry *e; u32int hash; maphash(key, strlen(key), &hash); for(e = m->tab[hash % HASHSIZE]; e != nil; e = e->next) if(e->hash == hash && strcmp(e->key, key) == 0) return e; return nil;} intmapset(Map *m, char *key, void *value){ Entry *e; u32int hash; if((e = mapgete(m, key)) == nil){ /* not found */ e = mallocz(sizeof(Entry), 1); if(e == nil) return -1; e->key = strdup(key); if(e->key == nil){ free(e); return -1; } maphash(key, strlen(key), &hash); e->hash = hash; e->value = value; e->next = m->tab[hash % HASHSIZE]; m->tab[hash % HASHSIZE] = e; } else { /* already there */ m->free(e->value); e->value = value; } return 0;} void*mapget(Map *m, char *key){ Entry *e; e = mapgete(m, key); if(e != nil) return e->value; return nil;} voidmapdelete(Map *m, char *key){ Entry *e, *t; u32int hash; maphash(key, strlen(key), &hash); e = t = m->tab[hash % HASHSIZE]; while(e != nil){ if(e->hash == hash && strcmp(e->key, key) == 0){ if(e == m->tab[hash % HASHSIZE]) m->tab[hash % HASHSIZE] = e->next; else t->next = e->next; free(e->key); m->free(e->value); free(e); return; } t = e; e = e->next; }} voidmapdump(Map *m, int fd){ u32int i; Entry *e; for(i = 0; i < HASHSIZE; i++){ fprint(2, "SLOT %d\n", i); for(e = m->tab[i]; e != nil; e = e->next){ fprint(fd, "%-10s\t%#0p\t%#010ux\n", e->key, e->value, e->hash); } }}
#include <u.h>
#include <libc.h>
#include "map.h"
#define DBG if(0)
#define isdeleted(x) ((x>>31) != 0)
#define setentry(e, key, value) (e->key = key, e->value = value)
#define mapdistance(m, hash, slot) ((slot + m->size - (hash % m->size)) % m->size)
static void
jenkinshash(const void *k, uintptr len, u32int *h)
{
u32int hash, i;
const u8int *key;
key = k;
/*
for(hash = i = 0; i < len; i++){
hash = hash * 33 ^ key[i];
}
assert(key);
assert(h);
*/
for(hash = i = 0; i < len; ++i){
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
/* XXX: drop top and bottom bits */
hash &= 0x7FFFFFFF;
hash |= (hash == 0);
*h = hash;
}
void (*maphash)(const void*, uintptr, u32int*) = jenkinshash;
typedef struct Entry Entry;
struct Entry {
char *key;
u32int hash;
void *value;
Entry *next;
};
#define HASHSIZE 13
struct Map {
Entry *tab[HASHSIZE];
void (*free)(void*);
};
static void
nopfree(void *v)
{
USED(v);
}
Map*
mapnew(void (*fr)(void*))
{
Map *m;
m = mallocz(sizeof(Map), 1);
if(m == nil)
return nil;
if(fr != nil)
m->free = fr;
else
m->free = nopfree;
return m;
}
void
mapfree(Map *m)
{
int i;
Entry *e, *next;
for(i = 0; i < HASHSIZE; i++){
e = m->tab[i];
while(e != nil){
next = e->next;
free(e->key);
m->free(e->value);
free(e);
e = next;
}
}
free(m);
}
static Entry*
mapgete(Map *m, char *key)
{
Entry *e;
u32int hash;
maphash(key, strlen(key), &hash);
for(e = m->tab[hash % HASHSIZE]; e != nil; e = e->next)
if(e->hash == hash && strcmp(e->key, key) == 0)
return e;
return nil;
}
int
mapset(Map *m, char *key, void *value)
{
Entry *e;
u32int hash;
if((e = mapgete(m, key)) == nil){
/* not found */
e = mallocz(sizeof(Entry), 1);
if(e == nil)
return -1;
e->key = strdup(key);
if(e->key == nil){
free(e);
return -1;
}
maphash(key, strlen(key), &hash);
e->hash = hash;
e->value = value;
e->next = m->tab[hash % HASHSIZE];
m->tab[hash % HASHSIZE] = e;
} else {
/* already there */
m->free(e->value);
e->value = value;
}
return 0;
}
void*
mapget(Map *m, char *key)
{
Entry *e;
e = mapgete(m, key);
if(e != nil)
return e->value;
return nil;
}
void
mapdelete(Map *m, char *key)
{
Entry *e, *t;
u32int hash;
maphash(key, strlen(key), &hash);
e = t = m->tab[hash % HASHSIZE];
while(e != nil){
if(e->hash == hash && strcmp(e->key, key) == 0){
if(e == m->tab[hash % HASHSIZE])
m->tab[hash % HASHSIZE] = e->next;
else
t->next = e->next;
free(e->key);
m->free(e->value);
free(e);
return;
}
t = e;
e = e->next;
}
}
void
mapdump(Map *m, int fd)
{
u32int i;
Entry *e;
for(i = 0; i < HASHSIZE; i++){
fprint(2, "SLOT %d\n", i);
for(e = m->tab[i]; e != nil; e = e->next){
fprint(fd, "%-10s\t%#0p\t%#010ux\n",
e->key, e->value, e->hash);
}
}
}