From da3621c1804e6da9cefd712da9d0dd48fff61add Mon Sep 17 00:00:00 2001
From: matthijs <matthijs@openttd.org>
Date: Thu, 7 Apr 2005 19:19:16 +0000
Subject: (svn r2165) - Codechange: [NPF] Properly enummed NPF hash size, it is
 easily changable now. - Codechange: [NPF] Improved the NPF hash calculation
 slightly. - Codechange: [NPF] Increased hash size, should speed up somewhat.

---
 npf.c   | 12 +++++++++++-
 npf.h   |  7 +++++++
 queue.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++--
 queue.h |  6 ++++--
 4 files changed, 69 insertions(+), 5 deletions(-)

diff --git a/npf.c b/npf.c
index 15f11dfcb..66061d1ae 100644
--- a/npf.c
+++ b/npf.c
@@ -102,9 +102,19 @@ static const uint _trackdir_length[14] = {
 
 uint NTPHash(uint key1, uint key2)
 {
+	/* This function uses the old hash, which is fixed on 10 bits (1024 buckets) */
 	return PATHFIND_HASH_TILE(key1);
 }
 
+uint NPFHash(uint key1, uint key2)
+{
+	/* TODO: think of a better hash? */
+	uint part1 = TileX(key1) & NPF_HASH_HALFMASK;
+	uint part2 = TileY(key1) & NPF_HASH_HALFMASK;
+	/* The value of 14 below is based on the maximum value of key2 (13) */
+	return ((((part1 << NPF_HASH_HALFBITS) | part2)) + (NPF_HASH_SIZE * key2 / 14)) % NPF_HASH_SIZE;
+}
+
 int32 NPFCalcZero(AyStar* as, AyStarNode* current, OpenListNode* parent) {
 	return 0;
 }
@@ -809,7 +819,7 @@ NPFFoundTargetData NPFRouteToDepotTrialError(TileIndex tile, byte trackdir, Tran
 
 void InitializeNPF(void)
 {
-	init_AyStar(&_npf_aystar, NTPHash, 1024);
+	init_AyStar(&_npf_aystar, NPFHash, NPF_HASH_SIZE);
 	_npf_aystar.loops_per_tick = 0;
 	_npf_aystar.max_path_cost = 0;
 	_npf_aystar.max_search_nodes = 0;
diff --git a/npf.h b/npf.h
index be2fb95c1..6f665ec7e 100644
--- a/npf.h
+++ b/npf.h
@@ -8,6 +8,13 @@
 //#define NPF_DEBUG
 //#define NPF_MARKROUTE //Mark the routes considered by the pathfinder by
 //mowing grass
+enum {
+	NPF_HASH_BITS = 12, /* The size of the hash used in pathfinding. Just changing this value should be sufficient to change the hash size. Should be an even value. */
+	/* Do no change below values */
+	NPF_HASH_SIZE = 1 << NPF_HASH_BITS,
+	NPF_HASH_HALFBITS = NPF_HASH_BITS / 2,
+	NPF_HASH_HALFMASK = (1 << NPF_HASH_HALFBITS) - 1
+};
 
 typedef struct NPFFindStationOrTileData { /* Meant to be stored in AyStar.targetdata */
 	TileIndex dest_coords; /* An indication of where the station is, for heuristic purposes, or the target tile */
diff --git a/queue.c b/queue.c
index 21c163688..8602bb673 100644
--- a/queue.c
+++ b/queue.c
@@ -443,9 +443,10 @@ Queue* new_BinaryHeap(uint max_size) {
  * Hash
  */
 
-void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets) {
+void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets) {
 	/* Allocate space for the Hash, the buckets and the bucket flags */
-	int i;
+	uint i;
+	uint max_hash;
 	assert(h);
 	#ifdef HASH_DEBUG
 	debug("Allocated hash: %p", h);
@@ -502,10 +503,54 @@ void delete_Hash(Hash* h, bool free_values) {
 		free(h);
 }
 
+void stat_Hash(Hash* h)
+{
+	uint used_buckets = 0;
+	uint max_collision = 0;
+	uint max_usage = 0;
+	uint usage[200];
+	uint i,j;
+	uint collision;
+	HashNode* node;
+
+	for (i=0;i<200;i++) usage[i] = 0;
+	for (i=0;i<h->num_buckets;i++) {
+		collision = 0;
+		if (h->buckets_in_use[i]) {
+			used_buckets++;
+			node = &h->buckets[i];
+			while (node != NULL) {
+				collision++;
+				node = node->next;
+			}
+			if (collision > max_collision) max_collision = collision;
+		}
+		if (collision > 199) collision = 199;
+		usage[collision]++;
+		if (collision >0 && usage[collision] >= max_usage) max_usage = usage[collision];
+	}
+	printf("---\nHash size: %d\nNodes used: %d\nNon empty buckets: %d\nMax collision: %d\n", h->num_buckets, h->size, used_buckets, max_collision);
+	printf("{ ");
+	for (i=0;i<=max_collision;i++)
+		if (usage[i]) {
+			printf("%d:%d ", i, usage[i]);
+			/*if (i>0)
+				for (j=0;j<(usage[i] * 160 / 800);j++)
+					printf("#");
+			printf("\n");
+			*/
+		}
+	printf ("}\n");
+}
+
 void clear_Hash(Hash* h, bool free_values)
 {
 	uint i;
 	HashNode* node;
+#ifdef HASH_STATS
+	if (h->size > 2000)
+		stat_Hash(h);
+#endif
 	/* Iterate all buckets */
 	for (i=0;i<h->num_buckets;i++)
 	{
diff --git a/queue.h b/queue.h
index 56ecd2a3e..c4a1bf0ee 100644
--- a/queue.h
+++ b/queue.h
@@ -4,6 +4,7 @@
 //#define NOFREE
 //#define QUEUE_DEBUG
 //#define HASH_DEBUG
+//#define HASH_STATS
 
 
 typedef struct Queue Queue;
@@ -142,7 +143,8 @@ struct HashNode {
 	void* value;
 	HashNode* next;
 };
-/* Generates a hash code from the given key pair. You should make sure that
+/**
+ * Generates a hash code from the given key pair. You should make sure that
  * the resulting range is clearly defined.
  */
 typedef uint Hash_HashProc(uint key1, uint key2);
@@ -184,7 +186,7 @@ void* Hash_Get(Hash* h, uint key1, uint key2);
 Hash* new_Hash(Hash_HashProc* hash, int num_buckets);
 /* Builds a new hash in an existing struct. Make sure that hash() always
  * returns a hash less than num_buckets! Call delete_hash after use */
-void init_Hash(Hash* h, Hash_HashProc* hash, int num_buckets);
+void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets);
 /*
  * Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash
  * & friends. If free is true, it will call free() on all the values that
-- 
cgit v1.2.3-54-g00ecf