corrupted double-linked list: 0x0804d0c0 (C++)?

NOTE: i have never had a problem of this scale before, and don't really know how to lay it out, if i have layed it out wrong then please explain how i should lay it out. If you cannot or will not help with the program, i am happy simply to learn about the problem.

I've been writing a piece of code in order to practise object orientated programming, but i have come across an error i have never before seen (i have been at this for only a few months and don't get a lot of time to learn because my time is wasted on compulsory education). The kernel itself (apparently) produced this error with my code. But running gdb (with debugging symbols) didn't give me an idea of the line number. Putting in a printf statement revealed that it is looping around a while loop even when the condition is no longer met? This seems odd to me because it appears that the condition isn't met, yet it keeps looping. The reason it throughs up an error (i think) when this happens is because somewhere in the "Stack" class it reallocates memory of negative size for an integer array - although, when i added an if statement to Stack::reloc in order to prevent it realocating negative array sizes it still throughs up the error. Looking down it shows several other pieces of info, (quoting gdb):

Program received signal SIGABRT, Aborted. 0x0012d422 in __kernel_vsyscall ()

I didn't really learn much from the wiki page for SIGABRT, and i don't think that hex number means anything to me. Here is my code, divided into the two classes and main:

headers:

#include <cstdio>
#include <cstdlib>

class Stack:

class Stack {
private:
    int *stack;
    int size;
    void init(int *top) {
        *top = 0;
    }

    void push2(int *s,int* top, int element) {
        s[(*top)++] = element;
    }

    int pop2(int *s,int *top) {
        return s[--(*top)];
    }
    void reloc(int diff) {
        if ((top+diff)>1) {
            realloc(stack, (size+diff));
            size = size+diff;
        }
    }

public:
    int top;
    Stack() {
        init(&top);
        size = 100;
        stack = (int *)malloc(100 * sizeof(int));
    }
    void push(int element) {
        if (top>=(size-1)) reloc(100);
        push2(stack, &top, element);
    }
    int pop() {
        if ((top<(size-120)) && (top>100)) reloc(-100);
        return (pop2(stack, &top));
    }
    int sth() {
        return size;
    }

};

class Universe:

/*Universe is the casual layout for the universe*/
class Universe {
    private:
        int y_cog; //y axis center of gravity
        int x_cog; //x axis "
        int force; //weight of universe
        int fps; //frames per second
        int g; //acceleration under gravity
        int G; //gravitational constant

        //NB: velocity in d/s
        //all stacks defined
        Stack y_pos; //y axis position
        Stack x_pos; //x axis "
        Stack mass; //mass of object
        Stack y_vel; //velocity on y axis
        Stack x_vel; //velocity on x axis
        Stack y_pos2; //stacks for repeating
        Stack x_pos2;
        Stack mass2;
        Stack y_vel2;
        Stack x_vel2;

        //function 'increments' the center of gravity
        void cog(int y, int x, int m) {
            //ratio is offset of unive开发者_Python百科rse cog
            //where 100 is exectly half way
            int ratio = ((m*100)/(force))/2;
            //set the center of gravity the ratio beween the objects
            y_cog = y_cog-(((y_cog-y)/100)*ratio);
            x_cog = x_cog-(((x_cog-x)/100)*ratio);
            force = m+force;
        }

        /*moves the object at the top of the stack and alters velocity
        according to previouse velocity and force towards the universe
        center of gravity*/
        void move() {
            int yp, xp, m, yv, xv, vi, yvi, xvi, rm;
            yp = y_pos2.pop();
            xp = x_pos2.pop();
            m = mass2.pop();
            yv = y_vel2.pop();
            xv = x_vel2.pop();
            //important part
            //set the position according to velocity and frame rate
            yp = yp+(yv/fps);
            xp = xp+(xv/fps);
            //find the ratio share of velocity
            vi = ((g*100)/fps); //velocity increase
            rm = ((y_cog-yp)+(x_cog-xp)); //ratio maximum
            if (rm==0) rm = 1;
            yvi = ((vi/rm)*(y_cog-yp))/100;
            xvi = ((vi/rm)*(x_cog-xp))/100;
            yv = yvi;
            xv = xvi;
            //push everything back
            y_pos.push(yp);
            x_pos.push(xp);
            mass.push(m);
            y_vel.push(yv);
            x_vel.push(xv);
        }

