29-Reference counting（引用计数）

第五章，技术

29-Reference counting（引用计数）

共享同一个“引用计数与数据”

class String {
public:
	String(const char *initValue = "")
		: value(new StringValue(initValue))
	{
		++value->refConunt;
	}

	String(const String& rhs)
	{
		value = rhs.value; // 同类对象可直接访问 private 成员 value
		++value->refConunt;
	}

	~String()
	{
		if (--value->refConunt == 0) delete value;
	}

	String& String::operator=(const String& rhs)
	{
		if (value == rhs.value) {
			return *this;
		}

		if (--value->refConunt == 0) { //因为不确定左边这个对象之前指向的是那一块内存，所以需要先判断它是不是最后一个引用，然后决定是否要释放它之前指向的东西
			delete value;
		}

		value = rhs.value;
		++value->refConunt;//重新记录当前指向的内容和引用计数

		return *this;
	}

private:
	//共享资源
	struct StringValue {
		int refConunt;
		char *data;

		StringValue(const char* initValue) :refConunt(1)
		{
			data = new char[strlen(initValue) + 1];
			strcpy(data, initValue);
		}
		~StringValue()
		{
			delete[] data;
		}
	};

	StringValue *value;
};

写时复制(Copy-on-Write)

和其他对象共享一份实值，直到必须对自己所拥有的那一份实值进行写动作时，单独复制出一个副本。
写时复制仍在计算机科学领域有很长历史，特别是操作系统领域： 各进程之间往往允许共享某些内存分页，直到它们打算修改属于自己的那一分页。

//操作符[]提供读写数据功能
const char& String::operator[](int index) const //用于读取
{
   return value->data[index];
}

char& String::operator[](int index)//用于写时复制
{
	if(value->refCount > 1){
		--value->refConunt; //不再拥有原来的共享数据，引用计数-1
		value = new StringValue(value->data); //单独做一份副本为自己使用
	}

	return value->data[index];
}

写时复制在工程中可能导致的问题：

String s1 = "Hellow";
char *p = &s1[1];
String s2 = s1;
*p = 'x'; //嗯~共享数据被污染了

解决方法1：忽视，假装不存在(我不明白为什么会把这个写在解决方法里面，可能是有一些人就是这样做的情况比较典型，原著要嘲讽一下)
解决方法2：注释说明（鸡肋）
解决方法3：添加共享标识flag，一旦调用了operator[]，就让flag置为false，不可共享

视线回到现在(公元2025年),现代的C++以及放弃了COW(写时复制)，而是使用SSO(小字符串优化)+立即复制+移动语义;
那么，我知道我很想马上知道现代的C++是什么样的，但是我劝我自己先别急，而是问，这个COW还有什么学习的必要：
1、引用计数、深拷贝浅拷贝、运算符重载的理解
2、设计缺陷分析能力
3、其他一些领域仍在使用：操作系统，数据库，容器技术(Docker)，游戏引擎等，这是一个使用广泛且历史长的技术概念

OK,看一下现代C++是怎么实现的:

彻底放弃共享，每个 string 独立拥有数据! 用 SSO + 立即复制替代 COW

SSO : 小字符串直接存在对象内部，不用堆分配

传统 string（无 SSO）：
┌─────────┐
│  string │     ┌───────────┐
│ 对象    │────→│ 堆内存    │
│(8字节)   │     │ "hello"   │
│ 存指针   │     │(6字节)    │
└─────────┘     └───────────┘
总计：8 + 6 = 14字节（两次内存访问）

SSO string（现代 C++）：
┌─────────────────────┐
│      string 对象    │
│ ┌─────────────────┐ │
│ │ buffer[16]      │ │  ← "hello\0" 直接存在这里！
│ │ "hello\0□□□□□□□"│ │    □ = 未使用
│ ├─────────────────┤ │
│ │ 其他成员        │ │
│ └─────────────────┘ │
└─────────────────────┘
总计：16字节（一次内存访问，无堆分配）

class String {
    char buffer[16];   // 预留16字节内部空间
    char* ptr;         // 大字符串时才用
    
