path: root/opl/opl_queue.c

// Emacs style mode select   -*- C++ -*- 
//-----------------------------------------------------------------------------
//
// Copyright(C) 2009 Simon Howard
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
//
// DESCRIPTION:
//     Queue of waiting callbacks, stored in a binary min heap, so that we
//     can always get the first callback.
//
//-----------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "opl_queue.h"

#define MAX_OPL_QUEUE 64

typedef struct
{
    opl_callback_t callback;
    void *data;
    unsigned int time;
} opl_queue_entry_t;

struct opl_callback_queue_s
{
    opl_queue_entry_t entries[MAX_OPL_QUEUE];
    unsigned int num_entries;
};

opl_callback_queue_t *OPL_Queue_Create(void)
{
    opl_callback_queue_t *queue;

    queue = malloc(sizeof(opl_callback_queue_t));
    queue->num_entries = 0;

    return queue;
}

void OPL_Queue_Destroy(opl_callback_queue_t *queue)
{
    free(queue);
}

int OPL_Queue_IsEmpty(opl_callback_queue_t *queue)
{
    return queue->num_entries == 0;
}

void OPL_Queue_Push(opl_callback_queue_t *queue,
                    opl_callback_t callback, void *data,
                    unsigned int time)
{
    int entry_id;
    int parent_id;

    if (queue->num_entries >= MAX_OPL_QUEUE)
    {
        fprintf(stderr, "OPL_Queue_Push: Exceeded maximum callbacks\n");
        return;
    }

    // Add to last queue entry.

    entry_id = queue->num_entries;
    ++queue->num_entries;

    // Shift existing entries down in the heap.

    while (entry_id > 0)
    {
        parent_id = (entry_id - 1) / 2;

        // Is the heap condition satisfied?

        if (time >= queue->entries[parent_id].time)
        {
            break;
        }

        // Move the existing entry down in the heap.

        memcpy(&queue->entries[entry_id],
               &queue->entries[parent_id],
               sizeof(opl_queue_entry_t));

        // Advance to the parent.

        entry_id = parent_id;
    }

    // Insert new callback data.

    queue->entries[entry_id].callback = callback;
    queue->entries[entry_id].data = data;
    queue->entries[entry_id].time = time;
}

int OPL_Queue_Pop(opl_callback_queue_t *queue,
                  opl_callback_t *callback, void **data)
{
    opl_queue_entry_t *entry;
    int child1, child2;
    int i, next_i;

    // Empty?

    if (queue->num_entries <= 0)
    {
        return 0;
    }

    // Store the result:

    *callback = queue->entries[0].callback;
    *data = queue->entries[0].data;

    // Decrease the heap size, and keep pointer to the last entry in
    // the heap, which must now be percolated down from the top.

    --queue->num_entries;
    entry = &queue->entries[queue->num_entries];

    // Percolate down.

    i = 0;

    for (;;)
    {
        child1 = i * 2 + 1;
        child2 = i * 2 + 2;

        if (child1 < queue->num_entries
         && queue->entries[child1].time < entry->time)
        {
            // Left child is less than entry.
            // Use the minimum of left and right children.

            if (child2 < queue->num_entries
             && queue->entries[child2].time < queue->entries[child1].time)
            {
                next_i = child2;
            }
            else
            {
                next_i = child1;
            }
        }
        else if (child2 < queue->num_entries
              && queue->entries[child2].time < entry->time)
        {
            // Right child is less than entry.  Go down the right side.

            next_i = child2;
        }
        else
        {
            // Finished percolating.
            break;
        }

        // Percolate the next value up and advance.

        memcpy(&queue->entries[i],
               &queue->entries[next_i],
               sizeof(opl_queue_entry_t));
        i = next_i;
    }

    // Store the old last-entry at its new position.

    memcpy(&queue->entries[i], entry, sizeof(opl_queue_entry_t));

    return 1;
}

unsigned int OPL_Queue_Peek(opl_callback_queue_t *queue)
{
    if (queue->num_entries > 0)
    {
        return queue->entries[0].time;
    }
    else
    {
        return 0;
    }
}

#ifdef TEST

#include <assert.h>

static void PrintQueueNode(opl_callback_queue_t *queue, int node, int depth)
{
    int i;

    if (node >= queue->num_entries)
    {
        return;
    }

    for (i=0; i<depth * 3; ++i)
    {
        printf(" ");
    }

    printf("%i\n", queue->entries[node].time);

    PrintQueueNode(queue, node * 2 + 1, depth + 1);
    PrintQueueNode(queue, node * 2 + 2, depth + 1);
}

static void PrintQueue(opl_callback_queue_t *queue)
{
    PrintQueueNode(queue, 0, 0);
}

int main()
{
    opl_callback_queue_t *queue;
    int iteration;

    queue = OPL_Queue_Create();

    for (iteration=0; iteration<5000; ++iteration)
    {
        opl_callback_t callback;
        void *data;
        unsigned int time;
        unsigned int newtime;
        int i;

        for (i=0; i<MAX_OPL_QUEUE; ++i)
        {
            time = rand() % 0x10000;
            OPL_Queue_Push(queue, NULL, NULL, time);
        }

        time = 0;

        for (i=0; i<MAX_OPL_QUEUE; ++i)
        {
            assert(!OPL_Queue_IsEmpty(queue));
            newtime = OPL_Queue_Peek(queue);
            assert(OPL_Queue_Pop(queue, &callback, &data));

            assert(newtime >= time);
            time = newtime;
        }

        assert(OPL_Queue_IsEmpty(queue));
        assert(!OPL_Queue_Pop(queue, &callback, &data));
    }
}

#endif