title: What could be cause of error "malloc: *** error for object 0x7b: pointer being freed was not allocated"
body: <p>I am writing this program for a class. This program is a simple parenthesis checker application using stacks. In this case, I have used static arrays to implement the stack data structure. The program builds fine but I run into this runtime error and thus far have not been able to see where the problem could be stemming from.  </p>
  
  <p>Here is little information that I do understand that the problem could be due to trying to free memory that was not allocated using malloc. But in the following code, I don't see where this could be happening.</p>
  
  <p>The following is the interface implementation code for stack using a static array. I have also added the stack interface code to add characters on the stack and the driver program to test the routines. </p>
  
  <pre><code>#include "stack.h"
  #include "stdlib.h" /* malloc, free */
  #include "stdio.h"
  
  #define MAXSTACKSIZE 10
  
  struct stack_record {
    generic_ptr base[MAXSTACKSIZE];
    generic_ptr * top;
  };
  
  unsigned int num_elements(stack * const p_S)
  {
    unsigned int numels = ((*p_S)-&gt;top - (*p_S)-&gt;base);
    /*  return ((*p_S)-&gt;top - (*p_S)-&gt;base); */
    printf("number of elements in the stack is: %u\n", numels);
    return numels;
  }
  status init_stack(stack * const p_S)
  {
    stack_record * record = (stack_record *)malloc(sizeof(stack_record));
    if(record == NULL) {
      return ERROR;
    }
    record-&gt;top = record-&gt;base;
    *p_S = record;
    return OK;
  }
  bool empty_stack(stack * const p_S)
  {
    if(num_elements(p_S) == 0)
      {
        printf("stack is EMPTY!\n");
        return TRUE;
      }
    else
      {
        printf("stack NOT Empty!\n");
        return FALSE;
      }
  }
  status push(stack * const p_S, generic_ptr const data)
  {
    if (num_elements(p_S) == MAXSTACKSIZE)
      return ERROR;
  
    *( (*p_S)-&gt;top ) = data;
    (*p_S)-&gt;top++;
     return OK;
  }
  
  status pop(stack * const p_S, generic_ptr * const p_data)
  {
    if (empty_stack(p_S) == TRUE)
      return ERROR;
    *p_data = *((*p_S)-&gt;top);
    (*p_S)-&gt;top--;
    /*  ((*p_S)-&gt;top)--; */
    return OK;
  }
  
  status top(stack *const p_S, generic_ptr * const p_data)
  {
     if (pop(p_S, p_data) == ERROR)
      return ERROR;
  
    return push(p_S, *p_data);
  }
  
  void destroy_stack(stack * const p_S, void (* const p_func_f)())
  {
    if ((p_func_f) != NULL) {
      generic_ptr * curr;    
      for(curr = (*p_S)-&gt;top;
      curr != (*p_S)-&gt;base;
      ++curr)
            (*p_func_f)(*curr);
    }
    free(*p_S); /*free the dynamically allocated memory on the heap */
    *p_S = NULL;
   }
  </code></pre>
  
  <p>Following are the stack interface routines for characters:</p>
  
  <pre><code>/*************************************************************************/
  /* adapted from Esakov and Weiss, Section 5.2                            */
  /*************************************************************************/
  
  #include "char_stack.h"
  #include "stdlib.h" /* malloc */
  #include "stdio.h"
  #define DEBUG 1 
  
  status push_char(stack * const p_S, char const c)
  {
    /*
     *     Push the character c onto the stack.
     */
    char * p_c = (char *) malloc(sizeof(char));
  
    if(p_c == NULL)
      return ERROR;
    *p_c = c;
  
    if(DEBUG)
    /* Debug code: begin */
    {
      printf("Character to PUSH on the stack: %c\n", *p_c);
    }
    /* Debug code: end */
  
    if (push(p_S, (generic_ptr)p_c) == ERROR) {
      if(DEBUG)
        printf("char_stack: push_char: failed to push the character on the stack!\n");
      free(p_c);
      return ERROR;
    }
    return OK;
  }
  
  status pop_char(stack * const p_S, char * const p_c)
  {
    /*
     *     Pop the stack. Return the character in p_c.
     */
  
    generic_ptr p_data;
  
    if( pop(p_S, &amp;p_data) == ERROR)
      return ERROR;
  
    *p_c = *((char*)p_data);
  
    if(DEBUG)
    /*Debug code: begin */
  printf("char_stack.c::pop_char: Character to POP on the stack: %c\n", *p_c);
  
    /*Debug code: end */
  
     free(p_data);
     return OK;
  }
  
  status top_char(stack * const p_S, char * const p_c)
  {
    /*
     *     Return the top character from the stack in p_c
     */
    generic_ptr p_data;
  
    if (top(p_S, &amp;p_data) == ERROR)
      return ERROR;
  
    *p_c = *((char *)p_data); 
    return OK;
  }
  </code></pre>
  
  <p>Driver program for the application:</p>
  
  <pre><code>/**************************************************************************/
  /* adapted from Esakov and Weiss, Section 5.2                             */
  /**************************************************************************/
  
  #include "stdio.h"
  #include "stdlib.h"
  #include "char_stack.h"
  
  char matching_symbol(char const c)
  {
    switch(c) {
      case '(': return ')';
      case ')': return '(';
      case '}': return '{';
      case '{': return '}';
      case '[': return ']';
      case ']': return '[';
    }
    return 0;
  }
  
  status consume_char(stack * const p_S, char input)
  {
    switch (input) {
      case '(':
      case '{':  
      case '[':
        return push_char(p_S, input); 
      case ')':
      case '}':
      case ']':
        { 
          char c;    
          if (pop_char(p_S, &amp;c) == ERROR || c != matching_symbol(input)) { 
            return ERROR;
          } else {
            return OK;
          }
        }
      default:
        return OK; 
    }
  }
  
  int main(int argc, char * argv[])
  {
  
    if (argc == 1) {
      exit(EXIT_SUCCESS);
    }
  
    {
      stack S;
  
      init_stack(&amp;S);
  
      {
        char *ptr;
        for (ptr = argv[1];
             *ptr != '\0' &amp;&amp; consume_char(&amp;S, *ptr) == OK;
             ++ptr); 
        if (*ptr == '\0' &amp;&amp; empty_stack(&amp;S)) { 
  
      destroy_stack(&amp;S,free);
          exit(EXIT_SUCCESS);
        } else {
      destroy_stack(&amp;S,free);
          exit(EXIT_FAILURE);
        }
      }
    }  
  
    exit(EXIT_SUCCESS);  
  }
  </code></pre>
  
  <p>I would like to add that in the driver program, I have narrowed that the call to destroy stack is what triggers this issue. But I have reviewed this code and believe this code is fine and the problem is elsewhere. </p>
  
  <p>[Edit 1]: For completeness, I have appended the driver code where these functions are being called. 
  [Edit 2]: Added the stack interface routines for characters.</p>