아래 2 개의 헤더파일은 예전에 회사를 그만두고 나서 집에서 쉬면서 만들었던 코드들입니다.

게임 프로그램은 작은 오브젝트를 여러개 많이 만들 경우가 자주 생깁니다. 필요할때마다 메모리를 할당하고, stl 의 list<T> 같은 자료구조를 사용해서 관리하는 것은 어렵지 않지만, 메모리 동적할당을 많이 하게 되면 성능상의 저하와, 단편화로 인한 메모리의 불안정을 초래하게 됩니다.

그래서 효율을 중시하는 엔진에서는 메모리를 좀 더 소비하고라도 동적할당을 줄이는 방식을 선호하게 되는데 이것에 필요한 클래스 템플릿을 2가지 만들어보았습니다.

첫번째는 pool<T> 입니다. 메모리를 페이지단위 (아래에 보면 8*1024-16) 로 할당해놓고 그 안에서 오브젝트 T를 만들어서 주는 식이며, 오브젝트는 모두 같은 크기를 쓰게 되어있기 때문에 동적할당의 횟수를 크게 줄일 수 있습니다.

두번째는 fixedlist<T> 입니다. stl 의 list<T>와 비슷하지만, 각 노드가 추가될 때 (push_back 등) 노드를 동적생성하는 것이 아니라 자체적인 pool<T> 에서 가져옴으로써, 효율저하를 막도록 하였습니다. 자체적인 pool 은 각 리스트마다 갖고 있게 할 수도 있고, static 으로 선언하여, 동일한 Type 을 갖는 fixedlist 끼리는 pool 을 공유하게 할 수도 있는데, 그것은 상황에 따라 달라지리라 생각합니다. (static 으로 선언하게 되면 소스파일에 따로 선언을 해줘야 합니다)

보잘것 없지만 이 두개의 소스를 공개하는 이유는, 비슷한 것을 만들고자 했던 분들께 참고가 되기를 바람과 동시에, 이 소스에 있을지도 모르는 버그에 대한 지적과 개선점에 대한 의견을 받기 위해서입니다.

이 소스는 공개용, 상업용 프로그램을 개발하는데에 자유롭게 사용하실 수 있습니다. 다만 이 소스를 다른 웹사이트나 책, 기타수단을 이용해 인용, 게제할 때에는 원작자의 출처를 밝혀주시기 바랍니다.

이 소스는 하단의 Reference 에서 밝힌 바와 같이, The C++ Programming Language 책과, ChrisC 의 튜토리얼, VC6 STL 소스코드등을 참고하여 만들었습니다.

--------------
<pool.h>

#ifndef        __POOL
#define        __POOL

//        pool<T>
//        -------
//
//        Purpose:        메모리 단편화를 줄이기 위해 커다란 영역의 메모리를 미리 할당해놓고 (as list of chunk)
//                                그 메모리 안에서 오브젝트를 O(1) 로 할당, 해제하도록 한다
//
//        Usage:                testPool.cpp 참조
//
//        Warning:        사용하려고 하는 클래스의 인스턴스의 크기가 chunk::size 보다 크면 안된다
//
//        Note:                템플릿을 이용하도록 함
//                                싱글턴 풀 생성과, 개체들의 자동 생성, 소멸을 위한 보조 매크로
//                                DECLARE_POOL 매크로를 이용해서 자동 관리를 하는 경우 컴파일러는 (C4291) 경고메시지를
//                                발생한다. 이것을 막으려면 throw() 를 생성자에 붙여주면 된다. testPool.cpp line 8 참조
//
//        Todo:                --
//
//        Reference:        [1]        Bjarne Stroustrup's The C++ Programming Language
//                                [2]        Flipcode: ChrisC's object pool lite
//
//        History:              neolith                note 에 warning 제거법 2 줄 추가

template <class        T>
class        pool {
        public:
                pool();
                ~pool();
                void *        Alloc();
                void        Free(void *b);

        private:
                struct        link { link *next; };
                struct        chunk {
                        enum { size = 8*1024-16 };
                        char        mem[size];
                        chunk *        next;
                };
                const unsigned int        esize;
                chunk *        m_chunks;
                link *        m_head;
                pool(pool &);
                void        operator = (pool &);
                void        Grow();
};

template <class        T>
inline        pool<T> :: pool()
        : esize(sizeof(T)<sizeof(link)?sizeof(link):sizeof(T))
{
        m_head = 0;
        m_chunks = 0;
}

template <class        T>
inline        pool<T> :: ~pool()
{
        chunk *        n = m_chunks;
        while (n) {
                chunk *        p = n;
                n = n->next;
                delete        p;
        }
}

