aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-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-09-21 14:07:34 +0000