tools/build/src/engine/lists.c

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