This isn't a physical project, but I think this is the most relevant forum to post in. I was going to wait until my finals were over, but curiosity got the better of me, and I made a hashmap for ROBOTC last night. It allows you to map any 'object' to a string. It's a real hashmap, but of course, some functions might slower than they should be because there is no dynamic memory allocation, and I had to make everything out of arrays (no linked lists for chaining collisions..ect).

Features:

HASH_PUT(str , data) : Inserts the data into the hashmap using 'str' as a key.

HASH_GET(str) : Gets the data referenced by 'str' from the hashmap. If you're using structs, you'll have to use memcpy(yourStruct, HASH_GET(structName), sizeof(yourStruct)) since you cant '=' structs.

HASH_REMOVE(str) : Removes the data referenced by 'str' from the hashmap, And frees up that memory (just for the hashmap's use of course).

HASH_CONTAINS(str) : Checks to see if the key exists in the hashmap. Returns true if it exists, false otherwise.

NUM_ITEMS_IN_HASH : Returns the number of items curently stored in the hashtable.

MAP_DATA_TYPE : Allows you to define what data type you want to put into the hashmap. Anything that's ROBOTC legal works.

HASH_CHOICE : Allows you to define what hashing function to use. You can choose from the 5 already written, or define your own. The choices are:
SIMPLE_HASH (default, not as computationally intensive as the others, and it seems to work well)
JAVA_HASH
JENKINS_HASH
FNV1A_HASH
BSDCHECK_HASH
CUSTOM_HASH - define your own in the format #define CUSTOM_HASH(str)

And there's other stuff that you can tweak to optimize performance, like max data set size, max hashmap size, and max collision array size.
To conserve space, the actual hashmap contains only ubyte values that correspond to array indexes where the actual data is stored; So, for example, if you were mapping large structs, you wouldn't need to allocate lots of unnecessary space.


I've tested it with ROBOTC Virtual Worlds, and everything I threw at it works. However, it's difficult to find good edge cases for this (especially at 3:00 A.M) and it's quite possible that there are bugs. Please test it out on various platforms and if you find errors, please let me know.

Awesome job! I think it is more intuitive to use HASH_PUT(key, data) than HASH_PUT(data, key). I've never seen it implemented in that order. Also, don't define things like NULL to numbers other than 0. There's an expectation for NULL to 0 or void or at least not 257

Useful additional features:
* Get the size of the current hash, ie how many elements are in there.

Next on the TODO list, self balancing binary trees, lists (double and single linked), circular buffers, queues and stacks

- Xander

Thanks Xander. Issues have been addressed. It's pretty interesting making these data structures without certain resources that they're normally dependent on.

Thanks for your code Magicode !

If I may do some suggestion too:
Name your different types of hash with explicit name, render them easy to understand and to keep them gather if you sort all your defines.
HASH_TYPE_SIMPLE
HASH_TYPE_JAVA
HASH_TYPE_JENKINS
HASH_TYPE_FNV1A
HASH_TYPE_BSDCHECK
HASH_TYPE_CUSTOM

Best regards
Miki.

Just verifying...

This is configured for a single instance of a hashmap, not multiple ones, right?

(Meaning, I can't define a hashmap called hm1 and another one called hm2?)

Great job on this, btw!

//Andrew

I'm not used to using preprocessor functions, so I don't know the etiquette. I get a tingling feeling like using so many macros is bad programming practice (I'm not saying it is). I just used them because you can't return anything other than primitive data types from methods, so for example, if the user puts a string into the hashmap, they have to do additional work to obtain their data from the method output. The macros just do that for you, and it didn't look right having macros for one functionality and methods for others.
I guess a plus side is that is saves some overhead.



Thanks And you are correct,you can't create multiple 'instances' of it. It'd be possible with even more multiply nested array indexes, but I didn't think anyone would want to use more than one in such memory starved platforms like the Cortex or NXT.

My remark about naming convention is very generic. It fits function name as well as variable or macro or whatever. When a program get huge or when you have to document it for other people, you have to organize not only the code itself but also its interface. All public names for functions, structures, global variables (if any) become important. IE it's easier to guess the role of function named 'list_insert_on_top()' than 'insert()'
Because you create a bundle of functions about hash, prefixing all names with 'hash_' or 'magicodeHash_' or any prefix that make sens is a good point.

macros can be usefull but I don't like them too because they hide code to people (let's say beginners) not knowing they are macro . I don't like C++ templates for the same reason.
In case they are mandatory for any good reason, using naming convention (like preprocessors tag are named using capital letters and underscore) is good tip to warn readers.
Btw, despite they use a same declaration syntax, I love C definitions that bring readability contrary to macro.

The lack of pointer management in RobotC brings all this complexity. In my project I made sorted lists and fifos tied to one specific element (COORD structure) to optimize size and speed. As soon a release of RobotC will brings pointer management, we all be able to transform our specific libraries (fifo, list, hash, etc) into more generic ones

Miki.

I fear the impending Mayan end of the World scenario is more likely to occur before we see pointers implemented in ROBOTC.

Hope Springs Eternal!

- Xander

oh!
So pointers would come later ? 2013 isn't it ?

It makes me good to laugh sometimes.
Mike

What about:

We'll see when it happens Who knows which items get what priority in the coming months.

- Xander