#眉標=Boost
#副標=「Boost技術與應用」系列文章（2）
#大標=Boost.Pool
#作者=文／侯捷



==本文相關資訊	<box>===========
• 讀者基礎：擁有C++ templates編程經驗和C++標準程式庫使用經驗。
• 本文測試環境：VC6, VS2003。
• 本系列文章將匯整至編寫中的《Boost運用與源碼剖析》一書。
• 本文關於STL, Loki, MFC, Boost之Pooled Allocation技術分析將匯整至編寫中的《C++記憶體管理》一書。
• 關鍵術語：Boost, Pool, Pooled Allocation, Embedded Pointers, chunks, blocks。
==<end>==============



======================
void* p = malloc(1024);
=====================



======================
Foo *p = new Foo;
======================



======================
//以下是 C++ 編譯器對new算式的分解動作
Foo *p;
try {
   void* mem = Foo::operator new( sizeof(Foo)); 	//配置記憶體
   p = static_cast<Foo*>(mem);               		//轉型（cast）
   p->Foo::Foo;   			                  		//建構
}
catch( std::bad_alloc ) {
     //若配置失敗，不執行建構式
}
======================



======================
inline void* _RTLENTRY 
operator new (size_t size, const std::nothrow_t &)
{
    size = size ? size : 1;
    return malloc(size);   // ::operator new 呼叫malloc()
}
======================




======================
void* p = std::alloc::allocate(512); 	//static函式   
std::alloc::deallocate(p,512);        	//static函式
======================




======================
SmallObjAllocator myAlloc(2048,256);  //可應付小於256的各種大小配置
void* p1 = (void*)myAlloc.Allocate(20);
void* p4 = (void*)myAlloc.Allocate(64);
void* p2 = (void*)myAlloc.Allocate(40);
void* p3 = (void*)myAlloc.Allocate(300); 
            //以上大於256，內部將轉由內建工具處理
myAlloc.Deallocate(p4,64);
myAlloc.Deallocate(p1,20);
myAlloc.Deallocate(p2,40);
myAlloc.Deallocate(p3,300);
======================




======================
//這裡是CFixedAlloc定義式內部
struct CNode
  {
     CNode* pNext;   // only valid when in free list
  };
======================




======================
CFixedAlloc fooAlloc(sizeof(Foo)); //建立配置器時指定其服務尺寸
void* p1 = fooAlloc.Alloc();
void* p2 = fooAlloc.Alloc();
fooAlloc.Free(p1);
fooAlloc.Free(p2);
======================




======================
boost::object_pool<Foo> fooPool;
std::vector<Foo*> v;
for (int i = 0; i < 10; ++i)
   v.push_back(fooPool.construct(1,2)); //會喚起Foo建構式並傳入(1,2)
…
for (int j = 0; j < 5; ++j)
   pool.destroy(v[j]);
======================





#程式1	poolfwd.hpp源碼。

// Copyright (C) 2000, 2001 Stephen Cleary
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_POOLFWD_HPP
#define BOOST_POOLFWD_HPP

#include <boost/config.hpp> // for workarounds
#include <cstddef>   // std::size_t

// boost::details::pool::default_mutex
#include <boost/pool/detail/mutex.hpp>

namespace boost {

// Location: <boost/pool/simple_segregated_storage.hpp>
template <typename SizeType = std::size_t>
class simple_segregated_storage;

// Location: <boost/pool/pool.hpp>
struct default_user_allocator_new_delete;
struct default_user_allocator_malloc_free;

template <typename UserAllocator = 
              default_user_allocator_new_delete>
class pool;

// Location: <boost/pool/object_pool.hpp>
template <typename T, 
            typename UserAllocator = 
                default_user_allocator_new_delete>
class object_pool;

//註：以下宣告singleton_pool, pool_allocator, fast_pool_allocator
//    不在本文討論之列，故略。
   //...
} // namespace boost
#endif
======================





======================
template <typename T, typename UserAllocator>
class object_pool: protected pool<UserAllocator>
{ … }

======================





======================
template <typename UserAllocator>
class pool: protected simple_segregated_storage<
                             typename UserAllocator::size_type>
{
  protected:
    details::PODptr<size_type> list;
    const size_type requested_size;
    size_type next_size;
  …
};

======================




======================
//此處位於namespace boost內
namespace details {
template <typename SizeType>
class PODptr
{
  private:
    char * ptr;
    size_type sz;
  …
};
} // namespace details
======================




======================
template <typename SizeType>
class simple_segregated_storage
{
  protected:
    void * first;
  …
};

======================



==程式2	<box>===========
template <typename T, typename UserAllocator>
class object_pool: protected pool<UserAllocator>
{ … }
======================




==程式3	<box>===========
template <typename UserAllocator>
class pool: protected simple_segregated_storage<
                             typename UserAllocator::size_type>
{
  …
};
======================




======================
boost::object_pool<Foo> fooPool;  //先前是這麼寫的
======================




==程式4	<box>===========
struct default_user_allocator_new_delete
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return new (std::nothrow) char[bytes]; }
  static void free(char * const block)
  { delete [] block; }
};
======================




