prog_hash_table: Convert to using util/hash_table.h.

Improves glretrace -b servo.trace (a trace of Mozilla's servo rendering
engine booting, rendering a page, and exiting) from 1.8s to 1.1s.  It uses
a large uniform array of structs, making a huge number of separate program
resources, and the fixed-size hash table was killing it.  Given how many
times we've improved performance by swapping the hash table to
util/hash_table.h, just do it once and for all.

This just rebases the old hash table API on top of util/, for minimal
diff.  Cleaning things up is left for later, particularly because I want
to fix up the new hash table API a little bit.

v2: Add UNUSED to the now-unused parameter.

Reviewed-by: Ian Romanick <[email protected]>
Reviewed-by: Timothy Arceri <[email protected]>

2 files changed, 54 insertions, 205 deletions

diff --git a/src/mesa/program/hash_table.h b/src/mesa/program/hash_table.h
index aba5282fe9e..91fc11ecc33 100644
--- a/src/mesa/program/hash_table.h
+++ b/src/mesa/program/hash_table.h
@@ -37,6 +37,7 @@
 #include <stdint.h>
 #include <limits.h>
 #include <assert.h>
+#include "util/hash_table.h"
 
 struct string_to_uint_map;
 
@@ -44,8 +45,6 @@ struct string_to_uint_map;
 extern "C" {
 #endif
 
-struct hash_table;
-
 typedef unsigned (*hash_func_t)(const void *key);
 typedef bool (*hash_compare_func_t)(const void *key1, const void *key2);
 
@@ -60,26 +59,32 @@ typedef bool (*hash_compare_func_t)(const void *key1, const void *key2);
  * \param hash         Function used to compute hash value of input keys.
  * \param compare      Function used to compare keys.
  */
-extern struct hash_table *hash_table_ctor(unsigned num_buckets,
-    hash_func_t hash, hash_compare_func_t compare);
-
+static inline struct hash_table *hash_table_ctor(UNUSED unsigned num_buckets,
+    hash_func_t hash, hash_compare_func_t compare)
+{
+   return _mesa_hash_table_create(NULL, hash, compare);
+}
 
 /**
  * Release all memory associated with a hash table
  *
  * \warning
- * This function cannot release memory occupied either by keys or data.
+ * This function does not release memory occupied either by keys or data.
  */
-extern void hash_table_dtor(struct hash_table *ht);
-
+static inline void hash_table_dtor(struct hash_table *ht)
+{
+   return _mesa_hash_table_destroy(ht, NULL);
+}
 
 /**
  * Flush all entries from a hash table
  *
  * \param ht  Table to be cleared of its entries.
  */
-extern void hash_table_clear(struct hash_table *ht);
-
+static inline void hash_table_clear(struct hash_table *ht)
+{
+   return _mesa_hash_table_clear(ht, NULL);
+}
 
 /**
  * Search a hash table for a specific element
@@ -92,25 +97,28 @@ extern void hash_table_clear(struct hash_table *ht);
  * the matching key was added.  If no matching key exists in the table,
  * \c NULL is returned.
  */
-extern void *hash_table_find(struct hash_table *ht, const void *key);
-
+static inline void *hash_table_find(struct hash_table *ht, const void *key)
+{
+   struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+   if (!entry)
+      return NULL;
+   return entry->data;
+}
 
 /**
  * Add an element to a hash table
  *
  * \warning
- * If \c key is already in the hash table, it will be added again.  Future
- * calls to \c hash_table_find and \c hash_table_remove will return or remove,
- * repsectively, the most recently added instance of \c key.
- *
- * \warning
  * The value passed by \c key is kept in the hash table and is used by later
  * calls to \c hash_table_find.
  *
  * \sa hash_table_replace
  */
-extern void hash_table_insert(struct hash_table *ht, void *data,
-    const void *key);
+static inline void hash_table_insert(struct hash_table *ht, void *data,
+                                     const void *key)
+{
+   _mesa_hash_table_insert(ht, key, data);
+}
 
 /**
  * Add an element to a hash table with replacement
@@ -126,13 +134,29 @@ extern void hash_table_insert(struct hash_table *ht, void *data,
  *
  * \sa hash_table_insert
  */
-extern bool hash_table_replace(struct hash_table *ht, void *data,
-    const void *key);
+static inline bool hash_table_replace(struct hash_table *ht, void *data,
+                                      const void *key)
+{
+   struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+   if (entry) {
+      entry->data = data;
+      return true;
+   } else {
+      _mesa_hash_table_insert(ht, key, data);
+      return false;
+   }
+}
 
 /**
  * Remove a specific element from a hash table.
  */
-extern void hash_table_remove(struct hash_table *ht, const void *key);
+static inline void hash_table_remove(struct hash_table *ht, const void *key)
+{
+   struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+
+   if (entry)
+      _mesa_hash_table_remove(ht, entry);
+}
 
 /**
  * Compute hash value of a string
@@ -180,12 +204,18 @@ hash_table_pointer_hash(const void *key);
 bool
 hash_table_pointer_compare(const void *key1, const void *key2);
 
-void
+static inline void
 hash_table_call_foreach(struct hash_table *ht,
 			void (*callback)(const void *key,
 					 void *data,
 					 void *closure),
-			void *closure);
+			void *closure)
+{
+   struct hash_entry *entry;
+
+   hash_table_foreach(ht, entry)
+      callback(entry->key, entry->data, closure);
+}
 
 struct string_to_uint_map *
 string_to_uint_map_ctor();
diff --git a/src/mesa/program/prog_hash_table.c b/src/mesa/program/prog_hash_table.c
index f8a7107eb5b..cbea74c05ab 100644
--- a/src/mesa/program/prog_hash_table.c
+++ b/src/mesa/program/prog_hash_table.c
@@ -32,187 +32,6 @@
 #include "util/simple_list.h"
 #include "hash_table.h"
 
-struct node {
-   struct node *next;
-   struct node *prev;
-};
-
-struct hash_table {
-    hash_func_t    hash;
-    hash_compare_func_t  compare;
-
-    unsigned num_buckets;
-    struct node buckets[1];
-};
-
-
-struct hash_node {
-    struct node link;
-    const void *key;
-    void *data;
-};
-
-
-struct hash_table *
-hash_table_ctor(unsigned num_buckets, hash_func_t hash,
-                hash_compare_func_t compare)
-{
-    struct hash_table *ht;
-    unsigned i;
-
-
-    if (num_buckets < 16) {
-        num_buckets = 16;
-    }
-
-    ht = malloc(sizeof(*ht) + ((num_buckets - 1) 
-				     * sizeof(ht->buckets[0])));
-    if (ht != NULL) {
-        ht->hash = hash;
-        ht->compare = compare;
-        ht->num_buckets = num_buckets;
-
-        for (i = 0; i < num_buckets; i++) {
-            make_empty_list(& ht->buckets[i]);
-        }
-    }
-
-    return ht;
-}
-
-
-void
-hash_table_dtor(struct hash_table *ht)
-{
-   hash_table_clear(ht);
-   free(ht);
-}
-
-
-void
-hash_table_clear(struct hash_table *ht)
-{
-   struct node *node;
-   struct node *temp;
-   unsigned i;
-
-
-   for (i = 0; i < ht->num_buckets; i++) {
-      foreach_s(node, temp, & ht->buckets[i]) {
-	 remove_from_list(node);
-	 free(node);
-      }
-
-      assert(is_empty_list(& ht->buckets[i]));
-   }
-}
-
-
-static struct hash_node *
-get_node(struct hash_table *ht, const void *key)
-{
-    const unsigned hash_value = (*ht->hash)(key);
-    const unsigned bucket = hash_value % ht->num_buckets;
-    struct node *node;
-
-    foreach(node, & ht->buckets[bucket]) {
-       struct hash_node *hn = (struct hash_node *) node;
-
-       if ((*ht->compare)(hn->key, key) == 0) {
-	  return hn;
-       }
-    }
-
-    return NULL;
-}
-
-void *
-hash_table_find(struct hash_table *ht, const void *key)
-{
-   struct hash_node *hn = get_node(ht, key);
-
-   return (hn == NULL) ? NULL : hn->data;
-}
-
-void
-hash_table_insert(struct hash_table *ht, void *data, const void *key)
-{
-    const unsigned hash_value = (*ht->hash)(key);
-    const unsigned bucket = hash_value % ht->num_buckets;
-    struct hash_node *node;
-
-    node = calloc(1, sizeof(*node));
-    if (node == NULL) {
-       _mesa_error_no_memory(__func__);
-       return;
-    }
-
-    node->data = data;
-    node->key = key;
-
-    insert_at_head(& ht->buckets[bucket], & node->link);
-}
-
-bool
-hash_table_replace(struct hash_table *ht, void *data, const void *key)
-{
-    const unsigned hash_value = (*ht->hash)(key);
-    const unsigned bucket = hash_value % ht->num_buckets;
-    struct node *node;
-    struct hash_node *hn;
-
-    foreach(node, & ht->buckets[bucket]) {
-       hn = (struct hash_node *) node;
-
-       if ((*ht->compare)(hn->key, key) == 0) {
-	  hn->data = data;
-	  return true;
-       }
-    }
-
-    hn = calloc(1, sizeof(*hn));
-    if (hn == NULL) {
-       _mesa_error_no_memory(__func__);
-       return false;
-    }
-
-    hn->data = data;
-    hn->key = key;
-
-    insert_at_head(& ht->buckets[bucket], & hn->link);
-    return false;
-}
-
-void
-hash_table_remove(struct hash_table *ht, const void *key)
-{
-   struct node *node = (struct node *) get_node(ht, key);
-   if (node != NULL) {
-      remove_from_list(node);
-      free(node);
-      return;
-   }
-}
-
-void
-hash_table_call_foreach(struct hash_table *ht,
-			void (*callback)(const void *key,
-					 void *data,
-					 void *closure),
-			void *closure)
-{
-   unsigned bucket;
-
-   for (bucket = 0; bucket < ht->num_buckets; bucket++) {
-      struct node *node, *temp;
-      foreach_s(node, temp, &ht->buckets[bucket]) {
-	 struct hash_node *hn = (struct hash_node *) node;
-
-	 callback(hn->key, hn->data, closure);
-      }
-   }
-}
-
 unsigned
 hash_table_string_hash(const void *key)
 {