util/cairo-script/cairo-script-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  *      Karl Tomlinson <karlt+@karlt.net>, Mozilla Corporation
  38  */
  39
  40 #include "cairo-script-private.h"
  41
  42 #include <stdlib.h>
  43
  44 /*
  45  * An entry can be in one of three states:
  46  *
  47  * FREE: Entry has never been used, terminates all searches.
  48  *       Appears in the table as a %NULL pointer.
  49  *
  50  * DEAD: Entry had been live in the past. A dead entry can be reused
  51  *       but does not terminate a search for an exact entry.
  52  *       Appears in the table as a pointer to DEAD_ENTRY.
  53  *
  54  * LIVE: Entry is currently being used.
  55  *       Appears in the table as any non-%NULL, non-DEAD_ENTRY pointer.
  56  */
  57
  58 #define DEAD_ENTRY ((csi_hash_entry_t *) 0x1)
  59
  60 #define ENTRY_IS_FREE(entry) ((entry) == NULL)
  61 #define ENTRY_IS_DEAD(entry) ((entry) == DEAD_ENTRY)
  62 #define ENTRY_IS_LIVE(entry) ((entry) >  DEAD_ENTRY)
  63
  64
  65 /* This table is open-addressed with double hashing. Each table size is a
  66  * prime chosen to be a little more than double the high water mark for a
  67  * given arrangement, so the tables should remain < 50% full. The table
  68  * size makes for the "first" hash modulus; a second prime (2 less than the
  69  * first prime) serves as the "second" hash modulus, which is co-prime and
  70  * thus guarantees a complete permutation of table indices.
  71  *
  72  * This structure, and accompanying table, is borrowed/modified from the
  73  * file xserver/render/glyph.c in the freedesktop.org x server, with
  74  * permission (and suggested modification of doubling sizes) by Keith
  75  * Packard.
  76  */
  77
  78 static const csi_hash_table_arrangement_t hash_table_arrangements [] = {
  79     { 16,               43,             41              },
  80     { 32,               73,             71              },
  81     { 64,               151,            149             },
  82     { 128,              283,            281             },
  83     { 256,              571,            569             },
  84     { 512,              1153,           1151            },
  85     { 1024,             2269,           2267            },
  86     { 2048,             4519,           4517            },
  87     { 4096,             9013,           9011            },
  88     { 8192,             18043,          18041           },
  89     { 16384,            36109,          36107           },
  90     { 32768,            72091,          72089           },
  91     { 65536,            144409,         144407          },
  92     { 131072,           288361,         288359          },
  93     { 262144,           576883,         576881          },
  94     { 524288,           1153459,        1153457         },
  95     { 1048576,          2307163,        2307161         },
  96     { 2097152,          4613893,        4613891         },
  97     { 4194304,          9227641,        9227639         },
  98     { 8388608,          18455029,       18455027        },
  99     { 16777216,         36911011,       36911009        },
 100     { 33554432,         73819861,       73819859        },
 101     { 67108864,         147639589,      147639587       },
 102     { 134217728,        295279081,      295279079       },
 103     { 268435456,        590559793,      590559791       }
 104 };
 105
 106 #define NUM_HASH_TABLE_ARRANGEMENTS ARRAY_LENGTH (hash_table_arrangements)
 107
 108 /**
 109  * _csi_hash_table_create:
 110  * @keys_equal: a function to return %TRUE if two keys are equal
 111  *
 112  * Creates a new hash table which will use the keys_equal() function
 113  * to compare hash keys. Data is provided to the hash table in the
 114  * form of user-derived versions of #csi_hash_entry_t. A hash entry
 115  * must be able to hold both a key (including a hash code) and a
 116  * value. Sometimes only the key will be necessary, (as in
 117  * _csi_hash_table_remove), and other times both a key and a value
 118  * will be necessary, (as in _csi_hash_table_insert).
 119  *
 120  * See #csi_hash_entry_t for more details.
 121  *
 122  * Return value: the new hash table or %NULL if out of memory.
 123  **/
 124 csi_status_t
 125 _csi_hash_table_init (csi_hash_table_t *hash_table,
 126                       csi_hash_keys_equal_func_t keys_equal)
 127 {
 128     hash_table->keys_equal = keys_equal;
 129
 130     hash_table->arrangement = &hash_table_arrangements[0];
 131
 132     hash_table->entries = calloc (hash_table->arrangement->size,
 133                                   sizeof(csi_hash_entry_t *));
 134     if (hash_table->entries == NULL)
 135         return _csi_error (CAIRO_STATUS_NO_MEMORY);
 136
 137     hash_table->live_entries = 0;
 138     hash_table->used_entries = 0;
 139     hash_table->iterating = 0;
 140
 141     return CSI_STATUS_SUCCESS;
 142 }
 143
 144 /**
 145  * _csi_hash_table_destroy:
 146  * @hash_table: an empty hash table to destroy
 147  *
 148  * Immediately destroys the given hash table, freeing all resources
 149  * associated with it.
 150  *
 151  * WARNING: The hash_table must have no live entries in it before
 152  * _csi_hash_table_destroy is called. It is a fatal error otherwise,
 153  * and this function will halt. The rationale for this behavior is to
 154  * avoid memory leaks and to avoid needless complication of the API
 155  * with destroy notifiy callbacks.
 156  *
 157  * WARNING: The hash_table must have no running iterators in it when
 158  * _csi_hash_table_destroy is called. It is a fatal error otherwise,
 159  * and this function will halt.
 160  **/
 161 void
 162 _csi_hash_table_fini (csi_hash_table_t *hash_table)
 163 {
 164     free (hash_table->entries);
 165 }
 166
 167 static csi_hash_entry_t **
 168 _csi_hash_table_lookup_unique_key (csi_hash_table_t *hash_table,
 169                                      csi_hash_entry_t *key)
 170 {
 171     unsigned long table_size, i, idx, step;
 172     csi_hash_entry_t **entry;
 173
 174     table_size = hash_table->arrangement->size;
 175     idx = key->hash % table_size;
 176
 177     entry = &hash_table->entries[idx];
 178     if (! ENTRY_IS_LIVE (*entry))
 179         return entry;
 180
 181     i = 1;
 182     step = key->hash % hash_table->arrangement->rehash;
 183     if (step == 0)
 184         step = 1;
 185     do {
 186         idx += step;
 187         if (idx >= table_size)
 188             idx -= table_size;
 189
 190         entry = &hash_table->entries[idx];
 191         if (! ENTRY_IS_LIVE (*entry))
 192             return entry;
 193     } while (++i < table_size);
 194
 195     return NULL;
 196 }
 197
 198 /**
 199  * _csi_hash_table_manage:
 200  * @hash_table: a hash table
 201  *
 202  * Resize the hash table if the number of entries has gotten much
 203  * bigger or smaller than the ideal number of entries for the current
 204  * size, or control the number of dead entries by moving the entries
 205  * within the table.
 206  *
 207  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 208  * %CAIRO_STATUS_NO_MEMORY if out of memory.
 209  **/
 210 static csi_status_t
 211 _csi_hash_table_manage (csi_hash_table_t *hash_table)
 212 {
 213     csi_hash_table_t tmp;
 214     csi_boolean_t realloc = TRUE;
 215     unsigned long i;
 216
 217     /* This keeps the size of the hash table between 2 and approximately 8
 218      * times the number of live entries and keeps the proportion of free
 219      * entries (search-terminations) > 25%.
 220      */
 221     unsigned long high = hash_table->arrangement->high_water_mark;
 222     unsigned long low = high >> 2;
 223     unsigned long max_used = high  + high / 2;
 224
 225     tmp = *hash_table;
 226
 227     if (hash_table->live_entries > high) {
 228         tmp.arrangement = hash_table->arrangement + 1;
 229         /* This code is being abused if we can't make a table big enough. */
 230     } else if (hash_table->live_entries < low &&
 231                /* Can't shrink if we're at the smallest size */
 232                hash_table->arrangement != &hash_table_arrangements[0])
 233     {
 234         tmp.arrangement = hash_table->arrangement - 1;
 235     }
 236     else if (hash_table->used_entries > max_used)
 237     {
 238         /* Clean out dead entries to prevent lookups from becoming too slow. */
 239         for (i = 0; i < hash_table->arrangement->size; ++i) {
 240             if (ENTRY_IS_DEAD (hash_table->entries[i]))
 241                 hash_table->entries[i] = NULL;
 242         }
 243         hash_table->used_entries = hash_table->live_entries;
 244
 245         /* There is no need to reallocate but some entries may need to be
 246          * moved.  Typically the proportion of entries needing to be moved is
 247          * small, but, if the moving should leave a large number of dead
 248          * entries, they will be cleaned out next time this code is
 249          * executed. */
 250         realloc = FALSE;
 251     }
 252     else
 253     {
 254         return CAIRO_STATUS_SUCCESS;
 255     }
 256
 257     if (realloc) {
 258         tmp.entries = calloc (tmp.arrangement->size,
 259                               sizeof (csi_hash_entry_t*));
 260         if (tmp.entries == NULL)
 261             return _csi_error (CAIRO_STATUS_NO_MEMORY);
 262
 263         hash_table->used_entries = 0;
 264     }
 265
 266     for (i = 0; i < hash_table->arrangement->size; ++i) {
 267         csi_hash_entry_t *entry, **pos;
 268
 269         entry = hash_table->entries[i];
 270         if (ENTRY_IS_LIVE (entry)) {
 271             hash_table->entries[i] = DEAD_ENTRY;
 272
 273             pos = _csi_hash_table_lookup_unique_key (&tmp, entry);
 274             if (pos == NULL) {
 275                 if (realloc)
 276                     free (tmp.entries);
 277                 return _csi_error (CAIRO_STATUS_NULL_POINTER);
 278             }
 279
 280             if (ENTRY_IS_FREE (*pos))
 281                 hash_table->used_entries++;
 282
 283             *pos = entry;
 284         }
 285     }
 286
 287     if (realloc) {
 288         free (hash_table->entries);
 289         hash_table->entries = tmp.entries;
 290         hash_table->arrangement = tmp.arrangement;
 291     }
 292
 293     return CAIRO_STATUS_SUCCESS;
 294 }
 295
 296 /**
 297  * _csi_hash_table_lookup:
 298  * @hash_table: a hash table
 299  * @key: the key of interest
 300  *
 301  * Performs a lookup in @hash_table looking for an entry which has a
 302  * key that matches @key, (as determined by the keys_equal() function
 303  * passed to _csi_hash_table_create).
 304  *
 305  * Return value: the matching entry, of %NULL if no match was found.
 306  **/
 307 void *
 308 _csi_hash_table_lookup (csi_hash_table_t *hash_table,
 309                         csi_hash_entry_t *key)
 310 {
 311     csi_hash_entry_t **entry;
 312     unsigned long table_size, i, idx, step;
 313
 314     table_size = hash_table->arrangement->size;
 315     idx = key->hash % table_size;
 316     entry = &hash_table->entries[idx];
 317
 318     if (ENTRY_IS_LIVE (*entry)) {
 319         if ((*entry)->hash == key->hash && hash_table->keys_equal (key, *entry))
 320             return *entry;
 321     } else if (ENTRY_IS_FREE (*entry))
 322         return NULL;
 323
 324     i = 1;
 325     step = key->hash % hash_table->arrangement->rehash;
 326     if (step == 0)
 327         step = 1;
 328     do {
 329         idx += step;
 330         if (idx >= table_size)
 331             idx -= table_size;
 332
 333         entry = &hash_table->entries[idx];
 334         if (ENTRY_IS_LIVE (*entry)) {
 335             if ((*entry)->hash == key->hash &&
 336                 hash_table->keys_equal (key, *entry))
 337             {
 338                 return *entry;
 339             }
 340         } else if (ENTRY_IS_FREE (*entry))
 341             return NULL;
 342     } while (++i < table_size);
 343
 344     return NULL;
 345 }
 346
 347 /**
 348  * _csi_hash_table_insert:
 349  * @hash_table: a hash table
 350  * @key_and_value: an entry to be inserted
 351  *
 352  * Insert the entry #key_and_value into the hash table.
 353  *
 354  * WARNING: There must not be an existing entry in the hash table
 355  * with a matching key.
 356  *
 357  * WARNING: It is a fatal error to insert an element while
 358  * an iterator is running
 359  *
 360  * Instead of using insert to replace an entry, consider just editing
 361  * the entry obtained with _csi_hash_table_lookup. Or if absolutely
 362  * necessary, use _csi_hash_table_remove first.
 363  *
 364  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 365  * %CAIRO_STATUS_NO_MEMORY if insufficient memory is available.
 366  **/
 367 csi_status_t
 368 _csi_hash_table_insert (csi_hash_table_t *hash_table,
 369                           csi_hash_entry_t *key_and_value)
 370 {
 371     csi_status_t status;
 372     csi_hash_entry_t **entry;
 373
 374     hash_table->live_entries++;
 375     status = _csi_hash_table_manage (hash_table);
 376     if (_csi_unlikely (status)) {
 377         /* abort the insert... */
 378         hash_table->live_entries--;
 379         return status;
 380     }
 381
 382     entry = _csi_hash_table_lookup_unique_key (hash_table,
 383                                                key_and_value);
 384     if (entry == NULL)
 385         return CAIRO_STATUS_NULL_POINTER;
 386
 387     if (ENTRY_IS_FREE (*entry))
 388         hash_table->used_entries++;
 389
 390     *entry = key_and_value;
 391     return CAIRO_STATUS_SUCCESS;
 392 }
 393
 394 static csi_hash_entry_t **
 395 _csi_hash_table_lookup_exact_key (csi_hash_table_t *hash_table,
 396                                     csi_hash_entry_t *key)
 397 {
 398     unsigned long table_size, i, idx, step;
 399     csi_hash_entry_t **entry;
 400
 401     table_size = hash_table->arrangement->size;
 402     idx = key->hash % table_size;
 403
 404     entry = &hash_table->entries[idx];
 405     if (*entry == key)
 406         return entry;
 407
 408     i = 1;
 409     step = key->hash % hash_table->arrangement->rehash;
 410     if (step == 0)
 411         step = 1;
 412     do {
 413         idx += step;
 414         if (idx >= table_size)
 415             idx -= table_size;
 416
 417         entry = &hash_table->entries[idx];
 418         if (*entry == key)
 419             return entry;
 420     } while (++i < table_size);
 421
 422     return NULL;
 423 }
 424 /**
 425  * _csi_hash_table_remove:
 426  * @hash_table: a hash table
 427  * @key: key of entry to be removed
 428  *
 429  * Remove an entry from the hash table which points to @key.
 430  *
 431  * Return value: %CAIRO_STATUS_SUCCESS if successful or
 432  * %CAIRO_STATUS_NO_MEMORY if out of memory.
 433  **/
 434 void
 435 _csi_hash_table_remove (csi_hash_table_t *hash_table,
 436                           csi_hash_entry_t *key)
 437 {
 438     csi_hash_entry_t **entry = _csi_hash_table_lookup_exact_key (hash_table, key);
 439     if (entry == NULL)
 440         return;
 441
 442     *entry = DEAD_ENTRY;
 443     hash_table->live_entries--;
 444
 445     /* Check for table resize. Don't do this when iterating as this will
 446      * reorder elements of the table and cause the iteration to potentially
 447      * skip some elements. */
 448     if (hash_table->iterating == 0) {
 449         /* This call _can_ fail, but only in failing to allocate new
 450          * memory to shrink the hash table. It does leave the table in a
 451          * consistent state, and we've already succeeded in removing the
 452          * entry, so we don't examine the failure status of this call. */
 453         _csi_hash_table_manage (hash_table);
 454     }
 455 }
 456
 457 /**
 458  * _csi_hash_table_foreach:
 459  * @hash_table: a hash table
 460  * @hash_callback: function to be called for each live entry
 461  * @closure: additional argument to be passed to @hash_callback
 462  *
 463  * Call @hash_callback for each live entry in the hash table, in a
 464  * non-specified order.
 465  *
 466  * Entries in @hash_table may be removed by code executed from @hash_callback.
 467  *
 468  * Entries may not be inserted to @hash_table, nor may @hash_table
 469  * be destroyed by code executed from @hash_callback. The relevant
 470  * functions will halt in these cases.
 471  **/
 472 void
 473 _csi_hash_table_foreach (csi_hash_table_t             *hash_table,
 474                          csi_hash_callback_func_t  hash_callback,
 475                          void                         *closure)
 476 {
 477     unsigned long i;
 478     csi_hash_entry_t *entry;
 479
 480     /* Mark the table for iteration */
 481     ++hash_table->iterating;
 482     for (i = 0; i < hash_table->arrangement->size; i++) {
 483         entry = hash_table->entries[i];
 484         if (ENTRY_IS_LIVE(entry))
 485             hash_callback (entry, closure);
 486     }
 487     /* If some elements were deleted during the iteration,
 488      * the table may need resizing. Just do this every time
 489      * as the check is inexpensive.
 490      */
 491     if (--hash_table->iterating == 0) {
 492         /* Should we fail to shrink the hash table, it is left unaltered,
 493          * and we don't need to propagate the error status. */
 494         _csi_hash_table_manage (hash_table);
 495     }
 496 }