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: 
Me@19: #include <stdio.h>
Me@19: #include <string.h>
Me@19: #include <errno.h>
Me@19: #include <stdlib.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;
Me@19:    retQ = (PrivQueueStruc *) malloc( sizeof( PrivQueueStruc ) );
Me@19: 
Me@19:    retQ->startOfData = 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: 
Me@19: void
Me@19: enlargePrivQ( PrivQueueStruc *Q )
Me@19:  { int    oldSize, newSize;
Me@19:    void **oldStartOfData;
Me@19: 
Me@19:    oldSize           = Q->endOfData - Q->startOfData;
Me@19:    newSize           = 2 * oldSize;
Me@19:    oldStartOfData = Q->startOfData;
Me@19:    Q->startOfData = malloc( newSize * sizeof(void *) );
Me@19:    memcpy(Q->startOfData, oldStartOfData, oldSize * sizeof(void *));
Me@19:    free(oldStartOfData);
Me@19:    
Me@19:    Q->extractPos  = &(Q->startOfData[0]); //side by side == empty
Me@19:    Q->insertPos   = &(Q->startOfData[1]); // so start pos's have to be
Me@19:    Q->endOfData   = &(Q->startOfData[newSize - 1]);
Me@19:  }
Me@19: 
Me@19: 
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:  */
Me@19: int 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:  }