15.4 Circular Bu ers
A circular bu er, like an array or linked-list, contains a sequence of elements. The di erence is that this data-structure has fixed size and its end loops back to its beginning. Circular bu ers are usually implemented with either an array or a linked-list as the underlying representation. (In the latter case, the end-node points back to the head-node.) In this section, we describe an array-based implementation.
The basic form of a circular bu er is shown in Figure 15.1. The bu er is allocated a fixed amount of space, and may contain no more elements than this maximum. There are two indexes into the bu er marking the front and back, respectively. The front index points to the empty slot where the next element will be added. The back index points to the next element to be extracted. Thus, items are pushed onto the front of the bu er and removed from the back. After each addition or removal, the associated index is moved forward to the next position and, when an index reaches the end of the bu er, it is cycled around to the beginning, so that the bu er appears as a continuous loop. (This continuity is represented naturally by a linked-list, with the connection of the end-node back to the head-node being no di erent to any other link. However, for an array-based implementation, special wrap-around operations must be performed for the end of the array.)
Figure 15.1: Circular bu er. Items are added to the front and extracted from the back. The end of the bu er wraps around to the beginning to form a continuous loop.
Circular bu ers are very common in real-time and embedded systems where there are various processes that communicate with each other. One process is a producer and puts data into the bu er, and another is a consumer and removes data from the bu er. The bu er acts as temporary storage to allow both processes to operate asynchronously, with neither process having to wait for the other to complete a transaction.
For our array-based implementation, we define the circular bu er type as follows.
typedef struct CircBuf_t {
ValueType *array; /* Pointer to array of items. */
int size; /* Maximum number of items in buffer. */
int nelems; /* Current number of items in buffer. */
int front; /* Index to front of buffer. */
int back; /* Index to back of buffer. */
} CircBuf;
The public interface is exported in a header file, and provides operations to create and destroy a bu er, to add and extract items, and to get the current size and maximum size of the bu er. Notice that, once again, the structure CircBuf is an opaque type with its definition hidden within the private interface.
1 typedef double ValueType;
2 typedef struct CircBuf t CircBuf;
3
4 /* create-destroy bu?er */
5 CircBuf *create bu er(int size);
6 void destroy bu er(CircBuf *cb);
7
8 /* add-remove elements */
9 int add item(CircBuf *cb, const ValueType *item);
10 int get item(CircBuf *cb, ValueType *item);
11
12 /* query state */
13 int get nitems(const CircBuf *cb);
14 int get size(const CircBuf *cb);
The two functions below form the crux of the bu er data-structure—insertion and extraction.
Their implementation is straightforward, with the wrap-around code being the only subtlety.
1 int add item(CircBuf *cb, const ValueType *item)
2 /* Add a new element to front of bu?er.
3* Returns 0 for success, and -1 if bu?er is full. */
4 {
5if (cb->nelems == cb->size)
6 return -1;
7
8cb->array[cb->front] = *item;
9if (++cb->front == cb->size) /* wrap around */
10 cb->front = 0;
11 ++cb->nelems;
12 return 0;
13 }
14
15 int get item(CircBuf *cb, ValueType *item)
16 /* Remove element from back of bu?er, and assign it to *item.
17 * Returns 0 for success, and -1 if bu?er is empty. */
18 {
19 if (cb->nelems == 0)
20 return -1;
21
22 --cb->nelems;
23 *item = cb->array[cb->back];
24 if (++cb->back == cb->size) /* wrap around */
25 cb->back = 0;
26 return 0;
27 }
5–6 Check whether bu er is full. Circular bu ers generally deal with being full in one of two ways. First, as in this example, they might return a flag to indicate full status.2 A second option is to over-write existing items so that, for a bu er of size n, only the most recent n elements are retained. That is, when the bu er is full, the front index meets the back index. If another element is inserted, both indexes are incremented and the back item is lost.
9–10 When the front index reaches the end of the array, it must be reset to zero to point to the beginning of the array again. A common alternative to this comparison code is the following idiom, which uses the modulus operator to bound the index.
cb->front = (cb->front + 1) % cb->size; /* wrap around */
Aside. A common di culty with all the data-structure implementations presented in this chapter, and with algorithm design in general, is ensuring correct behaviour for boundary conditions. Bound-ary conditions occur at the extremities of normal algorithm operation. For example, the boundaries for a circular bu er occur when the bu er is full or empty, or when the indices wrap around. Care must be taken to avoid “o -by-one” indexing errors, and to make the appropriate choices of pre- or post-increment. Checking boundary conditions is an important technique for finding subtle bugs.
2 For a circular bu er connecting two concurrent processes (i.e., two processes that execute simultaneously), an implementation might not return a status flag, but instead might block the producer process until the consumer process has removed an element. Concurrent programming, concerned with multiple threads or processes, is beyond the scope of this text.
The idea is that most bugs occur at boundaries. If a piece of code is going to fail, it will likely fail at a boundary. Conversely, if it works at its boundaries, its likely to work elsewhere too [KP99, page 140].
15.5 Stacks
A stack, also known as a last-in-first-out (LIFO) bu er, is used to store items and then extract them in reverse order. The basic form is shown in Figure 15.2. The stack grows upwards as items are pushed onto the top, and shrinks back down as items are popped o the top. Stacks with fixed maximum size are usually implemented with a simple array. If a stack does not have a fixed maximum, it might be implemented using a dynamic representation such as our expandable vector.
Figure 15.2: Stack. Items are pushed onto the top of the stack and popped o the top in reverse order.
As an example implementation, consider the following data type for a stack with maximum size MAXSIZE.
typedef struct Stack {
double buffer[MAXSIZE]; /* Stack buffer. */
int count; /* Number of elements in stack. */
} Stack;
The code for pushing items onto the stack and popping them o is trivial. (We neglect bounds checking, for brevity.)
void push(Stack *s, double item) { s->buffer[s->count++] = item; } double pop(Stack *s) { return s->buffer[--s->count]; }
15.6 Queues
A queue, otherwise known as a first-in-first-out (FIFO) bu er, represents the other side of the coin to a stack. Where a stack pushes and pops items from the top (or front) of the bu er, a queue pushes items on at the front and pops them o at the back. Thus, a queue removes items in the same order as they were placed onto it.The basic form of a queue is shown in Figure 15.3. If a queue has fixed maximum size, it becomes equivalent to a circular bu er. Variable length queues are a little more complicated. That is, they are di cult to implement e ciently with an expandable vector, but are well suited to implementation with a singly linked-list. Another alternative is to use a deque, which is a linked-list of short arrays and provides certain e ciency advantages of both arrays and lists.
The following implementation demonstrates a fixed size queue, which is a simple wrapper of the circular bu er described above. Once again, we neglect error checking for the sake of brevity, but the basic operations are clear.
typedef CircBuf Queue;
void push(Queue *q, ValueType item) { add_item(q, &item); } ValueType pop(Queue *q) { ValueType v; get_item(q, &v); return v; }
Figure 15.3: Queue. Items are pushed onto the queue from the front and popped o from the back. Thus, items are extracted in the same order as they were inserted.
No comments:
Post a Comment