Project 11: Ring Module - Circular Buffers

Build a fixed-size circular buffer with O(1) insertions and deletions at both ends, plus rotation operations.

Quick Reference

Attribute	Value
Difficulty	Level 3 - Advanced
Time Estimate	3-5 days
Language	C
Prerequisites	Mem module, Assert module, Array fundamentals
Key Topics	Circular buffers, Modular arithmetic, Producer-consumer patterns, Fixed-size data structures

---

1. Learning Objectives

By completing this project, you will:

1. Understand circular buffer mechanics - Master the head/tail pointer management and wrap-around logic that makes ring buffers work
2. Implement bounded containers - Learn how fixed-size constraints enable simpler, faster implementations compared to dynamic structures
3. Solve the full/empty ambiguity - Address the classic ring buffer problem where head == tail could mean full OR empty
4. Apply modular arithmetic - Use modulo operations for efficient circular indexing without branching
5. Design producer-consumer interfaces - Create APIs suitable for real-time systems where overflow/underflow must be explicit

Why Ring Buffers Matter:

Ring buffers are everywhere in systems programming:

• Audio systems: Buffering samples between producer (microphone) and consumer (speaker)
• Network drivers: Storing incoming packets before processing
• Keyboard input: Buffering keystrokes until the application reads them
• Logging systems: Keeping the last N log entries in memory
• UART/Serial communication: Handling byte streams at different rates

The key insight is that a ring buffer provides O(1) operations at both ends with predictable memory usage - no allocations during normal operation, making it ideal for real-time and embedded systems.

---

2. Theoretical Foundation

2.1 Core Concepts

The Circular Nature of Ring Buffers

A ring buffer treats a linear array as if it were circular. When you reach the end, you wrap around to the beginning:

Ring Buffer Visualization
--------------------------------------------------------------------------------

Physical Memory (Linear Array):
    Index:    0      1      2      3      4      5      6      7
            +------+------+------+------+------+------+------+------+
            |  D   |  E   |      |      |      |  A   |  B   |  C   |
            +------+------+------+------+------+------+------+------+
                    ^                           ^
                    |                           |
                   tail                        head
                  (write)                      (read)

Logical View (Circular):
                        ┌─────┐
                       /   A   \
                     /           \
                   ┌─────┐     ┌─────┐
                  │   H   │   │   B   │
                   └─────┘     └─────┘
                  │               │
             ┌─────┐           ┌─────┐
             │   G   │         │   C   │
             └─────┘           └─────┘
                  │               │
                   └─────┐     ┌─────┘
                         │   │
                        ┌─────┐
                         │   D   │
                        └─────┘

Operations:
- Add at tail: Store value, advance tail
- Remove from head: Return value, advance head
- Both "advance" operations wrap using modulo: (index + 1) % capacity

Index Wrap-Around Mathematics

The modulo operation is the key to circular behavior:

Modular Arithmetic for Ring Buffers
--------------------------------------------------------------------------------

Given:
  - capacity = 8
  - current_index = 7 (last position)

Advance:
  next_index = (current_index + 1) % capacity
             = (7 + 1) % 8
             = 8 % 8
             = 0  ← Wraps back to start!

Key properties:
  - (index + 1) % capacity always gives next position
  - (index - 1 + capacity) % capacity gives previous position
  - For power-of-2 capacity: index & (capacity - 1) is faster than %

Example with capacity = 8:

  Position sequence as we advance:
  0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 0 → 1 → 2 → ...

  Using modulo:
  (0+1)%8=1, (1+1)%8=2, ..., (7+1)%8=0, (0+1)%8=1, ...

The Full/Empty Ambiguity Problem

The classic ring buffer challenge: when head equals tail, is the buffer full or empty?

The Full vs Empty Ambiguity
--------------------------------------------------------------------------------

Empty state:          Full state (with the problem):
head = tail = 0       head = tail = 0

  +---+---+---+---+     +---+---+---+---+
  |   |   |   |   |     | A | B | C | D |
  +---+---+---+---+     +---+---+---+---+
    ^                     ^
    |                     |
  head                  head
  tail                  tail

PROBLEM: Both states have head == tail!

Three solutions:

