歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

STL中的空間配置器

一般我們習慣的c++內存配置如下

class Foo { ... };
Foo* pf = new Foo;
delete pf;

 這裡的new實際上分為兩部分執行。首先是先用::operator new配置內存,然後執行Foo::Foo()構造對象內容。delete也一樣,先運行Foo::~Foo()析構對象,再用::operator delete釋放內存。在SGI STL中,這兩部分分別在<stl_alloc.h>和<stl_construct.h>中。本文講的便是<stl_alloc.h>中的故事。
  SGI STL中將配置器分為兩級。第一級直接用malloc和free管理內存,第二級則使用內存池以避免內存碎片。這兩級都由simple_alloc包裝起來以符合stl標准。如圖

第一級由於沒有用operator new,所以要自己實現new-handler機制。我仿寫的代碼如下

#ifndef _MALLOC_ALLOC_H_
#define _MALLOC_ALLOC_H_

//定義內存不足又沒有定義相關處理函數時拋出的異常
#ifndef THROW_OOM
#    include <stdio.h>
#    include <stdlib.h>
#    define THROW_OOM fprintf(stderr, "out of memory\n"); exit(1)
#endif

#include<stdlib.h>

namespace Chenstl{

//第一級空間配置器,直接用mallloc分配內存
//當需要分配的空間大於MAX_BYTES時使用
    class malloc_alloc{
    private:
        static void *oom_malloc(size_t);    //聲明時可以只寫類型啊。。現在才知道
        static void *oom_realloc(void *,size_t);
        static void (* malloc_oom_handler)();    //處理malloc時內存不足時的函數指針
    public:
        static void *allocate(size_t n);
        static void decllocate(void *p);

        static void *realloc(void *p, size_t new_sz);
        //當內存不足時,需要客戶端設置handler
        static void set_malloc_oom_handler(void(*f)());
    };   
}

#endif

----------------------------------------------------------------------------------

#include "malloc_alloc.h"

using namespace Chenstl;
void *malloc_alloc::allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);
    return result;
}

void malloc_alloc::decllocate(void *p)
{
    free(p);
}

void * malloc_alloc::realloc(void *p, size_t new_sz)
{
    void *result = realloc(p, new_sz);
    if (0 == result)    result = oom_realloc(p, new_sz);
    return result;
}

//當內存不足時,需要客戶端設置handler
void malloc_alloc::set_malloc_oom_handler(void(*f)())
{
    malloc_oom_handler = f;
}

void(*malloc_alloc::malloc_oom_handler)() = 0;

void *malloc_alloc::oom_malloc(size_t n)
{//不斷試圖獲得內存
    void *result;
    for (;;)    //據說這樣比while(1)效果更優
    {
        if (0 == malloc_oom_handler) THROW_OOM;
        (*malloc_oom_handler)();
        result = malloc(n);
        if (result)    return result;
    }
}

void *malloc_alloc::oom_realloc(void *p, size_t n)
{
    void *result;
    for (;;)
    {
        if (0 == malloc_oom_handler) THROW_OOM;
        (*malloc_oom_handler)();
        result = realloc(p, n);
        if (result)    return result;
    }
}

malloc_alloc.cpp

如果需要的區塊超過128bytes則用第一級,否則用第二級的內存池管理。為了便於管理,配置器會自動將內存需求量上調到8的倍數(要求20bytes時,自動調整為24bytes)。用16個freelist管理內存池,為節省空間,使用union

union obj {  //free-lists的節點構造
  union obj *next;
  char client[1];  //使用者可見
  };

獲取內存時的代碼及步驟如下

void *default_alloc::allocate(size_t n)
{
    obj *result = 0;
    obj **my_free_list = 0;
    if (n > MAX_BYTES)
        return malloc_alloc::allocate(n);
    //尋找free lists中合適的一個               
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if(0 == result)
    {//沒有找到可用的freelist,從內存池裡取出空間
        return refill(ROUND_UP(n));
    }
    //調整freelist
    *my_free_list = result->next;
    return result;
}

當free list中沒有可用區塊時,調用refill()為free list填充空間,新的空間取自內存池(由chunk_alloc()完成)。如果內存池不夠,則malloc之,如果系統heap空間也不夠,chunk_alloc()就尋找還有空閒區塊的free list並將其內存充公,如果還是不夠就調用第一級配置器。第一級配置器有實現new-handler機制,內存不夠會拋出異常。

#ifndef _DEFAULT_ALLOC_H
#define _DEFAULT_ALLOC_H

