Thus even if hl is not already reduced modulo n, a subtraction of n (rather than a more expensive division b y n)
will make it so. Since even this subtraction is needed only
about Q/n of the time, a small Q (as in the last paragraph)
saves subtract time.
6.

Conclusion
We have presented a new algorithm for hash coding. I t
has been shown to possess certain attributes that are desired in such algorithms. Specifically it is simple, efficient,
exhaustive, needs little time per probe, and uses few probes
per lookup.

A Nonrecursive List Compacting
Algorithm

RECEIVED JUNE, 1970
REFERENCES
1. MORRIS, R. Scatter storage techniques. Comm. A C M 11, 1
(Jan. 1968), 35-38.
2. MAURER, W . D . An improved hash code for scatter storage.
Comm. ACM 11, 1 (Jan. 1968), 38--44.
3. BELL, J. R. The quadratic quotient method: A hash code
eliminating secondary clustering. Comm. ACM 13, 2 (Feb.
1970), 107-109.
4. RADKE, E . E . The use of quadratic residue research. Comm.
ACM 13, 2 (Feb. 1970), 103-105.

The structure is accessed via the pointer HEAD. This
structure has two lists, the first consisting of three atoms
A, B, C and a list pointer to the second list which consists
solely of a list pointer to the atom A of the first list. Lists

C. J. CI-IENEY

University Mathematical Laboratory, Cambridge, England
+o

A simple nonrecursive list structure compacting scheme or
garbage collector suitable for both compact and LISP-like
list structures is presented. The algorithm avoids the need for
recursion by using the partial structure as it is built up to keep
track of those lists that have been copied.
KEY WORDS AND PHRASES:
llst, LISP
CR CATEGORIES: 4.19, 4.49

(a)
old

list

area

list compacting, garbage collection, compacl

HEAD

new
list

I q/q

SCAN't

area

NEXT~
(b)

Hansen [1] and Fenichel and Yochelson [2] have presented two algorithms for compacting list structures. One
feature of both algorithms is that, on finding a list pointer,
recursion is needed to collect the sublist. The authors of
the second paper suggest that a nonrecursive but complex
scheme should be possible using the algorithm of Deutsch,
Schorr, and Waite [3]. However a much simpler algorithm
is possible.
This algorithm uses a function C O P Y L I S T to copy a
list in the C D R direction from the original list area (the
old area) to a new list area. List pointers are copied without transformation. A linear scan of the new list area
applying C O P Y L I S T to any list pointers found will
copy any sublists into the new area.
To demonstrate the algorithm, consider the structure
in Figure l(a). The cells shown with a pointer from them,
drawn with a broken line, serve only to connect the list in
the C D R direction--these cells will be called "nonitems."
V o l u m e 13 / N u m b e r 11 / November, 1970

HEAD

:: i i

....

,+AIBI¢I

I/1

SCANT

I

,
I
I

NEXTT

(c)

II I,. . . . .
I ,
I
I
I

I

:

.~

'.---5....,_.,,
Itl/l

Is

+
I

HEAD dAiSlCi ~,iA i,i/, 1
TNEXT
SCAN
(d)

FIG. 1. Compacting a structure without looped lists: (a) initial
structure; (b) and (c) during processing; (d) final structure.
Communications

o f t h e ACM

677

are terminated by N I L cells. The algorithm with some
modification can be applied to LISP-type structures.
To compact the structure, the list pointed to by H E A D
is copied by C O P Y L I S T into the new area--the contents
of each item (not nonitems) are placed in consecutive cells
in the new area, and the cells in the old area are changed
to nonitems pointing to their equivalent cells in the new
area. C O P Y L I S T returns as a result the address of the
first cell of the list in the new area. This value is used to
update H E A D . A pointer N E X T is kept pointing to the
next free cell in the new area. This intermediate structure
is shown in Figure 1 (b).
A further pointer SCAN now scans the new area from
the beginning. If SCAN points to a N I L or an atom, it is
moved on to the next cell. If SCAN points to a list pointer,
C O P Y L I S T is entered with this list pointer as its parameter. The sublist is therefore copied, updating N E X T ,
and the value returned is used to make the list pointer
pointed at by SCAN point to the copied list in the new
area. The structure resulting when SCAN has processed
the first list pointer is shown in Figure 1 (c). Note that, in
copying, C O P Y L I S T omits the nonitems of the original
structure.
SCAN continues its traverse of the new area and will
pass over the N I L to the second list to reach another list
pointer. C O P Y L I S T is again applied, but this time it
finds the first item is already in the new area (e.g. by comparing core addresses), and the function returns with the
address of this cell in the new area, which is used to update
the list pointer, but without recopying the list.
The compact structure is complete when SCAN reaches
the cell pointed to by N E X T . The procedure is capable of
dealing with looped lists as C O P Y L I S T will place a nonitem in the new area when necessary (see Figure 2).

