common/worklist.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
   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 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include <stdarg.h>
  19 #include <string.h>
  20
  21 /* utility */
  22 #include "log.h"
  23 #include "mem.h"
  24 #include "support.h"
  25
  26 /* common */
  27 #include "city.h"
  28 #include "requirements.h"
  29 #include "unit.h"
  30
  31 #include "worklist.h"
  32
  33 /****************************************************************
  34   Initialize a worklist to be empty.
  35   For elements, only really need to set [0], but initialize the
  36   rest to avoid junk values in savefile.
  37 ****************************************************************/
  38 void worklist_init(struct worklist *pwl)
  39 {
  40   int i;
  41
  42   pwl->length = 0;
  43
  44   for (i = 0; i < MAX_LEN_WORKLIST; i++) {
  45     /* just setting the entry to zero: */
  46     pwl->entries[i].kind = VUT_NONE;
  47     /* all the union pointers should be in the same place: */
  48     pwl->entries[i].value.building = NULL;
  49   }
  50 }
  51
  52 /****************************************************************************
  53   Returns the number of entries in the worklist.  The returned value can
  54   also be used as the next available worklist index (assuming that
  55   len < MAX_LEN_WORKLIST).
  56 ****************************************************************************/
  57 int worklist_length(const struct worklist *pwl)
  58 {
  59   fc_assert_ret_val(pwl->length >= 0 && pwl->length <= MAX_LEN_WORKLIST, -1);
  60   return pwl->length;
  61 }
  62
  63 /****************************************************************
  64   Returns whether worklist has no elements.
  65 ****************************************************************/
  66 bool worklist_is_empty(const struct worklist *pwl)
  67 {
  68   return !pwl || pwl->length == 0;
  69 }
  70
  71 /****************************************************************
  72   Fill in the id and is_unit values for the head of the worklist
  73   if the worklist is non-empty.  Return 1 iff id and is_unit
  74   are valid.
  75 ****************************************************************/
  76 bool worklist_peek(const struct worklist *pwl, struct universal *prod)
  77 {
  78   return worklist_peek_ith(pwl, prod, 0);
  79 }
  80
  81 /****************************************************************
  82   Fill in the id and is_unit values for the ith element in the
  83   worklist. If the worklist has fewer than idx elements,
  84   return FALSE.
  85 ****************************************************************/
  86 bool worklist_peek_ith(const struct worklist *pwl,
  87                        struct universal *prod, int idx)
  88 {
  89   /* Out of possible bounds. */
  90   if (idx < 0 || pwl->length <= idx) {
  91     prod->kind = VUT_NONE;
  92     prod->value.building = NULL;
  93     return FALSE;
  94   }
  95
  96   *prod = pwl->entries[idx];
  97
  98   return TRUE;
  99 }
 100
 101 /****************************************************************
 102   Remove first element from worklist.
 103 ****************************************************************/
 104 void worklist_advance(struct worklist *pwl)
 105 {
 106   worklist_remove(pwl, 0);
 107 }
 108
 109 /****************************************************************
 110   Copy contents from worklist src to worklist dst.
 111 ****************************************************************/
 112 void worklist_copy(struct worklist *dst, const struct worklist *src)
 113 {
 114   fc_assert_ret(sizeof(*dst) == sizeof(*src));
 115   memcpy(dst, src, sizeof(*dst));
 116 }
 117
 118 /****************************************************************
 119   Remove element from position idx.
 120 ****************************************************************/
 121 void worklist_remove(struct worklist *pwl, int idx)
 122 {
 123   int i;
 124
 125   /* Don't try to remove something way outside of the worklist. */
 126   if (idx < 0 || pwl->length <= idx) {
 127     return;
 128   }
 129
 130   /* Slide everything up one spot. */
 131   for (i = idx; i < pwl->length - 1; i++) {
 132     pwl->entries[i] = pwl->entries[i + 1];
 133   }
 134   /* just setting the entry to zero: */
 135   pwl->entries[pwl->length - 1].kind = VUT_NONE;
 136   /* all the union pointers should be in the same place: */
 137   pwl->entries[pwl->length - 1].value.building = NULL;
 138   pwl->length--;
 139 }
 140
 141 /****************************************************************************
 142   Adds the id to the next available slot in the worklist.  'id' is the ID of
 143   the unit/building to be produced; is_unit specifies whether it's a unit or
 144   a building.  Returns TRUE if successful.
 145 ****************************************************************************/
 146 bool worklist_append(struct worklist *pwl, struct universal prod)
 147 {
 148   int next_index = worklist_length(pwl);
 149
 150   if (next_index >= MAX_LEN_WORKLIST) {
 151     return FALSE;
 152   }
 153
 154   pwl->entries[next_index] = prod;
 155   pwl->length++;
 156
 157   return TRUE;
 158 }
 159
 160 /****************************************************************************
 161   Inserts the production at the location idx in the worklist, thus moving
 162   all subsequent entries down.  'id' specifies the unit/building to
 163   be produced; is_unit tells whether it's a unit or building.  Returns TRUE
 164   if successful.
 165 ****************************************************************************/
 166 bool worklist_insert(struct worklist *pwl,
 167                      struct universal prod, int idx)
 168 {
 169   int new_len = MIN(pwl->length + 1, MAX_LEN_WORKLIST), i;
 170
 171   if (idx < 0 || idx > pwl->length) {
 172     return FALSE;
 173   }
 174
 175   /* move all active values down an index to get room for new id
 176    * move from [idx .. len - 1] to [idx + 1 .. len].  Any entries at the
 177    * end are simply lost. */
 178   for (i = new_len - 2; i >= idx; i--) {
 179     pwl->entries[i + 1] = pwl->entries[i];
 180   }
 181
 182   pwl->entries[idx] = prod;
 183   pwl->length = new_len;
 184
 185   return TRUE;
 186 }
 187
 188 /**************************************************************************
 189   Return TRUE iff the two worklists are equal.
 190 **************************************************************************/
 191 bool are_worklists_equal(const struct worklist *wlist1,
 192                          const struct worklist *wlist2)
 193 {
 194   int i;
 195
 196   if (wlist1->length != wlist2->length) {
 197     return FALSE;
 198   }
 199
 200   for (i = 0; i < wlist1->length; i++) {
 201     if (!are_universals_equal(&wlist1->entries[i], &wlist2->entries[i])) {
 202       return FALSE;
 203     }
 204   }
 205
 206   return TRUE;
 207 }