Logo Search packages:      
Sourcecode: u++ version File versions

uHeapQ.cc

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Ashif S. Harji 2000
// 
// uHeapQ.cc -- 
// 
// Author           : Ashif S. Harji
// Created On       : Fri Feb  4 10:57:13 2000
// Last Modified By : Peter A. Buhr
// Last Modified On : Thu Aug 12 08:57:06 2004
// Update Count     : 19
//
// This  library is free  software; you  can redistribute  it and/or  modify it
// under the terms of the GNU Lesser General Public License as published by the
// Free Software  Foundation; either  version 2.1 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 Lesser General Public License
// for more details.
// 
// You should  have received a  copy of the  GNU Lesser General  Public License
// along  with this library.
// 


#define __U_KERNEL__
#include <uC++.h>
#include <uHeapQ.h>
//#include <uDebug.h>

#define uLockAcquired  0
#define uLockReleased  1

// compare for Heapify property, ie parent(i) <= i
int uPriorityQ::compare( int k1, int k2 ) {
    if ( k1 < k2 ) {
      return 1;
    } else if ( k1 == k2 ){
      return 0;
    } else {
      return -1;
    } // if
} // compare


void uPriorityQ::exchange( uHeapable<int, uHeapBaseSeq *> &x, uHeapable<int, uHeapBaseSeq *> &y ) {
    uHeapable<int, uHeapBaseSeq *> temp = x;
    int t_index = x.data->index;
    x = y;   
    y = temp;
    y.data->index = x.data->index;              // swapping locations requires the index pointers to be updated
    x.data->index = t_index;
#ifdef DEBUG_SHOW_COUNT
    NumExchg += 1;
#endif
} // uPriorityQ::exchange


uPriorityQ::uPriorityQ() : heap( &compare, &exchange ) {
    //for ( int i = 0; i < __U_MAX_NUMBER_PRIORITIES__ ; i += 1 ) {
    //    heap.A[i + 1].data = &(uObjects[i]);
    //} // for
    //num_priorities = 1; // first is always non-real-time tasks
    // uObjects[0].priority = 2147483647;  // use a large number, syn which uAddInitialize
    // uPriorityValue = -1;
    // uInheritTask = NULL;
    // uQueueNum = -1;
    uExecuteHooks = true;
    uCurrPriority = -1;
    uCurrQueueNum = -1;
} // uPriorityQ::uPriorityQ


bool uPriorityQ::uEmpty() const {
    return heap.size() == 0;
} // uPriorityQ::uEmpty


uBaseTaskDL *uPriorityQ::uHead() {              
    if ( ! uEmpty() ) {
      uHeapable<int,uHeapBaseSeq *> rqueue;
      heap.getRoot(rqueue);
      return rqueue.data->queue.uHead();
    } else {
      return NULL;
    } // if
} // uPriorityQ::uHead


int uPriorityQ::uAdd( uBaseTaskDL *node, uBaseTask *uOwner ) {    
    // Dynamic check to verify that the task being added to entry queue is
    // compliant with PIHeap type.
    uPIHeap *PIHptr = dynamic_cast<uPIHeap *>(node->uGet().uPIQ);
    if ( PIHptr == NULL ) {
      uAbort("(uPriorityQ &)0x%p.uAdd: Task 0x%p has incorrect uPIQ type for mutex object", this, &node->uGet());
    } //if

    // check if your priority needs to be updated
    if ( PIHptr->uGetHighestPriority() < uGetActivePriorityValue( node->uGet() )  ) {
      uThisCluster().uTaskSetPriority( node->uGet(), node->uGet() );
    } // if

    // As uCurrentSerial is updated, the calling task's priority can no longer
    // change because the tasks uPIQ is fixed as the entry lock is acquired.
    // So subsequent updates will only reaffirm the task's current priority.

    int priority = uGetActivePriorityValue( node->uGet() );
    int queueNum = uGetActiveQueueValue( node->uGet() ); // use the node for you active priority

    // if empty then must add to heap, otherwise just insert node
    if ( uObjects[queueNum].queue.uEmpty() ) {
      uObjects[queueNum].queue.uAdd(node);
      // the index must be set before inserting because the index can change as part of the insert
      uObjects[queueNum].index = heap.size() + 1;
      heap.insert( priority, &(uObjects[queueNum]) );
    } else {
      uObjects[queueNum].queue.uAdd(node);
    } // if
    
    // only perform inheritance for entry list
    if ( uIsEntryBlocked( node->uGet() ) && uCheckHookConditions( *uOwner, node->uGet() ) ) {   // TEMP: entry queue??
      return( uAfterEntry( uOwner ) );          // perform any priority inheritance
    } else {
      return uLockAcquired;
    } // if
} // uPriorityQ::uAdd


uBaseTaskDL *uPriorityQ::uDrop() {                    
    if ( ! uEmpty() ) {
      uHeapable<int,uHeapBaseSeq *> rqueue;
      heap.getRoot(rqueue);
      uBaseTaskDL *pnode = rqueue.data->queue.uDrop();

      if ( rqueue.data->queue.uEmpty() ){
          heap.deleteRoot();
      } // if
      return pnode;
    } else {
      return NULL;
    } // if
} // uPriorityQ::uDrop