namespace Chenstl{   
    //使用內存池以減少碎片
    class default_alloc {
    private:
        enum { ALIGN = 8};
        enum { MAX_BYTES = 128 };
        enum { NFREELISTS = 16 };
        //static const int ALIGN = 8;
        //static const int MAX_BYTES = 128;
        //static const int NFREELISTS = 16;    //MAX_BYTES/ALIGN
        union obj {            //free-lists的節點構造
            union obj *next;
            char client[1];
        };
        //freelist
        static obj *free_list[NFREELISTS];
        static char *start_free;    //內存池的起始位置
        static char *end_free;        //內存池的終止位置
        static size_t heap_size;

    private:
        //將bytes上調至8的倍數
        static size_t ROUND_UP(size_t bytes) {
            return ((bytes +ALIGN - 1) & ~(ALIGN - 1));
        }
        //獲取合適的區塊在freelist中的位置
        static  size_t FREELIST_INDEX(size_t __bytes) {
            return (((__bytes)+(size_t)ALIGN - 1) / (size_t)ALIGN - 1);
        }
        //返回一個大小為n的對象,並可能加入大小為n的其他區塊到free-list
        static void *refill(size_t n);
        //配置一大塊空間,可容納nobjs個大小為size的區塊
        //如果配置nobjs個區塊有所不便,nobjs可能會降低
        static char *chunk_alloc(size_t size, int &nobjs);

    public:
        static void *allocate(size_t n);
        static void deallocate(void *p, size_t n);
        static void *realloc(void *p, size_t old_sz, size_t new_sz);
    };
}

#endif

default_alloc.h

---------------------------------------------------------

#include "default_alloc.h"
#include "malloc_alloc.h"
using namespace Chenstl;

default_alloc::obj *default_alloc::free_list[NFREELISTS]
= { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
char *default_alloc::start_free = 0;    //內存池的起始位置
char *default_alloc::end_free = 0;        //內存池的終止位置
size_t default_alloc::heap_size = 0;

void *default_alloc::allocate(size_t n)
{
    obj *result = 0;
    obj **my_free_list = 0;
    if (n > MAX_BYTES)
        return malloc_alloc::allocate(n);
    //尋找free lists中合適的一個               
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if(0 == result)
    {//沒有找到可用的freelist,從內存池裡取出空間
        return refill(ROUND_UP(n));
    }
    //調整freelist
    *my_free_list = result->next;
    return result;
}

void default_alloc::deallocate(void *p, size_t n)
{

}
//返回一個大小為n的對象,並可能加入大小為n的其他區塊到freelist
//在ANSI c中,void *不允許進行加減操作,所以chunk用char *
void *default_alloc::refill(size_t n)
{
    int objs = 20;
    char *chunk = chunk_alloc(n, objs);
   
    obj *next, *current;
    obj *result;
    obj **my_free_list;
    if (1 == objs)    //只取出一個區塊
        return chunk;
    my_free_list = free_list + FREELIST_INDEX(n);
    result = (obj *)chunk;    //這一塊返回給客戶端
    //將freellist指向分配的區域
    *my_free_list = next = (obj *)chunk + n;
    for (int i = 1;; i++)
    {
        current = next;
        next = (obj *)((char *)next + n);    //這裡注意不能直接用next+n
        if (i == objs - 1)
        {
            current->next = 0;
            break;
        }
        else
            current->next = next;
    }
    return result;   
}

char *default_alloc::chunk_alloc(size_t size, int &nobjs)
{
    char *result = 0;
    size_t total_bytes = size*nobjs;
    size_t bytes_left = end_free - start_free;    //內存池剩余空間
    if (bytes_left >= total_bytes)
    {//內存池足夠提供所需內存
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else if (bytes_left >= size)
    {//內存池足夠供應一個以上的區塊
        nobjs = bytes_left / size;
        total_bytes = nobjs * size;
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else
    {//內存池一塊區塊也供應不了
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);;
        if (bytes_left>0)
        {//將內存池的零頭分配給合適的freelist
            obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *)start_free)->next = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
        start_free = (char *)malloc(bytes_to_get);
        if (!start_free)
        {//系統堆內存不足,尋找還未使用的freelist
            obj *p = 0;
            obj **my_free_list = 0;
            for (int i = size; i < MAX_BYTES; ++i)
            {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p)
                {//還有未使用的freelist
                    start_free = (char *)p;
                    *my_free_list = p->next;
                    end_free = start_free + i;
                    //遞歸調用,修正nobjs
                    return chunk_alloc(size, nobjs);
                }
            }
            //沒內存可用,寄希望於第一級的new-handler或拋出異常
            end_free = 0;
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return chunk_alloc(size, nobjs);//遞歸調用,修正nobjs
    }
}

default_alloc.cpp

Copyright © Linux教程網 All Rights Reserved