SOLUTION 1: Waste One Slot
  - Never fill the last slot
  - Full when (tail + 1) % capacity == head
  - Empty when tail == head
  - Wastes one slot of capacity

  Empty:                Full (capacity-1 items):
    +---+---+---+---+     +---+---+---+---+
    |   |   |   |   |     | A | B | C |   |
    +---+---+---+---+     +---+---+---+---+
      ^                     ^           ^
      |                     |           |
    head                  head        tail
    tail                  (tail+1)%4 == head → FULL

SOLUTION 2: Track Count Separately
  - Keep a count variable
  - Full when count == capacity
  - Empty when count == 0
  - No wasted slots
  - Extra variable to maintain

SOLUTION 3: Use a Flag
  - Boolean flag indicates last operation was write or read
  - If head == tail && last_was_write → Full
  - If head == tail && !last_was_write → Empty
  - Slightly more complex logic

Hanson's CII uses Solution 2 (count tracking) for clarity.

2.2 Why This Matters

Ring buffers are fundamental to systems programming because they provide:

1. Bounded Memory: You know exactly how much memory is used, always
2. O(1) Operations: Add and remove are constant time, no reallocation
3. Cache-Friendly: Sequential memory access when iterating
4. Real-Time Safe: No dynamic allocation during operation
5. Lock-Free Potential: Single producer/single consumer can be lock-free

Industry Applications:

Domain	Application	Why Ring Buffer?
Audio	Sample buffering	Constant latency, no allocation during playback
Networking	Packet queues	Bounded memory, predictable overflow behavior
Logging	Circular logs	Keep last N entries, oldest entries overwritten
Embedded	UART buffers	No heap allocation, interrupt-safe
Games	Input buffering	Fixed latency, handles input bursts

2.3 Historical Context

Ring buffers date back to early computing when memory was scarce and expensive. The technique was formalized in the context of producer-consumer problems in operating systems design.

Historical Milestones:

• 1960s: Ring buffers used in early operating systems for I/O buffering
• 1970s: Formalized in Dijkstra’s producer-consumer problem solutions
• 1990s: Lock-free ring buffers developed for multiprocessor systems
• 2000s: High-performance network stacks (DPDK) rely heavily on ring buffers
• Today: Every audio API, network driver, and embedded system uses them

Hanson’s Contribution: In CII, Hanson presents the Ring module as a complement to Seq (double-ended queue). While Seq grows dynamically, Ring has a fixed capacity. This constraint isn’t a limitation - it’s a feature that enables simpler implementation and predictable behavior.

2.4 Common Misconceptions

Misconception 1: “Ring buffers are just arrays”

• Reality: The wrap-around logic and head/tail management are non-trivial. Off-by-one errors are extremely common.

Misconception 2: “Wasting one slot is inefficient”

• Reality: The wasted slot approach is often preferred because it simplifies the code and avoids the overhead of maintaining a count.

Misconception 3: “Ring buffers are only for single-producer/single-consumer”

• Reality: While SPSC is common, multi-producer/multi-consumer ring buffers exist (with appropriate synchronization).

Misconception 4: “Modulo is slow, avoid it”

• Reality: For power-of-2 capacities, index & (capacity - 1) is as fast as any other bitwise operation. Modern CPUs also have fast division/modulo.

---

3. Project Specification

3.1 What You Will Build

A complete Ring module implementing Hanson’s CII interface:

// ring.h - The Interface

#ifndef RING_INCLUDED
#define RING_INCLUDED

#define T Ring_T
typedef struct T *T;

/* Creation and destruction */
extern T    Ring_new    (int hint);
extern T    Ring_ring   (void *x, ...);  /* NULL-terminated varargs */
extern void Ring_free   (T *ring);

/* Properties */
extern int  Ring_length (T ring);

/* Access */
extern void *Ring_get   (T ring, int i);
extern void *Ring_put   (T ring, int i, void *x);

/* Add/remove operations */
extern void *Ring_addhi (T ring, void *x);   /* Add at high end (tail) */
extern void *Ring_addlo (T ring, void *x);   /* Add at low end (head) */
extern void *Ring_remhi (T ring);            /* Remove from high end */
extern void *Ring_remlo (T ring);            /* Remove from low end */

/* Rotation */
extern void  Ring_rotate(T ring, int n);     /* Positive = rotate left */

#undef T
#endif

3.2 Functional Requirements

