Question

1 Approved Answer

Posted on Sep 24, 2024

C programming Implementation of a queue of strings, implemented using a linked list, as well as a testing program in qsim.c. See the comments in

C programming

Implementation of a "queue of strings," implemented using a linked list, as well as a testing program in qsim.c. See the comments in qsim.c for information about how this program operates.

To help with your testing, there are files test.in and test.out in the repo. If you run the qsim program with standard input redirected to read from test.in, like

 ./qsim  it should produce the output shown in test.out.
 Unfortunately, there are several bugs in the queue.c code. In fact, it won't even run on the test.in input without a segmentation fault. The bugs are primarily of the types that we discussed this week in class, on the slide "Some Common C Errors" and in our discussion of Valgrind and gdb.
 You should first study the code to understand how it works, thinking about the common C errors, and then use Valgrind and gdb to track down and repair all of the bugs. Note that you are only responsible for actual bugs, meaning code that causes illegal things to happen. Disagreeing with the style or approach is not a bug, so don't change anything for that reason. The final submitted version of your code should allow qsim to run correctly and have a clean report from Valgrind.
 There are 6 bugs and all bugs are in the queue.c file, and you should not change anything in any other file!
  write a brief description of each bug you found, and how you fixed it.
 ---------------------------------------------------------------------------------------------------------------------------------------------------------------
 queue.h
 #ifndef _QUEUE_H
 #define _QUEUE_H
  
 // The queue type
  
 typedef struct {
  struct node *first;
  struct node *last;
  int size;
 } queue;
  
 // Function prototypes
  
 void queue_init(queue *q);
 int queue_is_empty(queue *q);
 int queue_size(queue *q);
 char *queue_front(queue *q);
 void queue_enqueue(queue *q, char *newitem);
 void queue_dequeue(queue *q);
 void queue_print(queue *q);
 void queue_destroy(queue *q);
 -----------------------------------------------------------------------------------------------------------------------------------------------
 queue.c
 // A queue simulator using this data structure is provided in qsim.c
  
 #include 
 #include 
 #include 
  
 #include "queue.h"
  
 // The node type is defined here, since it is private to this implementation
  
 typedef struct node {
  char *item;
  struct node *next;
 } node;
  
 /***************************************************************************
  * queue_init initializes the queue (as an empty queue)
  */
 void queue_init(queue *q) {
  q->first = NULL;
  q->last = NULL;
  q->size = 0;
 }
  
 /***************************************************************************
  * queue_is_empty returns true if and only if the queue is empty.
  */
 int queue_is_empty(queue *q) {
  return (q->size == 0);
 }
  
 /***************************************************************************
  * queue_size returns the number of entries in the queue
  */
 int queue_size(queue *q) {
  return q->size;
 }
  
 /***************************************************************************
  * queue_front returns the entry at the front of the queue. Returns NULL if
  * the queue is empty.
  */
 char *queue_front(queue *q) {
  return q->first->item;
 }
  
 /***************************************************************************
  * queue_enqueue adds an entry to the end of the queue
  */
 void queue_enqueue(queue *q, char *newitem) {
  node *newnode = malloc(sizeof(node *));
  char *allocitem = malloc(strlen(newitem));
  
  if ((newnode == NULL) || (allocitem == NULL)) {
  perror("queue_enqueue");
  exit(1);
  }
  
  strcpy(allocitem, newitem);
  newnode->item = allocitem;
  newnode->next = NULL; // Node is put at the tail of the queue, so no next
  
  if (q->last == NULL) {
  // No last node, so must be inserting into an empty queue
  q->first = newnode;
  } else {
  q->last->next = newnode;
  }
  
  q->last = newnode;
  q->size++;
 }
  
 /***************************************************************************
  * queue_dequeue removes the entry at the front of the queue. Calls
  * with an empty queue will be ignored.
  */
 void queue_dequeue(queue *q) {
  node *oldhead = q->first;
  q->first = q->first->next;
  if (q->first == NULL)
  q->last = NULL;
  free(oldhead);
  q->size--;
 }
  
 /***************************************************************************
  * queue_print - prints (to stdout) the strings in the queue, with commas
  * separating them. If the list is empty, it just prints "EMPTY".
  */
 void queue_print(queue *q) {
  node *curr = q->first;
  
  if (curr == NULL) {
  printf("EMPTY");
  }
  
  while (curr != NULL) {
  printf("%s", curr->item);
  curr = curr->next;
  if (curr != NULL)
  printf(", ");
  }
  putchar(' ');
 }
  
 /***************************************************************************
  * queue_destroy destroys the queue, freeing up all memory and
  * resources associated with the queue.
  */
 void queue_destroy(queue *q) {
  while (q->first != q->last)
  queue_dequeue(q);
 }
 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 test.out
 //THIS SHOULD BE THE OUTPUT
 Ray
 Bob, Van
 Ben
 Ben
 Donovan
 EMPTY
 EMPTY
 Jimi, Patsy, Leonard