ceph/src/boost/tools/build/src/engine/object.cpp

   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 {
  58     int32_t num;
  59     int32_t size;
  60     struct hash_item * * data;
  61 } string_set;
  62
  63 #if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
  64 static string_set strhash;
  65 #endif
  66 static int32_t strtotal = 0;
  67 static int32_t strcount_in = 0;
  68 static int32_t strcount_out = 0;
  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
  85 #if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
  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
  95 static char * allocate( int32_t n )
  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. */
 101     int32_t remaining = int32_t(storage_finish - storage_start);
 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;
 112         int32_t nalloc = n;
 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 ] ) +
 118             size_t(nalloc) * sizeof( new_block->data[ 0 ] ) );
 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 }
 134 #endif
 135
 136
 137 static unsigned int hash_keyval( char const * key, int32_t size )
 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
 161 #if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
 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 {
 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 );
 185     for ( int32_t i = 0; i < set->num; ++i )
 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,
 202     int32_t const size )
 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 }
 235 #endif
 236
 237
 238 /*
 239  * object_new_range() - create an object from a string of given length
 240  */
 241
 242 OBJECT * object_new_range( char const * const string, int32_t size )
 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 {
 272     return object_new_range( string, int32_t(strlen( string )) );
 273 }
 274
 275
 276 #ifndef object_copy
 277
 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
 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
 393 #if !defined(BJAM_NO_MEM_CACHE) || (BJAM_NO_MEM_CACHE == 0)
 394     string_set_done( &strhash );
 395 #endif
 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 }