1. Ring_new(hint): Create a new ring with initial capacity hint (or default if hint <= 0)
2. Ring_ring(x, …): Create a ring initialized with NULL-terminated variadic arguments
3. Ring_free(&ring): Deallocate ring and set pointer to NULL
4. Ring_length(ring): Return number of elements currently in ring
5. Ring_get(ring, i): Get element at logical index i (0-based from head)
6. Ring_put(ring, i, x): Replace element at index i, return old value
7. Ring_addhi(ring, x): Add element at tail, return x (or NULL if full)
8. Ring_addlo(ring, x): Add element at head, return x (or NULL if full)
9. Ring_remhi(ring): Remove and return element from tail (or NULL if empty)
10. Ring_remlo(ring): Remove and return element from head (or NULL if empty)
11. Ring_rotate(ring, n): Rotate elements by n positions (positive = left)

3.3 Non-Functional Requirements

1. O(1) operations: All add/remove operations must be constant time
2. Fixed capacity: Ring has bounded size, no automatic growth
3. Memory safety: Use Mem module for allocation, Assert for preconditions
4. Clear overflow/underflow: Return NULL (not crash) when ring is full/empty
5. Portable: No platform-specific code, standard C only

3.4 Example Usage / Output

# Build ring module test
$ make ring_test

# Test 1: Basic ring operations
$ ./ring_test basic
Ring created with capacity 8
Added: A B C D E
Ring contents (head to tail): [A, B, C, D, E, _, _, _]
Ring length: 5, capacity: 8

Removed from head: A
Removed from tail: E
Ring contents: [B, C, D, _, _, _, _, _]

Added: F G H I
Ring FULL - cannot add more
Ring contents: [B, C, D, F, G, H, I, _]
Wait, that's 7 elements... Ring reports: length=7, capacity=8

# Test 2: Rotation operations
$ ./ring_test rotation
Ring: [1, 2, 3, 4, 5]
Rotate left by 2: [3, 4, 5, 1, 2]
Rotate right by 1: [2, 3, 4, 5, 1]

# Test 3: Audio buffer simulation
$ ./ring_test audio
Simulating audio buffer (1024 samples, 44100 Hz)
Producer writes 256 samples... OK
Consumer reads 128 samples... OK
Buffer level: 128/1024 (12.5%)
Producer writes 512 samples... OK
Consumer reads 512 samples... OK
Buffer level: 128/1024 (12.5%)
Underrun test: Consumer tries to read 256...
UNDERRUN! Only 128 samples available

# Test 4: Keyboard buffer simulation
$ ./ring_test keyboard
Simulating keyboard buffer (capacity 16)
Type simulation: "Hello World"
Keystrokes buffered: 11
Reading all keystrokes: H-e-l-l-o- -W-o-r-l-d
Buffer empty

Overflow test: Typing 20 characters into 16-slot buffer...
First 16 buffered, last 4 dropped
This simulates the classic keyboard buffer overflow behavior

---

4. Solution Architecture

4.1 High-Level Design

Ring Module Architecture
--------------------------------------------------------------------------------

                    ┌─────────────────────────────────────┐
                    │           ring.h (Interface)          │
                    │                                       │
                    │  Ring_T ─────► opaque pointer         │
                    │  Ring_new, Ring_free                  │
                    │  Ring_addhi, Ring_addlo               │
                    │  Ring_remhi, Ring_remlo               │
                    │  Ring_get, Ring_put                   │
                    │  Ring_rotate                          │
                    └─────────────────┬─────────────────────┘
                                      │
                    ┌─────────────────┴─────────────────────┐
                    │          ring.c (Implementation)       │
                    │                                       │
                    │  struct Ring_T {                      │
                    │      int head;      // Read position  │
                    │      int length;    // Element count  │
                    │      int size;      // Capacity       │
                    │      void **ring;   // Element array  │
                    │  }                                    │
                    │                                       │
                    │  Index calculation:                   │
                    │  physical = (head + logical) % size   │
                    │                                       │
                    └───────────────────────────────────────┘
                                      │
                    ┌─────────────────┴─────────────────────┐
                    │              Dependencies             │
                    │                                       │
                    │  mem.h ─────► ALLOC, FREE, RESIZE     │
                    │  assert.h ──► precondition checks     │
                    └───────────────────────────────────────┘

