PDA

View Full Version : C++ Problem with dynamic memory allocation




Soulstorm
May 26, 2006, 11:24 AM
I have a stash class, which will hold an array of characters and will be dynamically expanded or shrink to fit the newly added characters each time (something like STL's string class - only primitive), and I am stuck at a problem I'm having... This is my stash.h code:

//********Created by Sotiriou Christos
//********(A.K.A.) Soulstorm
//******** http://users.forthnet.gr/ath/jonmecos

//Personnal Stash beta1
//This will hold an array of characters and will return it as a string
//Not completed yet. Modify at your own risk.
#ifndef STASH_H
#define STASH_H
#include <iostream>
using std::cout;
using std::cin;

int gIncrement = 4;

class stash{
char *ch;
int currentSize; //position of the last character
int currentStorage; //size of the entire array
int next;
public:
stash();
stash(int startSize);
stash(char *p);
~stash();

void show(){
cout << "currentStorage: " << currentStorage << "\n";
cout << "current size: " << currentSize << "\n";
cout << "Next: " << next << "\n";
for(int i=0; i<currentSize; i++)
cout << ch[i];
cout << "\n";
}

void inflate();
void add(char p);
void insertString(char *p);
char* returnAsString();
void clearStash();

char returnCharacterAtPosition(int i);
int returnCurrentSize(){return currentSize;}

void operator+(char *p);
void operator=(char *p);
stash operator=(stash s);

};

//**constructors and destructors
stash::stash(){
ch = new char [0];
currentSize = 0;
currentStorage = 0;
next = 0;
}

stash::stash(int startSize){
ch = new char [startSize];
currentSize = 0;
currentStorage = startSize;
next = currentStorage - currentSize;
}

stash::~stash(){
delete [] ch;
cout << "Freeing storage\n";
}

stash::stash(char *p){
clearStash();
insertString(p);
}
//**

//--Increase the stash's size to hold more chars.
void stash::inflate(){
int i;
char *temp = new char [currentSize + gIncrement];
for(i=0; i<currentSize; i++)
temp[i] = ch[i];
delete [] ch;
ch = temp;
currentStorage = currentStorage + gIncrement;
}

//--add a character to the stash and resize it according
//--to space needed
void stash::add(char p){
if(next == 0)
inflate();
ch[currentSize] = p;
++currentSize;
next = currentStorage - currentSize;
}

//--reset the stash
void stash::clearStash(){
currentSize = 0;
currentStorage = 0;
ch = new char [0];
next = currentStorage - currentSize;
}

//--insert an entire string into the stash
void stash::insertString(char *p){
int i;
for(i=0; p[i]; i++){
add(p[i]);
}
}

//--make the chars a string
char* stash::returnAsString(){
add('\0');
next--; //to overwrite the zero byte next time we add something
return ch;
}

//--add more chars into the string;
void stash::operator+(char *p){
insertString(p);
}

//--Return a character at a specified position
//--Return NULL if a character doesn't exist at the
//--requested position
char stash::returnCharacterAtPosition(int i){
if(i>currentSize)
return NULL;
return ch[i];
}

//--clear the stash and hold a new string
void stash::operator=(char *p){
clearStash();
insertString(p);
}

//--THIS HAS PROBLEMS WITH MEMORY ALLOCATION!!!
stash stash::operator=(stash s){
clearStash();
insertString(s.returnAsString());
return *this;
}

#endif
In main(), I am giving the following code:int main(){
stash o = "hello world";


stash b;
b = o;

o.show();
b.show();
return 0;
}
But I am getting this in the console[Session started at 2006-05-26 17:56:43 +0300.]
Freeing storage
Freeing storage
currentStorage: 12
current size: 11
Next: 1
hello world
currentStorage: 12
current size: 11
Next: 1
hello world
Freeing storage
C++ tool 3(1296) malloc: *** Deallocation of a pointer not malloced: 0x3003c0; This could be a double free(), or free() called with the middle of an allocated block; Try setting environment variable MallocHelp to see tools to help debug
Freeing storage
1)Why does this happen? What can I do to fix it?

2)Please if you have recommendations about my code, or any other mistakes I have done, please tell me so, I want to make this class as efficient as I can.

Thank you in advance.



savar
May 26, 2006, 01:46 PM
1)Why does this happen? What can I do to fix it?

2)Please if you have recommendations about my code, or any other mistakes I have done, please tell me so, I want to make this class as efficient as I can.

Thank you in advance.

I dont' use C++ very much, but I have a few comments. First of all, it seems like you are creating a lot of char[]...is the goal to use only as much memory as is exactly needed to store the string? While I understand your desire to be "efficient", efficiency has more than one meaning. In creating and disposing so many objects you're likely to fragment your memory space and waste a lot of time copying stuff between buffers. I think it would be better to only decrease allocated memory through a reset() function...shortening the stored string shouldn't cause a new buffer to be created. (Just my opinion)

