Freeciv-3.2: /fast/freeciv/nightly/S3_2/utility/specpq.h Source File

Freeciv-3.2

Loading...
Searching...
No Matches
specpq.h
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 2002 - The Freeciv Project
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13
14/* specpqs: "specific priority queues".
15 *
16 * This file is used to implement a "specific" priority queues.
17 * That is, a (sometimes) type-checked priority queue. (Or at least a
18 * priority queue with related functions with distinctly typed parameters.)
19 *
20 * Before including this file, you must define the following:
21 * SPECPQ_TAG - this tag will be used to form names for functions etc.
22 * SPECPQ_PRIORITY_TYPE - the type for the priority property of the cells.
23 * SPECPQ_DATA_TYPE - the type for the data property of the cells.
24 *
25 * Assuming SPECPQ_TAG were 'foo', SPECPQ_PRIORITY_TYPE were 'priority_t',
26 * and SPECPQ_DATA_TYPE were 'data_t'.
27 * including this file would provide a struct definition for:
28 * struct foo_pq;
29 *
30 * function typedefs:
31 * typedef void (*foo_pq_data_free_fn_t) (data_t);
32 *
33 * and prototypes for the following functions:
34 * struct foo_pq *foo_pq_new(int initial_size);
35 * void foo_pq_destroy(struct foo_pq *pq);
36 * void foo_pq_destroy_full(struct foo_pq *pq,
37 * foo_pq_data_free_fn_t data_free);
38 * void foo_pq_insert(struct foo_pq *pq, data_t data,
39 * priority_t priority);
40 * void foo_pq_replace(struct foo_pq *pq, data_t data,
41 * priority_t priority);
42 * bool foo_pq_remove(struct foo_pq *pq, data_t *pdata);
43 * bool foo_pq_peek(const struct foo_pq *pq, data_t *pdata);
44 * bool foo_pq_priority(const struct foo_pq *pq, priority_t *ppriority);
45 *
46 * Note this is not protected against multiple inclusions; this is so that
47 * you can have multiple different speclists. For each speclist, this file
48 * should be included _once_, inside a .h file which _is_ itself protected
49 * against multiple inclusions. */
50
51#ifdef __cplusplus
52extern "C" {
53#endif /* __cplusplus */
54
55/* utility */
56#include "mem.h"
57
58#ifndef SPECPQ_TAG
59#error Must define a SPECPQ_TAG to use this header
60#endif
61#ifndef SPECPQ_PRIORITY_TYPE
62#error Must define a SPECPQ_PRIORITY_TYPE to use this header
63#endif
64#ifndef SPECPQ_DATA_TYPE
65#error Must define a SPECPQ_DATA_TYPE to use this header
66#endif
67
68#define SPECPQ_PASTE_(x, y) x ## y
69#define SPECPQ_PASTE(x, y) SPECPQ_PASTE_(x, y)
70
71#define SPECPQ_PQ struct SPECPQ_PASTE(SPECPQ_TAG, _pq)
72#define SPECPQ_PQ_ struct SPECPQ_PASTE(SPECPQ_TAG, _pq_private_)
73#define SPECPQ_CELL_ struct SPECPQ_PASTE(SPECPQ_TAG, _cell_private_)
74#define SPECPQ_FOO(suffix) SPECPQ_PASTE(SPECPQ_TAG, suffix)
75
76/* Dummy type. Actually a SPECPQ_PQ_, and not defined anywhere. */
77 SPECPQ_PQ;
78
79/* Function related typedefs. */
80 typedef void (*SPECPQ_FOO(_pq_data_free_fn_t)) (SPECPQ_DATA_TYPE);
81
82
83/* Private. */
84 SPECPQ_CELL_ {
85 SPECPQ_DATA_TYPE data;
86 SPECPQ_PRIORITY_TYPE priority;
87};
88
89 SPECPQ_PQ_ {
90 int size;
91 int avail;
92 int step;
93 SPECPQ_CELL_ *cells;
94};
95
96/************************************************************************/
103 static inline SPECPQ_PQ *SPECPQ_FOO(_pq_new)(int initial_size)
104{
105 SPECPQ_PQ_ *pq = fc_malloc(sizeof(*pq));
106
107 pq->cells = fc_malloc(sizeof(*pq->cells) * initial_size);
108 pq->avail = initial_size;
109 pq->step = initial_size;
110 pq->size = 1;
111 return (SPECPQ_PQ *) pq;
112}
113
114/************************************************************************/
117 static inline void SPECPQ_FOO(_pq_destroy)(SPECPQ_PQ *_pq)
118{
119 SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
120
121 free(pq->cells);
122 free(pq);
123}
124
125/************************************************************************/
128static inline void
129 SPECPQ_FOO(_pq_destroy_full)(SPECPQ_PQ *_pq,
130 SPECPQ_FOO(_pq_data_free_fn_t) data_free)
131{
132 SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
133 int i;
134
135 if (data_free != NULL) {
136 for (i = 1; i < pq->size; i++) {
137 data_free(pq->cells[i].data);
138 }
139 }
140 free(pq->cells);
141 free(pq);
142}
143
144/************************************************************************/
147 static inline void SPECPQ_FOO(_pq_insert)(SPECPQ_PQ *_pq,
148 SPECPQ_DATA_TYPE data,
149 SPECPQ_PRIORITY_TYPE priority)
150{
151 SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
152 int i, j;
153
154 /* Allocate more memory if necessary. */
155 if (pq->size >= pq->avail) {
156 int newsize = pq->size + pq->step;
157
158 pq->cells = fc_realloc(pq->cells, sizeof(*pq->cells) * newsize);
159 pq->avail = newsize;
160 }
161
162 /* Insert item. */
163 i = pq->size++;
164 while (i > 1 && (j = i / 2) && pq->cells[j].priority < priority) {
165 pq->cells[i] = pq->cells[j];
166 i = j;
167 }
168 pq->cells[i].data = data;
169 pq->cells[i].priority = priority;
170}
171
172/************************************************************************/
175 static inline void SPECPQ_FOO(_pq_replace)(SPECPQ_PQ *_pq,
176 SPECPQ_DATA_TYPE data,
177 SPECPQ_PRIORITY_TYPE priority)
178{
179 SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
180 int i, j;
181
182 /* Lookup for 'data'... */
183 for (i = pq->size - 1; i >= 1; i--) {
184 if (pq->cells[i].data == data) {
185 break;
186 }
187 }
188
189 if (i == 0) {
190 /* Not found, insert. */
191 SPECPQ_FOO(_pq_insert)(_pq, data, priority);
192 } else if (pq->cells[i].priority < priority) {
193 /* Found, percolate-up. */
194 while ((j = i / 2) && pq->cells[j].priority < priority) {
195 pq->cells[i] = pq->cells[j];
196 i = j;
197 }
198 pq->cells[i].data = data;
199 pq->cells[i].priority = priority;
200 }
201}
202
203/************************************************************************/
208 static inline bool SPECPQ_FOO(_pq_remove)(SPECPQ_PQ *_pq,
209 SPECPQ_DATA_TYPE *pdata)
210{
211 SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
212 SPECPQ_CELL_ tmp;
213 SPECPQ_CELL_ *pcelli, *pcellj;
214 SPECPQ_DATA_TYPE top;
215 int i, j, s;
216
217 if (pq->size == 1) {
218 return FALSE;
219 }
220
221 fc_assert_ret_val(pq->size <= pq->avail, FALSE);
222 top = pq->cells[1].data;
223 pq->size--;
224 tmp = pq->cells[pq->size];
225 s = pq->size / 2;
226 i = 1;
227 pcelli = pq->cells + 1;
228
229 while (i <= s) {
230 j = 2 * i;
231 pcellj = pq->cells + j;
232 if (j < pq-> size && pcellj->priority < pq->cells[j + 1].priority) {
233 j++;
234 pcellj++;
235 }
236 if (pcellj->priority <= tmp.priority) {
237 break;
238 }
239 *pcelli = *pcellj;
240 i = j;
241 pcelli = pcellj;
242 }
243 *pcelli = tmp;
244 if (pdata) {
245 *pdata = top;
246 }
247
248 return TRUE;
249}
250
251/************************************************************************/
255 static inline bool SPECPQ_FOO(_pq_peek)(const SPECPQ_PQ *_pq,
256 SPECPQ_DATA_TYPE *pdata)
257{
258 const SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
259
260 if (pq->size == 1) {
261 return FALSE;
262 }
263
264 *pdata = pq->cells[1].data;
265 return TRUE;
266}
267
268/************************************************************************/
272 static inline bool SPECPQ_FOO(_pq_priority)(const SPECPQ_PQ *_pq,
273 SPECPQ_PRIORITY_TYPE *ppriority)
274{
275 const SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
276
277 if (pq->size == 1) {
278 return FALSE;
279 }
280
281 *ppriority = pq->cells[1].priority;
282 return TRUE;
283}
284
285#undef SPECPQ_TAG
286#undef SPECPQ_PRIORITY_TYPE
287#undef SPECPQ_DATA_TYPE
288#undef SPECPQ_PASTE_
289#undef SPECPQ_PASTE
290#undef SPECPQ_PQ
291#undef SPECPQ_PQ_
292#undef SPECPQ_CELL_
293#undef SPECPQ_FOO
294
295#ifdef __cplusplus
296}
297#endif /* __cplusplus */
incite_cost
char * incite_cost
Definition comments.c:74
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
mem.h
fc_realloc
#define fc_realloc(ptr, sz)
Definition mem.h:36
fc_malloc
#define fc_malloc(sz)
Definition mem.h:34
SPECPQ_PRIORITY_TYPE
#define SPECPQ_PRIORITY_TYPE
Definition path_finding.c:38
SPECPQ_DATA_TYPE
#define SPECPQ_DATA_TYPE
Definition path_finding.c:37
SPECPQ_FOO
#define SPECPQ_FOO(suffix)
Definition specpq.h:74
_pq_insert
static void SPECPQ_FOO() _pq_insert(SPECPQ_PQ *_pq, SPECPQ_DATA_TYPE data, SPECPQ_PRIORITY_TYPE priority)
Definition specpq.h:147
SPECPQ_CELL_
#define SPECPQ_CELL_
Definition specpq.h:73
_pq_replace
static void SPECPQ_FOO() _pq_replace(SPECPQ_PQ *_pq, SPECPQ_DATA_TYPE data, SPECPQ_PRIORITY_TYPE priority)
Definition specpq.h:175
_pq_destroy
static void SPECPQ_FOO() _pq_destroy(SPECPQ_PQ *_pq)
Definition specpq.h:117
SPECPQ_PQ
#define SPECPQ_PQ
Definition specpq.h:71
_pq_peek
static bool SPECPQ_FOO() _pq_peek(const SPECPQ_PQ *_pq, SPECPQ_DATA_TYPE *pdata)
Definition specpq.h:255
cells
SPECPQ_CELL_ * cells
Definition specpq.h:93
_pq_destroy_full
static void SPECPQ_FOO() _pq_destroy_full(SPECPQ_PQ *_pq, SPECPQ_FOO(_pq_data_free_fn_t) data_free)
Definition specpq.h:129
priority
SPECPQ_PRIORITY_TYPE priority
Definition specpq.h:86
_pq_new
static SPECPQ_PQ *SPECPQ_FOO() _pq_new(int initial_size)
Definition specpq.h:103
avail
int avail
Definition specpq.h:91
step
int step
Definition specpq.h:92
SPECPQ_PQ_
#define SPECPQ_PQ_
Definition specpq.h:72
_pq_remove
static bool SPECPQ_FOO() _pq_remove(SPECPQ_PQ *_pq, SPECPQ_DATA_TYPE *pdata)
Definition specpq.h:208
_pq_priority
static bool SPECPQ_FOO() _pq_priority(const SPECPQ_PQ *_pq, SPECPQ_PRIORITY_TYPE *ppriority)
Definition specpq.h:272
size
size_t size
Definition specvec.h:72
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47