[ceph.git] / ceph / src / boost / tools / build / src / engine / modules / property-set.c

/*
 * Copyright 2013 Steven Watanabe
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 */

#include "../object.h"
#include "../lists.h"
#include "../modules.h"
#include "../rules.h"
#include "../variable.h"
#include "../native.h"
#include "../compile.h"
#include "../mem.h"
#include "../constants.h"
#include "string.h"

struct ps_map_entry
{
    struct ps_map_entry * next;
    LIST * key;
    OBJECT * value;
};

struct ps_map
{
    struct ps_map_entry * * table;
    size_t table_size;
    size_t num_elems;
};

static unsigned list_hash(LIST * key)
{
    unsigned int hash = 0;
    LISTITER iter = list_begin( key ), end = list_end( key );
    for ( ; iter != end; ++iter )
    {
        hash = hash * 2147059363 + object_hash( list_item( iter ) );
    }
    return hash;
}

static int list_equal( LIST * lhs, LIST * rhs )
{
    LISTITER lhs_iter, lhs_end, rhs_iter;
    if ( list_length( lhs ) != list_length( rhs ) )
    {
        return 0;
    }
    lhs_iter = list_begin( lhs );
    lhs_end = list_end( lhs );
    rhs_iter = list_begin( rhs );
    for ( ; lhs_iter != lhs_end; ++lhs_iter, ++rhs_iter )
    {
        if ( ! object_equal( list_item( lhs_iter ), list_item( rhs_iter ) ) )
        {
            return 0;
        }
    }
    return 1;
}

static void ps_map_init( struct ps_map * map )
{
    size_t i;
    map->table_size = 2;
    map->num_elems = 0;
    map->table = BJAM_MALLOC( map->table_size * sizeof( struct ps_map_entry * ) );
    for ( i = 0; i < map->table_size; ++i )
    {
        map->table[ i ] = NULL;
    }
}

static void ps_map_destroy( struct ps_map * map )
{
    size_t i;
    for ( i = 0; i < map->table_size; ++i )
    {
        struct ps_map_entry * pos;
        for ( pos = map->table[ i ]; pos; )
        {
            struct ps_map_entry * tmp = pos->next;
            object_free( pos->value );
            BJAM_FREE( pos );
            pos = tmp;
        }
    }
    BJAM_FREE( map->table );
}

static void ps_map_rehash( struct ps_map * map )
{
    struct ps_map old = *map;
    size_t i;
    map->table = BJAM_MALLOC( map->table_size * 2 * sizeof( struct ps_map_entry * ) );
    map->table_size *= 2;
    for ( i = 0; i < map->table_size; ++i )
    {
        map->table[ i ] = NULL;
    }
    for ( i = 0; i < old.table_size; ++i )
    {
        struct ps_map_entry * pos;
        for ( pos = old.table[ i ]; pos; )
        {
            struct ps_map_entry * tmp = pos->next;

            unsigned hash_val = list_hash( pos->key );
            unsigned bucket = hash_val % map->table_size;
            pos->next = map->table[ bucket ];
            map->table[ bucket ] = pos;

            pos = tmp;
        }
    }
    BJAM_FREE( old.table );
}

static struct ps_map_entry * ps_map_insert(struct ps_map * map, LIST * key)
{
    unsigned hash_val = list_hash( key );
    unsigned bucket = hash_val % map->table_size;
    struct ps_map_entry * pos;
    for ( pos = map->table[bucket]; pos ; pos = pos->next )
    {
        if ( list_equal( pos->key, key ) )
            return pos;
    }

    if ( map->num_elems >= map->table_size )
    {
        ps_map_rehash( map );
        bucket = hash_val % map->table_size;
    }
    pos = BJAM_MALLOC( sizeof( struct ps_map_entry ) );
    pos->next = map->table[bucket];
    pos->key = key;
    pos->value = 0;
    map->table[bucket] = pos;
    ++map->num_elems;
    return pos;
}

static struct ps_map all_property_sets;

LIST * property_set_create( FRAME * frame, int flags )
{
    LIST * properties = lol_get( frame->args, 0 );
    LIST * sorted = list_sort( properties );
    LIST * unique = list_unique( sorted );
    struct ps_map_entry * pos = ps_map_insert( &all_property_sets, unique );
    list_free( sorted );
    if ( pos->value )
    {
        list_free( unique );
        return list_new( object_copy( pos->value ) );
    }
    else
    {
        OBJECT * rulename = object_new( "new" );
        OBJECT * varname = object_new( "self.raw" );
        LIST * val = call_rule( rulename, frame,
            list_new( object_new( "property-set" ) ), 0 );
        LISTITER iter, end;
        object_free( rulename );
        pos->value = object_copy( list_front( val ) );
        var_set( bindmodule( pos->value ), varname, unique, VAR_SET );
        object_free( varname );

        for ( iter = list_begin( unique ), end = list_end( unique ); iter != end; ++iter )
        {
            const char * str = object_str( list_item( iter ) );
            if ( str[ 0 ] != '<' || ! strchr( str, '>' ) )
            {
                string message[ 1 ];
                string_new( message );
                string_append( message, "Invalid property: '" );
                string_append( message, str );
                string_append( message, "'" );
                rulename = object_new( "errors.error" );
                call_rule( rulename, frame,
                    list_new( object_new( message->value ) ), 0 );
                /* unreachable */
                string_free( message );
                object_free( rulename );
            }
        }

        return val;
    }
}

