view CircularQueue.c @ 44:56855942fdc6

Split off background thread (threads only) termination and creation into separate functions from Interruption handling to make it easier to avoid race condition bug with Apple rdar://10081775 w.r.t. setting the OpenAL context. New APIs to suspend and resume update threads. Interruption handling calls these automatically. Also partially regressed simplification with regards to getting the current playing state in the main update loop.
author Eric Wing <ewing@anscamobile.com>
date Tue, 13 Sep 2011 18:03:21 -0700
parents 279d0427ef26
children
line wrap: on
line source

/*
    CircularQueue
    Copyright (C) 2002  Eric Wing

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library 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
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "CircularQueue.h"
#include <stddef.h> /* for NULL */
#include <stdlib.h> /* for malloc/free */
#include <stdio.h> /* for debugging */

CircularQueueUnsignedInt* CircularQueueUnsignedInt_CreateQueue(unsigned int max_size)
{
	CircularQueueUnsignedInt* ret_ptr;
	if(max_size < 1)
	{
		return NULL;
	}
	ret_ptr = (CircularQueueUnsignedInt*)malloc(sizeof(CircularQueueUnsignedInt));
	if(NULL == ret_ptr)
	{
		/* Out of memory */
		return NULL;
	}
	ret_ptr->internalQueue = (unsigned int*)malloc(sizeof(unsigned int) * max_size);
	if(NULL == ret_ptr->internalQueue)
	{
		/* Out of memory */
		free(ret_ptr);
		return NULL;
	}
	ret_ptr->maxSize = max_size;
	ret_ptr->currentSize = 0;
	ret_ptr->headIndex = 0;
	ret_ptr->tailIndex = 0;

	return ret_ptr;
}

void CircularQueueUnsignedInt_FreeQueue(CircularQueueUnsignedInt* queue)
{
	if(NULL == queue)
	{
		return;
	}

	free(queue->internalQueue);
	free(queue);
}

/**
 * Returns 1 if successful, 0 if failure.
 */
unsigned int CircularQueueUnsignedInt_PushBack(CircularQueueUnsignedInt* queue, unsigned int value)
{
//	printf("pushBack: %d\n", value);
	
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize >= queue->maxSize)
	{
		printf("failed to pushBack: %d\n", value);
		
		return 0;
	}
	temp_index = queue->tailIndex + 1;
	if(temp_index >= queue->maxSize)
	{
		/* need to wrap tail index around */
		temp_index = 0;
	}
	/* So with my implementation, the tail index actually points 
	 * to the slot right after the last value.
	 * So we will enter the value in the current tail, and then increment
	 * the tail.
	 * Note that in a full queue, the head and tail will be the same (I think).
	 */
	queue->internalQueue[queue->tailIndex] = value;
	queue->tailIndex = temp_index;
	queue->currentSize++;
		
	return 1;
}

/**
 * Returns 1 if successful, 0 if failure.
 */
unsigned int CircularQueueUnsignedInt_PushFront(CircularQueueUnsignedInt* queue, unsigned int value)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize >= queue->maxSize)
	{
		return 0;
	}

	/* This check is needed to prevent the unsigned int from overflowing. */
	if(0 == queue->headIndex)
	{
		/* Need to wrap head index around */
		temp_index = queue->maxSize - 1;
	}
	else
	{
		temp_index = queue->headIndex - 1;
	}
	/* So unlike the tail, the head index actually points to the element
	 * at the head, and not an element before (or after) the head.
	 */
	queue->internalQueue[temp_index] = value;
	queue->headIndex = temp_index;
	queue->currentSize++;
	return 1;
}

unsigned int CircularQueueUnsignedInt_PopFront(CircularQueueUnsignedInt* queue)
{
	unsigned int temp_index;
//	printf("PopFront: %d, %d\n", queue->headIndex,queue->internalQueue[queue->headIndex]  );
	
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize == 0)
	{
		return 0;
	}
	temp_index = queue->headIndex + 1;
	if(temp_index >= queue->maxSize)
	{
		/* need to wrap tail index around */
		temp_index = 0;
	}
	queue->headIndex = temp_index;
	queue->currentSize--;
	return 1;
}


