http://forums.leaflabs.com/topic.php?id=837 A place to share, learn, and grow... en-US Fri, 22 Jan 2016 00:27:00 +0000 http://bbpress.org/?v=1.0.2 q http://forums.leaflabs.com/search.php http://forums.leaflabs.com/topic.php?id=837#post-5035 Tue, 07 Jun 2011 08:06:19 +0000 gbulmer 5035@http://forums.leaflabs.com/ <p>gregorius - there are a few different ways you might go about this. Could you give a few more requirements?</p> <p>Are you interested in a highly optimised solution, or will something simple be preferable?</p> <p>Does the program need to be relatively fast, i.e. does it need to do, say, more than 1,000 lookups/second?<br /> Will the program add to the data, i.e. add new numbers and names, while it is being used?<br /> Are updates frequent, i.e. several/second, or rare, i.e. one/day.<br /> Will the program need to remove names and numbers while it's being used (unusual to do this, but maybe)?<br /> Are deletions frequent or rare?<br /> Is there any information about 'hit' patterns, i.e. is a small number of caller-IDs likely to be the majority of lookups?<br /> Does the program need to store a relatively short name, like older mobiles which might only have 12-14 characters, or does it need to store a name no matter how long it is?</p> <p>If it is fixed data, all known ahead of time, and it must be extremely quick at lookup, you could use a perfect hash:<br /> <a href="http://en.wikipedia.org/wiki/Perfect_hash_function" rel="nofollow">http://en.wikipedia.org/wiki/Perfect_hash_function</a><br /> Make it even easier by using a fixed size for names. Run the algorithm to generate the perfect hash on a host PC. To decouple the code from the data, load the data and hash terms into serial flash (with a little program), and the lookup program might read the hash terms when it starts.</p> <p>For a more traditional solution, almost any algorithm book will give plenty of solutions. Look for something which is suitable for disk access. If the names are fixed length, or you are willing to allocate multiples of a fixed length, you can treat the actual storage as an array of entries which makes storage management easier.</p> <p>If it can afford a few seconds start up time, the program can scan the entire flash, and come up with in-RAM structures to help with access.</p> <p>If additions are rare, and could be handled as a 'batch', you could hash with an overflow, and do a linear search on the overflow, then reorganise periodically.</p> <p>If simplicity dominates over speed, just keep a big array of entries in flash and do a binary search. The memory is 4MByres, so about 200,000 entries. With a binary search, that is only 18 'probes' into the flash memory.</p> <p>Anyway, please tells us whatever requirements you feel comfortable share, and we might be able to help.</p> <p>(full disclosure: I am not a member of LeafLabs staff) </p> http://forums.leaflabs.com/topic.php?id=837#post-5012 Mon, 06 Jun 2011 22:37:53 +0000 gregorius 5012@http://forums.leaflabs.com/ <p>Hi,</p> <p>Let's say I want to write a Caller-ID that links phone numbers to a caller's name and I wanted to include many many numbers from a file that is formated as such</p> <p>"<br /> 555-2718 Joe Shmoe<br /> 555-1618 Jane Doe<br /> 555-3145 John Smith ... "</p> <p>I would like to store the name data as char[] data in an external serial flash chip (I'm using <a href="http://parts.digikey.com/1/parts/1904100-ic-flash-ser-32m-80mhz-spi-8soic-sst25vf032b-80-4i-s2af.html" rel="nofollow">http://parts.digikey.com/1/parts/1904100-ic-flash-ser-32m-80mhz-spi-8soic-sst25vf032b-80-4i-s2af.html</a> - which seems to be reading/writing fine). Would I use a hash table to link phone numbers to memory indices/Is there a hash table implementation? How would I program the flash chip with all the data beforehand?</p> <p>Sorry if these are obvious questions, while I've done a fair amount of C/C++, embedded programming is pretty new to me. </p>