Copy-On-Write example

[zanklob]

Hi,

I want to create a copu-on-write mechanism.
I am supposed to have a class (StringHolder), that will keep a pointer to a string. I want if there are other objects with pointers to the same string the program to be aware of it and make the new pointers to point to the same string.
Plus I want it to delete the string if no pointer points to that string, should not allow to alter the string if there are other pointers to that string (instead to point in a new string), and i want to make use of the operator '+=' . A reference of more or less what i want to do is here : http://ccfit.nsu.ru/~ddol/2006-2007/oop-2-course/cow/index.html
The objects of the class StringHolder are supposed to be called in the main like this :
StringHolder a;
a("kiri");

This is what i have done so far :

#include "stdafx.h"

#include <iostream>
#include <cstring>
#include <string>
#include <map>


//A class that keeps count of how many pointers point to each std::string
class U_Ptr
{
friend class StringHolder;
std::string* ip;
std::map<std::string*, int> pointer_count; //A map that counts how many pointers to each std::string exist
public:

U_Ptr() {}

U_Ptr(std::string* p) : ip(p)
{
	pointer_count[ip] = 1;
}

~U_Ptr() 
{ 
	pointer_count.clear();
}

void AddString(std::string* a_Data)
{
	Map_Type::iterator iter = pointer_count.find(a_Data);
	if (iter != pointer_count.end())
		++iter->second;
	else
		pointer_count.insert(std::pair<std::string, int>(a_Data, 1));
}

};

//A class that keeps a pointer to a std::string object
class StringHolder
{
public:
	StringHolder(std::string* a_Data)  
	{
		m_Data = a_Data;
		AddString(m_Data);
	}
	
	void StringHolder::operator+=(std::string rhs)  
	
	{
		std::string a = (*m_Data);
	    a.append(rhs);
	    std::cout << *m_Data << std::endl;
	}
	
	~StringHolder()
	{ 

	}
	void Print()
	{
		std::cout << *m_Data << std::endl;
	}

	std::string GetString()
	{
		return m_Data;
	}
private:
	std::string* m_Data;
};


int main()
{
	U_Ptr ptr;

	std::string test = "kiri";
	std::string* p_test = &test;
	StringHolder a(p_test);
	StringHolder b(p_test);
	b += "Luc";
	b.Print();
	return 0;
}

Am i on the right track?

[mik2718]

Looks complicated with the map in there - here is the usual COW layout

bag of bits for the string placeholder (would be neater as a nested class)

struct strholder
{
  string str;
  int instancecount;
};

outline of COW class

class mystring
{
private:
  strholder* ptr;
  void detach();
public:
  mystring()
    : ptr(new strholder)
    { ptr->instancecount = 1; }
  mystring(const string& setstr)
    : ptr(new strholder)
    { ptr->str = setstr; ptr->instancecount = 1;}
  mystring(const mystring& other) // link up this instance to data from other instance
    : ptr(other.ptr)
    { ++ptr->instanceount; }
  ~mystring();
  mystring& operator=(const mystring&);
  
  // non mutative service
   char charAt(int i) const;

  // mutative service - must detach
   mystring& operator+=(const mystring&);

};

mystring::~mystring()
{ 
  --ptr->instancecount;
  if(ptr->instancecount == 0) // only delete the data if no more instances
    delete ptr;
}

mystring& operator=(const mystring& other)
{
   if(this == &other || ptr == other.ptr) // self assignment might cause a problem
      return *this;
   --ptr->instancecount; // this element will no longer point to its current data
   if(ptr->instancecount == 0) // and if no other instance then delete the data
      delete ptr;
   ptr = other.ptr; // link up to RHS object's data
   ++ptr->instancecount; // which now has an extra instance
   return *this;
}

// do this first thing for any mutative (non const) service
void mystring::detach()
{ // make a deep copy of the object - if necessary
  if(ptr->instancecount == 1) // not necessary - only one instance
     return;
   // make deep copy
   strholder* temp new strholder;
   temp->str = ptr->str; // copy string
   temp->instancecount = 1;
   --ptr->instancecount; // no of instances to old data is decremented
   ptr = temp; // now pointing to new data with one instance
}

char mystring::charAt(int i) const
{ // this is a const service so just operate on ptr->str directly

}

mystring& mystring::operator=(const mystring& other)
{ // this is a non const service so must detach first
    detach();
    // now have a single instance, free to operate on the data

}

[zanklob]

Hmm..it seems that your way is better..
But what is wrong with the way i do it?
After my first result "String kiri has : 1 pointer(s)."
I get an Segmentation fault.
I updated the code a little :

//#include "stdafx.h"

#include <iostream>
#include <cstring>
#include <string>
#include <map>
//changes

