Files
@ r16010:3315aa6280e6
Branch filter:
Location: cpp/openttd-patchpack/source/src/pathfinder/npf/queue.h - annotation
r16010:3315aa6280e6
3.7 KiB
text/x-c
(svn r20713) -Fix (r20654): when ignoring action0 object properties, ignore property 13 correctly
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r15990:de3d8a27ca9a r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r15990:de3d8a27ca9a r15990:de3d8a27ca9a r15990:de3d8a27ca9a r15988:8f73c5ff20dd r15990:de3d8a27ca9a r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15988:8f73c5ff20dd r15988:8f73c5ff20dd r15983:f0411901aafb r15984:bcc367d75af3 r15985:7b20596488ea r15987:8f5915ae68a2 r15986:6938896f8f15 r13825:5de0a5d39b9e r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15989:2991c69fb193 r15982:9794718f9aff r15982:9794718f9aff r15982:9794718f9aff r15982:9794718f9aff r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r15610:623a23fb6560 r15610:623a23fb6560 r13825:5de0a5d39b9e r15613:193c12018337 r15613:193c12018337 r13825:5de0a5d39b9e r15610:623a23fb6560 r15610:623a23fb6560 r15613:193c12018337 r15613:193c12018337 r13825:5de0a5d39b9e r15610:623a23fb6560 r15610:623a23fb6560 r15613:193c12018337 r15613:193c12018337 r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r15610:623a23fb6560 r15610:623a23fb6560 r15613:193c12018337 r15613:193c12018337 r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e r13825:5de0a5d39b9e | /* $Id$ */
/*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
*/
/** @file queue.h Binary heap implementation, hash implementation. */
#ifndef QUEUE_H
#define QUEUE_H
//#define NOFREE
//#define QUEUE_DEBUG
//#define HASH_DEBUG
//#define HASH_STATS
struct BinaryHeapNode {
void *item;
int priority;
};
/**
* Binary Heap.
* For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
*/
struct BinaryHeap {
static const int BINARY_HEAP_BLOCKSIZE;
static const int BINARY_HEAP_BLOCKSIZE_BITS;
static const int BINARY_HEAP_BLOCKSIZE_MASK;
void Init(uint max_size);
bool Push(void *item, int priority);
void *Pop();
bool Delete(void *item, int priority);
void Clear(bool free_values);
void Free(bool free_values);
/**
* Get an element from the #elements.
* @param i Element to access (starts at offset \c 1).
* @return Value of the element.
*/
FORCEINLINE BinaryHeapNode &GetElement(uint i)
{
assert(i > 0);
return this->elements[(i - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][(i - 1) & BINARY_HEAP_BLOCKSIZE_MASK];
}
uint max_size;
uint size;
uint blocks; ///< The amount of blocks for which space is reserved in elements
BinaryHeapNode **elements;
};
/*
* Hash
*/
struct HashNode {
uint key1;
uint key2;
void *value;
HashNode *next;
};
/**
* 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);
struct Hash {
/* The hash function used */
Hash_HashProc *hash;
/* The amount of items in the hash */
uint size;
/* The number of buckets allocated */
uint num_buckets;
/* A pointer to an array of num_buckets buckets. */
HashNode *buckets;
/* A pointer to an array of numbuckets booleans, which will be true if
* there are any Nodes in the bucket */
bool *buckets_in_use;
};
/* Call these function to manipulate a hash */
/**
* Deletes the value with the specified key pair from the hash and returns
* that value. Returns NULL when the value was not present. The value returned
* is _not_ free()'d!
*/
void *Hash_Delete(Hash *h, uint key1, uint key2);
/**
* Sets the value associated with the given key pair to the given value.
* Returns the old value if the value was replaced, NULL when it was not yet present.
*/
void *Hash_Set(Hash *h, uint key1, uint key2, void *value);
/**
* Gets the value associated with the given key pair, or NULL when it is not
* present.
*/
void *Hash_Get(const Hash *h, uint key1, uint key2);
/* Call these function to create/destroy a hash */
/**
* 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, 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
* are left in the hash.
*/
void delete_Hash(Hash *h, bool free_values);
/**
* Cleans the hash, but keeps the memory allocated
*/
void clear_Hash(Hash *h, bool free_values);
/**
* Gets the current size of the Hash
*/
uint Hash_Size(const Hash *h);
#endif /* QUEUE_H */
|