diff options
| -rw-r--r-- | lib/cbit/htab.h | 49 | ||||
| -rw-r--r-- | script/mconfig.py | 1 | ||||
| -rw-r--r-- | test/test-htab.c | 32 |
3 files changed, 67 insertions, 15 deletions
diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h index 054b423..7dbbf6b 100644 --- a/lib/cbit/htab.h +++ b/lib/cbit/htab.h @@ -105,25 +105,46 @@ struct htab_internal { return NULL; \ } \ \ - /* slow but who cares */ \ + /* a bit inefficient */ \ void __htab_key_removeat_##name(struct htab_internal *restrict hi, \ void *op, \ size_t entry_size) { \ - key_ty *orig = op; \ - key_ty *end = (void *) ((char *) hi->base + hi->capacity * entry_size); \ - key_ty *cur = orig; \ - key_ty *prev; \ - do { \ - prev = cur; \ + size_t capacity = hi->capacity; \ + char *buckets = (char *) hi->base; \ + key_ty *end = (void *) buckets + capacity * entry_size; \ + key_ty *hole = op; \ + key_ty *cur = hole; \ + key_ty *last_cf_not_after_hole = NULL; \ + while (1) { \ cur = (void *) ((char *) cur + entry_size); \ - if (cur == end) \ + if (cur == end)\ cur = hi->base; \ - if (null_func(cur)) \ - break; \ - memmove(prev, cur, entry_size); \ - prev = cur; \ - } while (cur != orig); \ - memset(cur, nil_byte, entry_size); \ + if (cur == hole || null_func(cur)) { \ + if (!last_cf_not_after_hole) { \ + /* all of the elements in this chain have starting \ + * positions (hashes) strictly 'after' the hole position, \ + * so we can't move any of them into the hole. but that \ + * also means it's safe to just erase the hole. */ \ + memset(hole, nil_byte, entry_size); \ + break; \ + } else { \ + memcpy(hole, last_cf_not_after_hole, entry_size); \ + /* if we could get the last element which has the + * 'earliest' hash in the chain, then it would be safe to + * end here, but ... */ \ + cur = hole = last_cf_not_after_hole; \ + last_cf_not_after_hole = NULL; \ + continue; \ + } \ + } \ + size_t cur_hash = (hash_func(cur)) % capacity; \ + key_ty *cur_chain_first = (void *) buckets + cur_hash * entry_size; \ + bool cf_after_hole /* cyclically */ = hole <= cur ? \ + (hole < cur_chain_first) : \ + (cur < cur_chain_first && cur_chain_first <= hole); \ + if (!cf_after_hole) \ + last_cf_not_after_hole = cur; \ + } \ hi->length--; \ } \ void __htab_key_memset_##name(void *ptr, size_t size) { \ diff --git a/script/mconfig.py b/script/mconfig.py index 9b37089..ac47d01 100644 --- a/script/mconfig.py +++ b/script/mconfig.py @@ -870,6 +870,7 @@ class MakefileEmitter(Emitter): raise ValueError("your awful filename %r can't be encoded in make (probably)" % (fn,)) return re.sub(r'([ :\$\\])', r'\\\1', fn) # depfile = ('makefile', filename) or ('msvc',) + # TODO TODO: the depfile out paths won't be relative, fix that somehow def add_command_raw(self, outs, ins, argvs, phony=False, depfile=None): bit = '' outs = ' '.join(map(self.filename_rel_and_escape, outs)) diff --git a/test/test-htab.c b/test/test-htab.c index c85d620..57886f7 100644 --- a/test/test-htab.c +++ b/test/test-htab.c @@ -13,6 +13,13 @@ struct teststr { DECL_EXTERN_HTAB_KEY(teststr, const char *); DECL_HTAB(teststr_int, teststr, int); +#define u32_hash(up) (*(up) % 100) +#define u32_null(up) (!*(up)) +#define u32_eq(u1p, u2p) (*(u1p) == *(u2p)) + +DECL_STATIC_HTAB_KEY(u32, uint32_t, u32_hash, u32_eq, u32_null, 0); +DECL_HTAB(u32_u32, u32, uint32_t); + int main() { /* test loop crap */ LET(int y = 5) @@ -31,7 +38,6 @@ int main() { struct htab_teststr_int *hp; HTAB_STORAGE(teststr_int) stor = HTAB_STORAGE_INIT_STATIC(&stor, teststr_int); - /*HTAB_STORAGE_INIT(&stor, teststr_int);*/ hp = &stor.h; for(int i = 0; i < 100; i++) { const char *k; @@ -55,6 +61,30 @@ int main() { printf("%s -> %d\n", *k, *v); } htab_free_storage_teststr_int(hp); + + HTAB_STORAGE(u32_u32) h2; + HTAB_STORAGE_INIT(&h2, u32_u32); + uint32_t h2_raw[501]; + memset(h2_raw, 0xff, sizeof(h2_raw)); + for (int i = 0; i < 3000; i++) { + uint32_t op = arc4random() & 1; + uint32_t key = (arc4random() % 500) + 1; + if (op == 0) { /* set */ + uint32_t val = arc4random() & 0x7fffffff; + *htab_setp_u32_u32(&h2.h, &key, NULL) = val; + h2_raw[key] = val; + } else { /* delete */ + htab_remove_u32_u32(&h2.h, &key); + h2_raw[key] = -1; + } + } + for (uint32_t k = 1; k <= 500; k++) { + uint32_t raw = h2_raw[k]; + uint32_t *hashedp = htab_getp_u32_u32(&h2.h, &k); + uint32_t hashed = hashedp ? *hashedp : -1; + /* printf("%d %x %x\n", k, raw, hashed); */ + assert(hashed == raw); + } } /* |