diff options
Diffstat (limited to '')
-rw-r--r-- | src/boost/tools/build/src/engine/object.cpp | 404 |
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 ); + } +} |