prique

main.c

#include <stdio.h>
#include "prique.h"

void prique_dump( prique * p )
{
	printf("DUMP:\n");
	prique_iter begin = prique_begin(p);
	size_t size = prique_size( p );
	for( size_t i = 0; i < size; ++i ) {		
		printf("> %d [%d]\n", begin.value->deadline, begin.value->value);
		begin = begin.step( &begin );
	}
	printf("DUMP END.\n");
}

void insert_data( prique * p ) {
	printf("IN insert_data()\n");
	printf("Inserting data\n");
	prique_dump( p );
	prique_priority_insert( p, 100, 101);
	prique_priority_insert( p, 200, 201);
	prique_priority_insert( p, 150, 151);
	prique_priority_insert( p, 150, 152);
	prique_priority_insert( p, 1, 1);
	printf("Data inserted\n");
	prique_dump( p );
	printf("OUT insert_data()\n");
}

void pop_all( prique * p ) {
	printf("IN pop_all()\n");
	printf("Current state:\n");
	prique_dump( p );	
	printf("Start popping:\n");
	while( prique_size( p ) > 0 ) {
		printf("Popping: %d\n", prique_pop( p ).value );
		prique_dump( p );
	}
	printf("OUT pop_all()\n");
}

void clear( prique * p )
{	
	printf("IN clear()\n");
	printf("State before:\n");
	prique_dump( p );
	prique_clear( p );
	printf("State after:\n");
	prique_dump( p );
	printf("OUT clear()\n");
}

void fill_too_much( prique * p )
{
	size_t const elem_count = PRIQUE_MAX_CAPACITY + 5;
	for( size_t i = 0; i < elem_count; ++i ) {		
		int16_t result = prique_priority_insert( p, i, i );
		if( i >= PRIQUE_MAX_CAPACITY ) {
			printf(
				"Expecting error: %d Actual error: %d Result: %s\n", 
				E_PRIQUE_NO_MEM, 
				result, 
				result == E_PRIQUE_NO_MEM ? "SUCCEEDED!" : "FAILED!"
			);
		}
		else {
			printf(
				"Expecting error: %d Actual error: %d Result: %s\n", 
				E_PRIQUE_OK, 
				result, 
				result == E_PRIQUE_OK ? "SUCCEEDED!" : "FAILED!" 
			);
		}
	}
}

int main()
{
	prique p = {};
	insert_data( &p );
	pop_all( &p );
	insert_data( &p );
	clear( &p );
	fill_too_much( &p );
	return 0;
}

prique.c

#include "prique.h"

prique_item * prique_next( prique * queue, prique_item * item )
{
	if( item == queue->data + queue->count -1 ) {
		item = queue->data;
	}
	return ++item;
}

prique_item * prique_prev( prique * queue, prique_item * item )
{
	if( item == queue->data ) {
		return queue->data + queue->count;
	}
	return --item;
}

prique_iter prique_step_next( prique_iter * iter )
{
	prique_iter step_iter = { 
		.queue = iter->queue, 
		.value = prique_next( iter->queue, iter->value ),
		.step = iter->step 
	};
	return step_iter;
}

prique_iter prique_step_prev( prique_iter * iter )
{
	prique_iter step_iter = { 
		.queue = iter->queue, 
		.value = prique_prev( iter->queue, iter->value ),
		.step = iter->step 
	};
	return step_iter;
}

prique_iter prique_begin( prique * p )
{
	prique_iter iter = {
		.queue = p,
		.value = p->data + p->start_offset,
		.step  = prique_step_next
	};
	return iter;
}

prique_iter prique_rbegin( prique * p )
{
	size_t last = p->start_offset + p->count - 1;
	if( p->start_offset > PRIQUE_MAX_CAPACITY - p->count )
	{
		last = PRIQUE_MAX_CAPACITY - p->count;
	}

	prique_iter iter = {
		.queue = p,
		.value = p->data + last,
		.step  = prique_step_prev
	};
	return iter;
}

