Ring Buffer Project

by: burt rosenberg
at: university of miami
date: sep 2015

NAME
    ringbuffer -- implement the ring buffer "interface" and test
    
SYNOPSIS
    ringbuffer [-v] [-s _size_] _commands_
		
DESCRIPTION

    Creates a ring buffer of characters of size _size_ and applies the 
    enqueue/dequeue commands from string _commands_. The _commands_ string 
    is understood as follows: 
	
    For each character c in _commands_, in order, either:
        * enqueue the character c or
        * if c is the hyphen character, dequeue a character
          from the ring buffer

	After each command the program writes either "deq: _X_" or "enq: _X_" to 
	standard out, where _X_ is either the character enqueued or dequeued, or the
	words "empty" or "full", according to the result of dequeue or enqueue.
	
    The following options are available:
    
    -v verbose output
    -s ring buffer size. Default is 8.

HISTORY
    Introduced in csc421.161 to prepare for the in-kernel ring buffer 
    introduced in csc421.151.
    
BUGS
    
    

Goals

• To write a ring buffer, reviewing the C concepts of struct, malloc and free.
• To review the use of header files, and data structures defined by an API.

Specific steps

1. Check-out class/csc421.161 from svn.cs.miami.edu.
2. Copy class/proj2 to [yourdirectory]/proj2; add and commit as "initial commit".
3. Implement the body of all functions in the ringbuffer.c file.
4. Test against the ringbuffer.ref until you get correct behavoir.
5. Consider additional tests that may be run, making further improvements to ringbuffer.c if necessary.
6. Commit for a grade by the due date.

Discussion

You have been provided with the structure "struct RingBuffer". This fields in this structure will be used to implement a ring buffer according the algorithm given here.

• The rb_create routine takes the size of the ring buffer from its arguments. It should then:
  1. malloc a struct RingBuffer
  2. malloc a buffer and place the pointer in the buffer field in the ring buffer struct
  3. place the size in the size field in the ring buffer struct
  4. initialize the other fields in the ring buffer struct to zero
  5. return a pointer to the ring buffer struct
  If something goes wrong, return NULL.

• The integer value of next_in is the index in buffer to where the next character should be enqueued. If the ring buffer pointer is named rb, then this is

  	rb->buffer[rb->next_in].
  

  If the buffer is not full, place the character to enqueue at index next_in then increment next_in, taking it mod size to wrap around to the beginning of the buffer. The value returned is the value just enqueued.

  If the buffer is full, return -1, and do not enqueue the character, do not increment next_in.

• The integer value of next_out is the index in buffer from where the next character should be dequeued. If the ring buffer pointer is named rb, then this is

  	rb->buffer[rb->next_out].
  

  If the buffer is not empty, return the character at index next_out, then increment next_out, taking it mod size to wrap around to the beginning of the buffer.

  If the buffer is empty, return -1, and do not increment next_out.

• When next_in != next_out, the ring buffer is neither empty nor full. next_in gives the "empty space" ready to take a character; next_out gives the "full space" ready to provide a character.

• If next_in == next_out, the ring buffer might be empty or might be full. You need to keep track of which of the two situations is the case by maintaining is_full properly.

• Initially is_full is false (zero), because although next_in == next_out that is because there is nothing in the ring buffer.

• Set is_full true (to one) when an enqueue operation causes next_in to equal next_out.

• Set is_full false (to zero) whenever a character is dequeued — the buffer cannot be full if something has just been removed.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 08 sep 2015
update: 08 sep 2015