0

This is a function for doubling the circular queue capacity in C
(https://i.stack.imgur.com/xxhah.jpg)
Code source : Fundamentals of data structures in C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int key;
} element;

element *queue;
void addq(element);
element deleteq(void);
void queueFull(void);
void displayq(void);
int capacity = 1;
int f, r;

void main() {
  element e, temp;
  int choice, done = 0;
  f = 0;
  r = 0;
  while (!done) {
    printf("1.Insert\t2.Delete\t3.Display\t4.Exit\n");
    printf("Enter choice");
    scanf("%d", &choice);
    switch (choice) {
      case 1:
        printf("Enter element");
        scanf("%d", &e.key);
        addq(e);
        break;
      case 2:
        temp = deleteq();
        if (temp.key == -1)
          printf("Queue Underflow\n");
        else
          printf("Queue element deleted : %d\n", temp.key);
        break;
      case 3:
        displayq();
        break;
      case 4:
        done = 1;
        break;
      default:
        printf("Illegal Entry\n");
        break;
    }
  }
}

void addq(element e) {
  if (f == (r + 1) % capacity)
    queueFull();
  r = (r + 1) % capacity;
  queue[r] = e;
}

void queueFull() {
  int start;
  element *newQueue;
  newQueue = (element*) malloc(2 * capacity * sizeof(queue));
  /*Copy from queue to newQueue*/
  start = (f + 1) % capacity;
  if (start < 2)
    /*No wrap around*/
    copy(queue + start, queue + start + capacity - 1, newQueue);
  else {
    copy(queue + start, queue + capacity, newQueue);
    copy(queue + start, queue + r + 1, newQueue + capacity - start);
  }
  /*Switch to newqueue*/
  f = 2 * capacity - 1;
  r = capacity - 1;
  capacity *= 2;
  free(queue);
  queue = newQueue;
}

element deleteq() {
  element temp;
  temp.key = -1;
  if (f == r)
    return temp;
  else {
    f = (f + 1) % capacity;
    temp = queue[f];
    return temp;
  }
}

void displayq() {
  int i;
  i = f;
  if (f == r)
    printf("Queue empty\n");
  else {
    while (i != r) {
      i = (i + 1) % capacity;
      printf("%d", queue[i].key);
    }
    printf("\n");
  }
}

When I compile the code, I get the error undefined reference to copy.

Does anyone know in which library this function exists? Or is there any other way around?

chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • 1
    The example you are basing this on was probably compiled as C++ (even though it looks like C). Just implement your own copy function using e.g. memmove. – Paul R Dec 15 '22 at 09:50
  • 1
    Start indenting your code properly. It's very hard to work with poorly indented code. – Jabberwocky Dec 15 '22 at 09:53
  • 1
    What is `copy` according to you? – Jabberwocky Dec 15 '22 at 09:54
  • What is this book of which you posted a picture? When has it been written? If it's older than 15 years or so, you should throw it away. – Jabberwocky Dec 15 '22 at 09:58
  • 1
    Say suppose copy(queue+start , queue+capacity , newQueue) , it copies the values pointing from queue+start to queue+capacity into new array named newQueue – Yoga Simha Vykuntam Dec 15 '22 at 09:59
  • 1
    It's from Fundamentals of data structures in C by Horowitz , Sahni , Anderson-Freed – Yoga Simha Vykuntam Dec 15 '22 at 10:00
  • 1
    The book is almost 30 years old, it's outdated and possibly older than you. Toss it away and read this: https://stackoverflow.com/questions/562303/the-definitive-c-book-guide-and-list – Jabberwocky Dec 15 '22 at 10:01
  • 1
    @PaulR `memcpy` would do since the source and destination do not overlap. – Ian Abbott Dec 15 '22 at 10:02
  • 1
    @IanAbbott: indeed, but if you’re going to write a copy function then you might as well make it robust for the general case. – Paul R Dec 15 '22 at 10:05
  • @YogaSimhaVykuntam I had a class led by Sartaj K Sahni, [BITD](https://en.wiktionary.org/wiki/BITD) - one of the best classes. I hope the poor liberal use of global variables was not something pick up with the book. – chux - Reinstate Monica Dec 15 '22 at 11:50
  • 1
    `newQueue = (element*) malloc(2 * capacity * sizeof(queue));` looks wrong as `sizeof(queue)` is the size of a _pointer_. Suggest `newQueue = malloc(2 * capacity * sizeof *newQueue);` – chux - Reinstate Monica Dec 15 '22 at 11:55
  • @chux-ReinstateMonica oh yeah! Thanks for reviewing , Could you be able to share the function for copy , I've been trying...I couldn't do it – Yoga Simha Vykuntam Dec 15 '22 at 12:25
  • @YogaSimhaVykuntam, "I've been trying" --> post that try for `copy(queue+start , queue+capacity , newQueue)` and perhaps example input and output. – chux - Reinstate Monica Dec 15 '22 at 18:06

0 Answers0