Sorting my EEProm (without actually moving the stuff)

Go To Last Post
7 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What can I say? I'm a database guy!

My EEProm is full of 3 byte records. 170 of them.

typedef struct tSchedule
{
	uint8_t SWhat;
	int SWhen ;

}tSchedule;

tSchedule * Schedule = (tSchedule *) 0x1000 ; //Schedule data held in eeprom

To make this work, I have to tell the NVM controler to let me read the eeprom as memory: NVM_CTRLB |= (1<<3)

There are really 4 fields as SWhat is 2 4-bit fields. This is sounding like an old depression-era joke.

Now, I want to sort this "table" in eeprom, but not bother to actually move all the data around, just leave it where it lies. To do this, I made a mapper:

uint8_t ScheduleMap[170] ;

This takes up only 170 bytes of valuable ram, not 1/2 a K. I can fill it up with a loop like:

for(uint8_t i = 0 ; i<170; i++) ScheduleMap[i] = i ;

Now, I want to sort this ScheduleMap by the top 4 bits of SWhat and the value of SWhen. I could code up a quicksort myself, as I have done many times in the distant past, but there's one in the stdlib that should do nicely.

The trick is how to write the compare function. It gets two pointers into the ScheduleMap array:

int cmp_Schedule(const uint8_t *a, const uint8_t *b)

So I now index the array in eeprom as

   if((Schedule[a].SWhat & 0xf0) < (Schedule[b].SWhat & 0xf0)) return -1;

The compiler complains that my array index isn't an integer. Do I have to dereference the a and b?

   if((Schedule[*a].SWhat & 0xf0) < (Schedule[*b].SWhat & 0xf0)) return -1;

Also, it warns me on the call to QSort:

   qsort(ScheduleMap,170,1,cmp_Schedule);

That my function type doesn't match. The only example I find says to put the function as

int cmp_Schedule(const void *a, const void *b)

but gcc seems to disagree.

(The whole idea is to move the 1byte entries in ScheduleMap around 'stead of the data in the eeprom.)

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It is lovely to see your mind work.

For 170 elements it really does not matter what sorting algorithm that you use.
It also does not really matter if you copied everything from EEPROM to SRAM, sorted it, put it back again.

Reading EEPROM is fast, even if you have indexed it indirectly. Writing to EEPROM is slow, but I think the Xmega can take EEPROM pages. This should remove the pain from any block copy.

Incidentally, you can make a single pass of the EEPROM and just use an insertion algorithm for your indexing array.

David.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, I got the information I have from nonguru.org. Just not sure what to do with it.

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

david.prentice wrote:
It is lovely to see your mind work.

You mean my deranged, fixated, dyslexic and unemployed mind?

The eeprom gets scanned on reset, and then again if the user changes the configuration stored therein, so no, I don't suppose I need quicksort, but since it was already nearly coded, it seemed silly to write something myself.

SWhat of 255 means "unused," so to add a new one, I just grab the first one that contains a 255 and write it there. To delete one, I just change the SWhat to 255.

After initial configuration, the users might not change it for years. It also, can potentially run for months and not be turned off (May through October).

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ha! Just as I suspected!

Using the built-in QSort function is quite easy, much easier than coding and debugging my own sorter. The trick is to cast the compare function.

So, for anybody wanting to know how to do it:

The qsort function takes a pointer to the data to be sorted, the number of elements to sort, the size of each element, and a function.

This function takes 2 pointers and returns an integer.

These pointers are to 2 elements, and it needs to return <0 if "a0 if "a>b" and 0 if "a=b."

So code your function to take pointers to whatever you're sorting. Without any explanation of what or why I'm sorting this, here is my function:

int cmp_Schedule(const uint8_t *a, const uint8_t *b)
{
	if ((Schedule[*a].SWhat & 0xf0) < (Schedule[*b].SWhat & 0xf0)) return -1 ;
	if ((Schedule[*a].SWhat & 0xf0) > (Schedule[*b].SWhat & 0xf0)) return +1 ;
	if ((Schedule[*a].SWhen < Schedule[*b].SWhen)) return -1 ;
	if ((Schedule[*a].SWhen > Schedule[*b].SWhen)) return +1 ;
	if (ab) return 1 ;
	return 0 ;
}

So I'm actually sorting an array I call "ScheduleMap." This array contains indices into the xMega's eeprom. The array "Schedule" is this eeprom. Instead of tediously and slowly moving things around in eeprom, I'm just letting the qsort function swap things around in the ScheduleMap array.

So when qsort calls my compare function, the two parameters are pointers to uint8s. You see that I dereference these pointers to get the indices into the array, and compare data in the eeprom and return -1, +1 or 0. xMega's feature that makes eeprom appear as ram makes this almost easy.

The trick now, is making the call to qsort that uses this function.

qsort(ScheduleMap,170,1, (int (*)(const void *, const void *)) cmp_Schedule);

I've called qsort, giving it my array to sort, the number of elements in the array, the size of the element is 1, since it's just a number >= 0 and < 170 indexing the array in eeprom.

Next, you see a complicated cast needed to get the compiler to accept that the compare function takes 2 pointers and returns an int. I still don't know much about this cast, but I got it from an example at http://www.cse.unt.edu/~donr/cou... . So my suggestion is to do like me and just copy/paste the cast, unless your cmagery is good enough to make up this sort of cast on your own. Mine is most definitely not

If you don't know my whole story, keep your mouth shut.

If you know my whole story, you're an accomplice. Keep your mouth shut. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The alternative to avoid the case (there) is to give the compare routine the same interface as requested:

int cmp_Schedule(const void *a, const void *b) { ...

That does get you into the cmp_Schedule function without 'a' and 'b' having known pointer targets but you can then just remedy that locally with a possible easier to understand local cast:

int cmp_Schedule(const void *a, const void *b)
{
   const uint8_t *local_a = (const uint8_t *)a;
   const uint8_t *local_b = (const uint8_t *)b;

   if ((Schedule[*local_a].SWhat & 0xf0) < (Schedule[*local_b].SWhat & 0xf0)) return -1 ;
   if ((Schedule[*local_a].SWhat & 0xf0) > (Schedule[*local_b].SWhat & 0xf0)) return +1 ; 
etc..

Obviously perhaps call it something more sensible like:

int cmp_Schedule(const void *void_a, const void *void_b)
{
   const uint8_t *a = (const uint8_t *)void_a;
   const uint8_t *b = (const uint8_t *)void_b;

   if ((Schedule[*a].SWhat & 0xf0) < (Schedule[*b].SWhat & 0xf0)) return -1 ;
   if ((Schedule[*a].SWhat & 0xf0) > (Schedule[*b].SWhat & 0xf0)) return +1 ; 
etc..

So now the parameters arrive in void_a and void_b with out indication of what they point to then you assign them to pointers (with a cast) that do know what they are pointing to and use those. The invocation of qsort() then becomes simply:

qsort(ScheduleMap,170,1, cmp_Schedule); 

without the tortuous cast.

Or if you want to keep things the way they are I always put the complicated stuff out of the way in a typedef:

typedef int (*cmp_fn_ptr)(const void *, const void *);

...

qsort(ScheduleMap,170,1, (cmp_fn_ptr) cmp_Schedule);