[Freeciv-Dev] (PR#11779) [PATCH] New genlist code: registry section hashtable

["Vasco Alexandre da Silva Costa" <vasc@xxxxxxxxxxxxxx>]

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

> [per - Sat Jan 22 19:59:31 2005]:
> 
> Now that the API change has been done, the new genlist code itself is a
> rather small patch. Here it is.
> 
> But before I commit this, I want to make section lookups in registry.c
> into a hashtable lookup instead of a genlist search.

And here is a patch which does just that.

Index: utility/registry.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/registry.c,v
retrieving revision 1.69
diff -u -u -r1.69 registry.c
--- utility/registry.c  22 Jan 2005 19:45:45 -0000      1.69
+++ utility/registry.c  7 May 2005 15:49:32 -0000
@@ -236,6 +236,14 @@
 section_file_insert_internal(struct section_file *my_section_file, 
                             char *fullpath);
 
+/* Only need use these explicitly on section_files constructed,
+   not for ones generated by section_file_load:
+*/
+static bool secfilehash_hashash(struct section_file *file);
+static void secfilehash_build(struct section_file *file,
+                             bool allow_duplicates);
+static void secfilehash_free(struct section_file *file);
+
 /**************************************************************************
   Return the filename the sectionfile was loaded as, or "(anonymous)"
   if this sectionfile was created rather than loaded from file.
@@ -258,6 +266,7 @@
 {
   file->filename = NULL;
   file->sections = section_list_new();
+  file->hash_sections = hash_new(hash_fval_string, hash_fcmp_string);
   file->num_entries = 0;
   file->hashd = NULL;
   file->sb = sbuf_new();
@@ -279,6 +288,10 @@
   section_list_free(file->sections);
   file->sections = NULL;
 
+  /* free the sections hash data: */
+  hash_free(file->hash_sections);
+  file->hash_sections = NULL;
+
   /* free the hash data: */
   if(secfilehash_hashash(file)) {
     secfilehash_free(file);
@@ -295,6 +308,26 @@
 }
 
 /**************************************************************************
+...
+**************************************************************************/
+static struct section*
+section_file_append_section(struct section_file *sf, const char *sec_name)
+{
+  struct section *psection;
+
+  psection = sbuf_malloc(sf->sb, sizeof(*psection));
+  psection->name = sbuf_strdup(sf->sb, sec_name);
+  psection->entries = entry_list_new();
+  section_list_append(sf->sections, psection);
+
+  if (!hash_insert(sf->hash_sections, psection->name, psection)) {
+    freelog(LOG_ERROR, "Section \"%s\" name collision", sec_name);
+  }
+
+  return psection;
+}
+
+/**************************************************************************
   Print log messages for any entries in the file which have
   not been looked up -- ie, unused or unrecognised entries.
   To mark an entry as used without actually doing anything with it,
@@ -359,20 +392,7 @@
 static struct section *find_section_by_name(struct section_file *sf,
                                            const char *name)
 {
-  /*
-   * Search backwards since on insertion the requested section is most
-   * likely at the end (on lookup it doesn't matter).
-   *
-   * Nonetheless this is slow if there are lots of sections.  We could have
-   * a hash on section names to speed it up.
-   */
-  section_list_iterate_rev(sf->sections, psection) {
-    if (strcmp(psection->name, name) == 0) {
-      return psection;
-    }
-  } section_list_iterate_rev_end;
-
-  return NULL;
+  return hash_lookup_data(sf->hash_sections, name);
 }      
 
 /**************************************************************************
@@ -432,10 +452,7 @@
       */
       psection = find_section_by_name(sf, tok);
       if (!psection) {
-       psection = sbuf_malloc(sb, sizeof(struct section));
-       psection->name = sbuf_strdup(sb, tok);
-       psection->entries = entry_list_new();
-       section_list_append(sf->sections, psection);
+       psection = section_file_append_section(sf, tok);
       }
       (void) inf_token_required(inf, INF_TOK_EOL);
       continue;
@@ -1254,7 +1271,6 @@
   return NULL;
 }
 
-
 /**************************************************************************
  The caller should ensure that "fullpath" should not refer to an entry
  which already exists in "my_section_file".  (Actually, in some cases
@@ -1301,11 +1317,8 @@
     return pentry;
   }
 
-  psection = sbuf_malloc(sb, sizeof(struct section));
-  psection->name = sbuf_strdup(sb, sec_name);
-  psection->entries = entry_list_new();
-  section_list_append(my_section_file->sections, psection);
-  
+  psection = section_file_append_section(my_section_file, sec_name);
+
   pentry = sbuf_malloc(sb, sizeof(struct entry));
   pentry->name = sbuf_strdup(sb, ent_name);
   entry_list_append(psection->entries, pentry);
@@ -1317,7 +1330,7 @@
 /**************************************************************************
  Return 0 if the section_file has not been setup for hashing.
 **************************************************************************/
-bool secfilehash_hashash(struct section_file *file)
+static bool secfilehash_hashash(struct section_file *file)
 {
   return (file->hashd && hash_num_buckets(file->hashd->htbl) != 0);
 }
@@ -1375,7 +1388,7 @@
  all entries must have unique names; in this case for duplicates
  the hash ref will be to the _last_ entry.
 **************************************************************************/
-void secfilehash_build(struct section_file *file, bool allow_duplicates)
+static void secfilehash_build(struct section_file *file, bool allow_duplicates)
 {
   struct hash_data *hashd;
   char buf[256];
@@ -1407,7 +1420,7 @@
 /**************************************************************************
  Free the memory allocated for the hash table.
 **************************************************************************/
-void secfilehash_free(struct section_file *file)
+static void secfilehash_free(struct section_file *file)
 {
   secfilehash_check(file);
   hash_free(file->hashd->htbl);
Index: utility/registry.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/registry.h,v
retrieving revision 1.25
diff -u -u -r1.25 registry.h
--- utility/registry.h  22 Jul 2004 19:04:33 -0000      1.25
+++ utility/registry.h  7 May 2005 15:49:32 -0000
@@ -24,6 +24,7 @@
   char *filename;
   int num_entries;
   struct section_list *sections;
+  struct hash_table *hash_sections;
   struct hash_data *hashd;
   struct sbuffer *sb;
 };
@@ -113,11 +114,4 @@
 char **secfile_get_section_entries(struct section_file *my_section_file,
                                   const char *section, int *num);
 
-/* Only need use these explicitly on section_files constructed,
-   not for ones generated by section_file_load:
-*/
-bool secfilehash_hashash(struct section_file *file);
-void secfilehash_build(struct section_file *file, bool allow_duplicates);
-void secfilehash_free(struct section_file *file);
-
 #endif  /* FC__REGISTRY_H */