Back to index

lightning-sunbird  0.9+nobinonly
Classes | Typedefs | Functions
cairo-hash-private.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  _cairo_hash_entry
 cairo_hash_entry_t: More...

Typedefs

typedef struct _cairo_hash_table
typedef struct _cairo_hash_entry cairo_hash_entry_t
 cairo_hash_entry_t:
typedef cairo_bool_t(* cairo_hash_keys_equal_func_t )(void *key_a, void *key_b)
typedef cairo_bool_t(* cairo_hash_predicate_func_t )(void *entry)
typedef void(* cairo_hash_callback_func_t )(void *entry, void *closure)

Functions

cairo_private cairo_hash_table_t * _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
 _cairo_hash_table_create: : a function to return TRUE if two keys are equal
cairo_private void _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
 _cairo_hash_table_destroy: : an empty hash table to destroy
cairo_private cairo_bool_t _cairo_hash_table_lookup (cairo_hash_table_t *hash_table, cairo_hash_entry_t *key, cairo_hash_entry_t **entry_return)
 _cairo_hash_table_lookup: : a hash table : the key of interest : pointer for return value.
cairo_private void_cairo_hash_table_random_entry (cairo_hash_table_t *hash_table, cairo_hash_predicate_func_t predicate)
 _cairo_hash_table_random_entry: : a hash table : a predicate function, or NULL for any entry.
cairo_private cairo_status_t _cairo_hash_table_insert (cairo_hash_table_t *hash_table, cairo_hash_entry_t *entry)
 _cairo_hash_table_insert: : a hash table : an entry to be inserted
cairo_private void _cairo_hash_table_remove (cairo_hash_table_t *hash_table, cairo_hash_entry_t *key)
 _cairo_hash_table_remove: : a hash table : key of entry to be removed
cairo_private void _cairo_hash_table_foreach (cairo_hash_table_t *hash_table, cairo_hash_callback_func_t hash_callback, void *closure)
 _cairo_hash_table_foreach: : a hash table : function to be called for each live entry : additional argument to be passed to

Class Documentation

struct _cairo_hash_entry

cairo_hash_entry_t:

