Circular buffer implementation using linked list

Question

I'm a beginner with C. The below is the implementation of circular buffer using linked list. Please review my code and suggest any improvements to make it efficient or to improve in coding style.

#include<stdio.h>
#include <stdlib.h>
struct link_list
{
 int item;
 struct link_list *next;
};
struct link_list *read=NULL;
struct link_list *write=NULL;
int size=NULL; //buffer size
static int p_size=0; //present size of buffer
void enqueue()
{
 int value;
 struct link_list *newnode=(struct link_list*)malloc(sizeof(struct link_list));
 printf("Enter new value : \n");
 scanf("%d",&value);
 newnode->item=value;
 newnode->next=NULL;
 if(read==NULL&&write==NULL)
 {
 read=write=newnode;
 p_size++;
 }
 else
 { 
 if (p_size<size)
 {
 printf("still buffer not filled\n");
 write->next=newnode;
 write=newnode;
 p_size++;
 }
 else
 {
 printf("size is exceeded\n");
 write=write->next;
 read->item=value;
 read=read->next;
 }
 write->next=read;
 }
 write->next=read;
}
void dequeue()
{
 int val;
 struct link_list *ptr=read;
 if(read==NULL)
 {
 printf("Stack is empty \n");
 }
 else
 {
 if (p_size>0)
 { 
 val=read->item;
 read=read->next;
 free(ptr);
 p_size--;
 printf("removed %d\n",val);
 }
 else 
 {
 p_size=0;
 read=write=NULL;
 printf("nothing else to remove\n");
 }
 } 
}
void print()
{
 printf("psize= %d\n",p_size);
 struct link_list *ptr=read;
 if (read==NULL)
 {
 printf("nothing in queue\n");return;
 }
 if (p_size==0) 
 {
 printf("stack empty\n");
 return;
 }
 else
 {
 while (ptr!=NULL)
 {
 if (ptr!=write)
 {
 printf("Value= %d Aderss= %p Next Address= %p\n", ptr->item,ptr, ptr->next);
 ptr=ptr->next;
 }
 else
 {
 printf("Value= %d Aderss= %p Next Address= %p\n", ptr->item,ptr, ptr->next);
 break;
 }
 }
 printf("read--@Value= %d Aderss= %p Next Address= %p\n", read->item,read, read->next);
 printf("write--@Value= %d Aderss= %p Next Address= %p\n", write->item,write, write->next);
 }
}
void main()
{
 char ch;
 int val;
 int loop=1;
 printf("enter the buffer size---\n");
 scanf("%d",&size);
 while(loop==1)
 {
 printf("select a) to add to queue, b) to dequeue s) sort p) print x)ext\n");
 scanf("%c",&ch);
 switch(ch)
 {
 case 'a':
 enqueue();
 break;
 case 'b':
 dequeue();
 break;
 case 'p':
 print();
 break;
 case 'x':
 loop=0;
 break;
 }
 }
}

• pacmaninbw: Welcome to code review, I hope you get some good answers.

Answer 1

Bug

When you dequeue the last element, this code will run with p_size being 1:

 if (p_size>0)
 { 
 val=read->item;
 read=read->next;
 free(ptr);
 p_size--;
 printf("removed %d\n",val);
 }

The result of this code is that the last element will be freed, but read and write will still be pointing at it, because the list was circular. Then the next time you call enqueue(), it will use those stale pointers to add to the list.

To fix this problem, you should clear the pointers to NULL when you dequeue the last element.

• shijuza: Thanks a lot for your comment. I did realize when enqueue() was called it was using stale pointers and not creating new ones. It was strange, I shall clear the pointers to NULL as you suggest. Also, did you see the else condition, it was written to handle the last element. Anything comments on this?
• JS1: @shijuza If you fix the case for size 1, then your size 0 case won't need to do anything.

Answer 2

Memory Leak

When calling enqueue() and the buffer is full (p_size==size), only the data part of the new element will replace the oldest element and allocated struct link_list is never freed.

Part 1 - The new node is allocated and initialized.

struct link_list *newnode=(struct link_list*)malloc(sizeof(struct link_list));
newnode->item=value;
newnode->next=NULL;

Part 2 - In the else-case of if (p_size<size), the newnode element is not used.

write=write->next;
// only the value entered is used
read->item=value;
read=read->next;

Solution 1 - the shortest way to solve that memory leak is to freed the unused 'newnode`.

The main problem for that solution and the previous implementation is the need to repeat the same initialization part as during Part 1. In the presented source code, the data structure attached to each node is very simple (int item;).

But in case of a more complex structure, bugs could appear due the code duplication.

write=write->next;
// only the value entered is used
read->item=value;
read=read->next;
free(newnode);

Solution 2 - a more powerful way to solve both memory leak and code duplication

1. The proposed solution doesn't access to the attached data;
2. The oldest node is extracted from the circular buffer;
3. The newest node is inserted into the circular buffer;
4. And delete the oldest node

No more memory leaks.

struct link_list *tmp;
// store the oldest node
tmp = queue_write->next;
// insert the new node in place of the oldest
queue_write->next = newnode;
newnode->next = tmp->next;
// rotate the circular buffer to the next node
queue_write = queue_write->next;
queue_read=queue_read->next;
// free the oldest node
free(tmp);