//A class that keeps count of how many pointers point to each string
class U_Ptr
{


public:

U_Ptr() {}

/*U_Ptr(std::string* p) : ip(p)
{
	pointer_count[ip] = 1;
}*/

~U_Ptr()
{
//	pointer_count.clear();
}

std::string* AddString(std::string* a_Data)
{
	std::string* m_pStr;
	std::string m_Str;
	std::string m_Data;
	m_Data = *a_Data;
//	Map_Type::iterator iter = pointer_count.find(a_Data); //psakse me vash to periexomeno tou pointer kai oxi ton pointer (isws proswrinh metavlhth gia na krathsei to periexomeno)
	if (pointer_count.empty())
	{
		pointer_count.insert(std::pair<std::string*, int>(a_Data, 1));
		return a_Data;
	}
	else
	{

		for (Map_Type::iterator iter = pointer_count.begin(); iter != pointer_count.end(); ++iter)
		{
			m_Data = *a_Data;
			m_pStr = iter->first;
			m_Str = *m_pStr;
			if (m_Data.compare(m_Str) == 0)
			{
				a_Data = iter->first;
				++iter->second;
			}
			else
				pointer_count.insert(std::pair<std::string*, int>(a_Data, 1));
		}

	}

}

void DeleteString(std::string* a_Data)
{
	Map_Type::iterator iter = pointer_count.find(a_Data);
	if (iter->second == 1)
	{
		pointer_count.erase(iter);
	}
	else
	{
		--iter->second;
	}
}
void PrintString(std::string* a_Data)
{
	Map_Type::iterator iter = pointer_count.find(a_Data);
    std::cout << "String " << *iter->first << " has : " << iter->second << " pointer(s)." << std::endl;
}

private:
friend class StringHolder;
typedef std::map<std::string*, int> Map_Type;
Map_Type pointer_count; //A map that counts how many pointers to each std::string exist

};//class U_Ptr

//A class that keeps a pointer to a std::string object
class StringHolder
{
public:
	StringHolder(std::string* a_Data, U_Ptr& a_ptr)
	{
//		ptr = new U_Ptr(a_Data);//creates a pointer to a U_Ptr object
		m_Data = a_Data;
		m_ptr = &a_ptr;
		m_Data = (*m_ptr).AddString(m_Data);
	}

	void operator+=(std::string rhs)
	{
		std::string temp = (*m_Data);
	    temp.append(rhs);
		(*m_Data) = temp;
		(*m_ptr).AddString(m_Data);
//	    std::cout << *m_Data << std::endl;
	}

	~StringHolder()
	{
		(*m_ptr).DeleteString(m_Data);

	}
	void Print()
	{
		(*m_ptr).PrintString(m_Data);
	}

private:
	U_Ptr* m_ptr;
	std::string* m_Data;

};//class StringHolder


int main()
{
	U_Ptr ptr;

	std::string test = "kiri";
	std::string test2 = "Oleg";
	std::string test3 = "kiri";
	std::string* p_test = &test;
	std::string* p_test2 = &test2;
	std::string* p_test3 = &test3;
	StringHolder a(p_test, ptr);
	a.Print();
	StringHolder b(p_test, ptr);
	b.Print();
	b += "Luc";
	b.Print();
	StringHolder c(p_test2, ptr);
	c.Print();
	StringHolder d(p_test3, ptr);
	d.Print();
	return 0;
}

[cire]

What's wrong with the way you do it? Let me count the ways.

To begin with a copy-on-write implementation of a string class should not visible outside of the class. A user of the string shouldn't care how the string's internals are implemented (and thus, should not be required to instantiate or supply a "U_ptr" in order to use the string class.)

U_ptr, what kind of name is that? Looks like it should be some kind of pointer. Is it? No, it's not.

Have you looked at the warnings generated by your compiler?

main.cpp(57): warning C4715: 'U_Ptr::AddString' : not all control paths return a value

In fact if we look at that function we can see that the only time a value is returned is when pointer_count is empty. Given that, what value do you think gets assigned to m_Data in the following code when a_ptr's map is non-empty?

	StringHolder(std::string* a_Data, U_Ptr& a_ptr)
	{
//		ptr = new U_Ptr(a_Data);//creates a pointer to a U_Ptr object
		m_Data = a_Data;
		m_ptr = &a_ptr;
		m_Data = (*m_ptr).AddString(m_Data);
	}

[zanklob]

Yes you are right..I don't know how i missed that.I fixed it and i don't get the Segmentation fault anymore.
But how should i use the class U_Ptr?I used it this way because the U_ptr object as a StringHolder constructor parameter because i couldn't think of another way.
Can you help me a little bit with that?
Thank you so much.

[cire]

If you insist on the use of a map this way (which I wouldn't recommend,) you could make a U_ptr a static member of the string class, and every string object could register with the static member on construction.

[zanklob]

Ok i will give it a shot.
But if you don't recommend the map what would you suggest as an alternative?