[Freeciv-Dev] Re: (PR#14343) Data: Egyptian city list

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=14343 >

Here is an optimised version of the patch. This version uses a hash so 
addition and removal of city aliases is efficient.

diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/common/nation.c freeciv.PR14343/common/nation.c
--- vendor.freeciv.current/common/nation.c      2005-11-27 02:35:25.000000000 
+0000
+++ freeciv.PR14343/common/nation.c     2005-11-27 17:59:08.000000000 +0000
@@ -25,6 +25,7 @@
 #include "fcintl.h"
 #include "game.h"
 #include "government.h"
+#include "hash.h"
 #include "log.h"
 #include "mem.h"
 #include "nation.h"
@@ -32,8 +33,20 @@
 #include "support.h"
 #include "tech.h"
 
+
+
 static struct nation_type *nations = NULL;
 
+/*
+ * A hash table mapping a canonical name string to the pointer-to
+ * the struct city_name_aliases for that canonical name.
+ *
+ * We need a hash-table, rather than a simple list, so add_city_name_alias
+ * is efficient. A naive implementation using a list gives O(N^2) performance
+ * because add_city_name_alias is called N times.
+ */
+static struct hash_table *all_city_aliases = NULL;
+
 static int num_nation_groups;
 static struct nation_group nation_groups[MAX_NUM_NATION_GROUPS];
 
@@ -238,12 +251,83 @@
 {
   int i;
 
+  assert(NULL == nations); /* else memory leak */
+  assert(NULL == all_city_aliases); /* else memory leak */
+
   nations = fc_calloc(num, sizeof(nations[0]));
   game.control.nation_count = num;
 
   for (i = 0; i < num; i++) {
     nations[i].index = i;
   }
+
+  all_city_aliases = hash_new(hash_fval_string, hash_fcmp_string);
+}
+
+/**************************************************************************
+ Find the list of aliases known so far for the given canonical name,
+ or NULL if it has no known aliases.
+**************************************************************************/
+static struct city_name_aliases *find_city_name_aliases(const char 
*canonical_name)
+{
+  assert(canonical_name);
+  return hash_lookup_data(all_city_aliases, canonical_name);
+}
+
+/**************************************************************************
+  Add a city-name alias to the list of all aliases.
+  The given name may be the first given alias for the given canonical_name,
+  in which case a new structure will be allocated to record the aliases
+  for that canonical_name.
+**************************************************************************/
+void add_city_name_alias(struct city_name *city_name,
+                         const char *canonical_name)
+{
+  struct city_name_aliases *aliases = find_city_name_aliases(canonical_name);
+
+  assert(all_city_aliases);
+  assert(city_name);
+  assert(canonical_name);
+
+  if (NULL == aliases) {
+    /* This is the first alias for the given canonical name,
+     * so create a struct for recording all aliases for the canonical name. */
+    aliases = fc_malloc(sizeof(struct city_name_aliases));
+    aliases->canonical_name = mystrdup(canonical_name);
+    aliases->names = city_name_list_new();
+
+    /* The hash-table code requires duplication of the key (canonical_name) */
+    hash_insert(all_city_aliases, mystrdup(canonical_name), aliases);
+  }
+
+  /* Add this alias to the list of aliases for the canonical name */
+  city_name_list_prepend(aliases->names, city_name);
+  city_name->aliases = aliases;
+}
+
+/***************************************************************
+ Remove all the cross-references supporting the aliases of a city name
+***************************************************************/
+static void remove_city_name_alias(struct city_name *city_name)
+{
+  assert(all_city_aliases);
+  assert(city_name);
+
+  if (NULL == city_name->aliases) {
+    /* This city name has no aliases */
+    return;
+  }
+
+  city_name_list_unlink(city_name->aliases->names, city_name);
+  if (0 == city_name_list_size(city_name->aliases->names)) {
+    /* That was the last alias for a particular canonical name, so remove
+     * the structure for recording the aliases of that canonical name */
+    hash_delete_entry(all_city_aliases, city_name->aliases->canonical_name);
+    free(city_name->aliases->canonical_name);
+    free(city_name->aliases->names);
+    free(city_name->aliases);
+  }
+  city_name->aliases = NULL;
 }
 
 /***************************************************************
@@ -306,6 +390,8 @@
 
   free(nations);
   nations = NULL;
+  hash_free(all_city_aliases);
+  all_city_aliases = NULL;
   game.control.nation_count = 0;
   num_nation_groups = 0;
 }
@@ -325,7 +411,10 @@
      * simpler elsewhere.
      */
     for (i = 0; city_names[i].name; i++) {
+      remove_city_name_alias(&city_names[i]);
       free(city_names[i].name);
+      /* Do not directly free city_names[i].aliases because it is shared.
+       * remove_city_name_alias should have done that if necessary. */
     }
     free(city_names);
   }
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/common/nation.h freeciv.PR14343/common/nation.h
--- vendor.freeciv.current/common/nation.h      2005-11-27 02:35:25.000000000 
+0000
+++ freeciv.PR14343/common/nation.h     2005-11-27 17:59:08.000000000 +0000
@@ -31,6 +31,30 @@
 
 #define MAX_NUM_NATION_GROUPS 128
 
