From: xushiweizh_at_[hidden]
Date: 2008-04-30 01:50:37
Author: xushiwei
Date: 2008-04-30 01:50:36 EDT (Wed, 30 Apr 2008)
New Revision: 44912
URL: http://svn.boost.org/trac/boost/changeset/44912
Log:
ticket #1885: gc_alloc::_TryGC, boost::priority_queue
Added:
sandbox/memory/boost/memory/stl/
sandbox/memory/boost/memory/stl/queue.hpp (contents, props changed)
Text files modified:
sandbox/memory/boost/memory/basic.hpp | 2
sandbox/memory/boost/memory/gc_alloc.hpp | 115 ++++++++++++++++++++++++++++-----------
2 files changed, 83 insertions(+), 34 deletions(-)
Modified: sandbox/memory/boost/memory/basic.hpp
==============================================================================
--- sandbox/memory/boost/memory/basic.hpp (original)
+++ sandbox/memory/boost/memory/basic.hpp 2008-04-30 01:50:36 EDT (Wed, 30 Apr 2008)
@@ -31,6 +31,8 @@
#endif
#pragma pack() // default pack
+#pragma warning(disable:4786)
+// warning: identifier was truncated to '255' characters in the debug information
// =========================================================================
Modified: sandbox/memory/boost/memory/gc_alloc.hpp
==============================================================================
--- sandbox/memory/boost/memory/gc_alloc.hpp (original)
+++ sandbox/memory/boost/memory/gc_alloc.hpp 2008-04-30 01:50:36 EDT (Wed, 30 Apr 2008)
@@ -12,10 +12,20 @@
#ifndef _BOOST_MEMORY_GC_ALLOC_HPP_
#define _BOOST_MEMORY_GC_ALLOC_HPP_
+#pragma warning(disable:4786)
+
#ifndef _BOOST_MEMORY_SCOPED_ALLOC_HPP_
#include "scoped_alloc.hpp"
#endif
+#ifndef _BOOST_MEMORY_STL_QUEUE_HPP_
+#include "stl/queue.hpp" // boost::priority_queue
+#endif
+
+#if !defined(_DEQUE_) && !defined(_DEQUE)
+#include <deque> // std::deque
+#endif
+
_NS_BOOST_BEGIN
// -------------------------------------------------------------------------
@@ -122,20 +132,23 @@
}
};
};
+#pragma pack()
- struct _FreeListNode
+ struct _Pred : std::binary_function<_FreeMemHeader*, _FreeMemHeader*, bool>
{
- _HeaderSizeT cbSize;
- _FreeListNode* pPrev;
+ bool operator()(_FreeMemHeader* a, _FreeMemHeader* b) const {
+ return a->cbSize > b->cbSize;
+ }
};
-#pragma pack()
+ typedef std::deque<_FreeMemHeader*> _Cont;
+ typedef boost::priority_queue<_FreeMemHeader*, _Cont, _Pred> _PriorityQ;
char* m_begin;
char* m_end;
_Alloc m_alloc;
_MemHeaderEx* m_destroyChain;
_MemBlock* m_blockList;
- _FreeListNode* m_freeList;
+ _PriorityQ m_freeList;
_HugeGCAlloc m_hugeAlloc;
static _FreeMemHeader _null;
@@ -185,6 +198,21 @@
}
}
+ void BOOST_MEMORY_CALL _ReduceDestroyChain() const
+ {
+ _MemHeaderEx** pp = &m_destroyChain;
+ while (*pp)
+ {
+ _MemHeaderEx* curr = (*pp)->pPrev;
+ if (curr->blkType == nodeFree) {
+ *pp = curr->pPrev;
+ }
+ else {
+ pp = &curr->pPrev;
+ }
+ }
+ }
+
void BOOST_MEMORY_CALL _Travel() const
{
_MemBlock* pHeader = m_blockList;
@@ -197,43 +225,57 @@
}
}
- _MemBlock* BOOST_MEMORY_CALL _NewMemBlock(size_t cbBlock)
+ void BOOST_MEMORY_CALL _TryGC()
+ {
+ }
+
+ _MemHeader* BOOST_MEMORY_CALL _NewBlock(size_t cbBlock)
{
- _MemBlock* pNew = (_MemBlock*)m_alloc.allocate(cbBlock);
- pNew->pPrev = m_blockList;
- m_blockList = pNew;
+ _MemBlock* pBlock = (_MemBlock*)m_alloc.allocate(cbBlock);
+ pBlock->pPrev = m_blockList;
+ m_blockList = pBlock;
+
+ _MemHeader* pNew = (_MemHeader*)pBlock->buffer;
+ pNew->blkType = nodeFree;
+ pNew->cbSize = m_alloc.alloc_size(pBlock) - (sizeof(_MemHeader) + HeaderSize);
return pNew;
}
+ void BOOST_MEMORY_CALL _CommitCurrentBlock()
+ {
+ _FreeMemHeader* old = (_FreeMemHeader*)m_begin - 1;
+ BOOST_MEMORY_ASSERT(old->getBlockType() == nodeFree);
+ old->cbSize = (m_end - m_begin);
+ }
+
void BOOST_MEMORY_CALL _Init()
{
- _MemBlock* pNew = _NewMemBlock(MemBlockSize);
- _MemHeader* p = (_MemHeader*)pNew->buffer;
- p->blkType = nodeFree;
- m_begin = (char*)(p + 1);
- m_end = (char*)pNew + m_alloc.alloc_size(pNew);
+ _MemHeader* pNew = _NewBlock(MemBlockSize);
+ m_begin = (char*)(pNew + 1);
+ m_end = m_begin + pNew->cbSize;
}
private:
enum { HeaderSize = sizeof(void*) };
enum { BlockSize = MemBlockSize - HeaderSize };
enum { _AllocSizeBigDef = MAX(_Policy::AllocSizeBig, BlockSize/4) };
+ enum { _AllocSizeHugeDef = MAX(_Policy::AllocSizeHuge, 64*1024) };
enum { AllocSizeBig = MIN(_AllocSizeBigDef, BlockSize/2) };
- enum { AllocSizeHuge = _Policy::AllocSizeHuge };
+ enum { AllocSizeHuge = MIN(_AllocSizeHugeDef, (1 << 29)) };
enum { RecycleSizeMin = MAX(_Policy::RecycleSizeMin, 128) };
public:
- gen_alloc() : m_blockList(NULL), m_freeList(NULL), m_destroyChain(NULL)
+ gen_alloc() : m_blockList(NULL), m_destroyChain(NULL)
{
_Init();
}
explicit gen_alloc(_Alloc alloc)
- : m_alloc(alloc), m_blockList(NULL), m_freeList(NULL), m_destroyChain(NULL)
+ : m_alloc(alloc), m_blockList(NULL), m_destroyChain(NULL)
{
_Init();
}
explicit gen_alloc(gen_alloc& owner)
- : m_alloc(owner.m_alloc), m_blockList(NULL), m_freeList(NULL), m_destroyChain(NULL)
+ : m_alloc(owner.m_alloc), m_blockList(NULL), m_destroyChain(NULL)
{
_Init();
}
@@ -272,7 +314,7 @@
}
m_begin = m_end = _null.getData();
m_blockList = NULL;
- m_freeList = NULL;
+ m_freeList.clear();
}
void* BOOST_MEMORY_CALL allocate(size_t cbData)
@@ -280,7 +322,7 @@
const size_t cb = cbData + sizeof(_MemHeader);
if ((size_t)(m_end - m_begin) < cb)
{
- _MemBlock* pNew;
+ _MemHeader* pNew;
if (cb >= AllocSizeBig)
{
if (cbData >= AllocSizeHuge)
@@ -288,26 +330,31 @@
if (cb >= BlockSize)
{
- pNew = _NewMemBlock(cb + HeaderSize);
- _MemHeader* p = (_MemHeader*)pNew->buffer;
- p->blkType = nodeAlloced;
- p->cbSize = cbData;
- return p + 1;
+ pNew = _NewBlock(cb + HeaderSize);
+ pNew->blkType = nodeAlloced;
+ return pNew + 1;
}
- pNew = _NewMemBlock(MemBlockSize);
+ pNew = _NewBlock(MemBlockSize);
}
else
{
- pNew = _NewMemBlock(MemBlockSize);
+ _TryGC();
+ _FreeMemHeader* p;
+ if (m_freeList.empty() || (p = m_freeList.top())->cbSize < cb) {
+ pNew = _NewBlock(MemBlockSize);
+ }
+ else {
+ pNew = (_MemHeader*)p;
+ m_freeList.pop();
+ }
}
- _FreeMemHeader* old = (_FreeMemHeader*)m_begin - 1;
- BOOST_MEMORY_ASSERT(old->getBlockType() == nodeFree);
- old->cbSize = m_end - m_begin;
- _MemHeader* p = (_MemHeader*)pNew->buffer;
- p->blkType = nodeFree;
- m_begin = (char*)(p + 1);
- m_end = (char*)pNew + m_alloc.alloc_size(pNew);
+ _CommitCurrentBlock();
+ m_begin = (char*)(pNew + 1);
+ m_end = m_begin + pNew->cbSize;
}
+
+ BOOST_MEMORY_ASSERT(m_end - m_begin >= cb);
+
_MemHeader* pAlloc = (_MemHeader*)(m_end -= cb);
pAlloc->blkType = nodeAlloced;
pAlloc->cbSize = cbData;
Added: sandbox/memory/boost/memory/stl/queue.hpp
==============================================================================
--- (empty file)
+++ sandbox/memory/boost/memory/stl/queue.hpp 2008-04-30 01:50:36 EDT (Wed, 30 Apr 2008)
@@ -0,0 +1,100 @@
+//
+// stl/queue.hpp (*)
+//
+// Copyright (c) 2004 - 2008 xushiwei (xushiweizh_at_[hidden])
+//
+// 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)
+//
+// See http://www.boost.org/libs/memory/index.htm for documentation.
+//
+#ifndef _BOOST_MEMORY_STL_QUEUE_HPP_
+#define _BOOST_MEMORY_STL_QUEUE_HPP_
+
+#if !defined(_DEQUE_) && !defined(_DEQUE)
+#include <deque> // std::deque
+#endif
+
+#if !defined(_FUNCTIONAL_) && !defined(_FUNCTIONAL)
+#include <functional> // std::less
+#endif
+
+#if !defined(_ALGORITHM_) && !defined(_ALGORITHM)
+#include <algorithm> // std::make_heap, etc
+#endif
+
+#ifndef _NS_BOOST_BEGIN
+#define _NS_BOOST_BEGIN namespace boost {
+#define _NS_BOOST_END }
+#endif
+
+_NS_BOOST_BEGIN
+
+// -------------------------------------------------------------------------
+
+template <class _Tp,
+ class _Sequence = std::deque<_Tp>,
+ class _Pred = std::less<_Tp> >
+class priority_queue
+{
+public:
+ typedef typename _Sequence::value_type value_type;
+ typedef typename _Sequence::size_type size_type;
+ typedef _Sequence container_type;
+
+ typedef typename _Sequence::reference reference;
+ typedef typename _Sequence::const_reference const_reference;
+
+protected:
+ _Sequence m_coll;
+ _Pred comp;
+
+public:
+ priority_queue() {}
+ explicit priority_queue(const _Pred& __x) : m_coll(), comp(__x) {}
+ priority_queue(const _Pred& __x, const _Sequence& __s)
+ : m_coll(__s), comp(__x)
+ { std::make_heap(m_coll.begin(), m_coll.end(), comp); }
+
+ template <class _InputIterator>
+ priority_queue(_InputIterator __first, _InputIterator __last)
+ : m_coll(__first, __last) { std::make_heap(m_coll.begin(), m_coll.end(), comp); }
+
+ template <class _InputIterator>
+ priority_queue(_InputIterator __first,
+ _InputIterator __last, const _Pred& __x)
+ : m_coll(__first, __last), comp(__x)
+ { std::make_heap(m_coll.begin(), m_coll.end(), comp); }
+
+ template <class _InputIterator>
+ priority_queue(_InputIterator __first, _InputIterator __last,
+ const _Pred& __x, const _Sequence& __s)
+ : m_coll(__s), comp(__x)
+ {
+ m_coll.insert(m_coll.end(), __first, __last);
+ std::make_heap(m_coll.begin(), m_coll.end(), comp);
+ }
+
+ bool empty() const { return m_coll.empty(); }
+ size_type size() const { return m_coll.size(); }
+ const_reference top() const { return m_coll.front(); }
+ void push(const value_type& __x) {
+ m_coll.push_back(__x);
+ std::push_heap(m_coll.begin(), m_coll.end(), comp);
+ }
+ void pop() {
+ std::pop_heap(m_coll.begin(), m_coll.end(), comp);
+ m_coll.pop_back();
+ }
+ void clear() {
+ m_coll.clear();
+ }
+};
+
+// -------------------------------------------------------------------------
+// $Log: $
+
+_NS_BOOST_END
+
+#endif /* _BOOST_MEMORY_STL_QUEUE_HPP_ */