Circular buffer

Circular buffer is a queueing mechanism with the help of a fixed size array often used in low memory footprint systems and device drivers. Circular buffer can be implemented with static array or fixed size dynamic array. It never calls any dynamic memory allocation routines like alloc/free/resize during runtime. It manages addition and deletion of queue elements in a circular rotational fashion.

Mechanism and Implementation

It has a fixed size array to hold elements. It has two memebrs called start and end to pint the index in the array to determine front and back of the queue. It also has the size memeber to save element count. At the beggining we set start and end both to zero index. End will increment as new elements gets added and start will be incremented when a oldet elemnt gets removed. Thse increments are circular and never crosses beyond max array index. They rounded off to the starting as we do a modulo. Now end may get back to start when buffer is entirely full. So start and end will point to same index when buffer is either full or empty. We often use a count to distinguish empty and full situation.

Advantages

  1. Simple logic using array and no complex data structures and logic used
  2. No dynamic allocation or deallocation and no chance of memory leak and other issues
  3. Best suit for low memory footprint systems or for device drivers
  4. Very fast operations and donot include delay of malloc and free
  5. These can be used in applications as well as low level codes in interrupt handlers and realtime systems

Limitations

  1. Queue is fixed fixed size and this cannot be changed
  2. addition of new element will overwrite old queue elements or has to wait till some elements are free

Source Code

#include<stdio.h>
#include<malloc.h>
#include<memory.h>
typedef struct sbuff_{
    int * buff;
    int start;
    int end;
10      int size;
11      int count;
12  } sbuff_t;
13 
14  sbuff_t * sbuff_new(int size)
15  {
16    sbuff_t * sb = (sbuff_t*)malloc(sizeof(sbuff_t));
17    memset(sb, 0, sizeof(sbuff_t));
18    sb->size = size;
19      sb->buff = (int*)malloc(sizeof(int)*size);
20    
21    return sb;
22  }
23  void sbuff_add(sbuff_t * sb, int elem)
24  {
25    int end = sb->end;
26    if(sb->count && (end % sb->size) == sb->start){
27      printf("Overflow Elem[%d] %d lost\n", sb->start, sb->buff[sb->start]);
28      sb->start = (sb->start + 1 ) %sb->size;
29      sb->count --;
30    }
31    printf("Added Elem[%d] = %d\n",sb->end, elem);
32    sb->buff[sb->end] = elem;
33    sb->end = (sb->end+1) % sb->size;
34    sb->count ++;
35    }
36 
37  }
38  int sbuff_remove(sbuff_t * sb)
39  {
40    int start = sb->start ;
41    int ret = -1;
42    if(sb->count <= 0) {
43      printf("Buffer is empty\n");
44      return ret;
45    }
46    if(sb->count || (start % sb->size) != sb->end) {
47      printf("Removed Elem[%d] = %d\n",sb->start, sb->buff[sb->start]);
48      ret = sb->buff[sb->start];
49      sb->start = (sb->start + 1 ) % sb->size;
50      sb->count--;
51    } else {
52      printf("Buffer is empty\n");
53    }
54    return ret;
55  }
56  void sbuff_print(sbuff_t * sb)
57  {
58    int start = sb->start ;
59    int end = sb->end ;
60    int i, count = 0;
61    for(= start; count < sb->count; i = (i + 1)%sb->size){
62      printf("Elem[%d] = %d\n", i, sb->buff[i]);
63      count++;
64      if(== (end - 1)) {
65        break;
66      }
67    }
68  }
69  void sbuff_delete(sbuff_t * sb)
70  {
71    free(sb->buff);
72    free(sb);
73  }
74  int main(int argc, char *argv[])
75  {
76    char key;
77    int elem;
78    sbuff_t * sb = sbuff_new(5);
79    while(1) {
80      printf("circular buffer add[a], remove[r], print[p] : ");
81      fflush(stdin);
82      key = getchar();
83      switch(key){
84        case 'a':
85        {
86          printf("Element to add : ");
87          scanf("%d", &elem);
88          sbuff_add(sb, elem);
89          break;
90        }
91        case 'r':
92        {
93          sbuff_remove(sb);
94          break;
95        }
96        case 'p':
97        {
98          sbuff_print(sb);
99          break;
100        }
101        default:
102        {
103          sbuff_delete(sb);
104          exit(0);
105        }
106      }
107    }
108    return 0;
109  }

Output

circular buffer add[a], remove[r], print[p] : r
Buffer is empty
circular buffer add[a], remove[r], print[p] : a
Element to add : 1
Added Elem[0] = 1
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 1
circular buffer add[a], remove[r], print[p] : a
Element to add : 2
Added Elem[1] = 2
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 1
Elem[1] = 2
circular buffer add[a], remove[r], print[p] : a
Element to add : 3
Added Elem[2] = 3
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 1
Elem[1] = 2
Elem[2] = 3
circular buffer add[a], remove[r], print[p] : a
Element to add : 4
Added Elem[3] = 4
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 1
Elem[1] = 2
Elem[2] = 3
Elem[3] = 4
circular buffer add[a], remove[r], print[p] : a
Element to add : 5
Added Elem[4] = 5
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 1
Elem[1] = 2
Elem[2] = 3
Elem[3] = 4
Elem[4] = 5
circular buffer add[a], remove[r], print[p] : a
Element to add : 6
Overflow Elem[0] 1 lost
Added Elem[0] = 6
circular buffer add[a], remove[r], print[p] : p
Elem[1] = 2
Elem[2] = 3
Elem[3] = 4
Elem[4] = 5
Elem[0] = 6
circular buffer add[a], remove[r], print[p] : r
Removed Elem[1] = 2
circular buffer add[a], remove[r], print[p] : p
Elem[2] = 3
Elem[3] = 4
Elem[4] = 5
Elem[0] = 6
circular buffer add[a], remove[r], print[p] : r
Removed Elem[2] = 3
circular buffer add[a], remove[r], print[p] : p
Elem[3] = 4
Elem[4] = 5
Elem[0] = 6
circular buffer add[a], remove[r], print[p] : r
Removed Elem[3] = 4
circular buffer add[a], remove[r], print[p] : p
Elem[4] = 5
Elem[0] = 6
circular buffer add[a], remove[r], print[p] : r
Removed Elem[4] = 5
circular buffer add[a], remove[r], print[p] : p
Elem[0] = 6
circular buffer add[a], remove[r], print[p] : r
Removed Elem[0] = 6
circular buffer add[a], remove[r], print[p] : p
circular buffer add[a], remove[r], print[p] : r
Buffer is empty
circular buffer add[a], remove[r], print[p] :

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

2D and 3D dynamic array, add Matrix, multiply Matrix, adjacency Matrix, Circular buffer, char array and char pointers, const char *,char * const, const char * const, alpha numeric,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan