Hello,
I am maintaining a C application running on a tiny embedded platform with only a few hundreds bytes of RAM. The engine of this application is an event queue which is used for all communications between interrupt handlers, main code and all the modules. Because of the small amount of RAM available, I'd rather not use malloc and friends. Therefore, the queue is now implemented as a staticly allocated ringbuffer, something like this :
-------------------------------------------------------------------
enum event_type { EV_TYPE_A, EV_TYPE_B };
/* The various event types */
struct event_type a { enum event_type type; int some_data; };
struct event_type b { enum event_type type; char other_data[10]; };
/* The main event union holding all possible structs */
union event { enum event_type type; struct event_type_a a; struct event_type_b b; };
/* The ringbuffer */
#define QUEUE_SIZE 16
struct eventqueue_t { int head; int tail; uinion event event_list[QUEUE_SIZE]; };
-------------------------------------------------
Events are put in the queue filling the event_list array at the 'head' position, and retrieved from the queue by reading the array_list from the tail position. Nothing special here.
void event_push(event *ev) { eq.event[eq.head] = *ev; eq.head = (eq.head + 1) % QUEUE_SIZE; }
et cetera.
This all works like a charm, but for a new application I need some kind of priority mechanism; events with low priority are just added to the end of the queue, but high-prio events should be inserted just before other events with the same priority. This would be no problem when the queue was implemented as some kind of dynamic data structure (linked list, etc), but as I said before, this is no option because of memory restrictions.
With the current queue implementation, I would need to re-shuffle data in the array for every inserted event to make room for new higher-priority events, which is not optimal, of course. My current solution is to use seperate queues for different priorities, but this tends to waste a lot of memory.
Does anybody have ideas how to create a tiny-footprint, efficient priority-queue without using any dynamic memory allocation ? Any ideas or pointers to books/documentation are welcome,
Thank you,