Re: [RFC] Adding a real HashTable implementation to gnulib

[Tim Rühsen]

On 12/4/18 3:32 AM, Bruno Haible wrote:
> Hi Tim,
> 
>> We have 'hashmap' [1] in GNU Wget2.
> 
> Things I like about the implementation:
> 
>   - Collision resolution through linked list (a robust algorithm).
> 
>   - Reasonably generic API.
> 
>   - The user-definable destructor functions.
> 
> Things that could be improved:
> 
>   - The ability to set a growth policy > 0. This leads to quadratic
>     run time behaviour. I mean, you make such an effort to have O(1)
>     access on average, and then the fixed-size increment of the size
>     turns the insertion operation into an average-O(n) operation.

Changed now, only supporting a float number as factor now.


>   - Some functions take keysize and valuesize arguments, some don't.
>     I'm confused.

That has a reason, I'll answer with examples in a second email. Not
enough time right now.


>   - NULL values are special. The documentation says "If there are NULL
>     values in the stringmap, you should use wget_stringmap_get_null() to
>     distinguish between 'not found' and 'found NULL value'." I would
>     prefer an API that does not require me to think about whether I have
>     null values in the map or not.

API has been changed to handle NULL values without thinking (put and get).


>   - To iterate through the table, you need to define an instance of the
>     wget_hashmap_browse_t function. I love functional programming, but
>     C is not the right language for that. If the inner part (the body
>     of the 'browse' function) needs to access outer variables, the
>     programmer needs to manually create a "context" struct and fill it -
>     things that the compiler would be doing in other programming languages.
>     Some people say that the solution to this problem are the nested
>     functions supported by GCC, but
>       1. This is not portable; only GCC supports this.
>       2. On many CPUs (including x86_64), the use of nested functions
>          requires to disable on the entire process a security feature
>          (namely, stacks without execute permission).
>     I therefore prefer the concept of "iterator" objects that allow
>     the programmer to step through the hash table without contorting
>     their code and without compromising on security.

Iterators are now implemented with three functions (...alloc, ...free,
...next).

BTW, nested functions are pretty nice to use.

But I still wonder why

 - nested functions need an executable stack (why does the code have to
be run on the stack ?)

 - there are no efforts to standardize either nested functions or blocks
(clang has 'blocks' instead of nested functions) or both. (There is a
C22 panel, but I couldn't find anything useful on their task list.)

Regards, Tim

signature.asc
Description: OpenPGP digital signature