4.2 Key Components

Header File (ring.h):

• Type definition (opaque pointer)
• Function declarations
• Include guards

Implementation File (ring.c):

• Private struct definition
• Index mapping functions
• Memory management via Mem module

4.3 Data Structures

// Internal representation
struct Ring_T {
    int head;       // Index of first element
    int length;     // Number of elements currently stored
    int size;       // Total capacity
    void **ring;    // Array of void* pointers to elements
};

// Index mapping:
// Logical index i (0 = first element) maps to:
// physical_index = (head + i) % size

// Example with size=8, head=6, length=4:
//
// Physical array:  [_, _, _, _, _, _, A, B]  [C, D, _, _, _, _, _, _]
//                   0  1  2  3  4  5  6  7    (wraps)
//                                     ^head
//
// Logical view:    [A, B, C, D]
//                   0  1  2  3
//
// Mapping:
//   logical 0 → (6 + 0) % 8 = 6 → A
//   logical 1 → (6 + 1) % 8 = 7 → B
//   logical 2 → (6 + 2) % 8 = 0 → C
//   logical 3 → (6 + 3) % 8 = 1 → D

4.4 Algorithm Overview

Adding to Tail (addhi):

1. Check if full (length == size) → return NULL
2. Calculate tail position: (head + length) % size
3. Store element at tail position
4. Increment length
5. Return the element

Adding to Head (addlo):

1. Check if full (length == size) → return NULL
2. Decrement head (with wrap): head = (head - 1 + size) % size
3. Store element at new head position
4. Increment length
5. Return the element

Removing from Head (remlo):

1. Check if empty (length == 0) → return NULL
2. Get element at head position
3. Increment head (with wrap): head = (head + 1) % size
4. Decrement length
5. Return the element

Removing from Tail (remhi):

1. Check if empty (length == 0) → return NULL
2. Calculate tail: (head + length - 1) % size
3. Get element at tail position
4. Decrement length
5. Return the element

Rotation:

Rotate by n positions (positive = left):
1. Normalize n to range [0, length): n = ((n % length) + length) % length
2. Adjust head: head = (head + n) % size
3. No elements moved! Just the logical view changes

---

5. Implementation Guide

5.1 Development Environment Setup

# Required tools
gcc --version          # GCC 9+ recommended
make --version         # GNU Make
valgrind --version     # Memory debugging (Linux)

# Project structure
C_INTERFACES_AND_IMPLEMENTATIONS_MASTERY/
├── include/
│   ├── ring.h         # Your interface
│   ├── mem.h          # Memory module (from Project 2)
│   └── assert.h       # Assert module (from Project 1)
├── src/
│   ├── ring.c         # Your implementation
│   ├── mem.c
│   └── assert.c
├── tests/
│   └── ring_test.c    # Test program
└── Makefile

# Compiler flags
CFLAGS = -Wall -Wextra -Wpedantic -std=c11 -g
CFLAGS += -fsanitize=address,undefined  # For debugging

5.2 Project Structure

ring.h          Interface (public API)
ring.c          Implementation (private details)
ring_test.c     Comprehensive test suite

5.3 The Core Question You’re Answering

“How do you create a bounded buffer that provides O(1) operations at both ends while preventing overflow and underflow?”

This question is fundamental to:

• Real-time systems where memory allocation is forbidden
• Producer-consumer patterns with different rates
• Fixed-memory embedded systems
• Performance-critical data paths (audio, network)

5.4 Concepts You Must Understand First

Before implementing, ensure you can answer:

1. Modular arithmetic: What is (7 + 3) % 8? What about (-1 + 8) % 8?
2. Head/tail pointers: In a ring buffer, what does “head” track? What does “tail” track?
3. The full/empty problem: Why is head == tail ambiguous?
4. Logical vs physical indexing: If head=6, size=8, where is logical index 3?

5.5 Questions to Guide Your Design

1. Capacity: Should capacity be power-of-2 for fast modulo (bitwise AND)?
2. Empty slot: Do you waste one slot to distinguish full from empty, or track count?
3. Growth: Should Ring ever grow, or is fixed-size fundamental to its contract?
4. Iteration: How do you iterate from head to tail correctly?
5. NULL handling: Is NULL a valid element, or reserved for error signaling?

