git.pond.sub.org Git - empserver/blob - src/lib/as/as_cache.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2010, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                           Ken Stevens, Steve McClure
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  *  ---
  21  *
  22  *  See files README, COPYING and CREDITS in the root of the source
  23  *  tree for related information and legal notices.  It is expected
  24  *  that future projects/authors will amend these files as needed.
  25  *
  26  *  ---
  27  *
  28  *  as_cache.c: Routines used to create/delete caches of A* paths.
  29  *
  30  *  Known contributors to this file:
  31  *     Steve McClure, 1998
  32  */
  33
  34 #include <config.h>
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include "as.h"
  39 #include "optlist.h"
  40
  41 /* The way this works is interesting. :) */
  42 /* We keep a pointer to a list of pointers.  The index into this list
  43  * is the y coordinate of the from sector.  This member points to a list
  44  * of from sectors on that y coordinate.  So, we march that list checking
  45  * the x value to find the from x,y we want. */
  46 /* Once we find the from x,y, that node has the same type of pointer to
  47  * a list of pointers.  The index into this list is the y coordinate of
  48  * the to sector.  This member points to a list of to sectors on that y
  49  * coordinate.  So, we march that list checking the x value to find the
  50  * to x,y we want. */
  51 /* These lists are dynamically created since the world is dynamically sized. */
  52 /* See, I told you it was interesting. :) */
  53
  54 static struct as_frompath **fromhead = (struct as_frompath **)0;
  55
  56 /* Note that we only want to cache during updates.  Other times, it
  57  * probably doesn't make much sense, but can be done. */
  58
  59 static int as_cachepath_on = 0; /* Default to off */
  60
  61 #ifdef AS_STATS
  62 unsigned as_cache_tries, as_cache_hits;
  63 #define as_cache_try() ((void)as_cache_tries++)
  64 #define as_cache_hit() ((void)as_cache_hits++)
  65 #else
  66 #define as_cache_try() ((void)0)
  67 #define as_cache_hit() ((void)0)
  68 #endif
  69
  70 void
  71 as_enable_cachepath(void)
  72 {
  73     as_cachepath_on = 1;
  74 }
  75
  76 void
  77 as_disable_cachepath(void)
  78 {
  79     as_cachepath_on = 0;
  80 }
  81
  82 /* Note we want these to be as fast as possible */
  83
  84 void
  85 as_add_cachepath(struct as_data *adp)
  86 {
  87     struct as_frompath *from;
  88     struct as_topath *to = (struct as_topath *)0;
  89     struct as_node *np;
  90
  91     /* Don't do anything if we aren't cacheing these */
  92     if (as_cachepath_on == 0)
  93         return;
  94
  95     /* Note we will only allocate this once.  Afterwards, we just keep
  96      * zeroing it since it's rather small and we don't need to re-allocate
  97      * each time. */
  98     if (fromhead == NULL) {
  99         fromhead = calloc(1, sizeof(struct as_frompath *) * WORLD_Y);
 100         if (fromhead == NULL)
 101             return;
 102     }
 103
 104     np = adp->head->np;
 105     for (from = fromhead[adp->from.y]; from; from = from->next)
 106         if (from->x == adp->from.x)
 107             break;
 108     if (from) {
 109         for (to = from->tolist[np->c.y]; to; to = to->next) {
 110             if (to->x == np->c.x) {
 111                 /* It is already here!  Don't bother adding it again */
 112                 return;
 113             }
 114         }
 115     } else {
 116         /* We must make a new one of these */
 117         from = malloc(sizeof(struct as_frompath));
 118         if (from == NULL)
 119             return;
 120         /* And set some stuff */
 121         from->x = adp->from.x;
 122         /* Here we malloc a whole bunch of tolist pointers. */
 123         from->tolist = calloc(1, sizeof(struct as_topath *) * WORLD_Y);
 124         /* Now, add from to the global list */
 125         from->next = fromhead[adp->from.y];
 126         fromhead[adp->from.y] = from;
 127     }
 128     if (!to) {
 129         /* We must make a new one */
 130         to = malloc(sizeof(struct as_topath));
 131         /* We can't, sorry */
 132         if (to == NULL)
 133             return;
 134         /* Now set some stuff */
 135         to->x = np->c.x;
 136         /* Now add it to the list we are in */
 137         to->next = from->tolist[np->c.y];
 138         from->tolist[np->c.y] = to;
 139     }
 140     /* Now, make the path */
 141     as_makepath(adp);
 142     /* Now, take the path */
 143     to->path = adp->path;
 144     /* And clear the path in the adp */
 145     adp->path = NULL;
 146 }
 147
 148 void
 149 as_clear_cachepath(void)
 150 {
 151     struct as_frompath *from, *from2;
 152     struct as_topath *to, *to2;
 153     int i, j;
 154 #ifdef AS_STATS
 155     size_t index_sz = 0;
 156     unsigned index_nb = 0, paths_nb = 0, paths = 0;
 157 #define stats_index(sz) ((void)(index_sz += (sz), index_nb++))
 158 #else
 159 #define stats_index(sz) ((void)0)
 160 #endif
 161
 162     /* Cache not used yet :) */
 163     if (fromhead == NULL)
 164         return;
 165
 166     for (j = 0; j < WORLD_Y; j++) {
 167         for (from = fromhead[j]; from; from = from2) {
 168             for (i = 0; i < WORLD_Y; i++) {
 169                 for (to = from->tolist[i]; to; to = to2) {
 170                     to2 = to->next;
 171                     /* Free this path */
 172 #ifdef AS_STATS
 173                     {
 174                         struct as_path *pp;
 175                         for (pp = to->path; pp; pp = pp->next)
 176                             paths_nb++;
 177                         paths++;
 178                     }
 179 #endif
 180                     as_free_path(to->path);
 181                     /* Free this node */
 182                     free(to);
 183                     stats_index(sizeof(*to));
 184                 }
 185             }
 186             /* Now, free the list of lists */
 187             free(from->tolist);
 188             stats_index(WORLD_Y * sizeof(*from->tolist));
 189             /* Save the next pointer */
 190             from2 = from->next;
 191             /* now, free this from node */
 192             free(from);
 193             stats_index(sizeof(*from));
 194         }
 195     }
 196     /* Note we don't free the fromhead here, we just zero it.  That way,
 197        we can use it next time without mallocing int */
 198     memset(fromhead, 0, (sizeof(struct as_frompath *) * WORLD_Y));
 199     stats_index(WORLD_Y * sizeof(*fromhead));
 200 #ifdef AS_STATS
 201     fprintf(stderr, "as_cache %u searches, %u hits, %u entries,"
 202             " index %zu bytes %u blocks, paths %zu bytes %u blocks\n",
 203             as_cache_tries, as_cache_hits,
 204             paths,
 205             index_sz, index_nb,
 206             paths_nb * sizeof(struct as_path), paths_nb);
 207     as_cache_hits = as_cache_tries = 0;
 208 #endif
 209 }
 210
 211 struct as_path *
 212 as_find_cachepath(coord fx, coord fy, coord tx, coord ty)
 213 {
 214     struct as_frompath *from;
 215     struct as_topath *to;
 216
 217     as_cache_try();
 218     /* Is the cache on?  if not, return NULL */
 219     if (as_cachepath_on == 0)
 220         return NULL;
 221
 222     /* Do we have any cached? */
 223     if (fromhead == NULL)
 224         return NULL;
 225
 226     /* Yes! */
 227     for (from = fromhead[fy]; from; from = from->next) {
 228         if (from->x == fx) {
 229             for (to = from->tolist[ty]; to; to = to->next) {
 230                 if (to->x == tx) {
 231                     as_cache_hit();
 232                     return to->path;
 233                 }
 234             }
 235         }
 236     }
 237     return NULL;
 238 }