diff options
| author | comex | 2015-07-12 23:00:57 -0400 |
|---|---|---|
| committer | comex | 2015-07-12 23:00:57 -0400 |
| commit | 985b1043b6285031cee976f5eeb8512a07e7acbb (patch) | |
| tree | 4df1533970a6a65a20f84181f3746217e37fe298 /lib/cbit/htab.h | |
| parent | aand, one last fix (diff) | |
| download | substitute-985b1043b6285031cee976f5eeb8512a07e7acbb.tar.gz | |
don't be n^2 for removal, lol. i should probably switch to rust's robin hood hashing - it isn't that much code and supposedly performs much better when the table gets full. *however*, it requires checking the hash of every entry in the chain during insert, which basically means storing it, which means more memory usage ... but by allowing fuller tables it could decrease memory usage. but if you have a big table anyway to avoid copying, you don't want *extra*... and storing the hash twice in the simple case is so dumb feeling. dunno.
Diffstat (limited to 'lib/cbit/htab.h')
| -rw-r--r-- | lib/cbit/htab.h | 33 |
1 files changed, 12 insertions, 21 deletions
diff --git a/lib/cbit/htab.h b/lib/cbit/htab.h index 7dbbf6b..2b3eeaa 100644 --- a/lib/cbit/htab.h +++ b/lib/cbit/htab.h @@ -114,36 +114,27 @@ struct htab_internal { 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)\ - cur = hi->base; \ + cur = (void *) buckets; \ + cur = (void *) ((char *) cur + 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; \ - } \ + /* 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, sizeof(key_ty)); \ + break; \ } \ 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; \ + if (!cf_after_hole) { \ + memcpy(hole, cur, entry_size); \ + hole = cur; \ + } \ } \ hi->length--; \ } \ |