Ok, so I'm working on an assignment where you have to build a circular deque in C. I have all of the functions implemented and I'm in the process of testing them. Everything was good until the 'reverse' function.
I thought this would be easy, you create a new link, hook it up in place of the Sentinel. Kill the old sentinel and then set the sentinel for the deque to the new link.
However, when I run this I get a malloc error, and since I'm new to C, I'm not sure how to debug.
--------ERROR-------
code
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include "cirListDeque.h"
/* Double Link Struture */
struct DLink {
TYPE value;/* value of the link */
struct DLink *next;/* pointer to the next link */
struct DLink *prev;/* pointer to the previous link */
};
# define TYPE_SENTINEL_VALUE DBL_MAX
/* ************************************************************************
Deque ADT based on Circularly-Doubly-Linked List WITH Sentinel
************************************************************************ */
struct cirListDeque {
int size;/* number of links in the deque */
struct DLink *Sentinel; /* pointer to the sentinel */
};
/* internal functions prototypes */
struct DLink* _createLink (TYPE val);
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk);
void _removeLink(struct cirListDeque *q, struct DLink *lnk);
/* ************************************************************************
Deque Functions
************************************************************************ */
/* Initialize deque.
param: q pointer to the deque
pre: q is not null
post: q->backSentinel is allocated and q->size equals zero
*/
void _initCirListDeque (struct cirListDeque *q)
{
struct DLink* lnk = (struct DLink*)malloc(sizeof(struct DLink));
assert(lnk != 0); //sentinel made
q->Sentinel = lnk;
q->Sentinel->next = q->Sentinel->prev = q->Sentinel;
q->size = 0;
}
/*
create a new circular list deque
*/
struct cirListDeque *createCirListDeque()
{
struct cirListDeque* newCL = malloc(sizeof(struct cirListDeque));
_initCirListDeque(newCL);
return(newCL);
}
/* Create a link for a value.
param: val the value to create a link for
pre: none
post: a link to store the value
*/
struct DLink * _createLink (TYPE val)
{
struct DLink* lnk = (struct DLink*) malloc(sizeof(struct DLink));
lnk->value = val;
return(lnk);
}
/* Adds a link after another link
param: q pointer to the deque
param: lnk pointer to the existing link in the deque
param: newLnk pointer to the new link to add after the existing link
pre: q is not null
pre: lnk and newLnk are not null
post: the new link is added into the deque after the existing link
*/
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk)
{
lnk->next->prev = newLnk; //right connects to new
newLnk->next = lnk->next; //new connect to right
newLnk->prev = lnk; //new connect to left
lnk->next = newLnk; //left connect to new
q->size++;
}
/* Adds a link to the back of the deque
param: q pointer to the deque
param: val value for the link to be added
pre: q is not null
post: a link storing val is added to the back of the deque
*/
void addBackCirListDeque (struct cirListDeque *q, TYPE val)
{
struct DLink* lnk = _createLink(val);
_addLinkAfter(q, q->Sentinel->prev, lnk);
}
/* Adds a link to the front of the deque
param: q pointer to the deque
param: val value for the link to be added
pre: q is not null
post: a link storing val is added to the front of the deque
*/
void addFrontCirListDeque(struct cirListDeque *q, TYPE val)
{
struct DLink* lnk = _createLink(val);
_addLinkAfter(q, q->Sentinel, lnk);
}
/* Get the value of the front of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: none
ret: value of the front of the deque
*/
TYPE frontCirListDeque(struct cirListDeque *q)
{
return q->Sentinel->next->value;
}
/* Get the value of the back of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: none
ret: value of the back of the deque
*/
TYPE backCirListDeque(struct cirListDeque *q)
{
return q->Sentinel->prev->value;
}
/* Remove a link from the deque
param: q pointer to the deque
param: lnk pointer to the link to be removed
pre: q is not null and q is not empty
post: the link is removed from the deque
*/
void _removeLink(struct cirListDeque *q, struct DLink *lnk)
{
//assert(!isEmptyList(lst));
lnk->next->prev = lnk->prev; //connect right link to left link
lnk->prev->next = lnk->next; //connect left link to right link
q->size--;
free(lnk);
}
/* Remove the front of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the front is removed from the deque
*/
void removeFrontCirListDeque (struct cirListDeque *q) {
_removeLink(q, q->Sentinel->next);
}
/* Remove the back of the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the back is removed from the deque
*/
void removeBackCirListDeque(struct cirListDeque *q)
{
_removeLink(q, q->Sentinel->prev);
}
/* De-allocate all links of the deque
param: q pointer to the deque
pre: none
post: All links (including backSentinel) are de-allocated
*/
void freeCirListDeque(struct cirListDeque *q)
{
while (q->size > 0){
removeFrontCirListDeque(q);
}
free(q->Sentinel);
}
/* Check whether the deque is empty
param: q pointer to the deque
pre: q is not null
ret: 1 if the deque is empty. Otherwise, 0.
*/
int isEmptyCirListDeque(struct cirListDeque *q) {
return q->size == 0;
}
/* Print the links in the deque from front to back
param: q pointer to the deque
pre: q is not null and q is not empty
post: the links in the deque are printed from front to back
*/
void printCirListDeque(struct cirListDeque *q)
{
struct DLink *current;
int x = 0;
assert(!isEmptyCirListDeque(q));
current = q->Sentinel->next;
while(current != q->Sentinel){
printf("value: %f\t", current->value);
current = current->next;
x++;
if (x >= 6){
printf("\n");
x = 0;
}
}
}
/* Reverse the deque
param: q pointer to the deque
pre: q is not null and q is not empty
post: the deque is reversed
*/
void reverseCirListDeque(struct cirListDeque *q)
{
//struct DLink *temp = _createNewLink(0); //try this allocat then assign then move
struct DLink *newSent = (struct DLink*) malloc(sizeof(struct DLink));
newSent->next = q->Sentinel->prev;
newSent->prev = q->Sentinel->next;
q->Sentinel->next->prev = newSent;
q->Sentinel->prev->next = newSent;
free(q->Sentinel);
q->Sentinel = newSent;
/* A different approach that didn't work.
temp->next = q->Sentinel->prev;
q->Sentinel->prev = q->Sentinel->next;
q->Sentinel->next = temp->next;
free(temp);*/
}
I'm answering my own question here, but thanks to the posters, the debugging tips made this answer possible.
My logic was flawed.
I thought that if you reversed the direction of the sentinel you could reverse the order of the circular list. However, even if you change all four of the links to the sentinel, the surrounding links prev and next fields point in the wrong direction.
To fix this I created a new deque with this code:
void reverseCirListDeque(struct cirListDeque *q)
{
struct cirListDeque* newQ = createCirListDeque();
while(!isEmptyCirListDeque(q)){
addBackCirListDeque(newQ, backCirListDeque(q));
removeBackCirListDeque(q);
}
q->Sentinel = newQ->Sentinel;
q->size = newQ->size;
free(newQ);
}