[cairo-commit] cairo/src cairo-hash-private.h, 1.3, 1.4 cairo-hash.c, 1.17, 1.18

[Carl Worth]

Committed by: cworth

Update of /cvs/cairo/cairo/src
In directory gabe:/tmp/cvs-serv5929/src

Modified Files:
	cairo-hash-private.h cairo-hash.c 
Log Message:

        * src/cairo-hash-private.h:
        * src/cairo-hash.c:
        (_cairo_hash_table_create): Remove destroy notifier. This
        simplifies the implementation a bit, and no anticipated use of
        cairo_hash_table_t in cairo needs the destroy notifier. Most uses
        will be hash-backed object create/destroy functions.

        (_cairo_hash_table_destroy): Document that it is now a fatal
        error to call _cairo_hash_table_destroy on a non-empty hash table.

        (_cairo_hash_table_insert): Document that it is now a fatal
        error to insert an entry with a key that matches an existing
        entry.

        (_cairo_hash_table_random_entry): Add predicate function so that
        the user can select a random entry satisying the given predicate.

        (_cairo_hash_table_remove): Change return type to void since
        failure is really not possible here.


Index: cairo-hash-private.h
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-hash-private.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- cairo-hash-private.h	30 Jun 2005 00:02:37 -0000	1.3
+++ cairo-hash-private.h	12 Jul 2005 21:43:37 -0000	1.4
@@ -39,7 +39,10 @@
 #ifndef CAIRO_HASH_PRIVATE_H
 #define CAIRO_HASH_PRIVATE_H
 
-#include "cairoint.h"
+/* XXX: I'd like this file to be self-contained in terms of
+ * includeability, but that's not really possible with the current
+ * monolithic cairoint.h. So, for now, just include cairoint.h instead
+ * if you want to include this file. */
 
 typedef struct _cairo_hash_table cairo_hash_table_t;
 
@@ -63,8 +66,11 @@
  *	_cairo_hash_table_insert (hash_table, &my_entry->base);
  *
  * IMPORTANT: The caller is reponsible for initializing
- * my_entry->base.hash with a reasonable hash code derived from the
- * key.
+ * my_entry->base.hash with a hash code derived from the key. The
+ * essential property of the hash code is that keys_equal must never
+ * return TRUE for two keys that have different hashes. The best hash
+ * code will reduce the frequency of two keys with the same code for
+ * which keys_equal returns FALSE.
  *
  * Which parts of the entry make up the "key" and which part make up
  * the value are entirely up to the caller, (as determined by the
@@ -79,15 +85,17 @@
 } cairo_hash_entry_t;
 
 typedef cairo_bool_t
-(*cairo_hash_keys_equal_func_t) (void *entry_a, void *entry_b);
+(*cairo_hash_keys_equal_func_t) (void *key_a, void *key_b);
+
+typedef cairo_bool_t
+(*cairo_hash_predicate_func_t) (void *entry);
 
 typedef void
 (*cairo_hash_callback_func_t) (void *entry,
 			       void *closure);
 
 cairo_private cairo_hash_table_t *
-_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal,
-			  cairo_destroy_func_t         entry_destroy);
+_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal);
 
 cairo_private void
 _cairo_hash_table_destroy (cairo_hash_table_t *hash_table);
@@ -98,13 +106,14 @@
 			  cairo_hash_entry_t **entry_return);
 
 cairo_private void *
-_cairo_hash_table_random_entry (cairo_hash_table_t *hash_table);
+_cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
+				cairo_hash_predicate_func_t predicate);
 
 cairo_private cairo_status_t
 _cairo_hash_table_insert (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *entry);
 
-cairo_private cairo_status_t
+cairo_private void
 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key);
 

Index: cairo-hash.c
===================================================================
RCS file: /cvs/cairo/cairo/src/cairo-hash.c,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -d -r1.17 -r1.18
--- cairo-hash.c	30 Jun 2005 00:05:31 -0000	1.17
+++ cairo-hash.c	12 Jul 2005 21:43:37 -0000	1.18
@@ -36,7 +36,7 @@
  *	Carl Worth <cworth at cworth.org>
  */
 
-#include "cairo-hash-private.h"
+#include "cairoint.h"
 
 /*
  * An entry can be in one of three states:
@@ -119,7 +119,6 @@
 
 struct _cairo_hash_table {
     cairo_hash_keys_equal_func_t keys_equal;
-    cairo_destroy_func_t entry_destroy;
 
     const cairo_hash_table_arrangement_t *arrangement;
     cairo_hash_entry_t **entries;
@@ -130,7 +129,6 @@
 /**
  * _cairo_hash_table_create:
  * @keys_equal: a function to return TRUE if two keys are equal
- * @entry_destroy: destroy notifier for hash entries
  * 
  * 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
@@ -145,8 +143,7 @@
  * Return value: the new hash table or NULL if out of memory.
  **/
 cairo_hash_table_t *
