> > > Think 'hash table'
> >
> > I was thinking b-tree.
> >
> > michael brown

I would really reccomend that you stay away from hashing at all. Never
hash a serial number that already fits into a reasonable ammount of
space. Hashing is really only useful when trying to take a large key of
data (ie a string, file, whole record, etc) and make it into a new key
that can be easily sorted/indexed/etc. A card # that is 1 to 10 milion
already fits nicely into 24 bits. Hashing this small ammount of data
will only complicate things.

A b-tree structure would be optimal for speed, but with the small
ammount of records you will be dealing with, a keyed linked list (aka
dictionary) will be far easier to code on a PIC.

Start by breaking your data storage (flash, battery backed sram, hdd,
etc) into blocks/records that are big enough to hold the data you need.
That way you can index each record. In this case the card#, ptr to next
record in list, date activated, data, and anything else you plan to
store.

When you insert a record (by scanning the card) traverse the list until
you find the 2 records that your new record will need to insert itself
between. That should be as simple as a less than check on the card #s.
You can even speed that up by comparing it byte by byte (msb first).
Then allocate a new record. You can keep a counter and incrementally
scan the memory for free/expired records to average the wear on the
flash. Make the new record point to the next in list and make the
previous in list point to the new record.

When you need to redeam a card, just run through the list. When you
find it, make the previous record point to the record after the
redeamed record and clear the redeamed record. double check the date
only if you want minute by minute expiration.

Every midnight scan the list and delete (as described above) records
that expire.

Each time you insert or remove a record you will end up altering 3
records. If you have 8640 activations and 8640 redemptions/expirations
a day thats 51,600 distributed flash/eeprom record writes per day. If
your flash was just big enoug to hold 120960 records, thats average of
about half a write per day. The larger a flash you use, the more
distributed the wear will be. If it is a heavily used vending machine
in a long term installation you might want to use battery backed sram.
Maxim has good lithium backed srams with an integrated RTC that lasts
10 years without power in a nice dip package. They are pricy for sram,
but since you share the data source it might be worth it in terms of
design complexity and service calls.


Hope that helps,
  Ben Hencke









__________________________________
Do you Yahoo!?
Yahoo! Photos: High-quality 4x6 digital prints for 25"
http://photos.yahoo.com/ph/print_splash

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics