Mercurial > almixer_isolated
view CircularQueue.c @ 41:e10dd3056782
Added API to check if in interruption.
Added more internal check if in interruption checks.
Fixed pathological sleep disorder on iOS problem...bug was I forgot to convert microseconds to milliseconds in usleep calls which led to very short sleep times and the pathological sleep disorder problem. Thanks so much oto Kapil K. for spotting this problem for me.
author | Eric Wing <ewing . public |-at-| gmail . com> |
---|---|
date | Thu, 23 Jun 2011 17:37:16 -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]; }