A cairo_hash_entry_t contains both a key and a value for cairo_hash_table_t. User-derived types for cairo_hash_entry_t must be type-compatible with this structure (eg. they must have an unsigned long as the first parameter. The easiest way to get this is to use:

  typedef _my_entry {
      cairo_hash_entry_t base;
      ... Remainder of key and value fields here ..
  } my_entry_t;

which then allows a pointer to my_entry_t to be passed to any of the cairo_hash_table functions as follows without requiring a cast:

  _cairo_hash_table_insert (hash_table, &my_entry->base);

IMPORTANT: The caller is reponsible for initializing my_entry->base.hash with a hash code derived from the key. The essential property of the hash code is that keys_equal must never return TRUE for two keys that have different hashes. The best hash code will reduce the frequency of two keys with the same code for which keys_equal returns FALSE.

Which parts of the entry make up the "key" and which part make up the value are entirely up to the caller, (as determined by the computation going into base.hash as well as the keys_equal function). A few of the cairo_hash_table functions accept an entry which will be used exclusively as a "key", (indicated by a parameter name of key). In these cases, the value-related fields of the entry need not be initialized if so desired.

Definition at line 83 of file cairo-hash-private.h.

Class Members
unsigned long hash

Typedef Documentation

typedef struct _cairo_hash_table

Definition at line 47 of file cairo-hash-private.h.

Definition at line 94 of file cairo-hash-private.h.

cairo_hash_entry_t:

A cairo_hash_entry_t contains both a key and a value for cairo_hash_table_t. User-derived types for cairo_hash_entry_t must be type-compatible with this structure (eg. they must have an unsigned long as the first parameter. The easiest way to get this is to use:

  typedef _my_entry {
      cairo_hash_entry_t base;
      ... Remainder of key and value fields here ..
  } my_entry_t;

which then allows a pointer to my_entry_t to be passed to any of the cairo_hash_table functions as follows without requiring a cast:

  _cairo_hash_table_insert (hash_table, &my_entry->base);

IMPORTANT: The caller is reponsible for initializing my_entry->base.hash with a hash code derived from the key. The essential property of the hash code is that keys_equal must never return TRUE for two keys that have different hashes. The best hash code will reduce the frequency of two keys with the same code for which keys_equal returns FALSE.

Which parts of the entry make up the "key" and which part make up the value are entirely up to the caller, (as determined by the computation going into base.hash as well as the keys_equal function). A few of the cairo_hash_table functions accept an entry which will be used exclusively as a "key", (indicated by a parameter name of key). In these cases, the value-related fields of the entry need not be initialized if so desired.

typedef cairo_bool_t(* cairo_hash_keys_equal_func_t)(void *key_a, void *key_b)

Definition at line 88 of file cairo-hash-private.h.

Definition at line 91 of file cairo-hash-private.h.


Function Documentation

_cairo_hash_table_create: : a function to return TRUE if two keys are equal

Creates a new hash table which will use the keys_equal() function to compare hash keys. Data is provided to the hash table in the form of user-derived versions of cairo_hash_entry_t. A hash entry must be able to hold both a key (including a hash code) and a value. Sometimes only the key will be necessary, (as in _cairo_hash_table_remove), and other times both a key and a value will be necessary, (as in _cairo_hash_table_insert).

See cairo_hash_entry_t for more details.

Return value: the new hash table or NULL if out of memory.

Definition at line 146 of file cairo-hash.c.

{    
    cairo_hash_table_t *hash_table;

    hash_table = malloc (sizeof (cairo_hash_table_t));
    if (hash_table == NULL)
       return NULL;

    hash_table->keys_equal = keys_equal;

    hash_table->arrangement = &hash_table_arrangements[0];

    hash_table->entries = calloc (hash_table->arrangement->size,
                              sizeof(cairo_hash_entry_t *));
    if (hash_table->entries == NULL) {
       free (hash_table);
       return NULL;
    }

    hash_table->live_entries = 0;

    return hash_table;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_private void _cairo_hash_table_destroy ( cairo_hash_table_t *  hash_table)

_cairo_hash_table_destroy: : an empty hash table to destroy

Immediately destroys the given hash table, freeing all resources associated with it.

WARNING: The hash_table must have no live entries in it before _cairo_hash_table_destroy is called. It is a fatal error otherwise, and this function will halt. The rationale for this behavior is to avoid memory leaks and to avoid needless complication of the API with destroy notifiy callbacks.

Definition at line 184 of file cairo-hash.c.

{
    if (hash_table == NULL)
       return;

    /* The hash table must be empty. Otherwise, halt. */
    assert (hash_table->live_entries == 0);
       
    free (hash_table->entries);
    hash_table->entries = NULL;

    free (hash_table);
}

Here is the caller graph for this function:

cairo_private void _cairo_hash_table_foreach ( cairo_hash_table_t *  hash_table,
cairo_hash_callback_func_t  hash_callback,
void closure 
)

_cairo_hash_table_foreach: : a hash table : function to be called for each live entry : additional argument to be passed to

Call for each live entry in the hash table, in a non-specified order.

Definition at line 518 of file cairo-hash.c.

{
    unsigned long i;
    cairo_hash_entry_t *entry;

    if (hash_table == NULL)
       return;
       
    for (i = 0; i < hash_table->arrangement->size; i++) {
       entry = hash_table->entries[i];
       if (ENTRY_IS_LIVE(entry))
           hash_callback (entry, closure);
    }
}
cairo_private cairo_status_t _cairo_hash_table_insert ( cairo_hash_table_t *  hash_table,
cairo_hash_entry_t key_and_value 
)

_cairo_hash_table_insert: : a hash table : an entry to be inserted

Insert the entry #key_and_value into the hash table.

WARNING: It is a fatal error if an entry exists in the hash table with a matching key, (this function will halt).

Instead of using insert to replace an entry, consider just editing the entry obtained with _cairo_hash_table_lookup. Or if absolutely necessary, use _cairo_hash_table_remove first.

Return value: CAIRO_STATUS_SUCCESS if successful or CAIRO_STATUS_NO_MEMORY if insufficient memory is available.

Definition at line 451 of file cairo-hash.c.

{
    cairo_status_t status;
    cairo_hash_entry_t **entry;
    
    entry = _cairo_hash_table_lookup_internal (hash_table,
                                          key_and_value, FALSE);
    
    if (ENTRY_IS_LIVE(*entry))
    {
       /* User is being bad, let's crash. */
       ASSERT_NOT_REACHED;
    }

    *entry = key_and_value;
    hash_table->live_entries++;

    status = _cairo_hash_table_resize (hash_table);
    if (status)
       return status;

    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_private cairo_bool_t _cairo_hash_table_lookup ( cairo_hash_table_t *  hash_table,
cairo_hash_entry_t key,
cairo_hash_entry_t **  entry_return 
)

_cairo_hash_table_lookup: : a hash table : the key of interest : pointer for return value.

Performs a lookup in looking for an entry which has a key that matches , (as determined by the keys_equal() function passed to _cairo_hash_table_create).

Return value: TRUE if there is an entry in the hash table that matches the given key, (which will now be in *entry_return). FALSE otherwise, (in which case *entry_return will be NULL).

Definition at line 358 of file cairo-hash.c.

{
    cairo_hash_entry_t **entry;

    /* See if we have an entry in the table already. */
    entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE);
    if (ENTRY_IS_LIVE(*entry)) {
       *entry_return = *entry;
       return TRUE;
    }

    *entry_return = NULL;
    return FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_private void* _cairo_hash_table_random_entry ( cairo_hash_table_t *  hash_table,
cairo_hash_predicate_func_t  predicate 
)

_cairo_hash_table_random_entry: : a hash table : a predicate function, or NULL for any entry.

Find a random entry in the hash table satisfying the given . A NULL is taken as equivalent to a function which always returns TRUE, (eg. any entry in the table will do).

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.

Definition at line 396 of file cairo-hash.c.

{
    cairo_hash_entry_t **entry;
    unsigned long hash;
    unsigned long table_size, i, idx, step;

    table_size = hash_table->arrangement->size;

    hash = rand ();
    idx = hash % table_size;
    step = 0;

    for (i = 0; i < table_size; ++i)
    {
       entry = &hash_table->entries[idx];

       if (ENTRY_IS_LIVE (*entry) &&
           (predicate == NULL || predicate (*entry)))
       {
           return *entry;
       }

       if (step == 0) {         
           step = hash % hash_table->arrangement->rehash;
           if (step == 0)
              step = 1;
       }

       idx += step;
       if (idx >= table_size)
           idx -= table_size;
    }

    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

cairo_private void _cairo_hash_table_remove ( cairo_hash_table_t *  hash_table,
cairo_hash_entry_t key 
)

_cairo_hash_table_remove: : a hash table : key of entry to be removed

Remove an entry from the hash table which has a key that matches , if any (as determined by the keys_equal() function passed to _cairo_hash_table_create).

Return value: CAIRO_STATUS_SUCCESS if successful or CAIRO_STATUS_NO_MEMORY if out of memory.

Definition at line 489 of file cairo-hash.c.

{
    cairo_hash_entry_t **entry;

    entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE);
    if (! ENTRY_IS_LIVE(*entry))
       return;

    *entry = DEAD_ENTRY;
    hash_table->live_entries--;

    /* This call _can_ fail, but only in failing to allocate new
     * memory to shrink the hash table. It does leave the table in a
     * consistent state, and we've already succeeded in removing the
     * entry, so we don't examine the failure status of this call. */
    _cairo_hash_table_resize (hash_table);
}

Here is the call graph for this function:

Here is the caller graph for this function: