A ring is much like a sequence: It holds N
values associated with the integer indices zero through N
−1 when N
is positive. An empty ring holds no values. Values are pointers. Like the values in a sequence, values in a ring may be accessed by indexing.
Unlike a sequence, however, values can be added to a ring anywhere, and any value in a ring can be removed. In addition, the values can be renumbered: “rotating” a ring left decrements the index of each value by one modulo the length of the ring; rotating it right increments the indices by one modulo the ring length. The price for the flexibility of adding values to and removing values from arbitrary locations in a ring is that accessing the i
th value is not guaranteed to take constant time.
As suggested by its name, a ring is an abstraction of a doubly linked list, but the Ring
ADT reveals only that a ring is an instance of an opaque pointer type:
<ring.h>≡ #ifndef RING_INCLUDED #define RING_INCLUDED #define T Ring_T typedef struct T *T; <exported functions 184> #undef T #endif
It is a checked runtime error to pass a null T
to any routine in this interface.
Rings are created by the functions that parallel similar functions in the Seq
interface:
<exported functions 184>≡
extern T Ring_new (void);
extern T Ring_ring(void *x, ...);
Ring_new
creates and returns an empty ring. Ring_ring
creates and returns a ring whose values are initialized to its nonnull pointer arguments. The argument list is terminated by the first null pointer argument. Thus
Ring_T names; ... names = Ring_ring("Lists", "Tables", "Sets", "Sequences", "Rings", NULL);
creates a ring with the five values shown, and assigns it to names
. The values in the argument list are associated with the indices zero through four. T
he pointers passed in the variable part of the ring’s argument list are assumed to be void pointers, so programmers must provide casts when passing other than char or void pointers; see page 105. Ring_new
and Ring_ring
can raise Mem_Failed
.
<exported functions 184>+≡
extern void Ring_free (T *ring);
extern int Ring_length(T ring);
Ring_free
deallocates the ring in *ring
and clears *ring
. It is a checked runtime error for ring
or *ring
to be null pointers. Ring_length
returns the number of values in ring
.
The values in a ring of length N
are associated with the integer indices zero through N
−1. These values are accessed by the functions
<exported functions 184>+≡
extern void *Ring_get(T ring, int i);
extern void *Ring_put(T ring, int i, void *x);
Ring_get
returns the i
th value in ring
. Ring_put
changes the i
th value in ring
to x
and returns the previous value. It is a checked runtime error for i
to be equal to or greater than N
.
Values may be added anywhere in a ring by
<exported functions 184>+≡
extern void *Ring_add(T ring, int pos, void *x);
Ring_add
adds x
to ring
at position pos
and returns x
. The positions in a ring with N
values specify locations between values as depicted in the following diagram, which shows a five-element ring holding the integers zero through four.
The middle row of numbers are the indices, the top row are the positive positions, and the bottom row are the nonpositive positions. The nonpositive positions specify locations from the end of the ring without knowing its length. The positions zero and one are also valid for empty rings. Ring_add
accepts either form of position. It is a checked runtime error to specify a nonexistent position, which inlcudes the positive positions than exceed one plus the length of the ring and the negative positions whose absolute values exceed the length of the ring.
Adding a new value increments both the indices of the values to its right and the length of the ring by one. Ring_add
can raise Mem_Failed
.
The functions
<exported functions 184>+≡
extern void *Ring_addlo(T ring, void *x);
extern void *Ring_addhi(T ring, void *x);
are equivalent to their similarly named counterparts in the Seq
interface. Ring_addlo
is equivalent to Ring_add(ring, 1, x)
, and Ring_addhi
is equivalent to Ring_add(ring, 0, x)
. Ring_addlo
and Ring_addhi
can raise Mem_Failed
.
The function
<exported functions 184>+≡
extern void *Ring_remove(T ring, int i);
removes and returns the i
th value in ring
. Removing a value decrements the indices of the remaining values to its right by one and the length of the ring by one. It is a checked runtime error for i
to be equal to or exceed the length of ring
.
Like the Seq
functions with similar names, the functions
<exported functions 184>+≡
extern void *Ring_remlo(T ring);
extern void *Ring_remhi(T ring);
remove and return the value at the low or high end of ring
. Ring_remlo
is equivalent to Ring_remove(ring, 0)
, and Ring_remhi
is equivalent to Ring_remove(ring, Ring_length(ring) - 1)
. It is a checked runtime error to pass an empty ring to Ring_remlo
or Ring_remhi
.
The name “ring” comes from the function
<exported functions 184>+≡
extern void Ring_rotate(T ring, int n);
which renumbers the values in ring
by “rotating” it left or right. If n
is positive, ring
is rotated to the right — clockwise — n
values, and the indices of each value are incremented by n
modulo the length of ring
. Rotating an eight-value ring that holds the strings A
through H
three places to the right is illustrated by the following diagram; the arrows point to the first element.
If n
is negative, ring
is rotated to the left — counterclockwise — n
values and the indices of each value are decremented by n
modulo the length of ring. If n
modulo the length of the ring is zero, Ring_rotate
has no effect. It is a checked runtime error for the absolute value of n
to exceed the length of ring
.
The implementation represents a ring as a structure with two fields:
<ring.c>≡ #include <stdlib.h> #include <stdarg.h> #include <string.h> #include "assert.h" #include "ring.h" #include "mem.h" #define T Ring_T struct T { struct node { struct node *llink, *rlink; void *value; } *head; int length; }; <functions 188>
The head
field points to a doubly linked list of node
structures in which the value
fields hold the values in the ring. head
points to the value associated with index zero; successive values are in the nodes linked by the rlink
fields, and each node’s llink
field points to its predecessor. Figure 12.1 shows the structures for a ring with six values. The dotted lines emanate from the llink
fields and go counterclockwise, and the solid lines emanate from the rlink
fields and go clockwise.
An empty ring has a zero length
field and a null head
field, which is what Ring_new
returns:
<functions 188>≡
T Ring_new(void) {
T ring;
NEW0(ring);
ring->head = NULL;
return ring;
}
Ring_ring
creates an empty ring, then calls Ring_addhi
to append each of its pointer arguments up to but not including the first null pointer:
<functions 188>+≡
T Ring_ring(void *x, ...) {
va_list ap;
T ring = Ring_new();
va_start(ap, x);
for ( ; x; x = va_arg(ap, void *))
Ring_addhi(ring, x);
va_end(ap);
return ring;
}
Deallocating a ring first deallocates the node
structures, then deallocates the ring header. It doesn’t matter in which order the nodes are deallocated, so Ring_free
just follows the rlink
pointers.
<functions 188>+≡
void Ring_free(T *ring) {
struct node *p, *q;
assert(ring && *ring);
if ((p = (*ring)->head) != NULL) {
int n = (*ring)->length;
for ( ; n-- > 0; p = q) {
q = p->rlink;
FREE(p);
}
}
FREE(*ring);
}
The function
<functions 188>+≡
int Ring_length(T ring) {
assert(ring);
return ring->length;
}
returns the number of values in a ring.
Ring_get
and Ring_put
must both find the i
th value in a ring. Doing this amounts to traversing the list to the i
th node structure, which is accomplished by the following chunk.
<q ← ith node 189>≡
{
int n;
q = ring->head;
if (i <= ring->length/2)
for (n = i; n-- > 0; )
q = q->rlink;
else
for (n = ring->length - i; n-- > 0; )
q = q->llink;
}
This code takes the shortest route to the i
th node: If i
is does not exceed one-half the ring’s length, the first for loop goes clockwise via the rlink
pointers to the desired node. Otherwise, the second for loop goes counterclockwise via the llink
pointers. In Figure 12.1, for example, values 0 through 3 are reached by going right, and values 4 and 5 are reached by going left.
Given this chunk, the two access functions are easy:
<functions 188>+≡ void *Ring_get(T ring, int i) { struct node *q; assert(ring); assert(i >= 0 && i < ring->length); <q ← ith node 189> return q->value; } void *Ring_put(T ring, int i, void *x) { struct node *q; void *prev; assert(ring); assert(i >= 0 && i < ring->length); <q ← ith node 189> prev = q->value; q->value = x; return prev; }
The functions that add values to a ring must allocate a node, initialize it, and insert it into its proper place in the doubly linked list. They must also cope with adding a node to an empty ring. Ring_addhi
is the easiest one of these functions: It adds a new node to the left of the node pointed to by head
, as shown in Figure 12.2. Shading distinguishes the new node, and the heavier lines in the righthand figure indicate which links are changed. Here’s the code:
<functions 188>+≡ void *Ring_addhi(T ring, void *x) { struct node *p, *q; assert(ring); NEW(p); if ((q = ring->head) != NULL) <insert p to the left of q 191> else <make p ring's only value 191> ring->length++; return p->value = x; }
Adding a value to an empty ring is easy: ring->head
points to the new node, and the node’s links point to the node itself.
<make p ring's only value 191>≡ ring->head = p->llink = p->rlink = p;
As suggested in Figure 12.2, Ring_addhi
aims q
at the first node in the ring and inserts the new node to its left. This insertion involves initializing the links of the new node and redirecting q
’s llink
and q
’s predecessor’s rlink
:
<insert p to the left of q 191>≡ { p->llink = q->llink; q->llink->rlink = p; p->rlink = q; q->llink = p; }
The second through fifth diagrams in the Figure 12.3’s sequence illustrate the individual effect of these four statements. At each step, heavy arcs show the new links. It’s instructive to redraw this sequence when q
points to the only node in the doubly linked list.
Ring_addlo
is almost as easy, but the new node becomes the first node in the ring. This transformation can be accomplished by calling Ring_addhi
then rotating the ring one value to the right, which is done by setting head
to its predecessor:
<functions 188>+≡
void *Ring_addlo(T ring, void *x) {
assert(ring);
Ring_addhi(ring, x);
ring->head = ring->head->llink;
return x;
}
Ring_add
is the most complicated of the three functions that add values to a ring because it deals with the arbitrary positions described in the previous section, which include adding values to either end of the ring. These cases can be handled by letting Ring_addlo
and Ring_addhi
deal with additions at the ends, which incidentally takes care of the empty ring case, and, for the other cases, converts a position to the index of the value to the right of the position and adds the new node to its left, as above.
<functions 188>+≡ void *Ring_add(T ring, int pos, void *x) { assert(ring); assert(pos >= -ring->length && pos<=ring->length+1); if (pos == 1 || pos == -ring->length) return Ring_addlo(ring, x); else if (pos == 0 || pos == ring->length + 1) return Ring_addhi(ring, x); else { struct node *p, *q; int i = pos < 0 ? pos + ring->length : pos - 1; <q ← ith node 189> NEW(p); <insert p to the left of q 191> ring->length++; return p->value = x; } }
The first two if statements cover positions that specify the ends of the ring. The initialization of i
handles the positions that correspond to the indices one through ring->length - 1
.
The three functions that remove values are easier than those that add values because there are fewer boundary conditions; the only one is when the last value in a ring is removed. Ring_remove
is the most general of the three functions: It finds the i
th node and removes it from the doubly linked list:
<functions 188>+≡ void *Ring_remove(T ring, int i) { void *x; struct node *q; assert(ring); assert(ring->length > 0); assert(i >= 0 && i < ring->length); <q ← ith node 189> if (i == 0) ring->head = ring->head->rlink; x = q->value; <delete node q 194> return x; }
If i
is zero, Ring_remove
deletes the first node and thus must redirect head
to the new first node.
Adding a node involves four pointer assignments; deleting one requires only two:
<delete node q 194>≡
q->llink->rlink = q->rlink;
q->rlink->llink = q->llink;
FREE(q);
if (--ring->length == 0)
ring->head = NULL;
The second and third diagrams in Figure 12.4 illustrate the individual effect of the two statements at the beginning of this chunk. The affected links are shown with heavy arcs. The third statement in <delete node
q 194
> frees the node, and the last two statements decrement ring
’s length
and clear its head
pointer if its last node was just deleted. Again, it’s instructive to draw the sequence for deleting a node from one- and two-node lists.
Ring_remhi
is similar, but finding the doomed node is easier:
<functions 188>+≡ void *Ring_remhi(T ring) { void *x; struct node *q; assert(ring); assert(ring->length > 0); q = ring->head->llink; x = q->value; <delete node q 194> return x; }
As shown above, Ring_addlo
is implemented by calling Ring_addhi
and changing ring
’s head
to point to its predecessor. The symmetric idiom implements Ring_remlo
: Change ring
’s head
to point to its successor and call Ring_remhi
.
<functions 188>+≡
void *Ring_remlo(T ring) {
assert(ring);
assert(ring->length > 0);
ring->head = ring->head->rlink;
return Ring_remhi(ring);
}
The last operation rotates a ring. If n
is positive, an N
-value ring is rotated clockwise, which means that the value with index n
modulo N
becomes its new head
. If n
is negative, the ring is rotated counterclockwise, which means its head
moves to the value with index n +
N
.
<functions 188>+≡ void Ring_rotate(T ring, int n) { struct node *q; int i; assert(ring); assert(n >= -ring->length && n <= ring->length); if (n >= 0) i = n%ring->length; else i = n + ring->length; <q ← ith node 189> ring->head = q; }
Using <q
← i
th node
189
> here ensures that the rotation takes the shortest route.
Both Knuth (1973a) and Sedgewick (1990) cover the algorithms for manipulating doubly linked lists in detail.
Some of the operations provided in Icon for removing and adding values to a list are similar to those provided by Ring
. Exercise 12.4 explores the Icon implementation. The scheme used in Ring_add
for specifying positions is from Icon.