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

   1 /*
   2  * Copyright 1993, 1995 Christopher Seiwald.
   3  *
   4  * This file is part of Jam - see jam.c for Copyright information.
   5  */
   6
   7 /*
   8  * lists.c - maintain lists of objects
   9  */
  10
  11 #include "jam.h"
  12 #include "lists.h"
  13 #include "output.h"
  14
  15 #include <assert.h>
  16
  17 static LIST * freelist[ 32 ];  /* junkpile for list_dealloc() */
  18
  19 static unsigned get_bucket( unsigned size )
  20 {
  21     unsigned bucket = 0;
  22     while ( size > ( 1u << bucket ) ) ++bucket;
  23     return bucket;
  24 }
  25
  26 static LIST * list_alloc( unsigned const size )
  27 {
  28     unsigned const bucket = get_bucket( size );
  29     if ( freelist[ bucket ] )
  30     {
  31         LIST * result = freelist[ bucket ];
  32         freelist[ bucket ] = result->impl.next;
  33         return result;
  34     }
  35     return (LIST *)BJAM_MALLOC( sizeof( LIST ) + ( 1u << bucket ) *
  36         sizeof( OBJECT * ) );
  37 }
  38
  39 static void list_dealloc( LIST * l )
  40 {
  41     unsigned size = list_length( l );
  42     unsigned bucket;
  43     LIST * node = l;
  44
  45     if ( size == 0 ) return;
  46
  47     bucket = get_bucket( size );;
  48
  49 #ifdef BJAM_NO_MEM_CACHE
  50     BJAM_FREE( node );
  51 #else
  52     node->impl.next = freelist[ bucket ];
  53     freelist[ bucket ] = node;
  54 #endif
  55 }
  56
  57 /*
  58  * list_append() - append a list onto another one, returning total
  59  */
  60
  61 LIST * list_append( LIST * l, LIST * nl )
  62 {
  63     if ( list_empty( l ) )
  64         return nl;
  65     if ( !list_empty( nl ) )
  66     {
  67         int const l_size = list_length( l );
  68         int const nl_size = list_length( nl );
  69         int const size = l_size + nl_size;
  70         unsigned const bucket = get_bucket( size );
  71
  72         /* Do we need to reallocate? */
  73         if ( l_size <= ( 1u << ( bucket - 1 ) ) )
  74         {
  75             LIST * result = list_alloc( size );
  76             memcpy( list_begin( result ), list_begin( l ), l_size * sizeof(
  77                 OBJECT * ) );
  78             list_dealloc( l );
  79             l = result;
  80         }
  81
  82         l->impl.size = size;
  83         memcpy( list_begin( l ) + l_size, list_begin( nl ), nl_size * sizeof(
  84             OBJECT * ) );
  85         list_dealloc( nl );
  86     }
  87     return l;
  88 }
  89
  90 LISTITER list_begin( LIST * l )
  91 {
  92     return l ? (LISTITER)( (char *)l + sizeof( LIST ) ) : 0;
  93 }
  94
  95 LISTITER list_end( LIST * l )
  96 {
  97     return l ? list_begin( l ) + l->impl.size : 0;
  98 }
  99
 100 LIST * list_new( OBJECT * value )
 101 {
 102     LIST * const head = list_alloc( 1 ) ;
 103     head->impl.size = 1;
 104     list_begin( head )[ 0 ] = value;
 105     return head;
 106 }
 107
 108 /*
 109  * list_push_back() - tack a string onto the end of a list of strings
 110  */
 111
 112 LIST * list_push_back( LIST * head, OBJECT * value )
 113 {
 114     unsigned int size = list_length( head );
 115     unsigned int i;
 116
 117     if ( DEBUG_LISTS )
 118         out_printf( "list > %s <\n", object_str( value ) );
 119
 120     /* If the size is a power of 2, reallocate. */
 121     if ( size == 0 )
 122     {
 123         head = list_alloc( 1 );
 124     }
 125     else if ( ( ( size - 1 ) & size ) == 0 )
 126     {
 127         LIST * l = list_alloc( size + 1 );
 128         memcpy( l, head, sizeof( LIST ) + size * sizeof( OBJECT * ) );
 129         list_dealloc( head );
 130         head = l;
 131     }
 132
 133     list_begin( head )[ size ] = value;
 134     head->impl.size = size + 1;
 135
 136     return head;
 137 }
 138
 139
 140 /*
 141  * list_copy() - copy a whole list of strings (nl) onto end of another (l).
 142  */
 143
 144 LIST * list_copy( LIST * l )
 145 {
 146     int size = list_length( l );
 147     int i;
 148     LIST * result;
 149
 150     if ( size == 0 ) return L0;
 151
 152     result = list_alloc( size );
 153     result->impl.size = size;
 154     for ( i = 0; i < size; ++i )
 155         list_begin( result )[ i ] = object_copy( list_begin( l )[ i ] );
 156     return result;
 157 }
 158
 159
 160 LIST * list_copy_range( LIST * l, LISTITER first, LISTITER last )
 161 {
 162     if ( first == last )
 163         return L0;
 164     else
 165     {
 166         int size = last - first;
 167         LIST * result = list_alloc( size );
 168         LISTITER dest = list_begin( result );
 169         result->impl.size = size;
 170         for ( ; first != last; ++first, ++dest )
 171             *dest = object_copy( *first );
 172         return result;
 173     }
 174 }
 175
 176
 177 /*
 178  * list_sublist() - copy a subset of a list of strings.
 179  */
 180
 181 LIST * list_sublist( LIST * l, int start, int count )
 182 {
 183     int end = start + count;
 184     int size = list_length( l );
 185     if ( start >= size ) return L0;
 186     if ( end > size ) end = size;
 187     return list_copy_range( l, list_begin( l ) + start, list_begin( l ) + end );
 188 }
 189
 190
 191 static int str_ptr_compare( void const * va, void const * vb )
 192 {
 193     OBJECT * a = *( (OBJECT * *)va );
 194     OBJECT * b = *( (OBJECT * *)vb );
 195     return strcmp( object_str( a ), object_str( b ) );
 196 }
 197
 198
 199 LIST * list_sort( LIST * l )
 200 {
 201     int len;
 202     int ii;
 203     LIST * result;
 204
 205     if ( !l )
 206         return L0;
 207
 208     len = list_length( l );
 209     result = list_copy( l );
 210
 211     qsort( list_begin( result ), len, sizeof( OBJECT * ), str_ptr_compare );
 212
 213     return result;
 214 }
 215
 216
 217 /*
 218  * list_free() - free a list of strings
 219  */
 220
 221 void list_free( LIST * head )
 222 {
 223     if ( !list_empty( head ) )
 224     {
 225         LISTITER iter = list_begin( head );
 226         LISTITER const end = list_end( head );
 227         for ( ; iter != end; iter = list_next( iter ) )
 228             object_free( list_item( iter ) );
 229         list_dealloc( head );
 230     }
 231 }
 232
 233
 234 /*
 235  * list_pop_front() - remove the front element from a list of strings
 236  */
 237
 238 LIST * list_pop_front( LIST * l )
 239 {
 240     unsigned size = list_length( l );
 241     assert( size );
 242     --size;
 243     object_free( list_front( l ) );
 244
 245     if ( size == 0 )
 246     {
 247         list_dealloc( l );
 248         return L0;
 249     }
 250
 251     if ( ( ( size - 1 ) & size ) == 0 )
 252     {
 253         LIST * const nl = list_alloc( size );
 254         nl->impl.size = size;
 255         memcpy( list_begin( nl ), list_begin( l ) + 1, size * sizeof( OBJECT * )
 256             );
 257         list_dealloc( l );
 258         return nl;
 259     }
 260
 261     l->impl.size = size;
 262     memmove( list_begin( l ), list_begin( l ) + 1, size * sizeof( OBJECT * ) );
 263     return l;
 264 }
 265
 266 LIST * list_reverse( LIST * l )
 267 {
 268     int size = list_length( l );
 269     if ( size == 0 ) return L0;
 270     {
 271         LIST * const result = list_alloc( size );
 272         int i;
 273         result->impl.size = size;
 274         for ( i = 0; i < size; ++i )
 275             list_begin( result )[ i ] = object_copy( list_begin( l )[ size - i -
 276                 1 ] );
 277         return result;
 278     }
 279 }
 280
 281 int list_cmp( LIST * t, LIST * s )
 282 {
 283     int status = 0;
 284     LISTITER t_it = list_begin( t );
 285     LISTITER const t_end = list_end( t );
 286     LISTITER s_it = list_begin( s );
 287     LISTITER const s_end = list_end( s );
 288
 289     while ( !status && ( t_it != t_end || s_it != s_end ) )
 290     {
 291         char const * st = t_it != t_end ? object_str( list_item( t_it ) ) : "";
 292         char const * ss = s_it != s_end ? object_str( list_item( s_it ) ) : "";
 293
 294         status = strcmp( st, ss );
 295
 296         t_it = t_it != t_end ? list_next( t_it ) : t_it;
 297         s_it = s_it != s_end ? list_next( s_it ) : s_it;
 298     }
 299
 300     return status;
 301 }
 302
 303 int list_is_sublist( LIST * sub, LIST * l )
 304 {
 305     LISTITER iter = list_begin( sub );
 306     LISTITER const end = list_end( sub );
 307     for ( ; iter != end; iter = list_next( iter ) )
 308         if ( !list_in( l, list_item( iter ) ) )
 309             return 0;
 310     return 1;
 311 }
 312
 313 /*
 314  * list_print() - print a list of strings to stdout
 315  */
 316
 317 void list_print( LIST * l )
 318 {
 319     LISTITER iter = list_begin( l ), end = list_end( l );
 320     if ( iter != end )
 321     {
 322         out_printf( "%s", object_str( list_item( iter ) ) );
 323         iter = list_next( iter );
 324         for ( ; iter != end; iter = list_next( iter ) )
 325             out_printf( " %s", object_str( list_item( iter ) ) );
 326     }
 327 }
 328
 329
 330 /*
 331  * list_length() - return the number of items in the list
 332  */
 333
 334 int list_length( LIST * l )
 335 {
 336     return l ? l->impl.size : 0;
 337 }
 338
 339
 340 int list_in( LIST * l, OBJECT * value )
 341 {
 342     LISTITER iter = list_begin( l );
 343     LISTITER end = list_end( l );
 344     for ( ; iter != end; iter = list_next( iter ) )
 345         if ( object_equal( list_item( iter ), value ) )
 346             return 1;
 347     return 0;
 348 }
 349
 350
 351 LIST * list_unique( LIST * sorted_list )
 352 {
 353     LIST * result = L0;
 354     OBJECT * last_added = 0;
 355
 356     LISTITER iter = list_begin( sorted_list ), end = list_end( sorted_list );
 357     for ( ; iter != end; iter = list_next( iter ) )
 358     {
 359         if ( !last_added || !object_equal( list_item( iter ), last_added ) )
 360         {
 361             result = list_push_back( result, object_copy( list_item( iter ) ) );
 362             last_added = list_item( iter );
 363         }
 364     }
 365     return result;
 366 }
 367
 368 void list_done()
 369 {
 370     int i;
 371     for ( i = 0; i < sizeof( freelist ) / sizeof( freelist[ 0 ] ); ++i )
 372     {
 373         LIST * l = freelist[ i ];
 374         while ( l )
 375         {
 376             LIST * const tmp = l;
 377             l = l->impl.next;
 378             BJAM_FREE( tmp );
 379         }
 380     }
 381 }
 382
 383
 384 /*
 385  * lol_init() - initialize a LOL (list of lists).
 386  */
 387
 388 void lol_init( LOL * lol )
 389 {
 390     lol->count = 0;
 391 }
 392
 393
 394 /*
 395  * lol_add() - append a LIST onto an LOL.
 396  */
 397
 398 void lol_add( LOL * lol, LIST * l )
 399 {
 400     if ( lol->count < LOL_MAX )
 401         lol->list[ lol->count++ ] = l;
 402 }
 403
 404
 405 /*
 406  * lol_free() - free the LOL and its LISTs.
 407  */
 408
 409 void lol_free( LOL * lol )
 410 {
 411     int i;
 412     for ( i = 0; i < lol->count; ++i )
 413         list_free( lol->list[ i ] );
 414     lol->count = 0;
 415 }
 416
 417
 418 /*
 419  * lol_get() - return one of the LISTs in the LOL.
 420  */
 421
 422 LIST * lol_get( LOL * lol, int i )
 423 {
 424     return i < lol->count ? lol->list[ i ] : L0;
 425 }
 426
 427
 428 /*
 429  * lol_print() - debug print LISTS separated by ":".
 430  */
 431
 432 void lol_print( LOL * lol )
 433 {
 434     int i;
 435     for ( i = 0; i < lol->count; ++i )
 436     {
 437         if ( i )
 438             out_printf( " : " );
 439         list_print( lol->list[ i ] );
 440     }
 441 }
 442
 443 #ifdef HAVE_PYTHON
 444
 445 PyObject * list_to_python( LIST * l )
 446 {
 447     PyObject * result = PyList_New( 0 );
 448     LISTITER iter = list_begin( l );
 449     LISTITER const end = list_end( l );
 450     for ( ; iter != end; iter = list_next( iter ) )
 451     {
 452         PyObject * s = PyString_FromString( object_str( list_item( iter ) ) );
 453         PyList_Append( result, s );
 454         Py_DECREF( s );
 455     }
 456
 457     return result;
 458 }
 459
 460 LIST * list_from_python( PyObject * l )
 461 {
 462     LIST * result = L0;
 463
 464     Py_ssize_t n = PySequence_Size( l );
 465     Py_ssize_t i;
 466     for ( i = 0; i < n; ++i )
 467     {
 468         PyObject * v = PySequence_GetItem( l, i );
 469         result = list_push_back( result, object_new( PyString_AsString( v ) ) );
 470         Py_DECREF( v );
 471     }
 472
 473     return result;
 474 }
 475
 476 #endif