+struct city_name;
+
+/* get 'struct city_name_list' and related functions: */
+#define SPECLIST_TAG city_name
+#define SPECLIST_TYPE struct city_name
+#include "speclist.h"
+
+#define city_name_list_iterate(citynamelist, pcityname) \
+    TYPED_LIST_ITERATE(struct city_name, citynamelist, pcityname)
+#define city_name_list_iterate_end  LIST_ITERATE_END
+
+/*
+ * Record (references to) city names that are aliases for each other.
+ * The listed names are all aliases for each other: this is one group
+ * of aliases.
+ * The canonical_name is a the single name used to identify this group
+ * of aliases. Typically, the canonical_name will be equivalent to one of
+ * the listed names, although that is not required.
+ */
+struct city_name_aliases {
+  char* canonical_name;
+  struct city_name_list *names;
+};
+
 /*
  * The city_name structure holds information about a default choice for
  * the city name.  The "name" field is, of course, just the name for
@@ -42,14 +66,18 @@
  * may hold a value of 0 (no preference), 1 (city likes the terrain), or -1
  * (city doesn't like the terrain).
  *
+ * If the aliases pointer is NULL, this name does not have aliases.
+ *
  * This is controlled through the nation's ruleset like this:
- *   cities = "Washington (ocean, river, swamp)", "New York (!mountains)"
+ *   cities = "Washington (ocean, river, swamp)",
+ *            "Londinium (!mountains,=London)"
  */
 typedef int ternary;
 struct city_name {
   char* name;
   ternary river;
   ternary terrain[MAX_NUM_TERRAINS];   
+  struct city_name_aliases *aliases;
 };
 
 struct leader {
@@ -125,6 +153,8 @@
 struct nation_type *get_nation_by_idx(Nation_type_id nation);
 bool check_nation_leader_name(const struct nation_type *nation,
                              const char *name);
+void add_city_name_alias(struct city_name *city_name,
+                         const char *canonical_name);
 void nations_alloc(int num);
 void nations_free(void);
 void nation_city_names_free(struct city_name *city_names);
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/aborigines.ruleset 
freeciv.PR14343/data/nation/aborigines.ruleset
--- vendor.freeciv.current/data/nation/aborigines.ruleset       2005-11-27 
02:35:13.000000000 +0000
+++ freeciv.PR14343/data/nation/aborigines.ruleset      2005-11-27 
17:58:47.000000000 +0000
@@ -28,7 +28,7 @@
 ; City names are mostly from the state of New South Wales
 ; plus the places of birth for a few of the leaders.
 cities =
- "Kamberra", ; Aboriginal name that became Canberra in English
+ "Kamberra (=Canberra)", ; The original, Aboriginal, name.
  "Beeliar",
  "Raukkan",
  "Ukerabagh",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/byzantium.ruleset 
freeciv.PR14343/data/nation/byzantium.ruleset
--- vendor.freeciv.current/data/nation/byzantium.ruleset        2005-11-27 
02:35:12.000000000 +0000
+++ freeciv.PR14343/data/nation/byzantium.ruleset       2005-11-27 
17:58:47.000000000 +0000
@@ -37,7 +37,7 @@
 civilwar_nations = "greek", "italian", "turk", "arab"
 
 cities =
- "Constantinople (ocean)",
+ "Constantinople (ocean,=Istanbul)",
  "Ephesus",
  "Iconium",
  "Roma",
@@ -45,7 +45,7 @@
  "Dyrrachium (ocean)",
  "Antioch",
  "Nicaea",
- "Thessalonica (ocean)",
+ "Thessalonica (ocean,=Thessaloniki)",
  "Rhodes (ocean)",
  "Tarsus",
  "Caesaria",
@@ -68,7 +68,7 @@
  "Germaniceia",
  "Sevastoupolis",
  "Prusa",
- "Athinae",
+ "Athinae (=Athina)",
  "Ioannina",
  "Pella", 
  "Doryleo",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/greek.ruleset 
freeciv.PR14343/data/nation/greek.ruleset
--- vendor.freeciv.current/data/nation/greek.ruleset    2005-11-27 
02:35:12.000000000 +0000
+++ freeciv.PR14343/data/nation/greek.ruleset   2005-11-27 17:58:47.000000000 
+0000
@@ -32,7 +32,7 @@
  "Sparti",
  "Thivai",
  "Korinthos",
- "Konstandinoupolis",
+ "Konstandinoupolis (=Istanbul)",
  "Militos",
  "Efesos",
  "Peiraiefs (ocean)",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/maori.ruleset 
freeciv.PR14343/data/nation/maori.ruleset
--- vendor.freeciv.current/data/nation/maori.ruleset    2005-11-27 
02:35:13.000000000 +0000
+++ freeciv.PR14343/data/nation/maori.ruleset   2005-11-27 17:58:47.000000000 
+0000
@@ -33,7 +33,7 @@
 ; Note that putting "(ocean)" as a qualifier for every city probably will not
 ; give very useful results.
 cities =
- "Poneke (ocean)",     ; Maori name for Wellington
+ "Poneke (ocean,=Wellington)",
  "Akarana",
  "Otautahi (ocean)",
  "Otepoti (ocean)",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/phoenician.ruleset 
freeciv.PR14343/data/nation/phoenician.ruleset
--- vendor.freeciv.current/data/nation/phoenician.ruleset       2005-11-27 
02:35:12.000000000 +0000
+++ freeciv.PR14343/data/nation/phoenician.ruleset      2005-11-27 
17:58:47.000000000 +0000
@@ -67,7 +67,7 @@
  "Solus",
  "Motye",
  "Gaulos",
- "Melita",
+ "Melita (=Malta)",
  "Sulci",
  "Karteia",
  "Panormos",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/roman.ruleset 
freeciv.PR14343/data/nation/roman.ruleset
--- vendor.freeciv.current/data/nation/roman.ruleset    2005-11-27 
02:35:13.000000000 +0000
+++ freeciv.PR14343/data/nation/roman.ruleset   2005-11-27 17:58:47.000000000 
+0000
@@ -40,10 +40,16 @@
   "Aquileia", "Florentia", "Bononia", "Verona", "Ostia", "Agrigentum",
   "Syracusae", "Neapolis", "Pompeii", "Salernum", "Tarraco",
   "Carthago", "Barcino", "Bracara", "Carthago Nova", "Baiae",
-  "Noviomagus", "Vindobona", "Atuatuca", "Caesarea", "Ierusalem",
+  "Noviomagus", "Vindobona", "Atuatuca", "Caesarea",
+  "Ierusalem (=Jerusalem)",
   "Trapezus", "Durocortorum", "Lutetia", "Burdigala", "Portus Namnetum",
-  "Utica", "Lugdunum", "Londinium", "Aquae Sulis", "Camulodunum", "Dubris",
-  "Eburacum", "Coriovallum", "Perusia", "Leptis Magna", "Corduba", "Edessa",
+  "Utica", "Lugdunum",
+  "Londinium (=London)",
+  "Aquae Sulis (=Bath)",
+  "Camulodunum (=Colchester)",
+  "Dubris",
+  "Eburacum (=York)",
+  "Coriovallum", "Perusia", "Leptis Magna", "Corduba", "Edessa",
   "Ariminum", "Narbo Martius", "Pergamum", "Vienna", "Hispalis",
   "Salonae", "Cyrenae", "Dyrrachium", "Luni", "Noreia", "Ephesus",
   "Panoramus", "Ancyra", "Caralis", "Patavium", "Petra", "Tolosa",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/data/nation/viking.ruleset 
freeciv.PR14343/data/nation/viking.ruleset
--- vendor.freeciv.current/data/nation/viking.ruleset   2005-11-27 
02:35:13.000000000 +0000
+++ freeciv.PR14343/data/nation/viking.ruleset  2005-11-27 17:58:47.000000000 
+0000
@@ -43,7 +43,7 @@
  "finnish", "russian", "scottish", "ukrainian"
 
 cities =
- "Skiringssal",                ; Viking era name for Kaupang, Norway
+ "Skiringssal (=Kaupang)",     ; Modern Norway
  "Birka",
  "Ribe",
  "Hedeby",
@@ -51,7 +51,7 @@
  "Reykjavik (ocean)",
  "Torshavn (ocean)",
  "Bjørgvin",
- "Jorvik (ocean)",
+ "Jorvik (ocean,=York)",
  "Fjaler",
  "Vikarskeid",
  "Hvitaby",
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/doc/README.nations freeciv.PR14343/doc/README.nations
--- vendor.freeciv.current/doc/README.nations   2005-11-27 02:35:05.000000000 
+0000
+++ freeciv.PR14343/doc/README.nations  2005-11-27 17:58:36.000000000 +0000
@@ -349,6 +349,33 @@
 to give bad results. This is a limitation of the system, and should be
 taken into account when labelling cities.)
 
