/
githubmirror
/
julia
Обзор
Документация
Войти
/
githubmirror
/
julia
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/support/htable.inc
247 строк
17 KB
Cody Tapscott
Various `htable_t` fixes / improvements. (#61446)
03 апр 2026, 22:36
Не верифицирован
03 апр 2026, 22:36
edd9a51
Код
Авторство
О чём код?
//-*- mode:c -*- /* include this file and call HTIMPL to generate an implementation */ #define hash_size(h) ((h)->size/2) #define _HTIMPL_IDENTITY_KEYALLOC(key,ctx) (key) #define _HTIMPL_NOOP_KEYFREE(key,ctx) (void)key // 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_EX(HTNAME, HFUNC, EQFUNC, KEYALLOC, KEYFREE, _STATIC) \ \ /* key_owned: if true, the key is already owned by the table */ \ /* if false, KEYALLOC is called on insert. */ \ static void **HTNAME##_lookup_bp_r_impl(htable_t *h, void *key, \ void *ctx, int key_owned) \ { \ uint_t hv; \ size_t i, orig, index, iter, empty_slot; \ size_t newsz, sz = hash_size(h); \ size_t maxprobe = max_probe(sz); \ void **tab = h->table; \ void **ol; \ \ hv = HFUNC((uintptr_t)key, ctx); \ while (1) { \ iter = 0; \ index = (size_t)(hv & (sz-1)) * 2; \ sz *= 2; \ orig = index; \ empty_slot = -1; \ \ do { \ if (tab[index] == HT_NOTFOUND) { \ if (empty_slot == -1) \ empty_slot = index; \ break; \ } \ if (tab[index+1] == HT_NOTFOUND) { \ if (empty_slot == -1) \ empty_slot = index; \ } \ \ if (EQFUNC(key, tab[index], ctx)) { \ if (tab[index+1] == HT_NOTFOUND) \ h->live++; /* reviving a tombstone */ \ return &tab[index+1]; \ } \ \ iter++; \ index = (index + iter*2) & (sz-1); \ if (iter > maxprobe) \ break; /* grow if probe took too long */ \ } while (index != orig); \ \ /* grow if live entries >= 75% of slots */ \ if (empty_slot != -1) { \ if (h->live * 4 >= hash_size(h) * 3) \ empty_slot = -1; \ } \ /* rehash if too many tombstones (>= 87.5% slots occupied) */ \ int grow = (empty_slot == -1); \ if (empty_slot != -1) { \ if (8 * (hash_size(h) - h->count) <= hash_size(h)) \ empty_slot = -1; \ } \ \ if (empty_slot != -1) { \ if (tab[empty_slot] == HT_NOTFOUND) \ h->count++; \ else \ KEYFREE(tab[empty_slot], ctx); /* free tombstone key */ \ h->live++; \ tab[empty_slot] = key_owned ? key : KEYALLOC(key, ctx); \ return &tab[empty_slot+1]; \ } \ \ /* 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 (!grow) \ newsz = sz; /* just rehash to clean tombstones */ \ else if (sz < HT_N_INLINE) \ newsz = HT_N_INLINE; \ else if (sz >= (1<<19) || (sz <= (1<<8))) \ newsz = sz<<1; \ else \ newsz = sz<<2; \ /*printf("trying to allocate %d words.\n", newsz); fflush(stdout);*/ \ tab = (void**)LLT_ALLOC(newsz*sizeof(void*)); \ if (tab == NULL) \ return NULL; \ for (i = 0; i < newsz; i++) \ tab[i] = HT_NOTFOUND; \ h->table = tab; \ h->size = newsz; \ h->count = 0; \ h->live = 0; \ for (i = 0; i < sz; i += 2) { \ if (ol[i+1] != HT_NOTFOUND) { \ (*HTNAME##_lookup_bp_r_impl(h, ol[i], ctx, 1)) = \ ol[i+1]; \ } \ else if (ol[i] != HT_NOTFOUND) { \ KEYFREE(ol[i], ctx); /* free tombstone key */ \ } \ } \ if (ol != &h->_space[0]) \ LLT_FREE(ol); \ \ sz = hash_size(h); \ maxprobe = max_probe(sz); \ tab = h->table; \ } \ \ return NULL; \ } \ \ static void **HTNAME##_lookup_bp_r(htable_t *h, void *key, void *ctx) \ { \ return HTNAME##_lookup_bp_r_impl(h, key, ctx, /* key_owned */ 0); \ } \ \ _STATIC void HTNAME##_put_r(htable_t *h, void *key, void *val, void *ctx) \ { \ void **bp = HTNAME##_lookup_bp_r(h, key, ctx); \ \ *bp = val; \ } \ \ _STATIC void **HTNAME##_bp_r(htable_t *h, void *key, void *ctx) \ { \ return HTNAME##_lookup_bp_r(h, key, ctx); \ } \ \ /* returns bp if key is in hash, otherwise NULL */ \ /* if return is non-NULL and *bp == HT_NOTFOUND then key was deleted */ \ static void **HTNAME##_peek_bp_r(htable_t *h, void *key, void *ctx) \ { \ size_t sz = hash_size(h); \ size_t maxprobe = max_probe(sz); \ void **tab = h->table; \ size_t index = (size_t)(HFUNC((uintptr_t)key, ctx) & (sz-1)) * 2; \ sz *= 2; \ size_t orig = index; \ size_t iter = 0; \ \ do { \ if (tab[index] == HT_NOTFOUND) \ return NULL; \ if (EQFUNC(key, tab[index], ctx)) \ return &tab[index+1]; \ \ iter++; \ /* quadratic (triangular) probing */ \ index = (index + iter*2) & (sz-1); \ if (iter > maxprobe) \ break; \ } while (index != orig); \ \ return NULL; \ } \ \ _STATIC void *HTNAME##_get_r(htable_t *h, void *key, void *ctx) \ { \ void **bp = HTNAME##_peek_bp_r(h, key, ctx); \ if (bp == NULL) \ return HT_NOTFOUND; \ return *bp; \ } \ \ _STATIC int HTNAME##_has_r(htable_t *h, void *key, void *ctx) \ { \ return (HTNAME##_get_r(h, key, ctx) != HT_NOTFOUND); \ } \ \ _STATIC int HTNAME##_remove_r(htable_t *h, void *key, void *ctx) \ { \ void **bp = HTNAME##_peek_bp_r(h, key, ctx); \ if (bp != NULL && *bp != HT_NOTFOUND) { \ *bp = HT_NOTFOUND; \ h->live--; \ return 1; \ } \ return 0; \ } \ \ _STATIC void HTNAME##_adjoin_r(htable_t *h, void *key, void *val, void *ctx) \ { \ void **bp = HTNAME##_lookup_bp_r(h, key, ctx); \ if (*bp == HT_NOTFOUND) \ *bp = val; \ } #define HTIMPL(HTNAME, HFUNC, EQFUNC) \ static uint_t HTNAME##_hfunc_wrapper(uintptr_t key, void *ctx) \ { \ (void)ctx; \ return HFUNC(key); \ } \ \ static uint_t HTNAME##_eqfunc_wrapper(void *key1, void *key2, void *ctx) \ { \ (void)ctx; \ return EQFUNC(key1, key2); \ } \ \ _HTIMPL_EX(HTNAME, HTNAME##_hfunc_wrapper, HTNAME##_eqfunc_wrapper, \ _HTIMPL_IDENTITY_KEYALLOC, _HTIMPL_NOOP_KEYFREE, static) \ \ void HTNAME##_put(htable_t *h, void *key, void *val) \ { \ HTNAME##_put_r(h, key, val, NULL); \ } \ \ void **HTNAME##_bp(htable_t *h, void *key) \ { \ return HTNAME##_bp_r(h, key, NULL); \ } \ \ void *HTNAME##_get(htable_t *h, void *key) \ { \ return HTNAME##_get_r(h, key, NULL); \ } \ \ int HTNAME##_has(htable_t *h, void *key) \ { \ return HTNAME##_has_r(h, key, NULL); \ } \ \ int HTNAME##_remove(htable_t *h, void *key) \ { \ return HTNAME##_remove_r(h, key, NULL); \ } \ \ void HTNAME##_adjoin(htable_t *h, void *key, void *val) \ { \ HTNAME##_adjoin_r(h, key, val, NULL); \ } #define HTIMPL_R(HTNAME, HFUNC, EQFUNC, KEYALLOC, KEYFREE) _HTIMPL_EX(HTNAME, HFUNC, EQFUNC, KEYALLOC, KEYFREE, )