1 files changed, 292 insertions, 105 deletions

diff --git a/tools/build/v2/engine/lists.c b/tools/build/v2/engine/lists.c
index ebabb63e90..c93fd7c090 100644
--- a/tools/build/v2/engine/lists.c
+++ b/tools/build/v2/engine/lists.c
@@ -5,27 +5,65 @@
  */
 
 # include "jam.h"
-# include "newstr.h"
+# include "object.h"
 # include "lists.h"
+# include "assert.h"
 
 /*
- * lists.c - maintain lists of strings
- *
- * This implementation essentially uses a singly linked list, but
- * guarantees that the head element of every list has a valid pointer
- * to the tail of the list, so the new elements can efficiently and
- * properly be appended to the end of a list.
- *
- * To avoid massive allocation, list_free() just tacks the whole freed
- * chain onto freelist and list_new() looks on freelist first for an
- * available list struct.  list_free() does not free the strings in the
- * chain: it lazily lets list_new() do so.
+ * lists.c - maintain lists of objects
  *
  * 08/23/94 (seiwald) - new list_append()
  * 09/07/00 (seiwald) - documented lol_*() functions
  */
 
-static LIST *freelist = 0;  /* junkpile for list_free() */
+struct freelist_node { struct freelist_node *next; };
+
+static struct freelist_node *freelist[32];  /* junkpile for list_free() */
+
+static unsigned get_bucket( unsigned size )
+{
+    unsigned bucket = 0;
+    while ( size > ( 1u << bucket ) ) ++bucket;
+    return bucket;
+}
+
+static LIST * list_alloc( unsigned size )
+{
+    unsigned bucket = get_bucket( size );
+    if ( freelist[ bucket ] )
+    {
+        struct freelist_node * result = freelist[ bucket ];
+        freelist[ bucket ] = result->next;
+        return (LIST *)result;
+    }
+    else
+    {
+        return (LIST *)BJAM_MALLOC( sizeof( LIST ) + ( 1u << bucket ) * sizeof( OBJECT * ) );
+    }
+}
+
+static void list_dealloc( LIST * l )
+{
+    unsigned size = list_length( l );
+    unsigned bucket;
+    struct freelist_node * node = (struct freelist_node *)l;
+
+    if ( size == 0 ) return;
+
+    bucket = get_bucket( size );;
+
+#ifdef BJAM_NO_MEM_CACHE
+
+    BJAM_FREE( node );
+
+#else
+
+    node->next = freelist[ bucket ];
+    freelist[ bucket ] = node;
+
+#endif
+
+}
 
 /*
  * list_append() - append a list onto another one, returning total
@@ -33,60 +71,104 @@ static LIST *freelist = 0;  /* junkpile for list_free() */
 
 LIST * list_append( LIST * l, LIST * nl )
 {
-    if ( !nl )
+    if ( list_empty( nl ) )
     {
         /* Just return l */
     }
-    else if ( !l )
+    else if ( list_empty( l ) )
     {
         l = nl;
     }
     else
     {
-        /* Graft two non-empty lists. */
-        l->tail->next = nl;
-        l->tail = nl->tail;
+        int l_size = list_length( l );
+        int nl_size = list_length( nl );
+        int size = l_size + nl_size;
+        unsigned bucket;
+        int i;
+
+        bucket = get_bucket( size );
+        /* Do we need to reallocate? */
+        if ( l_size <= ( 1u << (bucket - 1) ) )
+        {
+            LIST * result = list_alloc( size );
+            memcpy( list_begin( result ), list_begin( l ), l_size * sizeof( OBJECT * ) );
+            list_dealloc( l );
+            l = result;
+        }
+
+        l->impl.size = size;
+        memcpy( list_begin( l ) + l_size, list_begin( nl ), nl_size *  sizeof( OBJECT * ) );
+        list_dealloc( nl );
+        return l;
     }
 
     return l;
 }
 
