util: Move the open-addressing linear-probing hash_table to src/util.

This hash table is used in core Mesa, the GLSL compiler, and the i965
driver, which makes it a good candidate for the new src/util module.

It's much faster than program/hash_table.[ch] (see commit 6991c2922f5
for data), and José's u_hash_table.c has a comment saying Gallium should
probably consider switching to a linear probing hash table at some point.
So this seems like the best candidate for a shared data structure.

Signed-off-by: Kenneth Graunke <[email protected]>

v2 (Jason Ekstrand): Pick up another hash_table use and patch up scons

Signed-off-by: Jason Ekstrand <[email protected]>
Reviewed-by: Marek Olšák <[email protected]>

35 files changed, 25 insertions, 27 deletions

diff --git a/configure.ac b/configure.ac
index b2b61c762fc..a3b3abdd4b0 100644
--- a/configure.ac
+++ b/configure.ac
@@ -2279,9 +2279,9 @@ AC_CONFIG_FILES([Makefile
 		src/mesa/drivers/osmesa/osmesa.pc
 		src/mesa/drivers/x11/Makefile
 		src/mesa/main/tests/Makefile
-		src/mesa/main/tests/hash_table/Makefile
 		src/util/Makefile
-		src/util/tests/Makefile])
+		src/util/tests/Makefile
+		src/util/tests/hash_table/Makefile])
 
 dnl Sort the dirs alphabetically
 GALLIUM_TARGET_DIRS=`echo $GALLIUM_TARGET_DIRS|tr " " "\n"|sort -u|tr "\n" " "`
diff --git a/src/glsl/Makefile.am b/src/glsl/Makefile.am
index 292c8f78775..2a20d119328 100644
--- a/src/glsl/Makefile.am
+++ b/src/glsl/Makefile.am
@@ -53,7 +53,6 @@ check_PROGRAMS =					\
 noinst_PROGRAMS = glsl_compiler
 
 tests_general_ir_test_SOURCES =		\
-	$(top_srcdir)/src/mesa/main/hash_table.c	\
 	$(top_srcdir)/src/mesa/main/imports.c		\
 	$(top_srcdir)/src/mesa/program/prog_hash_table.c\
 	$(top_srcdir)/src/mesa/program/symbol_table.c	\
@@ -71,7 +70,6 @@ tests_general_ir_test_LDADD =				\
 	$(PTHREAD_LIBS)
 
 tests_uniform_initializer_test_SOURCES =		\
-	$(top_srcdir)/src/mesa/main/hash_table.c	\
 	$(top_srcdir)/src/mesa/main/imports.c		\
 	$(top_srcdir)/src/mesa/program/prog_hash_table.c\
 	$(top_srcdir)/src/mesa/program/symbol_table.c	\
@@ -120,7 +118,6 @@ libglsl_la_SOURCES =					\
 	$(LIBGLSL_FILES)
 
 glsl_compiler_SOURCES = \
-	$(top_srcdir)/src/mesa/main/hash_table.c \
 	$(top_srcdir)/src/mesa/main/imports.c \
 	$(top_srcdir)/src/mesa/program/prog_hash_table.c \
 	$(top_srcdir)/src/mesa/program/symbol_table.c \
@@ -131,7 +128,6 @@ glsl_compiler_LDADD =					\
 	$(PTHREAD_LIBS)
 
 glsl_test_SOURCES = \
-	$(top_srcdir)/src/mesa/main/hash_table.c \
 	$(top_srcdir)/src/mesa/main/imports.c \
 	$(top_srcdir)/src/mesa/program/prog_hash_table.c \
 	$(top_srcdir)/src/mesa/program/symbol_table.c \
diff --git a/src/glsl/SConscript b/src/glsl/SConscript
index d1d5993d60a..847e9624685 100644
--- a/src/glsl/SConscript
+++ b/src/glsl/SConscript
@@ -58,7 +58,6 @@ if env['msvc']:
 
 # Copy these files to avoid generation object files into src/mesa/program
 env.Prepend(CPPPATH = ['#src/mesa/main'])