+Freeciv supports aliases for city names. This is useful for rule-sets that have
+ancient nations and their successor nations, for successor nations that changed
+the city names. You indicate names are aliases by selecting one of the names as
+the 'canonical name' for the city, then annotating the aliases to indicate
+their associated canonical name. The annotation is simply a label consisting of
+an equals sign (=) followed by the canonical name.
+
+For example, the modern English city of York has previously been known as
+Jorvik (to the Vikings) and Eburacum (to the Romans). Therefore a Roman
+rule-set could include an entry like this:
+  "Eburacum (=York)"
+a Viking rule-set could include an entry like this:
+  "Jorvik (=York)"
+and an English rule-set could include an entry like this:
+  "York"
+or, equivalently but redundantly, like this:
+  "York (=York)"
+
+Freeciv tries to avoid selecting as a "default" name a name that is an alias of
+an already existing city name. Freeciv treats all the aliases, including the
+canonical name itself, equally in this respect.
+
+The canonical name usually itself appears in the city list of some nation (as
+for "York" in the example above), however, that is not required. You should
+usually select as the canonical name the modern name as used by the modern
+sovereign nation in which it is located.
+
 At this point, it is useful to put one city per line, only.
 
 Finally, don't forget to leave a blank line feed in the end of your nation
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/server/citytools.c freeciv.PR14343/server/citytools.c
--- vendor.freeciv.current/server/citytools.c   2005-11-27 02:35:07.000000000 
+0000
+++ freeciv.PR14343/server/citytools.c  2005-11-27 17:58:39.000000000 +0000
@@ -114,6 +114,28 @@
 }
 
 /****************************************************************
+  Whether an existing city has a name that is an alias
+  for a given (candidate) name.
+*****************************************************************/
+static bool is_city_alias_used(const struct city_name *city_name)
+{
+  assert(city_name);
+
+  if (city_name->aliases) {
+    /* Must examine the list of aliases.
+     * Each name typically has only a few aliases,
+     * so check the entire list is not too expensive. */
+    city_name_list_iterate(city_name->aliases->names, alias) {
+      if (game_find_city_by_name(alias->name)) {
+        return TRUE;
+      }
+    } city_name_list_iterate_end;
+  }
+
+  return FALSE;
+}
+
+/****************************************************************
 Returns the priority of the city name at the given position,
 using its own internal algorithm.  Lower priority values are
 more desired, and all priorities are non-negative.
@@ -195,6 +217,11 @@
     }
   } terrain_type_iterate_end;
 
+  /* Avoid choosing names that are merely aliases for existing cities */
+  if (is_city_alias_used(city_name)) {
+    priority *= mult_factor * mult_factor * mult_factor;
+  }
+
   return (int)priority;        
 }
 
