Back to index

lightning-sunbird  0.9+nobinonly
cairo-hash.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * Copyright © 2004 Red Hat, Inc.
00004  * Copyright © 2005 Red Hat, Inc.
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it either under the terms of the GNU Lesser General Public
00008  * License version 2.1 as published by the Free Software Foundation
00009  * (the "LGPL") or, at your option, under the terms of the Mozilla
00010  * Public License Version 1.1 (the "MPL"). If you do not alter this
00011  * notice, a recipient may use your version of this file under either
00012  * the MPL or the LGPL.
00013  *
00014  * You should have received a copy of the LGPL along with this library
00015  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00017  * You should have received a copy of the MPL along with this library
00018  * in the file COPYING-MPL-1.1
00019  *
00020  * The contents of this file are subject to the Mozilla Public License
00021  * Version 1.1 (the "License"); you may not use this file except in
00022  * compliance with the License. You may obtain a copy of the License at
00023  * http://www.mozilla.org/MPL/
00024  *
00025  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00026  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00027  * the specific language governing rights and limitations.
00028  *
00029  * The Original Code is the cairo graphics library.
00030  *
00031  * The Initial Developer of the Original Code is Red Hat, Inc.
00032  *
00033  * Contributor(s):
00034  *      Keith Packard <keithp@keithp.com>
00035  *     Graydon Hoare <graydon@redhat.com>
00036  *     Carl Worth <cworth@cworth.org>
00037  */
00038 
00039 #include "cairoint.h"
00040 
00041 /*
00042  * An entry can be in one of three states:
00043  *
00044  * FREE: Entry has never been used, terminates all searches.
00045  *       Appears in the table as a NULL pointer.
00046  *
00047  * DEAD: Entry had been live in the past. A dead entry can be reused
00048  *       but does not terminate a search for an exact entry.
00049  *       Appears in the table as a pointer to DEAD_ENTRY.
00050  * 
00051  * LIVE: Entry is currently being used.
00052  *       Appears in the table as any non-NULL, non-DEAD_ENTRY pointer.
00053  */
00054 
00055 static cairo_hash_entry_t dead_entry = { 0 };
00056 #define DEAD_ENTRY (&dead_entry)
00057 
00058 #define ENTRY_IS_FREE(entry) ((entry) == NULL)
00059 #define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
00060 #define ENTRY_IS_LIVE(entry) ((entry) && ! ENTRY_IS_DEAD(entry))
00061 
00062 /* We expect keys will not be destroyed frequently, so our table does not
00063  * contain any explicit shrinking code nor any chain-coalescing code for
00064  * entries randomly deleted by memory pressure (except during rehashing, of
00065  * course). These assumptions are potentially bad, but they make the
00066  * implementation straightforward.
00067  *
00068  * Revisit later if evidence appears that we're using excessive memory from
00069  * a mostly-dead table.
00070  *
00071  * This table is open-addressed with double hashing. Each table size is a
00072  * prime chosen to be a little more than double the high water mark for a
00073  * given arrangement, so the tables should remain < 50% full. The table
00074  * size makes for the "first" hash modulus; a second prime (2 less than the
00075  * first prime) serves as the "second" hash modulus, which is co-prime and
00076  * thus guarantees a complete permutation of table indices.
00077  *
00078  * This structure, and accompanying table, is borrowed/modified from the
00079  * file xserver/render/glyph.c in the freedesktop.org x server, with
00080  * permission (and suggested modification of doubling sizes) by Keith
00081  * Packard.
00082  */
00083 
00084 typedef struct _cairo_hash_table_arrangement {
00085     unsigned long high_water_mark;
00086     unsigned long size;
00087     unsigned long rehash;
00088 } cairo_hash_table_arrangement_t;
00089 
00090 static const cairo_hash_table_arrangement_t hash_table_arrangements [] = {
00091     { 16,            43,           41            },
00092     { 32,            73,           71            },
00093     { 64,            151,          149           },
00094     { 128,           283,          281           },
00095     { 256,           571,          569           },
00096     { 512,           1153,         1151          },
00097     { 1024,          2269,         2267          },
00098     { 2048,          4519,         4517          },
00099     { 4096,          9013,         9011          },
00100     { 8192,          18043,        18041         },
00101     { 16384,         36109,        36107         },
00102     { 32768,         72091,        72089         },
00103     { 65536,         144409,              144407        },
00104     { 131072,        288361,              288359        },
00105     { 262144,        576883,              576881        },
00106     { 524288,        1153459,      1153457              },
00107     { 1048576,              2307163,      2307161              },
00108     { 2097152,              4613893,      4613891              },
00109     { 4194304,              9227641,      9227639              },
00110     { 8388608,              18455029,     18455027      },
00111     { 16777216,             36911011,     36911009      },
00112     { 33554432,             73819861,     73819859      },
00113     { 67108864,             147639589,    147639587     },
00114     { 134217728,     295279081,    295279079     },
00115     { 268435456,     590559793,    590559791     }
00116 };
00117 
00118 #define NUM_HASH_TABLE_ARRANGEMENTS (sizeof(hash_table_arrangements)/sizeof(hash_table_arrangements[0]))
00119 
00120 struct _cairo_hash_table {
00121     cairo_hash_keys_equal_func_t keys_equal;
00122 
00123     const cairo_hash_table_arrangement_t *arrangement;
00124     cairo_hash_entry_t **entries;
00125 
00126     unsigned long live_entries;
00127 };
00128 
00145 cairo_hash_table_t *
00146 _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
00147 {    
00148     cairo_hash_table_t *hash_table;
00149 
00150     hash_table = malloc (sizeof (cairo_hash_table_t));
00151     if (hash_table == NULL)
00152        return NULL;
00153 
00154     hash_table->keys_equal = keys_equal;
00155 
00156     hash_table->arrangement = &hash_table_arrangements[0];
00157 
00158     hash_table->entries = calloc (hash_table->arrangement->size,
00159                               sizeof(cairo_hash_entry_t *));
00160     if (hash_table->entries == NULL) {
00161        free (hash_table);
00162        return NULL;
00163     }
00164 
00165     hash_table->live_entries = 0;
00166 
00167     return hash_table;
00168 }
00169 
00183 void
00184 _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
00185 {
00186     if (hash_table == NULL)
00187        return;
00188 
00189     /* The hash table must be empty. Otherwise, halt. */
00190     assert (hash_table->live_entries == 0);
00191        
00192     free (hash_table->entries);
00193     hash_table->entries = NULL;
00194 
00195     free (hash_table);
00196 }
00197 
00222 static cairo_hash_entry_t **
00223 _cairo_hash_table_lookup_internal (cairo_hash_table_t *hash_table,
00224                                cairo_hash_entry_t *key,
00225                                cairo_bool_t             key_is_unique)
00226 {    
00227     cairo_hash_entry_t **entry, **first_available = NULL;
00228     unsigned long table_size, i, idx, step;
00229     
00230     table_size = hash_table->arrangement->size;
00231 
00232     idx = key->hash % table_size;
00233     step = 0;
00234 
00235     for (i = 0; i < table_size; ++i)
00236     {
00237        entry = &hash_table->entries[idx];
00238 
00239        if (ENTRY_IS_FREE(*entry))
00240        {
00241            return entry;
00242        }
00243        else if (ENTRY_IS_DEAD(*entry))
00244        {
00245            if (key_is_unique) {
00246               return entry;
00247            } else {
00248               if (! first_available)
00249                   first_available = entry;
00250            }
00251        }
00252        else /* ENTRY_IS_LIVE(*entry) */
00253        {
00254            if (! key_is_unique)
00255               if (hash_table->keys_equal (key, *entry))
00256                   return entry;
00257        }
00258 
00259        if (step == 0) {         
00260            step = key->hash % hash_table->arrangement->rehash;
00261            if (step == 0)
00262               step = 1;
00263        }
00264 
00265        idx += step;
00266        if (idx >= table_size)
00267            idx -= table_size;
00268     }
00269 
00270     /* 
00271      * The table should not have permitted you to get here if you were just
00272      * looking for a free slot: there should have been room.
00273      */
00274     assert (key_is_unique == 0);
00275 
00276     return first_available;
00277 }
00278 
00290 static cairo_status_t
00291 _cairo_hash_table_resize  (cairo_hash_table_t *hash_table)
00292 {
00293     cairo_hash_table_t tmp;
00294     cairo_hash_entry_t **entry;
00295     unsigned long new_size, i;
00296 
00297     /* This keeps the hash table between 25% and 50% full. */
00298     unsigned long high = hash_table->arrangement->high_water_mark;
00299     unsigned long low = high >> 2;
00300 
00301     if (hash_table->live_entries >= low && hash_table->live_entries <= high)
00302        return CAIRO_STATUS_SUCCESS;
00303 
00304     tmp = *hash_table;
00305 
00306     if (hash_table->live_entries > high)
00307     {
00308        tmp.arrangement = hash_table->arrangement + 1;
00309        /* This code is being abused if we can't make a table big enough. */
00310        assert (tmp.arrangement - hash_table_arrangements <
00311               NUM_HASH_TABLE_ARRANGEMENTS);
00312     }
00313     else /* hash_table->live_entries < low */
00314     {
00315        /* Can't shrink if we're at the smallest size */
00316        if (hash_table->arrangement == &hash_table_arrangements[0])
00317            return CAIRO_STATUS_SUCCESS;
00318        tmp.arrangement = hash_table->arrangement - 1;
00319     }
00320 
00321     new_size = tmp.arrangement->size;
00322     tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
00323     if (tmp.entries == NULL) 
00324        return CAIRO_STATUS_NO_MEMORY;
00325         
00326     for (i = 0; i < hash_table->arrangement->size; ++i) {
00327        if (ENTRY_IS_LIVE (hash_table->entries[i])) {
00328            entry = _cairo_hash_table_lookup_internal (&tmp,
00329                                                  hash_table->entries[i],
00330                                                  TRUE);
00331            assert (ENTRY_IS_FREE(*entry));
00332            *entry = hash_table->entries[i];
00333        }
00334     }
00335 
00336     free (hash_table->entries);
00337     hash_table->entries = tmp.entries;
00338     hash_table->arrangement = tmp.arrangement;
00339 
00340     return CAIRO_STATUS_SUCCESS;
00341 }
00342 
00357 cairo_bool_t
00358 _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
00359                        cairo_hash_entry_t *key,
00360                        cairo_hash_entry_t **entry_return)
00361 {
00362     cairo_hash_entry_t **entry;
00363 
00364     /* See if we have an entry in the table already. */
00365     entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE);
00366     if (ENTRY_IS_LIVE(*entry)) {
00367        *entry_return = *entry;
00368        return TRUE;
00369     }
00370 
00371     *entry_return = NULL;
00372     return FALSE;
00373 }
00374 
00395 void *
00396 _cairo_hash_table_random_entry (cairo_hash_table_t         *hash_table,
00397                             cairo_hash_predicate_func_t predicate)
00398 {
00399     cairo_hash_entry_t **entry;
00400     unsigned long hash;
00401     unsigned long table_size, i, idx, step;
00402 
00403     table_size = hash_table->arrangement->size;
00404 
00405     hash = rand ();
00406     idx = hash % table_size;
00407     step = 0;
00408 
00409     for (i = 0; i < table_size; ++i)
00410     {
00411        entry = &hash_table->entries[idx];
00412 
00413        if (ENTRY_IS_LIVE (*entry) &&
00414            (predicate == NULL || predicate (*entry)))
00415        {
00416            return *entry;
00417        }
00418 
00419        if (step == 0) {         
00420            step = hash % hash_table->arrangement->rehash;
00421            if (step == 0)
00422               step = 1;
00423        }
00424 
00425        idx += step;
00426        if (idx >= table_size)
00427            idx -= table_size;
00428     }
00429 
00430     return NULL;
00431 }
00432 
00450 cairo_status_t
00451 _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
00452                        cairo_hash_entry_t *key_and_value)
00453 {
00454     cairo_status_t status;
00455     cairo_hash_entry_t **entry;
00456     
00457     entry = _cairo_hash_table_lookup_internal (hash_table,
00458                                           key_and_value, FALSE);
00459     
00460     if (ENTRY_IS_LIVE(*entry))
00461     {
00462        /* User is being bad, let's crash. */
00463        ASSERT_NOT_REACHED;
00464     }
00465 
00466     *entry = key_and_value;
00467     hash_table->live_entries++;
00468 
00469     status = _cairo_hash_table_resize (hash_table);
00470     if (status)
00471        return status;
00472 
00473     return CAIRO_STATUS_SUCCESS;
00474 }
00475 
00488 void
00489 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
00490                        cairo_hash_entry_t *key)
00491 {
00492     cairo_hash_entry_t **entry;
00493 
00494     entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE);
00495     if (! ENTRY_IS_LIVE(*entry))
00496        return;
00497 
00498     *entry = DEAD_ENTRY;
00499     hash_table->live_entries--;
00500 
00501     /* This call _can_ fail, but only in failing to allocate new
00502      * memory to shrink the hash table. It does leave the table in a
00503      * consistent state, and we've already succeeded in removing the
00504      * entry, so we don't examine the failure status of this call. */
00505     _cairo_hash_table_resize (hash_table);
00506 }
00507 
00517 void
00518 _cairo_hash_table_foreach (cairo_hash_table_t          *hash_table,
00519                         cairo_hash_callback_func_t  hash_callback,
00520                         void                           *closure)
00521 {
00522     unsigned long i;
00523     cairo_hash_entry_t *entry;
00524 
00525     if (hash_table == NULL)
00526        return;
00527        
00528     for (i = 0; i < hash_table->arrangement->size; i++) {
00529        entry = hash_table->entries[i];
00530        if (ENTRY_IS_LIVE(entry))
00531            hash_callback (entry, closure);
00532     }
00533 }