pqueues.cpp

eC++编译器源码

#pragma PQueues
#include <SYSTEM.h>
#include <PQueues.h>
#include <PLinks.h>
#include <Errors.h>
#include <Limits.h>
  /* CAK07-89 FindThis check of q.tail.next always succeeded; thus, items were
              never found. *)
  (* RPC11-89 FindThis; bad fix; it still never found anything */

/************************* IMPLEMENTATION NOTE ***************************)
(*                                                                       *)
(* Each variable, q, of type Queue has the equivalent of two permanant   *)
(* RECORD entries -- q.head and q.tail.  This simplifies the coding      *)
(* considerably since we never need to check if we are inserting or      *)
(* deleting at the real head or tail of the queue since we always        *)
(* perform all our operations somewhere INBETWEEN the two permanent      *)
(* entries.  The permanent entries are established at Queue              *)
(* initialization time and are never removed.  Our final pointer         *)
(* picture looks like this:                                              *)
(*                                                                       *)
(*                                                                       *)
(*    ------       ----       ----                 ----       ------     *)
(* /- q.head <---> rec1 <---> rec2 <---> ... <---> recN <---> q.tail -\  *)
(*    ------       ----       ----                 ----       ------     *)
(*                                                                       *)
(* where:                                                                *)
(*    q.head.previous = NIL    (previous = left)                         *)
(*    q.tail.next = NIL        (next = right)                            *)
(*    q.head.next = rec1                                                 *)
(*    rec1.previous = q.head                                             *)
(*    rec1.next = rec2                                                   *)
(*    rec2.previous = rec1                                               *)
(*    recN.next = q.tail                                                 *)
(*    q.tail.previous = recN                                             *)
(*    etc.                                                               *)
(*                                                                       *)
(* Note that an empty queue looks like this:                             *)
(*                                                                       *)
(*         ------       ------                                           *)
(*      /- q.head <---> q.tail -\                                        *)
(*         ------       ------                                           *)
(*                                                                       *)
(* where:                                                                *)
(*    q.head.previous = NIL     (always!!)                               *)
(*    q.tail.next = NIL         (always!!)                               *)
(*    q.head.next = q.tail                                               *)
(*    q.tail.previous = q.head                                           *)
(*                                                                       *)
(*************************************************************************)


(*************************************************************************)
(**************************** Add PROCEDUREs *****************************)
(*************************************************************************)

(********************************* AddAfter ******************************)
(*                                                                       *)
(* This routine adds the RECORD at the specified address to a            *)
(* Queue immediately following an old RECORD already in the Queue.       *)
(*                                                                       *)
(*************************************************************************/
void AddAfter(Queue &q,Link &next, Link &old)
{
   if (next.priority > old.priority) {
     SoftwareError("PQueues.AddAfter:Add priority wrong");
   }
  AddsAfter(old, next);
};


/*********************************** AddBefore ***************************)
(*                                                                       *)
(* This routine adds the RECORD at the specified address to a            *)
(* Queue immediately preceeding an old RECORD already in the Queue.      *)
(*                                                                       *)
(*************************************************************************/

void AddBefore(Queue &q,Link &prev, Link &old)
{
   if (prev.priority < old.priority) {
    SoftwareError("PQueues.AddBefore:Add priority wrong");
      }
  AddsBefore(old, prev);
};


/***************************** AddHead ***********************************)
(*                                                                       *)
(* This routine adds the RECORD at the specified address to the          *)
(* head of the specified Queue.                                          *)
(*                                                                       *)
(*************************************************************************/
void AddHead(Queue &q,Link &l)
{
  AddAfter(q, l, q.head);
};


/********************************* AddTail *******************************)
(*                                                                       *)
(* This routine adds the RECORD at the specified address to the tail     *)
(* of the specified Queue.                                               *)
(*                                                                       *)
(*************************************************************************/
void AddTail(Queue &q, Link &l)
{
  AddBefore(q, l, q.tail);
};


/******************************** AddPriority ****************************)
(*                                                                       *)
(* This routine adds the RECORD at the specified address to the          *)
(* specified Queue just before the first record already present with a   *)
(* lower priority.  In other words, the RECORDs in the Queue will be     *)
(* ordered from highest (numerically greatest) to lowest priority with   *)
(* RECORDs of equal priority ordered in first-in-first-out fashion.      *)
(*                                                                       *)
(*************************************************************************/
void AddPriority(Queue &q,Link &l,int prio)
{
    pLink scanPtr;
  l.priority = prio;
  scanPtr = q.tail.previous;
    while (scanPtr->priority < prio) {
        scanPtr = scanPtr->previous;
        };
    AddsAfter(*scanPtr, l);
};

/***************************** ChangePriority ****************************)
(*                                                                       *)
(* This routine changes the priority of a queue record by moving it to   *)
(* a new position, if necessary.  If the new priority is the same as the *)
(* old, the queue position is not changed.                               *)
(*                                                                       *)
(*************************************************************************/
void ChangePriority(Queue &q,Link &l,int prio)
{
    pLink scanPtr; 
    if (prio != l.priority) {
      Delete(l);
      AddPriority(q, l, prio);
     }
};
                   
