Ring Buffer
#include <stdio.h> #define MAX_ITEM 10 #define NEXT(index) (((index) + 1) % MAX_ITEM) #define PREV(index) (((index) + MAX_ITEM - 1) % MAX_ITEM) typedef struct { int head; int tail; int cnt; void* items[MAX_ITEM]; } RingBuffer; void Initialize(RingBuffer *ring) { int i; ring->head = MAX_ITEM - 1; ring->tail = 0; ring->cnt = 0; for (i = 0; i < MAX_ITEM; i++) ring->items[i] = NULL; } void AddHead(RingBuffer *ring, void *item) { if (ring->cnt == MAX_ITEM) { printf("Error: ring buffer is already full\n"); return; } ring->items[ring->head] = item; ring->head = PREV(ring->head); ring->cnt++; } void AddTail(RingBuffer *ring, void* item) { if (ring->cnt == MAX_ITEM) { printf("Error: ring buffer is already full\n"); return; } ring->items[ring->tail] = item; ring->tail = NEXT(ring->tail); ring->cnt++; } void* RemoveHead(RingBuffer *ring) { if (!ring->cnt) { printf("Error: ring buffer is empty\n"); return NULL; } void* temp; ring->head = NEXT(ring->head); temp = ring->items[ring->head]; ring->items[ring->head] = NULL; ring->cnt--; return temp; } void* RemoveTail(RingBuffer *ring) { if (!ring->cnt) { printf("Error: ring buffer is empty\n"); return NULL; } void* temp; ring->tail = PREV(ring->tail); temp = ring->items[ring->tail]; ring->items[ring->tail] = NULL; ring->cnt--; return temp; } int ItemCount(RingBuffer *ring) { return ring->cnt; } void* ItemAt(RingBuffer *ring, int index) { if (index >= MAX_ITEM || index < 0) { printf("Error: invalid index. Usage: 0 to %d\n", MAX_ITEM); return NULL; } if (index >= ring->cnt) { printf("Error: index %d has no user's data\n", index); return NULL; } int temp; temp = (ring->head + index + 1) % MAX_ITEM; return ring->items[temp]; } void MoveToBack(RingBuffer *ring, int index) { int k; k = ring->tail; while (k != index) { ring->items[k] = ring->items[PREV(k)]; k = PREV(k); } } void MoveToFront(RingBuffer *ring, int index) { while (NEXT(index) != ring->tail) { ring->items[index] = ring->items[NEXT(index)]; index = NEXT(index); } ring->items[index] = NULL; } void AddItemAt(RingBuffer *ring, void* item, int index) { if (index >= MAX_ITEM || index < 0) { printf("Error: invalid index. Usage: 0 to %d\n", MAX_ITEM); return; } if (ring->cnt == MAX_ITEM) { printf("Error: ring buffer is already full\n"); return; } if (index >= ring->cnt) { printf("Error: invalid operation, items should be contiguous in buffer\n"); return; } int temp; temp = (ring->head + index + 1) % MAX_ITEM; MoveToBack(ring, temp); ring->tail = NEXT(ring->tail); ring->items[temp] = item; ring->cnt++; } void* RemoveItemAt(RingBuffer *ring, void* item) { int p = NEXT(ring->head); while (p != ring->tail) { if (ring->items[p] == item) break; else p = NEXT(p); } if (p == ring->tail) { printf("Error: can't find item\n"); return NULL; } void* temp; temp = ring->items[p]; MoveToFront(ring, p); ring->tail = PREV(ring->tail); ring->cnt--; return temp; } void PrintItem(RingBuffer *ring) { int i; for (i = 1; i <= ring->cnt; i++) printf("%d ", *(int*)ring->items[(ring->head + i) % MAX_ITEM]); printf("\n"); } int main() { int a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8; RingBuffer rb; Initialize(&rb); PrintItem(&rb); AddTail(&rb, (void*)&a); PrintItem(&rb); AddTail(&rb, (void*)&b); PrintItem(&rb); AddHead(&rb, (void*)&c); PrintItem(&rb); AddHead(&rb, (void*)&d); PrintItem(&rb); RemoveTail(&rb); PrintItem(&rb); RemoveTail(&rb); PrintItem(&rb); RemoveTail(&rb); PrintItem(&rb); AddTail(&rb, (void*)&e); PrintItem(&rb); AddTail(&rb, (void*)&f); PrintItem(&rb); AddItemAt(&rb, (void*)&g, 1); PrintItem(&rb); RemoveItemAt(&rb, (void*)&e); PrintItem(&rb); AddHead(&rb, (void*)&h); PrintItem(&rb); }
page revision: 0, last edited: 29 Apr 2010 07:19