-env.Command('hash_table.c', '#src/mesa/main/hash_table.c', Copy('$TARGET', '$SOURCE'))
 env.Command('imports.c', '#src/mesa/main/imports.c', Copy('$TARGET', '$SOURCE'))
 # Copy these files to avoid generation object files into src/mesa/program
 env.Prepend(CPPPATH = ['#src/mesa/program'])
@@ -68,7 +67,6 @@ env.Command('symbol_table.c', '#src/mesa/program/symbol_table.c', Copy('$TARGET'
 compiler_objs = env.StaticObject(source_lists['GLSL_COMPILER_CXX_FILES'])
 
 mesa_objs = env.StaticObject([
-    'hash_table.c',
     'imports.c',
     'prog_hash_table.c',
     'symbol_table.c',
diff --git a/src/glsl/ir_variable_refcount.cpp b/src/glsl/ir_variable_refcount.cpp
index 923eb1a8274..f67fe678443 100644
--- a/src/glsl/ir_variable_refcount.cpp
+++ b/src/glsl/ir_variable_refcount.cpp
@@ -33,7 +33,7 @@
 #include "ir_visitor.h"
 #include "ir_variable_refcount.h"
 #include "glsl_types.h"
-#include "main/hash_table.h"
+#include "util/hash_table.h"
 
 ir_variable_refcount_visitor::ir_variable_refcount_visitor()
 {
diff --git a/src/glsl/link_uniform_block_active_visitor.h b/src/glsl/link_uniform_block_active_visitor.h
index 524cd6b91d9..64de8268007 100644
--- a/src/glsl/link_uniform_block_active_visitor.h
+++ b/src/glsl/link_uniform_block_active_visitor.h
@@ -26,7 +26,7 @@
 #define LINK_UNIFORM_BLOCK_ACTIVE_VISITOR_H
 
 #include "ir.h"
-#include "main/hash_table.h"
+#include "util/hash_table.h"
 
 struct link_uniform_block_active {
    const glsl_type *type;
diff --git a/src/glsl/link_uniform_blocks.cpp b/src/glsl/link_uniform_blocks.cpp
index fef3626bf02..0b1291d9a9b 100644
--- a/src/glsl/link_uniform_blocks.cpp
+++ b/src/glsl/link_uniform_blocks.cpp
@@ -26,7 +26,7 @@
 #include "linker.h"
 #include "ir_uniform.h"
 #include "link_uniform_block_active_visitor.h"
-#include "main/hash_table.h"
+#include "util/hash_table.h"
 #include "program.h"
 
 namespace {
diff --git a/src/glsl/opt_dead_code.cpp b/src/glsl/opt_dead_code.cpp
index da90bfb4045..3df01b4137d 100644
--- a/src/glsl/opt_dead_code.cpp
+++ b/src/glsl/opt_dead_code.cpp
@@ -31,7 +31,7 @@
 #include "ir_visitor.h"
 #include "ir_variable_refcount.h"
 #include "glsl_types.h"
-#include "main/hash_table.h"
+#include "util/hash_table.h"
 
 static bool debug = false;
 
diff --git a/src/mesa/Makefile.sources b/src/mesa/Makefile.sources
index 8a04980e167..5ccce54e0b5 100644
--- a/src/mesa/Makefile.sources
+++ b/src/mesa/Makefile.sources
@@ -57,7 +57,6 @@ MAIN_FILES = \
 	$(SRCDIR)main/getstring.c \
 	$(SRCDIR)main/glformats.c \
 	$(SRCDIR)main/hash.c \
-	$(SRCDIR)main/hash_table.c \
 	$(SRCDIR)main/hint.c \
 	$(SRCDIR)main/histogram.c \
 	$(SRCDIR)main/image.c \
diff --git a/src/mesa/drivers/dri/i965/brw_fs.cpp b/src/mesa/drivers/dri/i965/brw_fs.cpp
index 0d1185b5e07..13ef6dde6de 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs.cpp
@@ -32,7 +32,7 @@ extern "C" {
 
 #include <sys/types.h>
 
-#include "main/hash_table.h"
+#include "util/hash_table.h"
 #include "main/macros.h"
 #include "main/shaderobj.h"
 #include "main/fbobject.h"
diff --git a/src/mesa/drivers/dri/i965/intel_fbo.c b/src/mesa/drivers/dri/i965/intel_fbo.c
index e43e18b78a2..12bd4521772 100644
--- a/src/mesa/drivers/dri/i965/intel_fbo.c
+++ b/src/mesa/drivers/dri/i965/intel_fbo.c
@@ -36,9 +36,9 @@
 #include "main/context.h"
 #include "main/teximage.h"
 #include "main/image.h"
-#include "main/hash_table.h"
 #include "main/set.h"
 #include "main/condrender.h"
+#include "util/hash_table.h"
 
 #include "swrast/swrast.h"
 #include "drivers/common/meta.h"
diff --git a/src/mesa/main/errors.c b/src/mesa/main/errors.c
index aa0ff50ac37..9cde1e02004 100644
--- a/src/mesa/main/errors.c
+++ b/src/mesa/main/errors.c
@@ -36,7 +36,7 @@
 #include "hash.h"
 #include "mtypes.h"
 #include "version.h"
-#include "hash_table.h"
+#include "util/hash_table.h"
 
 static mtx_t DynamicIDMutex = _MTX_INITIALIZER_NP;
 static GLuint NextDynamicID = 1;
diff --git a/src/mesa/main/hash.c b/src/mesa/main/hash.c
index 674c29d650b..52095f7d1c3 100644
--- a/src/mesa/main/hash.c
+++ b/src/mesa/main/hash.c
@@ -37,7 +37,7 @@
 #include "glheader.h"
 #include "imports.h"
 #include "hash.h"
-#include "hash_table.h"
+#include "util/hash_table.h"
 
 /**
  * Magic GLuint object name that gets stored outside of the struct hash_table.
diff --git a/src/mesa/main/shaderapi.c b/src/mesa/main/shaderapi.c
index 85b975304ad..b4a5e70506b 100644
--- a/src/mesa/main/shaderapi.c
+++ b/src/mesa/main/shaderapi.c
@@ -42,7 +42,6 @@
 #include "main/dispatch.h"
 #include "main/enums.h"
 #include "main/hash.h"
-#include "main/hash_table.h"
 #include "main/mtypes.h"
 #include "main/pipelineobj.h"
 #include "main/shaderapi.h"
@@ -53,6 +52,7 @@
 #include "program/prog_print.h"
 #include "program/prog_parameter.h"
 #include "util/ralloc.h"
+#include "util/hash_table.h"
 #include <stdbool.h>
 #include "../glsl/glsl_parser_extras.h"
 #include "../glsl/ir.h"
diff --git a/src/mesa/main/shared.c b/src/mesa/main/shared.c
index 5ae7014b1cd..0189dd2960a 100644
--- a/src/mesa/main/shared.c
+++ b/src/mesa/main/shared.c
@@ -30,7 +30,6 @@
 #include "imports.h"
 #include "mtypes.h"
 #include "hash.h"
-#include "hash_table.h"
 #include "atifragshader.h"
 #include "bufferobj.h"
 #include "shared.h"
@@ -42,6 +41,7 @@
 #include "shaderobj.h"
 #include "syncobj.h"
 
+#include "util/hash_table.h"
 
 /**
  * Allocate and initialize a shared context state structure.
diff --git a/src/mesa/main/syncobj.c b/src/mesa/main/syncobj.c
index a88d7e469f2..225399eda3b 100644
--- a/src/mesa/main/syncobj.c
+++ b/src/mesa/main/syncobj.c
@@ -64,7 +64,7 @@
 #include "dispatch.h"
 #include "mtypes.h"
 #include "set.h"
-#include "hash_table.h"
+#include "util/hash_table.h"
 
 #include "syncobj.h"
 
diff --git a/src/mesa/main/tests/Makefile.am b/src/mesa/main/tests/Makefile.am
index 3c7c1b51ad8..251474d5c25 100644
--- a/src/mesa/main/tests/Makefile.am
+++ b/src/mesa/main/tests/Makefile.am
@@ -1,5 +1,3 @@
-SUBDIRS = hash_table
-
 AM_CFLAGS = \
 	$(X11_CFLAGS) \
 	$(PTHREAD_CFLAGS)
diff --git a/src/mesa/main/vdpau.c b/src/mesa/main/vdpau.c
index 975b812cda5..e1c3e00ba5a 100644
--- a/src/mesa/main/vdpau.c
+++ b/src/mesa/main/vdpau.c
@@ -32,9 +32,9 @@
  */
 
 #include <stdbool.h>
+#include "util/hash_table.h"
 #include "context.h"
 #include "glformats.h"
-#include "hash_table.h"
 #include "set.h"
 #include "texobj.h"
 #include "teximage.h"
diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index 1ed70c2c6ef..0f9dcab6a59 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -28,6 +28,7 @@ noinst_LTLIBRARIES = libmesautil.la
 libmesautil_la_CPPFLAGS = \
 	$(DEFINES) \
 	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/src/mapi \
 	-I$(top_srcdir)/src/mesa \
 	$(VISIBILITY_CFLAGS)
 
diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources
index c4c79ca4431..5daa731ce1d 100644
--- a/src/util/Makefile.sources
+++ b/src/util/Makefile.sources
@@ -1,2 +1,3 @@
-MESA_UTIL_FILES := \
+MESA_UTIL_FILES :=	\
+	hash_table.c	\
 	ralloc.c
diff --git a/src/util/SConscript b/src/util/SConscript
index 9653ef62ea1..a36340deebf 100644
--- a/src/util/SConscript
+++ b/src/util/SConscript
@@ -8,6 +8,7 @@ env = env.Clone()
 
 env.Prepend(CPPPATH = [
     '#include',
+    '#src/mapi',
     '#src/mesa',
     '#src/util',
 ])
diff --git a/src/mesa/main/hash_table.c b/src/util/hash_table.c
index b51dada6691..f98a1a647ea 100644
--- a/src/mesa/main/hash_table.c
+++ b/src/util/hash_table.c
@@ -43,9 +43,9 @@
 #include <stdlib.h>
 #include <string.h>
 
-#include "main/hash_table.h"
+#include "hash_table.h"
 #include "main/macros.h"
-#include "util/ralloc.h"
+#include "ralloc.h"
 
 static const uint32_t deleted_key_value;
 
diff --git a/src/mesa/main/hash_table.h b/src/util/hash_table.h
index f51131aeed8..5fa58991e30 100644
--- a/src/mesa/main/hash_table.h
+++ b/src/util/hash_table.h
@@ -31,7 +31,7 @@
 #include <inttypes.h>
 #include <stdbool.h>
 
-#include "compiler.h"
+#include "main/compiler.h"
 
 #ifdef __cplusplus
 extern "C" {
diff --git a/src/util/tests/Makefile.am b/src/util/tests/Makefile.am
index a2b54982ff1..8ec8c3aa55c 100644
--- a/src/util/tests/Makefile.am
+++ b/src/util/tests/Makefile.am
@@ -19,6 +19,8 @@
 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 # IN THE SOFTWARE.
 
+SUBDIRS = hash_table
+
 AM_CFLAGS = \
 	$(PTHREAD_CFLAGS)
 AM_CPPFLAGS = \
diff --git a/src/mesa/main/tests/hash_table/.gitignore b/src/util/tests/hash_table/.gitignore
index 1b9aaf4a27e..1b9aaf4a27e 100644
--- a/src/mesa/main/tests/hash_table/.gitignore
+++ b/src/util/tests/hash_table/.gitignore
diff --git a/src/mesa/main/tests/hash_table/Makefile.am b/src/util/tests/hash_table/Makefile.am
index 0330ebb3e8f..55cc0b72335 100644
--- a/src/mesa/main/tests/hash_table/Makefile.am
+++ b/src/util/tests/hash_table/Makefile.am
@@ -20,6 +20,8 @@
 
 AM_CPPFLAGS = \
 	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/src/util \
+	-I$(top_srcdir)/src/mesa \
 	-I$(top_srcdir)/src/mesa/main \
 	$(DEFINES) $(INCLUDE_DIRS)
 
diff --git a/src/mesa/main/tests/hash_table/collision.c b/src/util/tests/hash_table/collision.c
index 9174c396151..9174c396151 100644
--- a/src/mesa/main/tests/hash_table/collision.c
+++ b/src/util/tests/hash_table/collision.c
diff --git a/src/mesa/main/tests/hash_table/delete_and_lookup.c b/src/util/tests/hash_table/delete_and_lookup.c
index fc886ff4f4e..fc886ff4f4e 100644
--- a/src/mesa/main/tests/hash_table/delete_and_lookup.c
+++ b/src/util/tests/hash_table/delete_and_lookup.c
diff --git a/src/mesa/main/tests/hash_table/delete_management.c b/src/util/tests/hash_table/delete_management.c
index b8d764019f4..b8d764019f4 100644
--- a/src/mesa/main/tests/hash_table/delete_management.c
+++ b/src/util/tests/hash_table/delete_management.c
diff --git a/src/mesa/main/tests/hash_table/destroy_callback.c b/src/util/tests/hash_table/destroy_callback.c
index dce2b333234..dce2b333234 100644
--- a/src/mesa/main/tests/hash_table/destroy_callback.c
+++ b/src/util/tests/hash_table/destroy_callback.c
diff --git a/src/mesa/main/tests/hash_table/insert_and_lookup.c b/src/util/tests/hash_table/insert_and_lookup.c
index 402f3fd4002..402f3fd4002 100644
--- a/src/mesa/main/tests/hash_table/insert_and_lookup.c
+++ b/src/util/tests/hash_table/insert_and_lookup.c
diff --git a/src/mesa/main/tests/hash_table/insert_many.c b/src/util/tests/hash_table/insert_many.c
index b2122dcf96c..b2122dcf96c 100644
--- a/src/mesa/main/tests/hash_table/insert_many.c
+++ b/src/util/tests/hash_table/insert_many.c
diff --git a/src/mesa/main/tests/hash_table/null_destroy.c b/src/util/tests/hash_table/null_destroy.c
index 3833464f454..3833464f454 100644
--- a/src/mesa/main/tests/hash_table/null_destroy.c
+++ b/src/util/tests/hash_table/null_destroy.c
diff --git a/src/mesa/main/tests/hash_table/random_entry.c b/src/util/tests/hash_table/random_entry.c
index 22cafa7e857..22cafa7e857 100644
--- a/src/mesa/main/tests/hash_table/random_entry.c
+++ b/src/util/tests/hash_table/random_entry.c
diff --git a/src/mesa/main/tests/hash_table/remove_null.c b/src/util/tests/hash_table/remove_null.c
index 90fb784ac40..90fb784ac40 100644
--- a/src/mesa/main/tests/hash_table/remove_null.c
+++ b/src/util/tests/hash_table/remove_null.c
diff --git a/src/mesa/main/tests/hash_table/replacement.c b/src/util/tests/hash_table/replacement.c
index 387cfc0fd94..387cfc0fd94 100644
--- a/src/mesa/main/tests/hash_table/replacement.c
+++ b/src/util/tests/hash_table/replacement.c