Improve lookup efficiency of color cache and prevent leaking

* src/xterm.c (x_parse_color): Move recently used colors to the
start of the cache and free unused entries when there are too
many.
(x_term_init, x_delete_display): Initialize and free new fields.
* src/xterm.h (struct x_display_info): New field
`color_names_length'.

2 files changed, 52 insertions, 2 deletions

diff --git a/src/xterm.c b/src/xterm.c
index 2c50b508151..5964a8bb483 100644
--- a/src/xterm.c
+++ b/src/xterm.c
@@ -7277,9 +7277,10 @@ x_parse_color (struct frame *f, const char *color_name,
   Display *dpy;
   Colormap cmap;
   struct x_display_info *dpyinfo;
-  struct color_name_cache_entry *cache_entry;
+  struct color_name_cache_entry *cache_entry, *last;
+  struct color_name_cache_entry *next, *color_entry;
   unsigned int hash, idx;
-  int rc;
+  int rc, i;
 
   /* Don't pass #RGB strings directly to XParseColor, because that
      follows the X convention of zero-extending each channel
@@ -7306,16 +7307,31 @@ x_parse_color (struct frame *f, const char *color_name,
   hash = x_hash_string_ignore_case (color_name);
   idx = hash % dpyinfo->color_names_size;
 
+  last = NULL;
+
   for (cache_entry = dpyinfo->color_names[idx];
        cache_entry; cache_entry = cache_entry->next)
     {
       if (!xstrcasecmp (cache_entry->name, color_name))
         {
+          /* Move recently used entries to the start of the color
+             cache.  */
+
+          if (last)
+            {
+              last->next = cache_entry->next;
+              cache_entry->next = dpyinfo->color_names[idx];
+
+              dpyinfo->color_names[idx] = cache_entry;
+            }
+
           if (cache_entry->valid)
             *color = cache_entry->rgb;
 
           return cache_entry->valid;
         }
+
+      last = cache_entry;
     }
 
   block_input ();
@@ -7323,6 +7339,7 @@ x_parse_color (struct frame *f, const char *color_name,
   unblock_input ();
 
   cache_entry = xzalloc (sizeof *cache_entry);
+  dpyinfo->color_names_length[idx] += 1;
 
   if (rc)
     cache_entry->rgb = *color;
@@ -7333,6 +7350,33 @@ x_parse_color (struct frame *f, const char *color_name,
 
   dpyinfo->color_names[idx] = cache_entry;
 
+  /* Don't let the color cache become too big.  */
+  if (dpyinfo->color_names_length[idx] > 128)
+    {
+      i = 0;
+
+      for (last = dpyinfo->color_names[idx]; last; last = last->next)
+        {
+          if (++i == 128)
+            {
+              next = last->next;
+              last->next = NULL;
+
+              for (color_entry = next; color_entry; color_entry = last)
+                {
+                  last = color_entry->next;
+
+                  xfree (color_entry->name);
+                  xfree (color_entry);
+
+                  dpyinfo->color_names_length[idx] -= 1;
+                }
+
+              return rc;
+            }
+        }
+    }
+
   return rc;
 }
 
@@ -24511,6 +24555,8 @@ x_term_init (Lisp_Object display_name, char *xrm_option, char *resource_name)
   dpyinfo->color_names_size = 256;
   dpyinfo->color_names = xzalloc (dpyinfo->color_names_size
                                   * sizeof *dpyinfo->color_names);
+  dpyinfo->color_names_length = xzalloc (dpyinfo->color_names_size
+                                         * sizeof *dpyinfo->color_names_length);
 
   /* Set the name of the terminal. */
   terminal->name = xlispstrdup (display_name);
@@ -25248,6 +25294,7 @@ x_delete_display (struct x_display_info *dpyinfo)
     }
 
   xfree (dpyinfo->color_names);
+  xfree (dpyinfo->color_names_length);
   xfree (dpyinfo->x_id_name);
   xfree (dpyinfo->x_dnd_atoms);
   xfree (dpyinfo->color_cells);
diff --git a/src/xterm.h b/src/xterm.h
index daeb1a4575f..fbb381d066e 100644
--- a/src/xterm.h
+++ b/src/xterm.h
@@ -520,6 +520,9 @@ struct x_display_info
   /* A cache mapping color names to RGB values.  */
   struct color_name_cache_entry **color_names;
 
+  /* The number of buckets for each hash in that hash table.  */
+  ptrdiff_t *color_names_length;
+
   /* The size of that hash table.  */
   int color_names_size;