A version has been written in assembly language involving the execution of between 30 and 40 orders on an
Atlas computer for each item of the structure transferred
to the new area.
The algorithm is presented below in two p a r t s - - t h e
"main program" first, and then the function COPYLIST.
Step 1. Initialize the pointers SCAN a n d N E X T to p o i n t to the
beginning of the new list area.
Step 2. Apply the function C O P Y L I S T - - d e s c r i b e d b e l o w - - t o
the pointer t h a t points to the whole s t r u c t u r e a n d assign
the result of C O P Y L I S T to t h a t pointer.
Step 3. If SCAN points to a list-pointer, t h e n apply C O P Y L I S T
to t h a t list pointer, the result of C O P Y L I S T replaces the
c o n t e n t s of the cell pointed at b y SCAN.
Step 4. I n c r e m e n t SCAN, unless SCAN now points to the same
cell pointed at b y N E X T , go to step 3 above. Otherwise the
compacting is complete.

The function C O P Y L I S T takes one parameter,
P O I N T E R , called by value; the function does the following:
Step 1. If P O I N T E R points to a cell t h a t is a n o n i t e m , make
P O I N T E R p o i n t to the cell pointed a t by the n o n i t e m . Repeat this step while P O I N T E R points to a n o n i t e m .
Step 2. If P O I N T E R is pointing to a cell in the new area, r e t u r n
w i t h the value of P O I N T E R as the result.
Step 3. Save the c u r r e n t value of N E X T in a v a r i a b l e V.
Step 4. If P O I N T E R is pointing to a cell in the new area, make
the cell pointed at b y N E X T into a n o n i t e m pointing to the
cell t h a t is pointed a t b y P O I N T E R , a n d go to step 11 below.
Step 5. Copy the c o n t e n t s of the cell pointed at by P O I N T E R to
the cell pointed a t b y N E X T .
Step 6. If P O I N T E R is pointing to a N I L , t h e n go to step 11 below.
Step 7. Make the cell pointed at by P O I N T E R into a n o n i t e m
t h a t points to the cell pointed at b y N E X T , i.e. the corres p o n d i n g cell in the new area.
Step 8. I n c r e m e n t N E X T , i n c r e m e n t P O I N T E R .
Step 9. If P O I N T E R points to a nonitem, make P O I N T E R p o i n t
to the cell pointed at b y the n o n i t e m , repeat this step while
P O I N T E R is pointing to a n o n i t e m .
Step 10. Go to step 4 of the function C O P Y L I S T .

(o)
o,0

list

HEAD

orgc]
i
I
i

i
i
I

fleW

~-]-~-N
POINTE

list

oreG

EXT
(b)

I
I

.....

I

I
I

4.,g-~---I

FIG. 2. C o m p a c t i n g a looped list
Communications

Acknowledgments. The author is particularly grateful
for many discussions with N. E. Wiseman and for the
criticisms of the draft of this note from M. V. Wilkes.
RECmVED MARCH, 1970; REVISED JUNE, 1970
REFERENCES

HEAD .~AiBi~i
(c}'rNEXT

678

Step 11. I n c r e m e n t N E X T a n d r e t u r n w i t h the v a l u e of V as the
result.

o f t h e ACM

1. HANSEN, W. J. C o m p a c t list r e p r e s e n t a t i o n : definition, garbage collection and s y s t e m i m p l e m e n t a t i o n . Comm. ACM 12,
9 (Sept. 1969), 499-507.
2. FENICHEL, R. R., AND YOCHELSON, J. C. A L I S P garbagecollector for v i r t u a l m e m o r y c o m p u t e r symstems. Comm.
ACM 1P, 11 (Nov. 1969), 611-612.
3. KNUTH, D. E. The Art of Computer Programming Vol. 1 Fundamental Algorithms. Addison-Wesley, Reading, Mass.,
1968, pp. 417-419.
V o l u m e 13 / N u m b e r 11 / N o v e m b e r , 1970