5.6 Thinking Exercise

Draw the ring buffer state after these operations on a capacity-4 ring:

Initial: head=0, length=0, size=4
         [_, _, _, _]

Operations:
1. addhi(A)  →  head=?, length=?, contents=?
2. addhi(B)  →  head=?, length=?, contents=?
3. addhi(C)  →  head=?, length=?, contents=?
4. remlo()   →  returns=?, head=?, length=?, contents=?
5. addhi(D)  →  head=?, length=?, contents=?
6. addhi(E)  →  head=?, length=?, contents=?
7. remlo()   →  returns=?, head=?, length=?, contents=?
8. addlo(X)  →  head=?, length=?, contents=?

Track head, length, and physical array contents at each step. Where does wrap-around occur?

Click to see solution

``` 1. addhi(A): head=0, length=1, [A, _, _, _] 2. addhi(B): head=0, length=2, [A, B, _, _] 3. addhi(C): head=0, length=3, [A, B, C, _] 4. remlo(): returns A, head=1, length=2, [_, B, C, _] 5. addhi(D): head=1, length=3, [_, B, C, D] 6. addhi(E): head=1, length=4, [E, B, C, D] ← WRAP! E at index 0 7. remlo(): returns B, head=2, length=3, [E, _, C, D] 8. addlo(X): head=1, length=4, [E, X, C, D] ← X inserted, head moved back Final logical view: [X, C, D, E] ```

5.7 Hints in Layers

Hint 1 - Starting Point (Conceptual Direction):

Start with head, length, and size as your state. The length variable solves the full/empty ambiguity directly - no need to waste a slot or use flags.

Your struct needs:

• head: Index where the first element lives
• length: How many elements currently stored
• size: Total capacity of the buffer
• ring: Pointer to the element array

Hint 2 - Next Level (More Specific Guidance):

For add_tail (addhi):

1. Check: if length == size, return NULL (full)
2. Calculate tail position: (head + length) % size
3. Store at that position: ring[tail] = x
4. Increment length
5. Return x

For remove_head (remlo):

1. Check: if length == 0, return NULL (empty)
2. Get element: x = ring[head]
3. Advance head: head = (head + 1) % size
4. Decrement length
5. Return x

Hint 3 - Technical Details (Approach/Pseudocode):

The tricky operation is add_head (addlo) - you need to move head backwards:

void *Ring_addlo(Ring_T ring, void *x) {
    assert(ring);
    if (ring->length == ring->size)
        return NULL;  // Full

    // Move head backwards (with wrap-around)
    ring->head = (ring->head - 1 + ring->size) % ring->size;

    // Store at new head position
    ring->ring[ring->head] = x;
    ring->length++;

    return x;
}

Note: (head - 1 + size) % size handles the negative modulo correctly in C.

Hint 4 - Tools/Debugging (Verification Methods):

Rotation is elegantly simple with this representation - just adjust head:

void Ring_rotate(Ring_T ring, int n) {
    assert(ring);
    if (ring->length == 0)
        return;

    // Normalize n to [0, length)
    n = n % ring->length;
    if (n < 0)
        n += ring->length;

    // Adjust head - this is all the "rotation" we need!
    ring->head = (ring->head + n) % ring->size;
}

No element copying needed! The logical view changes, but physical memory is unchanged.

5.8 The Interview Questions They’ll Ask

1. “Implement a circular buffer for a real-time audio system. What’s your overflow strategy?”

   Expected Strong Answer: I’d implement a ring buffer with explicit full detection. For audio, there are typically three overflow strategies: (1) drop new samples (lose newest data), (2) overwrite oldest samples (lose oldest data), or (3) block/signal the producer. For real-time audio, strategy 2 is often preferred because slightly stale audio is better than silence, but this depends on the application. The key is making the overflow behavior explicit in the API and documenting it clearly.

2. “How would you implement a ring buffer that’s lock-free for single producer, single consumer?”

   Expected Strong Answer: For SPSC, I’d use atomic operations on head and tail indices. The producer owns tail, the consumer owns head. Key insight: producer reads head (to check if full) but only writes tail. Consumer reads tail (to check if empty) but only writes head. With proper memory ordering (acquire on reads, release on writes), no locks are needed. The “wasted slot” approach is cleaner here because both threads can check fullness/emptiness independently.

