szwolf

   使用STL已经有一段时间了，对里面的运作方式一直不了解。这几天突发其想，找了一些关于STL源码的书看了一下，觉得其内部实现非常精妙。作为进一步学习，我打算把STL中的主要组件自己动手实现一下。
   首先从空间配置器开始，从内部逐渐了解STL中各种容器的实现细节。
   根据STL的规范，allocator必须有以下接口：
   

typedef    size_t        size_type;
typedef    T        value_type;
typedef    T *         pointer;
typedef    ptrdiff_t    difference_type;
typedef     const  T *     const_pointer;
typedef    T &         reference;
typedef     const  T &     const_reference;

rebind
allocator( const  allocator < U >&  )
~ allocator() 
pointer address(reference x)
const_pointer address(const_pointer x)
T *  allocate(size_type n,  void *  p  =   0 )
void  deallocate(pointer p, size_type n)
size_type max_size()
void  construct(pointer p, const_reference val)
void  destroy(pointer p)

 SGI STL并没有按C++ STD的说没直接做一个Allocator出来,而是先做出两个Allocator template及以内存池的形式来构 //造Allocator比STD::allocator效率更高且减少了内存碎片。下面是sgi_allocator.h的代码:

#ifndef SGI_ALLOCATOR
#define  SGI_ALLOCATOR
#include  < iostream >
#include  < cstddef >          // for size_t
using   namespace  std;

namespace  SGI
{
    template < int  inst >
     class  malloc_alloc_template     // 一级空间配置器
     {
     public :
         static   void *  allocate(size_t n)
         {
             void *  result  =  malloc(n);
             if  (result  ==  NULL)
             {
                result  =  oom_malloc(n);         // 内存不足调用oom_malloc()进行处理
            }

             return  result;
        }

         static   void  deallocate( void *  p, size_t)     // 第二个参数无所谓,只要一进来就把它干掉..
         {
            free(p);
        }

         static   void *  reallocate( void *  p, size_t /**/ /* old size */ , size_t new_size)
         {
             void *  result  =  realloc(p, new_size);
             if (result  ==  NULL)
             {
                result  =  oom_realloc(p, new_size);
            }

             return  result;
        }

         static   void  ( * set_malloc_handler( void  ( * f)()))()
         {
             void  ( * old)()  =  oom_malloc_handler;
            oom_malloc_handler  =  f;

             return  old;
        }
     private :
         static   void *  oom_malloc(size_t);         // 内存不足时调用这个函数(因为里面有处理函数)
         static   void *  oom_realloc( void * , size_t); // 同上
         static   void  ( * oom_malloc_handler)();     // 内存不足时的处理函数
    } ;
    template < int  inst >
     void *  malloc_alloc_template < inst > ::oom_malloc(size_t size)
     {
         void *  result;
        
         while ( true )             // 反得调用处理函数,直到申请成功.如果没有定义处理函数则抛出异常
         {
             if  (oom_malloc_handler  ==  NULL)
             {
                 throw  bad_alloc();
            }
            ( * oom_malloc_handler)();
             if  ( (result  =  malloc(size))  !=  NULL)
             {
                 return  result;
            }
        }
    }

    template < int  inst >
     void *  malloc_alloc_template < inst > ::oom_realloc( void *  p, size_t new_size)
     {
         void *  result;

         while ( true )
         {
             if  (oom_malloc_handler  ==  NULl)
             {
                 throw  bad_alloc();
            }
            ( * oom_alloc_handler)();
             if  ( (result  =  realloc(p, new_size))  !=  NULL)
             {
                 return  result;
            }
        }
    }

    template < int  inst >
     void  ( * malloc_alloc_template < inst > ::oom_malloc_handler)()  =  NULL;

    typedef malloc_alloc_template < 0 >  malloc_alloc;         // 到此完成一级空间配置器的定义

     /**/ //////////////////////////////////////////////////////
     // 下面是对一二级配置器的封装, 其中Alloc即为空间配置器
     // 默认用的是二级配置器,当>128K或内存不足时会交给一级
     // 配置器处理
     /**/ /////////////////////////////////////////////////// //j 
    template < typename T, typename Alloc >             
     class  simple_alloc
     {
     public :
         static  T *  allocate(size_t n)
         {
             return  n  ==   0   ?   0  : (T * )Alloc::allocate(n  *   sizeof (T));
        }

         static  T *  allocate()
         {
             return  (T * )Alloc::allocate( sizeof (T));
        }

         static   void  deallocate(T *  p, size_t n)
         {
             if  (n  !=   0 )
             {
                Alloc::deallocate(p, n  *   sizeof (T));         // 这里要用两个参数是为了与后面的二级配置器配合(这个问题郁闷了我好久,呵呵,菜啊!)
            }
        }

         static   void  deallocate(T *  p)
         {
            Alloc::deallocate(p,  sizeof (T));
        }
    } ;

     enum {ALIGN  =   8 , MAX_BYTES  =   128 , NFREELISTS  =   16 } ;     //  其中NFREELISTS = MAX_BYTES / ALIGN
    