    public:
        Universe() {
            y_cog = 0;
            x_cog = 0;
            force = 0;
            fps = 10;
            g = 10;
            //all stacks initialised
            y_pos = Stack();
            x_pos = Stack();
            mass = Stack();
            y_vel = Stack();
            x_vel = Stack();
        }

        void add(int yp, int xp, int m, int yv, int xv) { //adds object to stack
            y_pos.push(yp);
            x_pos.push(xp);
            mass.push(m);
            y_vel.push(yv);
            x_vel.push(xv);
        }

        void run() {
            int yp, xp, m, yv, xv;
            while (y_pos.top<=0) { //reposition center of gravity
                //mainly pushing things around
                yp = y_pos.pop();
                xp = x_pos.pop();
                m = mass.pop();
                yv = y_vel.pop();
                xv = x_vel.pop();
                cog(yp, xp, m); //the important part
                y_pos2.push(yp);
                x_pos2.push(xp);
                mass2.push(m);
                y_vel2.push(yv);
                x_vel2.push(xv);
            }
            while (y_pos2.top<1) {
                move();
            }
        }

        void outh() { //human output
            int yp, xp, m, yv, xv;
            while (y_pos.top<=0) {
                yp = y_pos.pop();
                xp = x_pos.pop();
                m = mass.pop();
                yv = y_vel.pop();
                xv = x_vel.pop();
                y_pos2.push(yp);
                x_pos2.push(xp);
                mass2.push(m);
                y_vel2.push(yv);
                x_vel2.push(xv);
                printf("%d, %d\t%d\t%d\n", yp, xp, m, yv+xv);
            }
            while (y_pos2.top<=0) {
                y_pos.push(y_pos2.pop());
                x_pos.push(x_pos2.pop());
                mass.push(mass.pop());
                y_vel.push(y_vel.pop());
                x_vel.push(x_vel.pop());
            }
        }       
};

function main:

int main() {
    Universe main = Universe();
    main.add(10, 10, 10, 0, 0);
    main.add(5, 5, 5, 0, 0);
    int i;
    for (i = 1; i<100; i++) {
        main.run();
        main.outh();
        printf("\n");
    }
    return 0;
}

GDB run results (with debugging symbols):

Starting program: /home/james/Desktop/coding/Universe/debug 
*** glibc detected *** /home/james/Desktop/coding/Universe/debug: corrupted double-linked list: 0x0804d0c0 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6(+0x6b591)[0x2d4591]
/lib/tls/i686/cmov/libc.so.6(+0x70ce3)[0x2d9ce3]
/lib/tls/i686/cmov/libc.so.6(realloc+0xdd)[0x2d9f9d]
/home/james/Desktop/coding/Universe/debug[0x80486b2]
/home/james/Desktop/coding/Universe/debug[0x804872c]
/home/james/Desktop/coding/Universe/debug[0x80489b0]
/home/james/Desktop/coding/Universe/debug[0x8048cec]
/home/james/Desktop/coding/Universe/debug[0x80485fd]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0x27fbd6]
/home/james/Desktop/coding/Universe/debug[0x80484d1]
======= Memory map: ========
00110000-0012b000 r-xp 00000000 08:01 393241     /lib/ld-2.11.1.so
0012b000-0012c000 r--p 0001a000 08:01 393241     /lib/ld-2.11.1.so
0012c000-0012d000 rw-p 0001b000 08:01 393241     /lib/ld-2.11.1.so
0012d000-0012e000 r-xp 00000000 00:00 0          [vdso]
0012e000-00217000 r-xp 00000000 08:01 2625203    /usr/lib/libstdc++.so.6.0.13
00217000-00218000 ---p 000e9000 08:01 2625203    /usr/lib/libstdc++.so.6.0.13
00218000-0021c000 r--p 000e9000 08:01 2625203    /usr/lib/libstdc++.so.6.0.13
0021c000-0021d000 rw-p 000ed000 08:01 2625203    /usr/lib/libstdc++.so.6.0.13
0021d000-00224000 rw-p 00000000 00:00 0 
00224000-00248000 r-xp 00000000 08:01 525255     /lib/tls/i686/cmov/libm-2.11.1.so
00248000-00249000 r--p 00023000 08:01 525255     /lib/tls/i686/cmov/libm-2.11.1.so
00249000-0024a000 rw-p 00024000 08:01 525255     /lib/tls/i686/cmov/libm-2.11.1.so
0024a000-00267000 r-xp 00000000 08:01 393299     /lib/libgcc_s.so.1
00267000-00268000 r--p 0001c000 08:01 393299     /lib/libgcc_s.so.1
00268000-00269000 rw-p 0001d000 08:01 393299     /lib/libgcc_s.so.1
00269000-003bc000 r-xp 00000000 08:01 525247     /lib/tls/i686/cmov/libc-2.11.1.so
003bc000-003bd000 ---p 00153000 08:01 525247     /lib/tls/i686/cmov/libc-2.11.1.so
003bd000-003bf000 r--p 00153000 08:01 525247     /lib/tls/i686/cmov/libc-2.11.1.so
003bf000-003c0000 rw-p 00155000 08:01 525247     /lib/tls/i686/cmov/libc-2.11.1.so
003c0000-003c3000 rw-p 00000000 00:00 0 
08048000-0804a000 r-xp 00000000 08:01 132105     /home/james/Desktop/coding/Universe/debug
0804a000-0804b000 r--p 00001000 08:01 132105     /home/james/Desktop/coding/Universe/debug
0804b000-0804c000 rw-p 00002000 08:01 132105     /home/james/Desktop/coding/Universe/debug
0804c000-0806d000 rw-p 00000000 00:00 0          [heap]
b7e00000-b7e21000 rw-p 00000000 00:00 0 
b7e21000-b7f00000 ---p 00000000 00:00 0 
b7fed000-b7fef000 rw-p 00000000 00:00 0 
b7ffe000-b8000000 rw-p 00000000 00:00 0 
bffeb000-c0000000 rw-p 00000000 00:00 0          [stack]