    String(const char* s) {
        if (strlen(s) <= 15) {
            memcpy(buffer, s, strlen(s)+1);  // 存内部，快！
            ptr = buffer;
        } else {
            ptr = new char[strlen(s)+1];      // 太长，只好堆分配
            memcpy(ptr, s, strlen(s)+1);
        }
    }
};

立即复制： 拷贝时立刻复制数据，绝不共享

COW（写时复制）- 延迟复制，共享数据：
s1 = "hello"
┌─────┐         ┌───────────┐
│ s1  │────────→│ "hello"   │
│     │         │ ref: 1    │
└─────┘         └───────────┘

s2 = s1（COW）
┌─────┐         ┌───────────┐
│ s1  │────────→│ "hello"   │←────┐
│     │         │ ref: 2    │     │
└─────┘         └───────────┘     │
                                  │
┌─────┐                           │
│ s2  │───────────────────────────┘
│     │
└─────┘
问题：s1 和 s2 共享同一块内存！修改会互相影响

立即复制（现代 C++）- 拷贝时立刻独立：
s1 = "hello"
┌─────┐         ┌───────────┐
│ s1  │────────→│ "hello"   │
│     │         │（独立）    │
└─────┘         └───────────┘

s2 = s1（立即复制）
┌─────┐         ┌───────────┐
│ s1  │────────→│ "hello"   │  ← s1 的数据
│     │         │（独立）    │
└─────┘         └───────────┘
                ┌───────────┐
┌─────┐         │ "hello"   │  ← s2 的数据（新分配，内容复制）
│ s2  │────────→│（独立）    │
│     │         └───────────┘
└─────┘
结果：s1 和 s2 完全独立！修改互不影响

// 拷贝构造：立即复制，绝不共享
String(const String& rhs) {
    // 不管 rhs 多大，立刻分配新内存复制内容
    size_t len = strlen(rhs.ptr);
    ptr = new char[len + 1];
    memcpy(ptr, rhs.ptr, len + 1);  // 立刻复制！
    // 没有引用计数，没有共享标志，简单粗暴安全
}

嗯，这么看来，现代的处理手法更加直接，反而没有引用计数和COW那样巧妙，但是大巧不工，也规避了复杂带来的问题。

一个Reference-Counting(引用计数)基类

为了将引用计数可以广泛的被简易使用，可以设计一个基类，继承它就将获得引用计数相关的能力

class RCObject{
public:
	RCObject();
	RCObject(const RCObject& rhs);
	RCObject& operator=(const RCObject& rhs);
	void addReference();
	void removeReference();
	void markUnshareable() const;
	bool isShareable() const;
	bool isShared() const;

protected:
	virtual ~RCObject() = 0;//析构函数变成protected，可继承的同时，强制对象必须产生于heap之上，确保成员函数中的delete this操作可以正常执行

private:
	int refCount;
	bool shareable;
};

RCObject::RCObject()
  : refCount(0), shareable(true){}//refCount初设为0，由派生类来置为1

RCObject::RCObject(const RCObject&)
  : refCount(0), shareable(true){}

RCObject& RCObject::operator=(const RCObject& rhs)
{ return *this; }

RCObject::~RCObject(){}

void RCObject::addReference(){ ++refConunt; }

void RCObject::removeReference()
{ if(--refCount == 0) delete this;}

bool RCObject::isShareable() const
{ return shareable; }

bool RCObject::isShared() const
{ return refConunt > 1; }

运用

class String{
private:
	struct StringValue: public RCObject{
        char *data;
        StringValue(const char *initValue);
        ~StringValue();
    };//相比之前的代码，删除了refCount，改为继承RCObject实现计数功能
    ...
};

String::StringValue::StringValue(const char *initValue)
{
	data = new char[strlen(initValue) + 1];
	strcpy(data,initValue);
}

String::StringValue::~StringValue()
{
	delete[] data;
}

//嗯~让一个嵌套类继承另一个类，而后者与外围类完全无关，这样的设计也是别具一格，但恰到好处

