三种的allocator实现源代码的对比

     转自：http://blog.csdn.net/eagleatustb/article/details/8031549

     最近看空间配置器的内容，把ACE的ACE_Allocator类实现，SGI的allocator类实现和MS的allocator实现也参考了侯捷先生的《STL源码剖析》，有不少收获。

 

      我听说是有说明STL中allocator实现标准的文件，但我没有找到，据我实验推测，标准allocator需要实现rebind，allocate，deallocate，max_size和构造及析构函数一共六个函数。也就是说，我要写一个在标准vector可用的allocator最小只需要上面的几个接口实现就可以了。

 

      先来说一下微软的allocator。文件名是xmemory，我觉得是最没有看头的，基本就是new和delete的封装，为了迎合C++标准库的标准做的。没有什么技巧，更别说微妙了。上面的六个接口下面都有实现。

 

[cpp] view plaincopy

    // 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] view plaincopy

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] view plaincopy

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底层原理，他都有所深入了解，他现在说的很多我都还不懂，我需要坚持自己的步伐，加快一点。