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

uHeapQ.h

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Ashif S. Harji 2000
// 
// uHeapQ.h -- 
// 
// Author           : Ashif S. Harji
// Created On       : Fri Jan 14 17:59:34 2000
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Aug  6 15:05:02 2004
// Update Count     : 24
//
// 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.
// 


#ifndef __U_HEAPQ_H__
#define __U_HEAPQ_H__

#pragma __U_NOT_USER_CODE__


//#include <uDebug.h>

#include <uC++.h>
#include <uHeap.h>

#include <limits.h>


#define __U_MAX_NUMBER_PRIORITIES__ 32


class uPriorityQ : public uBasePrioritySeq {
    struct uHeapBaseSeq {
      // int priority;
      int index;
      uBaseTaskSeq queue;
    };

    uHeapBaseSeq uObjects[__U_MAX_NUMBER_PRIORITIES__ ]; 
    uHeap<int, uHeapBaseSeq *, __U_MAX_NUMBER_PRIORITIES__> heap;
    //int num_priorities;
    // int uPriorityValue;
    // int uQueueNum;
    // uBaseTask *uInheritTask;
    
    int uCurrPriority;
    int uCurrQueueNum;

    static int compare(int k1, int k2);
    static void exchange( uHeapable<int, uHeapBaseSeq *> &x, uHeapable<int, uHeapBaseSeq *> &y );
  public:
    uPriorityQ ();
    virtual bool uEmpty() const;
    virtual uBaseTaskDL *uHead();
    virtual int uAdd( uBaseTaskDL *node, uBaseTask *uOwner );
    virtual uBaseTaskDL *uDrop();
    virtual void uRemove( uBaseTaskDL *node ); 
    virtual void uOnAcquire(uBaseTask &uOwner );
    virtual void uOnRelease(uBaseTask &uOwner );

    int uAfterEntry( uBaseTask *uOwner );
}; // PriorityQ


template<class List, class Node> class uPriorityScheduleQ : public uBaseSchedule<Node> {
    struct uHeapScheduleSeq {
      int priority;
      int index;
      List queue;
    };

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

    static void exchange( uHeapable<int, uHeapScheduleSeq *> &x, uHeapable<int, uHeapScheduleSeq *> &y ) {
      uHeapable<int, uHeapScheduleSeq *> 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
    } // exchange
  protected:
    uHeapScheduleSeq uObjects[__U_MAX_NUMBER_PRIORITIES__ ];
    uHeap<int, uHeapScheduleSeq *, __U_MAX_NUMBER_PRIORITIES__> heap;
    unsigned int verCount;
    int num_priorities;
  public:
    uPriorityScheduleQ() : heap( &compare, &exchange ) {
      verCount = 0;
      num_priorities = 1;                       // first is always non-real-time tasks
      uObjects[0].priority = INT_MAX;                 // use a large number, syn which uAddInitialize

    } // uPriorityScheduleQ::uPriorityScheduleQ

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

    virtual Node *uHead() {
      if ( !uEmpty() ) {
          uHeapable<int, uHeapScheduleSeq *> rqueue;
          heap.getRoot(rqueue);
          return rqueue.data->queue.uHead();
      } else {
          return NULL;
      } // if
    } // uPriorityScheduleQ::uHead

    virtual void uAdd( Node *node ) {
      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( uObjects[queueNum].priority, &(uObjects[queueNum]) );
      } else {
          uObjects[queueNum].queue.uAdd(node);
      } // if
    } // uPriorityScheduleQ::uAdd

    virtual Node *uDrop() {
      if ( !uEmpty() ) {
          uHeapable<int, uHeapScheduleSeq *> rqueue;
          heap.getRoot(rqueue);
          Node *pnode = rqueue.data->queue.uDrop();
          
          if ( rqueue.data->queue.uEmpty() ){
            heap.deleteRoot();
          } // if
          return pnode;
      } else {
          return NULL;
      } // if
    } // uPriorityScheduleQ::uDrop

    virtual bool uCheckPriority( Node &, Node & ) {
      return false;
    } // uPriorityScheduleQ::uCheckPriority

    virtual void uResetPriority( Node &, Node & ) {
    } // uPriorityScheduleQ::uResetPriority

    virtual void uAddInitialize( uBaseTaskSeq & ) {
    } // uPriorityScheduleQ::uAddInitialize

    virtual void uRemoveInitialize( uBaseTaskSeq & ) {
    } // uPriorityScheduleQ::uRemoveInitialize

    virtual void uRescheduleTask( uBaseTaskDL *, uBaseTaskSeq & ) {
    } // uPriorityScheduleQ::uRescheduleTask
}; // uPriorityScheduleQ


template<class List, class Node> class uPriorityScheduleQSeq : public uPriorityScheduleQ<List, Node> {
  protected:
    using uPriorityScheduleQ<List, Node>::uObjects;
    using uPriorityScheduleQ<List, Node>::uSetActivePriority;
    using uPriorityScheduleQ<List, Node>::uSetActiveQueue;
    using uPriorityScheduleQ<List, Node>::heap;
  public:
    virtual bool uCheckPriority( Node &owner, Node &calling ) {
      return uGetActivePriorityValue( owner.uGet() ) > uGetActivePriorityValue( calling.uGet() );
    } // uPriorityScheduleQSeq::uCheckPriority

    virtual void uResetPriority( Node &owner, Node &calling ) {
      int queueNum;
      uBaseTask &uOwner = owner.uGet();
      uBaseTask &uCalling = calling.uGet();
      // if same, update owner based on uPIQ
      if ( &uOwner == &uCalling ) {
          queueNum = (static_cast<uPIHeap *>(uOwner.uPIQ))->uHead(); // TODO: dynamic needed???
          // if queue is empty use base priority
          if ( queueNum == -1 ) {
            queueNum = uOwner.uGetBaseQueue();
          } // if
      } else {  // otherwise, update to atmost calling task's priority
          if ( uCalling.uGetActivePriorityValue() > uOwner.uGetActivePriorityValue() ) return;
          queueNum = uCalling.uGetActiveQueueValue();
      } // if
            
      if ( owner.uListed() ) {
          uRemove( &owner );
          uSetActivePriority( uOwner, uObjects[queueNum].priority );
          uSetActiveQueue( uOwner, queueNum );
          uAdd( &owner );
      } else {
          uSetActivePriority( uOwner, uObjects[queueNum].priority );
          uSetActiveQueue( uOwner, queueNum );
      } // if
    } // uPriorityScheduleQSeq::uResetPriority

    virtual void uRemove( Node *node ) {
      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] );
      }
    } // uPriorityScheduleQSeq::uRemove
}; // uPriorityScheduleQSeq


#endif // __U_HEAPQ_H__


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

Generated by  Doxygen 1.6.0   Back to index