    template < bool  threads,  int  inst >
     class  default_alloc_template     // 定义二级配置器
     {
     public :
         static   void *  allocate(size_t n)
         {
             void *  result;
            
             if  (n  >  (size_t)MAX_BYTES)
             {
                result  =  malloc_alloc::allocate(n);         // >128K交给一级配置器处理
            }
             else
             {
                Obj *   volatile *  my_free_list     =  free_list  +  free_list_index(n);
                 if  ( (result  =   * my_free_list)  ==  NULL)
                 {
                    result     =     refill(round_up(n));
                }
                 else
                 {
                    Obj *  tmp         =   * my_free_list;
                     * my_free_list     =  tmp -> free_list_link;
                    result             =  tmp;
                }
            }

             return  result;
        }

         static   void  deallocate( void *  p, size_t n)
         {
             if  (n  >  (size_t)MAX_BYTES)
             {
                malloc_alloc::deallocate(p, n);
            }
             else
             {
                Obj *   volatile *  my_free_list  =  free_list  +  free_list_index(n);
                Obj *  q  =  (Obj * ) p;
                q -> free_list_link     =   * my_free_list;
                 * my_free_list         =  q;
            }
        }

         static   void *  reallocate( void *  p, size_t old_size, size_t new_ize);

     private :
         static  size_t round_up(size_t bytes)
         {
             return  ((bytes  +  (size_t)ALIGN  -   1 )  &   ~ ((size_t)ALIGN  -   1 ));
        }
        
        union Obj             // Trick,既可以作指针,又可以作为内存地址
         {
            union Obj *  free_list_link;
             char  client_data[ 1 ];
        } ;

         static  Obj *   volatile  free_list[NFREELISTS];

         static  size_t free_list_index(size_t size)
         {
             return  ((size  +  (size_t)ALIGN  -   1 )  /  (size_t)ALIGN  - 1 );
        }
        
         static   void *  refill(size_t n);
         static   char *  chunk_alloc(size_t size, size_t &  objs);
        
         static   char *     chunk_start;     // 内存池起始位置
         static   char *     chunk_end;         // 内存池结束位置
         static  size_t    heap_size;         // 从开始至今在堆中申请的字节总数

    } ;

    template < bool  threads,  int  inst >
     char *  default_alloc_template < threads, inst > ::chunk_start  =  NULL;

    template < bool  threads,  int  inst >
     char *  default_alloc_template < threads, inst > ::chunk_end  =  NULL;

    template < bool  threads,  int  inst >
    size_t default_alloc_template < threads, inst > ::heap_size  =   0 ;
    
    template < bool  threads,  int  inst >
    typename default_alloc_template < threads, inst > ::Obj *   volatile  default_alloc_template < threads, inst > ::free_list[NFREELISTS]  =   { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } ;


     // 核心部分,从内存池中申请空间
    template < bool  threads,  int  inst >
     char *  default_alloc_template < threads, inst > ::chunk_alloc(size_t size, size_t &  nobjs)
     {
         char *     result         =  NULL;
        size_t    total_bytes     =  size  *  nobjs;                        
        size_t    bytes_left     =  chunk_end  -  chunk_start;             // 内存池所剩水量

         if  ( bytes_left  >  total_bytes)                             // 内存池中有足够空间可以分配
         {
            result         =     chunk_start;
            chunk_start  +=     total_bytes;

             return  result;
        }
         else   if (bytes_left  >=  size)                         // 内存池中空间至少可以分配一个块
         {
            nobjs             =     ( int )bytes_left  /  size;
            total_bytes         =     size  *  nobjs;
            result             =     chunk_start;
            chunk_start     +=     total_bytes;

             return  result;
        }
         else                                          // 内存池已山穷水尽一个块都无法分配出来 T_T
         {
            size_t bytes_to_get     =  total_bytes  +  round_up(heap_size  >>   4 );         // 申请总数两位加上扩展

             if  (bytes_left  >   0 )
             {
                Obj *   volatile *  my_free_list             =  free_list  +  free_list_index(bytes_left);
                ((Obj * )chunk_start) -> free_list_link     =   * my_free_list;
                 * my_free_list                         =  (Obj * )chunk_start;
            }
            chunk_start     =     ( char * )malloc(bytes_to_get);
             if  (chunk_start  ==  NULL)         // 内存不足这下麻烦了,看看表中有没有空间可以回收
             {
                Obj *   volatile *  my_free_list;
                Obj *  p;

                 for (size_t i  =  size; i  <=  MAX_BYTES; i  +=  ALIGN)
                 {
                    my_free_list     =     free_list  +  free_list_index(i);
                    p                 =      * my_free_list;

                     if  (p  !=  NULL)     // 找到适合的空间,进行回收
                     {                        
                         * my_free_list     =     p -> free_list_link;
                        chunk_start         =     ( char * )p;
                        chunk_end         +=     i;

                         return  chunk_alloc(size, nobjs);

                    }
                }
                
                 // 完全走投无路了,只好看看内存不足的处理函数能不能帮上忙
                chunk_end     =     NULL;
                chunk_start     =     ( char * )malloc_alloc::allocate(bytes_to_get);
            }
            chunk_end     +=     bytes_to_get;
            heap_size     +=     bytes_to_get;

             return  chunk_alloc(size, nobjs);
        }
    }

