Supporting Hardware without Floating Point Support

[Pusnow]

Hi, thank you for nice library!

Many embedded processors lack supports for floating points.
To use Verstable in these processors, I have to define MAX_LOAD as 1 or fallbacking to software-based floating point calculation.

It seems that Verstable uses floating points only for calculating table loads.
It would be nicer if Verstable supports load calculation based on integer arithmetics only.
(e.g., for 0.9 #define MAX_LOAD_N 9 / #define MAX_LOAD_D 10, THRESHOLD = (TOTAL * MAX_LOAD_N) / MAX_LOAD_D)

Also, if load calculation is done through bit operations (no multiplication and division), it would be faster in some low-end hardware.
(e.g., THRESHOLD = (TOTAL - (TOTAL >> 3)))

[JacksonAllan]

Hi! Sorry about the slow response.

This seems like a useful improvement. I'll think about how to best integrate it. Ideally it would be a non-breaking API change so that I can introduce it immediately. For example, perhaps we should allow the user to define MAX_LOAD_FN (a max-load function that takes the current bucket count as an argument and returns a size_t) as an alternative to MAX_LOAD.

In the meantime, the problem with simply defining MAX_LOAD as 1 as a work-around is primarily that when the table is full or nearly full, it will - on insertion - scan about 2,048 buckets before deciding that it needs to expand the bucket count. That will work but is pretty bad for insertion performance (lookup performance, on the other hand, should be relatively unaffected).

The maximum load factor is used in three separate places within the library. In the current version, those are the following lines:

Line 1273:

      VT_UNLIKELY( table->key_count + 1 > VT_CAT( NAME, _bucket_count )( table ) * MAX_LOAD ) ||

Line 1346:

      table->key_count + 1 > VT_CAT( NAME, _bucket_count )( table ) * MAX_LOAD ||

Line 1738:

  while( size > bucket_count * MAX_LOAD )

If you're not worried about overflowing a size_t by multiplying it by 9, I think you could just define MAX_LOAD as e.g. 9 / 10 (since the default is 0.9).

Otherwise, editing the right hand side of these comparisons to read VT_CAT( NAME, _bucket_count )( table ) - ( VT_CAT( NAME, _bucket_count )( table ) + 9 ) / 10 and bucket_count - ( bucket_count + 9 ) / 10 should, if I'm thinking clearly, achieve the same effect without any real overflow risk.

In either case, the compiler should replace the integer division with a multiplication and bit shift if optimizations are turned on.