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   dst->length = src->length;
 115
 116   memcpy(dst->entries, src->entries, sizeof(struct universal) * src->length);
 117 }
 118
 119 /****************************************************************
 120   Remove element from position idx.
 121 ****************************************************************/
 122 void worklist_remove(struct worklist *pwl, int idx)
 123 {
 124   int i;
 125
 126   /* Don't try to remove something way outside of the worklist. */
 127   if (idx < 0 || pwl->length <= idx) {
 128     return;
 129   }
 130
 131   /* Slide everything up one spot. */
 132   for (i = idx; i < pwl->length - 1; i++) {
 133     pwl->entries[i] = pwl->entries[i + 1];
 134   }
 135   /* just setting the entry to zero: */
 136   pwl->entries[pwl->length - 1].kind = VUT_NONE;
 137   /* all the union pointers should be in the same place: */
 138   pwl->entries[pwl->length - 1].value.building = NULL;
 139   pwl->length--;
 140 }
 141
 142 /****************************************************************************
 143   Adds the id to the next available slot in the worklist.  'id' is the ID of
 144   the unit/building to be produced; is_unit specifies whether it's a unit or
 145   a building.  Returns TRUE if successful.
 146 ****************************************************************************/
 147 bool worklist_append(struct worklist *pwl, const struct universal *prod)
 148 {
 149   int next_index = worklist_length(pwl);
 150
 151   if (next_index >= MAX_LEN_WORKLIST) {
 152     return FALSE;
 153   }
 154
 155   pwl->entries[next_index] = *prod;
 156   pwl->length++;
 157
 158   return TRUE;
 159 }
 160
 161 /****************************************************************************
 162   Inserts the production at the location idx in the worklist, thus moving
 163   all subsequent entries down.  'id' specifies the unit/building to
 164   be produced; is_unit tells whether it's a unit or building.  Returns TRUE
 165   if successful.
 166 ****************************************************************************/
 167 bool worklist_insert(struct worklist *pwl, const struct universal *prod,
 168                      int idx)
 169 {
 170   int new_len = MIN(pwl->length + 1, MAX_LEN_WORKLIST), i;
 171
 172   if (idx < 0 || idx > pwl->length) {
 173     return FALSE;
 174   }
 175
 176   /* move all active values down an index to get room for new id
 177    * move from [idx .. len - 1] to [idx + 1 .. len].  Any entries at the
 178    * end are simply lost. */
 179   for (i = new_len - 2; i >= idx; i--) {
 180     pwl->entries[i + 1] = pwl->entries[i];
 181   }
 182
 183   pwl->entries[idx] = *prod;
 184   pwl->length = new_len;
 185
 186   return TRUE;
 187 }
 188
 189 /**************************************************************************
 190   Return TRUE iff the two worklists are equal.
 191 **************************************************************************/
 192 bool are_worklists_equal(const struct worklist *wlist1,
 193                          const struct worklist *wlist2)
 194 {
 195   int i;
 196
 197   if (wlist1->length != wlist2->length) {
 198     return FALSE;
 199   }
 200
 201   for (i = 0; i < wlist1->length; i++) {
 202     if (!are_universals_equal(&wlist1->entries[i], &wlist2->entries[i])) {
 203       return FALSE;
 204     }
 205   }
 206
 207   return TRUE;
 208 }