3. “What’s the difference between a ring buffer and a deque? When would you choose each?”

   Expected Strong Answer: A deque (like Hanson’s Seq) grows dynamically while a ring buffer has fixed capacity. Choose ring buffer when: (1) memory is constrained, (2) allocation is forbidden (real-time, embedded), (3) you want predictable overflow behavior, or (4) for producer-consumer patterns. Choose deque when: you don’t know the maximum size in advance and occasional reallocation is acceptable.

4. “How do you distinguish between a full and empty ring buffer without wasting space?”

   Expected Strong Answer: Three approaches: (1) Track count separately - adds one integer but simplifies logic. (2) Keep a flag indicating whether last operation was read or write - if head==tail and last was write, it’s full. (3) For SPSC lock-free buffers, some implementations keep indices as ever-incrementing values and check (write - read) == capacity for full, write == read for empty. I prefer the count approach for clarity unless optimizing for specific use cases.

5. “Design a bounded queue for a keyboard driver. What happens on overflow?”

   Expected Strong Answer: Keyboard buffers typically use ring buffers with a “drop new” overflow policy - if you type faster than the system processes keystrokes, the newest keystrokes are lost and often accompanied by an audible beep. The buffer is usually 16-32 characters. For a keyboard driver, I’d assert on NULL returns rather than silently dropping, or better, return an error code that the higher layer can use to signal the overflow (the classic PC beep).

5.9 Books That Will Help

Topic	Book	Chapter
Ring implementation	“C Interfaces and Implementations” by Hanson	Ch. 12
Circular buffer theory	“Algorithms in C” by Sedgewick	Queues section
Lock-free rings	“C++ Concurrency in Action” by Williams	Ch. 7 (concepts apply to C)
Real-time audio	“Audio Programming Book” by Boulanger & Lazzarini	Buffer management chapters
Embedded systems	“Making Embedded Systems” by White	Memory management

5.10 Implementation Phases

Phase 1: Basic Structure (Day 1)

• Define struct Ring_T
• Implement Ring_new and Ring_free
• Implement Ring_length
• Write basic tests

Phase 2: Core Operations (Day 2)

• Implement Ring_addhi and Ring_remhi
• Implement Ring_addlo and Ring_remlo
• Test wrap-around behavior thoroughly

Phase 3: Access Functions (Day 3)

• Implement Ring_get and Ring_put
• Handle index bounds checking
• Test random access patterns

Phase 4: Advanced Features (Day 4)

• Implement Ring_rotate
• Implement Ring_ring (varargs constructor)
• Stress test with many operations

Phase 5: Integration (Day 5)

• Audio buffer simulation test
• Keyboard buffer simulation test
• Memory leak testing with Valgrind
• Performance benchmarking

5.11 Key Implementation Decisions

1. Index Type: Use int for simplicity, but document the maximum capacity (~2 billion)

2. NULL as Error vs Valid Element: Design decision - if NULL can be a valid element, you need a different error signaling mechanism (out parameter, or exception via Except module)

3. Power-of-2 Optimization: Consider requiring power-of-2 sizes to use & (size-1) instead of %

4. Growth Policy: Hanson’s Ring is fixed-size. If you want growth, that’s a different data structure (more like Seq)

---

6. Testing Strategy

Unit Tests

// test_ring_basic.c

void test_create_destroy(void) {
    Ring_T r = Ring_new(10);
    assert(r != NULL);
    assert(Ring_length(r) == 0);
    Ring_free(&r);
    assert(r == NULL);
    printf("test_create_destroy: PASSED\n");
}

void test_add_remove_hi(void) {
    Ring_T r = Ring_new(4);

    assert(Ring_addhi(r, "A") == "A");
    assert(Ring_addhi(r, "B") == "B");
    assert(Ring_length(r) == 2);

    assert(Ring_remhi(r) == "B");
    assert(Ring_remhi(r) == "A");
    assert(Ring_length(r) == 0);

    Ring_free(&r);
    printf("test_add_remove_hi: PASSED\n");
}

