View unanswered posts | View active topics It is currently Sat Apr 19, 2014 4:27 am






Reply to topic  [ 11 posts ] 
ROBOTC Hashmap 
Author Message
Moderator
Moderator
User avatar

Joined: Tue Sep 14, 2010 9:19 pm
Posts: 496
Post ROBOTC Hashmap
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.


Attachments:
Hashmap.c [4.98 KiB]
Downloaded 566 times

_________________
sudo rm -rf /
Mon Apr 30, 2012 6:36 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: ROBOTC Hashmap
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

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Mon Apr 30, 2012 7:08 am
Profile WWW
Moderator
Moderator
User avatar

Joined: Tue Sep 14, 2010 9:19 pm
Posts: 496
Post Re: ROBOTC Hashmap
Thanks Xander. Issues have been addressed. It's pretty interesting making these data structures without certain resources that they're normally dependent on.

_________________
sudo rm -rf /


Mon Apr 30, 2012 7:40 am
Profile
Moderator
Moderator
User avatar

Joined: Thu Dec 22, 2011 7:42 am
Posts: 43
Post Re: ROBOTC Hashmap
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.

_________________
Visit my project RainBot v0.11 on source forge, a 6 wheels robot featuring A* & Dijkstra's path finding, motors & sensors emulation, small font, fifo & sorted list libraries, using Xander's drivers for HT Compass, and documented with doxygen.


Mon Apr 30, 2012 7:43 am
Profile
Novice
User avatar

Joined: Sat Jul 10, 2010 3:06 pm
Posts: 86
Location: Roanoke, VA
Post Re: ROBOTC Hashmap
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

_________________
Check out my website! www.RoboDesigners.com

VRC Team 2190

Twitter: @RoboDesigners


Mon Apr 30, 2012 6:42 pm
Profile WWW
Moderator
Moderator
User avatar

Joined: Tue Sep 14, 2010 9:19 pm
Posts: 496
Post Re: ROBOTC Hashmap
miki wrote:
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.

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.

RoboDesigners wrote:
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


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.

_________________
sudo rm -rf /


Mon Apr 30, 2012 7:00 pm
Profile
Moderator
Moderator
User avatar

Joined: Thu Dec 22, 2011 7:42 am
Posts: 43
Post Re: ROBOTC Hashmap
magicode wrote:
I get a tingling feeling like using so many macros is bad programming practice (I'm not saying it is).
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.

magicode wrote:
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.
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.

_________________
Visit my project RainBot v0.11 on source forge, a 6 wheels robot featuring A* & Dijkstra's path finding, motors & sensors emulation, small font, fifo & sorted list libraries, using Xander's drivers for HT Compass, and documented with doxygen.


Tue May 01, 2012 4:19 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: ROBOTC Hashmap
miki wrote:
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 :-)

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

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Tue May 01, 2012 4:38 am
Profile WWW
Moderator
Moderator
User avatar

Joined: Thu Dec 22, 2011 7:42 am
Posts: 43
Post Re: ROBOTC Hashmap
oh! :shock:
So pointers would come later ? 2013 isn't it ? :mrgreen:

It makes me good to laugh sometimes. :D ;-)
Mike

_________________
Visit my project RainBot v0.11 on source forge, a 6 wheels robot featuring A* & Dijkstra's path finding, motors & sensors emulation, small font, fifo & sorted list libraries, using Xander's drivers for HT Compass, and documented with doxygen.


Tue May 01, 2012 5:11 am
Profile
Moderator
Moderator
User avatar

Joined: Tue Sep 14, 2010 9:19 pm
Posts: 496
Post Re: ROBOTC Hashmap
What about:
Dick Swan wrote:
The lack of re-entrant functions is being addressed. Hopefully new version of ROBOTC this summer that support re-entrant functions and better pointer support.
-Feb 29, 2012

_________________
sudo rm -rf /


Tue May 01, 2012 10:41 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3105
Location: Rotterdam, The Netherlands
Post Re: ROBOTC Hashmap
We'll see when it happens :) Who knows which items get what priority in the coming months.

- Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Tue May 01, 2012 11:29 am
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 11 posts ] 

Who is online

Users browsing this forum: No registered users and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.