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

/*
 * Copyright 1993, 1995 Christopher Seiwald.
 *
 * This file is part of Jam - see jam.c for Copyright information.
 */

/*
 * lists.c - maintain lists of objects
 */

#include "jam.h"
#include "lists.h"
#include "output.h"

#include <assert.h>

static LIST * freelist[ 32 ];  /* junkpile for list_dealloc() */

static unsigned get_bucket( unsigned size )
{
    unsigned bucket = 0;
    while ( size > ( 1u << bucket ) ) ++bucket;
    return bucket;
}

static LIST * list_alloc( unsigned const size )
{
    unsigned const bucket = get_bucket( size );
    if ( freelist[ bucket ] )
    {
        LIST * result = freelist[ bucket ];
        freelist[ bucket ] = result->impl.next;
        return result;
    }
    return (LIST *)BJAM_MALLOC( sizeof( LIST ) + ( 1u << bucket ) *
        sizeof( OBJECT * ) );
}

static void list_dealloc( LIST * l )
{
    unsigned size = list_length( l );
    unsigned bucket;
    LIST * node = l;

    if ( size == 0 ) return;

    bucket = get_bucket( size );;

#ifdef BJAM_NO_MEM_CACHE
    BJAM_FREE( node );
#else
    node->impl.next = freelist[ bucket ];
    freelist[ bucket ] = node;
#endif
}

/*
 * list_append() - append a list onto another one, returning total
 */

LIST * list_append( LIST * l, LIST * nl )
{
    if ( list_empty( l ) )
        return nl;
    if ( !list_empty( nl ) )
    {
        unsigned int const l_size = list_length( l );
        int const nl_size = list_length( nl );
        int const size = l_size + nl_size;
        unsigned const 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;
}

LISTITER list_begin( LIST * l )
{
    return l ? (LISTITER)( (char *)l + sizeof( LIST ) ) : 0;
}

LISTITER list_end( LIST * l )
{
    return l ? list_begin( l ) + l->impl.size : 0;
}

LIST * list_new( OBJECT * value )
{
    LIST * const head = list_alloc( 1 ) ;
    head->impl.size = 1;
    list_begin( head )[ 0 ] = value;
    return head;
}

/*
 * list_push_back() - tack a string onto the end of a list of strings
 */

LIST * list_push_back( LIST * head, OBJECT * value )
{
    unsigned int size = list_length( head );

    if ( DEBUG_LISTS )
        out_printf( "list > %s <\n", object_str( value ) );

    /* If the size is a power of 2, reallocate. */
    if ( size == 0 )
    {
        head = list_alloc( 1 );
    }
    else if ( ( ( size - 1 ) & size ) == 0 )
    {
        LIST * l = list_alloc( size + 1 );
        memcpy( l, head, sizeof( LIST ) + size * sizeof( OBJECT * ) );
        list_dealloc( head );
        head = l;
    }

    list_begin( head )[ size ] = value;
    head->impl.size = size + 1;

    return head;
}


/*
 * list_copy() - copy a whole list of strings (nl) onto end of another (l).
 */

LIST * list_copy( LIST * 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;
    }
}


/*
 * list_sublist() - copy a subset of a list of strings.
 */

LIST * list_sublist( LIST * l, int start, int count )
{
    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 )
{
    OBJECT * a = *( (OBJECT * *)va );
    OBJECT * b = *( (OBJECT * *)vb );
    return strcmp( object_str( a ), object_str( b ) );
}


LIST * list_sort( LIST * l )
{
    int len;
    LIST * result;

    if ( !l )
        return L0;

    len = list_length( l );
    result = list_copy( l );

    qsort( list_begin( result ), len, sizeof( OBJECT * ), str_ptr_compare );

    return result;
}


/*
 * list_free() - free a list of strings
 */

void list_free( LIST * head )
{
    if ( !list_empty( head ) )
    {
        LISTITER iter = list_begin( head );
        LISTITER const end = list_end( head );
        for ( ; iter != end; iter = list_next( iter ) )
            object_free( list_item( iter ) );
        list_dealloc( head );
    }
}


/*
 * list_pop_front() - remove the front element from a list of strings
 */

