utility/specpq.h

   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
  52 extern "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 /****************************************************************************
  97   Build a new queue.
  98   'initial_size' is the numer of queue items for which memory should be
  99   preallocated, that is, the initial size of the item array the queue
 100   uses. If you insert more than n items to the queue, another n items
 101   will be allocated automatically.
 102 ****************************************************************************/
 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 /****************************************************************************
 115   Destructor for queue structure.
 116 ****************************************************************************/
 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 /****************************************************************************
 126   Alternative destructor for queue structure.
 127 ****************************************************************************/
 128 static 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 /****************************************************************************
 145   Insert an item into the queue.
 146 ****************************************************************************/
 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 /****************************************************************************
 173   Set a better priority for datum. Insert if 'data' is not present yet.
 174 ****************************************************************************/
 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 /****************************************************************************
 204   Remove the highest-ranking item from the queue and store it in 'pdata'.
 205   'pdata' may be NULL. Return FALSE iff no item could be removed, because
 206   the queue was empty.
 207 ****************************************************************************/
 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   while (i <= s) {
 229     j = 2 * i;
 230     pcellj = pq->cells + j;
 231     if (j < pq->size && pcellj->priority < pq->cells[j + 1].priority) {
 232       j++;
 233       pcellj++;
 234     }
 235     if (pcellj->priority <= tmp.priority) {
 236       break;
 237     }
 238     *pcelli = *pcellj;
 239     i = j;
 240     pcelli = pcellj;
 241   }
 242   *pcelli = tmp;
 243   if (pdata) {
 244     *pdata = top;
 245   }
 246   return TRUE;
 247 }
 248
 249 /****************************************************************************
 250   Store the highest-ranking item in dest without removing it. Return FALSE
 251   if the queue is empty, in case 'pdata' is not set.
 252 ****************************************************************************/
 253 static inline bool SPECPQ_FOO(_pq_peek)(const SPECPQ_PQ *_pq,
 254                                         SPECPQ_DATA_TYPE *pdata)
 255 {
 256   const SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
 257
 258   if (pq->size == 1) {
 259     return FALSE;
 260   }
 261
 262   *pdata = pq->cells[1].data;
 263   return TRUE;
 264 }
 265
 266 /****************************************************************************
 267   Set the highest priority of the queue in 'datum_priority'. Return FALSE
 268   iff the queue is empty.
 269 ****************************************************************************/
 270 static inline bool SPECPQ_FOO(_pq_priority)(const SPECPQ_PQ *_pq,
 271                                             SPECPQ_PRIORITY_TYPE *ppriority)
 272
 273 {
 274   const SPECPQ_PQ_ *pq = (SPECPQ_PQ_ *) _pq;
 275
 276   if (pq->size == 1) {
 277     return FALSE;
 278   }
 279
 280   *ppriority = pq->cells[1].priority;
 281   return TRUE;
 282 }
 283
 284 #undef SPECPQ_TAG
 285 #undef SPECPQ_PRIORITY_TYPE
 286 #undef SPECPQ_DATA_TYPE
 287 #undef SPECPQ_PASTE_
 288 #undef SPECPQ_PASTE
 289 #undef SPECPQ_PQ
 290 #undef SPECPQ_PQ_
 291 #undef SPECPQ_CELL_
 292 #undef SPECPQ_FOO
 293
 294 #ifdef __cplusplus
 295 }
 296 #endif /* __cplusplus */