/* binary search for the property value */
LIST * property_set_get( FRAME * frame, int flags )
{
    OBJECT * varname = object_new( "self.raw" );
    LIST * props = var_get( frame->module, varname );
    const char * name = object_str( list_front( lol_get( frame->args, 0 ) ) );
    size_t name_len = strlen( name );
    LISTITER begin, end;
    LIST * result = L0;
    object_free( varname );

    /* Assumes random access */
    begin = list_begin( props ), end = list_end( props );

    while ( 1 )
    {
        ptrdiff_t diff = (end - begin);
        LISTITER mid = begin + diff / 2;
        int res;
        if ( diff == 0 )
        {
            return L0;
        }
        res = strncmp( object_str( list_item( mid ) ), name, name_len );
        if ( res < 0 )
        {
            begin = mid + 1;
        }
        else if ( res > 0 )
        {
            end = mid;
        }
        else /* We've found the property */
        {
            /* Find the beginning of the group */
            LISTITER tmp = mid;
            while ( tmp > begin )
            {
                --tmp;
                res = strncmp( object_str( list_item( tmp ) ), name, name_len );
                if ( res != 0 )
                {
                    ++tmp;
                    break;
                }
            }
            begin = tmp;
            /* Find the end of the group */
            tmp = mid + 1;
            while ( tmp < end )
            {
                res = strncmp( object_str( list_item( tmp ) ), name, name_len );
                if ( res != 0 ) break;
                ++tmp;
            }
            end = tmp;
            break;
        }
    }

    for ( ; begin != end; ++begin )
    {
        result = list_push_back( result,
            object_new( object_str( list_item( begin ) ) + name_len ) );
    }

    return result;
}

/* binary search for the property value */
LIST * property_set_contains_features( FRAME * frame, int flags )
{
    OBJECT * varname = object_new( "self.raw" );
    LIST * props = var_get( frame->module, varname );
    LIST * features = lol_get( frame->args, 0 );
    LIST * result = L0;
    LISTITER features_iter = list_begin( features );
    LISTITER features_end = list_end( features ) ;
    object_free( varname );

    for ( ; features_iter != features_end; ++features_iter )
    {
        const char * name = object_str( list_item( features_iter ) );
        size_t name_len = strlen( name );
        LISTITER begin, end;
        /* Assumes random access */
        begin = list_begin( props ), end = list_end( props );

        while ( 1 )
        {
            ptrdiff_t diff = (end - begin);
            LISTITER mid = begin + diff / 2;
            int res;
            if ( diff == 0 )
            {
                /* The feature is missing */
                return L0;
            }
            res = strncmp( object_str( list_item( mid ) ), name, name_len );
            if ( res < 0 )
            {
                begin = mid + 1;
            }
            else if ( res > 0 )
            {
                end = mid;
            }
            else /* We've found the property */
            {
                break;
            }
        }
    }
    return list_new( object_copy( constant_true ) );
}

void init_property_set()
{
    {
        char const * args[] = { "raw-properties", "*", 0 };
        declare_native_rule( "property-set", "create", args, property_set_create, 1 );
    }
    {
        char const * args[] = { "feature", 0 };
        declare_native_rule( "class@property-set", "get", args, property_set_get, 1 );
    }
    {
        char const * args[] = { "features", "*", 0 };
        declare_native_rule( "class@property-set", "contains-features", args, property_set_contains_features, 1 );
    }
    ps_map_init( &all_property_sets );
}

