[ceph.git] / ceph / src / boost / tools / build / src / engine / object.cpp

/*
 * 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 );
    }
}
Commit	Line	Data
7c673cae FG	1	/*
	2	* Copyright 1993, 1995 Christopher Seiwald.
	3	* Copyright 2011 Steven Watanabe
	4	*
	5	* This file is part of Jam - see jam.c for Copyright information.
	6	*/
	7
	8	/*
	9	* object.c - object manipulation routines
	10	*
	11	* External functions:
	12	* object_new() - create an object from a string
	13	* object_new_range() - create an object from a string of given length
	14	* object_copy() - return a copy of an object
	15	* object_free() - free an object
	16	* object_str() - get the string value of an object
	17	* object_done() - free string tables
	18	*
	19	* This implementation builds a hash table of all strings, so that multiple
	20	* calls of object_new() on the same string allocate memory for the string once.
	21	* Strings are never actually freed.
	22	*/
	23
	24	#include "jam.h"
	25	#include "object.h"
	26	#include "output.h"
	27
	28	#include <assert.h>
	29	#include <stddef.h>
	30	#include <stdlib.h>
	31
	32
	33	#define OBJECT_MAGIC 0xa762e0e3u
	34
	35	#ifndef object_copy
	36
	37	struct hash_header
	38	{
	39	#ifndef NDEBUG
	40	unsigned int magic;
	41	#endif
	42	unsigned int hash;
	43	struct hash_item * next;
	44	};
	45
	46	#endif
	47
	48	struct hash_item
	49	{
	50	struct hash_header header;
	51	char data[ 1 ];
	52	};
	53
	54	#define ALLOC_ALIGNMENT (sizeof(struct hash_item) - sizeof(struct hash_header))
	55
	56	typedef struct string_set
	57	{
1e59de90 TL	58	int32_t num;
1e59de90 TL	59	int32_t size;
7c673cae FG	60	struct hash_item * * data;
	61	} string_set;
	62
1e59de90	63	#if !defined(BJAM_NO_MEM_CACHE) \|\| (BJAM_NO_MEM_CACHE == 0)
7c673cae	64	static string_set strhash;
1e59de90 TL	65	#endif
	66	static int32_t strtotal = 0;
	67	static int32_t strcount_in = 0;
	68	static int32_t strcount_out = 0;
7c673cae FG	69
	70
	71	/*
	72	* Immortal string allocator implementation speeds string allocation and cuts
	73	* down on internal fragmentation.
	74	*/
	75
	76	#define STRING_BLOCK 4096
	77	typedef struct strblock
	78	{
	79	struct strblock * next;
	80	char data[ STRING_BLOCK ];
	81	} strblock;
	82
	83	static strblock * strblock_chain = 0;
	84
1e59de90	85	#if !defined(BJAM_NO_MEM_CACHE) \|\| (BJAM_NO_MEM_CACHE == 0)
7c673cae FG	86	/* Storage remaining in the current strblock */
	87	static char * storage_start = 0;
	88	static char * storage_finish = 0;
	89
	90
	91	/*
	92	* allocate() - Allocate n bytes of immortal string storage.
	93	*/
	94
1e59de90	95	static char * allocate( int32_t n )
7c673cae FG	96	{
	97	#ifdef BJAM_NEWSTR_NO_ALLOCATE
	98	return (char *)BJAM_MALLOC( n );
	99	#else
	100	/* See if we can grab storage from an existing block. */
1e59de90	101	int32_t remaining = int32_t(storage_finish - storage_start);
7c673cae FG	102	n = ( ( n + ALLOC_ALIGNMENT - 1 ) / ALLOC_ALIGNMENT ) * ALLOC_ALIGNMENT;
	103	if ( remaining >= n )
	104	{
	105	char * result = storage_start;
	106	storage_start += n;
	107	return result;
	108	}
	109	else /* Must allocate a new block. */
	110	{
	111	strblock * new_block;
1e59de90	112	int32_t nalloc = n;
7c673cae FG	113	if ( nalloc < STRING_BLOCK )
	114	nalloc = STRING_BLOCK;
	115
	116	/* Allocate a new block and link into the chain. */
	117	new_block = (strblock *)BJAM_MALLOC( offsetof( strblock, data[ 0 ] ) +
1e59de90	118	size_t(nalloc) * sizeof( new_block->data[ 0 ] ) );
7c673cae FG	119	if ( new_block == 0 )
	120	return 0;
	121	new_block->next = strblock_chain;
	122	strblock_chain = new_block;
	123
	124	/* Take future allocations out of the larger remaining space. */
	125	if ( remaining < nalloc - n )
	126	{
	127	storage_start = new_block->data + n;
	128	storage_finish = new_block->data + nalloc;
	129	}
	130	return new_block->data;
	131	}
	132	#endif
	133	}