+LISTITER list_begin( LIST * l )
+{
+    if ( l )
+        return (LISTITER)( (char *)l + sizeof(LIST) );
+    else
+        return 0;
+}
+
+LISTITER list_end( LIST * l )
+{
+    if ( l )
+        return list_begin( l ) + l->impl.size;
+    else
+        return 0;
+}
+
+LIST * list_new( OBJECT * value )
+{   
+    LIST * head;
+    if ( freelist[ 0 ] )
+    {
+        struct freelist_node * result = freelist[ 0 ];
+        freelist[ 0 ] = result->next;
+        head = (LIST *)result;
+    }
+    else
+    {
+        head = BJAM_MALLOC( sizeof( LIST * ) + sizeof( OBJECT * ) );
+    }
+
+    head->impl.size = 1;
+    list_begin( head )[ 0 ] = value;
+
+    return head;
+}
+
 /*
- * list_new() - tack a string onto the end of a list of strings
+ * list_push_back() - tack a string onto the end of a list of strings
  */
 
-LIST * list_new( LIST * head, char * string )
+LIST * list_push_back( LIST * head, OBJECT * value )
 {
-    LIST * l;
+    unsigned int size = list_length( head );
+    unsigned int i;
 
     if ( DEBUG_LISTS )
-        printf( "list > %s <\n", string );
+        printf( "list > %s <\n", object_str( value ) );
 
-    /* Get list struct from freelist, if one available.  */
-    /* Otherwise allocate. */
-    /* If from freelist, must free string first */
-
-    if ( freelist )
+    /* If the size is a power of 2, reallocate. */
+    if ( size == 0 )
     {
-        l = freelist;
-        freestr( l->string );
-        freelist = freelist->next;
+        head = list_alloc( 1 );
     }
-    else
+    else if ( ( ( size - 1 ) & size ) == 0 )
     {
-        l = (LIST *)BJAM_MALLOC( sizeof( LIST ) );
+        LIST * l = list_alloc( size + 1 );
+        memcpy( l, head, sizeof( LIST ) + size * sizeof( OBJECT * ) );
+        list_dealloc( head );
+        head = l;
     }
 
-    /* If first on chain, head points here. */
-    /* If adding to chain, tack us on. */
-    /* Tail must point to this new, last element. */
-
-    if ( !head ) head = l;
-    else head->tail->next = l;
-    head->tail = l;
-    l->next = 0;
-
-    l->string = string;
+    list_begin( head )[ size ] = value;
+    head->impl.size = size + 1;
 
     return head;
 }
@@ -96,11 +178,42 @@ LIST * list_new( LIST * head, char * string )
  * list_copy() - copy a whole list of strings (nl) onto end of another (l).
  */
 
-LIST * list_copy( LIST * l, LIST * nl )
+LIST * list_copy( LIST * l )
 {
-    for ( ; nl; nl = list_next( nl ) )
-        l = list_new( l, copystr( nl->string ) );
-    return l;
+    int size = list_length( l );
+    int i;
+    LIST * result;
+
+    if ( size == 0 ) return L0;
+
+    result = list_alloc( size );
+    result->impl.size = size;
+    for ( i = 0; i < size; ++i )
+    {
+        list_begin( result )[ i ] = object_copy( list_begin( l )[ i ] );
+    }
+    return result;
+}
+
+
+LIST * list_copy_range( LIST *l, LISTITER first, LISTITER last )
+{
+    if ( first == last )
+    {
+        return L0;
+    }
+    else
+    {
+        int size = last - first;
+        LIST * result = list_alloc( size );
+        LISTITER dest = list_begin( result );
+        result->impl.size = size;
+        for ( ; first != last; ++first, ++dest )
+        {
+            *dest = object_copy( *first );
+        }
+        return result;
+    }
 }
 
 
@@ -110,19 +223,19 @@ LIST * list_copy( LIST * l, LIST * nl )
 
 LIST * list_sublist( LIST * l, int start, int count )
 {
-    LIST * nl = 0;
-    for ( ; l && start--; l = list_next( l ) );
-    for ( ; l && count--; l = list_next( l ) )
-        nl = list_new( nl, copystr( l->string ) );
-    return nl;
+    int end = start + count;
+    int size = list_length( l );
+    if ( start >= size ) return L0;
+    if ( end > size ) end = size;
+    return list_copy_range( l, list_begin( l ) + start, list_begin( l ) + end );
 }
 
 
 static int str_ptr_compare( void const * va, void const * vb )
 {
-    char * a = *( (char * *)va );
-    char * b = *( (char * *)vb );
-    return strcmp(a, b);
+    OBJECT * a = *( (OBJECT * *)va );
+    OBJECT * b = *( (OBJECT * *)vb );
+    return strcmp(object_str(a), object_str(b));
 }
 
 
