Files
@ r13579:0b78e691a532
Branch filter:
Location: cpp/openttd-patchpack/source/src/queue.h - annotation
r13579:0b78e691a532
4.8 KiB
text/x-c
(svn r18113) -Fix: RTL glitch in play heightmap window
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 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r12768:980ae0491352 r12768:980ae0491352 r12768:980ae0491352 r12768:980ae0491352 r12768:980ae0491352 r12768:980ae0491352 r12768:980ae0491352 r9111:983de9c5a848 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6248:b940b09d7ab8 r7318:844268a38029 r10647:62911ec68e89 r10647:62911ec68e89 r7318:844268a38029 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r10647:62911ec68e89 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6352:af9fc661a26d r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6352:af9fc661a26d r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6248:b940b09d7ab8 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r6248:b940b09d7ab8 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r6352:af9fc661a26d r5475:3f5cd13d1b63 r7318:844268a38029 r6352:af9fc661a26d r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r6352:af9fc661a26d r5475:3f5cd13d1b63 r7318:844268a38029 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r6352:af9fc661a26d r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 r7318:844268a38029 r5475:3f5cd13d1b63 r5475:3f5cd13d1b63 | /* $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 Simple Queue/Hash implementations. */
#ifndef QUEUE_H
#define QUEUE_H
//#define NOFREE
//#define QUEUE_DEBUG
//#define HASH_DEBUG
//#define HASH_STATS
struct Queue;
typedef bool Queue_PushProc(Queue *q, void *item, int priority);
typedef void *Queue_PopProc(Queue *q);
typedef bool Queue_DeleteProc(Queue *q, void *item, int priority);
typedef void Queue_ClearProc(Queue *q, bool free_values);
typedef void Queue_FreeProc(Queue *q, bool free_values);
struct InsSortNode {
void *item;
int priority;
InsSortNode *next;
};
struct BinaryHeapNode {
void *item;
int priority;
};
struct Queue{
/*
* Pushes an element into the queue, at the appropriate place for the queue.
* Requires the queue pointer to be of an appropriate type, of course.
*/
Queue_PushProc *push;
/*
* Pops the first element from the queue. What exactly is the first element,
* is defined by the exact type of queue.
*/
Queue_PopProc *pop;
/*
* Deletes the item from the queue. priority should be specified if
* known, which speeds up the deleting for some queue's. Should be -1
* if not known.
*/
Queue_DeleteProc *del;
/* Clears the queue, by removing all values from it. It's state is
* effectively reset. If free_items is true, each of the items cleared
* in this way are free()'d.
*/
Queue_ClearProc *clear;
/* Frees the queue, by reclaiming all memory allocated by it. After
* this it is no longer usable. If free_items is true, any remaining
* items are free()'d too.
*/
Queue_FreeProc *free;
union {
struct {
InsSortNode *first;
} inssort;
struct {
uint max_size;
uint size;
uint blocks; ///< The amount of blocks for which space is reserved in elements
BinaryHeapNode **elements;
} binaryheap;
} data;
};
/**
* Insertion Sorter
*/
/* Initializes a inssort and allocates internal memory. There is no maximum
* size */
void init_InsSort(Queue *q);
/*
* Binary Heap
* For information, see:
* http://www.policyalmanac.org/games/binaryHeaps.htm
*/
/* The amount of elements that will be malloc'd at a time */
#define BINARY_HEAP_BLOCKSIZE_BITS 10
/** Initializes a binary heap and allocates internal memory for maximum of
* max_size elements */
void init_BinaryHeap(Queue *q, uint max_size);
/*
* 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 */
|