[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Tim Rühsen
Subject: Re: [RFC] Adding a real HashTable implementation to gnulib
Date: Thu, 3 Jan 2019 17:32:51 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0

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,

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

Attachment: signature.asc
Description: OpenPGP digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]