attractivechaos / klib

A standalone and lightweight C library

http://attractivechaos.github.io/klib/

MIT License

4.18k stars 556 forks source link

calculating size for flags array #93

Closed ctbtol84 closed 6 years ago

ctbtol84 commented 6 years ago

In the version "0.2.8" of khash you have changed the method used to calculate the size of the flags array (__ac_fsize). This change results in Keys being overwritten or not stored correctly. In my project, I changed the '__ac_fsize' function as following:

define __ac_fsize(m) (((m)>>4) + 1)

The following implementation:

define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)

does not ensure that the size of flags > n_buckets, right?

Thanks in advance, TB

attractivechaos commented 6 years ago

The current implementation is correct because m is always power-of-2. Your change is also correct, but will waste one 4-bit integer, probably with mmap allocation.

pskocik commented 5 years ago

Hi, attractivechaos. You can also remove the branching and shorten the code by calculating the flagset size with (((m)+15)/16) (or >>4 instead of /16 if you prefer the >> form).