@@ -130,29 +243,15 @@ LIST * list_sort( LIST * l )
 {
     int len;
     int ii;
-    char * * strings;
-    LIST * listp;
-    LIST * result = 0;
+    LIST * result;
 
     if ( !l )
         return L0;
 
     len = list_length( l );
-    strings = (char * *)BJAM_MALLOC( len * sizeof(char*) );
-
-    listp = l;
-    for ( ii = 0; ii < len; ++ii )
-    {
-        strings[ ii ] = listp->string;
-        listp = listp->next;
-    }
-
-    qsort( strings, len, sizeof( char * ), str_ptr_compare );
+    result = list_copy( l );
 
-    for ( ii = 0; ii < len; ++ii )
-        result = list_append( result, list_new( 0, strings[ ii ] ) );
-
-    BJAM_FREE( strings );
+    qsort( list_begin( result ), len, sizeof( OBJECT * ), str_ptr_compare );
 
     return result;
 }
@@ -164,11 +263,14 @@ LIST * list_sort( LIST * l )
 
 void list_free( LIST * head )
 {
-    /* Just tack onto freelist. */
-    if ( head )
+    if ( !list_empty( head ) )
     {
-        head->tail->next = freelist;
-        freelist = head;
+        LISTITER iter = list_begin( head ), end = list_end( head );
+        for ( ; iter != end; iter = list_next( iter ) )
+        {
+            object_free( list_item( iter ) );
+        }
+        list_dealloc( head );
     }
 }
 
@@ -179,17 +281,79 @@ void list_free( LIST * head )
 
 LIST * list_pop_front( LIST * l )
 {
-    LIST * result = l->next;
-    if ( result )
+    unsigned size = list_length( l );
+    assert( size != 0 );
+    --size;
+    object_free( list_front( l ) );
+
+    if ( size == 0 )
     {
-        result->tail = l->tail;
-        l->next = L0;
-        l->tail = l;
+        list_dealloc( l );
+        return L0;
+    }
+    else if ( ( ( size - 1 ) & size ) == 0 )
+    {
+        LIST * nl = list_alloc( size );
+        nl->impl.size = size;
+        memcpy( list_begin( nl ), list_begin( l ) + 1, size * sizeof( OBJECT * ) );
+        list_dealloc( l );
+        return nl;
+    }
+    else
+    {
+        l->impl.size = size;
+        memmove( list_begin( l ), list_begin( l ) + 1, size * sizeof( OBJECT * ) );
+        return l;
+    }
+}
+
+LIST *  list_reverse( LIST * l )
+{
+    int size = list_length( l );
+    if ( size == 0 ) return L0;
+    else
+    {
+        LIST * result = list_alloc( size );
+        int i;
+        result->impl.size = size;
+        for ( i = 0; i < size; ++i )
+        {
+            list_begin( result )[ i ] = object_copy( list_begin( l )[ size - i - 1 ] );
+        }
+        return result;
     }
-    list_free( l );
-    return result;
 }
 