void property_set_done()
{
    ps_map_destroy( &all_property_sets );
}
Commit	Line	Data
7c673cae FG	1	/*
	2	* Copyright 2013 Steven Watanabe
	3	* Distributed under the Boost Software License, Version 1.0.
	4	* (See accompanying file LICENSE_1_0.txt or copy at
	5	* http://www.boost.org/LICENSE_1_0.txt)
	6	*/
	7
	8	#include "../object.h"
	9	#include "../lists.h"
	10	#include "../modules.h"
	11	#include "../rules.h"
	12	#include "../variable.h"
	13	#include "../native.h"
	14	#include "../compile.h"
	15	#include "../mem.h"
	16	#include "../constants.h"
	17	#include "string.h"
	18
	19	struct ps_map_entry
	20	{
	21	struct ps_map_entry * next;
	22	LIST * key;
	23	OBJECT * value;
	24	};
	25
	26	struct ps_map
	27	{
	28	struct ps_map_entry * * table;
	29	size_t table_size;
	30	size_t num_elems;
	31	};
	32
	33	static unsigned list_hash(LIST * key)
	34	{
	35	unsigned int hash = 0;
	36	LISTITER iter = list_begin( key ), end = list_end( key );
	37	for ( ; iter != end; ++iter )
	38	{
	39	hash = hash * 2147059363 + object_hash( list_item( iter ) );
	40	}
	41	return hash;
	42	}
	43
	44	static int list_equal( LIST * lhs, LIST * rhs )
	45	{
	46	LISTITER lhs_iter, lhs_end, rhs_iter;
	47	if ( list_length( lhs ) != list_length( rhs ) )
	48	{
	49	return 0;
	50	}
	51	lhs_iter = list_begin( lhs );
	52	lhs_end = list_end( lhs );
	53	rhs_iter = list_begin( rhs );
	54	for ( ; lhs_iter != lhs_end; ++lhs_iter, ++rhs_iter )
	55	{
	56	if ( ! object_equal( list_item( lhs_iter ), list_item( rhs_iter ) ) )
	57	{
	58	return 0;
	59	}
	60	}
	61	return 1;
	62	}
	63
	64	static void ps_map_init( struct ps_map * map )
65	{
66	size_t i;
67	map->table_size = 2;
68	map->num_elems = 0;
69	map->table = BJAM_MALLOC( map->table_size * sizeof( struct ps_map_entry * ) );
70	for ( i = 0; i < map->table_size; ++i )
71	{
72	map->table[ i ] = NULL;
73	}
74	}
75
76	static void ps_map_destroy( struct ps_map * map )
77	{
78	size_t i;
79	for ( i = 0; i < map->table_size; ++i )
80	{
81	struct ps_map_entry * pos;
82	for ( pos = map->table[ i ]; pos; )
83	{
84	struct ps_map_entry * tmp = pos->next;
85	object_free( pos->value );
86	BJAM_FREE( pos );
87	pos = tmp;
88	}
89	}
90	BJAM_FREE( map->table );
91	}
92
93	static void ps_map_rehash( struct ps_map * map )
94	{
95	struct ps_map old = *map;
96	size_t i;
97	map->table = BJAM_MALLOC( map->table_size * 2 * sizeof( struct ps_map_entry * ) );
98	map->table_size *= 2;
99	for ( i = 0; i < map->table_size; ++i )
100	{
101	map->table[ i ] = NULL;
102	}
103	for ( i = 0; i < old.table_size; ++i )
104	{
105	struct ps_map_entry * pos;
106	for ( pos = old.table[ i ]; pos; )
107	{
108	struct ps_map_entry * tmp = pos->next;
109
110	unsigned hash_val = list_hash( pos->key );
111	unsigned bucket = hash_val % map->table_size;
112	pos->next = map->table[ bucket ];
113	map->table[ bucket ] = pos;
114
115	pos = tmp;
116	}
117	}
118	BJAM_FREE( old.table );
119	}
120
121	static struct ps_map_entry * ps_map_insert(struct ps_map * map, LIST * key)
122	{
123	unsigned hash_val = list_hash( key );
124	unsigned bucket = hash_val % map->table_size;
125	struct ps_map_entry * pos;
126	for ( pos = map->table[bucket]; pos ; pos = pos->next )
127	{
128	if ( list_equal( pos->key, key ) )
129	return pos;
130	}
131
132	if ( map->num_elems >= map->table_size )
133	{
134	ps_map_rehash( map );
135	bucket = hash_val % map->table_size;
136	}
137	pos = BJAM_MALLOC( sizeof( struct ps_map_entry ) );
138	pos->next = map->table[bucket];
139	pos->key = key;
140	pos->value = 0;
141	map->table[bucket] = pos;
142	++map->num_elems;
143	return pos;
144	}
145
146	static struct ps_map all_property_sets;
147
148	LIST * property_set_create( FRAME * frame, int flags )
149	{
150	LIST * properties = lol_get( frame->args, 0 );
151	LIST * sorted = list_sort( properties );
152	LIST * unique = list_unique( sorted );
153	struct ps_map_entry * pos = ps_map_insert( &all_property_sets, unique );
154	list_free( sorted );
155	if ( pos->value )
156	{
157	list_free( unique );
158	return list_new( object_copy( pos->value ) );
159	}
160	else
161	{
162	OBJECT * rulename = object_new( "new" );
163	OBJECT * varname = object_new( "self.raw" );
164	LIST * val = call_rule( rulename, frame,
165	list_new( object_new( "property-set" ) ), 0 );
166	LISTITER iter, end;
167	object_free( rulename );
168	pos->value = object_copy( list_front( val ) );
169	var_set( bindmodule( pos->value ), varname, unique, VAR_SET );
170	object_free( varname );
171
172	for ( iter = list_begin( unique ), end = list_end( unique ); iter != end; ++iter )
173	{
174	const char * str = object_str( list_item( iter ) );
175	if ( str[ 0 ] != '<' \|\| ! strchr( str, '>' ) )
176	{
177	string message[ 1 ];
178	string_new( message );
179	string_append( message, "Invalid property: '" );
180	string_append( message, str );
181	string_append( message, "'" );
182	rulename = object_new( "errors.error" );
183	call_rule( rulename, frame,
184	list_new( object_new( message->value ) ), 0 );
185	/* unreachable */
186	string_free( message );
187	object_free( rulename );
188	}
189	}
190
191	return val;
192	}
193	}
194
195	/* binary search for the property value */
196	LIST * property_set_get( FRAME * frame, int flags )
197	{
198	OBJECT * varname = object_new( "self.raw" );
199	LIST * props = var_get( frame->module, varname );
200	const char * name = object_str( list_front( lol_get( frame->args, 0 ) ) );
201	size_t name_len = strlen( name );
202	LISTITER begin, end;
203	LIST * result = L0;
204	object_free( varname );
205
206	/* Assumes random access */
207	begin = list_begin( props ), end = list_end( props );
208
209	while ( 1 )
210	{
211	ptrdiff_t diff = (end - begin);
212	LISTITER mid = begin + diff / 2;
213	int res;
214	if ( diff == 0 )
215	{
216	return L0;
217	}
218	res = strncmp( object_str( list_item( mid ) ), name, name_len );
219	if ( res < 0 )
220	{
221	begin = mid + 1;
222	}
223	else if ( res > 0 )
224	{
225	end = mid;
226	}
227	else /* We've found the property */
228	{
229	/* Find the beginning of the group */
230	LISTITER tmp = mid;
231	while ( tmp > begin )
232	{
233	--tmp;
234	res = strncmp( object_str( list_item( tmp ) ), name, name_len );
235	if ( res != 0 )
236	{
237	++tmp;
238	break;
239	}
240	}
241	begin = tmp;
242	/* Find the end of the group */
243	tmp = mid + 1;
244	while ( tmp < end )
245	{
246	res = strncmp( object_str( list_item( tmp ) ), name, name_len );
247	if ( res != 0 ) break;
248	++tmp;
249	}
250	end = tmp;
251	break;
252	}
253	}
254
255	for ( ; begin != end; ++begin )
256	{
257	result = list_push_back( result,
258	object_new( object_str( list_item( begin ) ) + name_len ) );
259	}
260
261	return result;
262	}
263
264	/* binary search for the property value */
265	LIST * property_set_contains_features( FRAME * frame, int flags )
266	{
267	OBJECT * varname = object_new( "self.raw" );
268	LIST * props = var_get( frame->module, varname );
269	LIST * features = lol_get( frame->args, 0 );
270	LIST * result = L0;
271	LISTITER features_iter = list_begin( features );
272	LISTITER features_end = list_end( features ) ;
273	object_free( varname );
274
275	for ( ; features_iter != features_end; ++features_iter )
276	{
277	const char * name = object_str( list_item( features_iter ) );
278	size_t name_len = strlen( name );
279	LISTITER begin, end;
280	/* Assumes random access */
281	begin = list_begin( props ), end = list_end( props );
282
283	while ( 1 )
284	{
285	ptrdiff_t diff = (end - begin);
286	LISTITER mid = begin + diff / 2;
287	int res;
288	if ( diff == 0 )
289	{
290	/* The feature is missing */
291	return L0;
292	}
293	res = strncmp( object_str( list_item( mid ) ), name, name_len );
294	if ( res < 0 )
295	{
296	begin = mid + 1;
297	}
298	else if ( res > 0 )
299	{
300	end = mid;
301	}
302	else /* We've found the property */
303	{
304	break;
305	}
306	}
307	}
308	return list_new( object_copy( constant_true ) );
309	}
310
311	void init_property_set()
312	{
313	{
314	char const * args[] = { "raw-properties", "*", 0 };
315	declare_native_rule( "property-set", "create", args, property_set_create, 1 );
316	}
317	{
318	char const * args[] = { "feature", 0 };
319	declare_native_rule( "class@property-set", "get", args, property_set_get, 1 );
320	}
321	{
322	char const * args[] = { "features", "*", 0 };
323	declare_native_rule( "class@property-set", "contains-features", args, property_set_contains_features, 1 );
324	}
325	ps_map_init( &all_property_sets );
326	}
327
328	void property_set_done()
329	{
330	ps_map_destroy( &all_property_sets );
331	}