aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2010-10-14 23:26:25 +0000
committerMike Buland <eichlan@xagasoft.com>2010-10-14 23:26:25 +0000
commit867dae89929a11a421ec21af71d494ad0ecc1963 (patch)
tree85d4330d5cdc0567194f1bfb2f9b1bda4e95b444 /src
parent13fa07280dd9ed2c62ad2be0848f88b0d85fe322 (diff)
downloadlibbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.gz
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.bz2
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.tar.xz
libbu++-867dae89929a11a421ec21af71d494ad0ecc1963.zip
SharedCore has more features now, which is cool, including a test to see if
another object of the parent type has the same core, and another to clone the parent object. That one is pretty cool, it means you can now get a real copy when you want to, great for multi-threaded stuff. Also, two more classes are now SharedCore: Hash and Heap!
Diffstat (limited to 'src')
-rw-r--r--src/archive.cpp9
-rw-r--r--src/archive.h4
-rw-r--r--src/archivebase.h5
-rw-r--r--src/array.h27
-rw-r--r--src/fbasicstring.h23
-rw-r--r--src/hash.h1036
-rw-r--r--src/heap.h298
-rw-r--r--src/list.h26
-rw-r--r--src/set.h760
-rw-r--r--src/sharedcore.h30
-rw-r--r--src/tests/sharedcore.cpp2
-rw-r--r--src/unit/hash.unit13
12 files changed, 836 insertions, 1397 deletions
diff --git a/src/archive.cpp b/src/archive.cpp
index 69d4a0c..7a10921 100644
--- a/src/archive.cpp
+++ b/src/archive.cpp
@@ -22,20 +22,15 @@ Bu::Archive::~Archive()
22{ 22{
23} 23}
24 24
25void Bu::Archive::write( const void *pData, int32_t nSize ) 25void Bu::Archive::write( const void *pData, size_t nSize )
26{ 26{
27 if( nSize == 0 || pData == NULL ) 27 if( nSize == 0 || pData == NULL )
28 return; 28 return;
29 29
30// Bu::sio << "Writing starting at pos: " << rStream.tell() << " - "
31// << Bu::sio.flush;
32
33 rStream.write( (const char *)pData, nSize ); 30 rStream.write( (const char *)pData, nSize );
34//
35// Bu::sio << rStream.tell() << " (" << nSize << "b)" << Bu::sio.nl;
36} 31}
37 32
38void Bu::Archive::read( void *pData, int32_t nSize ) 33void Bu::Archive::read( void *pData, size_t nSize )
39{ 34{
40 if( nSize == 0 || pData == NULL ) 35 if( nSize == 0 || pData == NULL )
41 return; 36 return;
diff --git a/src/archive.h b/src/archive.h
index bd85113..9d2aee2 100644
--- a/src/archive.h
+++ b/src/archive.h
@@ -83,8 +83,8 @@ namespace Bu
83 virtual ~Archive(); 83 virtual ~Archive();
84 virtual void close(); 84 virtual void close();
85 85
86 virtual void write(const void *, int32_t); 86 virtual void write( const void *pData, size_t iSize );
87 virtual void read(void *, int32_t); 87 virtual void read( void *pData, size_t iSize );
88 88
89 /** 89 /**
90 * For storage, get an ID for the pointer to the object you're going to 90 * For storage, get an ID for the pointer to the object you're going to
diff --git a/src/archivebase.h b/src/archivebase.h
index c871bb5..18591f0 100644
--- a/src/archivebase.h
+++ b/src/archivebase.h
@@ -9,6 +9,7 @@
9#define BU_ARCHIVE_BASE_H 9#define BU_ARCHIVE_BASE_H
10 10
11#include <stdint.h> 11#include <stdint.h>
12#include <unistd.h>
12 13
13namespace Bu 14namespace Bu
14{ 15{
@@ -19,8 +20,8 @@ namespace Bu
19 virtual ~ArchiveBase(); 20 virtual ~ArchiveBase();
20 21
21 virtual void close()=0; 22 virtual void close()=0;
22 virtual void write( const void *pData, int32_t iLength )=0; 23 virtual void write( const void *pData, size_t iLength )=0;
23 virtual void read( void *pData, int32_t iLength )=0; 24 virtual void read( void *pData, size_t iLength )=0;
24 virtual bool isLoading()=0; 25 virtual bool isLoading()=0;
25 }; 26 };
26 27
diff --git a/src/array.h b/src/array.h
index eeee677..fc4fb12 100644
--- a/src/array.h
+++ b/src/array.h
@@ -18,9 +18,17 @@ namespace Bu
18 subExceptionDecl( ArrayException ) 18 subExceptionDecl( ArrayException )
19 19
20 template<typename value, int inc, typename valuealloc> 20 template<typename value, int inc, typename valuealloc>
21 class Array;
22
23 template<typename value, int inc, typename valuealloc>
21 class ArrayCore 24 class ArrayCore
22 { 25 {
23 public: 26 friend class Array<value, inc, valuealloc>;
27 friend class SharedCore<
28 Array<value, inc, valuealloc>,
29 ArrayCore<value, inc, valuealloc>
30 >;
31 private:
24 ArrayCore() : 32 ArrayCore() :
25 pData( NULL ), 33 pData( NULL ),
26 iSize( 0 ), 34 iSize( 0 ),
@@ -110,16 +118,20 @@ namespace Bu
110 *@ingroup Containers 118 *@ingroup Containers
111 */ 119 */
112 template<typename value, int inc=10, typename valuealloc=std::allocator<value> > 120 template<typename value, int inc=10, typename valuealloc=std::allocator<value> >
113 class Array : public SharedCore<ArrayCore<value, inc, valuealloc> > 121 class Array : public SharedCore<
122 Array<value, inc, valuealloc>,
123 ArrayCore<value, inc, valuealloc>
124 >
114 { 125 {
115 private: 126 private:
116 typedef class Array<value, inc, valuealloc> MyType; 127 typedef class Array<value, inc, valuealloc> MyType;
117 typedef class ArrayCore<value, inc, valuealloc> Core; 128 typedef class ArrayCore<value, inc, valuealloc> Core;
118 129
119 protected: 130 protected:
120 using SharedCore< Core >::core; 131 using SharedCore<MyType, Core>::core;
121 using SharedCore< Core >::_hardCopy; 132 using SharedCore<MyType, Core>::_hardCopy;
122 using SharedCore< Core >::_allocateCore; 133 using SharedCore<MyType, Core>::_resetCore;
134 using SharedCore<MyType, Core>::_allocateCore;
123 135
124 public: 136 public:
125 struct const_iterator; 137 struct const_iterator;
@@ -130,7 +142,7 @@ namespace Bu
130 } 142 }
131 143
132 Array( const MyType &src ) : 144 Array( const MyType &src ) :
133 SharedCore< Core >( src ) 145 SharedCore<MyType, Core >( src )
134 { 146 {
135 } 147 }
136 148
@@ -168,8 +180,7 @@ namespace Bu
168 */ 180 */
169 void clear() 181 void clear()
170 { 182 {
171 _hardCopy(); 183 _resetCore();
172 core->clear();
173 } 184 }
174 185
175 MyType &append( const value &rVal ) 186 MyType &append( const value &rVal )
diff --git a/src/fbasicstring.h b/src/fbasicstring.h
index 19853f5..82c5137 100644
--- a/src/fbasicstring.h
+++ b/src/fbasicstring.h
@@ -34,10 +34,19 @@ namespace Bu
34 }; 34 };
35 35
36#define cpy( dest, src, size ) Bu::memcpy( dest, src, size*sizeof(chr) ) 36#define cpy( dest, src, size ) Bu::memcpy( dest, src, size*sizeof(chr) )
37
38 template< typename chr, int nMinSize, typename chralloc,
39 typename chunkalloc> class FBasicString;
37 40
38 template<typename chr, int nMinSize, typename chralloc, typename chunkalloc> 41 template<typename chr, int nMinSize, typename chralloc, typename chunkalloc>
39 struct FStringCore 42 struct FStringCore
40 { 43 {
44 friend class FBasicString<chr, nMinSize, chralloc, chunkalloc>;
45 friend class SharedCore<
46 FBasicString<chr, nMinSize, chralloc, chunkalloc>,
47 FStringCore<chr, nMinSize, chralloc, chunkalloc>
48 >;
49 private:
41 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> MyType; 50 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> MyType;
42 typedef struct FStringChunk<chr> Chunk; 51 typedef struct FStringChunk<chr> Chunk;
43 FStringCore() : 52 FStringCore() :
@@ -174,16 +183,20 @@ namespace Bu
174 *@param chralloc (typename) Memory Allocator for chr 183 *@param chralloc (typename) Memory Allocator for chr
175 *@param chunkalloc (typename) Memory Allocator for chr chunks 184 *@param chunkalloc (typename) Memory Allocator for chr chunks
176 */ 185 */
177 template< typename chr, int nMinSize=256, typename chralloc=std::allocator<chr>, typename chunkalloc=std::allocator<struct FStringChunk<chr> > > 186 template< typename chr, int nMinSize=256,
178 class FBasicString : public SharedCore< FStringCore<chr, nMinSize, chralloc, chunkalloc> > 187 typename chralloc=std::allocator<chr>,
188 typename chunkalloc=std::allocator<struct FStringChunk<chr> > >
189 class FBasicString : public SharedCore<
190 FBasicString<chr, nMinSize, chralloc, chunkalloc>,
191 FStringCore<chr, nMinSize, chralloc, chunkalloc> >
179 { 192 {
180 protected: 193 protected:
181 typedef struct FStringChunk<chr> Chunk; 194 typedef struct FStringChunk<chr> Chunk;
182 typedef struct FBasicString<chr, nMinSize, chralloc, chunkalloc> MyType; 195 typedef struct FBasicString<chr, nMinSize, chralloc, chunkalloc> MyType;
183 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> Core; 196 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> Core;
184 197
185 using SharedCore< Core >::core; 198 using SharedCore<MyType, Core >::core;
186 using SharedCore< Core >::_hardCopy; 199 using SharedCore<MyType, Core >::_hardCopy;
187 200
188 public: 201 public:
189 FBasicString() 202 FBasicString()
@@ -201,7 +214,7 @@ namespace Bu
201 } 214 }
202 215
203 FBasicString( const MyType &rSrc ) : 216 FBasicString( const MyType &rSrc ) :
204 SharedCore<Core>( rSrc ) 217 SharedCore<MyType, Core>( rSrc )
205 { 218 {
206 } 219 }
207 220
diff --git a/src/hash.h b/src/hash.h
index 1cb539b..714a7f7 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -12,7 +12,8 @@
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/list.h" 13#include "bu/list.h"
14#include "bu/util.h" 14#include "bu/util.h"
15#include "archivebase.h" 15#include "bu/archivebase.h"
16#include "bu/sharedcore.h"
16 17
17#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) 18#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
18 19
@@ -49,137 +50,354 @@ namespace Bu
49 } 50 }
50 }; 51 };
51 52
52 template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> > 53 template<typename key, typename value, typename sizecalc, typename keyalloc,
54 typename valuealloc, typename challoc>
53 class Hash; 55 class Hash;
54 56
55 template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> > 57 template<typename key, typename value, typename sizecalc, typename keyalloc,
56 struct HashProxy 58 typename valuealloc, typename challoc >
59 class HashCore
57 { 60 {
58 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>; 61 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
62 friend class SharedCore<
63 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
64 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
65 >;
59 private: 66 private:
60 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, const key *k, uint32_t nPos, uint32_t hash ) : 67 HashCore() :
61 hsh( h ), 68 nCapacity( 0 ),
62 pKey( k ), 69 nFilled( 0 ),
63 nPos( nPos ), 70 nDeleted( 0 ),
64 hash( hash ), 71 bFilled( NULL ),
65 bFilled( false ) 72 bDeleted( NULL ),
73 aKeys( NULL ),
74 aValues( NULL ),
75 aHashCodes( NULL )
66 { 76 {
67 } 77 }
68 78
69 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) : 79 virtual ~HashCore()
70 hsh( h ),
71 nPos( nPos ),
72 pValue( pValue ),
73 bFilled( true )
74 { 80 {
81 clear();
75 } 82 }
76 83
77 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 84 void init()
78 const key *pKey; 85 {
79 uint32_t nPos; 86 if( nCapacity > 0 )
80 _value *pValue; 87 return;
81 uint32_t hash;
82 bool bFilled;
83 88
84 public: 89 nCapacity = 11;
85 /** 90 nKeysSize = bitsToBytes( nCapacity );
86 * Cast operator for HashProxy. 91 bFilled = ca.allocate( nKeysSize );
87 *@returns (value_type &) The value the HashProxy is pointing to. 92 bDeleted = ca.allocate( nKeysSize );
88 */ 93 clearBits();
89 operator _value &() 94
95 aHashCodes = ca.allocate( nCapacity );
96 aKeys = ka.allocate( nCapacity );
97 aValues = va.allocate( nCapacity );
98 }
99
100 void clearBits()
90 { 101 {
91 if( bFilled == false ) 102 if( nCapacity == 0 )
92 throw HashException( 103 return;
93 excodeNotFilled, 104
94 "No data assosiated with that key." 105 for( uint32_t j = 0; j < nKeysSize; j++ )
95 ); 106 {
96 return *pValue; 107 bFilled[j] = bDeleted[j] = 0;
108 }
97 } 109 }
98 110
99 /** 111 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
100 * Direct function for retrieving a value out of the HashProxy.
101 *@returns (value_type &) The value pointed to by this HashProxy.
102 */
103 DEPRECATED
104 _value &value()
105 { 112 {
106 if( bFilled == false ) 113 init();
107 throw HashException( 114
108 excodeNotFilled, 115 bFilled[loc/32] |= (1<<(loc%32));
109 "No data assosiated with that key." 116 va.construct( &aValues[loc], v );
110 ); 117 ka.construct( &aKeys[loc], k );
111 return *pValue; 118 aHashCodes[loc] = hash;
119 nFilled++;
120 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
121 // nFilled, nDeleted, nCapacity );
122 }
123
124 void _erase( uint32_t loc )
125 {
126 if( nCapacity == 0 )
127 return;
128
129 bDeleted[loc/32] |= (1<<(loc%32));
130 va.destroy( &aValues[loc] );
131 ka.destroy( &aKeys[loc] );
132 nDeleted++;
133 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
134 // nFilled, nDeleted, nCapacity );
135 }
136
137 key &getKeyAtPos( uint32_t nPos )
138 {
139 if( nPos >= nCapacity )
140 throw HashException("Referenced position invalid.");
141 return aKeys[nPos];
112 } 142 }
113 143
114 /** 144 const key &getKeyAtPos( uint32_t nPos ) const
115 * Direct function for retrieving a value out of the HashProxy.
116 *@returns (value_type &) The value pointed to by this HashProxy.
117 */
118 _value &getValue()
119 { 145 {
120 if( bFilled == false ) 146 if( nPos >= nCapacity )
121 throw HashException( 147 throw HashException("Referenced position invalid.");
122 excodeNotFilled, 148 return aKeys[nPos];
123 "No data assosiated with that key." 149 }
124 ); 150
125 return *pValue; 151 value &getValueAtPos( uint32_t nPos )
152 {
153 if( nPos >= nCapacity )
154 throw HashException("Referenced position invalid.");
155 return aValues[nPos];
156 }
157
158 const value &getValueAtPos( uint32_t nPos ) const
159 {
160 if( nPos >= nCapacity )
161 throw HashException("Referenced position invalid.");
162 return aValues[nPos];
126 } 163 }
127 164
128 /** 165 uint32_t getFirstPos( bool &bFinished ) const
129 * Whether this HashProxy points to something real or not.
130 */
131 bool isFilled()
132 { 166 {
133 return bFilled; 167 for( uint32_t j = 0; j < nCapacity; j++ )
168 {
169 if( isFilled( j ) )
170 if( !isDeleted( j ) )
171 return j;
172 }
173
174 bFinished = true;
175 return 0;
134 } 176 }
135 177
136 /** 178 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
137 * Erase the data pointed to by this HashProxy.
138 */
139 void erase()
140 { 179 {
141 if( bFilled ) 180 for( uint32_t j = nPos+1; j < nCapacity; j++ )
142 { 181 {
143 hsh._erase( nPos ); 182 if( isFilled( j ) )
144 hsh.onDelete(); 183 if( !isDeleted( j ) )
184 return j;
145 } 185 }
186
187 bFinished = true;
188 return 0;
146 } 189 }
147 190
148 /** 191 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
149 * Assign data to this point in the hash table.
150 *@param nval (value_type) the data to assign.
151 */
152 _value operator=( _value nval )
153 { 192 {
154 if( bFilled ) 193 init();
194
195 uint32_t nCur = hash%nCapacity;
196
197 // First we scan to see if the key is already there, abort if we
198 // run out of probing room, or we find a non-filled entry
199 int8_t j;
200 for( j = 0;
201 isFilled( nCur ) && j < 32;
202 nCur = (nCur + (1<<j))%nCapacity, j++
203 )
155 { 204 {
156 hsh.va.destroy( &hsh.aValues[nPos] ); 205 // Is this the same hash code we were looking for?
157 hsh.va.construct( &hsh.aValues[nPos], nval ); 206 if( hash == aHashCodes[nCur] )
158 hsh.onUpdate(); 207 {
208 // Skip over deleted entries. Deleted entries are also filled,
209 // so we only have to do this check here.
210 if( isDeleted( nCur ) )
211 continue;
212
213 // Is it really the same key? (for safety)
214 if( __cmpHashKeys( aKeys[nCur], k ) == true )
215 {
216 bFill = true;
217 return nCur;
218 }
219 }
220 }
221
222 // This is our insurance, if the table is full, then go ahead and
223 // rehash, then try again.
224 if( (isFilled( nCur ) || j == 32) && rehash == true )
225 {
226 reHash( szCalc( nCapacity, nFilled, nDeleted ) );
227
228 // This is potentially dangerous, and could cause an infinite loop.
229 // Be careful writing probe, eh?
230 return probe( hash, k, bFill );
231 }
232
233 bFill = false;
234 return nCur;
235 }
236
237 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
238 {
239 if( nCapacity == 0 )
240 throw Bu::ExceptionBase("Probe in empty hash table.");
241
242 uint32_t nCur = hash%nCapacity;
243
244 // First we scan to see if the key is already there, abort if we
245 // run out of probing room, or we find a non-filled entry
246 for( int8_t j = 0;
247 isFilled( nCur ) && j < 32;
248 nCur = (nCur + (1<<j))%nCapacity, j++
249 )
250 {
251 // Is this the same hash code we were looking for?
252 if( hash == aHashCodes[nCur] )
253 {
254 // Skip over deleted entries. Deleted entries are also filled,
255 // so we only have to do this check here.
256 if( isDeleted( nCur ) )
257 continue;
258
259 // Is it really the same key? (for safety)
260 if( __cmpHashKeys( aKeys[nCur], k ) == true )
261 {
262 bFill = true;
263 return nCur;
264 }
265 }
266 }
267
268 bFill = false;
269 return nCur;
270 }
271
272 void insert( const key &k, const value &v )
273 {
274 uint32_t hash = __calcHashCode( k );
275 bool bFill;
276 uint32_t nPos = probe( hash, k, bFill );
277
278 if( bFill )
279 {
280 va.destroy( &aValues[nPos] );
281 va.construct( &aValues[nPos], v );
159 } 282 }
160 else 283 else
161 { 284 {
162 hsh.fill( nPos, *pKey, nval, hash ); 285 fill( nPos, k, v, hash );
163 hsh.onInsert();
164 } 286 }
287 }
165 288
166 return nval; 289 void reHash( uint32_t nNewSize )
290 {
291 //printf("---REHASH---");
292 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
293 // nFilled, nDeleted, nCapacity );
294
295 // Save all the old data
296 uint32_t nOldCapacity = nCapacity;
297 uint32_t *bOldFilled = bFilled;
298 uint32_t *aOldHashCodes = aHashCodes;
299 uint32_t nOldKeysSize = nKeysSize;
300 uint32_t *bOldDeleted = bDeleted;
301 value *aOldValues = aValues;
302 key *aOldKeys = aKeys;
303
304 // Calculate new sizes
305 nCapacity = nNewSize;
306 nKeysSize = bitsToBytes( nCapacity );
307
308 // Allocate new memory + prep
309 bFilled = ca.allocate( nKeysSize );
310 bDeleted = ca.allocate( nKeysSize );
311 clearBits();
312
313 aHashCodes = ca.allocate( nCapacity );
314 aKeys = ka.allocate( nCapacity );
315 aValues = va.allocate( nCapacity );
316
317 nDeleted = nFilled = 0;
318
319 // Re-insert all of the old data (except deleted items)
320 for( uint32_t j = 0; j < nOldCapacity; j++ )
321 {
322 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
323 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
324 {
325 insert( aOldKeys[j], aOldValues[j] );
326 }
327 }
328
329 // Delete all of the old data
330 for( uint32_t j = 0; j < nOldCapacity; j++ )
331 {
332 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
333 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
334 {
335 va.destroy( &aOldValues[j] );
336 ka.destroy( &aOldKeys[j] );
337 }
338 }
339 va.deallocate( aOldValues, nOldCapacity );
340 ka.deallocate( aOldKeys, nOldCapacity );
341 ca.deallocate( bOldFilled, nOldKeysSize );
342 ca.deallocate( bOldDeleted, nOldKeysSize );
343 ca.deallocate( aOldHashCodes, nOldCapacity );
167 } 344 }
168 345
169 /** 346 bool isFilled( uint32_t loc ) const
170 * Pointer extraction operator. Access to members of data pointed to
171 * by HashProxy.
172 *@returns (value_type *)
173 */
174 _value *operator->()
175 { 347 {
176 if( bFilled == false ) 348 if( loc >= nCapacity )
177 throw HashException( 349 throw HashException("Referenced position invalid.");
178 excodeNotFilled, 350 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
179 "No data assosiated with that key." 351 }
180 ); 352
181 return pValue; 353 bool isDeleted( uint32_t loc ) const
354 {
355 if( loc >= nCapacity )
356 throw HashException("Referenced position invalid.");
357 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
358 }
359
360 void clear()
361 {
362 for( uint32_t j = 0; j < nCapacity; j++ )
363 {
364 if( isFilled( j ) )
365 if( !isDeleted( j ) )
366 {
367 va.destroy( &aValues[j] );
368 ka.destroy( &aKeys[j] );
369 }
370 }
371 va.deallocate( aValues, nCapacity );
372 ka.deallocate( aKeys, nCapacity );
373 ca.deallocate( bFilled, nKeysSize );
374 ca.deallocate( bDeleted, nKeysSize );
375 ca.deallocate( aHashCodes, nCapacity );
376
377 bFilled = NULL;
378 bDeleted = NULL;
379 aKeys = NULL;
380 aValues = NULL;
381 aHashCodes = NULL;
382
383 nCapacity = 0;
384 nFilled = 0;
385 nDeleted = 0;
182 } 386 }
387
388 uint32_t nCapacity;
389 uint32_t nFilled;
390 uint32_t nDeleted;
391 uint32_t *bFilled;
392 uint32_t *bDeleted;
393 uint32_t nKeysSize;
394 key *aKeys;
395 value *aValues;
396 uint32_t *aHashCodes;
397 valuealloc va;
398 keyalloc ka;
399 challoc ca;
400 sizecalc szCalc;
183 }; 401 };
184 402
185 /** 403 /**
@@ -224,119 +442,38 @@ namespace Bu
224 *@param challoc (typename) Byte allocator for bitflags 442 *@param challoc (typename) Byte allocator for bitflags
225 *@ingroup Containers 443 *@ingroup Containers
226 */ 444 */
227 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 445 template<typename key, typename value,
228 class Hash 446 typename sizecalc = __calcNextTSize_fast,
447 typename keyalloc = std::allocator<key>,
448 typename valuealloc = std::allocator<value>,
449 typename challoc = std::allocator<uint32_t>
450 >
451 class Hash : public SharedCore<
452 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
453 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
454 >
229 { 455 {
230 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>; 456 private:
457 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core;
231 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType; 458 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType;
459 protected:
460 using SharedCore<MyType, Core>::core;
461 using SharedCore<MyType, Core>::_hardCopy;
462 using SharedCore<MyType, Core>::_resetCore;
463 using SharedCore<MyType, Core>::_allocateCore;
464
232 public: 465 public:
233 Hash() : 466 Hash()
234 nCapacity( 11 ),
235 nFilled( 0 ),
236 nDeleted( 0 ),
237 bFilled( NULL ),
238 bDeleted( NULL ),
239 aKeys( NULL ),
240 aValues( NULL ),
241 aHashCodes( NULL )
242 { 467 {
243 nKeysSize = bitsToBytes( nCapacity );
244 bFilled = ca.allocate( nKeysSize );
245 bDeleted = ca.allocate( nKeysSize );
246 clearBits();
247
248 aHashCodes = ca.allocate( nCapacity );
249 aKeys = ka.allocate( nCapacity );
250 aValues = va.allocate( nCapacity );
251 } 468 }
252 469
253 Hash( const Hash &src ) : 470 Hash( const MyType &src ) :
254 nCapacity( src.nCapacity ), 471 SharedCore<MyType, Core >( src )
255 nFilled( 0 ),
256 nDeleted( 0 ),
257 bFilled( NULL ),
258 bDeleted( NULL ),
259 aKeys( NULL ),
260 aValues( NULL ),
261 aHashCodes( NULL )
262 { 472 {
263 nKeysSize = bitsToBytes( nCapacity );
264 bFilled = ca.allocate( nKeysSize );
265 bDeleted = ca.allocate( nKeysSize );
266 clearBits();
267
268 aHashCodes = ca.allocate( nCapacity );
269 aKeys = ka.allocate( nCapacity );
270 aValues = va.allocate( nCapacity );
271
272 for( uint32_t j = 0; j < src.nCapacity; j++ )
273 {
274 if( src.isFilled( j ) && !src.isDeleted( j ) )
275 {
276 insert( src.aKeys[j], src.aValues[j] );
277 }
278 }
279 }
280
281 /**
282 * Hashtable assignment operator. Clears this hashtable and
283 * copies RH into it.
284 */
285 Hash &operator=( const Hash &src )
286 {
287 for( uint32_t j = 0; j < nCapacity; j++ )
288 {
289 if( isFilled( j ) && !isDeleted( j ) )
290 {
291 va.destroy( &aValues[j] );
292 ka.destroy( &aKeys[j] );
293 }
294 }
295 va.deallocate( aValues, nCapacity );
296 ka.deallocate( aKeys, nCapacity );
297 ca.deallocate( bFilled, nKeysSize );
298 ca.deallocate( bDeleted, nKeysSize );
299 ca.deallocate( aHashCodes, nCapacity );
300
301 nFilled = 0;
302 nDeleted = 0;
303 nCapacity = src.nCapacity;
304 nKeysSize = bitsToBytes( nCapacity );
305 bFilled = ca.allocate( nKeysSize );
306 bDeleted = ca.allocate( nKeysSize );
307 clearBits();
308
309 aHashCodes = ca.allocate( nCapacity );
310 aKeys = ka.allocate( nCapacity );
311 aValues = va.allocate( nCapacity );
312
313 for( uint32_t j = 0; j < src.nCapacity; j++ )
314 {
315 if( src.isFilled( j ) && !src.isDeleted( j ) )
316 {
317 insert( src.aKeys[j], src.aValues[j] );
318 }
319 }
320
321 return *this;
322 } 473 }
323 474
324 virtual ~Hash() 475 virtual ~Hash()
325 { 476 {
326 for( uint32_t j = 0; j < nCapacity; j++ )
327 {
328 if( isFilled( j ) )
329 if( !isDeleted( j ) )
330 {
331 va.destroy( &aValues[j] );
332 ka.destroy( &aKeys[j] );
333 }
334 }
335 va.deallocate( aValues, nCapacity );
336 ka.deallocate( aKeys, nCapacity );
337 ca.deallocate( bFilled, nKeysSize );
338 ca.deallocate( bDeleted, nKeysSize );
339 ca.deallocate( aHashCodes, nCapacity );
340 } 477 }
341 478
342 /** 479 /**
@@ -345,7 +482,7 @@ namespace Bu
345 */ 482 */
346 uint32_t getCapacity() const 483 uint32_t getCapacity() const
347 { 484 {
348 return nCapacity; 485 return core->nCapacity;
349 } 486 }
350 487
351 /** 488 /**
@@ -355,7 +492,7 @@ namespace Bu
355 */ 492 */
356 uint32_t getFill() const 493 uint32_t getFill() const
357 { 494 {
358 return nFilled; 495 return core->nFilled;
359 } 496 }
360 497
361 /** 498 /**
@@ -364,12 +501,12 @@ namespace Bu
364 */ 501 */
365 uint32_t getSize() const 502 uint32_t getSize() const
366 { 503 {
367 return nFilled-nDeleted; 504 return core->nFilled-core->nDeleted;
368 } 505 }
369 506
370 bool isEmpty() const 507 bool isEmpty() const
371 { 508 {
372 return (nFilled-nDeleted) == 0; 509 return (core->nFilled-core->nDeleted) == 0;
373 } 510 }
374 511
375 /** 512 /**
@@ -379,27 +516,140 @@ namespace Bu
379 */ 516 */
380 uint32_t getDeleted() const 517 uint32_t getDeleted() const
381 { 518 {
382 return nDeleted; 519 return core->nDeleted;
383 } 520 }
384 521
522 struct HashProxy
523 {
524 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
525 private:
526 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) :
527 hsh( h ),
528 pKey( k ),
529 nPos( nPos ),
530 hash( hash ),
531 bFilled( false )
532 {
533 }
534
535 HashProxy( MyType &h, uint32_t nPos, value *pValue ) :
536 hsh( h ),
537 nPos( nPos ),
538 pValue( pValue ),
539 bFilled( true )
540 {
541 }
542
543 MyType &hsh;
544 const key *pKey;
545 uint32_t nPos;
546 value *pValue;
547 uint32_t hash;
548 bool bFilled;
549
550 public:
551 /**
552 * Cast operator for HashProxy.
553 *@returns (value_type &) The value the HashProxy is pointing to.
554 */
555 operator value &()
556 {
557 if( bFilled == false )
558 throw HashException(
559 excodeNotFilled,
560 "No data assosiated with that key."
561 );
562 return *pValue;
563 }
564
565 /**
566 * Direct function for retrieving a value out of the HashProxy.
567 *@returns (value_type &) The value pointed to by this HashProxy.
568 */
569 value &getValue()
570 {
571 if( bFilled == false )
572 throw HashException(
573 excodeNotFilled,
574 "No data assosiated with that key."
575 );
576 return *pValue;
577 }
578
579 /**
580 * Whether this HashProxy points to something real or not.
581 */
582 bool isFilled()
583 {
584 return bFilled;
585 }
586
587 /**
588 * Erase the data pointed to by this HashProxy.
589 */
590 void erase()
591 {
592 if( bFilled )
593 {
594 hsh.core->_erase( nPos );
595 }
596 }
597
598 /**
599 * Assign data to this point in the hash table.
600 *@param nval (value_type) the data to assign.
601 */
602 value operator=( value nval )
603 {
604 if( bFilled )
605 {
606 hsh.core->va.destroy( &hsh.core->aValues[nPos] );
607 hsh.core->va.construct( &hsh.core->aValues[nPos], nval );
608 }
609 else
610 {
611 hsh.core->fill( nPos, *pKey, nval, hash );
612 }
613
614 return nval;
615 }
616
617 /**
618 * Pointer extraction operator. Access to members of data pointed to
619 * by HashProxy.
620 *@returns (value_type *)
621 */
622 value *operator->()
623 {
624 if( bFilled == false )
625 throw HashException(
626 excodeNotFilled,
627 "No data assosiated with that key."
628 );
629 return pValue;
630 }
631 };
632
385 /** 633 /**
386 * Hash table index operator 634 * Hash table index operator
387 *@param k (key_type) Key of data to be retrieved. 635 *@param k (key_type) Key of data to be retrieved.
388 *@returns (HashProxy) Proxy pointing to the data. 636 *@returns (HashProxy) Proxy pointing to the data.
389 */ 637 */
390 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( const key &k ) 638 HashProxy operator[]( const key &k )
391 { 639 {
640 _hardCopy();
641
392 uint32_t hash = __calcHashCode( k ); 642 uint32_t hash = __calcHashCode( k );
393 bool bFill; 643 bool bFill;
394 uint32_t nPos = probe( hash, k, bFill ); 644 uint32_t nPos = core->probe( hash, k, bFill );
395 645
396 if( bFill ) 646 if( bFill )
397 { 647 {
398 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] ); 648 return HashProxy( *this, nPos, &core->aValues[nPos] );
399 } 649 }
400 else 650 else
401 { 651 {
402 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash ); 652 return HashProxy( *this, &k, nPos, hash );
403 } 653 }
404 } 654 }
405 655
@@ -408,39 +658,28 @@ namespace Bu
408 *@param k (key_type) Key to list the value under. 658 *@param k (key_type) Key to list the value under.
409 *@param v (value_type) Value to store in the hash table. 659 *@param v (value_type) Value to store in the hash table.
410 */ 660 */
411 virtual void insert( const key &k, const value &v ) 661 void insert( const key &k, const value &v )
412 { 662 {
413 uint32_t hash = __calcHashCode( k ); 663 _hardCopy();
414 bool bFill;
415 uint32_t nPos = probe( hash, k, bFill );
416 664
417 if( bFill ) 665 core->insert( k, v );
418 {
419 va.destroy( &aValues[nPos] );
420 va.construct( &aValues[nPos], v );
421 onUpdate();
422 }
423 else
424 {
425 fill( nPos, k, v, hash );
426 onInsert();
427 }
428 } 666 }
429 667
430 /** 668 /**
431 * Remove a value from the hash table. 669 * Remove a value from the hash table.
432 *@param k (key_type) The data under this key will be erased. 670 *@param k (key_type) The data under this key will be erased.
433 */ 671 */
434 virtual void erase( const key &k ) 672 void erase( const key &k )
435 { 673 {
674 _hardCopy();
675
436 uint32_t hash = __calcHashCode( k ); 676 uint32_t hash = __calcHashCode( k );
437 bool bFill; 677 bool bFill;
438 uint32_t nPos = probe( hash, k, bFill ); 678 uint32_t nPos = core->probe( hash, k, bFill );
439 679
440 if( bFill ) 680 if( bFill )
441 { 681 {
442 _erase( nPos ); 682 core->_erase( nPos );
443 onDelete();
444 } 683 }
445 } 684 }
446 685
@@ -450,14 +689,16 @@ namespace Bu
450 * Remove a value from the hash pointed to from an iterator. 689 * Remove a value from the hash pointed to from an iterator.
451 *@param i (iterator &) The data to be erased. 690 *@param i (iterator &) The data to be erased.
452 */ 691 */
453 virtual void erase( struct iterator &i ) 692 void erase( struct iterator &i )
454 { 693 {
455 if( this != i.hsh ) 694 if( this != i.hsh )
456 throw HashException("This iterator didn't come from this Hash."); 695 throw HashException("This iterator didn't come from this Hash.");
457 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) 696
697 _hardCopy();
698
699 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) )
458 { 700 {
459 _erase( i.nPos ); 701 core->_erase( i.nPos );
460 onDelete();
461 } 702 }
462 } 703 }
463 704
@@ -466,17 +707,7 @@ namespace Bu
466 */ 707 */
467 virtual void clear() 708 virtual void clear()
468 { 709 {
469 for( uint32_t j = 0; j < nCapacity; j++ ) 710 _resetCore();
470 {
471 if( isFilled( j ) )
472 if( !isDeleted( j ) )
473 {
474 _erase( j );
475 onDelete();
476 }
477 }
478
479 clearBits();
480 } 711 }
481 712
482 /** 713 /**
@@ -484,15 +715,17 @@ namespace Bu
484 *@param k (key_type) Key pointing to the data to be retrieved. 715 *@param k (key_type) Key pointing to the data to be retrieved.
485 *@returns (value_type &) The data pointed to by (k). 716 *@returns (value_type &) The data pointed to by (k).
486 */ 717 */
487 virtual value &get( const key &k ) 718 value &get( const key &k )
488 { 719 {
720 _hardCopy();
721
489 uint32_t hash = __calcHashCode( k ); 722 uint32_t hash = __calcHashCode( k );
490 bool bFill; 723 bool bFill;
491 uint32_t nPos = probe( hash, k, bFill, false ); 724 uint32_t nPos = core->probe( hash, k, bFill, false );
492 725
493 if( bFill ) 726 if( bFill )
494 { 727 {
495 return aValues[nPos]; 728 return core->aValues[nPos];
496 } 729 }
497 else 730 else
498 { 731 {
@@ -509,15 +742,15 @@ namespace Bu
509 *@returns (const value_type &) A const version of the data pointed 742 *@returns (const value_type &) A const version of the data pointed
510 * to by (k). 743 * to by (k).
511 */ 744 */
512 virtual const value &get( const key &k ) const 745 const value &get( const key &k ) const
513 { 746 {
514 uint32_t hash = __calcHashCode( k ); 747 uint32_t hash = __calcHashCode( k );
515 bool bFill; 748 bool bFill;
516 uint32_t nPos = probe( hash, k, bFill ); 749 uint32_t nPos = core->probe( hash, k, bFill );
517 750
518 if( bFill ) 751 if( bFill )
519 { 752 {
520 return aValues[nPos]; 753 return core->aValues[nPos];
521 } 754 }
522 else 755 else
523 { 756 {
@@ -533,18 +766,10 @@ namespace Bu
533 *@param k (key_type) The key to check. 766 *@param k (key_type) The key to check.
534 *@returns (bool) Whether there was an item in the hash under key (k). 767 *@returns (bool) Whether there was an item in the hash under key (k).
535 */ 768 */
536 virtual bool has( const key &k ) 769 bool has( const key &k ) const
537 { 770 {
538 bool bFill; 771 bool bFill;
539 probe( __calcHashCode( k ), k, bFill, false ); 772 core->probe( __calcHashCode( k ), k, bFill );
540
541 return bFill;
542 }
543
544 virtual bool has( const key &k ) const
545 {
546 bool bFill;
547 probe( __calcHashCode( k ), k, bFill );
548 773
549 return bFill; 774 return bFill;
550 } 775 }
@@ -561,7 +786,7 @@ namespace Bu
561 nPos( 0 ), 786 nPos( 0 ),
562 bFinished( false ) 787 bFinished( false )
563 { 788 {
564 nPos = hsh->getFirstPos( bFinished ); 789 nPos = hsh->core->getFirstPos( bFinished );
565 } 790 }
566 791
567 iterator( MyType *hsh, bool bDone ) : 792 iterator( MyType *hsh, bool bDone ) :
@@ -590,11 +815,6 @@ namespace Bu
590 { 815 {
591 } 816 }
592 817
593 DEPRECATED bool isActive() const
594 {
595 return !bFinished;
596 }
597
598 bool isValid() const 818 bool isValid() const
599 { 819 {
600 return !bFinished; 820 return !bFinished;
@@ -611,7 +831,7 @@ namespace Bu
611 iterator operator++( int ) 831 iterator operator++( int )
612 { 832 {
613 if( bFinished == false ) 833 if( bFinished == false )
614 nPos = hsh->getNextPos( nPos, bFinished ); 834 nPos = hsh->core->getNextPos( nPos, bFinished );
615 835
616 return *this; 836 return *this;
617 } 837 }
@@ -622,7 +842,7 @@ namespace Bu
622 iterator operator++() 842 iterator operator++()
623 { 843 {
624 if( bFinished == false ) 844 if( bFinished == false )
625 nPos = hsh->getNextPos( nPos, bFinished ); 845 nPos = hsh->core->getNextPos( nPos, bFinished );
626 846
627 return *this; 847 return *this;
628 } 848 }
@@ -671,21 +891,22 @@ namespace Bu
671 */ 891 */
672 value &operator *() 892 value &operator *()
673 { 893 {
674 return hsh->getValueAtPos( nPos ); 894 hsh->_hardCopy();
895 return hsh->core->getValueAtPos( nPos );
675 } 896 }
676 897
677 const value &operator *() const 898 const value &operator *() const
678 { 899 {
679 return hsh->getValueAtPos( nPos ); 900 return hsh->core->getValueAtPos( nPos );
680 } 901 }
681 902
682 /** 903 /**
683 * Get the key behind this iterator. 904 * Get the key behind this iterator.
684 *@returns (key_type &) The key behind this iterator. 905 *@returns (key_type &) The key behind this iterator.
685 */ 906 */
686 key &getKey() 907 const key &getKey() const
687 { 908 {
688 return hsh->getKeyAtPos( nPos ); 909 return hsh->core->getKeyAtPos( nPos );
689 } 910 }
690 911
691 /** 912 /**
@@ -694,7 +915,17 @@ namespace Bu
694 */ 915 */
695 value &getValue() 916 value &getValue()
696 { 917 {
697 return hsh->getValueAtPos( nPos ); 918 hsh->_hardCopy();
919 return hsh->core->getValueAtPos( nPos );
920 }
921
922 /**
923 * Get the value behind this iterator.
924 *@returns (value_type &) The value behind this iterator.
925 */
926 const value &getValue() const
927 {
928 return hsh->core->getValueAtPos( nPos );
698 } 929 }
699 } iterator; 930 } iterator;
700 931
@@ -710,7 +941,7 @@ namespace Bu
710 nPos( 0 ), 941 nPos( 0 ),
711 bFinished( false ) 942 bFinished( false )
712 { 943 {
713 nPos = hsh->getFirstPos( bFinished ); 944 nPos = hsh->core->getFirstPos( bFinished );
714 } 945 }
715 946
716 const_iterator( const MyType *hsh, bool bDone ) : 947 const_iterator( const MyType *hsh, bool bDone ) :
@@ -762,7 +993,7 @@ namespace Bu
762 const_iterator operator++( int ) 993 const_iterator operator++( int )
763 { 994 {
764 if( bFinished == false ) 995 if( bFinished == false )
765 nPos = hsh->getNextPos( nPos, bFinished ); 996 nPos = hsh->core->getNextPos( nPos, bFinished );
766 997
767 return *this; 998 return *this;
768 } 999 }
@@ -773,7 +1004,7 @@ namespace Bu
773 const_iterator operator++() 1004 const_iterator operator++()
774 { 1005 {
775 if( bFinished == false ) 1006 if( bFinished == false )
776 nPos = hsh->getNextPos( nPos, bFinished ); 1007 nPos = hsh->core->getNextPos( nPos, bFinished );
777 1008
778 return *this; 1009 return *this;
779 } 1010 }
@@ -822,7 +1053,7 @@ namespace Bu
822 */ 1053 */
823 const value &operator *() const 1054 const value &operator *() const
824 { 1055 {
825 return hsh->getValueAtPos( nPos ); 1056 return hsh->core->getValueAtPos( nPos );
826 } 1057 }
827 1058
828 /** 1059 /**
@@ -831,7 +1062,7 @@ namespace Bu
831 */ 1062 */
832 const key &getKey() const 1063 const key &getKey() const
833 { 1064 {
834 return hsh->getKeyAtPos( nPos ); 1065 return hsh->core->getKeyAtPos( nPos );
835 } 1066 }
836 1067
837 /** 1068 /**
@@ -840,7 +1071,7 @@ namespace Bu
840 */ 1071 */
841 const value &getValue() const 1072 const value &getValue() const
842 { 1073 {
843 return hsh->getValueAtPos( nPos ); 1074 return hsh->core->getValueAtPos( nPos );
844 } 1075 }
845 } const_iterator; 1076 } const_iterator;
846 1077
@@ -883,13 +1114,13 @@ namespace Bu
883 { 1114 {
884 Bu::List<key> lKeys; 1115 Bu::List<key> lKeys;
885 1116
886 for( uint32_t j = 0; j < nCapacity; j++ ) 1117 for( uint32_t j = 0; j < core->nCapacity; j++ )
887 { 1118 {
888 if( isFilled( j ) ) 1119 if( core->isFilled( j ) )
889 { 1120 {
890 if( !isDeleted( j ) ) 1121 if( !core->isDeleted( j ) )
891 { 1122 {
892 lKeys.append( aKeys[j] ); 1123 lKeys.append( core->aKeys[j] );
893 } 1124 }
894 } 1125 }
895 } 1126 }
@@ -901,13 +1132,13 @@ namespace Bu
901 { 1132 {
902 Bu::List<value> lValues; 1133 Bu::List<value> lValues;
903 1134
904 for( uint32_t j = 0; j < nCapacity; j++ ) 1135 for( uint32_t j = 0; j < core->nCapacity; j++ )
905 { 1136 {
906 if( isFilled( j ) ) 1137 if( core->isFilled( j ) )
907 { 1138 {
908 if( !isDeleted( j ) ) 1139 if( !core->isDeleted( j ) )
909 { 1140 {
910 lValues.append( aValues[j] ); 1141 lValues.append( core->aValues[j] );
911 } 1142 }
912 } 1143 }
913 } 1144 }
@@ -916,243 +1147,32 @@ namespace Bu
916 } 1147 }
917 1148
918 protected: 1149 protected:
919 virtual void onInsert() {} 1150 virtual Core *_copyCore( Core *src )
920 virtual void onUpdate() {}
921 virtual void onDelete() {}
922 virtual void onReHash() {}
923
924 virtual void clearBits()
925 {
926 for( uint32_t j = 0; j < nKeysSize; j++ )
927 {
928 bFilled[j] = bDeleted[j] = 0;
929 }
930 }
931
932 virtual void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
933 {
934 bFilled[loc/32] |= (1<<(loc%32));
935 va.construct( &aValues[loc], v );
936 ka.construct( &aKeys[loc], k );
937 aHashCodes[loc] = hash;
938 nFilled++;
939 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
940 // nFilled, nDeleted, nCapacity );
941 }
942
943 virtual void _erase( uint32_t loc )
944 {
945 bDeleted[loc/32] |= (1<<(loc%32));
946 va.destroy( &aValues[loc] );
947 ka.destroy( &aKeys[loc] );
948 nDeleted++;
949 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
950 // nFilled, nDeleted, nCapacity );
951 }
952
953 virtual key &getKeyAtPos( uint32_t nPos )
954 {
955 return aKeys[nPos];
956 }
957
958 virtual const key &getKeyAtPos( uint32_t nPos ) const
959 {
960 return aKeys[nPos];
961 }
962
963 virtual value &getValueAtPos( uint32_t nPos )
964 {
965 return aValues[nPos];
966 }
967
968 virtual const value &getValueAtPos( uint32_t nPos ) const
969 {
970 return aValues[nPos];
971 }
972
973 virtual uint32_t getFirstPos( bool &bFinished ) const
974 {
975 for( uint32_t j = 0; j < nCapacity; j++ )
976 {
977 if( isFilled( j ) )
978 if( !isDeleted( j ) )
979 return j;
980 }
981
982 bFinished = true;
983 return 0;
984 }
985
986 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
987 {
988 for( uint32_t j = nPos+1; j < nCapacity; j++ )
989 {
990 if( isFilled( j ) )
991 if( !isDeleted( j ) )
992 return j;
993 }
994
995 bFinished = true;
996 return 0;
997 }
998
999 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
1000 {
1001 uint32_t nCur = hash%nCapacity;
1002
1003 // First we scan to see if the key is already there, abort if we
1004 // run out of probing room, or we find a non-filled entry
1005 int8_t j;
1006 for( j = 0;
1007 isFilled( nCur ) && j < 32;
1008 nCur = (nCur + (1<<j))%nCapacity, j++
1009 )
1010 {
1011 // Is this the same hash code we were looking for?
1012 if( hash == aHashCodes[nCur] )
1013 {
1014 // Skip over deleted entries. Deleted entries are also filled,
1015 // so we only have to do this check here.
1016 if( isDeleted( nCur ) )
1017 continue;
1018
1019 // Is it really the same key? (for safety)
1020 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1021 {
1022 bFill = true;
1023 return nCur;
1024 }
1025 }
1026 }
1027
1028 // This is our insurance, if the table is full, then go ahead and
1029 // rehash, then try again.
1030 if( (isFilled( nCur ) || j == 32) && rehash == true )
1031 {
1032 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
1033
1034 // This is potentially dangerous, and could cause an infinite loop.
1035 // Be careful writing probe, eh?
1036 return probe( hash, k, bFill );
1037 }
1038
1039 bFill = false;
1040 return nCur;
1041 }
1042
1043 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
1044 {
1045 uint32_t nCur = hash%nCapacity;
1046
1047 // First we scan to see if the key is already there, abort if we
1048 // run out of probing room, or we find a non-filled entry
1049 for( int8_t j = 0;
1050 isFilled( nCur ) && j < 32;
1051 nCur = (nCur + (1<<j))%nCapacity, j++
1052 )
1053 {
1054 // Is this the same hash code we were looking for?
1055 if( hash == aHashCodes[nCur] )
1056 {
1057 // Skip over deleted entries. Deleted entries are also filled,
1058 // so we only have to do this check here.
1059 if( isDeleted( nCur ) )
1060 continue;
1061
1062 // Is it really the same key? (for safety)
1063 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1064 {
1065 bFill = true;
1066 return nCur;
1067 }
1068 }
1069 }
1070
1071 bFill = false;
1072 return nCur;
1073 }
1074
1075 void reHash( uint32_t nNewSize )
1076 { 1151 {
1077 //printf("---REHASH---"); 1152 Core *pRet = _allocateCore();
1078 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
1079 // nFilled, nDeleted, nCapacity );
1080
1081 // Save all the old data
1082 uint32_t nOldCapacity = nCapacity;
1083 uint32_t *bOldFilled = bFilled;
1084 uint32_t *aOldHashCodes = aHashCodes;
1085 uint32_t nOldKeysSize = nKeysSize;
1086 uint32_t *bOldDeleted = bDeleted;
1087 value *aOldValues = aValues;
1088 key *aOldKeys = aKeys;
1089
1090 // Calculate new sizes
1091 nCapacity = nNewSize;
1092 nKeysSize = bitsToBytes( nCapacity );
1093
1094 // Allocate new memory + prep
1095 bFilled = ca.allocate( nKeysSize );
1096 bDeleted = ca.allocate( nKeysSize );
1097 clearBits();
1098 1153
1099 aHashCodes = ca.allocate( nCapacity ); 1154 pRet->nFilled = 0;
1100 aKeys = ka.allocate( nCapacity ); 1155 pRet->nDeleted = 0;
1101 aValues = va.allocate( nCapacity ); 1156 pRet->nCapacity = src->nCapacity;
1157 pRet->nKeysSize = bitsToBytes( pRet->nCapacity );
1158 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize );
1159 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize );
1160 pRet->clearBits();
1102 1161
1103 nDeleted = nFilled = 0; 1162 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity );
1163 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity );
1164 pRet->aValues = pRet->va.allocate( pRet->nCapacity );
1104 1165
1105 // Re-insert all of the old data (except deleted items) 1166 for( uint32_t j = 0; j < src->nCapacity; j++ )
1106 for( uint32_t j = 0; j < nOldCapacity; j++ )
1107 { 1167 {
1108 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 1168 if( src->isFilled( j ) && !src->isDeleted( j ) )
1109 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1110 { 1169 {
1111 insert( aOldKeys[j], aOldValues[j] ); 1170 pRet->insert( src->aKeys[j], src->aValues[j] );
1112 } 1171 }
1113 } 1172 }
1114 1173
1115 // Delete all of the old data 1174 return pRet;
1116 for( uint32_t j = 0; j < nOldCapacity; j++ )
1117 {
1118 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
1119 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1120 {
1121 va.destroy( &aOldValues[j] );
1122 ka.destroy( &aOldKeys[j] );
1123 }
1124 }
1125 va.deallocate( aOldValues, nOldCapacity );
1126 ka.deallocate( aOldKeys, nOldCapacity );
1127 ca.deallocate( bOldFilled, nOldKeysSize );
1128 ca.deallocate( bOldDeleted, nOldKeysSize );
1129 ca.deallocate( aOldHashCodes, nOldCapacity );
1130 }
1131
1132 virtual bool isFilled( uint32_t loc ) const
1133 {
1134 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
1135 }
1136
1137 virtual bool isDeleted( uint32_t loc ) const
1138 {
1139 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
1140 } 1175 }
1141
1142 protected:
1143 uint32_t nCapacity;
1144 uint32_t nFilled;
1145 uint32_t nDeleted;
1146 uint32_t *bFilled;
1147 uint32_t *bDeleted;
1148 uint32_t nKeysSize;
1149 key *aKeys;
1150 value *aValues;
1151 uint32_t *aHashCodes;
1152 valuealloc va;
1153 keyalloc ka;
1154 challoc ca;
1155 sizecalc szCalc;
1156 }; 1176 };
1157 1177
1158 template<typename T> uint32_t __calcHashCode( const T &k ) 1178 template<typename T> uint32_t __calcHashCode( const T &k )
diff --git a/src/heap.h b/src/heap.h
index 9df4121..1dac69b 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -13,76 +13,92 @@
13#include "bu/exceptionbase.h" 13#include "bu/exceptionbase.h"
14#include "bu/util.h" 14#include "bu/util.h"
15#include "bu/queue.h" 15#include "bu/queue.h"
16#include "bu/sharedcore.h"
16 17
17namespace Bu 18namespace Bu
18{ 19{
19 subExceptionDecl( HeapException ); 20 subExceptionDecl( HeapException );
20 21
21 /** 22 template<typename item, typename cmpfunc, typename itemalloc>
22 * A priority queue that allows for an unlimited number of priorities. All 23 class Heap;
23 * objects enqueued must support less-than-comparison. Then every time an 24
24 * item is dequeued it is always the least item in the heap. The heap 25 template<typename item, typename cmpfunc, typename itemalloc>
25 * operates using a binary tree for storage, which allows most operations 26 class HeapCore
26 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
27 * whereas peeking is constant time.
28 *
29 * This heap implementation allows iterating, however please note that any
30 * enqueue or dequeue operation will invalidate the iterator and make it
31 * unusable (if it still works, you shouldn't trust the results). Also,
32 * the items are not stored in memory in order, they are optomized into a
33 * tree. This means that the items will be in effectively random order
34 * while iterating through them, and the order cannot be trusted. Also,
35 * modifying an item in the heap will not cause that item to be re-sorted.
36 * If you want to change the position of an item in the heap you will have
37 * to dequeue every item before it, dequeue that item, change it, and
38 * re-enqueue all of the items removed.
39 */
40 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
41 class Heap : public Queue<item>
42 { 27 {
43 public: 28 friend class Heap<item, cmpfunc, itemalloc>;
44 Heap() : 29 friend class SharedCore<
45 iSize( 7 ), 30 Heap<item, cmpfunc, itemalloc>, HeapCore<item, cmpfunc, itemalloc>
31 >;
32 private:
33 HeapCore() :
34 iSize( 0 ),
46 iFill( 0 ), 35 iFill( 0 ),
47 aItem( ia.allocate( iSize ) ) 36 aItem( NULL )
48 { 37 {
49 } 38 }
50 39
51 Heap( cmpfunc cmpin ) : 40 virtual ~HeapCore()
52 iSize( 7 ),
53 iFill( 0 ),
54 aItem( ia.allocate( iSize ) ),
55 cmp( cmpin )
56 { 41 {
42 clear();
57 } 43 }
58 44
59 Heap( int iInitialCapacity ) : 45 void init()
60 iSize( 0 ),
61 iFill( 0 ),
62 aItem( NULL )
63 { 46 {
64 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } 47 if( iSize > 0 )
48 return;
49
50 iSize = 7;
51 iFill = 0;
65 aItem = ia.allocate( iSize ); 52 aItem = ia.allocate( iSize );
66 } 53 }
67 54
68 Heap( cmpfunc cmpin, int iInitialCapacity ) : 55 void init( int iCap )
69 iSize( 0 ),
70 iFill( 0 ),
71 aItem( NULL ),
72 cmp( cmpin )
73 { 56 {
74 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } 57 if( iSize > 0 )
58 return;
59
60 for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { }
61 iFill = 0;
75 aItem = ia.allocate( iSize ); 62 aItem = ia.allocate( iSize );
76 } 63 }
77 64
78 virtual ~Heap() 65 void clear()
79 { 66 {
67 if( iSize == 0 )
68 return;
69
80 for( int j = 0; j < iFill; j++ ) 70 for( int j = 0; j < iFill; j++ )
81 ia.destroy( &aItem[j] ); 71 ia.destroy( &aItem[j] );
82 ia.deallocate( aItem, iSize ); 72 ia.deallocate( aItem, iSize );
83 aItem = NULL; 73 aItem = NULL;
74 iSize = 0;
75 iFill = 0;
84 } 76 }
77
78 void upSize()
79 {
80 if( iSize == 0 )
81 {
82 init();
83 return;
84 }
85 85
86 item *aNewItems = ia.allocate( iSize*2+1 );
87 //
88 // We cannot use a memcopy here because we don't know what kind
89 // of datastructures are being used, we have to copy them one at
90 // a time.
91 //
92 for( int j = 0; j < iFill; j++ )
93 {
94 ia.construct( &aNewItems[j], aItem[j] );
95 ia.destroy( &aItem[j] );
96 }
97 ia.deallocate( aItem, iSize );
98 aItem = aNewItems;
99 iSize = iSize*2+1;
100 }
101
86 virtual void enqueue( const item &it ) 102 virtual void enqueue( const item &it )
87 { 103 {
88 item i = it; // TODO: This is a silly workaround, put the i item 104 item i = it; // TODO: This is a silly workaround, put the i item
@@ -126,20 +142,6 @@ namespace Bu
126 iFill++; 142 iFill++;
127 } 143 }
128 144
129 virtual item &peek()
130 {
131 if( iFill == 0 )
132 throw HeapException("Heap empty.");
133 return aItem[0];
134 }
135
136 virtual const item &peek() const
137 {
138 if( iFill == 0 )
139 throw HeapException("Heap empty.");
140 return aItem[0];
141 }
142
143 virtual item dequeue() 145 virtual item dequeue()
144 { 146 {
145 if( iFill == 0 ) 147 if( iFill == 0 )
@@ -174,14 +176,117 @@ namespace Bu
174 return iRet; 176 return iRet;
175 } 177 }
176 178
179 private:
180 int iSize;
181 int iFill;
182 item *aItem;
183 cmpfunc cmp;
184 itemalloc ia;
185 };
186
187 /**
188 * A priority queue that allows for an unlimited number of priorities. All
189 * objects enqueued must support less-than-comparison. Then every time an
190 * item is dequeued it is always the least item in the heap. The heap
191 * operates using a binary tree for storage, which allows most operations
192 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
193 * whereas peeking is constant time.
194 *
195 * This heap implementation allows iterating, however please note that any
196 * enqueue or dequeue operation will invalidate the iterator and make it
197 * unusable (if it still works, you shouldn't trust the results). Also,
198 * the items are not stored in memory in order, they are optomized into a
199 * tree. This means that the items will be in effectively random order
200 * while iterating through them, and the order cannot be trusted. Also,
201 * modifying an item in the heap will not cause that item to be re-sorted.
202 * If you want to change the position of an item in the heap you will have
203 * to dequeue every item before it, dequeue that item, change it, and
204 * re-enqueue all of the items removed.
205 */
206 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
207 class Heap : public Queue<item>, public SharedCore<
208 Heap<item, cmpfunc, itemalloc>,
209 HeapCore<item, cmpfunc, itemalloc>
210 >
211 {
212 private:
213 typedef class Heap<item,cmpfunc,itemalloc> MyType;
214 typedef class HeapCore<item,cmpfunc,itemalloc> Core;
215
216 protected:
217 using SharedCore<MyType, Core>::core;
218 using SharedCore<MyType, Core>::_hardCopy;
219 using SharedCore<MyType, Core>::_resetCore;
220 using SharedCore<MyType, Core>::_allocateCore;
221
222 public:
223 Heap()
224 {
225 }
226
227 Heap( cmpfunc cmpin )
228 {
229 core->cmp = cmpin;
230 }
231
232 Heap( int iInitialCapacity )
233 {
234 core->init( iInitialCapacity );
235 }
236
237 Heap( cmpfunc cmpin, int iInitialCapacity )
238 {
239 core->cmp = cmpin;
240 core->init( iInitialCapacity );
241 }
242
243 Heap( const MyType &rSrc ) :
244 SharedCore<MyType, Core>( rSrc )
245 {
246 }
247
248 virtual ~Heap()
249 {
250 }
251
252 virtual void enqueue( const item &it )
253 {
254 _hardCopy();
255
256 core->enqueue( it );
257 }
258
259 virtual item &peek()
260 {
261 _hardCopy();
262
263 if( core->iFill == 0 )
264 throw HeapException("Heap empty.");
265 return core->aItem[0];
266 }
267
268 virtual const item &peek() const
269 {
270 if( core->iFill == 0 )
271 throw HeapException("Heap empty.");
272 return core->aItem[0];
273 }
274
275 virtual item dequeue()
276 {
277 _hardCopy();
278
279 return core->dequeue();
280 }
281
177 virtual bool isEmpty() const 282 virtual bool isEmpty() const
178 { 283 {
179 return (iFill==0); 284 return (core->iFill==0);
180 } 285 }
181 286
182 virtual int getSize() const 287 virtual int getSize() const
183 { 288 {
184 return iFill; 289 return core->iFill;
185 } 290 }
186 291
187 class iterator 292 class iterator
@@ -201,7 +306,7 @@ namespace Bu
201 { 306 {
202 if( pHeap == NULL ) 307 if( pHeap == NULL )
203 throw Bu::ExceptionBase("Iterator not initialized."); 308 throw Bu::ExceptionBase("Iterator not initialized.");
204 if( iIndex < 0 || iIndex >= pHeap->iFill ) 309 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
205 throw Bu::ExceptionBase("Iterator out of bounds."); 310 throw Bu::ExceptionBase("Iterator out of bounds.");
206 } 311 }
207 312
@@ -230,12 +335,16 @@ namespace Bu
230 335
231 item &operator*() 336 item &operator*()
232 { 337 {
233 return pHeap->aItem[iIndex]; 338 pHeap->_hardCopy();
339
340 return pHeap->core->aItem[iIndex];
234 } 341 }
235 342
236 item *operator->() 343 item *operator->()
237 { 344 {
238 return &(pHeap->aItem[iIndex]); 345 pHeap->_hardCopy();
346
347 return &(pHeap->core->aItem[iIndex]);
239 } 348 }
240 349
241 iterator &operator++() 350 iterator &operator++()
@@ -260,7 +369,7 @@ namespace Bu
260 { 369 {
261 checkValid(); 370 checkValid();
262 iIndex++; 371 iIndex++;
263 if( iIndex >= pHeap->iFill ) 372 if( iIndex >= pHeap->core->iFill )
264 iIndex = -1; 373 iIndex = -1;
265 374
266 return *this; 375 return *this;
@@ -279,7 +388,7 @@ namespace Bu
279 checkValid(); 388 checkValid();
280 iterator ret( *this ); 389 iterator ret( *this );
281 ret.iIndex += iDelta; 390 ret.iIndex += iDelta;
282 if( ret.iIndex >= pHeap->iFill ) 391 if( ret.iIndex >= pHeap->core->iFill )
283 ret.iIndex = -1; 392 ret.iIndex = -1;
284 return ret; 393 return ret;
285 } 394 }
@@ -294,12 +403,12 @@ namespace Bu
294 return ret; 403 return ret;
295 } 404 }
296 405
297 operator bool() 406 operator bool() const
298 { 407 {
299 return iIndex != -1; 408 return iIndex != -1;
300 } 409 }
301 410
302 bool isValid() 411 bool isValid() const
303 { 412 {
304 return iIndex != -1; 413 return iIndex != -1;
305 } 414 }
@@ -328,7 +437,7 @@ namespace Bu
328 { 437 {
329 if( pHeap == NULL ) 438 if( pHeap == NULL )
330 throw Bu::ExceptionBase("Iterator not initialized."); 439 throw Bu::ExceptionBase("Iterator not initialized.");
331 if( iIndex < 0 || iIndex >= pHeap->iFill ) 440 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
332 throw Bu::ExceptionBase("Iterator out of bounds."); 441 throw Bu::ExceptionBase("Iterator out of bounds.");
333 } 442 }
334 443
@@ -363,19 +472,23 @@ namespace Bu
363 472
364 const item &operator*() 473 const item &operator*()
365 { 474 {
366 return pHeap->aItem[iIndex]; 475 pHeap->_hardCopy();
476
477 return pHeap->core->aItem[iIndex];
367 } 478 }
368 479
369 const item *operator->() 480 const item *operator->()
370 { 481 {
371 return &(pHeap->aItem[iIndex]); 482 pHeap->_hardCopy();
483
484 return &(pHeap->core->aItem[iIndex]);
372 } 485 }
373 486
374 const_iterator &operator++() 487 const_iterator &operator++()
375 { 488 {
376 checkValid(); 489 checkValid();
377 iIndex++; 490 iIndex++;
378 if( iIndex >= pHeap->iFill ) 491 if( iIndex >= pHeap->core->iFill )
379 iIndex = -1; 492 iIndex = -1;
380 493
381 return *this; 494 return *this;
@@ -393,7 +506,7 @@ namespace Bu
393 { 506 {
394 checkValid(); 507 checkValid();
395 iIndex++; 508 iIndex++;
396 if( iIndex >= pHeap->iFill ) 509 if( iIndex >= pHeap->core->iFill )
397 iIndex = -1; 510 iIndex = -1;
398 511
399 return *this; 512 return *this;
@@ -427,12 +540,12 @@ namespace Bu
427 return ret; 540 return ret;
428 } 541 }
429 542
430 operator bool() 543 operator bool() const
431 { 544 {
432 return iIndex != -1; 545 return iIndex != -1;
433 } 546 }
434 547
435 bool isValid() 548 bool isValid() const
436 { 549 {
437 return iIndex != -1; 550 return iIndex != -1;
438 } 551 }
@@ -452,14 +565,14 @@ namespace Bu
452 565
453 iterator begin() 566 iterator begin()
454 { 567 {
455 if( iFill == 0 ) 568 if( core->iFill == 0 )
456 return end(); 569 return end();
457 return iterator( this, 0 ); 570 return iterator( this, 0 );
458 } 571 }
459 572
460 const_iterator begin() const 573 const_iterator begin() const
461 { 574 {
462 if( iFill == 0 ) 575 if( core->iFill == 0 )
463 return end(); 576 return end();
464 return const_iterator( this, 0 ); 577 return const_iterator( this, 0 );
465 } 578 }
@@ -475,31 +588,22 @@ namespace Bu
475 } 588 }
476 589
477 590
478 private: 591 protected:
479 void upSize() 592 virtual Core *_copyCore( Core *src )
480 { 593 {
481 item *aNewItems = ia.allocate( iSize*2+1 ); 594 Core *pRet = _allocateCore();
482 // 595
483 // We cannot use a memcopy here because we don't know what kind 596 pRet->iSize = src->iSize;
484 // of datastructures are being used, we have to copy them one at 597 pRet->iFill = src->iFill;
485 // a time. 598 pRet->cmp = src->cmp;
486 // 599 pRet->aItem = pRet->ia.allocate( pRet->iSize );
487 for( int j = 0; j < iFill; j++ ) 600 for( int j = 0; j < pRet->iFill; j++ )
488 { 601 {
489 ia.construct( &aNewItems[j], aItem[j] ); 602 pRet->ia.construct( &pRet->aItem[j], src->aItem[j] );
490 ia.destroy( &aItem[j] );
491 } 603 }
492 ia.deallocate( aItem, iSize );
493 aItem = aNewItems;
494 iSize = iSize*2+1;
495 }
496 604
497 private: 605 return pRet;
498 int iSize; 606 }
499 int iFill;
500 item *aItem;
501 cmpfunc cmp;
502 itemalloc ia;
503 }; 607 };
504}; 608};
505 609
diff --git a/src/list.h b/src/list.h
index 9b95983..ba1d2c4 100644
--- a/src/list.h
+++ b/src/list.h
@@ -24,10 +24,18 @@ namespace Bu
24 ListLink *pPrev; 24 ListLink *pPrev;
25 }; 25 };
26 26
27 template<typename value, typename valuealloc, 27 template<typename value, typename valuealloc, typename linkalloc>
28 typename linkalloc> 28 class List;
29
30 template<typename value, typename valuealloc, typename linkalloc>
29 struct ListCore 31 struct ListCore
30 { 32 {
33 friend class List<value, valuealloc, linkalloc>;
34 friend class SharedCore<
35 List<value, valuealloc, linkalloc>,
36 ListCore<value, valuealloc, linkalloc>
37 >;
38 private:
31 typedef struct ListLink<value> Link; 39 typedef struct ListLink<value> Link;
32 ListCore() : 40 ListCore() :
33 pFirst( NULL ), 41 pFirst( NULL ),
@@ -193,8 +201,10 @@ namespace Bu
193 */ 201 */
194 template<typename value, typename valuealloc=std::allocator<value>, 202 template<typename value, typename valuealloc=std::allocator<value>,
195 typename linkalloc=std::allocator<struct ListLink<value> > > 203 typename linkalloc=std::allocator<struct ListLink<value> > >
196 class List : public SharedCore< struct ListCore<value, valuealloc, 204 class List : public SharedCore<
197 linkalloc> > 205 List<value, valuealloc, linkalloc>,
206 ListCore<value, valuealloc, linkalloc>
207 >
198 { 208 {
199 private: 209 private:
200 typedef struct ListLink<value> Link; 210 typedef struct ListLink<value> Link;
@@ -202,9 +212,9 @@ namespace Bu
202 typedef struct ListCore<value, valuealloc, linkalloc> Core; 212 typedef struct ListCore<value, valuealloc, linkalloc> Core;
203 213
204 protected: 214 protected:
205 using SharedCore< Core >::core; 215 using SharedCore<MyType, Core>::core;
206 using SharedCore< Core >::_hardCopy; 216 using SharedCore<MyType, Core>::_hardCopy;
207 using SharedCore< Core >::_allocateCore; 217 using SharedCore<MyType, Core>::_allocateCore;
208 218
209 public: 219 public:
210 struct const_iterator; 220 struct const_iterator;
@@ -215,7 +225,7 @@ namespace Bu
215 } 225 }
216 226
217 List( const MyType &src ) : 227 List( const MyType &src ) :
218 SharedCore< Core >( src ) 228 SharedCore<MyType, Core >( src )
219 { 229 {
220 } 230 }
221 231
diff --git a/src/set.h b/src/set.h
index 6a2abce..047ff7f 100644
--- a/src/set.h
+++ b/src/set.h
@@ -24,17 +24,10 @@ namespace Bu
24{ 24{
25 subExceptionDecl( SetException ) 25 subExceptionDecl( SetException )
26 26
27 template<typename T>
28 uint32_t __calcHashCode( const T &k );
29
30 template<typename T>
31 bool __cmpHashKeys( const T &a, const T &b );
32
33 template<typename key, typename sizecalc = struct __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename challoc = std::allocator<uint32_t> >
34 class Set;
35
36 /** 27 /**
37 * Libbu Template Set 28 *@todo Set should be rewritten, possibly using a b-tree as ordered storage
29 * in the backend. It should use either a b-tree or array for storage and
30 * allow set intersections, unions, etc.
38 *@param key (typename) The datatype of the hashtable keys 31 *@param key (typename) The datatype of the hashtable keys
39 *@param sizecalc (typename) Functor to compute new table size on rehash 32 *@param sizecalc (typename) Functor to compute new table size on rehash
40 *@param keyalloc (typename) Memory allocator for hashtable keys 33 *@param keyalloc (typename) Memory allocator for hashtable keys
@@ -45,754 +38,7 @@ namespace Bu
45 class Set 38 class Set
46 { 39 {
47 public: 40 public:
48 Set() :
49 nCapacity( 11 ),
50 nFilled( 0 ),
51 nDeleted( 0 ),
52 bFilled( NULL ),
53 bDeleted( NULL ),
54 aKeys( NULL ),
55 aHashCodes( NULL )
56 {
57 nKeysSize = bitsToBytes( nCapacity );
58 bFilled = ca.allocate( nKeysSize );
59 bDeleted = ca.allocate( nKeysSize );
60 clearBits();
61
62 aHashCodes = ca.allocate( nCapacity );
63 aKeys = ka.allocate( nCapacity );
64 }
65
66 Set( const Set &src ) :
67 nCapacity( src.nCapacity ),
68 nFilled( 0 ),
69 nDeleted( 0 ),
70 bFilled( NULL ),
71 bDeleted( NULL ),
72 aKeys( NULL ),
73 aHashCodes( NULL )
74 {
75 nKeysSize = bitsToBytes( nCapacity );
76 bFilled = ca.allocate( nKeysSize );
77 bDeleted = ca.allocate( nKeysSize );
78 clearBits();
79
80 aHashCodes = ca.allocate( nCapacity );
81 aKeys = ka.allocate( nCapacity );
82
83 for( uint32_t j = 0; j < src.nCapacity; j++ )
84 {
85 if( src.isFilled( j ) )
86 {
87 insert( src.aKeys[j] );
88 }
89 }
90 }
91
92 /**
93 * Set assignment operator. Clears this hashtable and
94 * copies RH into it.
95 */
96 Set &operator=( const Set &src )
97 {
98 for( uint32_t j = 0; j < nCapacity; j++ )
99 {
100 if( isFilled( j ) )
101 if( !isDeleted( j ) )
102 {
103 ka.destroy( &aKeys[j] );
104 }
105 }
106 ka.deallocate( aKeys, nCapacity );
107 ca.deallocate( bFilled, nKeysSize );
108 ca.deallocate( bDeleted, nKeysSize );
109 ca.deallocate( aHashCodes, nCapacity );
110
111 nFilled = 0;
112 nDeleted = 0;
113 nCapacity = src.nCapacity;
114 nKeysSize = bitsToBytes( nCapacity );
115 bFilled = ca.allocate( nKeysSize );
116 bDeleted = ca.allocate( nKeysSize );
117 clearBits();
118
119 aHashCodes = ca.allocate( nCapacity );
120 aKeys = ka.allocate( nCapacity );
121
122 for( uint32_t j = 0; j < src.nCapacity; j++ )
123 {
124 if( src.isFilled( j ) )
125 {
126 insert( src.aKeys[j] );
127 }
128 }
129
130 return *this;
131 }
132
133 virtual ~Set()
134 {
135 for( uint32_t j = 0; j < nCapacity; j++ )
136 {
137 if( isFilled( j ) )
138 if( !isDeleted( j ) )
139 {
140 ka.destroy( &aKeys[j] );
141 }
142 }
143 ka.deallocate( aKeys, nCapacity );
144 ca.deallocate( bFilled, nKeysSize );
145 ca.deallocate( bDeleted, nKeysSize );
146 ca.deallocate( aHashCodes, nCapacity );
147 }
148
149 /**
150 * Get the current hash table capacity. (Changes at re-hash)
151 *@returns (uint32_t) The current capacity.
152 */
153 uint32_t getCapacity()
154 {
155 return nCapacity;
156 }
157
158 /**
159 * Get the number of hash locations spoken for. (Including
160 * not-yet-cleaned-up deleted items.)
161 *@returns (uint32_t) The current fill state.
162 */
163 uint32_t getFill()
164 {
165 return nFilled;
166 }
167
168 /**
169 * Get the number of items stored in the hash table.
170 *@returns (uint32_t) The number of items stored in the hash table.
171 */
172 uint32_t getSize()
173 {
174 return nFilled-nDeleted;
175 }
176
177 /**
178 * Get the number of items which have been deleted, but not yet
179 * cleaned up.
180 *@returns (uint32_t) The number of deleted items.
181 */
182 uint32_t getDeleted()
183 {
184 return nDeleted;
185 }
186
187 /**
188 * Insert key (k) into the set
189 *@param k (key_type) Key to list the value under.
190 */
191 virtual void insert( key k )
192 {
193 uint32_t hash = __calcHashCode( k );
194 bool bFill;
195 uint32_t nPos = probe( hash, k, bFill );
196
197 if( bFill )
198 {
199 onUpdate();
200 }
201 else
202 {
203 fill( nPos, k, hash );
204 onInsert();
205 }
206 }
207
208 /**
209 * Remove a value from the hash table.
210 *@param k (key_type) The data under this key will be erased.
211 */
212 virtual void erase( key k )
213 {
214 uint32_t hash = __calcHashCode( k );
215 bool bFill;
216 uint32_t nPos = probe( hash, k, bFill );
217
218 if( bFill )
219 {
220 _erase( nPos );
221 onDelete();
222 }
223 }
224
225 struct iterator;
226
227 /**
228 * Remove a value from the hash pointed to from an iterator.
229 *@param i (iterator &) The data to be erased.
230 */
231 virtual void erase( struct iterator &i )
232 {
233 if( this != &i.hsh )
234 throw SetException("This iterator didn't come from this Hash.");
235 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
236 {
237 _erase( i.nPos );
238 onDelete();
239 }
240 }
241
242 /**
243 * Remove all data from the hash table.
244 */
245 virtual void clear()
246 {
247 for( uint32_t j = 0; j < nCapacity; j++ )
248 {
249 if( isFilled( j ) )
250 if( !isDeleted( j ) )
251 {
252 _erase( j );
253 onDelete();
254 }
255 }
256
257 clearBits();
258 }
259
260 /**
261 * Does the hash table contain an item under key (k).
262 *@param k (key_type) The key to check.
263 *@returns (bool) Whether there was an item in the hash under key (k).
264 */
265 virtual bool has( key k )
266 {
267 bool bFill;
268 probe( __calcHashCode( k ), k, bFill, false );
269
270 return bFill;
271 }
272
273 /**
274 * Iteration structure for iterating through the hash.
275 */
276 typedef struct iterator
277 {
278 friend class Set<key, sizecalc, keyalloc, challoc>;
279 private:
280 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh ) :
281 hsh( hsh ),
282 nPos( 0 ),
283 bFinished( false )
284 {
285 nPos = hsh.getFirstPos( bFinished );
286 }
287
288 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
289 hsh( hsh ),
290 nPos( 0 ),
291 bFinished( bDone )
292 {
293 }
294
295 Set<key, sizecalc, keyalloc, challoc> &hsh;
296 uint32_t nPos;
297 bool bFinished;
298
299 public:
300 /**
301 * Iterator incrementation operator. Move the iterator forward.
302 */
303 iterator operator++( int )
304 {
305 if( bFinished == false )
306 nPos = hsh.getNextPos( nPos, bFinished );
307
308 return *this;
309 }
310
311 /**
312 * Iterator incrementation operator. Move the iterator forward.
313 */
314 iterator operator++()
315 {
316 if( bFinished == false )
317 nPos = hsh.getNextPos( nPos, bFinished );
318
319 return *this;
320 }
321
322 /**
323 * Iterator equality comparison operator. Iterators the same?
324 */
325 bool operator==( const iterator &oth ) const
326 {
327 if( bFinished != oth.bFinished )
328 return false;
329 if( bFinished == true )
330 {
331 return true;
332 }
333 else
334 {
335 if( oth.nPos == nPos )
336 return true;
337 return false;
338 }
339 }
340
341 /**
342 * Iterator not equality comparison operator. Not the same?
343 */
344 bool operator!=( const iterator &oth ) const
345 {
346 return !(*this == oth );
347 }
348
349 /**
350 * Iterator assignment operator.
351 */
352 iterator operator=( const iterator &oth )
353 {
354 if( &hsh != &oth.hsh )
355 throw SetException(
356 "Cannot mix iterators from different set objects.");
357 nPos = oth.nPos;
358 bFinished = oth.bFinished;
359 }
360
361 /**
362 * Iterator dereference operator... err.. get the value
363 *@returns (value_type &) The value behind this iterator.
364 */
365 key &operator *()
366 {
367 return hsh.getKeyAtPos( nPos );
368 }
369
370 const key &operator *() const
371 {
372 return hsh.getKeyAtPos( nPos );
373 }
374
375 bool isValid() const
376 {
377 return !bFinished;
378 }
379
380 operator bool() const
381 {
382 return !bFinished;
383 }
384 } iterator;
385
386 /**
387 * Iteration structure for iterating through the set (const).
388 */
389 typedef struct const_iterator
390 {
391 friend class Set<key, sizecalc, keyalloc, challoc>;
392 private:
393 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh ) :
394 hsh( hsh ),
395 nPos( 0 ),
396 bFinished( false )
397 {
398 nPos = hsh.getFirstPos( bFinished );
399 }
400
401 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
402 hsh( hsh ),
403 nPos( 0 ),
404 bFinished( bDone )
405 {
406 }
407
408 const Set<key, sizecalc, keyalloc, challoc> &hsh;
409 uint32_t nPos;
410 bool bFinished;
411
412 public:
413 /**
414 * Iterator incrementation operator. Move the iterator forward.
415 */
416 const_iterator operator++( int )
417 {
418 if( bFinished == false )
419 nPos = hsh.getNextPos( nPos, bFinished );
420
421 return *this;
422 }
423
424 /**
425 * Iterator incrementation operator. Move the iterator forward.
426 */
427 const_iterator operator++()
428 {
429 if( bFinished == false )
430 nPos = hsh.getNextPos( nPos, bFinished );
431
432 return *this;
433 }
434
435 /**
436 * Iterator equality comparison operator. Iterators the same?
437 */
438 bool operator==( const const_iterator &oth ) const
439 {
440 if( bFinished != oth.bFinished )
441 return false;
442 if( bFinished == true )
443 {
444 return true;
445 }
446 else
447 {
448 if( oth.nPos == nPos )
449 return true;
450 return false;
451 }
452 }
453
454 /**
455 * Iterator not equality comparison operator. Not the same?
456 */
457 bool operator!=( const const_iterator &oth ) const
458 {
459 return !(*this == oth );
460 }
461
462 /**
463 * Iterator assignment operator.
464 */
465 const_iterator operator=( const const_iterator &oth )
466 {
467 if( &hsh != &oth.hsh )
468 throw SetException(
469 "Cannot mix iterators from different hash objects.");
470 nPos = oth.nPos;
471 bFinished = oth.bFinished;
472 }
473
474 /**
475 * Iterator dereference operator... err.. get the value
476 *@returns (value_type &) The value behind this iterator.
477 */
478 const key &operator *() const
479 {
480 return hsh.getKeyAtPos( nPos );
481 }
482
483 bool isValid() const
484 {
485 return !bFinished;
486 }
487
488 operator bool() const
489 {
490 return !bFinished;
491 }
492 } const_iterator;
493
494 /**
495 * Get an iterator pointing to the first item in the hash table.
496 *@returns (iterator) An iterator pointing to the first item in the
497 * hash table.
498 */
499 iterator begin()
500 {
501 return iterator( *this );
502 }
503
504 const_iterator begin() const
505 {
506 return const_iterator( *this );
507 }
508
509 /**
510 * Get an iterator pointing to a point just past the last item in the
511 * hash table.
512 *@returns (iterator) An iterator pointing to a point just past the
513 * last item in the hash table.
514 */
515 iterator end()
516 {
517 return iterator( *this, true );
518 }
519
520 const_iterator end() const
521 {
522 return const_iterator( *this, true );
523 }
524
525 /**
526 * Get a list of all the keys in the hash table.
527 *@returns (std::list<key_type>) The list of keys in the hash table.
528 */
529 Bu::List<key> getKeys() const
530 {
531 Bu::List<key> lKeys;
532
533 for( uint32_t j = 0; j < nCapacity; j++ )
534 {
535 if( isFilled( j ) )
536 {
537 if( !isDeleted( j ) )
538 {
539 lKeys.append( aKeys[j] );
540 }
541 }
542 }
543
544 return lKeys;
545 }
546
547 protected:
548 virtual void onInsert() {}
549 virtual void onUpdate() {}
550 virtual void onDelete() {}
551 virtual void onReHash() {}
552
553 virtual void clearBits()
554 {
555 for( uint32_t j = 0; j < nKeysSize; j++ )
556 {
557 bFilled[j] = bDeleted[j] = 0;
558 }
559 }
560
561 virtual void fill( uint32_t loc, key &k, uint32_t hash )
562 {
563 bFilled[loc/32] |= (1<<(loc%32));
564 ka.construct( &aKeys[loc], k );
565 aHashCodes[loc] = hash;
566 nFilled++;
567 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
568 // nFilled, nDeleted, nCapacity );
569 }
570
571 virtual void _erase( uint32_t loc )
572 {
573 bDeleted[loc/32] |= (1<<(loc%32));
574 ka.destroy( &aKeys[loc] );
575 nDeleted++;
576 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
577 // nFilled, nDeleted, nCapacity );
578 }
579
580 virtual key &getKeyAtPos( uint32_t nPos )
581 {
582 return aKeys[nPos];
583 }
584
585 virtual const key &getKeyAtPos( uint32_t nPos ) const
586 {
587 return aKeys[nPos];
588 }
589
590 virtual uint32_t getFirstPos( bool &bFinished ) const
591 {
592 for( uint32_t j = 0; j < nCapacity; j++ )
593 {
594 if( isFilled( j ) )
595 if( !isDeleted( j ) )
596 return j;
597 }
598
599 bFinished = true;
600 return 0;
601 }
602
603 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
604 {
605 for( uint32_t j = nPos+1; j < nCapacity; j++ )
606 {
607 if( isFilled( j ) )
608 if( !isDeleted( j ) )
609 return j;
610 }
611
612 bFinished = true;
613 return 0;
614 }
615
616 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true )
617 {
618 uint32_t nCur = hash%nCapacity;
619
620 // First we scan to see if the key is already there, abort if we
621 // run out of probing room, or we find a non-filled entry
622 int8_t j;
623 for( j = 0;
624 isFilled( nCur ) && j < 32;
625 nCur = (nCur + (1<<j))%nCapacity, j++
626 )
627 {
628 // Is this the same hash code we were looking for?
629 if( hash == aHashCodes[nCur] )
630 {
631 // Skip over deleted entries. Deleted entries are also filled,
632 // so we only have to do this check here.
633 if( isDeleted( nCur ) )
634 continue;
635
636 // Is it really the same key? (for safety)
637 if( __cmpHashKeys( aKeys[nCur], k ) == true )
638 {
639 bFill = true;
640 return nCur;
641 }
642 }
643 }
644
645 // This is our insurance, if the table is full, then go ahead and
646 // rehash, then try again.
647 if( (isFilled( nCur ) || j == 32) && rehash == true )
648 {
649 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
650
651 // This is potentially dangerous, and could cause an infinite loop.
652 // Be careful writing probe, eh?
653 return probe( hash, k, bFill );
654 }
655
656 bFill = false;
657 return nCur;
658 }
659
660 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) const
661 {
662 uint32_t nCur = hash%nCapacity;
663
664 // First we scan to see if the key is already there, abort if we
665 // run out of probing room, or we find a non-filled entry
666 for( int8_t j = 0;
667 isFilled( nCur ) && j < 32;
668 nCur = (nCur + (1<<j))%nCapacity, j++
669 )
670 {
671 // Is this the same hash code we were looking for?
672 if( hash == aHashCodes[nCur] )
673 {
674 // Skip over deleted entries. Deleted entries are also filled,
675 // so we only have to do this check here.
676 if( isDeleted( nCur ) )
677 continue;
678
679 // Is it really the same key? (for safety)
680 if( __cmpHashKeys( aKeys[nCur], k ) == true )
681 {
682 bFill = true;
683 return nCur;
684 }
685 }
686 }
687
688 bFill = false;
689 return nCur;
690 }
691
692 void reHash( uint32_t nNewSize )
693 {
694 //printf("---REHASH---");
695 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
696 // nFilled, nDeleted, nCapacity );
697
698 // Save all the old data
699 uint32_t nOldCapacity = nCapacity;
700 uint32_t *bOldFilled = bFilled;
701 uint32_t *aOldHashCodes = aHashCodes;
702 uint32_t nOldKeysSize = nKeysSize;
703 uint32_t *bOldDeleted = bDeleted;
704 key *aOldKeys = aKeys;
705
706 // Calculate new sizes
707 nCapacity = nNewSize;
708 nKeysSize = bitsToBytes( nCapacity );
709
710 // Allocate new memory + prep
711 bFilled = ca.allocate( nKeysSize );
712 bDeleted = ca.allocate( nKeysSize );
713 clearBits();
714
715 aHashCodes = ca.allocate( nCapacity );
716 aKeys = ka.allocate( nCapacity );
717
718 nDeleted = nFilled = 0;
719
720 // Re-insert all of the old data (except deleted items)
721 for( uint32_t j = 0; j < nOldCapacity; j++ )
722 {
723 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
724 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
725 {
726 insert( aOldKeys[j] );
727 }
728 }
729
730 // Delete all of the old data
731 for( uint32_t j = 0; j < nOldCapacity; j++ )
732 {
733 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
734 {
735 ka.destroy( &aOldKeys[j] );
736 }
737 }
738 ka.deallocate( aOldKeys, nOldCapacity );
739 ca.deallocate( bOldFilled, nOldKeysSize );
740 ca.deallocate( bOldDeleted, nOldKeysSize );
741 ca.deallocate( aOldHashCodes, nOldCapacity );
742 }
743
744 virtual bool isFilled( uint32_t loc ) const
745 {
746 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
747 }
748
749 virtual bool isDeleted( uint32_t loc ) const
750 {
751 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
752 }
753
754 protected:
755 uint32_t nCapacity;
756 uint32_t nFilled;
757 uint32_t nDeleted;
758 uint32_t *bFilled;
759 uint32_t *bDeleted;
760 uint32_t nKeysSize;
761 key *aKeys;
762 uint32_t *aHashCodes;
763 keyalloc ka;
764 challoc ca;
765 sizecalc szCalc;
766 }; 41 };
767
768 template<typename key, typename b, typename c, typename d>
769 Archive &operator<<( Archive &ar, const Set<key, b, c, d> &h )
770 {
771 ar << h.getSize();
772 for( typename Set<key, b, c, d>::const_iterator i = h.begin(); i != h.end(); i++ )
773 {
774 ar << (*i);
775 }
776
777 return ar;
778 }
779
780 template<typename key, typename b, typename c, typename d>
781 Archive &operator>>( Archive &ar, Set<key, b, c, d> &h )
782 {
783 h.clear();
784 long nSize;
785 ar >> nSize;
786
787 for( long j = 0; j < nSize; j++ )
788 {
789 key v;
790 ar >> v;
791 h.insert( v );
792 }
793
794 return ar;
795 }
796} 42}
797 43
798#endif 44#endif
diff --git a/src/sharedcore.h b/src/sharedcore.h
index 5a44df9..ac36606 100644
--- a/src/sharedcore.h
+++ b/src/sharedcore.h
@@ -15,10 +15,10 @@
15 15
16namespace Bu 16namespace Bu
17{ 17{
18 template<typename Core> 18 template<typename Shell, typename Core>
19 class SharedCore 19 class SharedCore
20 { 20 {
21 typedef class SharedCore<Core> _SharedType; 21 typedef class SharedCore<Shell, Core> _SharedType;
22 public: 22 public:
23 SharedCore() : 23 SharedCore() :
24 core( NULL ), 24 core( NULL ),
@@ -54,6 +54,18 @@ namespace Bu
54 return *iRefCount; 54 return *iRefCount;
55 } 55 }
56 56
57 Shell clone() const
58 {
59 Shell s( dynamic_cast<const Shell &>(*this) );
60 s._hardCopy();
61 return s;
62 }
63
64 bool isCoreShared( const Shell &rOther ) const
65 {
66 return rOther.core == core;
67 }
68
57 protected: 69 protected:
58 Core *core; 70 Core *core;
59 void _hardCopy() 71 void _hardCopy()
@@ -68,6 +80,20 @@ namespace Bu
68 iRefCount = new int( 1 ); 80 iRefCount = new int( 1 );
69 } 81 }
70 82
83 /**
84 * Reset core acts like a hard copy, except instead of providing a
85 * standalone copy of the shared core, it provides a brand new core.
86 *
87 * Very useful in functions used to reset the state of an object.
88 */
89 void _resetCore()
90 {
91 if( core )
92 _deref();
93 core = _allocateCore();
94 iRefCount = new int( 1 );
95 }
96
71 virtual Core *_allocateCore() 97 virtual Core *_allocateCore()
72 { 98 {
73 return new Core(); 99 return new Core();
diff --git a/src/tests/sharedcore.cpp b/src/tests/sharedcore.cpp
index 1d0c16e..9b0a0ec 100644
--- a/src/tests/sharedcore.cpp
+++ b/src/tests/sharedcore.cpp
@@ -14,7 +14,7 @@ struct ShintCore
14{ 14{
15 int val; 15 int val;
16}; 16};
17class Shint : public Bu::SharedCore<struct ShintCore> 17class Shint : public Bu::SharedCore<Shint, struct ShintCore>
18{ 18{
19public: 19public:
20 Shint() 20 Shint()
diff --git a/src/unit/hash.unit b/src/unit/hash.unit
index e3d7e42..124b074 100644
--- a/src/unit/hash.unit
+++ b/src/unit/hash.unit
@@ -84,4 +84,17 @@ suite Hash
84 printf(" - \"%s\" = %d\n", i.getKey().getStr(), i.getValue() ); 84 printf(" - \"%s\" = %d\n", i.getKey().getStr(), i.getValue() );
85 } */ 85 } */
86 } 86 }
87
88 test copy
89 {
90 StrIntHash h;
91 h.insert("hello", 55 );
92 h.insert("goodbye", -1812 );
93
94 StrIntHash h2 = h;
95 unitTest( h2.isCoreShared( h ) );
96
97 StrIntHash h3 = h.clone();
98 unitTest( !h3.isCoreShared( h ) );
99 }
87} 100}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 07:26:32 +0000