ref: f5e20c5823337a159618f02c861af69879b0f0e8
dir: /llt/htable.inc/
//-*- mode:c -*- /* include this file and call HTIMPL to generate an implementation */ #define hash_size(h) ((h)->size/2) // compute empirical max-probe for a given size #define max_probe(size) ((size) <= (HT_N_INLINE*2) ? (HT_N_INLINE/2) : (size)>>3) #define HTIMPL(HTNAME, HFUNC, EQFUNC) \ static void ** \ HTNAME##_lookup_bp(htable_t *h, void *key) \ { \ lltuint_t hv; \ size_t i, orig, index, iter; \ size_t newsz, sz = hash_size(h); \ size_t maxprobe = max_probe(sz); \ void **tab = h->table; \ void **ol; \ \ hv = HFUNC((uintptr_t)key); \ retry_bp: \ iter = 0; \ index = (hv & (sz-1)) * 2; \ sz *= 2; \ orig = index; \ \ do{ \ if(tab[index+1] == HT_NOTFOUND){ \ tab[index] = key; \ return &tab[index+1]; \ } \ if(EQFUNC(key, tab[index])) \ return &tab[index+1]; \ index = (index+2) & (sz-1); \ iter++; \ if(iter > maxprobe) \ break; \ }while(index != orig); \ \ /* table full */ \ /* quadruple size, rehash, retry the insert */ \ /* it's important to grow the table really fast; otherwise we waste */ \ /* lots of time rehashing all the keys over and over. */ \ sz = h->size; \ ol = h->table; \ if(sz >= (1<<19) || (sz <= (1<<8))) \ newsz = sz<<1; \ else if(sz <= HT_N_INLINE) \ newsz = HT_N_INLINE; \ else \ newsz = sz<<2; \ tab = (void**)LLT_ALLOC(newsz*sizeof(void*)); \ if(tab == nil) \ return nil; \ for(i = 0; i < newsz; i++) \ tab[i] = HT_NOTFOUND; \ h->table = tab; \ h->size = newsz; \ for(i = 0; i < sz; i += 2) { \ if(ol[i+1] != HT_NOTFOUND) \ (*HTNAME##_lookup_bp(h, ol[i])) = ol[i+1]; \ } \ if(ol != &h->_space[0]) \ LLT_FREE(ol); \ sz = hash_size(h); \ maxprobe = max_probe(sz); \ tab = h->table; \ goto retry_bp; \ } \ \ void \ HTNAME##_put(htable_t *h, void *key, void *val) \ { \ void **bp = HTNAME##_lookup_bp(h, key); \ *bp = val; \ } \ \ void ** \ HTNAME##_bp(htable_t *h, void *key) \ { \ return HTNAME##_lookup_bp(h, key); \ } \ \ /* returns bp if key is in hash, otherwise nil */ \ /* if return is non-nil and *bp == HT_NOTFOUND then key was deleted */ \ static void ** \ HTNAME##_peek_bp(htable_t *h, void *key) \ { \ size_t sz = hash_size(h); \ size_t maxprobe = max_probe(sz); \ void **tab = h->table; \ size_t index = (HFUNC((uintptr_t)key) & (sz-1)) * 2; \ sz *= 2; \ size_t orig = index; \ size_t iter = 0; \ \ do { \ if(tab[index] == HT_NOTFOUND) \ return nil; \ if(EQFUNC(key, tab[index])) \ return &tab[index+1]; \ \ index = (index+2) & (sz-1); \ iter++; \ if(iter > maxprobe) \ break; \ }while(index != orig); \ \ return nil; \ } \ \ void *\ HTNAME##_get(htable_t *h, void *key) \ { \ void **bp = HTNAME##_peek_bp(h, key); \ if(bp == nil) \ return HT_NOTFOUND; \ return *bp; \ } \ \ int \ HTNAME##_has(htable_t *h, void *key) \ { \ return HTNAME##_get(h, key) != HT_NOTFOUND; \ } \ \ int \ HTNAME##_remove(htable_t *h, void *key) \ { \ void **bp = HTNAME##_peek_bp(h, key); \ if(bp != nil){ \ *bp = HT_NOTFOUND; \ return 1; \ } \ return 0; \ } \ \ void \ HTNAME##_adjoin(htable_t *h, void *key, void *val) \ { \ void **bp = HTNAME##_lookup_bp(h, key); \ if(*bp == HT_NOTFOUND) \ *bp = val; \ }