unsigned int CircularQueueUnsignedInt_PopBack(CircularQueueUnsignedInt* queue)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize == 0)
	{
		return 0;
	}

	/* This check is needed to prevent the unsigned int from overflowing. */
	if(0 == queue->tailIndex)
	{
		temp_index = queue->maxSize - 1;
	}
	else
	{
		temp_index = queue->tailIndex - 1;
	}

	queue->tailIndex = temp_index;
	queue->currentSize--;
	return 1;
}

unsigned int CircularQueueUnsignedInt_Front(CircularQueueUnsignedInt* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	if(0 == queue->currentSize)
	{
		return 0;
	}
	return queue->internalQueue[queue->headIndex];
}


unsigned int CircularQueueUnsignedInt_Back(CircularQueueUnsignedInt* queue)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(0 == queue->currentSize)
	{
		return 0;
	}
	if(0 == queue->tailIndex)
	{
		/* need to wrap tail index around */
		temp_index = queue->maxSize-1;
	}
	else
	{
		temp_index = queue->tailIndex-1;
	}
	
	return queue->internalQueue[temp_index];
}

unsigned int CircularQueueUnsignedInt_Size(CircularQueueUnsignedInt* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	return queue->currentSize;
}

unsigned int CircularQueueUnsignedInt_MaxSize(CircularQueueUnsignedInt* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	return queue->maxSize;
}

void CircularQueueUnsignedInt_Clear(CircularQueueUnsignedInt* queue)
{
	if(NULL == queue)
	{
		return;
	}

	queue->currentSize = 0;
	queue->headIndex = 0;
	queue->tailIndex = 0;
}

void CircularQueueUnsignedInt_Print(CircularQueueUnsignedInt* queue)
{
	unsigned int i;
	unsigned int count;
	if(NULL == queue)
	{
		return;
	}
	fprintf(stderr, "Queue: ");
	for(count=0, i=queue->headIndex; count<queue->currentSize; count++, i++)
	{
		if(i >= queue->maxSize)
		{
			i=0;
		}
		fprintf(stderr, "%d ", queue->internalQueue[i]);
	}
	fprintf(stderr, "\n");
}

unsigned int CircularQueueUnsignedInt_ValueAtIndex(CircularQueueUnsignedInt* queue, unsigned int the_index)
{
	unsigned int i;
	if(NULL == queue)
	{
		return 0;
	}
	if(the_index >= queue->currentSize)
	{
		return 0;
	}
	i = (queue->headIndex + the_index) % queue->currentSize;
//	fprintf(stderr, "%d\n", queue->internalQueue[i]);
	return queue->internalQueue[i];
}

/*
 * Implementation for void* version starts here.
 */

CircularQueueVoid* CircularQueueVoid_CreateQueue(unsigned int max_size)
{
	CircularQueueVoid* ret_ptr;
	if(max_size < 1)
	{
		return NULL;
	}
	ret_ptr = (CircularQueueVoid*)malloc(sizeof(CircularQueueVoid));
	if(NULL == ret_ptr)
	{
		/* Out of memory */
		return NULL;
	}
	ret_ptr->internalQueue = (void**)malloc(sizeof(void*) * max_size);
	if(NULL == ret_ptr->internalQueue)
	{
		/* Out of memory */
		free(ret_ptr);
		return NULL;
	}
	ret_ptr->maxSize = max_size;
	ret_ptr->currentSize = 0;
	ret_ptr->headIndex = 0;
	ret_ptr->tailIndex = 0;

	return ret_ptr;
}

void CircularQueueVoid_FreeQueue(CircularQueueVoid* queue)
{
	if(NULL == queue)
	{
		return;
	}

	free(queue->internalQueue);
	free(queue);
}

/**
 * Returns 1 if successful, 0 if failure.
 */