自动操作Reference Count(引用次数)

结合智能指针，使得可以自动调用RCObject中计数相关的成员函数，而不是手动安插

template<class T>
class RCPtr{
public:
	RCPtr(T* realPtr = 0);
	RCPtr(const RCPtr& rhs);
	~RCPtr();
 
    RCPtr& operator=(const RCPtr& rhs);
    T* operator->() const;
    T& operator*() const;
private:
	T *pointee;
	void init();//共同初始化动作
};

template<class T>
RCPtr<T>::RCPtr(T* realPtr):pointee(realPtr)
{
	init();
}

template<class T>
RCPtr<T>::RCPtr(const RCPtr& rhs):pointee(rhs.pointee)
{
    init();
}

template<class T>
RCPtr<T>::init()
{
   if(pointee == 0){
   	 return;
   }
   if(pointee->isShareable() == false){
   	 pointee = new T(*pointee);
   }
   pointee->addReference();//自动调用RCObject中的添加计数
}

/*init的关键问题
pointee = new T(*pointee);分配完空间后会调用T的拷贝构造函数进行初始化，
但是！如果T没有拷贝构造函数呢？假如这个T就是StringValue,而StringValue只有StringValue(const char* initValue)这一个构造函数，
pointee就是一个StringValue类型的指针，需要拷贝构造函数，于是编译器给出默认拷贝构造，但是这是浅拷贝。

编译器生成的默认拷贝构造：
StringValue(const StringValue& rhs)
    : refCount(rhs.refCount),  
      data(rhs.data)//data指针指向rhs.data，浅拷贝

后续这极有可能会引发双重释放！导致程序崩溃 ;
这就是为什么要为所有内含指针的classes撰写copy constructor及assignment operator的原因
*/

重点提醒： 为所有内含指针的classes撰写copy constructor及assignment operator

发现上述浅拷贝的问题后，马上修补StringValue

class String{
private:
	struct StringValue: public RCObject{
       StringValue(const StringValue& rhs);
       ...
	};
	...
};

String::StringValue::StringValue(const StringValue& rhs)//提供默认拷贝构造深拷贝
{
   data = new char[strlen(rhs.data) + 1];
   strcpy(data,rhs.data);
}

继续回来，实现RCPtr的其他地方

//赋值操作符重载
template<class T>
RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
{
   if(pointee != rhs.pointee){
   	 if(pointee){
   	 	pointee->removeReference();//移除当前实值引用次数
   	 }
   	 pointee = rhs.pointee;//指向新的实值
   	 init(); //是否共享(添加引用次数)，否则创建副本
   }
   return *this;
}

//析构
template<class T>
RCPtr<T>::~RCPtr()
{
   if(pointee) pointee->removeReference();
}

// 复习一下，引用计数管理heap上的资源，实现自动释放的机制就是每一个拥有资源控制权的对象在析构时都会检查一下引用计数是否为0，为0则释放。

//“指针模拟”
template<class T>
T* RCPtr<T>::operator-() const { return pointee; }

template<class T>
T& RCPtr<T>::operator*() const { return *pointee; }

把所有努力放在一起

template<class T>
class RCPtr {                          // template class，用来产生
public:                                // smart-pointers-to-T objects;
    RCPtr(T* realPtr = 0);             // T 必须继承自 RCObject。
    RCPtr(const RCPtr& rhs);
    ~RCPtr();
    
    RCPtr& operator=(const RCPtr& rhs);
    
    T* operator->() const;
    T& operator*() const;
    
private:
    T *pointee;
    
    void init();
};

class RCObject {                       // base class，用于 reference-counted objects。
public:
    void addReference();
    void removeReference();
    
    void markUnshareable();
    bool isShareable() const;
    
    bool isShared() const;
    
protected:
    RCObject();
    RCObject(const RCObject& rhs);
    RCObject& operator=(const RCObject& rhs);
    virtual ~RCObject() = 0;
    
private:
    int refCount;
    bool shareable;
};

