SGI STL中string的源碼解讀（1）

STL中string的源碼解讀

Ryan peng

[email protected]

Sunday, June 03, 2007

這是個人最近比較閑暇之餘，對SGI STL中string分析，如果有任何了解錯誤，請和我聯系，謝謝！

為什麼要分析string呢？我們知道大多數的編譯器實作的string都各不相同（即便是同一個編譯廠商在不同的版本string的實作也不一樣，例如MSVC6.0和VS2005中string的實作就不一樣，VC6.0中string的實作是用copy_on_write[COW,寫時拷貝]，VS2005則是直接進行深拷貝）。

以前各個編譯器的廠商對String的實作都是使用COW，但目前string的實作趨勢是直接使用深拷貝，不再使用COW，其主要原因是目前多線程的使用越來越多，COW技術在多線程會帶來額外的性能惡化（原因在于COW在成員函數内部加/解鎖），但是不可否認的是，掌握這些技術仍然很有吸引力，也許會在其他地方使用到。

以SGI STL版本3.4.2為主，閱讀string的源代碼。本文主要分以下幾個部分：

Ø         原子操作的作用和實作；

Ø         STL中的concepts；

Ø         String概述；

Ø         實作計數的結構體Rep_Base和Rep；

«        Rep_Base的定義;

«        Rep的定義；

«        Rep中的幾個主要函數;

Ø         Basic_string的構造函數和析構函數；

Ø         指派構造函數operator=;

Ø         replace函數；

Ø         insert和erase函數；

Ø         swap函數；

Ø         Operator[]函數；

Ø         Reverse和resize函數；

Ø         Swap函數；

Ø         Append和operator+函數；

Ø         其他函數；

Ø         調試版本的string。

最初為了描述的友善，把一些函數/變量進行了修改或者删減，後來發現太麻煩了，就偷懶了，可能導緻前後文中的變量和函數名不一緻。最開始的時候都是是使用字元串來表示，後來發現可能引起大家的誤解，是以後來的描述區分的比較清楚分别使用string對象/string，或者c_style的字元串，但是前面寫的可能需要根據上下文自己判斷了，不好意思了。

1.原子操作的作用和實作

在string中真正存儲的字元串使用COW，也就是說當兩個字元串完全相同時可能（不是一定，取決于編譯器實作string指派和copy構造的方法）指向的是同一塊記憶體，當其中一個string對象被修改時，才為這個string對象建立真正的copy（即配置設定記憶體，并初始化對象），很明顯在單線程情況下，該方法很有效，因為配置設定記憶體很耗時間，而且也可能節約記憶體。COW用的非常廣泛，如Linux下的fork()函數在建立新程序的時候也是使用COW，讓子程序和父程序共享同一程序控制塊。

在string中為了實作COW，必須記錄有多少個對象指向真實的字元串（實際的存儲體在下面會看到對應的資料結構），才能正确的操作string對象。為了正确的實作提供原子操作（即要麼操作成功，要麼什麼也不做），如修改這個記錄的時候需要原子操作，調用一些成員函數的時候需要原子操作。

一般來說原子操作都是作業系統提供的，當然也可以直接通過彙編代碼控制CPU來完成。作業系統一般都會提供mutex，atom，lock等操作，但是不同的作業系統提供的接口不同，也就需要對這些接口進行封裝。這些内容一般在GCC的頭檔案atomicity.h找到。

在此隻簡單的示範兩種方法，看看是怎麼實作的，如下：一個例子（Redhat中的實作）完成引用計數值修改的原子操作，

__exchange_and_add(volatile _Atomic_word* __mem, int __val)

{

        __glibcxx_mutex_lock(__gnu_internal::atomic_mutex);

        Int __result;

        __result = *__mem;

        *__mem += __val;

        __glibcxx_mutex_unlock(__gnu_internal::atomic_mutex);

        return __result;

}

