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. The 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 ith value in ring. Ring_put changes the ith 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 ith 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.

Figure 12.1. A six-element ring

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 ith value in a ring. Doing this amounts to traversing the list to the ith 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 ith 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;
   }

Figure 12.2. Inserting a new node to the left of head

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.

Figure 12.3. Inserting a new node to the left of q

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 ith 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.

Figure 12.4. Deleting node q

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 ← ith 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.