void uPriorityQ::uRemove( uBaseTaskDL *node ) {       
    // use stored queue value because this task has entry lock, so its uPIQ may
    // be updated, but not its position on the entry queue.
    int queueNum = uGetActiveQueueValue( node->uGet() );// use the node for you active priority
    
    // do remove
    uObjects[queueNum].queue.uRemove(node);

    // if empty then must remove from heap
    if ( uObjects[queueNum].queue.uEmpty() ) {
      heap.deletenode( heap.A[uObjects[queueNum].index] );
    } // if
} // uPriorityQ::uRemove


int uPriorityQ::uAfterEntry(uBaseTask *uOwner ) {     // use pointer to owner as it could be Null
    // static_cast to PIHeap are valid here as uAdd and uOnAcquire already
    // verify that the associated tasks use type uPIHeap.

    // assume entry lock acquired
    int uRelPrevLock = uLockAcquired;

    // if entry queue empty (called by owner) or no owner, then no inheritance
    if ( uEmpty() || uOwner == NULL /* || uCurrPriority == -1 */ ) {
      return uRelPrevLock;
    } // if

    uBaseTask &uCalling = uHead()->uGet();            // can't be NULL as not empty 

    // does node need to be updated?
    if ( uCalling.uGetActivePriorityValue() < uCurrPriority ) { 
        // only task with entry lock can be modifying this mutex's node
      // remove node
      (static_cast<uPIHeap *>(uOwner->uPIQ))->uRemove( uCurrPriority, uCurrQueueNum );
      
      // reset priority value for monitor
      uCurrPriority = uCalling.uGetActivePriorityValue();
      uCurrQueueNum = uCalling.uGetActiveQueueValue();

        // update mutex owner's uPIQ for new priority
      (static_cast<uPIHeap *>(uOwner->uPIQ))->uAdd( uCurrPriority, uCurrQueueNum ) ;  
    
      // does inheritance occur ?
      if ( uCurrPriority < uOwner->uGetActivePriorityValue() ) {
          
          uRepositionEntry rep(*uOwner, uCalling);
            // if task is blocked on entry list, adjust and perform transitivity
          if ( uIsEntryBlocked( *uOwner ) ) {
            uRelPrevLock = rep.uReposition(true);
          } else {
                // call cluster routine to adjust ready queue and active
                // priority Note: can only raise priority to at most uCalling,
                // otherwise updating uOwner's priority can conflit with the
                // uOwner blocking on an entry queue at a particular priority
                // level.  Furthermore, uCalling's priority is fixed while the
                // entry lock of where it is blocked (s->lock) is acquired, but
                // uThisTask()'s priority can change as entry lock's are
                // released along inheritance chain.
            uThisCluster().uTaskSetPriority( *uOwner, uCalling );
          } // if
      } // if
    } // if

    return uRelPrevLock;
} // uPriorityQ::uAfterEntry


void uPriorityQ::uOnAcquire(uBaseTask &uOwner ) {
    // Dynamic check to verify that the task acquiring the serial is compliant
    // with PIHeap type.
    uPIHeap *PIHptr = dynamic_cast<uPIHeap *>(uOwner.uPIQ);
    if ( PIHptr == NULL ) {
      uAbort("(uPriorityQ &)0x%p.uOnAcquire: Task 0x%p has incorrect uPIQ type for mutex object", this, &uOwner);
    } //if

    // check if mutex owner's priority needs to be updated
    if ( PIHptr->uGetHighestPriority() < uGetActivePriorityValue( uOwner ) ) {
      uThisCluster().uTaskSetPriority( uOwner, uOwner );
    } // if

    // remember current priority value, update task's uPIQ
    uCurrPriority = uOwner.uGetBasePriority();
    uCurrQueueNum = uOwner.uGetBaseQueue();
    PIHptr->uAdd( uCurrPriority, uCurrQueueNum );

    // perform priority inheritance
    uAfterEntry( &uOwner );
} // uPriorityQ::uOnAcquire


void uPriorityQ::uOnRelease(uBaseTask &uOldOwner ) {
    // static_cast to PIHeap are valid here as uAdd and uOnAcquire already
    // verify that the associated tasks use type uPIHeap.

    // update task's uPIQ, reset stored values
    (static_cast<uPIHeap *>(uOldOwner.uPIQ))->uRemove( uCurrPriority, uCurrQueueNum ); 
    uCurrPriority = -1;
    uCurrQueueNum = -1;

    // reset active priority if necessary
    // only case where priority can decrease
    if ( (static_cast<uPIHeap *>(uOldOwner.uPIQ))->uEmpty() ||
       (static_cast<uPIHeap *>(uOldOwner.uPIQ))->uGetHighestPriority() > uGetActivePriorityValue( uOldOwner ) ) {
      uThisCluster().uTaskSetPriority( uOldOwner, uOldOwner );
    } // if
} // uPriorityQ::uOnRelease

// Local Variables: //
// compile-command: "gmake install" //
// End: //

Generated by  Doxygen 1.6.0   Back to index