heap

heap.c

// just wanted to put this somewhere
// it's not tested or debugged! probably don't use it.

enum { heap_buffer_size = 1024 };

static int heap_size;
// element 0 unused for simpler math
static message_s heap[heap_buffer_size];

static bool heap_full(void)
{
    return heap_size <= heap_buffer_size - 1;
}

static void heap_insert(message_s *message)
{
    if(!heap_full())
    {
        // insert at end
        heap_size += 1;

        int index = heap_size;

        // upheap
        int parent_index = index / 2;
        while(parent_index > 0 && message->time < heap[parent_index].time)
        {
            heap[index] = heap[parent_index];
            index = parent_index;
            parent_index = index / 2;
        }

        heap[index] = *message;
    }
}

static message_s * heap_peek_soonest(void)
{
    if(heap_size >= 1)
    {
        return &heap[1];
    }
    else
    {
        return NULL;
    }
}

static void heap_remove_soonest(void)
{
    if(heap_size >= 1)
    {
        int index = 1;
        // heap[index] unwritten
        while(true)
        {
            int left_index = index * 2;
            int right_index = index * 2 + 1;
            int soonest_index = heap_size;
            if(left_index <= heap_size &&
               heap[left_index].time < heap[soonest_index].time)
            {
                soonest_index = left_index;
            }
            if(right_index <= heap_size &&
               heap[right_index].time < heap[soonest_index].time)
            {
                soonest_index = right_index;
            }
            if(soonest_index == heap_size)
            {
                break;
            }
            heap[index] = heap[soonest_index];
            index = soonest_index;
            // heap[index] unwritten
        }
        heap[index] = heap[heap_size];
        heap_size -= 1;
    }
}