LIST * list_pop_front( LIST * l )
{
    unsigned size = list_length( l );
    assert( size );
    --size;
    object_free( list_front( l ) );

    if ( size == 0 )
    {
        list_dealloc( l );
        return L0;
    }

    if ( ( ( size - 1 ) & size ) == 0 )
    {
        LIST * const nl = list_alloc( size );
        nl->impl.size = size;
        memcpy( list_begin( nl ), list_begin( l ) + 1, size * sizeof( OBJECT * )
            );
        list_dealloc( l );
        return nl;
    }

    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;
    {
        LIST * const 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;
    }
}

int list_cmp( LIST * t, LIST * s )
{
    int status = 0;
    LISTITER t_it = list_begin( t );
    LISTITER const t_end = list_end( t );
    LISTITER s_it = list_begin( s );
    LISTITER const s_end = list_end( s );

    while ( !status && ( t_it != t_end || s_it != s_end ) )
    {
        char const * st = t_it != t_end ? object_str( list_item( t_it ) ) : "";
        char const * 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 );
    LISTITER const 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
 */

void list_print( LIST * l )
{
    LISTITER iter = list_begin( l ), end = list_end( l );
    if ( iter != end )
    {
        out_printf( "%s", object_str( list_item( iter ) ) );
        iter = list_next( iter );
        for ( ; iter != end; iter = list_next( iter ) )
            out_printf( " %s", object_str( list_item( iter ) ) );
    }
}


/*
 * list_length() - return the number of items in the list
 */

int list_length( LIST * l )
{
    return l ? l->impl.size : 0;
}


int list_in( LIST * l, OBJECT * value )
{
    LISTITER iter = list_begin( l );
    LISTITER end = list_end( l );
    for ( ; iter != end; iter = list_next( iter ) )
        if ( object_equal( list_item( iter ), value ) )
            return 1;
    return 0;
}


LIST * list_unique( LIST * sorted_list )
{
    LIST * result = L0;
    OBJECT * last_added = 0;

    LISTITER iter = list_begin( sorted_list ), end = list_end( sorted_list );
    for ( ; iter != end; iter = list_next( iter ) )
    {
        if ( !last_added || !object_equal( list_item( iter ), last_added ) )
        {
            result = list_push_back( result, object_copy( list_item( iter ) ) );
            last_added = list_item( iter );
        }
    }
    return result;
}

void list_done()
{
    unsigned int i;
    for ( i = 0; i < sizeof( freelist ) / sizeof( freelist[ 0 ] ); ++i )
    {
        LIST * l = freelist[ i ];
        while ( l )
        {
            LIST * const tmp = l;
            l = l->impl.next;
            BJAM_FREE( tmp );
        }
    }
}


/*
 * lol_init() - initialize a LOL (list of lists).
 */

void lol_init( LOL * lol )
{
    lol->count = 0;
}


/*
 * lol_add() - append a LIST onto an LOL.
 */

void lol_add( LOL * lol, LIST * l )
{
    if ( lol->count < LOL_MAX )
        lol->list[ lol->count++ ] = l;
}


/*
 * lol_free() - free the LOL and its LISTs.
 */

void lol_free( LOL * lol )
{
    int i;
    for ( i = 0; i < lol->count; ++i )
        list_free( lol->list[ i ] );
    lol->count = 0;
}


/*
 * lol_get() - return one of the LISTs in the LOL.
 */

LIST * lol_get( LOL * lol, int i )
{
    return i < lol->count ? lol->list[ i ] : L0;
}


/*
 * lol_print() - debug print LISTS separated by ":".
 */

void lol_print( LOL * lol )
{
    int i;
    for ( i = 0; i < lol->count; ++i )
    {
        if ( i )
            out_printf( " : " );
        list_print( lol->list[ i ] );
    }
}

#ifdef HAVE_PYTHON

PyObject * list_to_python( LIST * l )
{
    PyObject * result = PyList_New( 0 );
    LISTITER iter = list_begin( l );
    LISTITER const end = list_end( l );
    for ( ; iter != end; iter = list_next( iter ) )
    {
        PyObject * s = PyString_FromString( object_str( list_item( iter ) ) );
        PyList_Append( result, s );
        Py_DECREF( s );
    }

    return result;
}

LIST * list_from_python( PyObject * l )
{
    LIST * result = L0;

    Py_ssize_t n = PySequence_Size( l );
    Py_ssize_t i;
    for ( i = 0; i < n; ++i )
    {
        PyObject * v = PySequence_GetItem( l, i );
        result = list_push_back( result, object_new( PyString_AsString( v ) ) );
        Py_DECREF( v );
    }

    return result;
}

#endif
Commit	Line	Data
7c673cae FG	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	{
f67539c2	67	unsigned int const l_size = list_length( l );
7c673cae FG	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 );
7c673cae FG	115
	116	if ( DEBUG_LISTS )
	117	out_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;
7c673cae FG	201	LIST * result;
	202
	203	if ( !l )
	204	return L0;
	205
	206	len = list_length( l );
	207	result = list_copy( l );
	208
	209	qsort( list_begin( result ), len, sizeof( OBJECT * ), str_ptr_compare );
	210
	211	return result;
	212	}
	213
	214
	215	/*
	216	* list_free() - free a list of strings
	217	*/
	218
	219	void list_free( LIST * head )
	220	{
	221	if ( !list_empty( head ) )
	222	{
	223	LISTITER iter = list_begin( head );
	224	LISTITER const end = list_end( head );
	225	for ( ; iter != end; iter = list_next( iter ) )
	226	object_free( list_item( iter ) );
	227	list_dealloc( head );
	228	}
	229	}
	230
	231
	232	/*
	233	* list_pop_front() - remove the front element from a list of strings
	234	*/
	235
	236	LIST * list_pop_front( LIST * l )
	237	{
	238	unsigned size = list_length( l );
	239	assert( size );
	240	--size;
	241	object_free( list_front( l ) );
	242
	243	if ( size == 0 )
	244	{
	245	list_dealloc( l );
	246	return L0;
	247	}
	248
	249	if ( ( ( size - 1 ) & size ) == 0 )
	250	{
	251	LIST * const nl = list_alloc( size );
	252	nl->impl.size = size;
	253	memcpy( list_begin( nl ), list_begin( l ) + 1, size * sizeof( OBJECT * )
	254	);
	255	list_dealloc( l );
	256	return nl;
	257	}
	258
	259	l->impl.size = size;
	260	memmove( list_begin( l ), list_begin( l ) + 1, size * sizeof( OBJECT * ) );
	261	return l;
	262	}
	263
	264	LIST * list_reverse( LIST * l )
