• Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.

C++ Help?

Status
Not open for further replies.

Magni

Member
Put some malloc's and free's for the gets() as well as for nbBI.abs->prev and next, now I'm getting the following SIGSEGV signal

Code:
Program received signal SIGSEGV, Segmentation fault.
0x08045f2 in newBigInteger (nbS=0x804a008 "123") at test.c:44
44             nbBI.abs->prev = (Block*) malloc(sizeof(Block));

The full source code (got C&P finally working in the VM Terminal):

Code:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

typedef struct block{
	struct block* prev;
	int val;
	struct block* next;
} Block;

typedef struct {
	int sign;
	Block* abs;
} BigInteger;

BigInteger newBigInteger(char*);
void printBigInteger(BigInteger);

int main(int argc, char* argv[]) {
	char* nbS = (char*) malloc(sizeof(char));
	BigInteger nbBI;
	
	gets(nbS);

	nbBI = newBigInteger(nbS);
	printBigInteger(nbBI);
	
	free(nbS);
	free(nbBI.abs->prev);
	nbBI.abs->prev = NULL;
	free(nbBI.abs->next);
	nbBI.abs->next = NULL;

	return 0;
}

BigInteger newBigInteger(char* nbS) {
	int i = 0;
	int n = strlen(nbS);

	BigInteger nbBI;
	nbBI.sign = 0;
	nbBI.abs->prev = (Block*) malloc(sizeof(Block));
	nbBI.abs->prev = NULL;
	nbBI.abs->val = 0;
	nbBI.abs->next = (Block*) malloc(sizeof(Block));
	nbBI.abs->next = NULL;

	if(nbS[i] == '-') {
		nbBI.sign = -1;
		i++;
	}

	while(i < n) {
		int p = 3;
		while(i < n && p >= 0) {
			nbBI.abs->val += atoi(&nbS[i]) * pow(10,p);
			p--;
			i++;
		}
		Block new;
		nbBI.abs->prev = &new;
		new.prev = NULL;
		new.val = 0;
		new.next = nbBI.abs;
		nbBI.abs = &new;
	}

	return nbBI;
}

void printBigInteger(BigInteger x) {
	printf("%d", x.abs->val);	
}

printBigInteger() is obviously unfinished right now, that's not the problem.
 

wolfmat

Confirmed Asshole
Just skimmed over it, but shouldn't this
Code:
typedef struct block{
	struct block* prev;
	int val;
	struct block* next;
} Block;

rather be this
Code:
typedef struct Block {
	struct Block* prev;
	int val;
	struct Block* next;
} Block;
 

Magni

Member
deadbeef said:
What are you doing with char* nbS?