/*************************************************************************)
(************************ Remove PROCEDUREs ******************************)
(*************************************************************************)

(******************************* RemoveThis ******************************)
(*                                                                       *)
(* This routine removes the RECORD at the specified address from its     *)
(* Queue.  This routine does NOT scan the Queue to ensure that           *)
(* such a RECORD really exists -- use FindThis for that purpose.         *)
(*                                                                       *)
(*************************************************************************/

void RemoveThis(Queue &q,Link &old)
{
  Delete(old);
};


/******************************* RemoveHead ******************************)
(*                                                                       *)
(* This routine removes the RECORD from the head of the specified Queue  *)
(* and returns its address.  If the Queue is empty then NIL is returned. *)
(*                                                                       *)
(*************************************************************************/

ADDRESS RemoveHead(Queue &q)
{
  pLink link;
  link = q.head.next;
   if (link == ADR(q.tail)) {
     return (NULL);
    }
    else
    {
    Delete(*link);
    return(link);
    };
};


/******************************** RemoveTail *****************************)
(*                                                                       *)
(* This routine removes the RECORD from the tail of the specified Queue  *)
(* and returns its address.  If the Queue is empty then NIL is returned. *)
(*                                                                       *)
(*************************************************************************/

ADDRESS RemoveTail(Queue &q)
{
  pLink link;
  link = q.tail.previous;
    if (link == ADR(q.head)) {   
    return (NULL);
    }
    else
    {
    Delete(*link);
    return(link);
     };
};



/*************************************************************************)
(*********************** Look PROCEDUREs *********************************)
(*************************************************************************)



(****************************** LookHead *********************************)
(*                                                                       *)
(* This routine returns the address of the RECORD at the head of the     *)
(* specified Queue WITHOUT removing the RECORD from the Queue.  If the   *)
(* Queue is empty then NIL is returned.                                  *)
(*                                                                       *)
(*************************************************************************/

ADDRESS LookHead(Queue &q)
{
   ADDRESS  a;
  a = q.head.next;
  if (a == ADR(q.tail)) {
    return NULL;
   }
   else
   {
    return a;
  }
};


/****************************** LookTail *********************************)
(*                                                                       *)
(* This routine returns the address of the RECORD at the tail of the     *)
(* specified Queue WITHOUT removing the RECORD from the Queue.  If the   *)
(* Queue is empty then NIL is returned.                                  *)
(*                                                                       *)
(*************************************************************************/

ADDRESS LookTail(Queue &q)
{
    ADDRESS a;
  a = q.tail.previous;
    if ( a == ADR(q.head)) {
       return(NULL);
  }
  else
  {
   return(a);
  };
};

/******************************** LookNext *******************************)
(*                                                                       *)
(* This routine returns the address of the next RECORD in the specified  *)
(* Queue following the old record already in the Queue.  If the old      *)
(* RECORD is the last RECORD in the Queue (and hence there is no next    *)
(* RECORD) then NIL is returned.                                         *)
(*                                                                       *)
(*************************************************************************/
pLink  LookNext(Queue &q,pLink old)
{
  ADDRESS a;
  a = old->next;
    if (a == ADR(q.tail)) {
      return(NULL);
       }
       else
     {
     return(a);
     };
};

/********************************* LookPrevious **************************)
(*                                                                       *)
(* This routine returns the address of the previous record in the        *)
(* specified Queue immediately preceeding the old record already in the  *)
(* Queue.  If the old RECORD is the first RECORD in the Queue (and       *)
(* hence there is no previous RECORD) then NIL is returned.              *)
(*                                                                       *)
(*************************************************************************/
pLink  LookPrevious(Queue &q,pLink old)
{
   pLink  a;
   a = old->previous;
    if (a == ADR(q.head)) {
    return(NULL);
    }
    else
    {
    return a;
   };
};


/*************************************************************************)
(************************* Find PROCEDUREs *******************************)
(*************************************************************************)



(********************************** FindThis *****************************)
(*                                                                       *)
(* This routine scans the specified Queue for the RECORD at the          *)
(* specified address.  If the RECORD is found then TRUE is returned;     *)
(* otherwise, FALSE is returned.                                         *)
(*                                                                       *)
(*************************************************************************/
unsigned int FindThis(Queue &q, Link &old)
{
     pLink scanPtr, temp;
      unsigned int count;

  count = 1; 
  scanPtr = ADR(q.head);
  temp = q.tail.next;  
  q.tail.next = ADR(old);
/* RPC11-89*/
    while (scanPtr->next != ADR(old)) {
      scanPtr = scanPtr->next;
      INC(count);
      };
  q.tail.next = temp;
/* not found (* CAK07-89 *) (*RPC11-89*/
    if (scanPtr == ADR(q.tail)) {
    count = 0;
    }
   return(count);
};



/*************************************************************************)
(************************* Initialize PROCEDUREs *************************)
(*************************************************************************)



(******************************* InitializeQueue *************************)
(*                                                                       *)
(* This routine initializes the specified Queue base variable to the     *)
(* empty state.  New RECORDs may then be added or removed from the       *)
(* Queue using the queues MODULE routines.                               *)
(*                                                                       *)
(*************************************************************************/

void InitializeQueue(Queue &q)
{
  InitLink(q.head, INT_MAX);
  InitLink(q.tail, INT_MIN);
  AddsAfter(q.head, q.tail);
};