In article <1159976595.342555.21350@[EMAIL PROTECTED]
>,
"Charles Turner" <vze26m98@[EMAIL PROTECTED]
> wrote:
> Hi all-
>
> Am I correct in thinking that Relative Chains are a bit of overkill if
> what I'm looking for is a simple linked list implementation for numbers
> and strings?
>
> Anyone willing to share or point to examples of either approach?
>
> Best, Charles
\ Assuming the list is made of nodes and each node is composed of two
cells.
\ Cell 1 contains pointer to another node, the link.
\ Cell2 points to another list, literal data, structure, xt, whatever.
\
\ There are many ways to create these lists, here I use a free list from
\ which I'll construct new lists.
\ Last Revision: 03/19/03 18:02:50 -rt
anew -lisp--
default-order
decimal
\ note on stack comments:
\ node = address node-structure
\ list = address first node-structure in list aka chain of nodes
\ Allocate LISP cells
2 cells constant Node \ a list node has '2 cells' a.units
512 constant #Nodes \ bit arbitrary, but dividable by '2 cells'
create List-Heap \ nodes will be cons from here
#Nodes Node * allot \ 8 bytes, sorry: a.units, per cell
create Nil Nil , Nil , \ special terminal node
variable Free-List \ free list handle
: Zero-Heap
List-Heap [ #Nodes Node * ] literal erase ;
: Init-Free-List ( --)
Zero-Heap \ not nescessary
List-Heap
#Nodes 1- 0 \ all nodes except the last
do \ will be linked
dup Node + dup >r swap ! r>
loop
Nil swap ! \ last is linked to Nil node
List-Heap Free-List ! \ Free-List contains whole heap
;
cr .( Initiating the Heap into a List)
Init-Free-List
\ Some words to deal with the list, some have LISP names
\ retrieves what is in the first node's 'pointer cell'
: CAR ( list -- x )
cell+ @[EMAIL PROTECTED]
;
\ return next node i.e. rest of list
: CDR ( list -- restlist)
@[EMAIL PROTECTED]
;
\ add node to the beginning of the list and return 'newlist'
: add-node ( node list -- newlist )
over ! ;
\ remove first node, returning node and 'newlist'
: remove-node ( list -- node restlist )
dup CDR ;
\ get us a node from heap
: heap> ( -- node )
Free-List @[EMAIL PROTECTED]
remove-node 2dup = abort" Empty List" Free-List ! ;
\ return node to heap
: >heap ( node -- )
Free-List @[EMAIL PROTECTED]
add-node Free-List ! ;
\ number of nodes in list
: nodes ( list -- n )
0 swap begin dup NIL <> while 1 under+ CDR repeat drop ;
\ add item to a list returning the newlist
: CONS ( item list -- newlist)
heap>
swap add-node
swap over cell+ ! ;
\ make new list from items, which can be lists themself
\ nil is always used as first node of a new list
: LIST ( item0 ... itemn n-1 -- newlist )
>r nil r> 0 ?do CONS loop ;
\ show what is in list
(*
: show ( list - )
begin dup Nil = invert
while dup CAR cr . CDR
repeat
drop cr ." nil" ;
*)
: SHOW ( list - )
dup Nil = if drop ." nil" exit then
dup CAR cr . CDR
recurse ;
prior.stream
\ example:
debug on
s" Charles Turner" 2 list dup
dup show
dup CAR swap CDR
dup CAR swap CDR
show
type
free-list @[EMAIL PROTECTED]
nodes .
hoi
roelf
|
