When programming in C for embedded systems where memory, disk usage and CPU usage are all very strict there are several ‘rules’ in place such as not use dynamically allocated arrays; this ensures that you can retain more control over memory management.
In a recent experience I had a fixed size array which was always populated below capacity, this array needed to be sorted which would normally leave my zero initialised elements at the start of my array and mess up my loop logic further on in the program.
I had an idea that I could use my sort comparison function to do two things – the first is the original sort purpose of ordering my elements, the second would be to move all unused elements to the end of the array.
Guess what, it’s very simple! I present the vinaigrette sort (so called because the oil and vinegar separate into layers in a vinaigrette).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* Vinaigrette sort example. Author: Jack Concanon Date: 14/05/2013 Website: www.acodemics.co.uk */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> const int BUF_SIZE = 14; const int NUM_SENSORS = 7; typedef struct { unsigned int id; float value; } Data; void printBuffer(Data *buf, unsigned size); int compare(const void *elem1, const void *elem2); int main(int argc, char* argv[]) { Data d[BUF_SIZE]; memset(d, 0, sizeof(Data)*BUF_SIZE); // Important to zero the array. srand(time(NULL)); unsigned i; for(i = 0; i < NUM_SENSORS; ++i) { d[i].id = rand(); // random ID number. d[i].value = rand(); // random sample value. } printf("-------- Unsorted array --------\n"); printBuffer(d, BUF_SIZE); // The Magic // Sort the d array by ID but at the same time // bubble empty elements to the end. qsort(d, BUF_SIZE, sizeof(Data), compare); printf("\n\n-------- Sorted By ID --------\n"); printBuffer(d, BUF_SIZE); return 0; } int compare(const void *elem1, const void *elem2) { const Data *da = elem1; const Data *db = elem2; if(db->id == 0) { return -1; } // Move empty elements to the end //if(da->id == 0) { return 1; } // Force empty structs to bubble to beginning. if(da->id > db->id) { return 1; } if(da->id < db->id) { return -1; } return 0; } void printBuffer(Data *buf, unsigned size) { // loop 'size' times over buf and print. unsigned i = 0; for(i = 0; i < size; ++i) { printf("%d %f\n", buf[i].id, buf[i].value); } } |
It is as simple as modifying the compare function required by the qsort function. Check if a field in your struct (or your data) is zero and therefore unused and then declare it as ‘greater’ than any comparison. I did find that an older GCC version (3.7) required the line as described in the above source code, GCC 4.7 compiled and ran as required with just the one comparison.
Note the memset line, if you leave the array uninitialised then the compare won’t have anything defined to search for that would signify an unused element.
Questions? Comments?