ref: d789157f513b2c3f324e00401f7e72e6010b6211
dir: hmap/hash.c
#include <u.h> #include <libc.h> #include "hash.h" Hmap* allochmap(uvlong (*hash)(void*), int (*cmp)(void*,void*), int nbuckets, usize size) { void *store; Hmap *h; store = mallocz(sizeof(*h) + (nbuckets * size), 1); if(store == nil) return nil; h = store; h->size = nbuckets; h->nsize = size; h->hash = hash; h->cmp = cmp; h->len = h->cap = nbuckets; h->nodes = store; h->nodes += sizeof(*h); return store; } void hmapset(Hmap **store, Hnode *new) { Hnode *n; Hmap *h; int tmp; tmp = 0; h = *store; n = (Hnode*)(h->nodes + (h->hash(new)%h->size)*h->nsize); for(;;){ if(n->filled == 0) goto replace; if(h->cmp(n, new) == 0){ tmp = n->next; goto replace; } if(n->next == 0) break; n = (Hnode*)(h->nodes + n->next*h->nsize); } if(h->cap == h->len){ h->cap *= 2; *store = realloc(*store, sizeof(*h) + h->cap*h->nsize); h = *store; h->nodes = (uchar*)*store + sizeof(*h); memset(h->nodes + h->len*h->nsize, 0, h->nsize); } n->next = h->len; h->len++; assert(h->len <= h->cap); n = (Hnode*)(h->nodes + n->next*h->nsize); replace: memmove(n, new, h->nsize); n->filled++; n->next = tmp; } void* hmapget(Hmap *h, Hnode *q) { Hnode *n; n = (Hnode*)(h->nodes + (h->hash(q)%h->size)*h->nsize); for(;;){ if(n->filled != 0 && h->cmp(n, q) == 0) return n; if(n->next == 0) break; n = (Hnode*)(h->nodes + n->next*h->nsize); } return nil; } void hmapmark(Hmap *h, Hnode *n) { n->filled = 0; } void* hmapdel(Hmap *h, Hnode *q) { Hnode *n; n = hmapget(h, q); if(n == nil) return nil; n->filled = 0; return n; } Hmap* hmaprehash(Hmap *old, int buckets) { int i; Hnode *n; Hmap *new; if(buckets == 0) buckets = old->len; new = allochmap(old->hash, old->cmp, buckets, old->nsize); for(i=0 ; i < old->len; i++){ n = (Hnode*)(old->nodes + i*old->nsize); hmapset(&new, n); } free(old); return new; } int hmapfmt(Fmt *f) { Hmap *h; Hnode *n, *o; char fmt[16]; int i, len; h = va_arg(f->args, Hmap*); fmt[0] = '%'; memset(fmt+1, 0, UTFmax+1); runetochar(fmt+1, &h->nodeverb); for(i=len=0; i < h->size; i++){ n = (Hnode*)(h->nodes + i*h->nsize); for(o=n;;){ if(o->filled != 0) len += fmtprint(f, (char*)fmt, o); if(o->next == 0) break; o = (Hnode*)(h->nodes + o->next*h->nsize); } } return len; }