1e59de90	134	#endif
7c673cae FG	135
7c673cae FG	136
1e59de90	137	static unsigned int hash_keyval( char const * key, int32_t size )
7c673cae FG	138	{
	139	unsigned int const magic = 2147059363;
	140	unsigned int hash = 0;
	141
	142	unsigned int i;
	143	for ( i = 0; i < size / sizeof( unsigned int ); ++i )
	144	{
	145	unsigned int val;
	146	memcpy( &val, key, sizeof( unsigned int ) );
	147	hash = hash * magic + val;
	148	key += sizeof( unsigned int );
	149	}
	150
	151	{
	152	unsigned int val = 0;
	153	memcpy( &val, key, size % sizeof( unsigned int ) );
	154	hash = hash * magic + val;
	155	}
	156
	157	return hash + ( hash >> 17 );
	158	}
	159
	160
1e59de90	161	#if !defined(BJAM_NO_MEM_CACHE) \|\| (BJAM_NO_MEM_CACHE == 0)
7c673cae FG	162	static void string_set_init( string_set * set )
	163	{
	164	set->size = 0;
	165	set->num = 4;
	166	set->data = (struct hash_item * )BJAM_MALLOC( set->num sizeof( struct hash_item * ) );
	167	memset( set->data, 0, set->num * sizeof( struct hash_item * ) );
	168	}
	169
	170
	171	static void string_set_done( string_set * set )
	172	{
	173	BJAM_FREE( set->data );
	174	}
	175
	176
	177	static void string_set_resize( string_set * set )
	178	{
7c673cae FG	179	string_set new_set;
	180	new_set.num = set->num * 2;
	181	new_set.size = set->size;
	182	new_set.data = (struct hash_item * )BJAM_MALLOC( sizeof( struct hash_item
	183	) * new_set.num );
	184	memset( new_set.data, 0, sizeof( struct hash_item * ) * new_set.num );
1e59de90	185	for ( int32_t i = 0; i < set->num; ++i )
7c673cae FG	186	{
	187	while ( set->data[ i ] )
	188	{
	189	struct hash_item * temp = set->data[ i ];
	190	unsigned pos = temp->header.hash % new_set.num;
	191	set->data[ i ] = temp->header.next;
	192	temp->header.next = new_set.data[ pos ];
	193	new_set.data[ pos ] = temp;
	194	}
	195	}
	196	BJAM_FREE( set->data );
	197	*set = new_set;
	198	}
	199
	200
	201	static char const * string_set_insert( string_set * set, char const * string,
1e59de90	202	int32_t const size )
7c673cae FG	203	{
	204	unsigned hash = hash_keyval( string, size );
	205	unsigned pos = hash % set->num;
	206
	207	struct hash_item * result;
	208
	209	for ( result = set->data[ pos ]; result; result = result->header.next )
	210	if ( !strncmp( result->data, string, size ) && !result->data[ size ] )
	211	return result->data;
	212
	213	if ( set->size >= set->num )
	214	{
	215	string_set_resize( set );
	216	pos = hash % set->num;
	217	}
	218
	219	result = (struct hash_item *)allocate( sizeof( struct hash_header ) + size +
	220	1 );
	221	result->header.hash = hash;
	222	result->header.next = set->data[ pos ];
	223	#ifndef NDEBUG
	224	result->header.magic = OBJECT_MAGIC;
	225	#endif
	226	memcpy( result->data, string, size );
	227	result->data[ size ] = '\0';
	228	assert( hash_keyval( result->data, size ) == result->header.hash );
	229	set->data[ pos ] = result;
	230	strtotal += size + 1;
	231	++set->size;
	232
	233	return result->data;
	234	}
1e59de90	235	#endif
7c673cae FG	236
	237
	238	/*
	239	* object_new_range() - create an object from a string of given length
	240	*/
	241