Converting it to a BigInteger with the newBigInteger function, and then (though that part isn't implemented yet in the code I posted), printing it with the printBigInteger function.

The gist of the function is to convert a string representing a "big" integer into a new type: BigInteger, consisting of its sign as an int and its absolute value as a doubly linked list of blocks of four digits, with "19201452210" becoming NULL <- 2210 <-> 145 <-> 192 -> NULL for example.

wmat, if there's one thing I'm sure of in my code, it's that that typedef declaration is correct.
 

wolfmat

Confirmed Asshole
MagniHarvald said:
wmat, if there's one thing I'm sure of in my code, it's that that typedef declaration is correct.
The way I posted it is the way self-referential structs are usually done. That's all. I don't really know what to think about your way of doing it.
 

Magni

Member
wmat said:
The way I posted it is the way self-referential structs are usually done. That's all. I don't really know what to think about your way of doing it.

Oh.. Because we've done so many of these so far this term, and I've got my lecture right in front of me right now, so I know the way I did it works. Maybe yours does too, but my teacher was pretty adamant about us distinguishing between the name used before and after the struct definition :lol
 

wolfmat

Confirmed Asshole
MagniHarvald said:
Oh.. Because we've done so many of these so far this term, and I've got my lecture right in front of me right now, so I know the way I did it works. Maybe yours does too, but my teacher was pretty adamant about us distinguishing between the name used before and after the struct definition :lol
Well, okay.

Your mistake there is that abs is an uninitialized pointer. You probably don't actually want a pointer for abs anyway. So if you take the asterisk away from abs in the BigInteger struct, that should do it.

Edit: Or keep the asterisk and initialize abs before filling its data (do a malloc). Probably smarter because you're operating on addresses below.
 

jvalioli

Member
wmat said:
The way I posted it is the way self-referential structs are usually done. That's all. I don't really know what to think about your way of doing it.
Your way is not the way it is usually done with that kind of typedef.

edit: Scratch this. I think maybe I don't understand the structure of your program?

Sorry if that isn't clear. It's like 2 AM here. Good luck!
 

wolfmat

Confirmed Asshole
jvalioli said:
Your way is not the way it is usually done with that kind of typedef.
Well, I guess you're right; the way I wrote it usually implies a followup typedef instead of typedef struct foo{};. But in C++, it should be all the same, right? And the namespace is polluted in any case.
 

Magni

Member
wmat said:
Well, okay.

Your mistake there is that abs is an uninitialized pointer. You probably don't actually want a pointer for abs anyway. So if you take the asterisk away from abs in the BigInteger struct, that should do it.

Edit: Or keep the asterisk and initialize abs before filling its data (do a malloc). Probably smarter because you're operating on addresses below.

Alright, I added:

Code:
nbBI.abs = (Block*) malloc(sizeof(Block)); //right after initializing nbBI
free(nbBI.abs); // with the other free()'s
nbBI.abs = NULL;

I no longer get a segfault! I get this instead..
Code:
123           
*** glibc detected *** ./test: free(): invalid pointer: 0xbffa7740 ***
======= Backtrace: =========
/lib/libc.so.6(+0x6efe1)[0x5f8fe1]
./test[0x804858c]
/lib/libc.so.6(__libc_start_main+0xe6)[0x5a0cc6]
./test[0x8048491]
======= Memory map: ========
0058a000-0070f000 r-xp 00000000 fd:00 12405      /lib/libc-2.12.1.so
0070f000-00710000 ---p 00185000 fd:00 12405      /lib/libc-2.12.1.so
00710000-00712000 r--p 00185000 fd:00 12405      /lib/libc-2.12.1.so
00712000-00713000 rw-p 00187000 fd:00 12405      /lib/libc-2.12.1.so
00713000-00716000 rw-p 00000000 00:00 0 
00add000-00ade000 r-xp 00000000 00:00 0          [vdso]
00b14000-00b32000 r-xp 00000000 fd:00 5437       /lib/ld-2.12.1.so
00b32000-00b33000 r--p 0001d000 fd:00 5437       /lib/ld-2.12.1.so
00b33000-00b34000 rw-p 0001e000 fd:00 5437       /lib/ld-2.12.1.so
00f9d000-00fc5000 r-xp 00000000 fd:00 13097      /lib/libm-2.12.1.so
00fc5000-00fc6000 r--p 00027000 fd:00 13097      /lib/libm-2.12.1.so
00fc6000-00fc7000 rw-p 00028000 fd:00 13097      /lib/libm-2.12.1.so
045a6000-045c3000 r-xp 00000000 fd:00 14586      /lib/libgcc_s-4.4.4-20100630.so.1
045c3000-045c4000 rw-p 0001d000 fd:00 14586      /lib/libgcc_s-4.4.4-20100630.so.1
08048000-08049000 r-xp 00000000 fd:00 131172     /home/Paul/Documents/Project/test
08049000-0804a000 rw-p 00000000 fd:00 131172     /home/Paul/Documents/Project/test
0849f000-084c0000 rw-p 00000000 00:00 0          [heap]
b78ea000-b78eb000 rw-p 00000000 00:00 0 
b78f8000-b78fb000 rw-p 00000000 00:00 0 
bff88000-bffa9000 rw-p 00000000 00:00 0          [stack]
0Aborted (core dumped)
123 is my input for nbS.

Trying to analyze this now..
 

jvalioli

Member
What is a block? Why do you have a linked list if you're only using one of them? (your print method might be broken too). Or are you just doing the most specific case of a 3 digit number?

Also, you need to allocate more space for your char*. You only have 1 byte(as in, you'll only read the sign).

Also you are malloc'ing data, and then for some reason setting those variables to NULL, creating memory leaks. Also your bigInteger variable in main shouldnt be assigned that way. Your method should return a newly allocated(malloc) bigInteger and the variable in main should be a pointer.
 

Magni

Member
jvalioli said:
What is a block? Why do you have a linked list if you're only using one of them?

Also, you need to allocate more space for your char*. You only have 1 byte(as in, you'll only read the sign).

A Block is a group of four digits from the BigInteger. I thought about that as well, but how many should I put? Just an arbitrary value (like 1000*sizeof(char)) ?

gdb output:

Code:
(gdb) b main
Breakpoint 1 at 0x8048535: file test.c, line 21.
(gdb) r
Starting program: /home/Paul/Documents/Project/test 

Breakpoint 1, main (argc=1, argv=0xbffff434) at test.c:21
21		char* nbS = (char*) malloc(sizeof(char));
Missing separate debuginfos, use: debuginfo-install glibc-2.12.1-3.i686
(gdb) s
24		gets(nbS);
(gdb) s
123
26		nbBI = newBigInteger(nbS);
(gdb) s
newBigInteger (nbS=0x804a008 "123") at test.c:41
41		int i = 0;
(gdb) s
42		int n = strlen(nbS);
(gdb) s
45		nbBI.sign = 0;
(gdb) s
46		nbBI.abs = (Block*) malloc(sizeof(Block));
(gdb) s
47		nbBI.abs->prev = (Block*) malloc(sizeof(Block));
(gdb) s
48		nbBI.abs->prev = NULL;
(gdb) s
49		nbBI.abs->val = 0;
(gdb) s
50		nbBI.abs->next = (Block*) malloc(sizeof(Block));
(gdb) s
51		nbBI.abs->next = NULL;
(gdb) s
53		if(nbS[i] == '-') {
(gdb) s
58		while(i < n) {
(gdb) s
59			int p = 3;
(gdb) s
60			while(i < n && p >= 0) {
(gdb) s
61				nbBI.abs->val += atoi(&nbS[i]) * pow(10,p);
(gdb) s
62				p--;
(gdb) s
63				i++;
(gdb) s
60			while(i < n && p >= 0) {
(gdb) s
61				nbBI.abs->val += atoi(&nbS[i]) * pow(10,p);
(gdb) s
62				p--;
(gdb) s
63				i++;
(gdb) s
60			while(i < n && p >= 0) {
(gdb) s
61				nbBI.abs->val += atoi(&nbS[i]) * pow(10,p);
(gdb) s
62				p--;
(gdb) s
63				i++;
(gdb) s
60			while(i < n && p >= 0) {
(gdb) s
66			nbBI.abs->prev = &new;
(gdb) s
67			new.prev = NULL;
(gdb) s
68			new.val = 0;
(gdb) s
69			new.next = nbBI.abs;
(gdb) s
70			nbBI.abs = &new;
(gdb) s
58		while(i < n) {
(gdb) s
73		return nbBI;
(gdb) s
74	}
(gdb) s
main (argc=1, argv=0xbffff434) at test.c:27
27		printBigInteger(nbBI);
(gdb) s
printBigInteger (x=...) at test.c:77
77		printf("%d", x.abs->val);	
(gdb) s
78	}
(gdb) s
main (argc=1, argv=0xbffff434) at test.c:29
29		free(nbS);
(gdb) s
30		free(nbBI.abs);
(gdb) s
*** glibc detected *** /home/Paul/Documents/Project/test: free(): invalid pointer: 0xbffff320 ***
======= Backtrace: =========
/lib/libc.so.6(+0x6efe1)[0x1c9fe1]
/home/Paul/Documents/Project/test[0x804858c]
/lib/libc.so.6(__libc_start_main+0xe6)[0x171cc6]
/home/Paul/Documents/Project/test[0x8048491]
======= Memory map: ========
00110000-0012e000 r-xp 00000000 fd:00 5437       /lib/ld-2.12.1.so
0012e000-0012f000 r--p 0001d000 fd:00 5437       /lib/ld-2.12.1.so
0012f000-00130000 rw-p 0001e000 fd:00 5437       /lib/ld-2.12.1.so
00130000-00131000 r-xp 00000000 00:00 0          [vdso]
00131000-00159000 r-xp 00000000 fd:00 13097      /lib/libm-2.12.1.so
00159000-0015a000 r--p 00027000 fd:00 13097      /lib/libm-2.12.1.so
0015a000-0015b000 rw-p 00028000 fd:00 13097      /lib/libm-2.12.1.so
0015b000-002e0000 r-xp 00000000 fd:00 12405      /lib/libc-2.12.1.so
002e0000-002e1000 ---p 00185000 fd:00 12405      /lib/libc-2.12.1.so
002e1000-002e3000 r--p 00185000 fd:00 12405      /lib/libc-2.12.1.so
002e3000-002e4000 rw-p 00187000 fd:00 12405      /lib/libc-2.12.1.so
002e4000-002e7000 rw-p 00000000 00:00 0 
045a6000-045c3000 r-xp 00000000 fd:00 14586      /lib/libgcc_s-4.4.4-20100630.so.1
045c3000-045c4000 rw-p 0001d000 fd:00 14586      /lib/libgcc_s-4.4.4-20100630.so.1
08048000-08049000 r-xp 00000000 fd:00 131172     /home/Paul/Documents/Project/test
08049000-0804a000 rw-p 00000000 fd:00 131172     /home/Paul/Documents/Project/test
0804a000-0806b000 rw-p 00000000 00:00 0          [heap]
b7fef000-b7ff0000 rw-p 00000000 00:00 0 
b7ffd000-b8000000 rw-p 00000000 00:00 0 
bffdf000-c0000000 rw-p 00000000 00:00 0          [stack]
0
Program received signal SIGABRT, Aborted.
0x00130416 in __kernel_vsyscall ()
Missing separate debuginfos, use: debuginfo-install libgcc-4.4.4-10.fc13.i686
(gdb) s
Single stepping until exit from function __kernel_vsyscall, 
which has no line number information.

Program terminated with signal SIGABRT, Aborted.
The program no longer exists.

So the problem happens when I free nbBI.abs

edit: I switched up the order of the free()'s, this time nbBI.abs->prev was freed first and the program aborted at that moment.

gnulp.png


abs points on a Block. To start with, there is only one Block, which is why both prev and next are set to NULL.
 

wolfmat

Confirmed Asshole
You shouldn't call the block "new". Call it "newBlock" or something.

When you write "nbBI.abs->prev = NULL;", then prev gets the literal address 0x0, so your initialization was in vain; free() has to fail in that case.
 

Magni

Member
wmat said:
You shouldn't call the block "new". Call it "newBlock" or something.

When you write "nbBI.abs->prev = NULL;", then prev gets the literal address 0x0, so your initialization was in vain; free() has to fail in that case.

So I can only set a pointer to NULL after having free'd it? In that case I should only do the malloc once I add newBlock, right?

And do if tests before free'ing, right?
 

jvalioli

Member
MagniHarvald said:
So I can only set a pointer to NULL after having free'd it? In that case I should only do the malloc once I add newBlock, right?

And do if tests before free'ing, right?
Yeah, i wrote some sample code showing you how to do this, but the whole block concept made me doubt myself and I deleted it :(. And you still should follow one of the suggestions I made about above allocating your bigInteger
 

Slavik81

Member
MagniHarvald said:
So I can only set a pointer to NULL after having free'd it? In that case I should only do the malloc once I add newBlock, right?

And do if tests before free'ing, right?
If you set a pointer to NULL before freeing it, you'll be freeing NULL. This will not crash, since freeing null does nothing (so no, you don't need an if test), but it won't achieve your objective of freeing what the memory at the pointer's previous value.
 

Magni

Member
jvalioli said:
Yeah, i wrote some sample code showing you how to do this, but the whole block concept made me doubt myself and I deleted it :(. And you still should follow one of the suggestions I made about above allocating your bigInteger

How should I go about then? nbBI is a BigInteger, so it is a an int and a Block*, so I should malloc nbBI directly? I'm not sure I understand what you mean =/

Slavik, that's what I though, but then why am I getting a SIGABRT signal when free'ing?

Thanks for bearing with me guys =)
 

wolfmat

Confirmed Asshole
MagniHarvald said:
So I can only set a pointer to NULL after having free'd it? In that case I should only do the malloc once I add newBlock, right?

And do if tests before free'ing, right?
By the book, no, you shouldn't set pointers to NULL. You should initialize all data in a Block in every case, and fill in meaningful data no matter what.
If you are at a stopping point in a self-referential structure, you should use special data for such Blocks that identify the stopping points.
This is sometimes solved with literal self-reference, meaning that prev == this, if you know what I mean. You can easily test for that.
You can also invent a special Block that holds no data and use it as a stopping point, then compare by address. That way, the free() is easier to do.

So you'd do
Code:
Block startingBlock;
startingBlock.prev = &startingBlock;
startingBlock.val = 0;
startingBlock.next = &startingBlock;
And to check whether your prev in some Block is the starting Block, you would compare by address.
When you free the whole thing, you start at the outer points of your self-referential structure and work your way inwards, and that generically. So the first thing you free() is the prev of the first Block, for instance. And that happens to be the starting Block, and all is well.
If you want to find the first block generically, you have to march towards it first, of course. To identify it, you need the address of the starting Block again, and compare with the prev. You found the first Block when those match.

You would then go about it in a similar fashion with the other end - you can even use the same Block as the starting Block.

Of course you CAN test for 0x0. Some people go about it like that. It's certainly less code.
 

jvalioli

Member
Yeah, it is safe to free a null pointer.

What I meant by my previous post was:

main{
BigInteger* m = newBigIteger(blah);
}

BigInteger* newBigInteger(char* blah){
BigInteger nbBS = malloc(sizeof(BigInteger);
...
..
...
return nbBS;

}

Okay, girlfriend is yelling at me to sleep. Good luck


edit:wmat, I think that is a really weird way to handle the ends to a doubly-linked-list. Do not recommend doing that at all.
 

Magni

Member
NovemberMike said:
Here's a tip. If I can't copy your code I'm not likely to help you fix it.

Said I was sorry, I installed updates for 20 minutes to get C&P-ing working again for you though =)

Thanks jvalioli, good night. I should get some sleep as well, it's 9:15am now..

Printing the various variables step by step in gdb is showing that atoi() is not working at all, so I'm gonna fix that as well..
 

wolfmat

Confirmed Asshole
jvalioli said:
edit:wmat, I think that is a really weird way to handle the ends to a doubly-linked-list. Do not recommend doing that at all.
The advantage is that no matter what you do, you always operate on Blocks.
 

jvalioli

Member
wmat said:
The advantage is that no matter what you do, you always operate on Blocks.
But this can also cause buggy behavior if you're not careful, while using NULLs will segfault in an easy to figure out manner. Also has very easy stopping conditions for iterations and such.
 
jvalioli said:
But this can also cause buggy behavior if you're not careful, while using NULLs will segfault in an easy to figure out manner. Also has very easy stopping conditions for iterations and such.

It's been awhile since I've done linked lists (thank god for other people solving problems) but what wmat did is a fairly standard way to do a circular linked list. There's pros and cons to both linear and circular but they both work.

Also Magniharvald, never use "new" as a variable name. It is going to confuse the hell out of anyone that tries to look at the code.
 

wolfmat

Confirmed Asshole
jvalioli said:
But this can also cause buggy behavior if you're not careful, while using NULLs will segfault in an easy to figure out manner. Also has very easy stopping conditions for iterations and such.
To an extent, that is of course right, there is maintenance overhead. And maybe it's a little much in this case. When you've got more complex structures though and do lots of generic operations on those that possibly march arbitrarily, it helps to have a way to identify your end, which is what this enables.

For instance, when you have a 4D structure as the starting point with linked lists on each end, you always know in which direction you went without having to remember once you've reached an end.

When you iterate, you do a compare of two ints in both cases anyhow to check where you're at, just with the one version testing for NULL and the other testing for the address of the capping Block.

When you take this further, you initialize such a structure with said capping Blocks and one element, and to expand, you replace appropriately. So there is no way of running into a segfault.
 

Magni

Member
NovemberMike said:
It's been awhile since I've done linked lists (thank god for other people solving problems) but what wmat did is a fairly standard way to do a circular linked list. There's pros and cons to both linear and circular but they both work.

Also Magniharvald, never use "new" as a variable name. It is going to confuse the hell out of anyone that tries to look at the code.

Point taken.

I should point out that I am not allowed to do a circular doubly-linked list. The ends have to point to NULL.
 

Magni

Member
Updated version:

Code:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

typedef struct block{
        struct block* prev;
        int val;
        struct block* next;
} Block;

typedef struct {
        int sign;
        Block* abs;
} BigInteger;

BigInteger newBigInteger(char*);
void printBigInteger(BigInteger);

int main(int argc, char* argv[]) {
        char* nbS = (char*) malloc(100*sizeof(char));
        BigInteger nbBI;

        gets(nbS);

        nbBI = newBigInteger(nbS);
        printBigInteger(nbBI);

        free(nbS);
        free(nbBI.abs);

        return 0;
}

BigInteger newBigInteger(char* nbS) {
        BigInteger nbBI;
        nbBI.sign = 0;
        nbBI.abs = (Block*) malloc(sizeof(Block));
        nbBI.abs->prev = NULL;
        nbBI.abs->val = 0;
        nbBI.abs->next = NULL;
        Block* currBlock = nbBI.abs;

        int n = strlen(nbS);
        int l = -1; // limit of the while loop, depends on whether nbBI is negative or not (to not do a test on the '-' char)
        int p;

        if(nbS[0] == '-') {
                nbBI.sign = -1;
                l++;
        }

        int i = n-1;
        int q = 0;

        while(i > l) {

                do {
                        p = n-i-1-(4*q);
                        currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
                        i--;
                } while(i > l && p < 3);

                q++;

                Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = (Block*) malloc(sizeof(Block));
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
                free(newBlock);
                newBlock = NULL;
        }

        return nbBI;
}

gdb step-by-step variable values: (there is a one-line delay between the instruction and the variable value updating)
Code:
Starting program: /home/Paul/Documents/Project/test 

Breakpoint 1, main (argc=1, argv=0xbffff434) at test.c:21
21		char* nbS = (char*) malloc(100*sizeof(char));
(gdb) 
(gdb) s
24		gets(nbS);
(gdb) 
-10321
26		nbBI = newBigInteger(nbS);
(gdb) s
newBigInteger (nbS=0x804a008 "-10321") at test.c:37
37		nbBI.sign = 0;
(gdb) 
38		nbBI.abs = (Block*) malloc(sizeof(Block));
(gdb) 
39		nbBI.abs->prev = NULL;
(gdb) 
40		nbBI.abs->val = 0;
(gdb) 
41		nbBI.abs->next = NULL;
(gdb) 
42		Block* currBlock = nbBI.abs;
(gdb) 
44		int n = strlen(nbS);
(gdb) 
45		int l = -1;
(gdb) 
48		if(nbS[0] == '-') {
(gdb) 
49			nbBI.sign = -1;
(gdb) 
50			l++;
(gdb) 
53		int i = n-1;
(gdb) 
54		int q = 0;
(gdb) 
56		while(i > l) {
(gdb) 
59				p = n-i-1-(4*q);
(gdb) 
60				currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
(gdb) 
61				i--;
(gdb) 
62			} while(i > l && p < 3);
(gdb) 
59				p = n-i-1-(4*q);
(gdb) 
60				currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
(gdb) 
61				i--;
(gdb) 
62			} while(i > l && p < 3);
(gdb) 
59				p = n-i-1-(4*q);
(gdb) 
60				currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
(gdb) 
61				i--;
(gdb) 
62			} while(i > l && p < 3);
(gdb) 
59				p = n-i-1-(4*q);
(gdb) 
60				currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
(gdb) 
61				i--;
(gdb) 
62			} while(i > l && p < 3);
(gdb) 
64			q++;
(gdb) print nbBI.abs->val
$37 = 321
(gdb) print currBlock->val
$38 = 321
(gdb) print nbBI.abs->next
$39 = (struct block *) 0x0
(gdb) print currBlock->next
$40 = (struct block *) 0x0
(gdb) s
66			Block* newBlock = (Block*) malloc(sizeof(Block));
(gdb) s
67			currBlock->next = (Block*) malloc(sizeof(Block));
(gdb) s
68			currBlock->next = newBlock;
(gdb) print currBlock->next
$41 = (struct block *) 0x804a090
(gdb) print nbBI.abs->next
$42 = (struct block *) 0x804a090
(gdb) s
69			newBlock->prev = (Block*) malloc(sizeof(Block));
(gdb) print currBlock->next
$43 = (struct block *) 0x804a080
(gdb) print nbBI.abs->next
$44 = (struct block *) 0x804a080
(gdb) s
70			newBlock->prev = currBlock;
(gdb) print newBlock->prev
$45 = (struct block *) 0x804a0a0 // here you see the delay
(gdb) print currBlock
$46 = (Block *) 0x804a070
(gdb) s
71			newBlock->next = NULL;
(gdb) print newBlock->prev
$47 = (struct block *) 0x804a070 // now it's the right address
(gdb) print nbBI.abs
$48 = (Block *) 0x804a070
(gdb) s
72			currBlock = newBlock;
(gdb) print newBlock->next
$49 = (struct block *) 0x0
(gdb) print nbBI.abs->next->next
$50 = (struct block *) 0x0
(gdb) print currBlock->next->next
$51 = (struct block *) 0x0
(gdb) s
73			currBlock->val = 0;
(gdb) print currBlock
$52 = (Block *) 0x804a080
(gdb) print currBlock->prev
$53 = (struct block *) 0x804a070
(gdb) print nbBI.abs->next
$54 = (struct block *) 0x804a080
(gdb) print currBlock->next
$55 = (struct block *) 0x0
(gdb) print currBlock->val
$56 = 0
(gdb) s
74			free(newBlock);
(gdb) s
75			newBlock = NULL;
(gdb) s
56		while(i > l) {
(gdb) s
59				p = n-i-1-(4*q);
(gdb) s
60				currBlock->val += (nbS[i]-48) * pow(10,p); // '0' = 48
(gdb) s
61				i--;
(gdb) print currBlock->val
$57 = 1
(gdb) print currBlock->prev->val
Cannot access memory at address 0x4
(gdb) print nbBI.abs->val
$58 = 321
(gdb) print nbBI.abs->next->val
$59 = 1

The highlighted error should return 321. I'm still trying to figure out how I broke the link and lost the pointer.. The broken link makes it impossible to print the BigInteger.
 

Zeppu

Member
Just woke up so I'm not really paying attention but:

Code:
Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = (Block*) malloc(sizeof(Block));
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
                free(newBlock);
                newBlock = NULL;

freeing newBlock means whatever is being pointed to by currBlock is now freed.
 

Magni

Member
edit: yeah, what you just said while I was busy having fun in gdb :lol

Code:
74			free(newBlock);
(gdb) print nbBI.abs
$29 = (Block *) 0x804a070
(gdb) print currBlock
$30 = (Block *) 0x804a080
(gdb) print newBlock
$31 = (Block *) 0x804a080
(gdb) print currBlock->prev
$32 = (struct block *) 0x804a070 // before free(newBlock) does effect
(gdb) print nbBI.abs->next
$33 = (struct block *) 0x804a080
(gdb) s
75			newBlock = NULL;
(gdb) print nbBI.abs
$34 = (Block *) 0x804a070
(gdb) print currBlock
$35 = (Block *) 0x804a080
(gdb) print newBlock
$36 = (Block *) 0x804a080
(gdb) print nbBI.abs->next
$37 = (struct block *) 0x804a080
(gdb) print currBlock->prev
$38 = (struct block *) 0x0 // after free(newBlock) does effect

The good news is I found the precise moment where it screws up. The bad news is I have no idea how to fix it =s
 

Zeppu

Member
Easy, don't free newBlock. You want to keep that block. Everything must be freed only at the instance when the queue is destroyed, at which point, you get the queue (this is a circular one, right?) get any item (ideally you would've stored the 'head' or 'tail' somewhere and simply

Code:
Block * current = tail/head;

while (current->next!= NULL) {
    Block * next = current->next;
    free (current);
    current = NULL;
    current = next;
}

Remember, this is all allocated on the heap. Unless you specifically free the memory it stays there until termination of program. And when you assign a pointer value to another pointer value it just means that they are both pointing to the same location. Therefore if you free one it means that the other is now pointing to freed memory.

Code:
Block * x = new Block;
x = NULL;

Means you have a leak. You've just permanently lost the newly allocated Block. However if you (pseudocode):

Code:
Block * x = new Block;
current->next = x;
x= NULL;

You still know the location of x, and just because you set x = NULL doesn't mean you changed the value of the created block, just the place where x points to (0x0 in this case).

(if you have problems with pointers let me know and I'll explain them to you in the same way I learnt them a long time ago, at a club, drunk, when I met my CS teacher and she was kind enough to let explain it to me in the intoxicated state i was.. worked though :D)
 

Magni

Member
josephdebono said:
Easy, don't free newBlock. You want to keep that block. Everything must be freed only at the instance when the queue is destroyed, at which point, you get the queue (this is a circular one, right?) get any item (ideally you would've stored the 'head' or 'tail' somewhere and simply

Code:
Block * current = tail/head;

while (current->next!= NULL) {
    Block * next = current->next;
    free (current);
    current = NULL;
    current = next;
}

No, I'm not allowed to use a circular list. What am I supposed to do with this? My currBlock->next = NULL in my case (since it's not circular).

Code:
                Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = (Block*) malloc(sizeof(Block));
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
              //free(newBlock); (removed)
                newBlock = NULL;

Would this work then?
 

Zeppu

Member
MagniHarvald said:
No, I'm not allowed to use a circular list. What am I supposed to do with this? My currBlock->next = NULL in my case (since it's not circular).

Code:
                Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = (Block*) malloc(sizeof(Block));
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
              //free(newBlock); (removed)
                newBlock = NULL;

Would this work then?

Gimme a moment I'm gonna look at all your posts (I've woken up now :)) to get an understand if what you're trying to achieve. However yes, removing the free(newBlock) is definitely required.

Edit: Ok from what I understand you want a doubly-linked list.

That means the following:

The first node in the list will have prev = NULL;
The last node will have next = NULL;
First->next = Second.
Second->prev = First;
Second->next = Third;
etc...

Therefore, you gotta do the following

Create the first node (malloc or new, whichever)
Assign value to abs
set prev = NULL (permanently)
set prev = NULL (until we get a new value)
Do not free since freeing it means you're losing all the data.

Create second node.
Assign value to abs
set prev = first node (such that second->prev points to first)
set next = NULL (until we get a new value)

Etc...
This will automatically mean that at any point in the linked list you can move forward and backward, and finding a NULL means you've reached the start or the end of the list.

You never have to free any created block except when you want to either delete a node, or you want to delete a whole linked list.

If you need to delete a node (say node 2) you should do the following

Code:
       (first)
Second->prev->next = Second->next;
Second->next->prev = Second->prev;
       (third)
 

Magni

Member
It works, I just gotta fix my printBigInteger function now. Thanks =)

There no need to free currBlock or newBlock because they are automatically free'd at the end of the function, is that it? Just to make sure I understood well =)
 

Zeppu

Member
MagniHarvald said:
It works, I just gotta fix my printBigInteger function now. Thanks =)

There no need to free currBlock or newBlock because they are automatically free'd at the end of the function, is that it? Just to make sure I understood well =)

I suggest you create a function to free all the nodes.

Basically when you call

Code:
free(nbBI.abs);

You are freeing nbBI.abs which is a Block. That means that you have freed the first block of the queue but left the rest there in memory. Furthermore, Second->prev will point to the previous location of nbBI which no longer exists and so will give you an error. Also, if you haven't stored the location of Second, etc etc, you have lost the location of all that memory.

You need to do the followingfunction to free up all memory:
Code:
void FreeNode(Block* block) {
Block * next = block->next; // gets you the location of the next item
free(block)
if (next != NULL) {
   FreeNode(next);
}
}

This recursive function, given the first item will delete all the items in your list.

Btw, bro, I found another leak in your code (sorry)...

Code:
Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = (Block*) malloc(sizeof(Block));
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
                newBlock = NULL;

Here is basically what you are doing - imagine the number after each line is a memory address where you allocated the new block, mkaay?

Assume currBlock location is [0x1]

Code:
Block* newBlock = (Block*) malloc(sizeof(Block));  // new Block at [0x2]
currBlock->next = (Block*) malloc(sizeof(Block));   // new Block at [0x3]
currBlock->next = newBlock; // currBlock->next points to [0x2], [0x3] has now been lost
newBlock->prev = (Block*) malloc(sizeof(Block)); // new Block at [0x4]
newBlock->prev = currBlock; // newBlock->prev points to [0x1], [0x4] has now been lost

Here you are allocating (and losing) 2 memory locations. That needs to be as follows;

Code:
Block* newBlock = (Block*) malloc(sizeof(Block));
                currBlock->next = newBlock;
                newBlock->prev = currBlock;
                newBlock->next = NULL;
                currBlock = newBlock;
                currBlock->val = 0;
                newBlock = NULL;

Remember, each time you malloc, you are allocating memory for it, assigning next = newBlock doesn't mean you are putting newBlock into that allocated memory, but that next points to the current (and permanent) location of newBlock.
 
Some class questions

So I have a .h file with a callSolver() function as public and private methods for different solvers, because I don't want whatever is calling callSolver() to be able to choose which one is used. So all of them are static, since there's no variables that persist or anything like that.

The thing is, when implementing them in the .cpp file, it keeps saying the private functions are inaccessible when trying to call them from the public callSolver() function. Am I allowed to do this or do I really have to make them all public (because that solves the problem when I do)
 
Zoramon089 said:
Some class questions

So I have a .h file with a callSolver() function as public and private methods for different solvers, because I don't want whatever is calling callSolver() to be able to choose which one is used. So all of them are static, since there's no variables that persist or anything like that.

The thing is, when implementing them in the .cpp file, it keeps saying the private functions are inaccessible when trying to call them from the public callSolver() function. Am I allowed to do this or do I really have to make them all public (because that solves the problem when I do)
A public function of a class should be able to access private functions and variables of that class. My guess is you're probably missing a keyword somewhere. You should post your code.
 

RiZ III

Member
Zoramon089 said:
Some class questions

So I have a .h file with a callSolver() function as public and private methods for different solvers, because I don't want whatever is calling callSolver() to be able to choose which one is used. So all of them are static, since there's no variables that persist or anything like that.

The thing is, when implementing them in the .cpp file, it keeps saying the private functions are inaccessible when trying to call them from the public callSolver() function. Am I allowed to do this or do I really have to make them all public (because that solves the problem when I do)

Are your static callSolvers are in different classes than your callSolver??
 
So I have:

ODEsolver.h
Code:
#include <vecmath.h>
#include <vector>

class ODEsolver
{

public:
	typedef vector< float > FloatVector;

	ODEsolver();
	static FloatVector getNewState(char type, float stepSize, FloatVector oldState, FloatVector derivatives);

private:
	static FloatVector EulerStep(float stepSize, FloatVector oldState, FloatVector derivatives);
	static FloatVector RungeKuttaStep(float stepSize, FloatVector oldState, FloatVector derivatives);

};


ODEsolver.cpp
Code:
#include "ODEsolver.h"
#include <vecmath.h>
#include <vector>

using namespace std;

typedef vector< float > FloatVector;

static FloatVector getNewState(char type, float stepSize, FloatVector oldState, FloatVector derivatives)
{
	if(type=='e')
		return ODEsolver::EulerStep(stepSize,oldState,derivatives);
	else if(type=='r')
		return ODEsolver::RungeKuttaStep(stepSize,oldState,derivatives);
}

static ODEsolver::FloatVector EulerStep(float stepSize, FloatVector oldState, FloatVector derivatives)
{
}

static ODEsolver::FloatVector RungeKuttaStep( float stepSize, ODEsolver::FloatVector oldState, ODEsolver::FloatVector derivatives)
{
}

And it keeps complaining that EulerStep and RungeKuttaStep are inaccessible in getNewState
 
Zoramon089 said:
It's been a while since I've coded in C++, but I think your functions in the .cpp file need to be inside a "class ODEsolver" block, otherwise, they're considered to be global functions, not belonging to any class. It's not enough to give the file the same name as the header file. File names don't really mean anything to the compiler.

Code:
#include "ODEsolver.h"
#include <vecmath.h>
#include <vector>

using namespace std;

typedef vector< float > FloatVector;

class ODEsolver
{
static FloatVector getNewState(char type, float stepSize, FloatVector oldState, FloatVector derivatives)
{
	if(type=='e')
		return ODEsolver::EulerStep(stepSize,oldState,derivatives);
	else if(type=='r')
		return ODEsolver::RungeKuttaStep(stepSize,oldState,derivatives);
}

static ODEsolver::FloatVector EulerStep(float stepSize, FloatVector oldState, FloatVector derivatives)
{
}

static ODEsolver::FloatVector RungeKuttaStep( float stepSize, ODEsolver::FloatVector oldState, ODEsolver::FloatVector derivatives)
{
}
}
 

Slavik81

Member
Zoramon089 said:
And it keeps complaining that EulerStep and RungeKuttaStep are inaccessible in getNewState
ODEsolver::FloatVector RungeKuttaStep
should be
ODEsolver::FloatVector ODEsolver::RungeKuttaStep

And same with the Euler step.

EDIT: edited slightly, since FloatVector is defined within ODEsolver.
 
CrayzeeCarl said:
It's been a while since I've coded in C++, but I think your functions in the .cpp file need to be inside a "class ODEsolver" block, otherwise, they're considered to be global functions, not belonging to any class. It's not enough to give the file the same name as the header file. File names don't really mean anything to the compiler.

Haha, oh wow, it worked. Such a trivial mistake that I'm surprised I didn't see...thanks. Now, after going through my code...I'm wondering, why is it that despite making a typedef for FloatVector in the .h file I need to include it again in the .cpp file for it to know what it is?
 
Is there any difference in wrapping the .cpp file contents in "class ODEsolver{}" vs prefixing everything in it with "ODEsolver::"?
 

RiZ III

Member
Zoramon089 said:
I'm wondering, why is it that despite making a typedef for FloatVector in the .h file I need to include it again in the .cpp file for it to know what it is?

Because your typedef is in the scope of OEDSolver, therefore you would need to do OEDSolver::FloatVector. Also, you don't need the static keyword when defining the method.
 

Slavik81

Member
Zoramon089 said:
Is there any difference in wrapping the .cpp file contents in "class ODEsolver{}" vs prefixing everything in it with "ODEsolver::"?
The main difference is that wrapping the cpp file contents in class ODEsolver won't compile since it will think you're redeclaring the type.
 

RiZ III

Member
Zoramon089 said:
Is there any difference in wrapping the .cpp file contents in "class ODEsolver{}" vs prefixing everything in it with "ODEsolver::"?

You'd be redfining the class by doing that and it wouldn't work. The difference between

class OEDSolver
{
...
void foo();
}


and
void OEDSolver::foo()
{
}

is that the first is a declaration, and the other a definition. You can implement the method within the declaration if you want and then you wouldn't have it in the cpp file.
 
RiZ III said:
You'd be redfining the class by doing that and it wouldn't work. The difference between

class OEDSolver
{
...
void foo();
}


and
void OEDSolver::foo()
{
}

is that the first is a declaration, and the other a definition. You can implement the method within the declaration if you want and then you wouldn't have it in the cpp file.
Aww, crap. Now I remember. I guess I've been programming in C# too long. :lol

This is the correct answer. Sorry about that.
 

Sapiens

Member
Can anyone help me here.

I have no idea where to start. But I'm burned out. I have to take this program and edit it so that it has support for multiple queues.

Here's the original we have to edit:

Code:
#include "genlib.h"
#include "random.h"
#include "queue.h"
#include <iostream>
#include <iomanip>

/* simulation parameters */

const int SIMULATION_TIME = 2000;
const double ARRIVAL_PROBABILITY = 0.10;
const int MIN_SERVICE_TIME = 5;
const int MAX_SERVICE_TIME = 15;

/* function prototypes */

void RunSimulation();
void ReportResults(int nServed, long totalWait, long totalLength);

/* main program */

int main() {
    Randomize();
    RunSimulation();
    return 0;
}

/*
 * Function: RunSimulation
 * Usage: RunSimulation();
 * -----------------------
 * This function runs the actual simulation. In each time unit,
 * the program first checks to see whether a new customer arrives.
 * Then, if the cashier is busy (indicated by a nonzero value for
 * serviceTimeRemaining), the program decrements that variable to
 * indicate that one more time unit has passed. Finally, if the
 * cashier is free, the simulation serves another customer from
 * the queue after recording the waiting time for that customer.
 */

void RunSimulation() {
    Queue<int> queue;
    int serviceTimeRemaining = 0;
    int nServed = 0;
    long totalWait = 0;
    long totalLength = 0;

    for (int t = 0; t < SIMULATION_TIME; t++) {
        if (RandomChance(ARRIVAL_PROBABILITY)) {
            queue.enqueue(t);
        }
        if (serviceTimeRemaining > 0) {
            serviceTimeRemaining--;
            if (serviceTimeRemaining == 0) nServed++;
        } else if (!queue.isEmpty()) {
            totalWait += t - queue.dequeue();
            serviceTimeRemaining =
              RandomInteger(MIN_SERVICE_TIME, MAX_SERVICE_TIME);
        }
        totalLength += queue.size();
    }
    ReportResults(nServed, totalWait, totalLength);
}

/*
 * Function: ReportResults
 * Usage: ReportResults(nServed, totalWait, totalLength);
 * ------------------------------------------------------
 * This function reports the results of the simulation.
 */

void ReportResults(int nServed, long totalWait, long totalLength) {
    cout << "Simulation results given the following parameters:"
         << endl;
    cout << fixed << setprecision(2);
    cout << "  SIMULATION_TIME:     " << setw(4)
         << SIMULATION_TIME << endl;
    cout << "  ARRIVAL_PROBABILITY: " << setw(7)
         << ARRIVAL_PROBABILITY << endl;
    cout << "  MIN_SERVICE_TIME:    " << setw(4)
         << MIN_SERVICE_TIME << endl;
    cout << "  MAX_SERVICE_TIME:    " << setw(4)
         << MAX_SERVICE_TIME << endl;
    cout << endl;
    cout << "Customers served:      " << setw(4) << nServed << endl;
    cout << "Average waiting time:  " << setw(7)
         << double(totalWait) / nServed << endl;
    cout << "Average queue length:  " << setw(7)
         << double(totalLength) / SIMULATION_TIME << endl;
 

RiZ III

Member
Sapiens said:
Can anyone help me here.

I have no idea where to start. But I'm burned out. I have to take this program and edit it so that it has support for multiple queues.

Here's the original we have to edit:

You could pass in a reference or a pointer to a queue to the function RunSimulation. You could process as many queues as you want that way.
 

bluemax

Banned
ultron87 said:
Yeah, but the index of arrays start at 1! It is so wrong that it hurts me!

I just recently start doing contracting work that is all done in LUA script. After being a C++ game engineer for 2.5 years it was really hard to adjust at first to index 1 arrays.
 
Status
Not open for further replies.
Top Bottom