Instructions
Requirements and Specifications
Screenshots of output
Source Code
#include
#include
#include
#include "leak_detector_c.h"
typedef struct failfish_st
{
int sequence;
struct failfish_st *prev;
struct failfish_st *next;
}failfish;
typedef struct
{
char *name;
int ni;
int ei;
int thi;
failfish *head;
failfish *tail;
}failfish_queue;
typedef struct pond_node_st
{
int n;
failfish_queue *queue;
struct pond_node_st *next;
}pond_node;
failfish *create_failfish(int sequence_number);
void destroy_failfish(failfish *fish);
failfish_queue *create_failfish_queue(char *pondname, int n, int e, int th);
void destroy_failfish_queue(failfish_queue *q);
void print_failfish_queue(failfish_queue *q, FILE *output);
pond_node *load_input(FILE *in);
void enqueue(failfish_queue *queue, failfish *fish);
failfish *dequeue(failfish_queue *queue);
failfish *peek(failfish_queue *queue);
int is_empty(failfish_queue *queue);
pond_node *create_pond(int n, failfish_queue *q);
int insert_pond(pond_node **list, int n, failfish_queue *q);
void destroy_ponds(pond_node *list);
void print_ponds(pond_node *list, FILE *output);
int main()
{
FILE *input, *output;
pond_node *ponds, *node, *nmax;
failfish_queue *pond, *qmax;
failfish *fish;
int i, totalfish;
/* open input file */
input = fopen("cop3502-as2-input.txt", "rt");
if (input == NULL)
{
fprintf(stderr, "Unable to open input file\n");
return 1;
}
/* open output file */
output = fopen("cop3502-as2-output.txt", "wt");
if (output == NULL)
{
fclose(output);
fprintf(stderr, "Unable to open output file\n");
return 1;
}
/* load queues into the ponds */
ponds = load_input(input);
if (ponds == NULL)
{
fprintf(stderr, "Error reading input file\n");
return 1;
}
fclose(input);
/* print initial ponds */
fprintf(output, "Initial Pond Status\n");
print_ponds(ponds, output);
fprintf(output, "\nFirst Course\n\n");
for (node = ponds; node != NULL; node = node->next)
{
pond = node->queue;
fprintf(output, "Pond %d: %s\n", node->n, pond->name);
/* repeat while number is above the threshold */
while (pond->ni > pond->thi)
{
for (i = 0; i < pond->ei - 1; i++) /* skip e-1 fishes */
{
fish = dequeue(pond); /* dequeue and enqueue to skip */
enqueue(pond, fish);
}
fish = dequeue(pond); /* last one is simply dequeued and freed */
fprintf(output, "Failfish %d eaten\n", fish->sequence);
destroy_failfish(fish);
}
fprintf(output, "\n");
}
/* put smallest sequence fish at head in all ponds */
totalfish = 0;
for (node = ponds; node != NULL; node = node->next)
{
pond = node->queue;
/* repeat while previous of head is smaller*/
while (peek(pond)->prev->sequence < peek(pond)->sequence)
{
fish = dequeue(pond); /* dequeue and enqueue to reorder */
enqueue(pond, fish);
}
totalfish += pond->ni;
}
/* print end ponds */
fprintf(output, "End of Course Pond Status\n");
print_ponds(ponds, output);
fprintf(output, "\nSecond Course\n\n");
while (totalfish > 1)
{
/* find the highest numbered failfish at the head of the pond queues */
for (nmax = NULL, node = ponds; node != NULL; node = node->next)
{
pond = node->queue;
if (!is_empty(pond))
{
if (nmax == NULL)
nmax = node;
else
{
qmax = nmax->queue;
if (peek(pond)->sequence > peek(qmax)->sequence /* if head is bigger than max */
|| (peek(pond)->sequence == peek(qmax)->sequence && pond->ni < qmax->ni)) /* if there's a tie, use smallest queue */
{
nmax = node; /* use current pond node as max */
}
}
}
}
fish = dequeue(nmax->queue); /* dequeue fish */
fprintf(output, "Eaten: Failfish %d from pond %d\n", fish->sequence, nmax->n);
destroy_failfish(fish);
totalfish--;
}
/* print remaining fish */
for (node = ponds; node != NULL; node = node->next)
{
pond = node->queue;
if (!is_empty(pond))
{
fprintf(output, "\nFailfish %d from pond %d remains\n", peek(pond)->sequence, node->n);
break;
}
}
/* free all memory used for queues */
destroy_ponds(ponds);
atexit(report_mem_leak);
return 0;
}
/* Loads the failfish queue information from the given file, makes a list of ponds and creates
the queues in the ponds, returns the list of ponds or NULL if there is an error */
pond_node *load_input(FILE *in)
{
failfish_queue *q;
pond_node *ponds;
char buffer[128];
int i, n;
int gi;
char name[100];
int ni;
int ei;
int thi;
ponds = NULL;
if (fgets(buffer, 128, in) == NULL) /* read number of failgroups */
return NULL;
if (sscanf(buffer, "%d", &n) != 1)
return NULL;
i = 0;
while (fgets(buffer, 128, in) != NULL) /* read number of failgroups */
{
if (buffer[0] == '\n' || buffer[0] == 0) /* ignore empty lines */
continue;
if (sscanf(buffer, "%d %s %d %d %d", &gi, name, &ni, &ei, &thi) != 5)
{
destroy_ponds(ponds);
return NULL;
}
if (gi < 1 || gi > 10 /* if not a valid pond */
|| ni < 2 || ni > 10000 /* if not a valid n */
|| ei < 1 || ei >= ni /* if not a valid ei */
|| thi < 1 || thi >= ni) /* if not a valid thi */
{
destroy_ponds(ponds);
return NULL;
}
q = create_failfish_queue(strdup(name), ni, ei, thi);
if (q == NULL)
{
destroy_ponds(ponds);
return NULL;
}
if (insert_pond(&ponds, gi, q) == 0) /* insert pond to the list */
{
destroy_ponds(ponds);
return NULL;
}
i++;
}
if (i < n)
{
destroy_ponds(ponds);
return NULL;
}
return ponds;
}
/* Creates a new failfish queue with the given arguments */
failfish_queue *create_failfish_queue(char *pondname, int n, int e, int th)
{
failfish_queue *fq;
failfish *fish;
int i;
fq = (failfish_queue *) malloc(sizeof(failfish_queue));
if (fq == NULL)
return NULL;
fq->name = pondname;
fq->ni = 0;
fq->ei = e;
fq->thi = th;
fq->head = NULL;
fq->tail = NULL;
for (i = 1; i <= n; i++)
{
fish = create_failfish(i);
enqueue(fq, fish);
}
return fq;
}
/* Deallocates all the memory used by the failfish queue */
void destroy_failfish_queue(failfish_queue *q)
{
if (q != NULL)
{
while (!is_empty(q))
destroy_failfish(dequeue(q));
if (q->name != NULL)
free(q->name);
free(q);
}
}
/* Creates a new failfish with the given sequence number */
failfish *create_failfish(int sequence_number)
{
failfish *fish;
fish = (failfish *) malloc(sizeof(failfish *));
if (fish == NULL)
return NULL;
fish->sequence = sequence_number;
fish->prev = NULL;
fish->next = NULL;
return fish;
}
/* Deallocates all the memory used by the failfish */
void destroy_failfish(failfish *fish)
{
if (fish != NULL)
free(fish);
}
/* prints the queue name and all the failfishes in the queue */
void print_failfish_queue(failfish_queue *q, FILE *output)
{
failfish *fish;
int i;
fprintf(output, "%s ", q->name);
fish = q->head;
for (i = 0; i < q->ni; i++)
{
fprintf(output, "%d ", fish->sequence);
fish = fish->next;
}
}
/* Adds a new failfish to the tail of the queue */
void enqueue(failfish_queue *queue, failfish *fish)
{
if (queue->ni == 0) /* if the queue was empty */
{
queue->head = fish; /* use same node for head and tail */
queue->tail = fish;
fish->next = fish; /* loop next and prev pointers */
fish->prev = fish;
}
else /* there are 1 or more nodes */
{
fish->prev = queue->tail; /* connect fish pointers */
fish->next = queue->tail->next;
queue->tail->next->prev = fish; /* correct tail pointers */
queue->tail->next = fish;
queue->tail = fish;
}
queue->ni++;
}
/* Removes a failfish from the front of the queue */
failfish *dequeue(failfish_queue *queue)
{
failfish *fish;
if (queue->ni == 0) /* if the queue is empty */
return NULL;
fish = queue->head;
if (queue->ni > 1)
{
queue->head->next->prev = queue->head->prev; /* remove node from queue */
queue->head->prev->next = queue->head->next;
queue->head = queue->head->next;
}
else
{
queue->head = NULL;
queue->tail = NULL;
}
queue->ni--;
return fish;
}
/* Returns the failfish at the head of the queue */
failfish *peek(failfish_queue *queue)
{
return queue->head;
}
/* Returns 1 if the queue is empty, 0 otherwise */
int is_empty(failfish_queue *queue)
{
if (queue == NULL)
return 1;
return (queue->ni == 0);
}
/* Creates a new pond node with the given queue */
pond_node *create_pond(int n, failfish_queue *q)
{
pond_node *pond;
pond = (pond_node *) malloc(sizeof(pond_node));
if (pond == NULL)
return NULL;
pond->n = n;
pond->queue = q;
pond->next = NULL;
return pond;
}
/* Adds a new pond on the list, returns 0 in error */
int insert_pond(pond_node **list, int n, failfish_queue *q)
{
pond_node *curnode, *prevnode;
pond_node *node;
node = create_pond(n, q);
if (node == NULL)
return 0;
if (*list == NULL) /* empty list */
*list = node;
else
{
curnode = *list;
prevnode = NULL;
while (curnode && curnode->n < n) /* insert in order */
{
prevnode = curnode;
curnode = curnode->next;
}
if (prevnode == NULL) /* inserting at the start */
{
node->next = *list;
*list = node;
}
else
{
node->next = prevnode->next;
prevnode->next = node;
}
}
return 1;
}
/* prints all the ponds in the list */
void print_ponds(pond_node *list, FILE *output)
{
pond_node *pond;
pond = list;
while(pond != NULL)
{
fprintf(output, "%d ", pond->n);
print_failfish_queue(pond->queue, output);
fprintf(output, "\n");
pond = pond->next;
}
}
/* Deallocates all memory used by the pond list */
void destroy_ponds(pond_node *list)
{
pond_node *pond, *temp;
pond = list;
while(pond != NULL)
{
temp = pond;
pond = pond->next;
destroy_failfish_queue(temp->queue);
free(temp);
}
}