Files
@ r21576:8f655ba7bab2
Branch filter:
Location: cpp/openttd-patchpack/source/src/pathfinder/npf/queue.h - annotation
r21576:8f655ba7bab2
2.8 KiB
text/x-c
(svn r26700) -Fix [FS#6066]: incorrect saving of order backups
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 | 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 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 r18782:6453522c2154 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 r16170:f2aca77ee29b r16176:ca654484bf24 r16176:ca654484bf24 r16171:dbd2b98ee201 r16172:25305cabce22 r16171:dbd2b98ee201 r16173:73db41aab83f r16173:73db41aab83f r16174:afa94818a5e8 r16175:8824ce9be711 r16174:afa94818a5e8 r16170:f2aca77ee29b r16170:f2aca77ee29b r16170:f2aca77ee29b r18782:6453522c2154 r16170:f2aca77ee29b r16170:f2aca77ee29b r16170:f2aca77ee29b r16177:6b0555337854 r16177:6b0555337854 r16177:6b0555337854 r16177:6b0555337854 r16177:6b0555337854 r16178:ec3cf64c17e2 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 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.
*/
inline 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;
void Init(Hash_HashProc *hash, uint num_buckets);
void *Get(uint key1, uint key2) const;
void *Set(uint key1, uint key2, void *value);
void *DeleteValue(uint key1, uint key2);
void Clear(bool free_values);
void Delete(bool free_values);
/**
* Gets the current size of the hash.
*/
inline uint GetSize() const
{
return this->size;
}
protected:
#ifdef HASH_STATS
void PrintStatistics() const;
#endif
HashNode *FindNode(uint key1, uint key2, HashNode** prev_out) const;
};
#endif /* QUEUE_H */
|