[Boost-commit] svn:boost r75545 - trunk/tools/build/v2/engine

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 );