; AltoQueue.asm - linked list routines ; Copyright Xerox Corporation 1979, 1982 ; Last modified August 25, 1982 9:34 AM by Taft ; The following conventions apply to all routines: ; Q is a pointer to the following structure: ; structure Q: ; [ ; head word // pointer to head item (0 => empty) ; tail word // pointer to tail item ; ] ; If the queue is empty, the tail word is undefined; however, procedures ; in this package that remove Items from queues leave this word pointing to ; the most recent Item which, when removed, caused the queue to become empty. ; Item is a pointer to an object that begins thus: ; structure Item: ; [ ; next word // pointer to next item on queue (0 => no more) ; rest word ?? // rest of object ; ] ; The value of the link word of an Item not on any queue is undefined; ; however, procedures in this package that remove Items from queues ; set this word to -1 for debugging purposes. .titl queue .bext Enqueue .bext Dequeue .bext Unqueue .bext InsertBefore .bext InsertAfter .bext QueueLength .srel Enqueue: .Enqueue Dequeue: .Dequeue Unqueue: .Unqueue InsertBefore: .InsertBefore InsertAfter: .InsertAfter QueueLength: .QueueLength .nrel SWAT=77400 ;----------------------------------------------------------------- ; Enqueue(Q,Item) - Place item on tail of Queue ;----------------------------------------------------------------- .Enqueue: sta 3 1 2 ;save return mov# 1 1 snr ;swat if attempt to queue zero SWAT mov 0 3 ;pointer to Q dir ;interrupts off lda 0 0 3 ;get head of Q mov 0 0 snr ;Q empty? sta 3 1 3 ;yes, make tail point to Q sta 1 @1 3 ;put pointer to Item in tail item's link sta 1 1 3 ;Item is new tail sub 0 0 ;zero Item's link sta 0 @1 3 jmp eirret ;reenable interrupts and return ;----------------------------------------------------------------- ; Dequeue(Q) - Take item from front of Queue; return zero if empty ;----------------------------------------------------------------- .Dequeue: sta 3 1 2 ;save return sta 0 2 2 ;pointer to Q dir ;critical section lda 3 @2 2 ;get head of Q mov 3 0 snr ;Q empty? jmp eirret ;yes, return zero lda 1 0 3 ;get successor sta 1 @2 2 ;put at head of Q adc 1 1 ;put -1 in removed item's link word sta 1 0 3 jmp eirret ;reenable interrupts and return ;----------------------------------------------------------------- ; InsertBefore(Q,Successor,Item) - Put Item before Successor on Q ;----------------------------------------------------------------- .InsertBefore: sta 3 1 2 ;save return dir ;critical section insblp: mov 0 3 snr ;predecessor pointer to usable ac jmp eirret ;return false if fail to find Successor lda 0 0 3 ;get next item sub# 0 1 szr ;is it the desired Successor? jmp insblp ;no, keep looking sta 0 @3 2 ;yes, put it in new Item's link lda 0 3 2 ;get pointer to Item sta 0 0 3 ;put in predecessor's link jmp truret ;reenable interrupts and return true ;----------------------------------------------------------------- ; InsertAfter(Q,Predecessor,Item) - Put Item after Predecessor on Q ;----------------------------------------------------------------- .InsertAfter: sta 3 1 2 ;save return mov 0 3 ;put Q pointer in 3 sta 1 2 2 ;put Predecessor pointer in frame temp dir ;critical section lda 0 @2 2 ;get successor of Predecessor sta 0 @3 2 ;store in Item's link lda 1 3 2 ;get pointer to Item sta 1 @2 2 ;store in Predecessor's link mov# 0 0 snr ;was Predecessor the tail item? sta 1 1 3 ;yes, now Item is tail, update Q jmp truret ;reenable interrupts and return true ;----------------------------------------------------------------- ; Unqueue(Q,Item) - Remove specific Item from Q, return true if found ;----------------------------------------------------------------- .Unqueue: sta 3 1 2 ;save return inc 0 3 ;make pointer to tail sta 3 2 2 ;save for later dir ;critical section unqlp: mov 0 3 snr ;predecessor pointer to usable ac jmp eirret ;return false if fail to find item lda 0 0 3 ;get next item sub# 0 1 szr ;is it the one? jmp unqlp ;no, keep looking lda 0 @0 3 ;yes, get successor adc 1 1 ;put -1 in removed item's link sta 1 @0 3 sta 0 0 3 ;put successor in predecessor's link mov# 0 0 snr ;was item the tail? sta 3 @2 2 ;yes, update tail pointer truret: adc 0 0 ;return true eirret: eir lda 3 1 2 ;get return jmp 1 3 ;----------------------------------------------------------------- ; QueueLength(Q) - Count number of items in Q ;----------------------------------------------------------------- .QueueLength: sta 3 1 2 ;save return mov 0 3 ;point at Q sub 0 0 ;count items for result in 0 dir ;critical section qlnxt: lda 3 0 3 ;next item mov 3 3 snr ;end? jmp eirret ;yes, return count incz 0 0 snc ;count item, punt if stuck jmp qlnxt ;get next SWAT ;Ran off wild probably .end