Subject: [Boost-commit] svn:boost r75545 - trunk/tools/build/v2/engine
From: steven_at_[hidden]
Date: 2011-11-18 12:27:30
Author: steven_watanabe
Date: 2011-11-18 12:27:28 EST (Fri, 18 Nov 2011)
New Revision: 75545
URL: http://svn.boost.org/trac/boost/changeset/75545
Log:
Use a separate hash table implementation for the strings table.
Text files modified:
trunk/tools/build/v2/engine/newstr.c | 170 ++++++++++++++++++++++++++++++++--------
1 files changed, 136 insertions(+), 34 deletions(-)
Modified: trunk/tools/build/v2/engine/newstr.c
==============================================================================
--- trunk/tools/build/v2/engine/newstr.c (original)
+++ trunk/tools/build/v2/engine/newstr.c 2011-11-18 12:27:28 EST (Fri, 18 Nov 2011)
@@ -6,7 +6,6 @@
# include "jam.h"
# include "newstr.h"
-# include "hash.h"
# include "compile.h"
# include <stddef.h>
# include <stdlib.h>
@@ -31,9 +30,28 @@
* Strings are never actually freed.
*/
-typedef char * STRING;
+struct hash_header
+{
+ unsigned int hash;
+ struct hash_item * next;
+};
+
+struct hash_item
+{
+ struct hash_header header;
+ char data[1];
+};
+
+#define ALLOC_ALIGNMENT ( sizeof( struct hash_item ) - sizeof( struct hash_header ) )
-static struct hash * strhash = 0;
+typedef struct string_set
+{
+ unsigned int num;
+ unsigned int size;
+ struct hash_item * * data;
+} string_set;
+
+static string_set strhash;
static int strtotal = 0;
static int strcount_in = 0;
static int strcount_out = 0;
@@ -62,13 +80,14 @@
* allocate() - Allocate n bytes of immortal string storage.
*/
-static char * allocate( size_t const n )
+static char * allocate( size_t n )
{
#ifdef BJAM_NEWSTR_NO_ALLOCATE
- return (char*)BJAM_MALLOC_ATOMIC(n);
+ return (char*)BJAM_MALLOC(n);
#else
/* See if we can grab storage from an existing block. */
size_t remaining = storage_finish - storage_start;
+ n = ((n + ALLOC_ALIGNMENT - 1) / ALLOC_ALIGNMENT) * ALLOC_ALIGNMENT;
if ( remaining >= n )
{
char * result = storage_start;
@@ -100,6 +119,102 @@
#endif
}
+static unsigned int hash_keyval( const char * key )
+{
+ unsigned int hash = 0;
+ unsigned i;
+ unsigned int len = strlen( key );
+
+ for ( i = 0; i < len / sizeof( unsigned int ); ++i )
+ {
+ unsigned int val;
+ memcpy( &val, key, sizeof( unsigned int ) );
+ hash = hash * 2147059363 + val;
+ key += sizeof( unsigned int );
+ }
+
+ {
+ unsigned int val = 0;
+ memcpy( &val, key, len % sizeof( unsigned int ) );
+ hash = hash * 2147059363 + val;
+ }
+
+ hash += (hash >> 17);
+
+ return hash;
+}
+
+static void string_set_init(string_set * set)
+{
+ set->size = 0;
+ set->num = 4;
+ set->data = (struct hash_item * *)BJAM_MALLOC( set->num * sizeof( struct hash_item * ) );
+ memset( set->data, 0, set->num * sizeof( struct hash_item * ) );
+}
+
+static void string_set_done(string_set * set)
+{
+ BJAM_FREE( set->data );
+}
+
+static void string_set_resize(string_set *set)
+{
+ unsigned i;
+ string_set new_set;
+ new_set.num = set->num * 2;
+ new_set.size = set->size;
+ new_set.data = (struct hash_item * *)BJAM_MALLOC( sizeof( struct hash_item * ) * new_set.num );
+ memset(new_set.data, 0, sizeof(struct hash_item *) * new_set.num);
+ for ( i = 0; i < set->num; ++i )
+ {
+ while ( set->data[i] )
+ {
+ int k = 0;
+ struct hash_item * temp = set->data[i];
+ unsigned pos = temp->header.hash % new_set.num;
+ set->data[i] = temp->header.next;
+ temp->header.next = new_set.data[pos];
+ new_set.data[pos] = temp;
+ }
+ }
+ BJAM_FREE( set->data );
+ *set = new_set;
+}
+
+static const char * string_set_insert ( string_set * set, const char * string )
+{
+ unsigned hash = hash_keyval( string );
+ unsigned pos = hash % set->num;
+ unsigned l;
+ unsigned aligned;
+
+ struct hash_item * result;
+
+ for ( result = set->data[pos]; result; result = result->header.next )
+ {
+ if ( strcmp( result->data, string ) == 0 )
+ {
+ return result->data;
+ }
+ }
+
+ if( set->size >= set->num )
+ {
+ string_set_resize( set );
+ pos = hash % set->num;
+ }
+
+ l = strlen( string );
+ result = (struct hash_item *)allocate( sizeof( struct hash_header ) + l + 1 );
+ result->header.hash = hash;
+ result->header.next = set->data[pos];
+ memcpy( result->data, string, l + 1 );
+ set->data[pos] = result;
+ strtotal += l + 1;
+ ++set->size;
+
+ return result->data;
+}
/*
* newstr() - return a dynamically allocated copy of a string.
@@ -115,26 +230,12 @@
memcpy( m, string, l + 1 );
return m;
#else
- STRING str;
- STRING * s = &str;
-
- if ( !strhash )
- strhash = hashinit( sizeof( STRING ), "strings" );
-
- *s = string;
-
- if ( hashenter( strhash, (HASHDATA **)&s ) )
- {
- int l = strlen( string );
- char * m = (char *)allocate( l + 1 );
-
- strtotal += l + 1;
- memcpy( m, string, l + 1 );
- *s = m;
- }
+ if ( ! strhash.data )
+ string_set_init( &strhash );
strcount_in += 1;
- return *s;
+
+ return (char *)string_set_insert( &strhash, string );
#endif
}
@@ -168,15 +269,6 @@
}
-#ifdef BJAM_NEWSTR_NO_ALLOCATE
-
-static void freestring( void * xstring, void * data )
-{
- BJAM_FREE( *(STRING *)xstring );
-}
-
-#endif
-
/*
* str_done() - free string tables.
*/
@@ -186,7 +278,17 @@
#ifdef BJAM_NEWSTR_NO_ALLOCATE
- hashenumerate( strhash, freestring, (void *)0 );
+ unsigned i;
+
+ for ( i = 0; i < strhash.num; ++i )
+ {
+ while ( strhash.data[i] )
+ {
+ struct hash_item * item = strhash.data[i];
+ strhash.data[i] = item->header.next;
+ BJAM_FREE( item );
+ }
+ }
#else
@@ -200,7 +302,7 @@
#endif
- hashdone( strhash );
+ string_set_done( &strhash );
if ( DEBUG_MEM )
printf( "%dK in strings\n", strtotal / 1024 );