class String {                         // 应用性 class，这是应用程序开发人员接触的层面。
public:
    String(const char *value = "");
    
    const char& operator[](int index) const;
    char& operator[](int index);
    
private:
    // 以下 struct 用以表现字符串实值。
    struct StringValue: public RCObject {
        char *data;
        
        StringValue(const char *initValue);
        StringValue(const StringValue& rhs);
        void init(const char *initValue);//功用和RCPtr的同名函数相同，只是将构造函数内重复代码集中起来
        ~StringValue();
    };
    
    RCPtr<StringValue> value;
};

//突然，发现String class的公开接口中，copy constructor和assignment operator，destrucor都没有了，但是这一切却运作得很完美。（嗯，原著是这么说的）

/*1、为什么String class不需要拷贝构造函数了？

因为编译器会自己产生默认构造函数，然后调用RCPtr member的拷贝构造函数RCPtr(const RCPtr& rhs);它会执行对StringValue对象的所有必要处理，包括引用次数。

// 编译器自动生成：
String(const String& rhs)          // 默认拷贝构造
    : value(rhs.value)             // ✅ 自动调用 RCPtr 的拷贝构造！
{}

//🌟C++ 规则：如果类有成员，默认拷贝构造会逐成员调用成员的拷贝构造
*/

//RCObject
RCObject::RCObject()
: refCount(0), shareable(true) {}

RCObject::RCObject(const RCObject&)
: refCount(0), shareable(true) {}

RCObject& RCObject::operator=(const RCObject&)
{ return *this; }

RCObject::~RCObject() {}

void RCObject::addReference() { ++refCount; }

void RCObject::removeReference()
{ if (--refCount == 0) delete this; }

void RCObject::markUnshareable()
{ shareable = false; }

bool RCObject::isShareable() const
{ return shareable; }

bool RCObject::isShared() const
{ return refCount > 1; }


//RCPtr
template<class T>
void RCPtr<T>::init()
{
    if (pointee == 0) return;
    if (pointee->isShareable() == false) {
        pointee = new T(*pointee);
    }
    pointee->addReference();
}

template<class T>
RCPtr<T>::RCPtr(T* realPtr)
: pointee(realPtr)
{ init(); }

template<class T>
RCPtr<T>::RCPtr(const RCPtr& rhs)
: pointee(rhs.pointee)
{ init(); }

template<class T>
RCPtr<T>::~RCPtr()
{ if (pointee)pointee->removeReference(); }

template<class T>
RCPtr<T>& RCPtr<T>::operator=(const RCPtr& rhs)
{
    if (pointee != rhs.pointee) {
        if (pointee) pointee->removeReference();
        pointee = rhs.pointee;
        init();
    }
    return *this;
}

template<class T>
T* RCPtr<T>::operator->() const { return pointee; }

template<class T>
T& RCPtr<T>::operator*() const { return *pointee; }


//StringValue
void String::StringValue::init(const char *initValue)
{
    data = new char[strlen(initValue) + 1];
    strcpy(data, initValue);
}

String::StringValue::StringValue(const char *initValue)
{ init(initValue); }

String::StringValue::StringValue(const StringValue& rhs)
{ init(rhs.data); }

String::StringValue::~StringValue()
{ delete [] data; }


//String
String::String(const char *initValue)
: value(new StringValue(initValue)) {}

const char& String::operator[](int index) const
{ return value->data[index]; }

char& String::operator[](int index)
{
    if (value->isShared()) {
        value = new StringValue(value->data);
    }
    value->markUnshareable();
    return value->data[index];
}

将Reference Counting加到既有的Classes身上

再进一步设计，为任何类型加上reference counting能力，包括无法修改源码的程序库中的类！

加上一层间接性，添加一个新的CountHolder class，用以持有引用计数；将CountHolder继承RCObject，然后令CountHolder内含一个需要拥有引用计数能力的类对象。

剩余的和之前代码差不多（存在细节差异），大体是将内含的StringValue变成了CountHolder

template<class T>
class RCIPtr {
public:
    RCIPtr(T* realPtr = 0);
    RCIPtr(const RCIPtr& rhs);
    ~RCIPtr();
    
