]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/tools/build/src/engine/hash.c
2fa12030b862fd2bb69baa99d2811151914061b8
2 * Copyright 1993, 1995 Christopher Seiwald.
4 * This file is part of Jam - see jam.c for Copyright information.
8 * hash.c - simple in-memory hashing routines
11 * hashinit() - initialize a hash table, returning a handle
12 * hashitem() - find a record in the table, and optionally enter a new one
13 * hashdone() - free a hash table, given its handle
16 * hashrehash() - resize and rebuild hp->tab, the hash table
28 #define HASH_DEBUG_PROFILE 1
31 /* Header attached to all hash table data items. */
33 typedef struct item ITEM
;
44 * the hash table, just an array of item pointers
52 int bloat
; /* tab.nel / items.nel */
53 int inel
; /* initial number of elements */
56 * the array of records, maintained by these routines - essentially a
61 int more
; /* how many more ITEMs fit in lists[ list ] */
62 ITEM
* free
; /* free list of items */
63 char * next
; /* where to put more ITEMs in lists[ list ] */
64 int size
; /* sizeof( ITEM ) + aligned datalen */
65 int nel
; /* total ITEMs held by all lists[] */
66 int list
; /* index into lists[] */
70 int nel
; /* total ITEMs held by this list */
71 char * base
; /* base of ITEMs array */
75 char const * name
; /* just for hashstats() */
78 static void hashrehash( struct hash
* );
79 static void hashstat( struct hash
* );
81 static unsigned int hash_keyval( OBJECT
* key
)
83 return object_hash( key
);
86 #define hash_bucket(hp, keyval) ((hp)->tab.base + ((keyval) % (hp)->tab.nel))
88 #define hash_data_key(data) (*(OBJECT * *)(data))
89 #define hash_item_data(item) ((HASHDATA *)((char *)item + sizeof(ITEM)))
90 #define hash_item_key(item) (hash_data_key(hash_item_data(item)))
93 #define ALIGNED(x) ((x + sizeof(ITEM) - 1) & ~(sizeof(ITEM) - 1))
96 * hashinit() - initialize a hash table, returning a handle
99 struct hash
* hashinit( int datalen
, char const * name
)
101 struct hash
* hp
= (struct hash
*)BJAM_MALLOC( sizeof( *hp
) );
108 hp
->items
.size
= sizeof( ITEM
) + ALIGNED( datalen
);
111 hp
->inel
= 11; /* 47 */
119 * hash_search() - Find the hash item for the given data.
121 * Returns a pointer to a hashed item with the given key. If given a 'previous'
122 * pointer, makes it point to the item prior to the found item in the same
123 * bucket or to 0 if our item is the first item in its bucket.
126 static ITEM
* hash_search( struct hash
* hp
, unsigned int keyval
,
127 OBJECT
* keydata
, ITEM
* * previous
)
129 ITEM
* i
= *hash_bucket( hp
, keyval
);
131 for ( ; i
; i
= i
->next
)
133 if ( object_equal( hash_item_key( i
), keydata
) )
146 * hash_insert() - insert a record in the table or return the existing one
149 HASHDATA
* hash_insert( struct hash
* hp
, OBJECT
* key
, int * found
)
152 unsigned int keyval
= hash_keyval( key
);
154 #ifdef HASH_DEBUG_PROFILE
155 profile_frame prof
[ 1 ];
157 profile_enter( 0, prof
);
160 if ( !hp
->items
.more
)
163 i
= hash_search( hp
, keyval
, key
, 0 );
168 ITEM
* * base
= hash_bucket( hp
, keyval
);
170 /* Try to grab one from the free list. */
171 if ( hp
->items
.free
)
174 hp
->items
.free
= i
->next
;
175 assert( !hash_item_key( i
) );
179 i
= (ITEM
*)hp
->items
.next
;
180 hp
->items
.next
+= hp
->items
.size
;
188 #ifdef HASH_DEBUG_PROFILE
190 profile_exit( prof
);
193 return hash_item_data( i
);
198 * hash_find() - find a record in the table or NULL if none exists
201 HASHDATA
* hash_find( struct hash
* hp
, OBJECT
* key
)
204 unsigned int keyval
= hash_keyval( key
);
206 #ifdef HASH_DEBUG_PROFILE
207 profile_frame prof
[ 1 ];
209 profile_enter( 0, prof
);
212 if ( !hp
->items
.nel
)
214 #ifdef HASH_DEBUG_PROFILE
216 profile_exit( prof
);
221 i
= hash_search( hp
, keyval
, key
, 0 );
223 #ifdef HASH_DEBUG_PROFILE
225 profile_exit( prof
);
228 return i
? hash_item_data( i
) : 0;
233 * hashrehash() - resize and rebuild hp->tab, the hash table
236 static void hashrehash( struct hash
* hp
)
238 int i
= ++hp
->items
.list
;
239 hp
->items
.more
= i
? 2 * hp
->items
.nel
: hp
->inel
;
240 hp
->items
.next
= (char *)BJAM_MALLOC( hp
->items
.more
* hp
->items
.size
);
243 hp
->items
.lists
[ i
].nel
= hp
->items
.more
;
244 hp
->items
.lists
[ i
].base
= hp
->items
.next
;
245 hp
->items
.nel
+= hp
->items
.more
;
248 BJAM_FREE( (char *)hp
->tab
.base
);
250 hp
->tab
.nel
= hp
->items
.nel
* hp
->bloat
;
251 hp
->tab
.base
= (ITEM
* *)BJAM_MALLOC( hp
->tab
.nel
* sizeof( ITEM
* * ) );
253 memset( (char *)hp
->tab
.base
, '\0', hp
->tab
.nel
* sizeof( ITEM
* ) );
255 for ( i
= 0; i
< hp
->items
.list
; ++i
)
257 int nel
= hp
->items
.lists
[ i
].nel
;
258 char * next
= hp
->items
.lists
[ i
].base
;
260 for ( ; nel
--; next
+= hp
->items
.size
)
262 ITEM
* i
= (ITEM
*)next
;
263 ITEM
* * ip
= hp
->tab
.base
+ object_hash( hash_item_key( i
) ) %
265 /* code currently assumes rehashing only when there are no free
268 assert( hash_item_key( i
) );
277 void hashenumerate( struct hash
* hp
, void (* f
)( void *, void * ), void * data
281 for ( i
= 0; i
<= hp
->items
.list
; ++i
)
283 char * next
= hp
->items
.lists
[ i
].base
;
284 int nel
= hp
->items
.lists
[ i
].nel
;
285 if ( i
== hp
->items
.list
)
286 nel
-= hp
->items
.more
;
288 for ( ; nel
--; next
+= hp
->items
.size
)
290 ITEM
* const i
= (ITEM
*)next
;
291 if ( hash_item_key( i
) != 0 ) /* Do not enumerate freed items. */
292 f( hash_item_data( i
), data
);
299 * hash_free() - free a hash table, given its handle
302 void hash_free( struct hash
* hp
)
308 BJAM_FREE( (char *)hp
->tab
.base
);
309 for ( i
= 0; i
<= hp
->items
.list
; ++i
)
310 BJAM_FREE( hp
->items
.lists
[ i
].base
);
311 BJAM_FREE( (char *)hp
);
315 static void hashstat( struct hash
* hp
)
317 struct hashstats stats
[ 1 ];
318 hashstats_init( stats
);
319 hashstats_add( stats
, hp
);
320 hashstats_print( stats
, hp
->name
);
324 void hashstats_init( struct hashstats
* stats
)
327 stats
->num_items
= 0;
329 stats
->item_size
= 0;
331 stats
->num_hashes
= 0;
335 void hashstats_add( struct hashstats
* stats
, struct hash
* hp
)
339 ITEM
* * tab
= hp
->tab
.base
;
340 int nel
= hp
->tab
.nel
;
345 for ( i
= 0; i
< nel
; ++i
)
349 for ( item
= tab
[ i
]; item
; item
= item
->next
)
357 stats
->count
+= count
;
359 stats
->num_items
+= hp
->items
.nel
;
360 stats
->tab_size
+= hp
->tab
.nel
;
361 stats
->item_size
= hp
->items
.size
;
367 void hashstats_print( struct hashstats
* stats
, char const * name
)
369 out_printf( "%s table: %d+%d+%d (%dK+%luK+%luK) items+table+hash, %f density\n",
374 stats
->num_items
* stats
->item_size
/ 1024,
375 (long unsigned)stats
->tab_size
* sizeof( ITEM
* * ) / 1024,
376 (long unsigned)stats
->num_hashes
* sizeof( struct hash
) / 1024,
377 (float)stats
->count
/ (float)stats
->sets
);
381 void hashdone( struct hash
* hp
)
385 if ( DEBUG_MEM
|| DEBUG_PROFILE
)