--- freeciv/server/airgoto.c	Thu Oct 17 15:43:26 2002
+++ flyciv/server/airgoto.c	Thu Oct 17 17:39:27 2002
@@ -21,7 +21,8 @@
 
 /* These are used for airplane GOTOs with waypoints */
 #define MAXFUEL 100
-#define MAX_FLIGHT 32
+/* Only used in the priority function for the queue */
+#define MAX_FLIGHT 256
 
 /* Type of refuel point */
 enum refuel_type {
@@ -42,11 +43,15 @@
   struct refuel *coming_from;
 };
 
+#define ALLOC_STEP 20
 static struct player_refuel_list {
-  struct refuel *points[MAP_MAX_WIDTH*MAP_MAX_HEIGHT]; /* enough :P */
-  struct player *pplayer;
+  struct refuel *points;
+  /* Size of the actual list */
   unsigned int list_size;
+  /* Size of the allocated memory in points */
+  unsigned int alloc_size;
   /* It is convenient to hold additional info here */
+  struct player *pplayer;
   struct unit *punit;
   int max_moves;
   int moves_per_turn;
@@ -56,9 +61,9 @@
 static void make_list_of_refuel_points(struct player *pplayer, 
                                        bool cities_only, 
                                        int moves_per_turn, int max_moves);
-static void dealloc_refuel_stack(void);
 
-#define PQDATUM void *
+#define PQDATUM int
+#define PQEMPTY -1
 /*
  *  Priority queue structure
  */
@@ -129,10 +134,10 @@
     PQDATUM *tmp_d;
     int *tmp_p;
     newsize = q->size + q->step;
-    if (!(tmp_d = realloc(q->cells, sizeof(PQDATUM) * newsize))) {
+    if (!(tmp_d = fc_realloc(q->cells, sizeof(PQDATUM) * newsize))) {
       return FALSE;
     }
-    if (!(tmp_p = realloc(q->priorities, sizeof(int) * newsize))) {
+    if (!(tmp_p = fc_realloc(q->priorities, sizeof(int) * newsize))) {
       return FALSE;
     }
     q->cells = tmp_d;
@@ -171,7 +176,7 @@
   int i = 1, j;
 
   if (!q || q->size == 1)
-    return NULL;
+    return PQEMPTY;
   top = q->cells[1];
   q->size--;
   tmp = q->cells[q->size];
@@ -207,7 +212,7 @@
 static PQDATUM pqpeek(struct pqueue * q)
 {
   if (!q || q->size == 1)
-    return NULL;
+    return PQEMPTY;
 
   return q->cells[1];
 }
@@ -242,61 +247,85 @@
 
 
 /*---------------- Refuel Points C/D and access --------------------------*/
-
-/******************************************************************
- * Creator/initializer for struct refuel
- *****************************************************************/
-static struct refuel *create_refuel_point(int x, int y,
-                                          enum refuel_type type,
-                                          int turns, int moves_left)
-{
-  struct refuel *pRefuel = fc_malloc(sizeof(struct refuel));
-  pRefuel->x = x;
-  pRefuel->y = y;
-  pRefuel->type = type;
-  pRefuel->listed = RLS_NOT_YET;
-  pRefuel->turns = turns;
-  pRefuel->moves_left = moves_left;
-  pRefuel->coming_from = NULL;
-  return pRefuel;
-}
-
-/******************************************************************
- * Destructor for struct refuel
- *****************************************************************/
-inline static void destroy_refuel_point(struct refuel *pRefuel)
-{
-  free(pRefuel);
-}
-
 /******************************************************************
  * Access function for struct refuel
  *****************************************************************/
-inline unsigned int get_refuel_x(struct refuel *pRefuel)
+unsigned int get_refuel_x(struct refuel *point)
 {
-  return pRefuel->x;
+  return point->x;
 }
 
 /******************************************************************
  * Access function for struct refuel
  *****************************************************************/
-inline unsigned int get_refuel_y(struct refuel *pRefuel)
+unsigned int get_refuel_y(struct refuel *point)
 {
-  return pRefuel->y;
+  return point->y;
 }
 
 /******************************************************************
  * Access function for struct refuel
  *****************************************************************/
-inline unsigned int get_turns_to_refuel(struct refuel *pRefuel)
+unsigned int get_turns_to_refuel(struct refuel *point)
 {
-  return pRefuel->turns;
+  return point->turns;
 }
 
 /*------------------- End of Refuel Point C/D and Access ---------------*/
 
 
 /*------------------- Refuel Point List Handling -----------------------*/
+/******************************************************************
+ * Add new refuel point to the (static) refuel point list.
+ * If the last argument start is TRUE, the point will be written at
+ * the head of the list.
+ *****************************************************************/
+static void add_refuel_point(int x, int y, 
+                             enum refuel_type type, int turns, 
+                             int moves_left, bool start)
+{
+  int pos;
+
+  if (start) {
+    pos = 0;
+  } else {
+    pos = refuels.list_size;
+    refuels.list_size++;
+  }
+
+  if (pos +1 > refuels.alloc_size) {
+    refuels.alloc_size += ALLOC_STEP;
+    /* If refuels.alloc_size was zero (on the first call), 
+     * then refuels.points is NULL and realloc will actually malloc */
+    refuels.points = fc_realloc(refuels.points, 
+                                refuels.alloc_size * sizeof(struct refuel));
+    /* This memory, because refuels is static, is never freed.
+     * It is just reused. */  
+  }
+  
+  /* Fill the new point in */
+  refuels.points[pos].x = x;
+  refuels.points[pos].y = y;
+  refuels.points[pos].type = type;
+  refuels.points[pos].listed = RLS_NOT_YET;
+  refuels.points[pos].turns = turns;
+  refuels.points[pos].moves_left = moves_left;
+  refuels.points[pos].coming_from = NULL;
+
+  return;
+}
+
+/******************************************************************
+ * Wrapper to refuel point access.  Checks range too.
+ ******************************************************************/
+static struct refuel *get_refuel_by_index(int i)
+{
+  if (i < 0 || i >= refuels.list_size) {
+    return NULL;
+  }
+
+  return &refuels.points[i];
+}
 
 /*************************************************************************
 This list should probably be made by having a list of airbase and then
@@ -317,46 +346,23 @@
   refuels.pplayer = pplayer;
   refuels.moves_per_turn = moves_per_turn;
   refuels.max_moves = max_moves;
-  
+
   whole_map_iterate(x, y) {
     ptile = map_get_tile(x, y);
     if ((pcity = is_allied_city_tile(ptile, pplayer)) != NULL
 	&& !is_non_allied_unit_tile(ptile, pplayer) ) {
-
-      struct refuel *prefuel 
-        = create_refuel_point(x, y, FUEL_CITY, 
-                              MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0);
-
-      refuels.points[refuels.list_size] = prefuel;
-      refuels.list_size++;
+      add_refuel_point(x, y, FUEL_CITY, 
+                       MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
     } else if (tile_has_special(ptile, S_AIRBASE)
                && !is_non_allied_unit_tile(ptile, pplayer)
                && !cities_only) {
-
-      struct refuel *prefuel
-        = create_refuel_point(x, y, FUEL_AIRBASE, 
-                              MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0);
-
-      refuels.points[refuels.list_size] = prefuel;
-      refuels.list_size++;
+      add_refuel_point(x, y, FUEL_AIRBASE, 
+                       MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
     }
   } whole_map_iterate_end;
 }
 
 /*************************************************************************
- * Clean up all the refuel points, including START and GOAL 
- * (0th and last in the list correspondingly)
- ************************************************************************/
-static void dealloc_refuel_stack(void)
-{
-  int i; 
-  for (i = 0; i < refuels.list_size; i++) {
-    destroy_refuel_point(refuels.points[i]);
-    refuels.points[i] = NULL;
-  }
-}
-
-/*************************************************************************
  * Priority function for refuel points --- on the basis of their 
  * turn-distance from the starting point
  ************************************************************************/
@@ -387,8 +393,6 @@
                                    int moves_per_turn, int max_fuel)
 {
   struct refuel *tmp;   
-  struct refuel *start_point 
-    = create_refuel_point(x, y, FUEL_START, 0, moves_left);
   struct pqueue *rp_queue = pqcreate(MAP_MAX_WIDTH);
 
   /* List of all refuel points of the player!  
@@ -396,20 +400,18 @@
   make_list_of_refuel_points(pplayer, cities_only, 
                              moves_per_turn, moves_per_turn * max_fuel);
   /* Add the starting point: we keep it for later backtracking */
-  refuels.points[0] = start_point;
+  add_refuel_point(x, y, FUEL_START, 0, moves_left, TRUE);
+
   if (!same_pos(x, y, dest_x, dest_y)) {
-    struct refuel *end_point 
-      = create_refuel_point(dest_x, dest_y, FUEL_GOAL, 
-                            MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0);
-    /* We are given a destination */
-    refuels.points[refuels.list_size] = end_point;
-    refuels.list_size ++;
+    add_refuel_point(dest_x, dest_y, FUEL_GOAL, 
+                     MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
   }
 
-  /* Process the starting point, no need to queue it */
-  refuel_iterate_process(rp_queue, start_point);
+  /* Process the starting point, no need to queue it
+   * Note: starting position is in the head of refuels list */
+  refuel_iterate_process(rp_queue, get_refuel_by_index(0));
 
-  tmp = (struct refuel *) pqpeek(rp_queue);
+  tmp = get_refuel_by_index(pqpeek(rp_queue));
 
   if (tmp && same_pos(x, y, tmp->x, tmp->y)) {
     /* We should get the starting point twice 
@@ -433,7 +435,7 @@
    * (ignoring already processed ones) */
   do {
     next_point 
-      = (struct refuel*) pqremove(rp_list);
+      = get_refuel_by_index(pqremove(rp_list));
   } while(next_point != NULL && next_point->listed == RLS_ALREADY_NOT);
 
 
@@ -458,7 +460,7 @@
 
   /* Iteration starts from 1, since 0 is occupied by the start point */
   for (k = 1; k < refuels.list_size; k++) {
-    struct refuel *pto = refuels.points[k];
+    struct refuel *pto = get_refuel_by_index(k);
     int moves_left 
       = air_can_move_between(max_moves, 
                              pfrom->x, pfrom->y, pto->x, pto->y, 
@@ -493,7 +495,7 @@
         pto->turns = total_turns;
         
         /* Insert it into the queue.  No problem if it's already there */
-        pqinsert(rp_list, pto, queue_priority_function(pto));
+        pqinsert(rp_list, k, queue_priority_function(pto));
         pto->listed = RLS_YES;
         
         freelog(LOG_DEBUG, "Recorded (%i,%i) from (%i,%i) in (%d %d)", 
@@ -509,9 +511,11 @@
  ************************************************************************/
 static void refuel_iterate_end(struct pqueue *rp_list)
 {
-  pqdestroy(rp_list);
+  /* No need to free memory allocated for the refuels list 
+   * -- it will be reused */
 
-  dealloc_refuel_stack();
+  /* Just destroy the queue */
+  pqdestroy(rp_list);
 }
 
 /*----------------- End of Refuel Point List Iterators -------------------*/
@@ -542,11 +546,12 @@
 { 
   unsigned int fullmoves = unit_type(punit)->move_rate / SINGLE_MOVE;
   unsigned int fullfuel = unit_type(punit)->fuel;
+  unsigned int moves_and_fuel_left 
+    = punit->moves_left / SINGLE_MOVE + fullmoves * (punit->fuel - 1);
   struct pqueue *my_list 
     = refuel_iterate_init(unit_owner(punit), punit->x, punit->y, 
                           *dest_x, *dest_y, FALSE, 
-                          punit->moves_left / SINGLE_MOVE, fullmoves, 
-                          fullfuel);
+                          moves_and_fuel_left, fullmoves, fullfuel);
   struct refuel *next_point;
   bool reached_goal = FALSE;