265	{
266	int size = list_length( l );
267	if ( size == 0 ) return L0;
268	{
269	LIST * const result = list_alloc( size );
270	int i;
271	result->impl.size = size;
272	for ( i = 0; i < size; ++i )
273	list_begin( result )[ i ] = object_copy( list_begin( l )[ size - i -
274	1 ] );
275	return result;
276	}
277	}
278
279	int list_cmp( LIST * t, LIST * s )
280	{
281	int status = 0;
282	LISTITER t_it = list_begin( t );
283	LISTITER const t_end = list_end( t );
284	LISTITER s_it = list_begin( s );
285	LISTITER const s_end = list_end( s );
286
287	while ( !status && ( t_it != t_end \|\| s_it != s_end ) )
288	{
289	char const * st = t_it != t_end ? object_str( list_item( t_it ) ) : "";
290	char const * ss = s_it != s_end ? object_str( list_item( s_it ) ) : "";
291
292	status = strcmp( st, ss );
293
294	t_it = t_it != t_end ? list_next( t_it ) : t_it;
295	s_it = s_it != s_end ? list_next( s_it ) : s_it;
296	}
297
298	return status;
299	}
300
301	int list_is_sublist( LIST * sub, LIST * l )
302	{
303	LISTITER iter = list_begin( sub );
304	LISTITER const end = list_end( sub );
305	for ( ; iter != end; iter = list_next( iter ) )
306	if ( !list_in( l, list_item( iter ) ) )
307	return 0;
308	return 1;
309	}
310
311	/*
312	* list_print() - print a list of strings to stdout
313	*/
314
315	void list_print( LIST * l )
316	{
317	LISTITER iter = list_begin( l ), end = list_end( l );
318	if ( iter != end )
319	{
320	out_printf( "%s", object_str( list_item( iter ) ) );
321	iter = list_next( iter );
322	for ( ; iter != end; iter = list_next( iter ) )
323	out_printf( " %s", object_str( list_item( iter ) ) );
324	}
325	}
326
327
328	/*
329	* list_length() - return the number of items in the list
330	*/
331
332	int list_length( LIST * l )
333	{
334	return l ? l->impl.size : 0;
335	}
336
337
338	int list_in( LIST * l, OBJECT * value )
339	{
340	LISTITER iter = list_begin( l );
341	LISTITER end = list_end( l );
342	for ( ; iter != end; iter = list_next( iter ) )
343	if ( object_equal( list_item( iter ), value ) )
344	return 1;
345	return 0;
346	}
347
348
349	LIST * list_unique( LIST * sorted_list )
350	{
351	LIST * result = L0;
352	OBJECT * last_added = 0;
353
354	LISTITER iter = list_begin( sorted_list ), end = list_end( sorted_list );
355	for ( ; iter != end; iter = list_next( iter ) )
356	{
357	if ( !last_added \|\| !object_equal( list_item( iter ), last_added ) )
358	{
359	result = list_push_back( result, object_copy( list_item( iter ) ) );
360	last_added = list_item( iter );
361	}
362	}
363	return result;
364	}
365
366	void list_done()
367	{
f67539c2	368	unsigned int i;
7c673cae FG	369	for ( i = 0; i < sizeof( freelist ) / sizeof( freelist[ 0 ] ); ++i )
	370	{
	371	LIST * l = freelist[ i ];
	372	while ( l )
	373	{
	374	LIST * const tmp = l;
	375	l = l->impl.next;
	376	BJAM_FREE( tmp );
	377	}
	378	}
	379	}
	380
	381
	382	/*
	383	* lol_init() - initialize a LOL (list of lists).
	384	*/
	385
	386	void lol_init( LOL * lol )
	387	{
	388	lol->count = 0;
	389	}
	390
	391
	392	/*
	393	* lol_add() - append a LIST onto an LOL.
	394	*/
	395
	396	void lol_add( LOL * lol, LIST * l )
	397	{
	398	if ( lol->count < LOL_MAX )
	399	lol->list[ lol->count++ ] = l;
	400	}
	401
	402
	403	/*
	404	* lol_free() - free the LOL and its LISTs.
	405	*/
	406
	407	void lol_free( LOL * lol )
	408	{
	409	int i;
	410	for ( i = 0; i < lol->count; ++i )
	411	list_free( lol->list[ i ] );
	412	lol->count = 0;
	413	}
	414
	415
	416	/*
	417	* lol_get() - return one of the LISTs in the LOL.
	418	*/
	419
	420	LIST * lol_get( LOL * lol, int i )
	421	{
	422	return i < lol->count ? lol->list[ i ] : L0;
	423	}
	424
	425
	426	/*
	427	* lol_print() - debug print LISTS separated by ":".
	428	*/
	429
	430	void lol_print( LOL * lol )
	431	{
	432	int i;
433	for ( i = 0; i < lol->count; ++i )
434	{
435	if ( i )
436	out_printf( " : " );
437	list_print( lol->list[ i ] );
438	}
439	}
440
441	#ifdef HAVE_PYTHON
442
443	PyObject * list_to_python( LIST * l )
444	{
445	PyObject * result = PyList_New( 0 );
446	LISTITER iter = list_begin( l );
447	LISTITER const end = list_end( l );
448	for ( ; iter != end; iter = list_next( iter ) )
449	{
450	PyObject * s = PyString_FromString( object_str( list_item( iter ) ) );
451	PyList_Append( result, s );
452	Py_DECREF( s );
453	}
454
455	return result;
456	}
457
458	LIST * list_from_python( PyObject * l )
459	{
460	LIST * result = L0;
461
462	Py_ssize_t n = PySequence_Size( l );
463	Py_ssize_t i;
464	for ( i = 0; i < n; ++i )
465	{
466	PyObject * v = PySequence_GetItem( l, i );
467	result = list_push_back( result, object_new( PyString_AsString( v ) ) );
468	Py_DECREF( v );
469	}
470
471	return result;
472	}
473
474	#endif