其中__glibcxx_mutex_lock和__glibcxx_mutex_unlock都是封裝好的操作，保證原子操作（如調用作業系統的函數pthread_mutex_lock, pthread_mutex_unlock, pthread_mutex_trylock）。

如果沒有定義上面的函數（準确的說是通過宏調用作業系統的函數），也可以直接通過彙編代碼完成，如下所示：

__exchange_and_add (volatile _Atomic_word *__mem, int __val)

{

register int __result;

__asm__ __volatile__ ("lock; xaddl %0,%2"

                                : "=r" (__result)

: "0" (__val), "m" (*__mem)

: "memory");

return __result;

}

關于C/C++語言中嵌套ASM彙編有很多資料可以參考，這裡簡單分析一下上面的代碼：

lock;

//lock；彙編指令字首，表示後面的指令在CPU上操作是串行完成；當CPU中的控制器檢測到這個字首時候，就會鎖定記憶體總線，一直到該條指令執行完畢，在此期間其它的CPU不能通路這條指令所通路的記憶體單元。

xaddl %0,%2"

//完成加法，其中0表示result，2表示*__mem

: "=r" (__result)

//表示輸出

: "0" (__val), "m" (*__mem)

//表示輸入，__val和__result使用同一個寄存器，*__mem表示在記憶體中；

    : "memory")

    //表示限定限制，memory中的内容被修改

值得注意的是不同類型的CPU對應的彙編也不同，上面的彙編是對應i386結構的。

為了能更好的說明這一部分，再舉一個簡單的例子，這個是針對m68000的實作，利用了C++語言的性質，如下：

template<int __inst>

struct _Atomicity_lock

{

static volatile unsigned char _S_atomicity_lock;

};

template<int __inst>

volatile unsigned char _Atomicity_lock<__inst>::_S_atomicity_lock = 0;

__exchange_and_add(volatile _Atomic_word* __mem, int __val)

{

    int __result;

// Use bset with immediate addressing for 68000/68010 (not SMP-safe)

__asm__ __volatile__("1: bset.b #7,%0/n/tjbne 1b"

                       : "+m"(_Atomicity_lock<0>::_S_atomicity_lock)

                       :

                       : "cc");

__result = *__mem;

__mem = __result + __val;

_Atomicity_lock<0>::_S_atomicity_lock = 0;

return __result;

}

基本思路也是鎖總線，隻不過實作方式不同罷了。

在__exchange_and_add函數前面還要修飾符__attribute__((unused))，這是GCC的擴充，表示該函數或變量可能不使用，這個屬性可以避免編譯器産生警告資訊。

2. STL中的concepts

在衆多的STL的實作中SGI STL的現實相對來說非常好的，在string中也使用到了concepts的概念，首先介紹一下concepts。

概念（Concepts）簡單的說是用于模闆參數的類型系統，對模闆的參數進行限制。模闆因為其獨特的性質，隻有在執行個體點的時候才會真正的生成代碼，那麼也就說按照以前我們所寫的代碼，即便是模闆參數有錯誤，在編譯時候我們也不能得到錯誤，這當然和我們的期望相違背，為了解決這個問題有一些方法如boost庫中使用的限制類，而限制類也存在一些缺點，引入concepts能夠解決很多問題。

下面就簡單的看一下SGI STL中的concepts。

例如我們在assign函數中看到這樣的代碼__glibcxx_requires_string(__s);這些其實是一些宏，和我們原來的方法一樣，它的對應展開就是assert(__s)，還不能說這是concepts。但是下面的例子就是concepts了。

template<typename _Tp>

inline void swap(_Tp& __a, _Tp& __b)

{

// concept requirements

__glibcxx_function_requires(_SGIAssignableConcept<_Tp>)

const _Tp __tmp = __a;

__a = __b;

__b = __tmp;

}

這是STL中swap算法，交換兩個變量，我們知道兩個變量能夠交換的條件就是他們具有可指派性，也就是說我們期望在編譯的時候判斷模闆參數是否具有可指派性，為此上面的範型算法就加入了concepts，對模闆參數進行判斷。Concepts将會通過下面的宏展開：

