w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-hash.c
Go to the documentation of this file.
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 {
113 
115 
116  const unsigned long *table_size;
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  **/
164 {
166 
168  if (unlikely (hash_table == NULL)) {
170  return NULL;
171  }
172 
173  if (keys_equal == NULL)
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,
183  if (unlikely (hash_table->entries == NULL)) {
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
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 **
228 {
229  unsigned long table_size, i, idx, step;
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 
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
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. */
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))
310 
311  for (i = 0; i < *hash_table->table_size; ++i) {
312  if (ENTRY_IS_LIVE (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 *
340 {
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 
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 *
403  cairo_hash_predicate_func_t predicate)
404 {
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  **/
456  cairo_hash_entry_t *key_and_value)
457 {
460 
461  /* Insert is illegal while an iterator is running. */
462  assert (hash_table->iterating == 0);
463 
465  if (unlikely (status))
466  return status;
467 
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 **
483 {
484  unsigned long table_size, i, idx, step;
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 
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
522 {
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. */
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
556  cairo_hash_callback_func_t hash_callback,
557  void *closure)
558 {
559  unsigned long i;
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. */
577  }
578 }
#define hash
Definition: aptex.h:388
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
#define _cairo_error_throw(status)
cairo_bool_t(* cairo_hash_predicate_func_t)(const void *entry)
void(* cairo_hash_callback_func_t)(void *entry, void *closure)
cairo_bool_t(* cairo_hash_keys_equal_func_t)(const void *key_a, const void *key_b)
cairo_status_t _cairo_hash_table_insert(cairo_hash_table_t *hash_table, cairo_hash_entry_t *key_and_value)
Definition: cairo-hash.c:455
void _cairo_hash_table_remove(cairo_hash_table_t *hash_table, cairo_hash_entry_t *key)
Definition: cairo-hash.c:520
void _cairo_hash_table_destroy(cairo_hash_table_t *hash_table)
Definition: cairo-hash.c:214
cairo_hash_table_t * _cairo_hash_table_create(cairo_hash_keys_equal_func_t keys_equal)
Definition: cairo-hash.c:163
void * _cairo_hash_table_lookup(cairo_hash_table_t *hash_table, cairo_hash_entry_t *key)
Definition: cairo-hash.c:338
void _cairo_hash_table_foreach(cairo_hash_table_t *hash_table, cairo_hash_callback_func_t hash_callback, void *closure)
Definition: cairo-hash.c:555
void * _cairo_hash_table_random_entry(cairo_hash_table_t *hash_table, cairo_hash_predicate_func_t predicate)
Definition: cairo-hash.c:402
#define _cairo_malloc(size)
static void step(struct edge *edge)
int cairo_bool_t
Definition: cairo.h:107
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
enum _cairo_status cairo_status_t
#define ASSERT_NOT_REACHED
Definition: cairoint.h:155
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
#define DEAD_ENTRY
Definition: cairo-hash.c:56
static cairo_hash_entry_t ** _cairo_hash_table_lookup_unique_key(cairo_hash_table_t *hash_table, cairo_hash_entry_t *key)
Definition: cairo-hash.c:226
#define ENTRY_IS_FREE(entry)
Definition: cairo-hash.c:58
static cairo_status_t _cairo_hash_table_manage(cairo_hash_table_t *hash_table)
Definition: cairo-hash.c:268
static const unsigned long hash_table_sizes[]
Definition: cairo-hash.c:83
static cairo_bool_t _cairo_hash_table_uid_keys_equal(const void *key_a, const void *key_b)
Definition: cairo-hash.c:138
#define ENTRY_IS_LIVE(entry)
Definition: cairo-hash.c:60
static cairo_hash_entry_t ** _cairo_hash_table_lookup_exact_key(cairo_hash_table_t *hash_table, cairo_hash_entry_t *key)
Definition: cairo-hash.c:481
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
assert(pcxLoadImage24((char *)((void *) 0), fp, pinfo, hdr))
#define unlikely(x)
Definition: jbig2arith.cc:116
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
FT_UInt idx
Definition: cffcmap.c:135
voidp calloc()
#define rand()
Definition: mem.h:49
pdf_obj * entry
Definition: pdfdoc.c:64
char * closure
Definition: font.h:85
bstring c int memset(void *s, int c, int length)
#define status
struct hash_table hash_table
unsigned long hash
unsigned long free_entries
Definition: cairo-hash.c:120
unsigned long live_entries
Definition: cairo-hash.c:119
unsigned long iterating
Definition: cairo-hash.c:121
const unsigned long * table_size
Definition: cairo-hash.c:116
cairo_hash_entry_t * cache[32]
Definition: cairo-hash.c:114
cairo_hash_keys_equal_func_t keys_equal
Definition: cairo-hash.c:112
cairo_hash_entry_t ** entries
Definition: cairo-hash.c:117
#define key
Definition: tex2xindy.c:753
static void new_size(int size, int block)
Definition: gc.c:702