Archive: forth/lists

Up to parent directory


`lists.log`	`28Aug21 17:30:18EDT`	`3.6K`
`NOTATION`	`30Nov04 13:25:05EST`	`845`	Source conventions.
`list-words.txt`	`28Aug21 17:30:18EDT`	`2.8K`	A functional listing of words in the four kinds of list.
`nodespace.fs`	`28Aug21 17:30:18EDT`	`7.8K`	Allocation and deallocation of nodes, including "unused" chain.
`nodespace-pfe.fs`	`28Aug21 17:30:18EDT`	`2.6K`	Extension of the above for dynamic-string node initialization.
`sendlist.fs`	`28Aug21 17:33:13EDT`	`3.7K`	Definitions common to single-ended lists.
`dendlist.fs`	`28Aug21 17:30:18EDT`	`4.0K`	Definitions common to double-ended lists.
`snode.fs`	`28Aug21 17:30:32EDT`	`1.9K`	Single-linked node structure.
`dnode.fs`	`28Aug21 17:30:18EDT`	`2.1K`	Double-linked node structure.
`sslist.fs`	`28Aug21 17:30:32EDT`	`3.6K`	Single-ended, single-linked lists.
`sdlist.fs`	`28Aug21 17:30:32EDT`	`5.1K`	Single-ended, double-linked lists.
`dslist.fs`	`28Aug21 17:30:18EDT`	`5.2K`	Double-ended, single-linked lists.
`ddlist.fs`	`28Aug21 17:30:18EDT`	`8.1K`	Double-ended, double-linked lists.
`sexample.fs`	`28Aug21 17:30:32EDT`	`3.3K`	Single-linked examples.
`dexample.fs`	`28Aug21 17:30:18EDT`	`4.5K`	Double-linked examples.

Up to top of archive

Files in this directory under the GNU LGPL typically have a POLITENESS request.
This page was last updated by DNW on September 5, 2006.

List Library Overview

These files provide a library which implements four kinds of lists in Forth, with essentially all Forth 200x compatible code. There is a system-dependence on the nonoccurrence of zero node addresses.

The organization of this overview is adapted from the comments in the BSD Unix sys/queue.h header file. Our terminology is slightly different: single-ended and double-ended, single-linked and double-linked lists instead of singly-linked lists, lists, simple queues, and tail queues. The code was written without referring to any C approach.

Heads and tails in list structures hold the addresses of the first and last nodes in the list.

As usual, all insert and remove operations can be done in principle with any of the list types; but not all are natural. We do not implement unnatural operations, those that require list traversal.

Single-ended, single-linked lists. List structures have a head but no tail, so nodes may be prepended to the list, and the first node may be removed.
Nodes have only forward pointers, so the natural traversal is forward, and nodes may be inserted or removed after any node.
Double-ended, single-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.
Nodes have only forward pointers, so the natural traversal is forward, and nodes may be inserted or removed after any node.
Single-ended, double-linked lists. List structures have only a head, so nodes may be prepended to the list, and the first node may be removed.
Nodes have both forward and backward pointers, so both traversals are natural, and nodes may be inserted or removed before or after any node.
Double-ended, double-linked lists. List structures have both a head and a tail, so nodes may be prepended or appended to the list, and the first and last nodes may be removed.
Nodes have both forward and backward pointers, so both traversals are natural, and nodes may be inserted or removed before or after any node.

It would be easy to add circular variants as well.

Loading

The Forth source files in this distribution use the Forth 200x standard word REQUIRED to load external files. All the .fs files listed above need to be placed in a directory where the host system can find them via REQUIRED.

These files are intended to be loaded by the application as a library. To facilitate that, each of the main files for the four types of list, sslist.fs, dslist.fs, sdlist.fs, and ddlist.fs, loads any of the other .fs files it needs, plus the files that complete the application glossary for the corresponding list type.

Any subset of the four may be loaded together without conflict.

The file nodespace-pfe.fs also uses the nonstandard, pfe word LOADM to load the dstrings shared library module, which implements our Dynamic-Strings word set. It becomes ANS Forth compatible if dstrings.fs is loaded instead.

Uncommenting

Some of these files contain words commented out with

  0 [IF] ... [THEN]

They are flagged as "uncommentable" in list-words.txt and in the files themselves. The intent is not that they should actually be uncommented in the list library files themselves, but that they should be pasted into the application as needed, and customized there.

Some word definitions have alternate versions with or without locals commented out with "\". Here the intent is for information only.

All code hidden in either kind of comment has been tested at the same level as the rest of the code. Bug reports for "normal" and "commented-out" code are equally welcome.