     /**/ /*
     * 返回一个大小为n的块, 并且可能适当地为free_list增加节点
     *
      */
    template < bool  threads,  int  inst >
     void *  default_alloc_template < threads, inst > ::refill(size_t n)
     {
        size_t        nobjs  =   20 ;                 // 默认申请块的个数
        Obj *         curr;
        Obj *         next;
        

         char *     result  =  chunk_alloc(n, nobjs);
         if  (nobjs  ==   1 )         // 只申请到一块空间则直接返回给调用者
         {
             return  result;
        }
         else              // 申请到多于一个块,将其它nobjs - 1个块加到free_list中 : )
         {
            Obj *   volatile *  my_free_list     =  free_list  +  free_list_index(n);;
             * my_free_list  =  next  =  (Obj * )(result  +  n);
             for ( int  i  =   1 ; ;  ++ i)
             {                
                curr     =     next;
                next     =  (Obj * )( ( char * )next  +  n);

                 if  (i  ==  nobjs  -   1 )
                 {
                    curr -> free_list_link     =     NULL;
                     break ;
                }
                 else
                 {
                    curr -> free_list_link     =     next;
                }
            }
             return  result;
        }
    }

    template < bool  threads,  int  inst >
     static   void *  default_alloc_template < threads, inst > ::reallocate( void *  p, size_t old_size, size_t new_size)
     {
         if  (old_size  >  MAX_BYTES  &&  new_size  >  MAX_BYTES)
         {
             return  realloc(p, new_size);
        }

         if  (round_up(old_size)  ==  round_up(new_size))
         {
             return  p;
        }

         void *  result  =  malloc(new_size);
         int  copy_size  =  new_size  >  old_size  ?  old_size : new_size;
        memcpy(result, p, copy_size);

         return  result;
    }
    
    typedef default_alloc_template < false ,  0 >  alloc;

     /**/ /*
     * 对以定义好的两个配置器模板进行封装,以使其与STL相容
      */
    template < typename T >
     class  allocator
     {
     public :
        typedef        size_t        size_type;
        typedef        T            value_type;
        typedef        T *             pointer;
        typedef        ptrdiff_t    difference_type;
        typedef         const  T *     const_pointer;
        typedef        T &             reference;
        typedef         const  T &     const_reference;

        template < typename U >  
         struct  rebind
         {
            typedef allocator < U >  other;
        } ;

        allocator()  throw ()
         {
        }

        template < typename U >
        allocator( const  allocator < U >&  )  throw ()
         {
        }
        
         ~ allocator()  throw ()
         {
        }

        pointer address(reference x)  const
         {
             return   &  x;
        }

        const_pointer address(const_pointer x)  const
         {
             return   & x;
        }

        T *  allocate(size_type n,  void *  p  =   0 )
         {
             return  n  !=   0   ?  static_cast < T *> (alloc::allocate(n  *   sizeof (T))) :  0 ;
        }

         void  deallocate(pointer p, size_type n)
         {
            alloc::deallocate(p, n * sizeof (T));
        }

        size_type max_size()  const   throw ()
         {
             return  (size_t) - 1 / sizeof (T);
        }

         void  construct(pointer p, const_reference val)
         {
             new (p)T(val);
        }

         void  destroy(pointer p)
         {
            p ->~ T();
        }         
    } ;

}

#endif

 以下是测试文件，现在比较晚了。。没有写一个比较像样的测试，以后有时候再写写。。。

//  sgi_allocator.cpp : 定义控制台应用程序的入口点。
//
/**/ /*
 *    模拟SGI STL中allocator的实现,以内存池的形式,构建一个比STD::allocator
 *    更高效的空间配置器
 *    作者: Szwolf
 *    2006.8.3:23.31'暑假@SZU
 *
  */
#include  " stdafx.h "
#include  " sgi_allocator.h "
#include  < iostream >
#include  < vector >
#include  < algorithm >

using   namespace  std;

class  test
{
public :
    friend ostream &   operator   <<  (ostream &  os,  const  test &  x)
     {
         return  os  <<   " test success : ) "   <<  endl;
    }
} ;

int  _tmain( int  argc, _TCHAR *  argv[])
{
     int  a[]  =   { 1 , 2 , 3 , 4 } ;
    test b[ 10 ];
    vector < int , SGI::allocator < int >   >  vec(a, a  +   4 );
    vector < test, SGI::allocator < test >   > vec2(b, b + 10 );
    copy(vec.begin(), vec.end(), ostream_iterator < int > (cout,  "   " ));
    cout  <<  endl;
    copy(vec2.begin(), vec2.end(), ostream_iterator < test > (cout));
    cout  <<  endl;

     return   0 ;
}

一个类似于SGI STL::allocator的空间配置器就这样完成了：）个人感觉在建内存池的过程从其无所不用其极的空间申请方式中受益颇多～～～（呵呵，链表操作又复习了一遍。。）
 以下是在VS2005中可以正常编译通过的源码：
http://www.cppblog.com/Files/szwolf/sgi_allocator.rar