int16_t prique_append( prique * p, prique_item * item ) {
	if( !p || !item ) {
		return E_PRIQUE_INVALID_PARAM;
	}

	if( p->count >= PRIQUE_MAX_CAPACITY ) {
		return E_PRIQUE_NO_MEM;
	}	

	++p->count;
	*prique_rbegin( p ).value = *item;

	return E_PRIQUE_OK;
}

void prique_swap( prique_item * a, prique_item * b ) 
{
	if( a && b )
	{
		prique_item tmp = *a;
		*a = *b;
		*b = tmp;
	}
}

void prique_dump( prique * p );

void prique_dump_titled( prique * p, char const * title )
{
	printf("BEGIN %s\n", title);
	prique_dump(p);
	printf("END %s\n", title);
}

int16_t prique_priority_insert( prique * p, uint16_t deadline, prique_value_type value ) {
	if( !p ) {
		return E_PRIQUE_INVALID_PARAM;
	}

	if( p->count >= PRIQUE_MAX_CAPACITY ) {
		return E_PRIQUE_NO_MEM;
	}
	
	prique_item item = { 
		.deadline 	= deadline, 
		.value 		= value 
	};

	if( p->count ) {
		// Increasing the count to point end behind the last and being able to insert
		++p->count;	
		// We're starting at the beginning
		prique_iter begin = prique_begin( p );	
		// And ending after the last item
		prique_iter end = prique_rbegin( p );
		// Find location
		for(; begin.value != end.value; begin = begin.step(&begin) ) {
			if( begin.value->deadline > deadline ) {
				// location found
				// saving current value to be able moving the rest
				prique_item saved = *begin.value;
				// inserting item
				*begin.value = item;			

				// Move the rest to the end
				for(begin = begin.step(&begin); 
					begin.value !=  end.value; 
					begin = begin.step(&begin) ) {
					prique_swap( begin.value, &saved );
				}
				// Final assignment
				*begin.value = saved;
				// We're done
				return E_PRIQUE_OK;
			}
		}
		// We did not find the item, so we'll append 
		// (for that we have to decrease the count again we increased just before )
		--p->count;
	}
	// Use append
	return prique_append( p, &item );
}

prique_item prique_top( prique * p )
{
	return *prique_begin( p ).value;
}

prique_item prique_pop( prique * p )
{
	prique_item item = prique_top(p);
	--p->count;
	++p->start_offset;
	if( p->start_offset == PRIQUE_MAX_CAPACITY ) {
		p->start_offset = 0;
	}
	return item;
}

void prique_clear( prique * p )
{
	prique cleared = {};
	*p = cleared;
}

size_t prique_size( prique * p )
{
	return p->count;
}

prique.h

#ifndef GUARD_PRIQUE_PRIQUE_H_INCLUDED
#define GUARD_PRIQUE_PRIQUE_H_INCLUDED

#include <stdint.h>
#include <stdlib.h>

#define PRIQUE_MAX_CAPACITY 16

enum prique_error {
	E_PRIQUE_INVALID_PARAM = -2,
	E_PRIQUE_NO_MEM = -1,
	E_PRIQUE_OK = 0
};

typedef uint16_t prique_value_type;

typedef struct prique_item_
{
	uint16_t 			deadline;
	prique_value_type 	value;
} prique_item;

typedef struct prique_
{
	prique_item data[PRIQUE_MAX_CAPACITY];
	size_t count;
	size_t start_offset;
} prique;

typedef struct prique_iter_
{
	prique * queue;
	prique_item * value;
	struct prique_iter_ (*step)( struct prique_iter_ * );
} prique_iter;

prique_item * prique_next( prique * queue, prique_item * item );
prique_item * prique_prev( prique * queue, prique_item * item );

// Get the first item in the circular buffer for iterating through it forward
prique_iter prique_begin( prique * p );

// Get the last item in the circular buffer for iterating through it backward
prique_iter prique_rbegin( prique * p );

// Insertion 
int16_t prique_priority_insert( prique * p, uint16_t deadline, prique_value_type value );

// Retrieve the top item
prique_item prique_top( prique * p );

// Pop top item
prique_item prique_pop( prique * p );

// Clear the whole queue
void prique_clear( prique * p );

// Count of items in the queue
size_t prique_size( prique * p );

#endif //GUARD_PRIQUE_PRIQUE_H_INCLUDED