void test_wrap_around(void) {
    Ring_T r = Ring_new(4);

    // Fill buffer
    Ring_addhi(r, "1");
    Ring_addhi(r, "2");
    Ring_addhi(r, "3");
    Ring_addhi(r, "4");

    // Remove from front
    assert(Ring_remlo(r) == "1");
    assert(Ring_remlo(r) == "2");

    // Add more - should wrap
    assert(Ring_addhi(r, "5") == "5");
    assert(Ring_addhi(r, "6") == "6");

    // Verify order
    assert(Ring_remlo(r) == "3");
    assert(Ring_remlo(r) == "4");
    assert(Ring_remlo(r) == "5");
    assert(Ring_remlo(r) == "6");

    Ring_free(&r);
    printf("test_wrap_around: PASSED\n");
}

Edge Case Tests

void test_full_buffer(void) {
    Ring_T r = Ring_new(3);

    assert(Ring_addhi(r, "A") == "A");
    assert(Ring_addhi(r, "B") == "B");
    assert(Ring_addhi(r, "C") == "C");
    assert(Ring_addhi(r, "D") == NULL);  // Full!

    assert(Ring_length(r) == 3);

    Ring_free(&r);
    printf("test_full_buffer: PASSED\n");
}

void test_empty_buffer(void) {
    Ring_T r = Ring_new(3);

    assert(Ring_remhi(r) == NULL);  // Empty!
    assert(Ring_remlo(r) == NULL);  // Still empty!

    Ring_addhi(r, "X");
    assert(Ring_remlo(r) == "X");
    assert(Ring_remlo(r) == NULL);  // Empty again!

    Ring_free(&r);
    printf("test_empty_buffer: PASSED\n");
}

void test_rotation(void) {
    Ring_T r = Ring_new(5);

    Ring_addhi(r, "1");
    Ring_addhi(r, "2");
    Ring_addhi(r, "3");
    Ring_addhi(r, "4");
    Ring_addhi(r, "5");

    // Rotate left by 2: [3,4,5,1,2]
    Ring_rotate(r, 2);
    assert(Ring_get(r, 0) == "3");
    assert(Ring_get(r, 4) == "2");

    // Rotate right by 1: [2,3,4,5,1]
    Ring_rotate(r, -1);
    assert(Ring_get(r, 0) == "2");

    Ring_free(&r);
    printf("test_rotation: PASSED\n");
}

Integration Tests

void test_audio_buffer_simulation(void) {
    // Simulate audio buffer: 1024 samples
    Ring_T audio = Ring_new(1024);
    int samples_written = 0;
    int samples_read = 0;

    // Producer writes 256 samples
    for (int i = 0; i < 256; i++) {
        void *sample = (void*)(intptr_t)(1000 + i);
        if (Ring_addhi(audio, sample))
            samples_written++;
    }
    assert(samples_written == 256);

    // Consumer reads 128 samples
    for (int i = 0; i < 128; i++) {
        if (Ring_remlo(audio))
            samples_read++;
    }
    assert(samples_read == 128);

    // Buffer level
    assert(Ring_length(audio) == 128);

    Ring_free(&audio);
    printf("test_audio_buffer_simulation: PASSED\n");
}

---

7. Common Pitfalls & Debugging

Problem 1: “Off-by-one errors on wrap-around”

• Symptom: Buffer appears to hold wrong elements after wrap
• Why: Confusing < vs <= or pre/post increment
• Fix: Always use modulo: index = (index + 1) % capacity
• Test: Verify add/remove at capacity boundary

Problem 2: “Ring appears full when empty (or vice versa)”

• Symptom: addhi returns NULL immediately after remlo
• Why: Not tracking count separately, or count not updated correctly
• Fix: Maintain explicit count variable, update it in every add/remove
• Test: Fill completely, empty completely, repeat multiple times

Problem 3: “Negative modulo gives wrong result”

• Symptom: head = (head - 1) % size gives negative number
• Why: C’s % operator can return negative for negative dividend
• Fix: Use (head - 1 + size) % size to ensure positive result
• Test: Test addlo when head is at position 0

Problem 4: “Ring_get returns wrong element”

• Symptom: Logical index 0 doesn’t return the first-added element
• Why: Not mapping logical index to physical correctly
• Fix: Physical index = (head + logical_index) % size
• Test: Add elements, verify Ring_get(0) returns first element

Problem 5: “Memory corruption after many operations”

