hashtable related

[pranamesh]

Posted on August 06, 2009 at 13:06

hashtable related

[pranamesh]

Posted on May 17, 2011 at 13:19

this is more of a software question (but still related to the MCU domain). and since I am using the stm32 MCU, I request some guidance on this topic before I move to the next step from persons in similar situations.

I have data coming into my UART1 for which I have to display pre stored (in the flash) info based on the value of the incoming data into my LCD. My problem is that this is excess of 2000 in individual numbers of data items. Simple switch/case is not suitable as it would be messy (and may be inefficient). I intend to use a hash-table for my purpose which in the normal (i.e. PC) domain, is the best solution for such a requirement. the incoming data is not in serial order but belong to a known set of data (2000 in no.) My questions are therefore 1: Is there a sample code for a *simple* hash-table in C that I can take as a starting point of my implementation (there are non in the GCC compiler/library I can find; well there are non in C for that matter!) 2: From memory perspective, how expensive is this solution (i understand it is dependent on the code, therefore I need a simple i.e. small code implementation) 3: are there any better solution with better being = small memory foot print (a slow code i.e. from execution point of view, will do) FIY my UART data rate is at 9.6 kbps, but this is immaterial. thanks in advance :-[

[st3]

Posted on May 17, 2011 at 13:19

You really need to give more information about the relationship between the ''value of the incoming data'' and the ''info'' to be displayed.

eg, why can't you just use a straightforward lookup table (ie, an array)?

[mvi]

Posted on May 17, 2011 at 13:19

Hi Pranamesh,

I agree with ST7. I think the easiest solution would be a lookup table depending on the data of course. This method would require a certain level of linearity between the data and the index. datatype data[2000] = {x, y, z, ...}; uint16_t key = 0; ... key = receivedData + offset; lcdDisplay(data[key]); This is a ''simple'' hash. Hope it helps. -Mad [ This message was edited by: mvi on 06-08-2009 01:50 ]

[pranamesh]

Posted on May 17, 2011 at 13:19

Thanks for your replies.

Ok, may be I did not clarify properly. When I wrote ''incoming data is not in serial order'' I meant the following The incoming data is in the range of 0x0000 to 0x4268, i.e. 0 to approx 17000. Out of this they are segregated into about 10 groups with about 200 in each, spread across the above range. So I have, say...0x0000, 0x0200, 0x0005.... 0x0107......0x06A4 for the first group and so on. Basically there is no linearity. Therefore if I use a look up table in the form of an array then I have to fill 17000 places of which only 2000 are important and useful rest will only occupy memory without any use. With this background I was hoping to use the hash-table. However my issue in using the hash-table was that it should have an overall memory footprint less than 17000*15 (assuming I occupy 15 bytes per array item, approximately + some overhead for the array and hash-table structures) st7, Info to be displayed is a 15 byte ASCII text explaining the incoming data with the data being treated as an incoming code from the application's point of view. Another specific point for simplification is that the table needs to be filled only once per application start-up, i.e. in the beginning. thereafter it is read only. There is no dynamic filling, removing or updating the data in the table. The ASCII text will also be part of the code to simplify matters for now. The issue with me is that I have been programming extensively for many years but on PC environments mostly under managed run times where I never bothered about system's resources until we started this embedded work recently, where I am being confronted to get my code perform with limited resources. So any help is highly appreciate. 8-)

[domen2]

Posted on May 17, 2011 at 13:19

How about a sorted array of these:

struct element { int id; const char *text; }; Then you can use binary search to quickly find your id and matching text. Or just an unsorted array, maybe it's fast enough for you.

[ivanov-i]

Posted on May 17, 2011 at 13:19

Hi Pranamesh,

You could simply use a sorted array of the keys and their corresponding strings. Then a binary search in the sorted array will return the correct index by only 11 compare instructions. If the data is static you could declare the array as ''const'' and fill it by values in the C source. Regards, Ivan Oops, someone posted this idea already...[ This message was edited by: ivanov-i on 06-08-2009 10:01 ]

[st3]

Posted on May 17, 2011 at 13:19

Quote:

How about a sorted array

Or, perhaps, a few (possibly sorted) arrays - each convering a ''range'' of possible input values...? [ This message was edited by: st7 on 06-08-2009 13:10 ]

[kutnickg]

Posted on May 17, 2011 at 13:19

There are a lot of compromises between space and lookup time you can make depending on what results you're after. You can have a direct lookup table that's 17000 * 2 bytes and stores indexes into a more compact 2000 * 15 byte table holding the actual data. You can then segregate that table either into sorted segments like suggested before or into multiple levels (like how page tables typically work). What works best will depend on how sparse your data is and where the holes are.

[pranamesh]

Posted on May 17, 2011 at 13:19

yes! this would do the job. Thanks to all!!

sorted data is no problem. I would also use a small cache as *most likely* the same data arrives per application run (for that specific feature). This would reduce my need to use the bsearch all the time. :D