#define __glibcxx_function_requires(...) /

__gnu_cxx::__function_requires< __gnu_cxx::__VA_ARGS__ >();

template <class _Concept>

inline void __function_requires()

{

void (_Concept::*__x)() _IsUnused = &_Concept::__constraints;

}

其中參數為：

template <class _Tp>

struct _SGIAssignableConcept

{

void __constraints()

{

_Tp __b _IsUnused(__a);

__a = __a;// require assignment operator

__const_constraints(__a);

}

void __const_constraints(const _Tp& __b)

{

_Tp __c _IsUnused(__b);

__a = __b;// const required for argument to assignment

}

_Tp __a;

};

可以看出實際上最後執行的是_SGIAssignableConcept：：__constraints()。

最後要注意一點，STL中的關于concepts不一定打開，如果你要使用concepts應該自己打開編譯開關。

3. string概述

很多資料都告訴了這樣的事實string其實就是使用typedef對下面模版類的别名定義。即basic_string<char, char_traits<char>, allocator<char> > class；typedef basic_string string；其中char_traits<char>也是模版類，主要定義了幾種類型和基本的操作。Allocator<char>也是模版類，主要是進行記憶體管理。當然上面的char也有可能是w_chart，當且僅當我們定義使用寬字元（是通過宏變量來控制）。

basic_string中的模闆參數Char_traits<class type>定義的類型主要有char_type（表明類型），int_type（就是int類型，定義該類型的目的是type可能和int發生類型轉換），pos_type（表明位置資訊），off_type（表明結束資訊）和state_type（表明目前的狀态，其實就是int），基本的操作主要有assign，copy，find，move，eq（等于），lt（小于）。

對于basic_string中的模闆參數allocator<>的分析在《STL源碼剖析》中已經分析的較為詳細，就是進行記憶體管理。

在模版類basic_string中定義了typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;首先請問你是覺得這樣的定義如果不是在模版中正常嗎？你會不會覺得basic_string的定義還沒有完成，怎麼可以看成是一個完整的類型作為參數傳遞呢？噢，這個應該不是問題，為什麼？因為我們隻是定義一個類型，并沒有定義任何變量，當然不用記憶體配置設定，編譯器當然會饒過他繼續編譯不會報錯。其實内部仍然是使用Pointer直接作為它的疊代器，隻不過對Pointer進行了封裝，形成類（重載了++，--，*，->，[]，&，+等操作符）。你會不會覺得這很麻煩，确實是，沒有提供比原始指針更強大的功能，但也要想想為什麼這麼設計，原因就是一個簡單的Pointer不能提供一些類型，如value_type等等（即traits），沒有辦法必須封裝。

4. 實作計數的結構體Rep_Base和Rep

在模闆類basic_string中嵌套定義了這兩個結構體，Rep_base在該結構體中主要進行引用計數的定義和Rep繼承于Rep_base主要是進行引用計數的相關操作和記憶體的配置設定政策，是以這兩個結構體是非常關鍵的。

結構體_Rep_base的定義如下：

Struct _Rep_base

{

    Size_type  _M_length;

    Size_type  _M_capaticty;

    Int        _M_refCount;

};

代碼中有這樣的解釋：

Ø         字元串真正存儲的是原字元串加上一個NULL，故真正的長度是_M_length+1;

Ø         _M_Capacity一定不小于_M_length，而且記憶體的配置設定的增長總是以目前_M_capacity+1為機關；

Ø         _M_refCount的取值可以分為三種：

«        -1：可能記憶體洩露，有一個變量指向字元串，字元串可以被更改，不允許引用copy，也就是當出現這種情況時，這個string對象不會再和其他string對象共享了；

«        0： 有一個變量指向字元串，字元串可以被更改；

