最近看空間配置器的內容，把ACE的ACE_Allocator類實現，SGI的allocator類實現和MS的allocator實現也參考了侯捷先生的《STL源碼剖析》，有不少收獲。
我聽說是有說明STL中allocator實現標准的文件，但我沒有找到，據我實驗推測，標准allocator需要實現rebind，allocate，deallocate，max_size和構造及析構函數一共六個函數。也就是說，我要寫一個在標准vector可用的allocator最小只需要上面的幾個接口實現就可以了。
先來說一下微軟的allocator。文件名是xmemory，我覺得是最沒有看頭的，基本就是new和delete的封裝，為了迎合C++標准庫的標准做的。沒有什麼技巧，更別說微妙了。上面的六個接口下面都有實現。
[cpp]
// TEMPLATE CLASS allocator
emplate<class _Ty>
class allocator
: public _Allocator_base<_Ty>
{ // generic allocator for objects of class _Ty
ublic:
typedef _Allocator_base<_Ty> _Mybase;
typedef typename _Mybase::value_type value_type;
typedef value_type _FARQ *pointer;
typedef value_type _FARQ& reference;
typedef const value_type _FARQ *const_pointer;
typedef const value_type _FARQ& const_reference;
typedef _SIZT size_type;
typedef _PDFT difference_type;
template<class _Other>
struct rebind
{ // convert an allocator<_Ty> to an allocator <_Other>
typedef allocator<_Other> other;
};
pointer address(reference _Val) const
{ // return address of mutable _Val
return (&_Val);
}
const_pointer address(const_reference _Val) const
{ // return address of nonmutable _Val
return (&_Val);
}
allocator() _THROW0()
{ // construct default allocator (do nothing)
}
allocator(const allocator<_Ty>&) _THROW0()
{ // construct by copying (do nothing)
}
template<class _Other>
allocator(const allocator<_Other>&) _THROW0()
{ // construct from a related allocator (do nothing)
}
template<class _Other>
allocator<_Ty>& operator=(const allocator<_Other>&)
{ // assign from a related allocator (do nothing)
return (*this);
}
void deallocate(pointer _Ptr, size_type)
{ // deallocate object at _Ptr, ignore size
::operator delete(_Ptr);
}
pointer allocate(size_type _Count)
{ // allocate array of _Count elements
return (_Allocate(_Count, (pointer)0));
}
pointer allocate(size_type _Count, const void _FARQ *)
{ // allocate array of _Count elements, ignore hint
return (allocate(_Count));
}
void construct(pointer _Ptr, const _Ty& _Val)
{ // construct object at _Ptr with value _Val
_Construct(_Ptr, _Val);
}
void destroy(pointer _Ptr)
{ // destroy object at _Ptr
_Destroy(_Ptr);
}
_SIZT max_size() const _THROW0()
{ // estimate maximum array size
_SIZT _Count = (_SIZT)(-1) / sizeof (_Ty);
return (0 < _Count ? _Count : 1);
}
};
2. SGI STL實現的allocator。作為C++作者都主推的STL實現版本，當然是符合標准的。它的主站：http://www.sgi.com/tech/stl/ ，怎麼去配置調試我已經在上一篇講過了。它的實現通過閱讀侯捷先生的書得到更深入的了解。當然代碼與侯先生解析的那個版本有一些不同，無非是加了一些代理以及包裝之類的，影響不大。我們可以看到這些接口大都通過__sgi_alloc中的函數去實現。
[cpp]
template <class _Tp>
struct __stlport_class
{ typedef _Tp _Type; };
template <class _Tp>
class allocator //: public _AllocatorAux<_Tp>
/* A small helper struct to recognize STLport allocator implementation
* from any user specialization one.
*/
: public __stlport_class<allocator<_Tp> >
{
public:
typedef _Tp value_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
#if defined (_STLP_MEMBER_TEMPLATE_CLASSES)
template <class _Tp1> struct rebind {
typedef allocator<_Tp1> other;
};
#endif
allocator() _STLP_NOTHROW {}
#if defined (_STLP_MEMBER_TEMPLATES)
template <class _Tp1> allocator(const allocator<_Tp1>&) _STLP_NOTHROW {}
#endif
allocator(const allocator<_Tp>&) _STLP_NOTHROW {}
#if !defined (_STLP_NO_MOVE_SEMANTIC)
allocator(__move_source<allocator<_Tp> > src) _STLP_NOTHROW {}
#endif
~allocator() _STLP_NOTHROW {}
pointer address(reference __x) const {return &__x;}
const_pointer address(const_reference __x) const { return &__x; }
// __n is permitted to be 0. The C++ standard says nothing about what the return value is when __n == 0.
_Tp* allocate(size_type __n, const void* = 0) {
if (__n > max_size()) {
_STLP_THROW_BAD_ALLOC;
}
if (__n != 0) {
size_type __buf_size = __n * sizeof(value_type);
_Tp* __ret = __REINTERPRET_CAST(_Tp*, __sgi_alloc::allocate(__buf_size));
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__ret, _STLP_SHRED_BYTE, __buf_size);
#endif
return __ret;
}
return 0;
}
// __p is permitted to be a null pointer, only if n==0.
void deallocate(pointer __p, size_type __n) {
_STLP_ASSERT( (__p == 0) == (__n == 0) )
if (__p != 0) {
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__p, _STLP_SHRED_BYTE, __n * sizeof(value_type));
#endif
__sgi_alloc::deallocate((void*)__p, __n * sizeof(value_type));
}
}
#if !defined (_STLP_NO_ANACHRONISMS)
// backwards compatibility
void deallocate(pointer __p) const { if (__p != 0) __sgi_alloc::deallocate((void*)__p, sizeof(value_type)); }
#endif
size_type max_size() const _STLP_NOTHROW { return size_t(-1) / sizeof(value_type); }
void construct(pointer __p, const_reference __val) { _STLP_STD::_Copy_Construct(__p, __val); }
void destroy(pointer __p) { _STLP_STD::_Destroy(__p); }
#if defined (_STLP_NO_EXTENSIONS)
/* STLport extension giving rounded size of an allocated memory buffer
* This method do not have to be part of a user defined allocator implementation
* and won't even be called if such a function was granted.
*/
protected:
#endif
_Tp* _M_allocate(size_type __n, size_type& __allocated_n) {
if (__n > max_size()) {
_STLP_THROW_BAD_ALLOC;
}
if (__n != 0) {
size_type __buf_size = __n * sizeof(value_type);
_Tp* __ret = __REINTERPRET_CAST(_Tp*, __sgi_alloc::allocate(__buf_size));
#if defined (_STLP_DEBUG_UNINITIALIZED) && !defined (_STLP_DEBUG_ALLOC)
memset((char*)__ret, _STLP_SHRED_BYTE, __buf_size);
#endif
__allocated_n = __buf_size / sizeof(value_type);
return __ret;
}
return 0;
}
#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
void _M_swap_workaround(allocator<_Tp>& __other) {}
#endif
};
在我調試的時候是用內存分配函數_M_allocate來從內存池（按侯先生的說法是空間，不一定是內存）中分配可用空間到自由鏈以及返回用戶使用。若想更進一步了解，必須自己去看源代碼：RTFSC。小結一下，SGI 的這份代碼符合標准規范，結合侯先生的書，可以讓你看清STL的實現本質。
3. 最後說一下ACE的allocator實現。應該說，ACE的實現可能在設計的時候，就不打算遵守C++標准庫的規范，只是為了高效安全的在ACE內部使用。我們也可以看以下接口代碼。基類ACE_Allocator直接使用了malloc和free讓子類去實現。這份代碼完全可以結合侯先生的書來看，只是在一些實現的名字前面加上ACE或者_S等前綴，實現的原理和SGI是很相似的。在內存塊管理方面，小塊內存（小於128），也是用自由鏈去管理，大塊內存（大於128）直接分配。在自由鏈表方面它也使用了一個和SGI一樣的小技巧，就是把next指針放在未使用內存塊的開頭處（我第一次看到這種技巧，有點怪怪的，但是能很好的實現，主要是效率有提升，多少就不考究了）。比SGI加多了一個block塊鏈的管理，可以更靈活的使用（應該是限於ACE的應用了，因為它不遵守標准）。
[cpp]
class ACE_Export ACE_Allocator
{
public:
/// Unsigned integer type used for specifying memory block lengths.
typedef size_t size_type;
// = Memory Management
/// Get pointer to a default ACE_Allocator.
static ACE_Allocator *instance (void);
/// Set pointer to a process-wide ACE_Allocator and return existing
/// pointer.
static ACE_Allocator *instance (ACE_Allocator *);
/// Delete the dynamically allocated Singleton
static void close_singleton (void);
/// "No-op" constructor (needed to make certain compilers happy).
ACE_Allocator (void);
/// Virtual destructor
virtual ~ACE_Allocator (void);
/// Allocate @a nbytes, but don't give them any initial value.
virtual void *malloc (size_type nbytes) = 0;
/// Allocate @a nbytes, giving them @a initial_value.
virtual void *calloc (size_type nbytes, char initial_value = '\0') = 0;
/// Allocate <n_elem> each of size @a elem_size, giving them
/// @a initial_value.
virtual void *calloc (size_type n_elem,
size_type elem_size,
char initial_value = '\0') = 0;
/// Free <ptr> (must have been allocated by <ACE_Allocator::malloc>).
virtual void free (void *ptr) = 0;
/// Remove any resources associated with this memory manager.
virtual int remove (void) = 0;
// = Map manager like functions
/**
* Associate @a name with @a pointer. If @a duplicates == 0 then do
* not allow duplicate @a name/@a pointer associations, else if
* @a duplicates != 0 then allow duplicate @a name/@a pointer
* assocations. Returns 0 if successfully binds (1) a previously
* unbound @a name or (2) @a duplicates != 0, returns 1 if trying to
* bind a previously bound @a name and @a duplicates == 0, else
* returns -1 if a resource failure occurs.
*/
virtual int bind (const char *name, void *pointer, int duplicates = 0) = 0;
/**
* Associate @a name with @a pointer. Does not allow duplicate
* @a name/@a pointer associations. Returns 0 if successfully binds
* (1) a previously unbound @a name, 1 if trying to bind a previously
* bound @a name, or returns -1 if a resource failure occurs. When
* this call returns @a pointer's value will always reference the
* void * that @a name is associated with. Thus, if the caller needs
* to use @a pointer (e.g., to free it) a copy must be maintained by
* the caller.
*/
virtual int trybind (const char *name, void *&pointer) = 0;
/// Locate @a name and pass out parameter via pointer. If found,
/// return 0, returns -1 if failure occurs.
virtual int find (const char *name, void *&pointer) = 0;
/// Returns 0 if the name is in the mapping. -1, otherwise.
virtual int find (const char *name) = 0;
/// Unbind (remove) the name from the map. Don't return the pointer
/// to the caller
virtual int unbind (const char *name) = 0;
/// Break any association of name. Returns the value of pointer in
/// case the caller needs to deallocate memory.
virtual int unbind (const char *name, void *&pointer) = 0;
// = Protection and "sync" (i.e., flushing memory to persistent
// backing store).
/**
* Sync @a len bytes of the memory region to the backing store
* starting at @c this->base_addr_. If @a len == -1 then sync the
* whole region.
*/
virtual int sync (ssize_t len = -1, int flags = MS_SYNC) = 0;
/// Sync @a len bytes of the memory region to the backing store
/// starting at @a addr.
virtual int sync (void *addr, size_type len, int flags = MS_SYNC) = 0;
/**
* Change the protection of the pages of the mapped region to @a prot
* starting at <this->base_addr_> up to @a len bytes. If @a len == -1
* then change protection of all pages in the mapped region.
*/
virtual int protect (ssize_t len = -1, int prot = PROT_RDWR) = 0;
/// Change the protection of the pages of the mapped region to @a prot
/// starting at @a addr up to @a len bytes.
virtual int protect (void *addr, size_type len, int prot = PROT_RDWR) = 0;
#if defined (ACE_HAS_MALLOC_STATS)
/// Dump statistics of how malloc is behaving.
virtual void print_stats (void) const = 0;
#endif /* ACE_HAS_MALLOC_STATS */
/// Dump the state of the object.
virtual void dump (void) const = 0;
private:
// DO NOT ADD ANY STATE (DATA MEMBERS) TO THIS CLASS!!!! See the
// <ACE_Allocator::instance> implementation for explanation.
/// Pointer to a process-wide ACE_Allocator instance.
static ACE_Allocator *allocator_;
/// Must delete the <allocator_> if non-0.
static int delete_allocator_;
};
最近自己也寫了幾個allocator，還沒有研究更好的實現方式。不過看上去，侯先生書上說空間配置器，我應該可以考慮一下讀取硬盤空間來做allocator的空間，虛擬內存估計就是這麼實現的吧。
隨想：回想一年前，我第一次使用標准庫，覺得allocator實現是很高深的學問，自己什麼時候才能學會啊。後來看侯先生的allocator這本書，覺得我也可以做到，但由於自己的懶惰，很久都沒有實踐，最近有時間，再把標准庫認認真真的讀一下，寫一些深得體會，也對得起自己這三年的工作學習。其實有很多事情，一開始覺得那麼高深而自己難為之，只要有信心，方法用對了，堅持下來就會有突破的，而且一旦突破，那種快樂是相當舒服的。
最近有一個用了C++快五年的程序員，對C++及開源的了解相當深入，我覺得他也是一步一步走過來的。對於一些元編程，模板的靈活用法，網絡編程的高級使用，服務器的負載均衡，linux內核機制，window底層原理，他都有所深入了解，他現在說的很多我都還不懂，我需要堅持自己的步伐，加快一點。