unsigned int CircularQueueVoid_PushBack(CircularQueueVoid* queue, void* value)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize >= queue->maxSize)
	{
		return 0;
	}
	temp_index = queue->tailIndex + 1;
	if(temp_index >= queue->maxSize)
	{
		/* need to wrap tail index around */
		temp_index = 0;
	}
	queue->internalQueue[queue->tailIndex] = value;
	queue->tailIndex = temp_index;
	queue->currentSize++;
		
	return 1;
}

/**
 * Returns 1 if successful, 0 if failure.
 */
unsigned int CircularQueueVoid_PushFront(CircularQueueVoid* queue, void* value)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize >= queue->maxSize)
	{
		return 0;
	}

	/* This check is needed to prevent the unsigned int from overflowing. */
	if(0 == queue->headIndex)
	{
		/* Need to wrap head index around */
		temp_index = queue->maxSize - 1;
	}
	else
	{
		temp_index = queue->headIndex - 1;
	}
	queue->internalQueue[temp_index] = value;
	queue->headIndex = temp_index;
	queue->currentSize++;
	return 1;
}

unsigned int CircularQueueVoid_PopFront(CircularQueueVoid* queue)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize == 0)
	{
		return 0;
	}
	temp_index = queue->headIndex + 1;
	if(temp_index >= queue->maxSize)
	{
		/* need to wrap tail index around */
		temp_index = 0;
	}
	queue->headIndex = temp_index;
	queue->currentSize--;
	return 1;
}


unsigned int CircularQueueVoid_PopBack(CircularQueueVoid* queue)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(queue->currentSize == 0)
	{
		return 0;
	}

	/* This check is needed to prevent the unsigned int from overflowing. */
	if(0 == queue->tailIndex)
	{
		temp_index = queue->maxSize - 1;
	}
	else
	{
		temp_index = queue->tailIndex - 1;
	}

	queue->tailIndex = temp_index;
	queue->currentSize--;
	return 1;
}

void* CircularQueueVoid_Front(CircularQueueVoid* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	if(0 == queue->currentSize)
	{
		return 0;
	}
	return queue->internalQueue[queue->headIndex];
}


void* CircularQueueVoid_Back(CircularQueueVoid* queue)
{
	unsigned int temp_index;
	if(NULL == queue)
	{
		return 0;
	}
	if(0 == queue->currentSize)
	{
		return 0;
	}
	if(0 == queue->tailIndex)
	{
		/* need to wrap tail index around */
		temp_index = queue->maxSize-1;
	}
	else
	{
		temp_index = queue->tailIndex-1;
	}
	
	return queue->internalQueue[temp_index];
}

unsigned int CircularQueueVoid_Size(CircularQueueVoid* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	return queue->currentSize;
}

unsigned int CircularQueueVoid_MaxSize(CircularQueueVoid* queue)
{
	if(NULL == queue)
	{
		return 0;
	}
	return queue->maxSize;
}

void CircularQueueVoid_Clear(CircularQueueVoid* queue)
{
	if(NULL == queue)
	{
		return;
	}

	queue->currentSize = 0;
	queue->headIndex = 0;
	queue->tailIndex = 0;
}

void CircularQueueVoid_Print(CircularQueueVoid* queue)
{
	unsigned int i;
	unsigned int count;
	if(NULL == queue)
	{
		return;
	}
	fprintf(stderr, "Queue: ");
	for(count=0, i=queue->headIndex; count<queue->currentSize; count++, i++)
	{
		if(i >= queue->maxSize)
		{
			i=0;
		}
		fprintf(stderr, "%x ", (unsigned int)queue->internalQueue[i]);
	}
	fprintf(stderr, "\n");
}

void* CircularQueueVoid_ValueAtIndex(CircularQueueVoid* queue, unsigned int the_index)
{
	unsigned int i;
	if(NULL == queue)
	{
		return NULL;
	}
	if(the_index >= queue->currentSize)
	{
		return NULL;
	}
	i = (queue->headIndex + the_index) % queue->currentSize;
	//	fprintf(stderr, "%d\n", queue->internalQueue[i]);
	return queue->internalQueue[i];
}