From 117241b1cd873bad6f955819112cafed8aa29616 Mon Sep 17 00:00:00 2001
From: bdemsky <bdemsky@uci.edu>
Date: Mon, 23 Oct 2017 19:36:35 -0700
Subject: [PATCH] Improve hash function to fix collision problem

---
 src/Backend/constraint.cc | 17 ++++++++++++-----
 src/Test/Makefile         |  2 +-
 src/csolver.cc            |  1 -
 3 files changed, 13 insertions(+), 7 deletions(-)

diff --git a/src/Backend/constraint.cc b/src/Backend/constraint.cc
index 7c3a094..b7cb320 100644
--- a/src/Backend/constraint.cc
+++ b/src/Backend/constraint.cc
@@ -146,12 +146,19 @@ Edge createNode(CNF *cnf, NodeType type, uint numEdges, Edge *edges) {
 }
 
 uint hashNode(NodeType type, uint numEdges, Edge *edges) {
-	uint hashvalue = type ^ numEdges;
+	uint hash = type;
+	hash += hash << 10;
+	hash ^= hash >> 6;
 	for (uint i = 0; i < numEdges; i++) {
-		hashvalue ^= (uint) ((uintptr_t) edges[i].node_ptr);
-		hashvalue = (hashvalue << 3) | (hashvalue >> 29);	//rotate left by 3 bits
-	}
-	return (uint) hashvalue;
+		uint c = (uint) ((uintptr_t) edges[i].node_ptr);
+		hash += c;
+		hash += hash << 10;
+		hash += hash >> 6;
+	}
+	hash += hash << 3;
+	hash ^= hash >> 11;
+	hash += hash << 15;
+	return hash;
 }
 
 bool compareNodes(Node *node, NodeType type, uint numEdges, Edge *edges) {
diff --git a/src/Test/Makefile b/src/Test/Makefile
index 0f1bc39..5ec7989 100644
--- a/src/Test/Makefile
+++ b/src/Test/Makefile
@@ -6,7 +6,7 @@ include $(BASE)/common.mk
 
 DEPS := $(join $(addsuffix ., $(dir $(OBJECTS))), $(addsuffix .d, $(notdir $(OBJECTS))))
 
-CPPFLAGS += -I$(BASE) -I$(BASE)/AST -I$(BASE)/Collections -I$(BASE)/Backend
+CPPFLAGS += -I$(BASE) -I$(BASE)/AST -I$(BASE)/Collections -I$(BASE)/Backend -I$(BASE)/Tuner
 
 all: $(OBJECTS) ../bin/run.sh
 
diff --git a/src/csolver.cc b/src/csolver.cc
index 95c06f8..533fc4b 100644
--- a/src/csolver.cc
+++ b/src/csolver.cc
@@ -465,7 +465,6 @@ int CSolver::solve() {
 		tuner = new DefaultTuner();
 		deleteTuner = true;
 	}
-	serialize();
 	
 	long long startTime = getTimeNano();
 	computePolarities(this);
-- 
2.34.1