util/hash_table: Use fast modulo computation

While we're here, copy the size table from set.c to get rid of hard tabs
in the hash_table.c version.

Reviewed-by: Eric Anholt <[email protected]>
Acked-by: Jason Ekstrand <[email protected]>

2 files changed, 52 insertions, 37 deletions

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 3882f2c73f9..74d03aa60fb 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -48,6 +48,7 @@
 #include "ralloc.h"
 #include "macros.h"
 #include "main/hash.h"
+#include "fast_urem_by_const.h"
 
 static const uint32_t deleted_key_value;
 
@@ -58,38 +59,43 @@ static const uint32_t deleted_key_value;
  */
 static const struct {
    uint32_t max_entries, size, rehash;
+   uint64_t size_magic, rehash_magic;
 } hash_sizes[] = {
-   { 2,			5,		3	  },
-   { 4,			7,		5	  },
-   { 8,			13,		11	  },
-   { 16,		19,		17	  },
-   { 32,		43,		41        },
-   { 64,		73,		71        },
-   { 128,		151,		149       },
-   { 256,		283,		281       },
-   { 512,		571,		569       },
-   { 1024,		1153,		1151      },
-   { 2048,		2269,		2267      },
-   { 4096,		4519,		4517      },
-   { 8192,		9013,		9011      },
-   { 16384,		18043,		18041     },
-   { 32768,		36109,		36107     },
-   { 65536,		72091,		72089     },
-   { 131072,		144409,		144407    },
-   { 262144,		288361,		288359    },
-   { 524288,		576883,		576881    },
-   { 1048576,		1153459,	1153457   },
-   { 2097152,		2307163,	2307161   },
-   { 4194304,		4613893,	4613891   },
-   { 8388608,		9227641,	9227639   },
-   { 16777216,		18455029,	18455027  },
-   { 33554432,		36911011,	36911009  },
-   { 67108864,		73819861,	73819859  },
-   { 134217728,		147639589,	147639587 },
-   { 268435456,		295279081,	295279079 },
-   { 536870912,		590559793,	590559791 },
-   { 1073741824,	1181116273,	1181116271},
-   { 2147483648ul,	2362232233ul,	2362232231ul}
+#define ENTRY(max_entries, size, rehash) \
+   { max_entries, size, rehash, \
+      REMAINDER_MAGIC(size), REMAINDER_MAGIC(rehash) }
+
+   ENTRY(2,            5,            3            ),
+   ENTRY(4,            7,            5            ),
+   ENTRY(8,            13,           11           ),
+   ENTRY(16,           19,           17           ),
+   ENTRY(32,           43,           41           ),
+   ENTRY(64,           73,           71           ),
+   ENTRY(128,          151,          149          ),
+   ENTRY(256,          283,          281          ),
+   ENTRY(512,          571,          569          ),
+   ENTRY(1024,         1153,         1151         ),
+   ENTRY(2048,         2269,         2267         ),
+   ENTRY(4096,         4519,         4517         ),
+   ENTRY(8192,         9013,         9011         ),
+   ENTRY(16384,        18043,        18041        ),
+   ENTRY(32768,        36109,        36107        ),
+   ENTRY(65536,        72091,        72089        ),
+   ENTRY(131072,       144409,       144407       ),
+   ENTRY(262144,       288361,       288359       ),
+   ENTRY(524288,       576883,       576881       ),
+   ENTRY(1048576,      1153459,      1153457      ),
+   ENTRY(2097152,      2307163,      2307161      ),
+   ENTRY(4194304,      4613893,      4613891      ),
+   ENTRY(8388608,      9227641,      9227639      ),
+   ENTRY(16777216,     18455029,     18455027     ),
+   ENTRY(33554432,     36911011,     36911009     ),
+   ENTRY(67108864,     73819861,     73819859     ),
+   ENTRY(134217728,    147639589,    147639587    ),
+   ENTRY(268435456,    295279081,    295279079    ),
+   ENTRY(536870912,    590559793,    590559791    ),
+   ENTRY(1073741824,   1181116273,   1181116271   ),
+   ENTRY(2147483648ul, 2362232233ul, 2362232231ul )
 };
 
 static int
@@ -120,6 +126,8 @@ _mesa_hash_table_init(struct hash_table *ht,
    ht->size_index = 0;
    ht->size = hash_sizes[ht->size_index].size;
    ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->size_magic = hash_sizes[ht->size_index].size_magic;
+   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
    ht->max_entries = hash_sizes[ht->size_index].max_entries;
    ht->key_hash_function = key_hash_function;
    ht->key_equals_function = key_equals_function;
@@ -243,9 +251,10 @@ static struct hash_entry *
 hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
 {
    uint32_t size = ht->size;
-   uint32_t start_hash_address = hash % size;
+   uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
    uint32_t hash_address = start_hash_address;
-   uint32_t double_hash = 1 + hash % ht->rehash;
 
    do {
       struct hash_entry *entry = ht->table + hash_address;
@@ -296,9 +305,10 @@ hash_table_insert_rehash(struct hash_table *ht, uint32_t hash,
                          const void *key, void *data)
 {
    uint32_t size = ht->size;
-   uint32_t start_hash_address = hash % size;
+   uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
    uint32_t hash_address = start_hash_address;
-   uint32_t double_hash = 1 + hash % ht->rehash;
    do {
       struct hash_entry *entry = ht->table + hash_address;
 
@@ -335,6 +345,8 @@ _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
    ht->size_index = new_size_index;
    ht->size = hash_sizes[ht->size_index].size;
    ht->rehash = hash_sizes[ht->size_index].rehash;
+   ht->size_magic = hash_sizes[ht->size_index].size_magic;
+   ht->rehash_magic = hash_sizes[ht->size_index].rehash_magic;
    ht->max_entries = hash_sizes[ht->size_index].max_entries;
    ht->entries = 0;
    ht->deleted_entries = 0;
@@ -363,9 +375,10 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
    }
 
    uint32_t size = ht->size;
-   uint32_t start_hash_address = hash % size;
+   uint32_t start_hash_address = util_fast_urem32(hash, size, ht->size_magic);
+   uint32_t double_hash = 1 + util_fast_urem32(hash, ht->rehash,
+                                               ht->rehash_magic);
    uint32_t hash_address = start_hash_address;
-   uint32_t double_hash = 1 + hash % ht->rehash;
    do {
       struct hash_entry *entry = ht->table + hash_address;
 
diff --git a/src/util/hash_table.h b/src/util/hash_table.h
index e451bd7c21b..c808a06d428 100644
--- a/src/util/hash_table.h
+++ b/src/util/hash_table.h
@@ -51,6 +51,8 @@ struct hash_table {
    const void *deleted_key;
    uint32_t size;
    uint32_t rehash;
+   uint64_t size_magic;
+   uint64_t rehash_magic;
    uint32_t max_entries;
    uint32_t size_index;
    uint32_t entries;