4 ms·
FWIW there's a standard hash table API in POSIX.
by varjag 6y ago
FWIW there's a standard hash table API in POSIX.
- jandrese 6y agoYeah, but it's pretty lame since you have to specify the size of the table up front and can't change it later. They didn't implement the hard stuff!
- ludocode 6y agoThere are many reasons why it's lame! Here's a short list: - There is only one global hash table for the whole process! If you want individual hash tables you need to use implementation-specific extensions (hcreate_r().) - There is no way to remove a key from a hash table. No implementation I know of provides an extension to do it. If you want to truly remove a key you must destroy and rebuild the table. - There is no requirement for a means to grow the table. On some platforms it's possible to run out of space. If you want to truly grow you must destroy and rebuild the table. - There is no standard way to free keys or data stored in the table. Destroying the table leaks all contents; you must keep track of keys and data externally and free them yourself. Only OpenBSD frees keys by default, and only NetBSD has extensions to call callbacks to free keys and data. - Keys must be strings. You cannot provide custom types or void pointers as keys. There is no way to specify custom hash or comparison functions. The quality of the hash function is unspecified. - When using ENTER, you may not want to allocate the key unless it is necessary to insert a new entry. Since the given key is inserted directly, it's not necessarily safe to use a stack-allocated buffer for lookups. It's awkward to replace the key with an allocation after insertion and it's unclear whether it's allowed. This doesn't even get into incompatibilities between the various implementations. You will encounter all of the above flaws even if your only target is glibc. No one should ever be encouraged to use POSIX hash tables. They should be deprecated and we should all just pretend they don't exist.
- jandrese 6y agoIMHO this is one area where the C committee could improve the situation by mandating a sane and useful hashtable implementation for the stdlib. Or at the very least just deprecate the old one. I can't remember ever seeing it used in code.
- coliveira 6y agoHash tables in C are not part of the standard. They are part of POSIX, so it is mandated only on UNIX-ish environments. The standard committee has nothing to do with that.
- jandrese 6y agoMaybe the should be. I know C is all about staying minimal, but native hash tables have proven themselves to be extremely useful in every other language where they are present.
- NwtnsMthd 6y agoWow, that's quite the list! Why was such a bad (overly simplistic?) implementation allowed into a standard library?
- queuebert 6y agoThis might sound stupid, but could you store N-1 entries, and then store a pointer to the next hash as the Nth entry? So you dynamically add fixed tables as you run out of space? Yes, I realize the lookup would get complicated.
- banana_giraffe 6y agoNope. The POSIX API lets you have one table. There is a GNU extension that lets you have more than one table.