«        n>=1:有n+1個變量指向字元串，對字元串操作時應該加鎖，字元串不可以被更改；

Ø         當_M_length，_M_capactiy和_M_refCount均為零，表示空串。

_Rep的定義

_Rep繼承于_Rep_base，同時_Rep中還定義了三個靜态資料成員，這些資料成員都有獨特的意思。size_type    _S_max_size和_CharT  _S_terminal分表表示字元的最大長度和字元串的結束标志（即是’/0’也就是0）。_S_max_size這個值表示可以最大配置設定的記憶體，這個值表示使用1G記憶體配置設定字元串，_S_max_size = (((npos -sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;，其中npos是定義在模版類basic_string中，初始值為-1(也即0xFFFFFFFF)。

定義一個數組size_type _S_empty_rep_storage[];（這并不是一個0長度的數組，0長度的數組是在編譯時并不配置設定空間，僅僅作為占位符），在對應的定義檔案（basic_string.tcc）中有明确的定義，如下_S_empty_rep_storage[ (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /sizeof(size_type)];

最後要注意一下靜态對象初始化的時機，靜态對象一般是在.ini段中完成初始化，即在main函數之前代碼段中完成，一般使用預設的構造函數完成，象上面的數組中的元素會被初始化為0（該數組初始化的結果可表示空串有1個引用）。

_Rep中的幾個主要函數

1. _S_Create配置設定字元串占用的記憶體空間

_S_create(size_type __capacity, size_type __old_capacity,

                const _Alloc& __alloc)

{

const size_type __pagesize = 4096; // must be 2^i * __subpagesize

const size_type __subpagesize = 128;

const size_type __malloc_header_size = 4 * sizeof (void*);

// The biggest string which fits in a memory page

const size_type __page_capacity = ((__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT)) /sizeof(_CharT));

//capacity使用指數增長的方法

if (__capacity > __old_capacity && __capacity < 2 * __old_capacity && __capacity > __page_capacity)

__capacity = 2 * __old_capacity;

size_type __size = (__capacity + 1) * sizeof(_CharT) +sizeof(_Rep); //加1的原因是在字元串最後添加一個’/0’

//根據_M_capacity調整size（真正需要new/malloc的記憶體大小）

const size_type __adj_size = __size + __malloc_header_size;

if (__adj_size > __pagesize)

{

const size_type __extra = __pagesize - __adj_size % __pagesize;

__capacity += __extra / sizeof(_CharT);

// Never allocate a string bigger than _S_max_size.

if (__capacity > _S_max_size)

__capacity = _S_max_size;

__size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);

}

else if (__size > __subpagesize)

{

const size_type __extra = __subpagesize - __adj_size % __subpagesize;

__capacity += __extra / sizeof(_CharT);

__size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);

}

//注意這裡是配置設定大小為size的記憶體，不是上面的adjsize，因為mallocheadersize是在new/malloc系統增加的

void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);

_Rep *__p = new (__place) _Rep;

__p->_M_capacity = __capacity;

__p->_M_set_sharable();  // One reference.，設定共享标志

 __p->_M_length = 0;

return __p;

}

上面的函數中幾個常量的含義是了解函數的關鍵，弄清楚這幾個常量這個函數的實作也就明白，這幾個變量的作用如下：

1.    __pageSize的大小是指在配置設定記憶體的時候使用的，很類似于實際中virtual memory（但是和實際中virtual memory的大小無關），__pageSize是每次記憶體配置設定的最小機關；

2.    __subPageSize的大小是每次配置設定的字元串必須以__subPageSize對齊，顯然這可以加快配置設定速度，不必要每次都對齊，但是顯然可能浪費了空間；

3.    __mallocHeaderSize的意思是這樣的，我們在malloc記憶體的時候，每次調用new/malloc都會比真正的所需要的記憶體大上幾個位元組（一般來說是4個位元組），這幾個位元組是存儲的是配置設定記憶體的真正的長度。【源碼中的注釋說這個可以為N ×sizeof(void*)（其中N＝0，2，4），并且寫到，據說N大比小好，是以取4，實際（vc/dev）中new/malloc附加的空間都是4個位元組而已，即1×sizeof(void*)】；

