src/cairo-hash.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2004 Red Hat, Inc.
   4  * Copyright © 2005 Red Hat, Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it either under the terms of the GNU Lesser General Public
   8  * License version 2.1 as published by the Free Software Foundation
   9  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11  * notice, a recipient may use your version of this file under either
  12  * the MPL or the LGPL.
  13  *
  14  * You should have received a copy of the LGPL along with this library
  15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  17  * You should have received a copy of the MPL along with this library
  18  * in the file COPYING-MPL-1.1
  19  *
  20  * The contents of this file are subject to the Mozilla Public License
  21  * Version 1.1 (the "License"); you may not use this file except in
  22  * compliance with the License. You may obtain a copy of the License at
  23  * http://www.mozilla.org/MPL/
  24  *
  25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  27  * the specific language governing rights and limitations.
  28  *
  29  * The Original Code is the cairo graphics library.
  30  *
  31  * The Initial Developer of the Original Code is Red Hat, Inc.
  32  *
  33  * Contributor(s):
  34  *      Keith Packard <keithp@keithp.com>
  35  *      Graydon Hoare <graydon@redhat.com>
  36  *      Carl Worth <cworth@cworth.org>
  37  */
  38
  39 #include "cairoint.h"
  40 #include "cairo-error-private.h"
  41
  42 /*
  43  * An entry can be in one of three states:
  44  *
  45  * FREE: Entry has never been used, terminates all searches.
  46  *       Appears in the table as a %NULL pointer.
  47  *
  48  * DEAD: Entry had been live in the past. A dead entry can be reused
  49  *       but does not terminate a search for an exact entry.
  50  *       Appears in the table as a pointer to DEAD_ENTRY.
  51  *
  52  * LIVE: Entry is currently being used.
  53  *       Appears in the table as any non-%NULL, non-DEAD_ENTRY pointer.
  54  */
  55
  56 #define DEAD_ENTRY ((cairo_hash_entry_t *) 0x1)
  57
  58 #define ENTRY_IS_FREE(entry) ((entry) == NULL)
  59 #define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
  60 #define ENTRY_IS_LIVE(entry) ((entry) >  DEAD_ENTRY)
  61
  62 /*
  63  * This table is open-addressed with double hashing. Each table size
  64  * is a prime and it makes for the "first" hash modulus; a second
  65  * prime (2 less than the first prime) serves as the "second" hash
  66  * modulus, which is smaller and thus guarantees a complete
  67  * permutation of table indices.
  68  *
  69  * Hash tables are rehashed in order to keep between 12.5% and 50%
  70  * entries in the hash table alive and at least 25% free. When table
  71  * size is changed, the new table has about 25% live elements.
  72  *
  73  * The free entries guarantee an expected constant-time lookup.
  74  * Doubling/halving the table in the described fashion guarantees
  75  * amortized O(1) insertion/removal.
  76  *
  77  * This structure, and accompanying table, is borrowed/modified from the
  78  * file xserver/render/glyph.c in the freedesktop.org x server, with
  79  * permission (and suggested modification of doubling sizes) by Keith
  80  * Packard.
  81  */
  82
  83 static const unsigned long hash_table_sizes[] = {
  84     43,
  85     73,
  86     151,
  87     283,
  88     571,
  89     1153,
  90     2269,
  91     4519,
  92     9013,
  93     18043,
  94     36109,
  95     72091,
  96     144409,
  97     288361,
  98     576883,
  99     1153459,
 100     2307163,
 101     4613893,
 102     9227641,
 103     18455029,
 104     36911011,
 105     73819861,
 106     147639589,
 107     295279081,
 108     590559793
 109 };
 110
 111 struct _cairo_hash_table {
 112     cairo_hash_keys_equal_func_t keys_equal;
 113
 114     cairo_hash_entry_t *cache[32];
 115
 116     const unsigned long *table_size;
 117     cairo_hash_entry_t **entries;
 118
 119     unsigned long live_entries;
 120     unsigned long free_entries;
 121     unsigned long iterating;   /* Iterating, no insert, no resize */
 122 };
 123
 124 /**
 125  * _cairo_hash_table_uid_keys_equal:
 126  * @key_a: the first key to be compared
 127  * @key_b: the second key to be compared
 128  *
 129  * Provides a #cairo_hash_keys_equal_func_t which always returns
 130  * %TRUE. This is useful to create hash tables using keys whose hash
 131  * completely describes the key, because in this special case
 132  * comparing the hashes is sufficient to guarantee that the keys are
 133  * equal.
 134  *
 135  * Return value: %TRUE.
 136  **/
 137 static cairo_bool_t
 138 _cairo_hash_table_uid_keys_equal (const void *key_a, const void *key_b)
 139 {
 140     return TRUE;
 141 }
 142
 143 /**
 144  * _cairo_hash_table_create:
 145  * @keys_equal: a function to return %TRUE if two keys are equal
 146  *
 147  * Creates a new hash table which will use the keys_equal() function
 148  * to compare hash keys. Data is provided to the hash table in the
 149  * form of user-derived versions of #cairo_hash_entry_t. A hash entry
 150  * must be able to hold both a key (including a hash code) and a
 151  * value. Sometimes only the key will be necessary, (as in
 152  * _cairo_hash_table_remove), and other times both a key and a value
 153  * will be necessary, (as in _cairo_hash_table_insert).
 154  *
 155  * If @keys_equal is %NULL, two keys will be considered equal if and
 156  * only if their hashes are equal.
 157  *
 158  * See #cairo_hash_entry_t for more details.
 159  *
 160  * Return value: the new hash table or %NULL if out of memory.
 161  **/
 162 cairo_hash_table_t *
 163 _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
 164 {
 165     cairo_hash_table_t *hash_table;
 166
 167     hash_table = malloc (sizeof (cairo_hash_table_t));
 168     if (unlikely (hash_table == NULL)) {
 169         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 170         return NULL;
 171     }
 172
 173     if (keys_equal == NULL)
 174         hash_table->keys_equal = _cairo_hash_table_uid_keys_equal;
 175     else
 176         hash_table->keys_equal = keys_equal;
 177
 178     memset (&hash_table->cache, 0, sizeof (hash_table->cache));
 179     hash_table->table_size = &hash_table_sizes[0];
 180
 181     hash_table->entries = calloc (*hash_table->table_size,
 182                                   sizeof (cairo_hash_entry_t *));
 183     if (unlikely (hash_table->entries == NULL)) {
 184         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 185         free (hash_table);
 186         return NULL;
 187     }
 188
 189     hash_table->live_entries = 0;
 190     hash_table->free_entries = *hash_table->table_size;
 191     hash_table->iterating = 0;
 192
 193     return hash_table;
 194 }
 195
 196 /**
 197  * _cairo_hash_table_destroy:
 198  * @hash_table: an empty hash table to destroy
 199  *
 200  * Immediately destroys the given hash table, freeing all resources
 201  * associated with it.
 202  *
 203  * WARNING: The hash_table must have no live entries in it before
 204  * _cairo_hash_table_destroy is called. It is a fatal error otherwise,
 205  * and this function will halt. The rationale for this behavior is to
 206  * avoid memory leaks and to avoid needless complication of the API
 207  * with destroy notifiy callbacks.
 208  *
 209  * WARNING: The hash_table must have no running iterators in it when
 210  * _cairo_hash_table_destroy is called. It is a fatal error otherwise,
 211  * and this function will halt.
 212  **/
 213 void
 214 _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
 215 {
 216     /* The hash table must be empty. Otherwise, halt. */
 217     assert (hash_table->live_entries == 0);
 218     /* No iterators can be running. Otherwise, halt. */
 219     assert (hash_table->iterating == 0);
 220
 221     free (hash_table->entries);
 222     free (hash_table);
 223 }
 224
 225 static cairo_hash_entry_t **
 226 _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table,
 227                                      cairo_hash_entry_t *key)
 228 {
 229     unsigned long table_size, i, idx, step;
 230     cairo_hash_entry_t **entry;
 231
 232     table_size = *hash_table->table_size;
 233     idx = key->hash % table_size;
 234
 235     entry = &hash_table->entries[idx];
 236     if (! ENTRY_IS_LIVE (*entry))
 237         return entry;
 238
 239     i = 1;
 240     step = 1 + key->hash % (table_size - 2);
 241     do {
 242         idx += step;
 243         if (idx >= table_size)
 244             idx -= table_size;
 245
 246         entry = &hash_table->entries[idx];
 247         if (! ENTRY_IS_LIVE (*entry))
 248             return entry;
 249     } while (++i < table_size);
 250
 251     ASSERT_NOT_REACHED;
 252     return NULL;
 253 }
 254
 255 /**
 256  * _cairo_hash_table_manage:
 257  * @hash_table: a hash table
 258  *
 259  * Resize the hash table if the number of entries has gotten much
 260  * bigger or smaller than the ideal number of entries for the current
 261  * size and guarantee some free entries to be used as lookup
 262  * termination points.
 263  *
 264  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 265  * %CAIRO_STATUS_NO_MEMORY if out of memory.
 266  **/
 267 static cairo_status_t
 268 _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
 269 {
 270     cairo_hash_table_t tmp;
 271     unsigned long new_size, i;
 272
 273     /* Keep between 12.5% and 50% entries in the hash table alive and
 274      * at least 25% free. */
 275     unsigned long live_high = *hash_table->table_size >> 1;
 276     unsigned long live_low = live_high >> 2;
 277     unsigned long free_low = live_high >> 1;
 278
 279     tmp = *hash_table;
 280
 281     if (hash_table->live_entries > live_high)
 282     {
 283         tmp.table_size = hash_table->table_size + 1;
 284         /* This code is being abused if we can't make a table big enough. */
 285         assert (tmp.table_size - hash_table_sizes <
 286                 ARRAY_LENGTH (hash_table_sizes));
 287     }
 288     else if (hash_table->live_entries < live_low)
 289     {
 290         /* Can't shrink if we're at the smallest size */
 291         if (hash_table->table_size == &hash_table_sizes[0])
 292             tmp.table_size = hash_table->table_size;
 293         else
 294             tmp.table_size = hash_table->table_size - 1;
 295     }
 296
 297     if (tmp.table_size == hash_table->table_size &&
 298         hash_table->free_entries > free_low)
 299     {
 300         /* The number of live entries is within the desired bounds
 301          * (we're not going to resize the table) and we have enough
 302          * free entries. Do nothing. */
 303         return CAIRO_STATUS_SUCCESS;
 304     }
 305
 306     new_size = *tmp.table_size;
 307     tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
 308     if (unlikely (tmp.entries == NULL))
 309         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 310
 311     for (i = 0; i < *hash_table->table_size; ++i) {
 312         if (ENTRY_IS_LIVE (hash_table->entries[i])) {
 313             *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
 314                 = hash_table->entries[i];
 315         }
 316     }
 317
 318     free (hash_table->entries);
 319     hash_table->entries = tmp.entries;
 320     hash_table->table_size = tmp.table_size;
 321     hash_table->free_entries = new_size - hash_table->live_entries;
 322
 323     return CAIRO_STATUS_SUCCESS;
 324 }
 325
 326 /**
 327  * _cairo_hash_table_lookup:
 328  * @hash_table: a hash table
 329  * @key: the key of interest
 330  *
 331  * Performs a lookup in @hash_table looking for an entry which has a
 332  * key that matches @key, (as determined by the keys_equal() function
 333  * passed to _cairo_hash_table_create).
 334  *
 335  * Return value: the matching entry, of %NULL if no match was found.
 336  **/
 337 void *
 338 _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 339                           cairo_hash_entry_t *key)
 340 {
 341     cairo_hash_entry_t *entry;
 342     unsigned long table_size, i, idx, step;
 343     unsigned long hash = key->hash;
 344
 345     entry = hash_table->cache[hash & 31];
 346     if (entry && entry->hash == hash && hash_table->keys_equal (key, entry))
 347         return entry;
 348
 349     table_size = *hash_table->table_size;
 350     idx = hash % table_size;
 351
 352     entry = hash_table->entries[idx];
 353     if (ENTRY_IS_LIVE (entry)) {
 354         if (entry->hash == hash && hash_table->keys_equal (key, entry))
 355                 goto insert_cache;
 356     } else if (ENTRY_IS_FREE (entry))
 357         return NULL;
 358
 359     i = 1;
 360     step = 1 + hash % (table_size - 2);
 361     do {
 362         idx += step;
 363         if (idx >= table_size)
 364             idx -= table_size;
 365
 366         entry = hash_table->entries[idx];
 367         if (ENTRY_IS_LIVE (entry)) {
 368             if (entry->hash == hash && hash_table->keys_equal (key, entry))
 369                     goto insert_cache;
 370         } else if (ENTRY_IS_FREE (entry))
 371             return NULL;
 372     } while (++i < table_size);
 373
 374     ASSERT_NOT_REACHED;
 375     return NULL;
 376
 377 insert_cache:
 378     hash_table->cache[hash & 31] = entry;
 379     return entry;
 380 }
 381
 382 /**
 383  * _cairo_hash_table_random_entry:
 384  * @hash_table: a hash table
 385  * @predicate: a predicate function.
 386  *
 387  * Find a random entry in the hash table satisfying the given
 388  * @predicate.
 389  *
 390  * We use the same algorithm as the lookup algorithm to walk over the
 391  * entries in the hash table in a pseudo-random order. Walking
 392  * linearly would favor entries following gaps in the hash table. We
 393  * could also call rand() repeatedly, which works well for almost-full
 394  * tables, but degrades when the table is almost empty, or predicate
 395  * returns %TRUE for most entries.
 396  *
 397  * Return value: a random live entry or %NULL if there are no entries
 398  * that match the given predicate. In particular, if predicate is
 399  * %NULL, a %NULL return value indicates that the table is empty.
 400  **/
 401 void *
 402 _cairo_hash_table_random_entry (cairo_hash_table_t         *hash_table,
 403                                 cairo_hash_predicate_func_t predicate)
 404 {
 405     cairo_hash_entry_t *entry;
 406     unsigned long hash;
 407     unsigned long table_size, i, idx, step;
 408
 409     assert (predicate != NULL);
 410
 411     table_size = *hash_table->table_size;
 412     hash = rand ();
 413     idx = hash % table_size;
 414
 415     entry = hash_table->entries[idx];
 416     if (ENTRY_IS_LIVE (entry) && predicate (entry))
 417         return entry;
 418
 419     i = 1;
 420     step = 1 + hash % (table_size - 2);
 421     do {
 422         idx += step;
 423         if (idx >= table_size)
 424             idx -= table_size;
 425
 426         entry = hash_table->entries[idx];
 427         if (ENTRY_IS_LIVE (entry) && predicate (entry))
 428             return entry;
 429     } while (++i < table_size);
 430
 431     return NULL;
 432 }
 433
 434 /**
 435  * _cairo_hash_table_insert:
 436  * @hash_table: a hash table
 437  * @key_and_value: an entry to be inserted
 438  *
 439  * Insert the entry #key_and_value into the hash table.
 440  *
 441  * WARNING: There must not be an existing entry in the hash table
 442  * with a matching key.
 443  *
 444  * WARNING: It is a fatal error to insert an element while
 445  * an iterator is running
 446  *
 447  * Instead of using insert to replace an entry, consider just editing
 448  * the entry obtained with _cairo_hash_table_lookup. Or if absolutely
 449  * necessary, use _cairo_hash_table_remove first.
 450  *
 451  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 452  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
 453  **/
 454 cairo_status_t
 455 _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
 456                           cairo_hash_entry_t *key_and_value)
 457 {
 458     cairo_hash_entry_t **entry;
 459     cairo_status_t status;
 460
 461     /* Insert is illegal while an iterator is running. */
 462     assert (hash_table->iterating == 0);
 463
 464     status = _cairo_hash_table_manage (hash_table);
 465     if (unlikely (status))
 466         return status;
 467
 468     entry = _cairo_hash_table_lookup_unique_key (hash_table, key_and_value);
 469
 470     if (ENTRY_IS_FREE (*entry))
 471         hash_table->free_entries--;
 472
 473     *entry = key_and_value;
 474     hash_table->cache[key_and_value->hash & 31] = key_and_value;
 475     hash_table->live_entries++;
 476
 477     return CAIRO_STATUS_SUCCESS;
 478 }
 479
 480 static cairo_hash_entry_t **
 481 _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table,
 482                                     cairo_hash_entry_t *key)
 483 {
 484     unsigned long table_size, i, idx, step;
 485     cairo_hash_entry_t **entry;
 486
 487     table_size = *hash_table->table_size;
 488     idx = key->hash % table_size;
 489
 490     entry = &hash_table->entries[idx];
 491     if (*entry == key)
 492         return entry;
 493
 494     i = 1;
 495     step = 1 + key->hash % (table_size - 2);
 496     do {
 497         idx += step;
 498         if (idx >= table_size)
 499             idx -= table_size;
 500
 501         entry = &hash_table->entries[idx];
 502         if (*entry == key)
 503             return entry;
 504     } while (++i < table_size);
 505
 506     ASSERT_NOT_REACHED;
 507     return NULL;
 508 }
 509 /**
 510  * _cairo_hash_table_remove:
 511  * @hash_table: a hash table
 512  * @key: key of entry to be removed
 513  *
 514  * Remove an entry from the hash table which points to @key.
 515  *
 516  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 517  * %CAIRO_STATUS_NO_MEMORY if out of memory.
 518  **/
 519 void
 520 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
 521                           cairo_hash_entry_t *key)
 522 {
 523     *_cairo_hash_table_lookup_exact_key (hash_table, key) = DEAD_ENTRY;
 524     hash_table->live_entries--;
 525     hash_table->cache[key->hash & 31] = NULL;
 526
 527     /* Check for table resize. Don't do this when iterating as this will
 528      * reorder elements of the table and cause the iteration to potentially
 529      * skip some elements. */
 530     if (hash_table->iterating == 0) {
 531         /* This call _can_ fail, but only in failing to allocate new
 532          * memory to shrink the hash table. It does leave the table in a
 533          * consistent state, and we've already succeeded in removing the
 534          * entry, so we don't examine the failure status of this call. */
 535         _cairo_hash_table_manage (hash_table);
 536     }
 537 }
 538
 539 /**
 540  * _cairo_hash_table_foreach:
 541  * @hash_table: a hash table
 542  * @hash_callback: function to be called for each live entry
 543  * @closure: additional argument to be passed to @hash_callback
 544  *
 545  * Call @hash_callback for each live entry in the hash table, in a
 546  * non-specified order.
 547  *
 548  * Entries in @hash_table may be removed by code executed from @hash_callback.
 549  *
 550  * Entries may not be inserted to @hash_table, nor may @hash_table
 551  * be destroyed by code executed from @hash_callback. The relevant
 552  * functions will halt in these cases.
 553  **/
 554 void
 555 _cairo_hash_table_foreach (cairo_hash_table_t         *hash_table,
 556                            cairo_hash_callback_func_t  hash_callback,
 557                            void                       *closure)
 558 {
 559     unsigned long i;
 560     cairo_hash_entry_t *entry;
 561
 562     /* Mark the table for iteration */
 563     ++hash_table->iterating;
 564     for (i = 0; i < *hash_table->table_size; i++) {
 565         entry = hash_table->entries[i];
 566         if (ENTRY_IS_LIVE(entry))
 567             hash_callback (entry, closure);
 568     }
 569     /* If some elements were deleted during the iteration,
 570      * the table may need resizing. Just do this every time
 571      * as the check is inexpensive.
 572      */
 573     if (--hash_table->iterating == 0) {
 574         /* Should we fail to shrink the hash table, it is left unaltered,
 575          * and we don't need to propagate the error status. */
 576         _cairo_hash_table_manage (hash_table);
 577     }
 578 }