title: reversing the order of a circular deque C
body: <p>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. </p>
  
  <p>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. </p>
  
  <p>However, when I run this I get a malloc error, and since I'm new to C, I'm not sure how to debug. </p>
  
  <p>--------ERROR-------</p>
  
  <h2>prog(10346) malloc: <em>*</em> error for object 0x7faf13c03920: pointer being freed was not allocated set a breakpoint in malloc_error_break to debug</h2>
  
  <p>code</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;assert.h&gt;
  #include &lt;float.h&gt;
  #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-&gt;backSentinel is allocated and q-&gt;size equals zero
  */
  void _initCirListDeque (struct cirListDeque *q) 
  {
      struct DLink* lnk = (struct DLink*)malloc(sizeof(struct DLink));
      assert(lnk != 0);   //sentinel made
      q-&gt;Sentinel = lnk;
      q-&gt;Sentinel-&gt;next = q-&gt;Sentinel-&gt;prev = q-&gt;Sentinel;
      q-&gt;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-&gt;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-&gt;next-&gt;prev = newLnk;       //right connects to new
      newLnk-&gt;next = lnk-&gt;next;       //new connect to right
      newLnk-&gt;prev = lnk;             //new connect to left
      lnk-&gt;next = newLnk;             //left connect to new
      q-&gt;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-&gt;Sentinel-&gt;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-&gt;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-&gt;Sentinel-&gt;next-&gt;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-&gt;Sentinel-&gt;prev-&gt;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-&gt;next-&gt;prev = lnk-&gt;prev;    //connect right link to left link
      lnk-&gt;prev-&gt;next = lnk-&gt;next;    //connect left link to right link
      q-&gt;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-&gt;Sentinel-&gt;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-&gt;Sentinel-&gt;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-&gt;size &gt; 0){
          removeFrontCirListDeque(q);
      }
      free(q-&gt;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-&gt;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-&gt;Sentinel-&gt;next;
      while(current != q-&gt;Sentinel){
          printf("value: %f\t", current-&gt;value);
          current = current-&gt;next;
          x++;
          if (x &gt;= 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-&gt;next = q-&gt;Sentinel-&gt;prev;
          newSent-&gt;prev = q-&gt;Sentinel-&gt;next;
          q-&gt;Sentinel-&gt;next-&gt;prev = newSent;
          q-&gt;Sentinel-&gt;prev-&gt;next = newSent;
          free(q-&gt;Sentinel);
          q-&gt;Sentinel = newSent;
  
  /* A different approach that didn't work.
          temp-&gt;next = q-&gt;Sentinel-&gt;prev;
              q-&gt;Sentinel-&gt;prev = q-&gt;Sentinel-&gt;next;
              q-&gt;Sentinel-&gt;next = temp-&gt;next;
              free(temp);*/
  }
  </code></pre>