+int list_cmp( LIST * t, LIST * s )
+{
+    int status = 0;
+    LISTITER t_it = list_begin( t ), t_end = list_end( t );
+    LISTITER s_it = list_begin( s ), s_end = list_end( s );
+
+    while ( !status && ( t_it != t_end || s_it != s_end ) )
+    {
+        const char *st = t_it != t_end ? object_str( list_item( t_it ) ) : "";
+        const char *ss = s_it != s_end ? object_str( list_item( s_it ) ) : "";
+
+        status = strcmp( st, ss );
+
+        t_it = t_it != t_end ? list_next( t_it ) : t_it;
+        s_it = s_it != s_end ? list_next( s_it ) : s_it;
+    }
+
+    return status;
+}
+
+int list_is_sublist( LIST * sub, LIST * l )
+{
+    LISTITER iter = list_begin( sub ), end = list_end( sub );
+    for ( ; iter != end; iter = list_next( iter ) )
+    {
+        if ( !list_in( l, list_item( iter ) ) )
+            return 0;
+    }
+    return 1;
+}
 
 /*
  * list_print() - print a list of strings to stdout
@@ -197,12 +361,14 @@ LIST * list_pop_front( LIST * l )
 
 void list_print( LIST * l )
 {
-    LIST * p = 0;
-    for ( ; l; p = l, l = list_next( l ) )
-        if ( p )
-            printf( "%s ", p->string );
-    if ( p )
-        printf( "%s", p->string );
+    LISTITER iter = list_begin( l ), end = list_end( l );
+    if ( iter != end )
+    {
+        printf( "%s", object_str( list_item( iter ) ) );
+        iter = list_next( iter );
+        for ( ; iter != end; iter = list_next( iter ) )
+            printf( " %s", object_str( list_item( iter ) ) );
+    }
 }
 
 
@@ -212,16 +378,18 @@ void list_print( LIST * l )
 
 int list_length( LIST * l )
 {
-    int n = 0;
-    for ( ; l; l = list_next( l ), ++n );
-    return n;
+    if ( l )
+        return l->impl.size;
+    else
+        return 0;
 }
 
 
-int list_in( LIST * l, char * value )
+int list_in( LIST * l, OBJECT * value )
 {
-    for ( ; l; l = l->next )
-        if ( strcmp( l->string, value ) == 0 )
+    LISTITER iter = list_begin( l ), end = list_end( l );
+    for ( ; iter != end; iter = list_next( iter ) )
+        if ( object_equal( list_item( iter ), value ) )
             return 1;
     return 0;
 }
@@ -229,20 +397,38 @@ int list_in( LIST * l, char * value )
 
 LIST * list_unique( LIST * sorted_list )
 {
-    LIST * result = 0;
-    LIST * last_added = 0;
+    LIST * result = L0;
+    OBJECT * last_added = 0;
 
-    for ( ; sorted_list; sorted_list = sorted_list->next )
+    LISTITER iter = list_begin( sorted_list ), end = list_end( sorted_list );
+    for ( ; iter != end; iter = list_next( iter ) )
     {
-        if ( !last_added || strcmp( sorted_list->string, last_added->string ) != 0 )
+        if ( !last_added || !object_equal( list_item( iter ), last_added ) )
         {
-            result = list_new( result, sorted_list->string );
-            last_added = sorted_list;
+            result = list_push_back( result, object_copy( list_item( iter ) ) );
+            last_added = list_item( iter );
         }
     }
     return result;
 }
 
+void list_done()
+{
+    int i;
+    int total = 0;
+    for ( i = 0; i < sizeof( freelist ) / sizeof( freelist[ 0 ] ); ++i )
+    {
+        struct freelist_node *l, *tmp;
+        int bytes;
+        for( l = freelist[ i ]; l;  )
+        {
+            tmp = l;
+            l = l->next;
+            BJAM_FREE( tmp );
+        }
+    }
+}
+
 
 /*
  * lol_init() - initialize a LOL (list of lists).
@@ -284,7 +470,7 @@ void lol_free( LOL * lol )
 
 LIST * lol_get( LOL * lol, int i )
 {
-    return i < lol->count ? lol->list[ i ] : 0;
+    return i < lol->count ? lol->list[ i ] : L0;
 }
 
 
@@ -309,10 +495,11 @@ void lol_print( LOL * lol )
 PyObject *list_to_python(LIST *l)
 {
     PyObject *result = PyList_New(0);
+    LISTITER iter = list_begin( l ), end = list_end( l );
 
-    for (; l; l = l->next)
+    for (; iter != end; iter = list_next( iter ) )
     {
-        PyObject* s = PyString_FromString(l->string);
+        PyObject* s = PyString_FromString(object_str(list_item(iter)));
         PyList_Append(result, s);
         Py_DECREF(s);
     }
@@ -322,14 +509,14 @@ PyObject *list_to_python(LIST *l)
 
 LIST *list_from_python(PyObject *l)
 {
-    LIST * result = 0;
+    LIST * result = L0;
 
     Py_ssize_t i, n;
     n = PySequence_Size(l);
     for (i = 0; i < n; ++i)
     {
         PyObject *v = PySequence_GetItem(l, i);        
-        result = list_new (result, newstr (PyString_AsString(v)));
+        result = list_push_back(result, object_new (PyString_AsString(v)));
         Py_DECREF(v);
     }