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