template <class        T>
inline        void *        pool<T> :: Alloc()
{
        if (m_head == 0)
                Grow();
        link *        p = m_head;
        m_head = p->next;
        return        p;
}

template <class        T>
inline        void         pool<T> :: Free(void *b)
{
        link *        p = static_cast<link *>(b);
        p->next = m_head;
        m_head = p;
}

template <class        T>
inline        void         pool<T> :: Grow()
{
        chunk *        n = new chunk;
        n->next = m_chunks;
        m_chunks = n;

        const int        nelem = chunk::size/esize;
        char *        start = n->mem;
        char *        last = &start[(nelem-1)*esize];
        for (char *p = start; p<last; p+=esize)
                reinterpret_cast<link *>(p)->next = reinterpret_cast<link *>(p+esize);
        reinterpret_cast<link *>(last)->next = 0;
        m_head = reinterpret_cast<link *>(start);
}

//        간단하게 풀 컨테이너 (singleton) 를 선언하고
//        모든 오브젝트의 생성, 소멸을 풀에서 관리하도록 해주는 매크로
//        [2] 참조

#define DECLARE_POOL(classname)
public:
        void* operator new(size_t size) { return g_pool.Alloc(); }
        void operator delete(void* ptr, size_t size) { g_pool.Free(ptr); }
static pool<classname> g_pool;

#define DEFINE_POOL(classname)
pool<classname> classname::g_pool;

#endif


-------------
<fixedlist.h>

#ifndef        __FIXEDLIST
#define        __FIXEDLIST

//        fixedlist<T>
//        ------------
//
//        Purpose:        list 와 pool_allocator 의 결합된 형태.
//                                양방향 iterator 를 지원. 메모리 단편화를 유발하지 않는 빠른 할당, 해제, 순차탐색이 특징
//
//        Usage:                주로 객체 관리자용으로 사용된다. testFixedlist.cpp 참조
//
//        Warning:        stl style 로 씌여졌으나 pooling 을 하는 자체 allocator 를 사용한다
//                                for_each 말고는 알고리즘을 쓸 일이 별로 없을 듯 (주로 포인터를 담기 위한 용도이므로)
//
//        Note:                원래는 stl list 와 pool_alloc 을 조합해 사용하려 하였으나, list 에서 node 를 alloc 하는 부분 때문에
//                                정확한 pool_alloc 의 구현이 불가능함 (VC6, SGI 공통으로 node 를 할당하는 allocate 와 item을 할당하는
//                                allocate 가 혼재되어 있음)
//                                내부적인 pooling 은 pool<T> 를 사용
//
//        Todo:                좀 더 상세한 테스트를 만들어야 함
//
//        Reference:        visual C++ 기본 STL 의 list 파일을 참고하여 만듬
//
//        History:                neolith                작성함
//                                                                                placement new 를 할때 #include <new> 를 해야 한다는 사실을 알았음

#include        <new>
#include        "pool.h"

template <class        T>
class        fixedlist {
        private:
                struct        node;
                typedef        node *        nodePtr;
                struct        node {
                        nodePtr        prev,next;
                        T                value;
                };
                static        pool<node>        m_pool;
                nodePtr        m_head;
                size_t        m_size;

        public:
                class        iterator;
                fixedlist() : m_head(AllocNode()), m_size(0) {}
                fixedlist(iterator f, iterator l) : m_head(AllocNode()), m_size(0) { insert(begin(), f, l); }
                fixedlist(const fixedlist<T> &x) : m_head(new node), m_size(0) { insert(begin(), x.begin(), x.end()); }
                fixedlist<T> &        operator=(const fixedlist<T> &x) { if (this != &x) {/* copy from x */ } }
                ~fixedlist() { erase(begin(), end()); FreeNode(m_head); m_head = 0; m_size = 0; }
                
                class        iterator {
                        public:
                                iterator() {}
                                iterator(nodePtr p) : m_ptr(p) {}
                                iterator(iterator &x) : m_ptr(x.m_ptr) {}
                                T &        operator *() const {return (*m_ptr).value;}
                                iterator &        operator++() {
                                        m_ptr = m_ptr->next;
                                        return *this;
                                }
                                iterator         operator++(int) {
                                        iterator        tmp = *this;
                                        ++*this;
                                        return tmp;
                                }
                                iterator &        operator--() {
                                        m_ptr = m_ptr->prev;
                                        return *this;
                                }
                                iterator         operator--(int) {
                                        iterator        tmp = *this;
                                        --*this;
                                        return tmp;
                                }
                                bool        operator==(const iterator &x) const { return m_ptr == x.m_ptr; }
                                bool        operator!=(const iterator &x) const { return !(*this == x); }
                                nodePtr        GetNode() const { return m_ptr; }

