C++ Problem with dynamic memory allocation

Discussion in 'Mac Programming' started by Soulstorm, May 26, 2006.

  1. macrumors 68000

    Soulstorm

    Joined:
    Feb 1, 2005
    #1
    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:

    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:
    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
    Code:
    [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.
     
  2. macrumors 68000

    savar

    Joined:
    Jun 6, 2003
    Location:
    District of Columbia
    #2
    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.
     
  3. macrumors newbie

    Joined:
    Jul 23, 2002
    #3
    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.
     
  4. thread starter macrumors 68000

    Soulstorm

    Joined:
    Feb 1, 2005
    #4
    Thanks a lot about your help. I solved the problem
    stash.h:
    Code:
    #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:
    Code:
    #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
    Code:
    void stash::clearStash(){
    	delete [] ch;
    	ch = new char [gIncrement];
    	currentSize = 0;
    	currentStorage = gIncrement;
    	next =  gIncrement - currentSize;
    }
    and in the main
    Code:
    int main(){
    	stash o("hello world");
    	stash b;
    	b = o;
    	o.show();
    	return 0;
    }
    I get this error:
    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...
     
  5. macrumors newbie

    Joined:
    Jul 23, 2002
    #5
    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).
     
  6. x86
    macrumors regular

    x86

    Joined:
    May 25, 2006
    Location:
    Dearborn, MI
    #6
    The problem is that you are trying to delete an unallocated string.

    In the constructor, set ch to 0 or NULL.
    Code:
    stash::stash(char *p){
    	ch = 0;
    	clearStash();
    	insertString(p);
    }
    
    Then check to make sure ch is not NULL before deleteing.
    Code:
    void stash::clearStash(){
    	if(ch)
    		delete [] ch;
    	ch = new char [gIncrement];
    	currentSize = 0;
    	currentStorage = gIncrement;
    	next =  gIncrement - currentSize;
    }
    Hope this helps.
     
  7. macrumors newbie

    Joined:
    Jul 23, 2002
    #7
  8. thread starter macrumors 68000

    Soulstorm

    Joined:
    Feb 1, 2005
    #8
    fixed it. Thank you all, guys, you've been really helpful!
     
  9. macrumors member

    Joined:
    May 21, 2006
    #9
    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
     
  10. thread starter macrumors 68000

    Soulstorm

    Joined:
    Feb 1, 2005
    #10
    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
    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...
     
  11. weg
    macrumors 6502a

    weg

    Joined:
    Mar 29, 2004
    Location:
    nj
    #11
    The STL is the BASIC library.. you should use <sstream> and <string> for what you want to do.
     
  12. thread starter macrumors 68000

    Soulstorm

    Joined:
    Feb 1, 2005
    #12
    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.
     
  13. macrumors 6502a

    Palad1

    Joined:
    Feb 24, 2004
    Location:
    London, UK
    #13
    Oh, templates eh? What a Show-off !
    :p
     

Share This Page