As far as debugging goes, all I can suggest is that you step through it in a debugger line by line. You know which pointer is invalid ( 0x3003c0 ), so use the debugger to associate that hex value with the name you gave it in your source code. Once you know which pointer is failing, it will be much easier to isolate the problem.

romanoffi
May 26, 2006, 03:38 PM
A couple of problems that combine to cause your bug:

1. Your assignment operator should take a const reference to the object being copied. This is for efficiency reasons. The way your code is now, a temporary object will be created and then destroyed, which leads to the second point...

2. When the temporary is copied, a copy constructor is called. Since you do not explicitly provide one, the compiler creates a default one. This default one just copies members bitwise. It will not handle allocating 'ch' on the copy. The signature for your copy constr should be stash::stash(const stash &s).

So here the bug: a copy of 'o' is created while assigning it to 'b' (because your assignment operator takes an object, not a reference to one). This copy has it's 'ch' member pointing to 'o's memory (you remedy this by creating a proper copy constructor). The temporary is the deleted, and this action frees the memory pointed to by 'o'! 'o's 'ch' member now points to memory in no man's land.

Another issue: each time you call stash::clearStash() and allocate new memory for 'ch' you cause a memory leak because you did not delete [] whatever ch was pointing to originally.

I agree with the prior poster that your choice of implementation does not seem very efficient. I'd recommend an approach taken by many implementations of std::string: Instead of adding one allocating one byte at a time, double the current size of the string each time the string outgrows its current allocation. Suppose string t is 'foobar' (6 bytes), it would live in an 8 byte buffer. If it were then assigned the value 'foobarbaz' (9 bytes), you would delete the 8 byte buffer and allocate a new 16 byte buffer, and then do the assignment. The buffer size is always a power of 2. As the previous poster said, don't bother reallocating when the string shrinks.

Hope this helps.

Soulstorm
May 26, 2006, 05:06 PM
Thanks a lot about your help. I solved the problem
stash.h:
#ifndef STASH_H
#define STASH_H
#include <iostream>

class stash{
char *ch;
int currentSize; //position of the last character
int currentStorage; //size of the entire array
int next;
public:
stash();
stash(int startSize);
stash(char *p);
stash(stash& other);//copy constructor
~stash();

void show();
void inflate();
void add(char p);
void insertString(char *p);
char* returnAsString();
void clearStash();

char returnCharacterAtPosition(int i);
int returnCurrentSize(){return currentSize;}
int returnCurrentStorage(){return currentStorage;}
int returnNext(){return next;}
char* returnPointerToCh(){return ch;}

void operator+(char *p);
void operator=(char *p);
void operator=(stash &s);

};

#endif
stash.cpp:
#ifndef STASH_CPP
#define STASH_CPP

#include <iostream>
#include "stash.h"
using std::cout;

int gIncrement = 4; //Number of bytes to add each time the class is expanded
//Smaller numbers guarantee less memory consuption, but
//also a small performance hit.
typedef stash MasterString; //New Definition for the Stash

//**constructors and destructors
stash::stash(){
ch = new char [gIncrement];
currentSize = 0;
currentStorage = gIncrement;
next = gIncrement - currentSize;
}

stash::stash(int startSize){
ch = new char [startSize];
currentSize = 0;
currentStorage = startSize;
next = currentStorage - currentSize;
}

stash::~stash(){
delete [] ch;
cout << "Freeing storage\n";
}

stash::stash(char *p){
clearStash();
insertString(p);
}

stash::stash(stash& other){
clearStash();
insertString(other.returnPointerToCh());
}

//**

//Show the elements of the class
void stash::show(){
cout << "currentStorage: " << currentStorage << "\n";
cout << "current size: " << currentSize << "\n";
cout << "Next: " << next << "\n";
for(int i=0; i<currentSize; i++)
cout << ch[i];
cout << "\n";
}

//--Increase the stash's size to hold more chars.
void stash::inflate(){
int i;
char *temp = new char [currentSize + gIncrement];
for(i=0; i<currentSize; i++)
temp[i] = ch[i];
delete [] ch;
ch = temp;
currentStorage = currentStorage + gIncrement;
}

//--add a character to the stash and resize it according
//--to space needed
void stash::add(char p){
if(next == 0)
inflate();
ch[currentSize] = p;
++currentSize;
next = currentStorage - currentSize;
}

//--reset the stash (memory leaks!!!)
void stash::clearStash(){
delete [] ch;
ch = new char [gIncrement];
currentSize = 0;
currentStorage = gIncrement;
next = gIncrement - currentSize;
}

//--insert an entire string into the stash
void stash::insertString(char *p){
int i;
for(i=0; p[i]; i++){
add(p[i]);
}
}

//--make the chars a string
char* stash::returnAsString(){
add('\0');
//next--;
currentSize--;
return ch;
}

//--add more chars into the string;
void stash::operator+(char *p){
insertString(p);
}

//--Return a character at a specified position
//--Return NULL if a character doesn't exist at the
//--requested position
char stash::returnCharacterAtPosition(int i){
if(i>currentSize)
return NULL;
return ch[i];
}

