@@ -1286,7 +1286,7 @@ static const uint RIVER_HASH_SIZE = 8; /
* @param dir The unused direction.
* @return The hash for the tile.
*/
static uint River_Hash(uint tile, uint dir)
static uint River_Hash(TileIndex tile, Trackdir dir)
{
return GB(TileHash(TileX(tile), TileY(tile)), 0, RIVER_HASH_SIZE);
}
@@ -132,20 +132,20 @@ static uint NPFDistanceTrack(TileIndex t
/**
* Calculates a hash value for use in the NPF.
* @param key1 The TileIndex of the tile to hash
* @param key2 The Trackdir of the track on the tile.
* @param tile The TileIndex of the tile to hash
* @param dir The Trackdir of the track on the tile.
*
* @todo Think of a better hash.
static uint NPFHash(uint key1, uint key2)
static uint NPFHash(TileIndex tile, Trackdir dir)
/* TODO: think of a better hash? */
uint part1 = TileX(key1) & NPF_HASH_HALFMASK;
uint part2 = TileY(key1) & NPF_HASH_HALFMASK;
uint part1 = TileX(tile) & NPF_HASH_HALFMASK;
uint part2 = TileY(tile) & NPF_HASH_HALFMASK;
assert(IsValidTrackdir((Trackdir)key2));
assert(IsValidTile((TileIndex)key1));
return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * key2 / TRACKDIR_END)) % NPF_HASH_SIZE;
assert(IsValidTrackdir(dir));
assert(IsValidTile(tile));
return ((part1 << NPF_HASH_HALFBITS | part2) + (NPF_HASH_SIZE * dir / TRACKDIR_END)) % NPF_HASH_SIZE;
static int32_t NPFCalcZero(AyStar *as, AyStarNode *current, OpenListNode *parent)
@@ -366,9 +366,9 @@ void Hash::Clear(bool free_values)
* bucket, or nullptr if it is empty. prev can also be nullptr, in which case it is
* not used for output.
HashNode *Hash::FindNode(uint key1, uint key2, HashNode** prev_out) const
HashNode *Hash::FindNode(TileIndex tile, Trackdir dir, HashNode** prev_out) const
uint hash = this->hash(key1, key2);
uint hash = this->hash(tile, dir);
HashNode *result = nullptr;
/* Check if the bucket is empty */
@@ -376,7 +376,7 @@ HashNode *Hash::FindNode(uint key1, uint
if (prev_out != nullptr) *prev_out = nullptr;
result = nullptr;
/* Check the first node specially */
} else if (this->buckets[hash].key1 == key1 && this->buckets[hash].key2 == key2) {
} else if (this->buckets[hash].tile == tile && this->buckets[hash].dir == dir) {
/* Save the value */
result = this->buckets + hash;
@@ -386,7 +386,7 @@ HashNode *Hash::FindNode(uint key1, uint
HashNode *node;
for (node = prev->next; node != nullptr; node = node->next) {
if (node->key1 == key1 && node->key2 == key2) {
if (node->tile == tile && node->dir == dir) {
/* Found it */
result = node;
break;
@@ -403,11 +403,11 @@ HashNode *Hash::FindNode(uint key1, uint
* that value. Returns nullptr when the value was not present. The value returned
* is _not_ free()'d!
void *Hash::DeleteValue(uint key1, uint key2)
void *Hash::DeleteValue(TileIndex tile, Trackdir dir)
void *result;
HashNode *prev; // Used as output var for below function call
HashNode *node = this->FindNode(key1, key2, &prev);
HashNode *node = this->FindNode(tile, dir, &prev);
if (node == nullptr) {
/* not found */
@@ -426,7 +426,7 @@ void *Hash::DeleteValue(uint key1, uint
} else {
/* This was the last in this bucket
* Mark it as empty */
this->buckets_in_use[hash] = false;
@@ -446,10 +446,10 @@ void *Hash::DeleteValue(uint key1, uint
* Sets the value associated with the given key pair to the given value.
* Returns the old value if the value was replaced, nullptr when it was not yet present.
void *Hash::Set(uint key1, uint key2, void *value)
void *Hash::Set(TileIndex tile, Trackdir dir, void *value)
HashNode *prev;
if (node != nullptr) {
@@ -461,7 +461,7 @@ void *Hash::Set(uint key1, uint key2, vo
/* It is not yet present, let's add it */
if (prev == nullptr) {
/* The bucket is still empty */
this->buckets_in_use[hash] = true;
node = this->buckets + hash;
@@ -470,8 +470,8 @@ void *Hash::Set(uint key1, uint key2, vo
prev->next = node;
node->next = nullptr;
node->key1 = key1;
node->key2 = key2;
node->tile = tile;
node->dir = dir;
node->value = value;
this->size++;
return nullptr;
@@ -481,9 +481,9 @@ void *Hash::Set(uint key1, uint key2, vo
* Gets the value associated with the given key pair, or nullptr when it is not
* present.
void *Hash::Get(uint key1, uint key2) const
void *Hash::Get(TileIndex tile, Trackdir dir) const
HashNode *node = this->FindNode(key1, key2, nullptr);
HashNode *node = this->FindNode(tile, dir, nullptr);
return (node != nullptr) ? node->value : nullptr;
@@ -10,6 +10,9 @@
#ifndef QUEUE_H
#define QUEUE_H
#include "../../tile_type.h"
#include "../../track_type.h"
//#define HASH_STATS
@@ -58,8 +61,8 @@ struct BinaryHeap {
* Hash
struct HashNode {
uint key1;
uint key2;
TileIndex tile;
Trackdir dir;
void *value;
HashNode *next;
};
@@ -67,7 +70,7 @@ struct HashNode {
* 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);
typedef uint Hash_HashProc(TileIndex tile, Trackdir dir);
struct Hash {
/* The hash function used */
Hash_HashProc *hash;
@@ -83,10 +86,10 @@ struct Hash {
void Init(Hash_HashProc *hash, uint num_buckets);
void *Get(uint key1, uint key2) const;
void *Set(uint key1, uint key2, void *value);
void *Get(TileIndex tile, Trackdir dir) const;
void *Set(TileIndex tile, Trackdir dir, void *value);
void *DeleteValue(uint key1, uint key2);
void *DeleteValue(TileIndex tile, Trackdir dir);
void Clear(bool free_values);
void Delete(bool free_values);
@@ -103,7 +106,7 @@ protected:
#ifdef HASH_STATS
void PrintStatistics() const;
#endif
HashNode *FindNode(uint key1, uint key2, HashNode** prev_out) const;
HashNode *FindNode(TileIndex tile, Trackdir dir, HashNode** prev_out) const;
#endif /* QUEUE_H */
Status change: