-2

Goal is to create a balanced symbol checker, program looks for input of these symbols <{[(, then check to see if they are closed. each time one of these is encountered, it is to be pushed onto the stack. Once the stack is full, more memory needs to be allocated. I'm not sure where this error is coming from, but I believe it might be from my push function. I am super confused and have searched everywhere(looked at every question with a similar title on here and tried suggested solutions) to try to fix it. From what I could gather, this error means I am trying to free something twice, but I cannot figure out where that would be happening. I have tried multiple different ways of doing this and nothing seems to work. please help.

Also slightly confused on how to resize a dynamic array. Going into this I thought you made a new temp* pointing to the array contents, resized the original with malloc which erases all contents, then put the contents saved in temp back in. I have seen it done several different ways and am unsure which way to use in which context. Thank you.

typedef struct{    //for reference
     char *darr;
     int size;
     int top;
 }
 stack;

void push (stack *s, char tsymbol){
 if (s->top == s->size){   //if stack is full
    char *temp = (char*)malloc(sizeof(char)*s->size);
    temp = s->darr;
    free(s->darr);
    s->darr = temp;
    s->size += 2;    
   }   
s->darr[++(s->top)] = tsymbol;
//s->top = s->top + 1;
}

different approach

if (s->top == s->size-1){   //if stack is full
   char *pTemp;
   pTemp = (char*)malloc(sizeof(char)*((s->size)+2));
   int i;
   for (i=0; i<(s->top); i++){
       pTemp[i] = s->darr[i];
   }
   free (s->darr);
   s->darr = pTemp;
 }
   s->darr[s->top] = tsymbol;
   s->top = s->top + 1;
}
Captain Patches
  • 31
  • 1
  • 8

1 Answers1

0

You have the following problems with your code:

  1. You're increasing size after you allocate using the current size.
  2. You're not copying the contents of the old array to the new array.
  3. You assign temp = s->darr; after you call malloc(), so you lose the pointer to the new memory.
  4. Later you assign s->darr = temp; after you free(s->darr). But because of #3, temp is the same as s->darr, so this doesn't do anything, and now s->darr is still pointing to the freed memory. The next time you call push() you'll free it again, which causes the double free error.
  5. You assign to s[++(s->top)]. But since you didn't increase the size before allocating, this assigns outside the array.
  6. You need to grow the array when s->top == s->size-1. This is because array indexes go from 0 to size-1; assigning to s->darr[s->size] will write out of bounds. And for a little extra safety, use >= rather than ==.
  7. You should use post-increment when storing the new item into s->darr. With pre-increment, you skip the first element of the array, and also you can write beyond the array unless the growth test used s->size-2.

Here's the corrected version.

void push (stack *s, char tsymbol){
    if (s->top >= s->size - 1){   //if stack is full
        char *temp = alloc(s->size + 2);
        memcpy(temp, s->darr, s->size);
        s->darr = temp;
        s->size += 2;    
    }   
    s->darr[(s->top)++] = tsymbol;
}

Also see Do I cast the result of malloc?

Barmar
  • 741,623
  • 53
  • 500
  • 612
  • Okay thank you, your answer makes sense. I believe most of those happened as a result of errors from trying different approaches and not correctly piecing them together. My original logic seemed to be more correct, however, I tried your correction as well as my original solution and I still get the same error, even when I only input one character. – Captain Patches Feb 15 '19 at 03:09
  • if (s->top == s->size){ //if stack is full char *pTemp; pTemp = (char*)malloc(sizeof(char)*((s->size)+2)); int i; for (i=0; i<(s->top); i++){ pTemp[i] = s->darr[i]; } free (s->darr); s->darr = pTemp; } s->darr[s->top] = tsymbol; s->top = s->top + 1; } Something like this is a bit easier for me to follow, would it follow the same logic? – Captain Patches Feb 15 '19 at 03:10
  • It's hard to read code in comments, since there's no formatting. I can't tell what you did differently. – Barmar Feb 15 '19 at 03:12
  • Also, `*` character has special meaning in comments. If you're going to post code, wrap it in backticks. – Barmar Feb 15 '19 at 03:12
  • I edited my original question to include my different approach – Captain Patches Feb 15 '19 at 03:13
  • Your `if` is wrong, it should be `s->top == s->size-1`. – Barmar Feb 15 '19 at 03:13
  • I meant to say that I have top initialized to 0, I wanted to ask you if that would be the same thing? – Captain Patches Feb 15 '19 at 03:15
  • The loop in place of `memcpy()` is fine. – Barmar Feb 15 '19 at 03:15
  • It doesn't matter what you initialize it to. The point is that `s->size` is the size of the array, and you can't write into `darr[size]` because the last element is `darr[size-1]` – Barmar Feb 15 '19 at 03:16
  • okay got it, thank you. I changed the if to include size-1, I am still getting *** Error in `./a.out': double free or corruption (out): 0x00007ffcd482ffa0 *** Aborted (core dumped) – Captain Patches Feb 15 '19 at 03:18
  • Also, the size of the stack is not changing – Captain Patches Feb 15 '19 at 03:23
  • You should also use post-increment rather than pre-increment with `s->top`. Your code skips index 0. – Barmar Feb 15 '19 at 19:43