Click here to Skip to main content
15,309,875 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.

C++
void*(*allocator)(size_t) // defaults to ::malloc

and
C++
void(*deallocator)(void*) // defaults to ::free


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?
Posted
Updated 15-Dec-21 0:13am
Comments
k5054 14-Dec-21 12:43pm
   
Quote:My PC is almost too fast for this Some possible work arounds would be to get a pi-zero and peg its max CPU freq to 700MHZ ( = min). That's still probably way faster than your IoT device, but it might be slow enough to evaluate code speed. Alternatively, maybe a Qemu, or other emulator, would suffice. Emulating is generally slow, so might be able to assist. With an emulator, even if you're emulating a Pi, you can probably limit the amount of RAM so you can get some idea how things are affected in that area too.
As to a hash tables, have you looked at hcreate/hsearch/hdestory? The big downside to those is that there can only be one hash table at a time, but there is a GNU extension hcreate_r() etc. that allows you to specify a search table. You could, of course, look a the code in gnu-libc, but then you get LGPL issues, which might be a deal breaker.

In the past, I have implemented a high performance hash table in shared memory using fixed array index tables. The hash table consisted of an array of indexes for each bucket. Then there was a corresponding table of next indexes for each possible item in the table so that constituted the "linked list." These were all fixed sizes (because of shared memory) and no dynamic allocations were used so it was very fast. The table index array was sized to be as big as it needed to be. Besides the bucket array there was another array of next indexes, one for each possible item in the table of data which was also in shared memory so it didn't take up very much space at all. This was a rather weird thing to do but it had its purpose and the speed made up for the weirdness.

I can elaborate in more detail if it looks like this might serve your purpose.
   
Comments
honey the codewitch 14-Dec-21 13:52pm
   
It's baking my noodle. I'll hit you up if I have questions. I'm not accepting just because I want more ideas but I'm +5ing your solution. :) Thanks.
You may have a look at Fraser and Hanson's "A Retargetable C Compiler: Design and Implementation". The authors show their implementations of both the allocator and the hash table used in LCC (I don't know if such implementations fit your needs).
They suggest Knuth, as ultimate reference.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900