Me@19: /*
Me@19:  *  Copyright 2009 OpenSourceStewardshipFoundation.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: 
nengel@41: #include <string.h>
nengel@41: #include <stdlib.h>
Me@19: #include <stdio.h>
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@32:    retQ = (PrivQueueStruc *) VMS_int__malloc( sizeof( PrivQueueStruc ) );
Me@19: 
seanhalle@32:       //This malloc is not safe to use in wrapper lib nor app code!
seanhalle@37:    retQ->startOfData = VMS_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: 
nengel@41:    #ifdef DEBUG_PRIVATE_Q
nengel@41:    retQ->numReads = 0;
nengel@41:    retQ->numWrites =0;
nengel@41:    #endif
nengel@41:    
Me@19:    return retQ;
Me@19:  }
Me@19: 
Me@19: 
Me@19: void
Me@19: enlargePrivQ( PrivQueueStruc *Q )
nengel@41:  { size_t  oldSize, newSize, topPartSize, bottPartSize;
nengel@41:    char *insertPos, *extractPos;
nengel@41:    char *oldStartOfData, *oldEndOfData, *newStartOfData, *newEndOfData;
nengel@41:    size_t  insertOffsetBytes, extractOffsetBytes;
nengel@41:    char*  copyStartAddr;
Me@19: 
nengel@41:    #ifdef DEBUG_PRIVATE_Q
nengel@41:    printf("Enlarging queue Q = %p\nnumReads = %d; numWrites = %d\n",Q,Q->numReads,Q->numWrites);
nengel@41:    #endif
nengel@41:    
nengel@41:    oldStartOfData = (char*)Q->startOfData;
nengel@41:    oldEndOfData   = (char*)(Q->endOfData + 1);
nengel@41:    insertPos      = (char*)Q->insertPos;
nengel@41:    extractPos     = (char*)Q->extractPos;
Me@19:    
seanhalle@32:       //TODO: verify these get number of bytes correct
nengel@41:    insertOffsetBytes  = (insertPos  - oldStartOfData);
nengel@41:    extractOffsetBytes = (extractPos - oldStartOfData);
seanhalle@32:    
nengel@41:    oldSize            = oldEndOfData - oldStartOfData; //in bytes
seanhalle@32:    newSize            = 2 * oldSize;
seanhalle@32:    
nengel@41:    #ifdef DEBUG_PRIVATE_Q
nengel@41:    printf("Old size = %d, new size = %d\n",(int)oldSize,(int)newSize);
nengel@41:    #endif
nengel@41:    
seanhalle@32:       //This malloc is not safe to use in wrapper lib nor app code!
nengel@41:    newStartOfData     = (char *) VMS_int__malloc( newSize );
nengel@41:    if(newStartOfData == NULL){
nengel@41:        perror("malloc"); exit(1);
nengel@41:    }
seanhalle@32:    newEndOfData       = newStartOfData + newSize; //all calcs in Bytes
nengel@41: 
nengel@41:       //TODO: test all of this, for both cases
nengel@41:    Q->startOfData     = newStartOfData;
nengel@41:    Q->endOfData       = ((void **)newEndOfData) - 1;
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!
nengel@41:    if( extractPos == oldStartOfData )
seanhalle@32:     {
seanhalle@32:       memcpy( newStartOfData, oldStartOfData, oldSize ); //oldSize is bytes
seanhalle@32:       Q->extractPos  = Q->startOfData; //start of valid data
nengel@41:       Q->insertPos   = (void**)(newStartOfData + insertOffsetBytes); //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
nengel@41:        
seanhalle@32:          //copy top part, starting at extract up until end of data,
seanhalle@35:          // into top of new array
nengel@41:       topPartSize = oldEndOfData - extractPos;
nengel@41:       copyStartAddr = newEndOfData - topPartSize;
nengel@41:       memcpy( copyStartAddr, 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		 
nengel@41:       bottPartSize = insertPos - oldStartOfData; //-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@32:    VMS_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)
nengel@42:        if (insertPos - extractPos != 1 &&
nengel@42:             !(extractPos == endOfData && insertPos == startOfData)) { //move before read
nengel@42:         if (extractPos == endOfData) //write new pos exactly once, correctly
nengel@42:         {
nengel@42:             out = *(startOfData); //can't overrun then fix it 'cause
nengel@42:         }// other thread might read bad pos
nengel@42:         else {
nengel@42:             out = *(Q->extractPos + 1);
nengel@42:         }
nengel@42:         
nengel@42:         return out;
seanhalle@37:     }
seanhalle@37:       //Q is empty
seanhalle@37:    return NULL;
seanhalle@37:  }
seanhalle@37: 
Me@19: /*Returns NULL when queue is empty
Me@19:  */
nengel@41: void* readPrivQ(PrivQueueStruc* Q) {
nengel@41:     
nengel@41:     void *out = 0;
nengel@41:     void **startOfData = Q->startOfData;
nengel@41:     void **endOfData = Q->endOfData;
Me@19: 
nengel@41:     void **insertPos = Q->insertPos;
nengel@41:     void **extractPos = Q->extractPos;
Me@19: 
nengel@41:     //if not empty -- (extract is just below insert when empty)
nengel@41:     if (insertPos - extractPos != 1 &&
nengel@41:             !(extractPos == endOfData && insertPos == startOfData)) { //move before read
nengel@41:         if (extractPos == endOfData) //write new pos exactly once, correctly
nengel@41:         {
nengel@41:             Q->extractPos = startOfData; //can't overrun then fix it 'cause
nengel@41:         }// other thread might read bad pos
nengel@41:         else {
nengel@41:             Q->extractPos++;
nengel@41:         }
nengel@41:         out = *(Q->extractPos);
nengel@42:         //*(Q->extractPos) = NULL;
nengel@42: #ifdef DEBUG_PRIVATE_Q
nengel@42:         Q->numReads++;
nengel@42: #endif
nengel@41:         return out;
Me@19:     }
nengel@41:     //Q is empty
nengel@41:     return NULL;
nengel@41: }
Me@19: /*Expands the queue size automatically when it's full
Me@19:  */
Me@19: void
nengel@41: writePrivQ(void * in, PrivQueueStruc* Q) {
Me@19: 
nengel@41:     #ifdef DEBUG_PRIVATE_Q
nengel@41:     Q->numWrites++;
nengel@41:     #endif
nengel@41:     
nengel@41:     //tryAgain:
nengel@41:     //Full? (insert is just below extract when full)
nengel@41:     if ((Q->extractPos - Q->insertPos) == 1 ||
nengel@41:             (Q->insertPos == Q->endOfData && Q->extractPos == Q->startOfData)) {
nengel@41:         enlargePrivQ(Q);
Me@19:     }
nengel@41: 
nengel@41:     *(Q->insertPos) = in; //insert before move
nengel@41:     if (Q->insertPos == Q->endOfData) //write new pos exactly once, correctly
nengel@41:     {
nengel@41:         Q->insertPos = Q->startOfData;
nengel@41:     } else {
nengel@41:         Q->insertPos++;
nengel@41:     }
nengel@41:     return;
nengel@41: 
nengel@41:     //Q is full
nengel@41: 
nengel@41:     //goto tryAgain;
nengel@41: }
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:        }
nengel@41:       #ifdef DEBUG_PRIVATE_Q
nengel@41:       Q->numWrites++;
nengel@41:       #endif
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:  {
nengel@41:     #ifdef DEBUG_PRIVATE_Q
nengel@41:     Q->numWrites++;
nengel@41:     #endif
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@32:  void
seanhalle@32:  freePrivQ( PrivQueueStruc *Q )
seanhalle@32:   {
seanhalle@32:       //This free is not safe to use in wrapper lib nor app code!
seanhalle@32:     VMS_int__free( Q->startOfData );
seanhalle@32: 	VMS_int__free( Q );
seanhalle@32:   }