Me@19: /* seanhalle@44: * Copyright 2009 OpenSourceResearchInstitute.org Me@19: * Licensed under GNU General Public License version 2 Me@19: * Me@19: * NOTE: this version of SRSW correct as of April 25, 2010 Me@19: * Me@19: * Author: seanhalle@yahoo.com Me@19: */ Me@19: Me@19: Me@19: #include Me@19: #include Me@19: #include Me@19: #include Me@19: Me@19: #include "PrivateQueue.h" Me@19: Me@19: Me@19: Me@19: //=========================================================================== Me@19: Me@19: /*This kind of queue is private to a single core at a time -- has no Me@19: * synchronizations Me@19: */ Me@19: Me@19: PrivQueueStruc* makePrivQ() Me@19: { Me@19: PrivQueueStruc* retQ; seanhalle@32: //This malloc is not safe to use in wrapper lib nor app code! seanhalle@43: retQ = (PrivQueueStruc *) PR_int__malloc( sizeof( PrivQueueStruc ) ); Me@19: seanhalle@32: //This malloc is not safe to use in wrapper lib nor app code! seanhalle@43: retQ->startOfData = PR_int__malloc( 1024 * sizeof(void *) ); Me@19: memset( retQ->startOfData, 0, 1024 * sizeof(void *) ); Me@19: retQ->extractPos = &(retQ->startOfData[0]); //side by side == empty Me@19: retQ->insertPos = &(retQ->startOfData[1]); // so start pos's have to be Me@19: retQ->endOfData = &(retQ->startOfData[1023]); Me@19: Me@19: return retQ; Me@19: } Me@19: Me@19: seanhalle@44: /*A bit tricky, 'cause have to copy in two halves, and be careful about case seanhalle@44: * when insert is at top and extract at bottom.. seanhalle@44: */ Me@19: void Me@19: enlargePrivQ( PrivQueueStruc *Q ) seanhalle@35: { int32 oldSize, newSize, topPartSize, bottPartSize; seanhalle@32: int8 *insertPos, *extractPos; seanhalle@32: int8 *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData; seanhalle@35: int32 insertOffsetBytes, extractOffsetBytes; seanhalle@35: int8 *copyStartAddr; Me@19: seanhalle@32: oldStartOfData = (int8 *)Q->startOfData; seanhalle@32: oldEndOfData = (int8 *)Q->endOfData; seanhalle@32: insertPos = (int8 *)Q->insertPos; seanhalle@32: extractPos = (int8 *)Q->extractPos; Me@19: seanhalle@32: //TODO: verify these get number of bytes correct seanhalle@35: insertOffsetBytes = (int32)(insertPos - oldStartOfData); seanhalle@35: extractOffsetBytes = (int32)(extractPos - oldStartOfData); seanhalle@32: seanhalle@35: oldSize = oldEndOfData - oldStartOfData + 1; //in bytes seanhalle@32: newSize = 2 * oldSize; seanhalle@32: seanhalle@32: //This malloc is not safe to use in wrapper lib nor app code! seanhalle@43: Q->startOfData = (void **)PR_int__malloc( newSize ); seanhalle@32: newStartOfData = (int8 *)Q->startOfData; seanhalle@32: newEndOfData = newStartOfData + newSize; //all calcs in Bytes seanhalle@32: Q->endOfData = (void **)newEndOfData; seanhalle@32: seanhalle@32: //TODO: test all of this, for both cases seanhalle@32: seanhalle@32: //Moving the data and pointers to the new array is seanhalle@32: //a little trickier than at first it seems.. the top part seanhalle@32: // of old queue must be moved to the top part of new queue, while seanhalle@32: // bottom part of old to bottom part of new, then the new insert seanhalle@32: // and extract positions calculated by offset from top and bottom seanhalle@32: //UNLESS the one case where old extract was at bottom and insert seanhalle@32: // was at top. seanhalle@32: //TODO: check that this is correct! seanhalle@35: if( extractPos == oldStartOfData && insertPos == oldEndOfData ) seanhalle@32: { seanhalle@32: memcpy( newStartOfData, oldStartOfData, oldSize ); //oldSize is bytes seanhalle@32: Q->extractPos = Q->startOfData; //start of valid data seanhalle@32: Q->insertPos = Q->startOfData + oldSize - 1; //end of valid data seanhalle@32: } seanhalle@32: else //have to copy two parts separately, then calc positions seanhalle@32: { //TODO: check end-addr, sizes, and new positions carefully seanhalle@35: seanhalle@32: //copy top part, starting at extract up until end of data, seanhalle@35: // into top of new array seanhalle@32: topPartSize = oldEndOfData - extractPos + 1; //+1 includes extractPos seanhalle@35: copyStartAddr = newEndOfData - topPartSize + 1;//+1 cancels other seanhalle@32: memcpy( copyStartAddr, Q->extractPos, topPartSize ); seanhalle@35: Q->extractPos = (void **)copyStartAddr; //extract just-copied data seanhalle@35: seanhalle@32: //copy bottom part, from old start up to old insert, seanhalle@35: // into bottom of new array seanhalle@32: bottPartSize = oldSize - topPartSize - 1; //-1 for empty insertPos seanhalle@32: memcpy( newStartOfData, oldStartOfData, bottPartSize ); seanhalle@32: Q->insertPos = (void **)(newStartOfData + bottPartSize); seanhalle@32: } seanhalle@32: //This free is not safe to use in wrapper lib nor app code! seanhalle@43: PR_int__free(oldStartOfData); Me@19: } Me@19: Me@19: seanhalle@37: /*Returns TRUE when queue is empty seanhalle@37: */ seanhalle@37: bool32 isEmptyPrivQ( PrivQueueStruc* Q ) seanhalle@37: { void *out = 0; seanhalle@37: void **startOfData = Q->startOfData; seanhalle@37: void **endOfData = Q->endOfData; seanhalle@37: seanhalle@37: void **insertPos = Q->insertPos; seanhalle@37: void **extractPos = Q->extractPos; seanhalle@37: seanhalle@37: //if not empty -- (extract is just below insert when empty) seanhalle@37: if( insertPos - extractPos != 1 && seanhalle@37: !(extractPos == endOfData && insertPos == startOfData)) seanhalle@37: { seanhalle@37: return FALSE; seanhalle@37: } seanhalle@37: //Q is empty seanhalle@37: return TRUE; seanhalle@37: } seanhalle@37: seanhalle@37: /*Returns NULL when queue is empty seanhalle@37: */ seanhalle@37: void* peekPrivQ( PrivQueueStruc* Q ) seanhalle@37: { void *out = 0; seanhalle@37: void **startOfData = Q->startOfData; seanhalle@37: void **endOfData = Q->endOfData; seanhalle@37: seanhalle@37: void **insertPos = Q->insertPos; seanhalle@37: void **extractPos = Q->extractPos; seanhalle@37: seanhalle@37: //if not empty -- (extract is just below insert when empty) seanhalle@37: if( insertPos - extractPos != 1 && seanhalle@37: !(extractPos == endOfData && insertPos == startOfData)) seanhalle@37: { seanhalle@37: out = *(Q->extractPos); seanhalle@37: return out; seanhalle@37: } seanhalle@37: //Q is empty seanhalle@37: return NULL; seanhalle@37: } seanhalle@37: seanhalle@37: Me@19: /*Returns NULL when queue is empty Me@19: */ Me@19: void* readPrivQ( PrivQueueStruc* Q ) Me@19: { void *out = 0; Me@19: void **startOfData = Q->startOfData; Me@19: void **endOfData = Q->endOfData; Me@19: Me@19: void **insertPos = Q->insertPos; Me@19: void **extractPos = Q->extractPos; Me@19: Me@19: //if not empty -- (extract is just below insert when empty) Me@19: if( insertPos - extractPos != 1 && Me@19: !(extractPos == endOfData && insertPos == startOfData)) Me@19: { //move before read Me@19: if( extractPos == endOfData ) //write new pos exactly once, correctly Me@19: { Q->extractPos = startOfData; //can't overrun then fix it 'cause Me@19: } // other thread might read bad pos Me@19: else Me@19: { Q->extractPos++; Me@19: } Me@19: out = *(Q->extractPos); Me@19: return out; Me@19: } Me@19: //Q is empty Me@19: return NULL; Me@19: } Me@19: Me@19: Me@19: /*Expands the queue size automatically when it's full Me@19: */ Me@19: void Me@19: writePrivQ( void * in, PrivQueueStruc* Q ) Me@19: { Me@19: void **startOfData = Q->startOfData; Me@19: void **endOfData = Q->endOfData; Me@19: Me@19: void **insertPos = Q->insertPos; Me@19: void **extractPos = Q->extractPos; Me@19: Me@19: tryAgain: Me@19: //Full? (insert is just below extract when full) Me@19: if( extractPos - insertPos != 1 && Me@19: !(insertPos == endOfData && extractPos == startOfData)) Me@19: { *(Q->insertPos) = in; //insert before move Me@19: if( insertPos == endOfData ) //write new pos exactly once, correctly Me@19: { Q->insertPos = startOfData; Me@19: } Me@19: else Me@19: { Q->insertPos++; Me@19: } Me@19: return; Me@19: } Me@19: //Q is full Me@19: enlargePrivQ( Q ); Me@19: goto tryAgain; Me@19: } Me@19: Me@19: Me@19: /*Returns false when the queue was full. Me@19: * have option of calling make_larger_PrivQ to make more room, then try again Me@19: */ seanhalle@35: bool32 seanhalle@35: writeIfSpacePrivQ( void * in, PrivQueueStruc* Q ) Me@19: { Me@19: void **startOfData = Q->startOfData; Me@19: void **endOfData = Q->endOfData; Me@19: Me@19: void **insertPos = Q->insertPos; Me@19: void **extractPos = Q->extractPos; Me@19: Me@19: if( extractPos - insertPos != 1 && Me@19: !(insertPos == endOfData && extractPos == startOfData)) Me@19: { *(Q->insertPos) = in; //insert before move Me@19: if( insertPos == endOfData ) //write new pos exactly once, correctly Me@19: { Q->insertPos = startOfData; Me@19: } Me@19: else Me@19: { Q->insertPos++; Me@19: } Me@19: return TRUE; Me@19: } Me@19: //Q is full Me@19: return FALSE; Me@19: } seanhalle@27: seanhalle@32: int32 seanhalle@32: numInPrivQ( PrivQueueStruc *Q ) seanhalle@32: { int32 size, numIn; seanhalle@32: seanhalle@32: if( Q->insertPos < Q->extractPos ) seanhalle@32: { //insert has wrapped around so numIn is: seanhalle@32: // insertPos + size - extractPos -- Consider, is empty when seanhalle@32: // extractPos = endOfData and insert = start -- correctly get zero seanhalle@33: size = Q->endOfData - Q->startOfData + 1; //sz of 10 is 0..9 seanhalle@33: numIn = Q->insertPos - Q->extractPos + size - 1; //-1 bec insrt empty seanhalle@32: } seanhalle@32: else seanhalle@32: { seanhalle@33: numIn = Q->insertPos - Q->extractPos -1;//-1 bec insertPos empty seanhalle@32: } seanhalle@32: return numIn; seanhalle@32: } seanhalle@32: seanhalle@32: seanhalle@32: /*Treats queue as a stack -- no matter contents, if read done right after seanhalle@32: * a push, then the pushed item is what comes out. seanhalle@32: * Expands the queue size automatically when it's full. seanhalle@32: */ seanhalle@32: void seanhalle@32: pushPrivQ( void * in, PrivQueueStruc* Q ) seanhalle@32: { seanhalle@32: while(1){ seanhalle@32: void **startOfData = Q->startOfData; seanhalle@32: void **endOfData = Q->endOfData; seanhalle@32: seanhalle@32: void **insertPos = Q->insertPos; seanhalle@32: void **extractPos = Q->extractPos; seanhalle@32: seanhalle@32: //Full? (insert is just below extract when full) seanhalle@32: if( extractPos - insertPos != 1 && seanhalle@32: !(insertPos == endOfData && extractPos == startOfData)) seanhalle@32: { //insert -- but go backwards, inserting at read position then seanhalle@32: // move read pos backwards seanhalle@32: *(Q->extractPos) = in; seanhalle@32: if( extractPos == startOfData ) //write new pos exactly once, correctly seanhalle@32: { Q->extractPos = endOfData; //can't overrun then fix it 'cause seanhalle@32: } // other thread might read bad pos seanhalle@32: else seanhalle@32: { Q->extractPos--; seanhalle@32: } seanhalle@32: return; seanhalle@32: } seanhalle@32: //Q is full seanhalle@32: enlargePrivQ( Q ); seanhalle@32: } seanhalle@32: } seanhalle@32: seanhalle@32: seanhalle@44: /*NOTE: This free is not safe to use in wrapper lib nor app code seanhalle@44: */ seanhalle@44: void seanhalle@44: freePrivQ( PrivQueueStruc *Q ) seanhalle@44: { seanhalle@44: //This free is not safe to use in wrapper lib nor app code! seanhalle@44: PR_int__free( Q->startOfData ); seanhalle@44: PR_int__free( Q ); seanhalle@44: }