static int as_cachepath_on = 0; /* Default to off */
+#ifdef AS_STATS
+unsigned as_cache_tries, as_cache_hits;
+#define as_cache_try() ((void)as_cache_tries++)
+#define as_cache_hit() ((void)as_cache_hits++)
+#else
+#define as_cache_try() ((void)0)
+#define as_cache_hit() ((void)0)
+#endif
+
void
as_enable_cachepath(void)
{
struct as_frompath *from, *from2;
struct as_topath *to, *to2;
int i, j;
+#ifdef AS_STATS
+ size_t index_sz = 0;
+ unsigned index_nb = 0, paths_nb = 0, paths = 0;
+#define stats_index(sz) ((void)(index_sz += (sz), index_nb++))
+#else
+#define stats_index(sz) ((void)0)
+#endif
/* Cache not used yet :) */
if (fromhead == NULL)
for (to = from->tolist[i]; to; to = to2) {
to2 = to->next;
/* Free this path */
+#ifdef AS_STATS
+ {
+ struct as_path *pp;
+ for (pp = to->path; pp; pp = pp->next)
+ paths_nb++;
+ paths++;
+ }
+#endif
as_free_path(to->path);
/* Free this node */
free(to);
+ stats_index(sizeof(*to));
}
}
/* Now, free the list of lists */
free(from->tolist);
+ stats_index(WORLD_Y * sizeof(*from->tolist));
/* Save the next pointer */
from2 = from->next;
/* now, free this from node */
free(from);
+ stats_index(sizeof(*from));
}
}
/* Note we don't free the fromhead here, we just zero it. That way,
we can use it next time without mallocing int */
memset(fromhead, 0, (sizeof(struct as_frompath *) * WORLD_Y));
+ stats_index(WORLD_Y * sizeof(*fromhead));
+#ifdef AS_STATS
+ fprintf(stderr, "as_cache %u searches, %u hits, %u entries,"
+ " index %zu bytes %u blocks, paths %zu bytes %u blocks\n",
+ as_cache_tries, as_cache_hits,
+ paths,
+ index_sz, index_nb,
+ paths_nb * sizeof(struct as_path), paths_nb);
+ as_cache_hits = as_cache_tries = 0;
+#endif
}
struct as_path *
struct as_frompath *from;
struct as_topath *to;
+ as_cache_try();
/* Is the cache on? if not, return NULL */
if (as_cachepath_on == 0)
return NULL;
for (from = fromhead[fy]; from; from = from->next) {
if (from->x == fx) {
for (to = from->tolist[ty]; to; to = to->next) {
- if (to->x == tx)
+ if (to->x == tx) {
+ as_cache_hit();
return to->path;
+ }
}
}
}
int i;
int j;
int total_q;
+ int total_p;
int total_h;
+ size_t other;
struct as_queue *qp;
+ struct as_path *pp;
struct as_hash *hp;
fprintf(fp, "Statistics:\n");
i++;
fprintf(fp, "\tsubsumed:\t%d\n", i);
total_q += i;
+ for (i = 0, pp = adp->path; pp; pp = pp->next)
+ i++;
+ total_p = i;
+ fprintf(fp, "path length: %d\n", total_p);
fprintf(fp, "hash table statistics (size %d):\n", adp->hashsize);
for (i = 0; i < adp->hashsize; i++) {
for (j = 0, hp = adp->hashtab[i]; hp; hp = hp->next)
fprintf(fp, "\tqueues\t%d\n",
(int)(total_q * sizeof(struct as_queue)));
fprintf(fp, "\tnodes\t%d\n", (int)(total_q * sizeof(struct as_node)));
+ fprintf(fp, "\tpath\t%d\n", (int)(total_p * sizeof(struct as_path)));
fprintf(fp, "\thash ents\t%d\n",
(int)(total_h * sizeof(struct as_hash)));
+ other = sizeof(struct as_data);
+ other += adp->maxneighbors * sizeof(struct as_coord);
+ other += (adp->maxneighbors + 1) * sizeof(struct as_node *);
+ other += adp->hashsize * sizeof(struct as_hash *);
+ fprintf(fp, "\tother\t%d\n", (int)other);
fprintf(fp, "\ttotal\t%d\n",
(int)(total_q * sizeof(struct as_queue) +
total_q * sizeof(struct as_node) +
- total_h * sizeof(struct as_hash)));
+ total_p * sizeof(struct as_path) +
+ total_h * sizeof(struct as_hash) +
+ other));
}
* ---
*
* path.c: Empire/A* Interface code.
- * Define AS_STATS for A* statistics.
*
* Known contributors to this file:
* Phil Lapsley, 1991
* Steve McClure, 1997
*/
+/*
+ * Define AS_STATS for A* statistics on stderr.
+ *
+ * Define AS_NO_PATH_CACHE to disable the path cache. The path cache
+ * saves a lot of work, but uses lots of memory. It should be a
+ * significant net win, unless you run out of memory.
+ *
+ * Define AS_NO_NEIGHBOR_CACHE to disable the neighbor cache. The
+ * neighbor cache trades a modest amount of memory to save a bit of
+ * work. In its current form, it doesn't really make a difference.
+ */
+
#include <config.h>
#include <stdio.h>
#define BP_NEIGHBORS 6 /* max number of neighbors */
struct bestp {
- int sctcache_hits;
- int sctcache_misses;
int bp_mobtype;
struct as_data *adp;
};
if (bp->adp == NULL)
return NULL;
+#ifndef AS_NO_NEIGHBOR_CACHE
if (neighsects == NULL)
neighsects = calloc(WORLD_SZ() * 6, sizeof(struct sctstr *));
+#endif
return bp;
}
static struct bestp *mybestpath;
struct as_data *adp;
struct as_path *ap;
+ int res;
if (!mybestpath)
mybestpath = bp_init();
adp = mybestpath->adp;
+#ifdef AS_NO_PATH_CACHE
+ ap = NULL;
+#else
ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y);
+#endif
if (ap == NULL) {
adp->from.x = from->sct_x;
adp->from.y = from->sct_y;
adp->to.y = to->sct_y;
mybestpath->bp_mobtype = mob_type;
- if (as_search(adp) < 0)
+ res = as_search(adp);
+#ifdef AS_STATS
+ as_stats(adp, stderr);
+#ifndef AS_NO_NEIGHBOR_CACHE
+ fprintf(stderr, "neighbor cache %zu bytes\n",
+ WORLD_SZ() * 6 * sizeof(struct sctstr *));
+#endif
+#endif
+ if (res < 0)
return -1;
ap = adp->path;
}
if (bp_path(ap, path) < 0)
return -1;
-
-#ifdef AS_STATS
- as_stats(adp, stderr);
-#endif /* AS_STATS */
-#ifdef BP_STATS
- fprintf(stderr, "best path %s\n", path);
- fprintf(stderr, "cache hits/misses: %d/%d\n",
- bp->sctcache_hits, bp->sctcache_misses);
-#endif /* BP_STATS */
return 0;
}
*ssp = sp;
} else {
sp = *ssp;
- sx = XNORM(sp->sct_x);
- sy = YNORM(sp->sct_y);
+ sx = sp->sct_x;
+ sy = sp->sct_y;
}
/* No need to calculate cost each time, just make sure we can
move through it. We calculate it later. */
void
bp_enable_cachepath(void)
{
+#ifndef AS_NO_PATH_CACHE
as_enable_cachepath();
+#endif
}
void
bp_disable_cachepath(void)
{
+#ifndef AS_NO_PATH_CACHE
as_disable_cachepath();
+#endif
}
void
bp_clear_cachepath(void)
{
+#ifndef AS_NO_PATH_CACHE
as_clear_cachepath();
+#endif
}
double
projects / empserver / commitdiff