1 files changed, 404 insertions, 0 deletions
diff --git a/src/boost/tools/build/src/engine/object.cpp b/src/boost/tools/build/src/engine/object.cpp
new file mode 100644
index 000000000..fc625e6f5
--- /dev/null
+++ b/src/boost/tools/build/src/engine/object.cpp
@@ -0,0 +1,404 @@
+/*
+ * Copyright 1993, 1995 Christopher Seiwald.
+ * Copyright 2011 Steven Watanabe
+ *
+ * This file is part of Jam - see jam.c for Copyright information.
+ */
+
+/*
+ * object.c - object manipulation routines
+ *
+ * External functions:
+ *    object_new()       - create an object from a string
+ *    object_new_range() - create an object from a string of given length
+ *    object_copy()      - return a copy of an object
+ *    object_free()      - free an object
+ *    object_str()       - get the string value of an object
+ *    object_done()      - free string tables
+ *
+ * This implementation builds a hash table of all strings, so that multiple
+ * calls of object_new() on the same string allocate memory for the string once.
+ * Strings are never actually freed.
+ */
+
+#include "jam.h"
+#include "object.h"
+#include "output.h"
+
+#include <assert.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+
+#define OBJECT_MAGIC 0xa762e0e3u
+
+#ifndef object_copy
+
+struct hash_header
+{
+#ifndef NDEBUG
+    unsigned int magic;
+#endif
+    unsigned int hash;
+    struct hash_item * next;
+};
+
+#endif
+
+struct hash_item
+{
+    struct hash_header header;
+    char data[ 1 ];
+};
+
+#define ALLOC_ALIGNMENT (sizeof(struct hash_item) - sizeof(struct hash_header))
+
+typedef struct string_set
+{
+    int32_t num;
+    int32_t size;
+    struct hash_item * * data;
+} string_set;
+
+#if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
+static string_set strhash;
+#endif
+static int32_t strtotal = 0;
+static int32_t strcount_in = 0;
+static int32_t strcount_out = 0;
+
+
+/*
+ * Immortal string allocator implementation speeds string allocation and cuts
+ * down on internal fragmentation.
+ */
+
+#define STRING_BLOCK 4096
+typedef struct strblock
+{
+    struct strblock * next;
+    char data[ STRING_BLOCK ];
+} strblock;
+
+static strblock * strblock_chain = 0;
+
+#if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
+/* Storage remaining in the current strblock */
+static char * storage_start = 0;
+static char * storage_finish = 0;
+
+
+/*
+ * allocate() - Allocate n bytes of immortal string storage.
+ */
+
+static char * allocate( int32_t n )
+{
+#ifdef BJAM_NEWSTR_NO_ALLOCATE
+    return (char *)BJAM_MALLOC( n );
+#else
+    /* See if we can grab storage from an existing block. */
+    int32_t remaining = int32_t(storage_finish - storage_start);
+    n = ( ( n + ALLOC_ALIGNMENT - 1 ) / ALLOC_ALIGNMENT ) * ALLOC_ALIGNMENT;
+    if ( remaining >= n )
+    {
+        char * result = storage_start;
+        storage_start += n;
+        return result;
+    }
+    else  /* Must allocate a new block. */
+    {
+        strblock * new_block;
+        int32_t nalloc = n;
+        if ( nalloc < STRING_BLOCK )
+            nalloc = STRING_BLOCK;
+
+        /* Allocate a new block and link into the chain. */
+        new_block = (strblock *)BJAM_MALLOC( offsetof( strblock, data[ 0 ] ) +
+            size_t(nalloc) * sizeof( new_block->data[ 0 ] ) );
+        if ( new_block == 0 )
+            return 0;
+        new_block->next = strblock_chain;
+        strblock_chain = new_block;
+
+        /* Take future allocations out of the larger remaining space. */
+        if ( remaining < nalloc - n )
+        {
+            storage_start = new_block->data + n;
+            storage_finish = new_block->data + nalloc;
+        }
+        return new_block->data;
+    }
+#endif
+}
+#endif
+
+
+static unsigned int hash_keyval( char const * key, int32_t size )
+{
+    unsigned int const magic = 2147059363;
+    unsigned int hash = 0;
+
+    unsigned int i;
+    for ( i = 0; i < size / sizeof( unsigned int ); ++i )
+    {
+        unsigned int val;
+        memcpy( &val, key, sizeof( unsigned int ) );
+        hash = hash * magic + val;
+        key += sizeof( unsigned int );
+    }
+
+    {
+        unsigned int val = 0;
+        memcpy( &val, key, size % sizeof( unsigned int ) );
+        hash = hash * magic + val;
+    }
+
+    return hash + ( hash >> 17 );
+}
+
+
+#if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
+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 )
+{
+    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 ( int32_t i = 0; i < set->num; ++i )
+    {
+        while ( set->data[ i ] )
+        {
+            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 char const * string_set_insert( string_set * set, char const * string,
+    int32_t const size )
+{
+    unsigned hash = hash_keyval( string, size );
+    unsigned pos = hash % set->num;
+
+    struct hash_item * result;
+
+    for ( result = set->data[ pos ]; result; result = result->header.next )
+        if ( !strncmp( result->data, string, size ) && !result->data[ size ] )
+            return result->data;
+
+    if ( set->size >= set->num )
+    {
+        string_set_resize( set );
+        pos = hash % set->num;
+    }
+
+    result = (struct hash_item *)allocate( sizeof( struct hash_header ) + size +
+        1 );
+    result->header.hash = hash;
+    result->header.next = set->data[ pos ];
+#ifndef NDEBUG
+    result->header.magic = OBJECT_MAGIC;
+#endif
+    memcpy( result->data, string, size );
+    result->data[ size ] = '\0';
+    assert( hash_keyval( result->data, size ) == result->header.hash );
+    set->data[ pos ] = result;
+    strtotal += size + 1;
+    ++set->size;
+
+    return result->data;
+}
+#endif
+
+
+/*
+ * object_new_range() - create an object from a string of given length
+ */
+
+OBJECT * object_new_range( char const * const string, int32_t size )
+{
+    ++strcount_in;
+
+#ifdef BJAM_NO_MEM_CACHE
+    {
+        struct hash_item * const m = (struct hash_item *)BJAM_MALLOC( sizeof(
+            struct hash_header ) + size + 1 );
+        strtotal += size + 1;
+        memcpy( m->data, string, size );
+        m->data[ size ] = '\0';
+#ifndef NDEBUG
+        m->header.magic = OBJECT_MAGIC;
+#endif
+        return (OBJECT *)m->data;
+    }
+#else
+    if ( !strhash.data )
+        string_set_init( &strhash );
+    return (OBJECT *)string_set_insert( &strhash, string, size );
+#endif
+}
+
+
+/*
+ * object_new() - create an object from a string
+ */
+
+OBJECT * object_new( char const * const string )
+{
+    return object_new_range( string, int32_t(strlen( string )) );
+}
+
+
+#ifndef object_copy
+
+static struct hash_item * object_get_item( OBJECT * obj )
+{
+    return (struct hash_item *)( (char *)obj - offsetof( struct hash_item, data
+        ) );
+}
+
+
+static void object_validate( OBJECT * obj )
+{
+    assert( obj );
+    assert( object_get_item( obj )->header.magic == OBJECT_MAGIC );
+}
+
+
+/*
+ * object_copy() - return a copy of an object
+ */
+
+OBJECT * object_copy( OBJECT * obj )
+{
+    object_validate( obj );
+#ifdef BJAM_NO_MEM_CACHE
+    return object_new( object_str( obj ) );
+#else
+    ++strcount_in;
+    return obj;
+#endif
+}
+
+
+/*
+ * object_free() - free an object
+ */
+
+void object_free( OBJECT * obj )
+{
+    object_validate( obj );
+#ifdef BJAM_NO_MEM_CACHE
+    BJAM_FREE( object_get_item( obj ) );
+#endif
+    ++strcount_out;
+}
+
+
+/*
+ * object_str() - return the OBJECT's internal C string
+ */
+
+char const * object_str( OBJECT * obj )
+{
+    object_validate( obj );
+    return (char const *)obj;
+}
+
+
+/*
+ * object_equal() - compare two objects
+ */
+
+int object_equal( OBJECT * lhs, OBJECT * rhs )
+{
+    object_validate( lhs );
+    object_validate( rhs );
+#ifdef BJAM_NO_MEM_CACHE
+    return !strcmp( object_str( lhs ), object_str( rhs ) );
+#else
+    assert( ( lhs == rhs ) == !strcmp( object_str( lhs ), object_str( rhs ) ) );
+    return lhs == rhs;
+#endif
+}
+
+
+/*
+ * object_hash() - returns the hash value of an object
+ */
+
+unsigned int object_hash( OBJECT * obj )
+{
+    object_validate( obj );
+#ifdef BJAM_NO_MEM_CACHE
+    return hash_keyval( object_str( obj ), strlen( object_str( obj ) ) );
+#else
+    return object_get_item( obj )->header.hash;
+#endif
+}
+
+#endif
+
+/*
+ * object_done() - free string tables.
+ */
+
+void object_done()
+{
+#ifdef BJAM_NEWSTR_NO_ALLOCATE
+    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
+    /* Reclaim string blocks. */
+    while ( strblock_chain )
+    {
+        strblock * const n = strblock_chain->next;
+        BJAM_FREE( strblock_chain );
+        strblock_chain = n;
+    }
+#endif
+
+#if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
+    string_set_done( &strhash );
+#endif
+
+    if ( DEBUG_MEM )
+    {
+        out_printf( "%dK in strings\n", strtotal / 1024 );
+        if ( strcount_in != strcount_out )
+            out_printf( "--- %d strings of %d dangling\n", strcount_in -
+                strcount_out, strcount_in );
+    }
+}