4.    字元串的存儲示意圖如下： 

_Rep             string

__P

2. _M_refdata傳回字元串的記憶體位置

_CharT* _M_refdata() throw()

{

return reinterpret_cast<_CharT*>(this + 1);

}

這個函數非常簡單，隻要注意一點，那就是this ＋ 1真正的位置。This指的是從頭開始的記憶體位址，this + 1就是上圖中的__P所指的位置（1就是sizeof(_Rep)）。

3. _M_colne建立新的字元串空間和資訊

_M_clone(const _Alloc& __alloc, size_type __res)

{

// Requested capacity of the clone.

const size_type __requested_cap = this->_M_length + __res;

//配置設定空間

_Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,

__alloc);

    //copy對應的字元串

if (this->_M_length)

traits_type::copy(__r->_M_refdata(),_M_refdata(),this->_M_length);

    //設定字元串的長度和結束标志

__r->_M_length = this->_M_length;

__r->_M_refdata()[this->_M_length] = _Rep::_S_terminal;

return __r->_M_refdata();

}

4. _M_refdata僅僅增加計數資訊

_CharT*    _M_refcopy() throw()

{

    if(__builtin_expect(this != &_S_empty_rep(), false))

__gnu_cxx::__atomic_add(&this->_M_refcount, 1);

    return _M_refdata();

}

__builtin_expect(x,expected_value)是GCC提供的實作的一個内部函數，其值就是x，但x的值等于expected_value的可能較大，這可以讓gcc産生較好的跳轉代碼。這隻是一種優化寫法。

If判斷完成的就是，this不是空串，則為真，執行原子操作，為計數值加1.

5. _M_grab是clone和refdata的入口判斷

_CharT*    _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)

{

    return (!_M_is_leaked() && __alloc1 == __alloc2)

               ? _M_refcopy() : _M_clone(__alloc1);

}

在這個函數中将判斷是進行引用計數加1還是重建立立一個新的字元串。必須說明的該函數隻有才basic_string的copy ctor和assignment（指派指的是相同類型的指派，當有str ＝“123”,這将是調用構造函數，即便是有很多的這樣的語句也不會調用引用計數的）中才可能被調用，也就是說在有在新的字元串按copy或者指派建立的時候才考慮使用引用計數。

進行refcopy或者clone的關鍵辨別是：首先沒有記憶體洩漏标志（關于這個标志主要是禁止string再次被共享，後面會有具體的描述），然後就是兩個string對象的配置設定相同。

6. _M_destroy釋放空間

_M_destroy(const _Alloc& __a) throw ()

{

//如果不是空串，将釋放空間

if (this == &_S_empty_rep())    return;

//調整釋放空間的大小，這才是真正需要釋放的大小

const size_type __size = sizeof(_Rep_base) + (this->_M_capacity + 1) * sizeof(_CharT);

//_Raw_bytes_alloc是allocator類型

_Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);

}

7. _M_dispose減少引用計數值并決定釋放空間

void   _M_dispose(const _Alloc& __a)

{

    if (__builtin_expect(this != &_S_empty_rep(), false))

       if (__gnu_cxx::__exchange_and_add(&this->_M_refcount, -1) <=0)

           _M_destroy(__a);

}

當引用計數值小于等于0的時候，已經表示沒有字元串指向這塊記憶體，需要釋放。注意這個地方的等于0也釋放記憶體的，和我們最初所說的0表示一個引用有沖突的。但是注意這裡是完全正确的，__exchange_and_add()函數傳回的是沒有修改前的值，是以傳回值為0其實真實的refcount已經為-1了。

Rep 中其他簡單的函數如設定 length ， capacity ， refcount 等都比較簡單。