[Freeciv-Dev] (PR#4636) make gotohand's local_vector denser

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

find_the_shortest_path in server/gotohand.c has a static variable 
local_vector, a 2d array with dimensions MAP_MAX_WIDHT * MAP_MAX_HEIGHT.

This is inefficient not only because of the wasted memory, but because 
the inferior cache usage slows things down.

The correct thing to do - and what is done everywhere else - is to make 
this value a 1d array indexed by index positions.

jason

Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.171
diff -u -r1.171 gotohand.c
--- server/gotohand.c   2003/07/17 18:56:51     1.171
+++ server/gotohand.c   2003/07/21 14:56:41
@@ -569,7 +569,8 @@
   int maxcost = MAXCOST;
   int move_cost, total_cost;
   int straight_dir = 0;        /* init to silence compiler warning */
-  static unsigned char local_vector[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];
+  static unsigned char *local_vector = NULL;
+#define LOCAL_VECTOR(x, y) local_vector[map_pos_to_index((x), (y))]
   struct unit *pcargo;
   /* 
    * Land/air units use warmap.cost while sea units use
@@ -583,9 +584,12 @@
   if (same_pos(dest_x, dest_y, orig_x, orig_y)) {
     return TRUE;               /* [Kero] */
   }
-  
-  local_vector[orig_x][orig_y] = 0;
 
+  if (!local_vector) {
+    local_vector = fc_malloc(map.xsize * map.ysize * sizeof(*local_vector));
+  }
+  LOCAL_VECTOR(orig_x, orig_y) = 0;
+
   init_warmap(punit->x, punit->y, move_type);
   warmap_cost = (move_type == SEA_MOVING) ? warmap.seacost : warmap.cost;
   add_to_mapqueue(0, orig_x, orig_y);
@@ -686,7 +690,7 @@
              move_cost = SINGLE_MOVE;
            }
          }
-       } else if (!goto_zoc_ok(punit, x, y, x1, y1, local_vector[x][y])) {
+       } else if (!goto_zoc_ok(punit, x, y, x1, y1, LOCAL_VECTOR(x, y))) {
          continue;
        }
 
@@ -780,12 +784,12 @@
        if (warmap_cost[map_pos_to_index(x1, y1)] > total_cost) {
          warmap_cost[map_pos_to_index(x1, y1)] = total_cost;
          add_to_mapqueue(total_cost, x1, y1);
-         local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
+         LOCAL_VECTOR(x1, y1) = 1 << DIR_REVERSE(dir);
          freelog(LOG_DEBUG,
                  "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
                  dir_get_name(dir), x, y, x1, y1, total_cost);
        } else if (warmap_cost[map_pos_to_index(x1, y1)] == total_cost) {
-         local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
+         LOCAL_VECTOR(x1, y1) |= 1 << DIR_REVERSE(dir);
          freelog(LOG_DEBUG,
                  "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
                  dir_get_name(dir), x, y, x1, y1, total_cost);
@@ -823,7 +827,7 @@
       if ((restriction == GOTO_MOVE_CARDINAL_ONLY)
          && !DIR_IS_CARDINAL(dir)) continue;
 
-      if (TEST_BIT(local_vector[x][y], dir)) {
+      if (TEST_BIT(LOCAL_VECTOR(x, y), dir)) {
        move_cost = (move_type == SEA_MOVING)
                ? WARMAP_SEACOST(x1, y1)
                : WARMAP_COST(x1, y1);
@@ -831,7 +835,7 @@
         add_to_mapqueue(MAXCOST-1 - move_cost, x1, y1);
        /* Mark it on the warmap */
        WARMAP_VECTOR(x1, y1) |= 1 << DIR_REVERSE(dir); 
-        local_vector[x][y] -= 1<<dir; /* avoid repetition */
+       LOCAL_VECTOR(x, y) -= 1<<dir; /* avoid repetition */
        freelog(LOG_DEBUG, "PATH-SEGMENT: %s from (%d, %d) to (%d, %d)",
                dir_get_name(DIR_REVERSE(dir)), x1, y1, x, y);
       }