hash: Code cleanup

Simplify arrangements by keeping only table sizes, remove some useless
code and fix make check.

1 files changed, 52 insertions, 62 deletions

diff --git a/src/cairo-hash.c b/src/cairo-hash.c
index e36dc6713..f4fb7cdd5 100644
--- a/src/cairo-hash.c
+++ b/src/cairo-hash.c
@@ -80,46 +80,38 @@
  * Packard.
  */
 
-typedef struct _cairo_hash_table_arrangement {
-    unsigned long high_water_mark;
-    unsigned long size;
-    unsigned long rehash;
-} cairo_hash_table_arrangement_t;
-
-static const cairo_hash_table_arrangement_t hash_table_arrangements [] = {
-    { 16,		43,		41		},
-    { 32,		73,		71		},
-    { 64,		151,		149		},
-    { 128,		283,		281		},
-    { 256,		571,		569		},
-    { 512,		1153,		1151		},
-    { 1024,		2269,		2267		},
-    { 2048,		4519,		4517		},
-    { 4096,		9013,		9011		},
-    { 8192,		18043,		18041		},
-    { 16384,		36109,		36107		},
-    { 32768,		72091,		72089		},
-    { 65536,		144409,		144407		},
-    { 131072,		288361,		288359		},
-    { 262144,		576883,		576881		},
-    { 524288,		1153459,	1153457		},
-    { 1048576,		2307163,	2307161		},
-    { 2097152,		4613893,	4613891		},
-    { 4194304,		9227641,	9227639		},
-    { 8388608,		18455029,	18455027	},
-    { 16777216,		36911011,	36911009	},
-    { 33554432,		73819861,	73819859	},
-    { 67108864,		147639589,	147639587	},
-    { 134217728,	295279081,	295279079	},
-    { 268435456,	590559793,	590559791	}
+static const unsigned long hash_table_sizes[] = {
+    43,
+    73,
+    151,
+    283,
+    571,
+    1153,
+    2269,
+    4519,
+    9013,
+    18043,
+    36109,
+    72091,
+    144409,
+    288361,
+    576883,
+    1153459,
+    2307163,
+    4613893,
+    9227641,
+    18455029,
+    36911011,
+    73819861,
+    147639589,
+    295279081,
+    590559793
 };
 
-#define NUM_HASH_TABLE_ARRANGEMENTS ARRAY_LENGTH (hash_table_arrangements)
-
 struct _cairo_hash_table {
     cairo_hash_keys_equal_func_t keys_equal;
 
-    const cairo_hash_table_arrangement_t *arrangement;
+    const unsigned long *table_size;
     cairo_hash_entry_t **entries;
 
     unsigned long live_entries;
@@ -132,7 +124,7 @@ struct _cairo_hash_table {
  * @key_a: the first key to be compared
  * @key_b: the second key to be compared
  *
- * Provides a cairo_hash_keys_equal_func_t which always returns
+ * Provides a #cairo_hash_keys_equal_func_t which always returns
  * %TRUE. This is useful to create hash tables using keys whose hash
  * completely describes the key, because in this special case
  * comparing the hashes is sufficient to guarantee that the keys are
@@ -181,10 +173,10 @@ _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
     else
 	hash_table->keys_equal = keys_equal;
 
-    hash_table->arrangement = &hash_table_arrangements[0];
+    hash_table->table_size = &hash_table_sizes[0];
 
-    hash_table->entries = calloc (hash_table->arrangement->size,
-				  sizeof(cairo_hash_entry_t *));
+    hash_table->entries = calloc (*hash_table->table_size,
+				  sizeof (cairo_hash_entry_t *));
     if (unlikely (hash_table->entries == NULL)) {
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	free (hash_table);
@@ -192,7 +184,7 @@ _cairo_hash_table_create (cairo_hash_keys_equal_func_t keys_equal)
     }
 
     hash_table->live_entries = 0;
-    hash_table->free_entries = hash_table->arrangement->size;
+    hash_table->free_entries = *hash_table->table_size;
     hash_table->iterating = 0;
 
     return hash_table;
@@ -224,8 +216,6 @@ _cairo_hash_table_destroy (cairo_hash_table_t *hash_table)
     assert (hash_table->iterating == 0);
 
     free (hash_table->entries);
-    hash_table->entries = NULL;
-
     free (hash_table);
 }
 
@@ -236,7 +226,7 @@ _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table,
     unsigned long table_size, i, idx, step;
     cairo_hash_entry_t **entry;
 
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     idx = key->hash % table_size;
 
     entry = &hash_table->entries[idx];
@@ -244,7 +234,7 @@ _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table,
 	return entry;
 
     i = 1;
-    step = 1 + key->hash % hash_table->arrangement->rehash;
+    step = 1 + key->hash % (table_size - 2);
     do {
 	idx += step;
 	if (idx >= table_size)
@@ -279,7 +269,7 @@ _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
 
     /* Keep between 12.5% and 50% entries in the hash table alive and
      * at least 25% free. */
-    unsigned long live_high = hash_table->arrangement->size >> 1;
+    unsigned long live_high = *hash_table->table_size >> 1;
     unsigned long live_low = live_high >> 2;
     unsigned long free_low = live_high >> 1;
 
@@ -287,21 +277,21 @@ _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
 
     if (hash_table->live_entries > live_high)
     {
-	tmp.arrangement = hash_table->arrangement + 1;
+	tmp.table_size = hash_table->table_size + 1;
 	/* This code is being abused if we can't make a table big enough. */
-	assert (tmp.arrangement - hash_table_arrangements <
-		NUM_HASH_TABLE_ARRANGEMENTS);
+	assert (tmp.table_size - hash_table_sizes <
+		ARRAY_LENGTH (hash_table_sizes));
     }
     else if (hash_table->live_entries < live_low)
     {
 	/* Can't shrink if we're at the smallest size */
-	if (hash_table->arrangement == &hash_table_arrangements[0])
-	    tmp.arrangement = hash_table->arrangement;
+	if (hash_table->table_size == &hash_table_sizes[0])
+	    tmp.table_size = hash_table->table_size;
 	else
-	    tmp.arrangement = hash_table->arrangement - 1;
+	    tmp.table_size = hash_table->table_size - 1;
     }
 
-    if (tmp.arrangement == hash_table->arrangement &&
+    if (tmp.table_size == hash_table->table_size &&
 	hash_table->free_entries > free_low)
     {
 	/* The number of live entries is within the desired bounds
@@ -310,12 +300,12 @@ _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
 	return CAIRO_STATUS_SUCCESS;
     }
 
-    new_size = tmp.arrangement->size;
+    new_size = *tmp.table_size;
     tmp.entries = calloc (new_size, sizeof (cairo_hash_entry_t*));
     if (unlikely (tmp.entries == NULL))
 	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 
-    for (i = 0; i < hash_table->arrangement->size; ++i) {
+    for (i = 0; i < *hash_table->table_size; ++i) {
 	if (ENTRY_IS_LIVE (hash_table->entries[i])) {
 	    *_cairo_hash_table_lookup_unique_key (&tmp, hash_table->entries[i])
 		= hash_table->entries[i];
@@ -324,7 +314,7 @@ _cairo_hash_table_manage (cairo_hash_table_t *hash_table)
 
     free (hash_table->entries);
     hash_table->entries = tmp.entries;
-    hash_table->arrangement = tmp.arrangement;
+    hash_table->table_size = tmp.table_size;
     hash_table->free_entries = new_size - hash_table->live_entries;
 
     return CAIRO_STATUS_SUCCESS;
@@ -348,7 +338,7 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
     cairo_hash_entry_t *entry;
     unsigned long table_size, i, idx, step;
 
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     idx = key->hash % table_size;
 
     entry = hash_table->entries[idx];
@@ -359,7 +349,7 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table,
 	return NULL;
 
     i = 1;
-    step = 1 + key->hash % hash_table->arrangement->rehash;
+    step = 1 + key->hash % (table_size - 2);
     do {
 	idx += step;
 	if (idx >= table_size)
@@ -406,7 +396,7 @@ _cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
 
     assert (predicate != NULL);
 
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     hash = rand ();
     idx = hash % table_size;
 
@@ -415,7 +405,7 @@ _cairo_hash_table_random_entry (cairo_hash_table_t	   *hash_table,
 	return entry;
 
     i = 1;
-    step = 1 + hash % hash_table->arrangement->rehash;
+    step = 1 + hash % (table_size - 2);
     do {
 	idx += step;
 	if (idx >= table_size)
@@ -481,7 +471,7 @@ _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table,
     unsigned long table_size, i, idx, step;
     cairo_hash_entry_t **entry;
 
-    table_size = hash_table->arrangement->size;
+    table_size = *hash_table->table_size;
     idx = key->hash % table_size;
 
     entry = &hash_table->entries[idx];
@@ -489,7 +479,7 @@ _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table,
 	return entry;
 
     i = 1;
-    step = 1 + key->hash % hash_table->arrangement->rehash;
+    step = 1 + key->hash % (table_size - 2);
     do {
 	idx += step;
 	if (idx >= table_size)
@@ -557,7 +547,7 @@ _cairo_hash_table_foreach (cairo_hash_table_t	      *hash_table,
 
     /* Mark the table for iteration */
     ++hash_table->iterating;
-    for (i = 0; i < hash_table->arrangement->size; i++) {
+    for (i = 0; i < *hash_table->table_size; i++) {
 	entry = hash_table->entries[i];
 	if (ENTRY_IS_LIVE(entry))
 	    hash_callback (entry, closure);