-_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal,
-			  cairo_destroy_func_t	       entry_destroy)
+_cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
 {    
     cairo_hash_table_t *hash_table;
 
@@ -155,7 +152,6 @@
 	return NULL;
 
     hash_table->keys_equal = keys_equal;
-    hash_table->entry_destroy = entry_destroy;
 
     hash_table->arrangement = &hash_table_arrangements[0];
 
@@ -171,41 +167,27 @@
     return hash_table;
 }
 
-static void
-_destroy_entry (cairo_hash_table_t *hash_table, cairo_hash_entry_t **entry)
-{
-    if (! ENTRY_IS_LIVE (*entry))
-	return;
-
-    if (hash_table->entry_destroy)
-	hash_table->entry_destroy (*entry);
-    *entry = DEAD_ENTRY;
-    hash_table->live_entries--;
-}
-
 /**
  * _cairo_hash_table_destroy:
- * @hash_table: a hash table to destroy
+ * @hash_table: an empty hash table to destroy
  * 
  * Immediately destroys the given hash table, freeing all resources
- * associated with it. As part of this process, the entry_destroy()
- * function, (as passed to cairo_hash_table_create), will be called
- * for each live entry in the hash table.
+ * 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.
  **/
 void
 _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
 {
-    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))
-	    _destroy_entry (hash_table, entry);
-    }
+
+    /* The hash table must be empty. Otherwise, halt. */
+    assert (hash_table->live_entries == 0);
 	
     free (hash_table->entries);
     hash_table->entries = NULL;
@@ -366,7 +348,7 @@
  * 
  * Performs a lookup in @hash_table looking for an entry which has a
  * key that matches @key, (as determined by the keys_equal() function
- * passed to cairo_hash_table_create).
+ * 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
@@ -393,24 +375,26 @@
 /**
  * _cairo_hash_table_random_entry:
  * @hash_table: a hash table
+ * @predicate: a predicate function, or NULL for any entry.
  * 
- * Find a random entry in the hash table.
+ * Find a random entry in the hash table satisfying the given
+ * @predicate. A NULL @predicate 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 false for most entries.
+ * returns TRUE for most entries.
  *
- * NOTE: It'd be really easy to turn this into a find function with a
- * predicate if anybody might want that.
- * 
- * Return value: a random live entry or NULL if there are no live
- * 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.
  **/
 void *
-_cairo_hash_table_random_entry (cairo_hash_table_t *hash_table)
+_cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
+				cairo_hash_predicate_func_t predicate)
 {
     cairo_hash_entry_t **entry;
     unsigned long hash;
@@ -426,8 +410,11 @@
     {
 	entry = &hash_table->entries[idx];
 
-	if (ENTRY_IS_LIVE (*entry))
+	if (ENTRY_IS_LIVE (*entry) &&
+	    (predicate == NULL || predicate (*entry)))
+	{
 	    return *entry;
+	}
 
 	if (step == 0) { 	    
 	    step = hash % hash_table->arrangement->rehash;
@@ -448,10 +435,14 @@
  * @hash_table: a hash table
  * @key_and_value: an entry to be inserted
  * 
- * Insert the entry #key_and_value into the hash table. If an existing
- * exists in the hash table with a matching key, then the old entry
- * will be removed first, (and the entry_destroy() callback will be
- * called on it).
+ * 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.
@@ -468,16 +459,12 @@
     
     if (ENTRY_IS_LIVE(*entry))
     {
-	if (hash_table->entry_destroy)
-	    hash_table->entry_destroy (*entry);
-	*entry = key_and_value;
+	/* User is being bad, let's crash. */
+	ASSERT_NOT_REACHED;
     }
-    else
-    {
-	*entry = key_and_value;
 
-	hash_table->live_entries++;
-    }
+    *entry = key_and_value;
+    hash_table->live_entries++;
 
     status = _cairo_hash_table_resize (hash_table);
     if (status)
@@ -492,30 +479,30 @@
  * @key: key of entry to be removed
  * 
  * Remove an entry from the hash table which has a key that matches
- * @key, (as determined by the keys_equal() function passed to
- * _cairo_hash_table_create), if any.
+ * @key, 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.
  **/
-cairo_status_t
+void
 _cairo_hash_table_remove (cairo_hash_table_t *hash_table,
 			  cairo_hash_entry_t *key)
 {
-    cairo_status_t status;
     cairo_hash_entry_t **entry;
 
     entry = _cairo_hash_table_lookup_internal (hash_table, key, FALSE);
     if (! ENTRY_IS_LIVE(*entry))
-	return CAIRO_STATUS_SUCCESS;
-
-    _destroy_entry (hash_table, entry);
+	return;
 
-    status = _cairo_hash_table_resize (hash_table);
-    if (status)
-	return status;
+    *entry = DEAD_ENTRY;
+    hash_table->live_entries--;
 
-    return CAIRO_STATUS_SUCCESS;
+    /* 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);
 }
 
 /**