It really frustrates me that there is not an easy way to do a hash table in C, and that in C++ it requires a ton of buy-in from the STL, when all they really need is a handful of static functions. Particularly in the IoT realm, in environments like the Arduino framework the STL implementation isn't complete and sometimes isn't so standard, often due to limitations, like running on an 8-bit CPU.
I've thought about implementing one, because it's begging to be done, but I'm suffering analysis paralysis I can't crack, and that has to do with memory allocations. It's why I've avoided re-implementing STL'less containers thus far.
Memory is weird in IoT. You have DMA capable memory, external memory (usually PSRAM), and then a small amount of SRAM, only part of which is usable because it also serves as the CPU code cache.
The bottom line is you have to control allocations, rather than letting the library do it.
So for example, at the very least, I'll take two function pointers in anything that needs to allocate memory.
void*(*allocator)(size_t)
and
void(*deallocator)(void*)
That way the owner of the library can choose how to allocate ram when it's needed. It's vital so that you can do things like store the data in PSRAM (which you often have a lot more of than SRAM)
But even if I do that, there are cases where I'll need it on the stack or in a global, and it doesn't need to be resized at all.
I'm thinking two different classes unless someone has a better idea. My other option is to create some kind of memory handler template I can make the hashtable use but I'm wary of the extra buy in if it can be avoided.
As far as getting the hash itself I can solve the problem of actually generating a hash code using a function pointer, so no big deal.
A) is there good code you think I can adapt (must be MIT compatible) that already has stuff like this? I haven't found anything I'm satisfied with thus far. It has to be as simple as possible, and relatively efficient.
B) I can't decide whether to use a vector style container or a linked list style container to hold the items in the resizable rendition of the code. Does anyone have any experience implementing hash tables that could point me in the right direction in this regard?
What I have tried:
I've found this:
HashTable/src at master · ijh165/HashTable · GitHub[
^]
Which is pretty close to what I want, but I'm not sure how to evaluate it in terms of performance. My PC is almost too fast for this, and I can't run a std::map on IoT where I'd like. Does it look okay to you?
Submit an article or tip