    RCIPtr& operator=(const RCIPtr& rhs);
    
    const T* operator->() const;    // 稍后会解释为什么
    T* operator->();                // 这些函数以此方式声明。
    
    const T& operator*() const;
    T& operator*();
    
private:
    struct CountHolder: public RCObject {
        ~CountHolder() { delete pointee; }
        T *pointee;
    };
    
    CountHolder *counter;
    void init();
    void makeCopy();    // 见稍后说明
};

template<class T>
void RCIPtr<T>::init()
{
    if (counter->isShareable() == false) {
        T *oldValue = counter->pointee;
        counter = new CountHolder;
        counter->pointee = new T(*oldValue);
    }
    counter->addReference();
}

template<class T>
RCIPtr<T>::RCIPtr(T* realPtr)
: counter(new CountHolder)
{
    counter->pointee = realPtr;
    init();
}

template<class T>
RCIPtr<T>::RCIPtr(const RCIPtr& rhs)
: counter(rhs.counter)
{ init(); }

template<class T>
RCIPtr<T>::~RCIPtr()
{ counter->removeReference(); }

template<class T>
RCIPtr<T>& RCIPtr<T>::operator=(const RCIPtr& rhs)
{
    if (counter != rhs.counter) {
        counter->removeReference();
        counter = rhs.counter;
        init();
    }
    return *this;
}

template<class T>
const T* RCIPtr<T>::operator->() const    // const access;
{ return counter->pointee; }               // 不需要 COW。

template<class T>
const T& RCIPtr<T>::operator*() const     // const access;
{ return *(counter->pointee); }            // 不需要 COW。


/*RCIPtr和RCPtr的差异：
1、“RCPtr对象”直接指向实值，而“RCIPtr对象”通过中介层“CountHolder对象”指向实值
2、RCIPtr将operator->和operator*重载了，如此依赖只要有non-const access发生于被指物上，copy-on-write就会自动执行
*/


/*补充说明makeCopy
// 实现出 copy-on-write (COW)
// 中的 copy 部分。
template<class T>
void RCIPtr<T>::makeCopy()
{
    if (counter->isShared()) {
        T *oldValue = counter->pointee;
        counter->removeReference();
        counter = new CountHolder;
        counter->pointee = new T(*oldValue);
        counter->addReference();
    }
}

// non-const access;
// 需要 COW。
template<class T>
T* RCIPtr<T>::operator->()
{ makeCopy(); return counter->pointee; }

// non-const access;
// 需要 COW。
template<class T>
T& RCIPtr<T>::operator*()
{ makeCopy(); return *(counter->pointee); }
*/

有了RCIPtr，RCWidget是实现就很容易，因为RCWidget的每一个函数都只是通过底层的RCIPtr转调用对应的Widget函数。

class Widget {
public:
    Widget(int size);
    Widget(const Widget& rhs);
    ~Widget();
    Widget& operator=(const Widget& rhs);
    void doThis();
    int showThat() const;
};

class RCWidget {
public:
    RCWidget(int size) : value(new Widget(size)) {}
    void doThis() { value->doThis(); }
    int showThat() const { return value->showThat(); }
private:
    RCIPtr<Widget> value;
};

OK了，家人们，结束了终于！最后让我总结一下：

/*
1. Reference counting 的成本
每个对象需额外内存存储引用计数器
大部分操作需查验/处理引用计数
源代码复杂度增加

2. 适用时机
多数对象共享少量实值（对象/实值比例高）
对象产生/销毁成本高、使用内存大

3. 不适用场景
循环引用结构（有向图等）→ 引用计数永不归零
未使用对象群互相指向，无法释放

4. 额外收益
解决"不确定谁删除"的内存管理负担

5. 关键约束
delete this  要求对象必须  new  分配
需确保 RCObjects 只以  new  产生

6. 实现方式
惯例规范：RCObject 作为基类
StringValue 作为 String 私有成员
限制产出权给特定类（如 String)
*/