==程式5	<box>===========
struct default_user_allocator_malloc_free
{
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;

  static char * malloc(const size_type bytes)
  { return reinterpret_cast<char *>(std::malloc(bytes)); }
  static void free(char * const block)
  { std::free(block); }
};
======================





======================
template <typename SizeType>
class simple_segregated_storage
{
  protected:
    void * first;
  …
};
======================





======================
    simple_segregated_storage()
      : first(0) { }
======================





======================
    bool empty() const { return (first == 0); }
======================




======================
    // pre: !empty()
    void * malloc()
    {
      void * const ret = first;

      // Increment the "first" pointer to point to the next chunk
      first = nextof(first);
      return ret;
    }
======================





======================
    static void * & nextof(void * const ptr)
    { return *(static_cast<void **>(ptr)); }
======================





===============================
//此處在namespace boost之內
namespace details {
template <typename SizeType>
class PODptr
{
  private:
    char * ptr;
    size_type sz;
  …
};
} // namespace details
===============================



=========================================
boost::object_pool<Foo> fooPool;
=========================================




=========================================
    explicit 
    object_pool(const size_type next_size = 32)
      : pool<UserAllocator>(sizeof(T), next_size) 
    { }
=========================================




=========================================
    explicit 
    pool(const size_type nrequested_size,
          const size_type nnext_size = 32)
      : list(0,0),requested_size(nrequested_size), 
         next_size(nnext_size)
    { }    
=========================================




=========================================
    simple_segregated_storage()
      : first(0) { }
=========================================




==程式6	<box>===========
//註：這裡是object_pool class 定義式內部
//因此以下出現的 element_type在先前例中就是Foo

    element_type * construct()
    {
      element_type * const ret = malloc();
      if (ret == 0)
        return ret;
      try { new (ret) element_type(); }
      catch (...) { free(ret); throw; }
      return ret;
    }
#ifndef BOOST_NO_TEMPLATE_CV_REF_OVERLOADS
#   include <boost/pool/detail/pool_construct.inc>
#else
#   include <boost/pool/detail/pool_construct_simple.inc>
#endif
===========================================




===========================================
boost::object_pool<Foo> fooPool;
fooPool.construct('a', 10); 
//假設已知Foo建構式第一參數為 type,第二參數為 value
===========================================




===========================================
  Foo * const ret = malloc();
  if (ret == 0)
    return ret;
  try { new (ret) Foo(a0, a1); }
  catch (...) { free(ret); throw; }
  return ret;
===========================================




==========================================
    // Returns 0 if out-of-memory
    element_type * malloc()
    { return static_cast<element_type *>(store().ordered_malloc()); }
===========================================



===========================================
//註：這裡是boost::object_pool定義式內部
  protected:
    pool<UserAllocator> & store() { return *this; }
    const pool<UserAllocator> & store() const { return *this; }
//註：這裡是boost::pool定義式內部
  protected:
    simple_segregated_storage<size_type> & store() 
    { return *this; }
    const simple_segregated_storage<size_type> & store() const 
    { return *this; }
===========================================




===========================================
    // Returns 0 if out-of-memory
    element_type * malloc()
    { return static_cast<element_type *>
                  (store().ordered_malloc()); }
===========================================




=========================================
//註：在 boost::object_pool定義式內
void destroy(element_type * const chunk)
{
   chunk->~T();
   free(chunk);
}

void free(element_type * const chunk)
{ store().ordered_free(chunk); }
===========================================



===========================================
//註：在 boost::pool定義式內
void ordered_free(void * const chunk)
{ store().ordered_free(chunk); }
===========================================



===========================================
//註：在 boost::simple_segregated_storage定義式內
// pre: chunk was previously returned from a malloc() referring 
//  to the same free list
// post: !empty()
void ordered_free(void * const chunk)
{
// This (slower) implementation of 'free' places 
//  the memory back in the list in its proper order.

// Find where "chunk" goes in the free list
      void * const loc = find_prev(chunk);

// Place either at beginning or in middle/end
      if (loc == 0)
        free(chunk);
      else  {
        nextof(chunk) = nextof(loc);
        nextof(loc) = chunk;
      }
}

void free(void * const chunk)
{
   nextof(chunk) = first;
   first = chunk;
}
===========================================




==更多資訊	<box>===========
以下是與本文相關的讀物或網上資源。
• 《Effective C++》3/e, by Scott Meyers，chap8 "Customizing new and delete".
• 《STL源碼剖析》by侯捷，第二章「空間配置器」。
• 《Modern C++ Design》by Andrei Alexandrescu，chap4 "Small Object Allocation".
• 《深入淺出MFC》2/e by侯捷。
• Boost Libraries Documentation, from http://www.boost.org.
==<end>==============


==作者簡介	<box>===========
侯捷
資訊顧問、專欄主筆、大學執教。常著文章自娛，頗示己志。
侯捷網站：http://www.jjhou.com（繁體）
北京鏡站：http://jjhou.csdn.net（簡體）
永久郵箱：jjhou@jjhou.com 
==<end>==============

 	



侯捷技術專欄