• Symptom: Random crashes or wrong values after heavy use
• Why: Head or length not being updated atomically/consistently
• Fix: Ensure every operation updates all necessary fields
• Test: Run millions of random add/remove operations under Valgrind

---

8. Extensions & Challenges

After completing the basic implementation, try these extensions:

8.1 Lock-Free SPSC Ring Buffer

Implement a single-producer/single-consumer ring buffer using only atomic operations:

• Producer only writes to tail
• Consumer only writes to head
• Use memory barriers for correctness

8.2 Growing Ring Buffer

Add Ring_grow() that doubles capacity:

• Allocate new buffer
• Copy elements maintaining logical order
• Update head to 0, size to new_size
• Free old buffer

8.3 Peek Operations

Add Ring_peekhi() and Ring_peeklo() that return without removing.

8.4 Bulk Operations

Add Ring_addmany(ring, array, count) and Ring_remmany(ring, array, count) for efficient batch operations (useful for DMA transfers in embedded systems).

8.5 Iterator Support

Implement iteration that works even as elements are added/removed (snapshot or live iteration with defined behavior).

---

9. Real-World Connections

Audio Systems

ALSA (Linux Audio):

// Simplified ALSA ring buffer concept
struct snd_pcm_runtime {
    unsigned char *dma_area;     // Ring buffer
    snd_pcm_uframes_t buffer_size;
    snd_pcm_uframes_t hw_ptr;    // Hardware pointer (consumer)
    snd_pcm_uframes_t appl_ptr;  // Application pointer (producer)
};

Network Drivers

DPDK (Data Plane Development Kit):

// DPDK uses ring buffers extensively for zero-copy networking
struct rte_ring {
    int flags;
    uint32_t size;           // Size of ring
    uint32_t mask;           // size - 1 for fast modulo
    volatile uint32_t head;  // Producer head
    volatile uint32_t tail;  // Consumer tail
    void *ring[] __rte_cache_aligned;  // Element array
};

Logging Systems

Kernel Ring Buffer (dmesg):

// Linux kernel log buffer is a ring buffer
// Recent messages replace oldest when full
// This is why `dmesg` shows only recent kernel messages

---

10. Resources

Primary References

1. C Interfaces and Implementations by David Hanson, Chapter 12
   • Official CII source: https://github.com/drh/cii
2. The Art of Multiprocessor Programming by Herlihy & Shavit
   • Chapter on lock-free queues and ring buffers

Online Resources

1. Lock-Free Ring Buffer: https://www.codeproject.com/Articles/43510/Lock-Free-Single-Producer-Single-Consumer-Circular
2. DPDK Ring Documentation: https://doc.dpdk.org/guides/prog_guide/ring_lib.html
3. Linux Kernel Ring Buffer: https://www.kernel.org/doc/html/latest/core-api/circular-buffers.html

---

11. Self-Assessment Checklist

Before considering this project complete, verify:

• Ring_new creates buffer with correct capacity
• Ring_free deallocates all memory and sets pointer to NULL
• Ring_length returns correct count after various operations
• Ring_addhi adds at tail, returns element (or NULL if full)
• Ring_addlo adds at head, returns element (or NULL if full)
• Ring_remhi removes from tail, returns element (or NULL if empty)
• Ring_remlo removes from head, returns element (or NULL if empty)
• Wrap-around works correctly (test with capacity 2, 3, 4)
• Full buffer correctly detected
• Empty buffer correctly detected
• Ring_get returns correct element at logical index
• Ring_put replaces element and returns old value
• Ring_rotate adjusts logical view correctly
• No memory leaks (verified with Valgrind)
• No buffer overflows (verified with AddressSanitizer)
• All assertions fire on precondition violations

---

12. Submission / Completion Criteria

Your Ring module implementation is complete when:

1. All tests pass: Both your own tests and any provided test suite
2. Memory-safe: No leaks, no overflows, no undefined behavior
3. Documented: Header file has clear comments explaining each function
4. Follows CII conventions: Opaque type, Module_operation naming, checked runtime errors
5. Practical demonstration: Audio buffer or keyboard buffer simulation works correctly

Deliverables:

• ring.h - Interface with documentation
• ring.c - Implementation
• ring_test.c - Comprehensive test suite
• Makefile - Build configuration
• Brief writeup explaining your design decisions (especially: how you handle full/empty, why)