]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | * Copyright 1993, 1995 Christopher Seiwald. | |
3 | * Copyright 2011 Steven Watanabe | |
4 | * | |
5 | * This file is part of Jam - see jam.c for Copyright information. | |
6 | */ | |
7 | ||
8 | /* | |
9 | * object.c - object manipulation routines | |
10 | * | |
11 | * External functions: | |
12 | * object_new() - create an object from a string | |
13 | * object_new_range() - create an object from a string of given length | |
14 | * object_copy() - return a copy of an object | |
15 | * object_free() - free an object | |
16 | * object_str() - get the string value of an object | |
17 | * object_done() - free string tables | |
18 | * | |
19 | * This implementation builds a hash table of all strings, so that multiple | |
20 | * calls of object_new() on the same string allocate memory for the string once. | |
21 | * Strings are never actually freed. | |
22 | */ | |
23 | ||
24 | #include "jam.h" | |
25 | #include "object.h" | |
26 | #include "output.h" | |
27 | ||
28 | #include <assert.h> | |
29 | #include <stddef.h> | |
30 | #include <stdlib.h> | |
31 | ||
32 | ||
33 | #define OBJECT_MAGIC 0xa762e0e3u | |
34 | ||
35 | #ifndef object_copy | |
36 | ||
37 | struct hash_header | |
38 | { | |
39 | #ifndef NDEBUG | |
40 | unsigned int magic; | |
41 | #endif | |
42 | unsigned int hash; | |
43 | struct hash_item * next; | |
44 | }; | |
45 | ||
46 | #endif | |
47 | ||
48 | struct hash_item | |
49 | { | |
50 | struct hash_header header; | |
51 | char data[ 1 ]; | |
52 | }; | |
53 | ||
54 | #define ALLOC_ALIGNMENT (sizeof(struct hash_item) - sizeof(struct hash_header)) | |
55 | ||
56 | typedef struct string_set | |
57 | { | |
58 | unsigned int num; | |
59 | unsigned int size; | |
60 | struct hash_item * * data; | |
61 | } string_set; | |
62 | ||
63 | static string_set strhash; | |
64 | static int strtotal = 0; | |
65 | static int strcount_in = 0; | |
66 | static int strcount_out = 0; | |
67 | ||
68 | ||
69 | /* | |
70 | * Immortal string allocator implementation speeds string allocation and cuts | |
71 | * down on internal fragmentation. | |
72 | */ | |
73 | ||
74 | #define STRING_BLOCK 4096 | |
75 | typedef struct strblock | |
76 | { | |
77 | struct strblock * next; | |
78 | char data[ STRING_BLOCK ]; | |
79 | } strblock; | |
80 | ||
81 | static strblock * strblock_chain = 0; | |
82 | ||
83 | /* Storage remaining in the current strblock */ | |
84 | static char * storage_start = 0; | |
85 | static char * storage_finish = 0; | |
86 | ||
87 | ||
88 | /* | |
89 | * allocate() - Allocate n bytes of immortal string storage. | |
90 | */ | |
91 | ||
92 | static char * allocate( size_t n ) | |
93 | { | |
94 | #ifdef BJAM_NEWSTR_NO_ALLOCATE | |
95 | return (char *)BJAM_MALLOC( n ); | |
96 | #else | |
97 | /* See if we can grab storage from an existing block. */ | |
98 | size_t remaining = storage_finish - storage_start; | |
99 | n = ( ( n + ALLOC_ALIGNMENT - 1 ) / ALLOC_ALIGNMENT ) * ALLOC_ALIGNMENT; | |
100 | if ( remaining >= n ) | |
101 | { | |
102 | char * result = storage_start; | |
103 | storage_start += n; | |
104 | return result; | |
105 | } | |
106 | else /* Must allocate a new block. */ | |
107 | { | |
108 | strblock * new_block; | |
109 | size_t nalloc = n; | |
110 | if ( nalloc < STRING_BLOCK ) | |
111 | nalloc = STRING_BLOCK; | |
112 | ||
113 | /* Allocate a new block and link into the chain. */ | |
114 | new_block = (strblock *)BJAM_MALLOC( offsetof( strblock, data[ 0 ] ) + | |
115 | nalloc * sizeof( new_block->data[ 0 ] ) ); | |
116 | if ( new_block == 0 ) | |
117 | return 0; | |
118 | new_block->next = strblock_chain; | |
119 | strblock_chain = new_block; | |
120 | ||
121 | /* Take future allocations out of the larger remaining space. */ | |
122 | if ( remaining < nalloc - n ) | |
123 | { | |
124 | storage_start = new_block->data + n; | |
125 | storage_finish = new_block->data + nalloc; | |
126 | } | |
127 | return new_block->data; | |
128 | } | |
129 | #endif | |
130 | } | |
131 | ||
132 | ||
133 | static unsigned int hash_keyval( char const * key, int const size ) | |
134 | { | |
135 | unsigned int const magic = 2147059363; | |
136 | unsigned int hash = 0; | |
137 | ||
138 | unsigned int i; | |
139 | for ( i = 0; i < size / sizeof( unsigned int ); ++i ) | |
140 | { | |
141 | unsigned int val; | |
142 | memcpy( &val, key, sizeof( unsigned int ) ); | |
143 | hash = hash * magic + val; | |
144 | key += sizeof( unsigned int ); | |
145 | } | |
146 | ||
147 | { | |
148 | unsigned int val = 0; | |
149 | memcpy( &val, key, size % sizeof( unsigned int ) ); | |
150 | hash = hash * magic + val; | |
151 | } | |
152 | ||
153 | return hash + ( hash >> 17 ); | |
154 | } | |
155 | ||
156 | ||
157 | static void string_set_init( string_set * set ) | |
158 | { | |
159 | set->size = 0; | |
160 | set->num = 4; | |
161 | set->data = (struct hash_item * *)BJAM_MALLOC( set->num * sizeof( struct hash_item * ) ); | |
162 | memset( set->data, 0, set->num * sizeof( struct hash_item * ) ); | |
163 | } | |
164 | ||
165 | ||
166 | static void string_set_done( string_set * set ) | |
167 | { | |
168 | BJAM_FREE( set->data ); | |
169 | } | |
170 | ||
171 | ||
172 | static void string_set_resize( string_set * set ) | |
173 | { | |
174 | unsigned i; | |
175 | string_set new_set; | |
176 | new_set.num = set->num * 2; | |
177 | new_set.size = set->size; | |
178 | new_set.data = (struct hash_item * *)BJAM_MALLOC( sizeof( struct hash_item * | |
179 | ) * new_set.num ); | |
180 | memset( new_set.data, 0, sizeof( struct hash_item * ) * new_set.num ); | |
181 | for ( i = 0; i < set->num; ++i ) | |
182 | { | |
183 | while ( set->data[ i ] ) | |
184 | { | |
185 | struct hash_item * temp = set->data[ i ]; | |
186 | unsigned pos = temp->header.hash % new_set.num; | |
187 | set->data[ i ] = temp->header.next; | |
188 | temp->header.next = new_set.data[ pos ]; | |
189 | new_set.data[ pos ] = temp; | |
190 | } | |
191 | } | |
192 | BJAM_FREE( set->data ); | |
193 | *set = new_set; | |
194 | } | |
195 | ||
196 | ||
197 | static char const * string_set_insert( string_set * set, char const * string, | |
198 | int const size ) | |
199 | { | |
200 | unsigned hash = hash_keyval( string, size ); | |
201 | unsigned pos = hash % set->num; | |
202 | ||
203 | struct hash_item * result; | |
204 | ||
205 | for ( result = set->data[ pos ]; result; result = result->header.next ) | |
206 | if ( !strncmp( result->data, string, size ) && !result->data[ size ] ) | |
207 | return result->data; | |
208 | ||
209 | if ( set->size >= set->num ) | |
210 | { | |
211 | string_set_resize( set ); | |
212 | pos = hash % set->num; | |
213 | } | |
214 | ||
215 | result = (struct hash_item *)allocate( sizeof( struct hash_header ) + size + | |
216 | 1 ); | |
217 | result->header.hash = hash; | |
218 | result->header.next = set->data[ pos ]; | |
219 | #ifndef NDEBUG | |
220 | result->header.magic = OBJECT_MAGIC; | |
221 | #endif | |
222 | memcpy( result->data, string, size ); | |
223 | result->data[ size ] = '\0'; | |
224 | assert( hash_keyval( result->data, size ) == result->header.hash ); | |
225 | set->data[ pos ] = result; | |
226 | strtotal += size + 1; | |
227 | ++set->size; | |
228 | ||
229 | return result->data; | |
230 | } | |
231 | ||
232 | ||
233 | static struct hash_item * object_get_item( OBJECT * obj ) | |
234 | { | |
235 | return (struct hash_item *)( (char *)obj - offsetof( struct hash_item, data | |
236 | ) ); | |
237 | } | |
238 | ||
239 | ||
240 | static void object_validate( OBJECT * obj ) | |
241 | { | |
242 | assert( obj ); | |
243 | assert( object_get_item( obj )->header.magic == OBJECT_MAGIC ); | |
244 | } | |
245 | ||
246 | ||
247 | /* | |
248 | * object_new_range() - create an object from a string of given length | |
249 | */ | |
250 | ||
251 | OBJECT * object_new_range( char const * const string, int const size ) | |
252 | { | |
253 | ++strcount_in; | |
254 | ||
255 | #ifdef BJAM_NO_MEM_CACHE | |
256 | { | |
257 | struct hash_item * const m = (struct hash_item *)BJAM_MALLOC( sizeof( | |
258 | struct hash_header ) + size + 1 ); | |
259 | strtotal += size + 1; | |
260 | memcpy( m->data, string, size ); | |
261 | m->data[ size ] = '\0'; | |
262 | #ifndef NDEBUG | |
263 | m->header.magic = OBJECT_MAGIC; | |
264 | #endif | |
265 | return (OBJECT *)m->data; | |
266 | } | |
267 | #else | |
268 | if ( !strhash.data ) | |
269 | string_set_init( &strhash ); | |
270 | return (OBJECT *)string_set_insert( &strhash, string, size ); | |
271 | #endif | |
272 | } | |
273 | ||
274 | ||
275 | /* | |
276 | * object_new() - create an object from a string | |
277 | */ | |
278 | ||
279 | OBJECT * object_new( char const * const string ) | |
280 | { | |
281 | return object_new_range( string, strlen( string ) ); | |
282 | } | |
283 | ||
284 | ||
285 | #ifndef object_copy | |
286 | ||
287 | /* | |
288 | * object_copy() - return a copy of an object | |
289 | */ | |
290 | ||
291 | OBJECT * object_copy( OBJECT * obj ) | |
292 | { | |
293 | object_validate( obj ); | |
294 | #ifdef BJAM_NO_MEM_CACHE | |
295 | return object_new( object_str( obj ) ); | |
296 | #else | |
297 | ++strcount_in; | |
298 | return obj; | |
299 | #endif | |
300 | } | |
301 | ||
302 | ||
303 | /* | |
304 | * object_free() - free an object | |
305 | */ | |
306 | ||
307 | void object_free( OBJECT * obj ) | |
308 | { | |
309 | object_validate( obj ); | |
310 | #ifdef BJAM_NO_MEM_CACHE | |
311 | BJAM_FREE( object_get_item( obj ) ); | |
312 | #endif | |
313 | ++strcount_out; | |
314 | } | |
315 | ||
316 | ||
317 | /* | |
318 | * object_str() - return the OBJECT's internal C string | |
319 | */ | |
320 | ||
321 | char const * object_str( OBJECT * obj ) | |
322 | { | |
323 | object_validate( obj ); | |
324 | return (char const *)obj; | |
325 | } | |
326 | ||
327 | ||
328 | /* | |
329 | * object_equal() - compare two objects | |
330 | */ | |
331 | ||
332 | int object_equal( OBJECT * lhs, OBJECT * rhs ) | |
333 | { | |
334 | object_validate( lhs ); | |
335 | object_validate( rhs ); | |
336 | #ifdef BJAM_NO_MEM_CACHE | |
337 | return !strcmp( object_str( lhs ), object_str( rhs ) ); | |
338 | #else | |
339 | assert( ( lhs == rhs ) == !strcmp( object_str( lhs ), object_str( rhs ) ) ); | |
340 | return lhs == rhs; | |
341 | #endif | |
342 | } | |
343 | ||
344 | ||
345 | /* | |
346 | * object_hash() - returns the hash value of an object | |
347 | */ | |
348 | ||
349 | unsigned int object_hash( OBJECT * obj ) | |
350 | { | |
351 | object_validate( obj ); | |
352 | #ifdef BJAM_NO_MEM_CACHE | |
353 | return hash_keyval( object_str( obj ), strlen( object_str( obj ) ) ); | |
354 | #else | |
355 | return object_get_item( obj )->header.hash; | |
356 | #endif | |
357 | } | |
358 | ||
359 | #endif | |
360 | ||
361 | /* | |
362 | * object_done() - free string tables. | |
363 | */ | |
364 | ||
365 | void object_done() | |
366 | { | |
367 | #ifdef BJAM_NEWSTR_NO_ALLOCATE | |
368 | unsigned i; | |
369 | for ( i = 0; i < strhash.num; ++i ) | |
370 | { | |
371 | while ( strhash.data[ i ] ) | |
372 | { | |
373 | struct hash_item * item = strhash.data[ i ]; | |
374 | strhash.data[ i ] = item->header.next; | |
375 | BJAM_FREE( item ); | |
376 | } | |
377 | } | |
378 | #else | |
379 | /* Reclaim string blocks. */ | |
380 | while ( strblock_chain ) | |
381 | { | |
382 | strblock * const n = strblock_chain->next; | |
383 | BJAM_FREE( strblock_chain ); | |
384 | strblock_chain = n; | |
385 | } | |
386 | #endif | |
387 | ||
388 | string_set_done( &strhash ); | |
389 | ||
390 | if ( DEBUG_MEM ) | |
391 | { | |
392 | out_printf( "%dK in strings\n", strtotal / 1024 ); | |
393 | if ( strcount_in != strcount_out ) | |
394 | out_printf( "--- %d strings of %d dangling\n", strcount_in - | |
395 | strcount_out, strcount_in ); | |
396 | } | |
397 | } |