diff -Xvendor.freeciv.current/diff_ignore -ruN 
vendor.freeciv.current/server/ruleset.c freeciv.PR14343/server/ruleset.c
--- vendor.freeciv.current/server/ruleset.c     2005-11-27 02:35:07.000000000 
+0000
+++ freeciv.PR14343/server/ruleset.c    2005-11-27 17:58:39.000000000 +0000
@@ -1910,6 +1910,7 @@
   This function loads a city name list from a section file.  The file and
   two section names (which will be concatenated) are passed in.  The
   malloc'ed city name list (which is all filled out) will be returned.
+  Also, update the lists of city aliases.
 **************************************************************************/
 static struct city_name* load_city_name_list(struct section_file *file,
                                             const char *secfile_str1,
@@ -1930,6 +1931,7 @@
    */
   city_names = fc_calloc(dim + 1, sizeof(*city_names));
   city_names[dim].name = NULL;
+  city_names[dim].aliases = NULL;
 
   /*
    * Each string will be of the form
@@ -1941,6 +1943,7 @@
    * city_name structure.
    */
   for (j = 0, value = 1; j < dim; j++, value++) {
+    char *canonical_name = NULL;
     char *name = strchr(cities[j], '(');
 
     /*
@@ -1966,12 +1969,13 @@
                "ruleset \"%s%s\": unmatched parenthesis.",
                cities[j], secfile_str1, secfile_str2);
        assert(FALSE);
-      } else { /* if (!next) */
+      } else { /* if (next) */
         name[0] = next[0] = '\0';
         name++;
 
         /* Handle the labels one at a time. */
         do {
+         bool alias = FALSE;
          int setting;
 
          next = strchr(name, ',');
@@ -1981,17 +1985,29 @@
          remove_leading_trailing_spaces(name);
        
          /*
+           * The = is used to mark the canonical name.
           * The ! is used to mark a negative, which is recorded
           * with a -1.  Otherwise we use a 1.
           */
-         if (name[0] == '!') {
+         if (name[0] == '=') {
+           name++;
+            alias = TRUE;
+         } else if (name[0] == '!') {
            name++;
            setting = -1;
          } else {
            setting = 1;
          }
        
-         if (mystrcasecmp(name, "river") == 0) {
+          if (alias && canonical_name) {
+            freelog(LOG_ERROR, "More than one canonical name for city %s "
+                               "in city name ruleset \"%s%s\" - skipping it.",
+                               cities[j], secfile_str1, secfile_str2);
+            assert(FALSE);
+          } else if (alias) {
+            canonical_name = name;
+            /* No need to strdup the name; it will remain available. */
+         } else if (mystrcasecmp(name, "river") == 0) {
            city_names[j].river = setting;
          } else {
            /* "handled" tracks whether we find a match (for error handling) */
@@ -2033,6 +2049,18 @@
       assert(FALSE);
       city_names[j].name[MAX_LEN_NAME - 1] = '\0';
     }
+
+    if (canonical_name) {
+      add_city_name_alias(&city_names[j], canonical_name);
+    } else {
+      /* Take the given name as the canonical name.
+       * This makes it easier to incrementally add canonical names to
+       * rulesets: only names that are non-canonical need to be
+       * annotated with a canonical name.
+       * Thus "York" is equivalent to "York (=York)"
+       */
+      add_city_name_alias(&city_names[j], city_names[j].name);
+    }
   }
   if (cities) {
     free(cities);