                        private:
                                nodePtr        m_ptr;
                };
                iterator        begin() const { return iterator(m_head->next); }
                iterator        end() const { return iterator(m_head); }
                size_t                size() const { return m_size; }
                bool                empty() const { return (size() == 0); }
                iterator        insert(iterator p, const T&x = T()) {
                        nodePtr        s = p.GetNode();
                        s->prev = AllocNode(s, s->prev);
                        s = s->prev;
                        s->prev->next = s;
                        Construct(&s->value, x);
                        ++m_size;
                        return        s;
                }
                void        insert(iterator p, size_t m, const T&x) {
                        for(; 0<m; --m)
                                insert(p, x);
                }
                void        insert(iterator p, const T *f, const T *l) {
                        for(; f!=l; ++f)
                                insert(p, *f);
                }
                void        insert(iterator p, iterator f, iterator l) {
                        for(; f!=l; ++f)
                                insert(p, *f);
                }
                iterator        erase(iterator p) {
                        nodePtr        s = (p++).GetNode();
                        s->prev->next = s->next;
                        s->next->prev = s->prev;
                        Destroy(&s->value);
                        FreeNode(s);
                        --m_size;
                        return        p;
                }
                iterator        erase(iterator f, iterator l) {
                        while (f != l)
                                erase(f++);
                        return        f;
                }
                void        resize(size_t n, T x = T()) {
                        if (size() < n)
                                insert(end(), n-size(), x);
                        else
                                while(n<size())
                                        pop_back();
                }
                void        clear() { erase(begin(), end()); }
                void        push_front(const T& x) { insert(begin(), x); }
                void        pop_front() { erase(begin()); }
                void        push_back(const T& x) { insert(end(), x); }
                void        pop_back() { erase(--end()); }
                void        assign(iterator f, iterator l) { clear(); insert(begin(), f, l); }
                void        assign(size_t n, const T &x = T()) { clear(); insert(begin(), n, x); }

        private:
                nodePtr        AllocNode(nodePtr nextarg = 0, nodePtr prevarg = 0) {
                        nodePtr        s = (nodePtr)m_pool.Alloc();
                        s->next = (nextarg != 0) ? nextarg : s;
                        s->prev = (prevarg != 0) ? prevarg : s;
                        return        s;
                }
                void        FreeNode(nodePtr s) {
                        m_pool.Free(s);
                }
                void        Construct(T *p, const T&val) { new (p) T(val); }
                void        Destroy(T *p) { p->~T(); }
};

#endif

----
<testPool.cpp>

#include        "pool.h"
#include        <list>
using namespace        std;

struct        foo {
public:
        foo() throw() { puts("foo::ctor"); }
        ~foo() { puts("foo::dtor"); }
private:
        DECLARE_POOL(foo)
        int                a;
        int                b[100];
};

DEFINE_POOL(foo)

void        TestPool()
{
        typedef        list<foo *>        fooList;
        fooList        l;

        for (int i=0; i<10; i++)
                l.push_back(new foo);

        fooList :: iterator        it = l.begin();
        while (it!=l.end()) {
                (*it)->a = 0;
                it++;
        }

        it = l.begin();
        while (it!=l.end()) {
                delete        *it;
                it++;
        }
        l.clear();
}


----
<testFixedlist.cpp>

#include        "fixedlist.h"
#include        <stdio.h>

typedef        fixedlist <int>        intlist;

pool<intlist::node>  intlist::m_pool;

void        printlist(const intlist &a)
{
        intlist :: iterator        it = a.begin();
        while (it != a.end()) {
                printf("%d ", *it);
                ++it;
        }
        printf("n");
}

void        TestFixedlist()
{
        //        basic        test
        intlist        a;

        printf("now size of a is %dn", a.size());
        puts("adding 10 members");
        for (int i=0; i<10; i++)
                a.push_back(i);

        printf("now size of a is %dn", a.size());
        puts("printing");
        printlist(a);
        puts("erasing");
        a.erase(a.begin());
        a.erase(a.begin());
        a.erase(a.begin());
        printlist(a);
        printf("now size of a is %dn", a.size());

        //        insert test
        intlist :: iterator        it = a.begin();
        a.insert(it, 999);
        it++;
        it++;
        it++;
        a.insert(it, 999);
        it = a.end();
        a.insert(it, 999);
        printlist(a);

        puts("clearing");
        a.clear();
        printf("now size of a is %dn", a.size());
}