/ rlink=-4 llink=-2 PROGRAM lists STRUCT l ;create structure l FIELD n,key ;assign n and key offsets END-STRUCT l ;+ ; Doubly linked list routines - C compatible ; ; FUNCTION ilist[lhead] ; Initialize a list head. List heads are 6 byte ; arrays where the 1st word is initialized to ; the address of the listhead itself, the 2nd ; and 3rd words are the links. If there was any ; data in this node then it would have been at ; word 4. Word one points to this location. All ; nodes look like: ; ; word 0 right link ; word 1 left link ; pointers->word 2-n data ; ; A listhead looks like: ; .word address-of-list ; .word pointer-to-right-link ; .word pointer-to-left-link ; address: (no data so nothing allocated here) ; ; Then the listhead array is used by referencing ; the contents of the first element which points ; to the first node. This is all only necessary ; to simplify matters since list operations ; assume a circular list where all nodes have ; two pointers. ; ; ; FUNCTION delete[ptr] ; Deletes the node ptr from the list it is in. ; Returns ptr which is now a doubly linked list ; of one single element. ; FUNCTION insert[x,newx] ; Inserts the node newx after the node x in the ; list x is in. returns pointer newx. ; FUNCTION prev[ptr] ; Returns a pointer to the previous node in the ; list. ; FUNCTION next[ptr] ; Returns a pointer to the next node in the ; list. ; FUNCTION release[ptr] ; This releases storage for the node pointed to ; by ptr. ; FUNCTION new[size] ; Allocates a node for a structure of size ; "size". Also allocates storage for the link ; fields (which precede the storage of "size" ; bytes. The pointer returned points to the ; start of the data (not the links which are a ; -2 and -4 from the data). Note that release ; must be used to return storage allocated by ; new since each of these routines know about ; the extra 4 bytes of linkage. New also ; initializes the link fields such that the node ; is a complete list of one item. ;- ; AUTO lh[6] ; FUNCTION main[argc,argv] ; . ilist[&lh] ;init listhead lh ; LET r4 = val[.argv[#1],#10.] ;get number from command line ; LOOP for r3 = #1 TO r4 ;allocate r4 nodes ; LET r2 = new[#l] ;get node of size l (structure l) ; mov r3,n(r2) ;move data to node r2 points to ; mov #-1,key(r2) ;thus n and key are loaded ; . insert[prev[lh],r2] ;now insert in list before lh ; NEXT r3 ; PRINTF "list head %o" &lh ; . ldump[lh] ;dump list ; . next[next[lh]] ;get 2nd node in list ; LET r4 = delete[r0] ;delete from list ; . ldump[r4] ;dump singleton list just extracted ; . insert[prev[lh],r4] ;put it back at beginning of list ; . ldump[lh] ;now dump same list re-ordered ; ;iot ; RET FUNCTION new[size] LET r2 = alloc[] + #4 IF r2 HI sp mov r2,rlink(r2) mov r2,llink(r2) RET r2 ELSE RET #0 FI FUNCTION release[ptr] LET r2 = free[] RET r2 ;----------------------------------------- ; FUNCTION next[ptr] ; LET r0 = ptr ; mov rlink(r0),r0 ; RET ;----------------------------------------- next:: ;fast versions, no register saves mov 2(sp),r0 mov rlink(r0),r0 rts pc ;----------------------------------------- ; FUNCTION prev[ptr] ; LET r0 = ptr ; mov llink(r0),r0 ; RET ;----------------------------------------- prev:: ;fast versions mov 2(sp),r0 mov llink(r0),r0 rts pc ;----------------------------------------- FUNCTION insert[x,newx] LET r0 = x LET r1 = newx mov r0,llink(r1) mov rlink(r0),rlink(r1) mov rlink(r0),r2 mov r1,llink(r2) mov r1,rlink(r0) RET r1 FUNCTION delete[ptr] LET r0 = ptr mov llink(r0),r1 mov rlink(r0),rlink(r1) mov rlink(r0),r1 mov llink(r0),llink(r1) mov r0,llink(r0) mov r0,rlink(r0) RET FUNCTION ilist[lhead] LET r0 = lhead + #6 mov r0,-2(r0) mov r0,-4(r0) mov r0,-6(r0) RET .end