1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
// -*- c++ -*-
/******************************************************************************
** recyclealloc.h
**
** Arena allocator with some modest recycling of freed resources.
** MIT license
**
*****************************************************************************/
#ifndef _RECYCLE_ALLOC_H
#define _RECYCLE_ALLOC_H
#include "arenaalloc.h"
#include <string.h>
#include <inttypes.h>
namespace ArenaAlloc
{
// todo:
// attempt refactor of boilerplate in _memblockimpl and _recycleallocimpl
template< typename AllocatorImpl, uint16_t StepSize = 16, uint16_t NumBuckets = 256 >
struct _recycleallocimpl : public _memblockimplbase<AllocatorImpl, _recycleallocimpl<AllocatorImpl> >
{
private:
static_assert( ( StepSize >= 16 && NumBuckets >= 16 ), "Min step size=16, Min num buckets=16" );
static_assert( !( StepSize & ( StepSize - 1 ) ), "Step size must be a power of 2" );
struct _freeEntry
{
// note: order of declaration matters
std::size_t m_size;
_freeEntry * m_next;
};
_freeEntry * m_buckets[ NumBuckets ]; // m_buckets[ NumBuckets - 1 ] is the oversize bucket
typedef struct _memblockimplbase< AllocatorImpl, _recycleallocimpl<AllocatorImpl> > base_t;
friend struct _memblockimplbase< AllocatorImpl, _recycleallocimpl<AllocatorImpl> >;
// to get around some sticky access issues between Alloc<T1> and Alloc<T2> when sharing
// the implementation.
template <typename U, typename A, typename M >
friend class Alloc;
template< typename T >
static void assign( const Alloc<T,AllocatorImpl, _recycleallocimpl<AllocatorImpl> >& src,
_recycleallocimpl *& dest )
{
dest = const_cast< _recycleallocimpl<AllocatorImpl>* >( src.m_impl );
}
static _recycleallocimpl<AllocatorImpl> * create( std::size_t defaultSize, AllocatorImpl& alloc )
{
return new (
alloc.allocate( sizeof( _recycleallocimpl ) ) ) _recycleallocimpl<AllocatorImpl>( defaultSize,
alloc );
}
static void destroy( _recycleallocimpl<AllocatorImpl> * objToDestroy )
{
AllocatorImpl allocImpl = objToDestroy->m_alloc;
objToDestroy-> ~_recycleallocimpl<AllocatorImpl>();
allocImpl.deallocate( objToDestroy );
}
_recycleallocimpl( std::size_t defaultSize, AllocatorImpl& allocImpl ):
_memblockimplbase<AllocatorImpl, _recycleallocimpl<AllocatorImpl> >( defaultSize, allocImpl )
{
memset( m_buckets, 0, sizeof( m_buckets ) );
#ifdef ARENA_ALLOC_DEBUG
fprintf( stdout, "_recycleallocimpl=%p constructed with default size=%ld\n", this,
base_t::m_defaultSize );
#endif
}
~_recycleallocimpl( )
{
#ifdef ARENA_ALLOC_DEBUG
fprintf( stdout, "~_recycleallocimpl() called on _recycleallocimpl=%p\n", this );
#endif
base_t::clear();
}
char * allocate( std::size_t numBytes )
{
numBytes = ( (numBytes + sizeof( std::size_t ) + StepSize - 1) / StepSize ) * StepSize;
char * returnValue = allocateInternal( numBytes );
if( !returnValue )
{
char * allocValue = base_t::allocate( numBytes );
if( !allocValue )
return 0; //allocation failure
*((std::size_t*)allocValue ) = numBytes; // that includes the header
return allocValue + sizeof( std::size_t );
}
return returnValue;
}
void deallocate( void * ptr )
{
deallocateInternal( reinterpret_cast<char*>(ptr) );
base_t::deallocate( ptr ); // this is called b/c it is known this just updates stats
}
char * allocateInternal( std::size_t numBytes )
{
// numBytes must already be rounded to a multiple of stepsize and have an
// extra sizeof( std::size_t ) bytes tacked on for the header
// pointer returned points sizeof( std::size_t ) bytes into the allocation
// bucket 0 is always null in this scheme.
uint16_t bucketNumber = numBytes / StepSize;
if( bucketNumber > NumBuckets - 1 )
bucketNumber = NumBuckets - 1; // oversize alloc
// search max 3 consecutive buckets for an item large enough.
// in the oversize bucket and only in the oversize bucket,
// search upto 3 items into the linked list for an entry
// large enough for the specified size
for( uint16_t bkt = bucketNumber, i = 0; i < 3 && bkt < NumBuckets; ++i, ++bkt )
{
if( m_buckets[ bkt ] )
return allocateFrom( numBytes, m_buckets[ bkt ] );
}
return 0;
}
char * allocateFrom( std::size_t numBytes, _freeEntry *& head )
{
_freeEntry * current = head;
_freeEntry * prev = 0;
int count = 0;
while( current && count < 3 )
{
if( current->m_size >= numBytes )
{
if( prev == 0 )
head = current->m_next;
else
prev->m_next = current->m_next;
return reinterpret_cast<char*>(¤t->m_next);
}
++count;
prev = current;
current = current->m_next;
}
return 0;
}
void deallocateInternal( char * ptr )
{
_freeEntry * v = reinterpret_cast< _freeEntry* >( ptr - sizeof( std::size_t ) );
uint16_t bucketNumber = v->m_size / StepSize;
if( bucketNumber > NumBuckets - 1 )
bucketNumber = NumBuckets - 1;
_freeEntry * next = m_buckets[ bucketNumber ];
v->m_next = next;
m_buckets[ bucketNumber ] = v;
}
};
template< typename T, typename Allocator = _newAllocatorImpl >
using RecycleAlloc = Alloc< T, Allocator, _recycleallocimpl<Allocator> >;
}
#endif
|
