home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / modula2 / library / queuem2 / queueadt.mod < prev    next >
Text File  |  1989-08-30  |  12KB  |  370 lines
  1. (* source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22
  2.    author: G.Greene, AGCS D/429 (NS/TS), 312/681-7783       created: 88.07.22
  3.  
  4.    function:
  5.     This is the implementation code for a package which provides an Abstract
  6.     Data Type for queues.
  7.  
  8.    history:
  9.     88.07.22  1.0a  initial release.
  10. *)
  11.  
  12.  
  13. IMPLEMENTATION MODULE  QueueADT;
  14.  
  15.  
  16. FROM  SYSTEM   IMPORT  (*TYPE*) ADDRESS,  BYTE,
  17.                        (*PROC*) SIZE;
  18.  
  19. FROM  Storage  IMPORT  (*PROC*) ALLOCATE,  DEALLOCATE;
  20.  
  21. FROM  Lib      IMPORT  (*PROC*) Move;
  22.  
  23.  
  24. TYPE
  25.   QueueNodePtrs = POINTER  TO QueueNodes;
  26.   Queues        = POINTER  TO QueueHeader;
  27.  
  28.   QueueNodes =
  29.     RECORD
  30.       contents:  ADDRESS;
  31.       size:      CARDINAL;
  32.       next:      QueueNodePtrs
  33.     END;
  34.  
  35.   QueueHeader =
  36.     RECORD
  37.       front:  QueueNodePtrs;
  38.       back:   QueueNodePtrs
  39.     END;
  40.  
  41.  
  42. VAR
  43.   prevBack:   QueueNodePtrs;
  44.  
  45.  
  46. (*  Create a new (empty) queue specified by the parameter.
  47.  
  48.     NB!!  This procedure MUST be invoked for a queue before any other
  49.     procedure in this module can be used on that queue.  The result of
  50.     failing to do so is likely to be disasterous.  In addition, this
  51.     procedure should not be invoked with an existing queue:  the storage
  52.     associated with that queue would be lost.  To empty an existing queue,
  53.     use EmptyTheQueue;  to deallocate ("destroy") an existing queue, use
  54.     DestroyQueue.
  55. *)
  56.  
  57.   PROCEDURE  CreateQueue (
  58.             (*out*)  VAR  queue: Queues );
  59.  
  60.     BEGIN
  61.       NEW ( queue );
  62.  
  63.       queue^ .front := NIL;
  64.       queue^ .back  := NIL;
  65.     END  CreateQueue;
  66.  
  67. (*                                                                         [2]
  68.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  69.  
  70.  
  71. (*  Empty the queue specified by the parameter of its contents.  If the
  72.     queue has been destroyed, this procedure will do nothing.
  73. *)
  74.  
  75.   PROCEDURE  EmptyTheQueue (
  76.            (*in/out*)  VAR  queue: Queues );
  77.  
  78.     VAR
  79.       NodePtr,
  80.       NextPtr: QueueNodePtrs;
  81.  
  82.     BEGIN
  83.       IF  queue # NIL  THEN
  84.         NodePtr := queue^ .front;
  85.  
  86.         WHILE  NodePtr # NIL  DO
  87.           DEALLOCATE ( NodePtr^ .contents, NodePtr^ .size );
  88.           NextPtr := NodePtr^ .next;
  89.           DISPOSE ( NodePtr );
  90.           NodePtr := NextPtr;
  91.         END;    (* WHILE *)
  92.  
  93.       END;    (* IF queue # NIL *)
  94.     END  EmptyTheQueue;
  95.  
  96.  
  97.  
  98. (*  Destroy the queue specified by the parameter, deallocating all the storage
  99.     associated with it.  If invoked for a previously destroyed queue, this
  100.     procedure will do nothing.  A queue destroyed by this procedure will be
  101.     ignored by most of the other procedures.  The specific action each will
  102.     take is indicated in its description.  One exception:  CreateQueue will
  103.     reinstate a queue which has been destroyed.
  104. *)
  105.  
  106.   PROCEDURE  DestroyQueue (
  107.           (*in/out*)  VAR  queue: Queues );
  108.  
  109.     BEGIN
  110.       IF  queue # NIL  THEN
  111.         EmptyTheQueue ( queue );
  112.  
  113.         DISPOSE ( queue );
  114.         queue := NIL;
  115.       END;
  116.     END  DestroyQueue;
  117.  
  118. (*                                                                         [3]
  119.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  120.  
  121.  
  122.  
  123. (*  Return TRUE if the queue specified by the parameter is currently empty,
  124.     or if the queue has been destroyed.  Return FALSE only if the queue
  125.     exists and has at least one entry.
  126. *)
  127.  
  128.   PROCEDURE  isEmpty (
  129.               (*in*)  queue: Queues ):  BOOLEAN;
  130.  
  131.     BEGIN
  132.       IF  queue = NIL
  133.         THEN  RETURN  TRUE;
  134.         ELSE  RETURN  queue^ .front = NIL;
  135.       END;
  136.     END  isEmpty;
  137.  
  138.  
  139.  
  140. (*  Return the number of elements in the queue specified by the parameter.
  141.     This procedure will return zero for an empty queue, or for a queue which
  142.     has been destroyed.
  143. *)
  144.  
  145.   PROCEDURE  QueueSize (
  146.                 (*in*)  queue:  Queues ):  CARDINAL;
  147.  
  148.     VAR
  149.       Node:  QueueNodePtrs;
  150.       Count: CARDINAL;
  151.  
  152.     BEGIN
  153.       Count := 0;
  154.  
  155.       IF  queue # NIL  THEN
  156.         Node := queue^ .front;
  157.  
  158.         WHILE  Node # NIL  DO
  159.           INC ( Count );
  160.           Node := Node^ .next;
  161.         END;
  162.  
  163.       END;    (* IF queue # nil *)
  164.  
  165.       RETURN  Count;
  166.     END  QueueSize;
  167.  
  168. (*                                                                         [4]
  169.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  170.  
  171.  
  172. (*  Enqueue the data specified in the first parameter into the queue specified
  173.     by the second parameter in first-in, first-out (FIFO) order.  No action
  174.     will be taken for a destroyed queue.
  175. *)
  176.  
  177.   PROCEDURE   FIFOEnqueue (
  178.                    (*in*)  data:   ARRAY  OF BYTE;
  179.                    (*in*)  queue:  Queues );
  180.  
  181.     VAR
  182.       NewNode:   QueueNodePtrs;
  183.       DataSize:  CARDINAL;
  184.  
  185.     BEGIN
  186.       IF  queue # NIL  THEN
  187.         NEW ( NewNode );
  188.         NewNode^ .next := NIL;
  189.  
  190.         (* determine the size in bytes for the BYTE ARRAY indexed 0..HIGH *)
  191.         DataSize       := HIGH ( data ) + 1;
  192.         NewNode^ .size := DataSize;
  193.  
  194.         ALLOCATE ( NewNode^ .contents,  DataSize );
  195.         Move ( ADR ( data ), NewNode^ .contents, DataSize );
  196.  
  197.         IF  isEmpty ( queue )
  198.           THEN  queue^ .front       := NewNode
  199.           ELSE  queue^ .back^ .next := NewNode
  200.         END;
  201.  
  202.         prevBack     := queue^ .back;   (* save for use by PriorityEnqueue *)
  203.         queue^ .back := NewNode;
  204.       END;
  205.     END  FIFOEnqueue;
  206.  
  207. (*                                                                         [5]
  208.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  209.  
  210.  
  211. (*  Enqueue the data specified in the first parameter into the priority queue
  212.     specified by the second parameter.  The entry's priority is taken to be
  213.     the first word of the data, interpreted as CARDINAL.  Zero is the highest
  214.     priority;  lower priorities have higher CARDINAL values.  Thus the queue
  215.     yields entries in increasing value of the priority.  This ordering was
  216.     chosen to accommodate time-based queues.  Entries with the same priority
  217.     are enqueued in order of receipt (FIFO).
  218.     Our implementation strategy is to use FIFOEnqueue to do most of the dirty
  219.     work, and then play with the pointers.
  220. *)
  221.  
  222.   PROCEDURE   PriorityEnqueue (
  223.                        (*in*)  data:   ARRAY  OF BYTE;
  224.                        (*in*)  queue:  Queues );
  225.  
  226.     VAR
  227.       Priority:  CARDINAL;
  228.       ThisPtr,
  229.       LastPtr,
  230.       NewNode:   QueueNodePtrs;
  231.       Scanning:  BOOLEAN;
  232.  
  233.     BEGIN
  234.       FIFOEnqueue ( data, queue );
  235.  
  236.       (* assemble the priority word value from the first two data bytes *)
  237.       Priority := CARDINAL ( data [ 0 ] )  +  CARDINAL ( data [ 1 ] ) << 8;
  238.  
  239.       ThisPtr  := queue^ .front;
  240.       LastPtr  := NIL;
  241.       Scanning := TRUE;
  242.  
  243.       WHILE  Scanning  AND  ( ThisPtr # NIL )  DO
  244.         IF  CARDINAL ( ThisPtr^ .contents^ ) > Priority  THEN
  245.           Scanning := FALSE;     (* found a home *)
  246.  
  247.         ELSE                     (* try the next element *)
  248.           LastPtr  := ThisPtr;
  249.           ThisPtr  := ThisPtr^ .next;
  250.         END;
  251.       END;
  252.  
  253.       (* NB:  if ThisPtr = NIL, the entry is already in the proper place at
  254.               the end of the queue.                                        *)
  255.  
  256.       IF  ThisPtr # NIL  THEN
  257.         NewNode        := queue^ .back;    (* save ptr to new node for use *)
  258.         NewNode^ .next := ThisPtr;
  259.  
  260.         IF  prevBack # NIL  THEN       (* NewNode is not the only entry ... *)
  261.           queue^ .back   := prevBack;  (* ... there's a next-to-last entry, & *)
  262.           prevBack^ .next := NIL;      (* ... that entry becomes last again. *)
  263.         END;
  264.  
  265.         IF  LastPtr = NIL
  266.           THEN  queue^ .front  := NewNode;   (* it goes at the front *)
  267.           ELSE  LastPtr^ .next := NewNode;   (* it goes in the middle *)
  268.         END;   (* IF LastPtr = NIL *)
  269.       END;     (* IF ThisPtr # NIL *)
  270.     END  PriorityEnqueue;
  271.  
  272. (*                                                                         [6]
  273.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  274.  
  275.  
  276. (*  Dequeue, to the data area specified by the first parameter, the front
  277.     element of the queue specified by the second parameter.   If the queue
  278.     is empty (or has been destroyed), the third parameter will be set FALSE;
  279.     it is also set FALSE if the size of the front data element in the queue
  280.     does not match the size of the data area to receive it.  Otherwise, the
  281.     third parameter is set TRUE, indicating that the first parameter has
  282.     valid data.  If the third parameter is FALSE, the queue has not been
  283.     changed, nor has a value been assigned to the first parameter.
  284. *)
  285.  
  286.   PROCEDURE  Dequeue (
  287.          (*out*) VAR  data:    ARRAY  OF BYTE;
  288.          (*in*)       queue:   Queues;
  289.          (*out*) VAR  DataOK:  BOOLEAN );
  290.  
  291.     VAR
  292.       QueueFront: QueueNodePtrs;
  293.       DataSize:   CARDINAL;
  294.  
  295.     BEGIN
  296.       DataOK := NOT isEmpty ( queue );
  297.  
  298.       IF  DataOK  THEN
  299.         (* determine the size in bytes for the BYTE ARRAY indexed 0..HIGH *)
  300.         DataSize   := HIGH ( data ) + 1;
  301.         QueueFront := queue^ .front;
  302.         DataOK     := QueueFront^ .size = DataSize;
  303.  
  304.         IF  DataOK  THEN
  305.           Move ( QueueFront^ .contents, ADR ( data ), DataSize );
  306.  
  307.           DEALLOCATE ( QueueFront^ .contents, QueueFront^ .size );
  308.           queue^ .front := QueueFront^ .next;
  309.  
  310.           IF  queue^ .front = NIL  THEN
  311.               queue^ .back := NIL
  312.           END;
  313.  
  314.           DISPOSE ( QueueFront );
  315.         END;    (* IF data size match *)
  316.       END;    (* IF queue not empty *)
  317.     END  Dequeue;
  318.  
  319. (*                                                                         [7]
  320.  source: h:\modula\code\queues\QueueADT.MOD  v1.0a        revised: 88.07.22 *)
  321.  
  322.  
  323. (*  Copy, to the data area specified by the first parameter, an element of the
  324.     queue specified by the second parameter.   The element to copy is the one
  325.     specified by the third parameter (the front element is numbered zero).
  326.     If the queue is empty (or has been destroyed), the fourth parameter will
  327.     be set FALSE;  it is also set FALSE if the size of the front data element
  328.     in the queue does not match the size of the data area to receive it, or
  329.     if there is no such element.  Otherwise, the fourth parameter is set TRUE,
  330.     indicating that the first parameter has valid data.  No change is made to
  331.     to the queue in any case.  This procedure can be used as part of code to
  332.     dump the contents of a queue--for example, LOOPing using the value of the
  333.     fourth parameter as an EXIT condition.
  334. *)
  335.  
  336.   PROCEDURE  ReadElement (
  337.              (*out*) VAR  data:    ARRAY  OF BYTE;
  338.              (*in*)       queue:   Queues;
  339.              (*in*)       element: CARDINAL;
  340.              (*out*) VAR  DataOK:  BOOLEAN );
  341.  
  342.     VAR
  343.       QueuePtr:  QueueNodePtrs;
  344.       DataSize:  CARDINAL;
  345.  
  346.     BEGIN
  347.       DataOK := NOT isEmpty ( queue );
  348.  
  349.       IF  DataOK  THEN
  350.         QueuePtr := queue^ .front;
  351.         WHILE  ( QueuePtr # NIL )  AND  ( element > 0 )  DO
  352.           QueuePtr := QueuePtr^ .next;
  353.           DEC ( element );
  354.         END;
  355.  
  356.         (* determine the size in bytes for the BYTE ARRAY indexed 0..HIGH *)
  357.         DataSize := HIGH ( data ) + 1;
  358.  
  359.         (* NB:  the following expression depends on Modula-2 short-circuit
  360.            evaluation.  care should be used in porting it.                *)
  361.         DataOK   := ( QueuePtr # NIL )  AND  ( QueuePtr^ .size = DataSize );
  362.  
  363.         IF  DataOK  THEN
  364.           Move ( QueuePtr^ .contents, ADR ( data ), DataSize );
  365.         END;    (* IF data size match *)
  366.       END;    (* IF queue not empty *)
  367.     END  ReadElement;
  368.  
  369. END  QueueADT.
  370.