1e59de90	242	OBJECT * object_new_range( char const * const string, int32_t size )
7c673cae FG	243	{
	244	++strcount_in;
	245
	246	#ifdef BJAM_NO_MEM_CACHE
	247	{
	248	struct hash_item * const m = (struct hash_item *)BJAM_MALLOC( sizeof(
	249	struct hash_header ) + size + 1 );
	250	strtotal += size + 1;
	251	memcpy( m->data, string, size );
	252	m->data[ size ] = '\0';
	253	#ifndef NDEBUG
	254	m->header.magic = OBJECT_MAGIC;
	255	#endif
	256	return (OBJECT *)m->data;
	257	}
	258	#else
	259	if ( !strhash.data )
	260	string_set_init( &strhash );
	261	return (OBJECT *)string_set_insert( &strhash, string, size );
	262	#endif
	263	}
	264
	265
	266	/*
	267	* object_new() - create an object from a string
	268	*/
	269
	270	OBJECT * object_new( char const * const string )
	271	{
1e59de90	272	return object_new_range( string, int32_t(strlen( string )) );
7c673cae FG	273	}
	274
	275
	276	#ifndef object_copy
	277
1e59de90 TL	278	static struct hash_item * object_get_item( OBJECT * obj )
	279	{
	280	return (struct hash_item )( (char )obj - offsetof( struct hash_item, data
	281	) );
	282	}
	283
	284
	285	static void object_validate( OBJECT * obj )
	286	{
	287	assert( obj );
	288	assert( object_get_item( obj )->header.magic == OBJECT_MAGIC );
	289	}
	290
	291
7c673cae FG	292	/*
	293	* object_copy() - return a copy of an object
	294	*/
	295
	296	OBJECT * object_copy( OBJECT * obj )
	297	{
	298	object_validate( obj );
	299	#ifdef BJAM_NO_MEM_CACHE
	300	return object_new( object_str( obj ) );
	301	#else
	302	++strcount_in;
	303	return obj;
	304	#endif
	305	}
	306
	307
	308	/*
	309	* object_free() - free an object
	310	*/
	311
	312	void object_free( OBJECT * obj )
	313	{
	314	object_validate( obj );
	315	#ifdef BJAM_NO_MEM_CACHE
	316	BJAM_FREE( object_get_item( obj ) );
	317	#endif
	318	++strcount_out;
	319	}
	320
	321
	322	/*
	323	* object_str() - return the OBJECT's internal C string
	324	*/
	325
	326	char const * object_str( OBJECT * obj )
	327	{
	328	object_validate( obj );
	329	return (char const *)obj;
	330	}
	331
	332
	333	/*
	334	* object_equal() - compare two objects
	335	*/
	336
	337	int object_equal( OBJECT * lhs, OBJECT * rhs )
	338	{
	339	object_validate( lhs );
	340	object_validate( rhs );
	341	#ifdef BJAM_NO_MEM_CACHE
	342	return !strcmp( object_str( lhs ), object_str( rhs ) );
	343	#else
	344	assert( ( lhs == rhs ) == !strcmp( object_str( lhs ), object_str( rhs ) ) );
	345	return lhs == rhs;
	346	#endif
	347	}
	348
	349
	350	/*
	351	* object_hash() - returns the hash value of an object
	352	*/
	353
	354	unsigned int object_hash( OBJECT * obj )
	355	{
356	object_validate( obj );
357	#ifdef BJAM_NO_MEM_CACHE
358	return hash_keyval( object_str( obj ), strlen( object_str( obj ) ) );
359	#else
360	return object_get_item( obj )->header.hash;
361	#endif
362	}
363
364	#endif
365
366	/*
367	* object_done() - free string tables.
368	*/
369
370	void object_done()
371	{
372	#ifdef BJAM_NEWSTR_NO_ALLOCATE
373	unsigned i;
374	for ( i = 0; i < strhash.num; ++i )
375	{
376	while ( strhash.data[ i ] )
377	{
378	struct hash_item * item = strhash.data[ i ];
379	strhash.data[ i ] = item->header.next;
380	BJAM_FREE( item );
381	}
382	}
383	#else
384	/* Reclaim string blocks. */
385	while ( strblock_chain )
386	{
387	strblock * const n = strblock_chain->next;
388	BJAM_FREE( strblock_chain );
389	strblock_chain = n;
390	}
391	#endif
392
1e59de90	393	#if !defined(BJAM_NO_MEM_CACHE) \|\| (BJAM_NO_MEM_CACHE == 0)
7c673cae	394	string_set_done( &strhash );
1e59de90	395	#endif
7c673cae FG	396
	397	if ( DEBUG_MEM )
	398	{
	399	out_printf( "%dK in strings\n", strtotal / 1024 );
	400	if ( strcount_in != strcount_out )
	401	out_printf( "--- %d strings of %d dangling\n", strcount_in -
	402	strcount_out, strcount_in );
	403	}
	404	}