Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Functions | Variables
cairo-hash.c File Reference
#include "cairoint.h"

Go to the source code of this file.

Classes

struct  _cairo_hash_table_arrangement
struct  _cairo_hash_table

Defines

#define DEAD_ENTRY   (&dead_entry)
#define ENTRY_IS_FREE(entry)   ((entry) == NULL)
#define ENTRY_IS_DEAD(entry)   ((entry) == DEAD_ENTRY)
#define ENTRY_IS_LIVE(entry)   ((entry) && ! ENTRY_IS_DEAD(entry))
#define NUM_HASH_TABLE_ARRANGEMENTS   (sizeof(hash_table_arrangements)/sizeof(hash_table_arrangements[0]))

Typedefs

typedef struct
_cairo_hash_table_arrangement 
cairo_hash_table_arrangement_t

Functions

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
void _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
 _cairo_hash_table_destroy: : an empty hash table to destroy
static cairo_hash_entry_t ** _cairo_hash_table_lookup_internal (cairo_hash_table_t *hash_table, cairo_hash_entry_t *key, cairo_bool_t key_is_unique)
 _cairo_hash_table_lookup_internal:
static cairo_status_t _cairo_hash_table_resize (cairo_hash_table_t *hash_table)
 _cairo_hash_table_resize: : a hash table
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.
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_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
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
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

Variables

static cairo_hash_entry_t dead_entry = { 0 }
static const
cairo_hash_table_arrangement_t 
hash_table_arrangements []

Class Documentation

struct _cairo_hash_table_arrangement

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

Class Members
unsigned long high_water_mark
unsigned long rehash
unsigned long size
struct _cairo_hash_table

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

Collaboration diagram for _cairo_hash_table:
Class Members
const
cairo_hash_table_arrangement_t *
arrangement
cairo_hash_entry_t ** entries
cairo_hash_keys_equal_func_t keys_equal
unsigned long live_entries

Define Documentation

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

#define ENTRY_IS_DEAD (   entry)    ((entry) == DEAD_ENTRY)

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

#define ENTRY_IS_FREE (   entry)    ((entry) == NULL)

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

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

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


Typedef Documentation


Function Documentation

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

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:

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:

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_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_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:

static cairo_hash_entry_t** _cairo_hash_table_lookup_internal ( cairo_hash_table_t *  hash_table,
cairo_hash_entry_t key,
cairo_bool_t  key_is_unique 
) [static]

_cairo_hash_table_lookup_internal:

: a #cairo_hash_table_t to search : the key to search on : the hash_code for : If TRUE, then caller asserts that no key already exists that will compare equal to key, so search can be optimized. If unsure, set to FALSE and the code will always work.

Search the hashtable for a live entry for which hash_table->keys_equal returns true. If no such entry exists then return the first available (free or dead entry).

If the key_unique flag is set, then the search will never call hash_table->keys_equal and will act as if it always returned false. This is useful as a performance optimization in special circumstances where the caller knows that there is no existing entry in the hash table with a matching key.

Return value: The matching entry in the hash table (if any). Otherwise, the first available entry. The caller should check entry->state to check whether a match was found or not.

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

{    
    cairo_hash_entry_t **entry, **first_available = NULL;
    unsigned long table_size, i, idx, step;
    
    table_size = hash_table->arrangement->size;

    idx = key->hash % table_size;
    step = 0;

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

       if (ENTRY_IS_FREE(*entry))
       {
           return entry;
       }
       else if (ENTRY_IS_DEAD(*entry))
       {
           if (key_is_unique) {
              return entry;
           } else {
              if (! first_available)
                  first_available = entry;
           }
       }
       else /* ENTRY_IS_LIVE(*entry) */
       {
           if (! key_is_unique)
              if (hash_table->keys_equal (key, *entry))
                  return entry;
       }

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

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

    /* 
     * The table should not have permitted you to get here if you were just
     * looking for a free slot: there should have been room.
     */
    assert (key_is_unique == 0);

    return first_available;
}

Here is the caller graph for this function:

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:

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:

static cairo_status_t _cairo_hash_table_resize ( cairo_hash_table_t *  hash_table) [static]

_cairo_hash_table_resize: : a hash table

Resize the hash table if the number of entries has gotten much bigger or smaller than the ideal number of entries for the current size.

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

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

{
    cairo_hash_table_t tmp;
    cairo_hash_entry_t **entry;
    unsigned long new_size, i;

    /* This keeps the hash table between 25% and 50% full. */
    unsigned long high = hash_table->arrangement->high_water_mark;
    unsigned long low = high >> 2;

    if (hash_table->live_entries >= low && hash_table->live_entries <= high)
       return CAIRO_STATUS_SUCCESS;

    tmp = *hash_table;

    if (hash_table->live_entries > high)
    {
       tmp.arrangement = hash_table->arrangement + 1;
       /* This code is being abused if we can't make a table big enough. */
       assert (tmp.arrangement - hash_table_arrangements <
              NUM_HASH_TABLE_ARRANGEMENTS);
    }
    else /* hash_table->live_entries < low */
    {
       /* Can't shrink if we're at the smallest size */
       if (hash_table->arrangement == &hash_table_arrangements[0])
           return CAIRO_STATUS_SUCCESS;
       tmp.arrangement = hash_table->arrangement - 1;
    }

    new_size = tmp.arrangement->size;
    tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
    if (tmp.entries == NULL) 
       return CAIRO_STATUS_NO_MEMORY;
        
    for (i = 0; i < hash_table->arrangement->size; ++i) {
       if (ENTRY_IS_LIVE (hash_table->entries[i])) {
           entry = _cairo_hash_table_lookup_internal (&tmp,
                                                 hash_table->entries[i],
                                                 TRUE);
           assert (ENTRY_IS_FREE(*entry));
           *entry = hash_table->entries[i];
       }
    }

    free (hash_table->entries);
    hash_table->entries = tmp.entries;
    hash_table->arrangement = tmp.arrangement;

    return CAIRO_STATUS_SUCCESS;
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

cairo_hash_entry_t dead_entry = { 0 } [static]

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

Initial value:
 {
    { 16,            43,           41            },
    { 32,            73,           71            },
    { 64,            151,          149           },
    { 128,           283,          281           },
    { 256,           571,          569           },
    { 512,           1153,         1151          },
    { 1024,          2269,         2267          },
    { 2048,          4519,         4517          },
    { 4096,          9013,         9011          },
    { 8192,          18043,        18041         },
    { 16384,         36109,        36107         },
    { 32768,         72091,        72089         },
    { 65536,         144409,              144407        },
    { 131072,        288361,              288359        },
    { 262144,        576883,              576881        },
    { 524288,        1153459,      1153457              },
    { 1048576,              2307163,      2307161              },
    { 2097152,              4613893,      4613891              },
    { 4194304,              9227641,      9227639              },
    { 8388608,              18455029,     18455027      },
    { 16777216,             36911011,     36911009      },
    { 33554432,             73819861,     73819859      },
    { 67108864,             147639589,    147639587     },
    { 134217728,     295279081,    295279079     },
    { 268435456,     590559793,    590559791     }
}

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