third_party/cairo/src/cairo-hash.c
void *
_cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
				cairo_hash_predicate_func_t predicate)
{
    cairo_hash_entry_t *entry;
    unsigned long hash;
    unsigned long table_size, i, idx, step;

    assert (predicate != NULL);

    table_size = *hash_table->table_size;
    hash = rand ();
    idx = hash % table_size;

    entry = hash_table->entries[idx];
    if (ENTRY_IS_LIVE (entry) && predicate (entry))
	return entry;

    i = 1;
    step = 1 + hash % (table_size - 2);
    do {
	idx += step;
	if (idx >= table_size)
	    idx -= table_size;

	entry = hash_table->entries[idx];
	if (ENTRY_IS_LIVE (entry) && predicate (entry))
	    return entry;
    } while (++i < table_size);

    return NULL;
}
/**
 * _cairo_hash_table_random_entry:
 * @hash_table: a hash table
 * @predicate: a predicate function.
 *
 * Find a random entry in the hash table satisfying the given
 * @predicate.
 *
 * We use the same algorithm as the lookup algorithm to walk over the
 * entries in the hash table in a pseudo-random order. Walking
 * linearly would favor entries following gaps in the hash table. We
 * could also call rand() repeatedly, which works well for almost-full
 * tables, but degrades when the table is almost empty, or predicate
 * returns %TRUE for most entries.
 *
 * Return value: a random live entry or %NULL if there are no entries
 * that match the given predicate. In particular, if predicate is
 * %NULL, a %NULL return value indicates that the table is empty.
 **/
@hash_table: a hash table
@predicate: a predicate function.

Find a random entry in the hash table satisfying the given
@predicate.

We use the same algorithm as the lookup algorithm to walk over the
entries in the hash table in a pseudo-random order. Walking
linearly would favor entries following gaps in the hash table. We
could also call rand() repeatedly, which works well for almost-full
tables, but degrades when the table is almost empty, or predicate
returns %TRUE for most entries.

Return value: a random live entry or %NULL if there are no entries
that match the given predicate. In particular, if predicate is
%NULL, a %NULL return value indicates that the table is empty.
@hash_table : a hash table @predicate : a predicate function . Find a random entry in the hash table satisfying the given @predicate . We use the same algorithm as the lookup algorithm to walk over the entries in the hash table in a pseudo - random order . Walking linearly would favor entries following gaps in the hash table . We could also call rand () repeatedly which works well for almost - full tables but degrades when the table is almost empty or predicate returns %TRUE for most entries . Return value : a random live entry or %NULL if there are no entries that match the given predicate . In particular if predicate is %NULL a %NULL return value indicates that the table is empty .
void *
_cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
				cairo_hash_predicate_func_t predicate)
{
    cairo_hash_entry_t *entry;
    unsigned long hash;
    unsigned long table_size, i, idx, step;
    assert (predicate != NULL);
    table_size = *hash_table->table_size;
    hash = rand ();
    idx = hash % table_size;
    entry = hash_table->entries[idx];
    if (ENTRY_IS_LIVE (entry) && predicate (entry))
	return entry;
    i = 1;
    step = 1 + hash % (table_size - 2);
    do {
	idx += step;
	if (idx >= table_size)
	    idx -= table_size;
	entry = hash_table->entries[idx];
	if (ENTRY_IS_LIVE (entry) && predicate (entry))
	    return entry;
    } while (++i < table_size);
    return NULL;
}
void * _cairo_hash_table_random_entry ( cairo_hash_table_t * hash_table , cairo_hash_predicate_func_t predicate ) { cairo_hash_entry_t * entry ; unsigned long hash ; unsigned long table_size , i , idx , step ; assert ( predicate != NULL ) ; table_size = * hash_table -> table_size ; hash = rand ( ) ; idx = hash % table_size ; entry = hash_table -> entries [ idx ] ; if ( ENTRY_IS_LIVE ( entry ) && predicate ( entry ) ) return entry ; i = 1 ; step = 1 + hash % ( table_size - 2 ) ; do { idx += step ; if ( idx >= table_size ) idx -= table_size ; entry = hash_table -> entries [ idx ] ; if ( ENTRY_IS_LIVE ( entry ) && predicate ( entry ) ) return entry ; } while ( ++ i < table_size ) ; return NULL ; }
_cairo_hash_table_random_entry:
 @hash_table: a hash table
 @predicate: a predicate function.
_cairo_hash_table_random_entry : @hash_table : a hash table @predicate : a predicate function .