|
Page 1 of 1
|
[ 11 posts ] |
|
Author |
Message |
magicode
Moderator
Joined: Tue Sep 14, 2010 9:19 pm Posts: 496
|
 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.
_________________ sudo rm -rf /
|
Mon Apr 30, 2012 6:36 am |
|
 |
mightor
Site Admin
Joined: Wed Mar 05, 2008 8:14 am Posts: 3654 Location: Rotterdam, The Netherlands
|
 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 |
|
 |
magicode
Moderator
Joined: Tue Sep 14, 2010 9:19 pm Posts: 496
|
 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 |
|
 |
miki
Moderator
Joined: Thu Dec 22, 2011 7:42 am Posts: 43
|
 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 |
|
 |
RoboDesigners
Novice
Joined: Sat Jul 10, 2010 3:06 pm Posts: 86 Location: Roanoke, VA
|
 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.comVRC Team 2190 Twitter: @RoboDesigners
|
Mon Apr 30, 2012 6:42 pm |
|
 |
magicode
Moderator
Joined: Tue Sep 14, 2010 9:19 pm Posts: 496
|
 Re: ROBOTC Hashmap
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.
_________________ sudo rm -rf /
|
Mon Apr 30, 2012 7:00 pm |
|
 |
miki
Moderator
Joined: Thu Dec 22, 2011 7:42 am Posts: 43
|
 Re: ROBOTC Hashmap
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.
_________________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 |
|
 |
mightor
Site Admin
Joined: Wed Mar 05, 2008 8:14 am Posts: 3654 Location: Rotterdam, The Netherlands
|
 Re: ROBOTC Hashmap
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 |
|
 |
miki
Moderator
Joined: Thu Dec 22, 2011 7:42 am Posts: 43
|
 Re: ROBOTC Hashmap
oh! So pointers would come later ? 2013 isn't it ?  It makes me good to laugh sometimes.  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 |
|
 |
magicode
Moderator
Joined: Tue Sep 14, 2010 9:19 pm Posts: 496
|
 Re: ROBOTC Hashmap
_________________ sudo rm -rf /
|
Tue May 01, 2012 10:41 am |
|
 |
mightor
Site Admin
Joined: Wed Mar 05, 2008 8:14 am Posts: 3654 Location: Rotterdam, The Netherlands
|
 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 |
|
|
|
Page 1 of 1
|
[ 11 posts ] |
|
Who is online |
Users browsing this forum: No registered users and 2 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
|
|