//--clear the stash and hold a new string
void stash::operator=(char *p){
clearStash();
insertString(p);
}

//--make a string hold exactly what the other holds!!!
void stash::operator=(stash &s){
int i;
delete [] ch;
char *temp = new char [s.returnCurrentSize()];
for(i=0; i<s.returnCurrentSize(); i++){
temp[i] = s.returnCharacterAtPosition(i);
}
next = s.returnNext();
currentStorage = s.returnCurrentStorage();
currentSize = s.returnCurrentSize();

ch = temp;
}

#endif
As for the clearstash function, when I write void stash::clearStash(){
delete [] ch;
ch = new char [gIncrement];
currentSize = 0;
currentStorage = gIncrement;
next = gIncrement - currentSize;
}
and in the main
int main(){
stash o("hello world");
stash b;
b = o;
o.show();
return 0;
}
I get this error:
C++ tool 3(2372) malloc: *** Deallocation of a pointer not malloced: 0x8fe067a8; This could be a double free(), or free() called with the middle of an allocated block; Try setting environment variable MallocHelp to see tools to help debug
currentStorage: 12
current size: 11
Next: 1
hello world
Freeing storage
Freeing storage
I don't know why this happens with the new 'clearstash()' function. I thought it was ok to delete a pointer array and then reallocate it...

romanoffi
May 26, 2006, 06:25 PM
A hint on the clearStash problem: Ask yourself what ch points to in clearStash() when that function is called from stash::stash(char *) and stash::stash(stash &other).

x86
May 26, 2006, 06:26 PM
The problem is that you are trying to delete an unallocated string.

In the constructor, set ch to 0 or NULL.

stash::stash(char *p){
ch = 0;
clearStash();
insertString(p);
}


Then check to make sure ch is not NULL before deleteing.

void stash::clearStash(){
if(ch)
delete [] ch;
ch = new char [gIncrement];
currentSize = 0;
currentStorage = gIncrement;
next = gIncrement - currentSize;
}

Hope this helps.

romanoffi
May 26, 2006, 06:57 PM
Yeah, that's what I was hinting at. Though, technically, you do not need to check ch for NULL before doing the delete. (http://www.parashift.com/c++-faq-lite/freestore-mgmt.html#faq-16.8)

Soulstorm
May 27, 2006, 01:47 AM
fixed it. Thank you all, guys, you've been really helpful!

jbusc
May 28, 2006, 04:00 AM
I also suggest using "const char*" in function parameters where possible. so for example, having operator+ or operator= use const char allows you to use assign or append regular quoted strings as well, i.e., strings in the source with quotes around them -> stash s = "this is a string"; s+= " more strings"..etc

Soulstorm
May 28, 2006, 06:42 AM
I also suggest using "const char*" in function parameters where possible. so for example, having operator+ or operator= use const char allows you to use assign or append regular quoted strings as well, i.e., strings in the source with quotes around them -> stash s = "this is a string"; s+= " more strings"..etc
When I have the time, I will do that too.

All other problems have been fixed. The files as they are now are in here:

stash.cpp (http://users.forthnet.gr/ath/jonmecos/Mainsite/Development/archives/limbo/MasterString/stash.cpp)
stash.h (http://users.forthnet.gr/ath/jonmecos/Mainsite/Development/archives/limbo/MasterString/stash.h)

Now that the basic structure has been fixed, I can add more operators and functions. I am developing this library to ensure that I will use the STL as few times as I can (some teachers in our university forbid the use of any other library except the basic ones)... I think the stash will come in handy later...

weg
May 28, 2006, 07:51 AM
When I have the time, I will do that too.

All other problems have been fixed. The files as they are now are in here:

stash.cpp (http://users.forthnet.gr/ath/jonmecos/Mainsite/Development/archives/limbo/MasterString/stash.cpp)
stash.h (http://users.forthnet.gr/ath/jonmecos/Mainsite/Development/archives/limbo/MasterString/stash.h)

Now that the basic structure has been fixed, I can add more operators and functions. I am developing this library to ensure that I will use the STL as few times as I can (some teachers in our university forbid the use of any other library except the basic ones)... I think the stash will come in handy later...

The STL is the BASIC library.. you should use <sstream> and <string> for what you want to do.

Soulstorm
May 29, 2006, 01:28 AM
The STL is the BASIC library.. you should use <sstream> and <string> for what you want to do.Of course I should. But can you please come to Greece and tell that to my teachers? I almost lost my semester for being 'too disobedient' as far as concerning programming techniques is concerned. I won't lose any more time.

The point is that in the programming class, no one told us about the existence of STL. I was forced to discover things as templates and dynamic memory allocation techniques over the internet. So, when you go to the class and present something new, they think you are just showing off. That's why I prefer not to use the STL now. This 'stash' class is made for my friends in my university that have a hard time doing things without STL.

Palad1
May 29, 2006, 06:04 AM
Oh, templates eh? What a Show-off !
:p