Program received signal SIGABRT, Aborted.
0x0012d422 in __kernel_vsyscall ()

One big problem, the realloc() line should be:

stack = realloc(stack, (size+diff));

Your program is misbehaving and crashing due to memory corruption.

In your case this is probably caused by writing through an invalid pointer. Since the only part of your code that directly uses pointers is your Stack class, it's likely that either Stack has a bug, or Universe has a bug that causes Stack to be used incorrectly.

The standard library already provides a stack implementation, so I don't understand why you are implementing your own. A problem with yours is that you haven't provided a destructor, copy constructor or copy assignment operator. When the destructor is called, it will release the pointer, but not the object it points to. This will lead to memory leaks. Similarly, when the copy constructor or assignment operator is called, it will copy the pointer, not the object it points to. If you've defined the destructor properly, but not the copy functions, you could be deleting non-existent objects if the object has been copied (improperly).

Another problem is that you are using realloc incorrectly. It should really be:

stack = realloc(stack, (size + diff) * sizeof(int));

This is in case the location of the allocation changes. Edit: Another thing I've noticed, thanks to a comment from another answer, is that you have to multiply the size by sizeof(int), since it's expecting the size in bytes.

The aforementioned problems aren't the reason your program is infinitely looping, but it was worth mentioning. The real problem is the loops. You are expecting the loops to execute while top is less than or equal to 0 (or less than 1 in one case). Really, it should be while top is more than 0, since 0 indicates that there are no more elements in the stack. Since you are allowing the stack to access elements at indexes that are less than 0, you're getting an error. It looks like the loops can only meet their condition once, anyway, so you can remove them.

Somewhere in your program you tried to use an invalid pointer. Memory corruption is hard to find, especially for beginners. Quoting Brian Kernighan: "When you try your best to write your code, how will you debug it?" GDB can help you in complicated programs, but in this case I would go to another direction.

Luckily Stack seems to be the only spot in your program dealing with memory. My advice would be to put in some assertions into its methods like this:

// at the beginning of pop():
  assert(top > 1);

This will help you to find errors in other parts of your code, which are misusing your Stack class:

while (y_pos.top<=0) {
  yp = y_pos.pop();

This will cause a stack underflow even if Stack would be correct. As other answers pointed out, realloc did not set the pointer.

There are some other points, I would object to your code:

• Use standard library containers like std::stack<T> or std::vector<T>. Don't mess around with pointers until you have to.
• Don't use malloc and free, use new and delete if you have to.
• Try to put data like x, y, mass, velocity in a data structure to reduce repetitive code.