;----------------------------------------------------------------- ;AltoQueue.asm - linked list routines ;Nova compatible file is NovaQueue.sr ;----------------------------------------------------------------- ; 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. ; Item is a pointer to an object whose first word may be used ; as a link to another Item (0 => no more items). .titl queue .bext Enqueue .bext Dequeue .bext Unqueue .bext InsertBefore .bext InsertAfter .bext LengthQ .srel Enqueue: .Enqueue Dequeue: .Dequeue Unqueue: .Unqueue InsertBefore: .InsertBefore InsertAfter: .InsertAfter LengthQ: .QueueLength .nrel SWAT=77400 ;----------------------------------------------------------------- ;Enqueue(Q,Item) - Place item on tail of Queue ;----------------------------------------------------------------- .Enqueue: sta 3 1 2 ;save return 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 ;----------------------------------------------------------------- .Dequeue: sta 3 1 2 ;save return mov 0 3 ;point at Q dir ;protect lda 0 0 3 ;get head of Q lda 1 @0 3 ;get successor if any mov 0 0 szr ;Q empty? sta 1 0 3 ;no, put successor at head of Q 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 sta 0 0 3 ;put 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 QLNxt: lda 3 0 3 ;next item mov 3 3 snr ;end? jmp QLEnd ;yes, return count incz 0 0 snc ;count item, punt if stuck jmp QLNxt ;get next SWAT ;Ran off wild probably QLEnd: lda 3 1 2 jmp 1 3 ;return, resultis count .end