--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/gccache-xlike-inc.c	Tue Feb 15 01:21:24 2005 +0000
@@ -0,0 +1,395 @@
+/* Efficient caching of GCs (graphics contexts) -- shared code, X and GTK.
+   Copyright (C) 1993 Free Software Foundation, Inc.
+   Copyright (C) 1994, 1995 Board of Trustees, University of Illinois.
+   Copyright (C) 2003, 2005 Ben Wing.
+
+This file is part of XEmacs.
+
+XEmacs is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+XEmacs is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with XEmacs; see the file COPYING.  If not, write to
+the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+/* Synched up with: Not in FSF. */
+
+/* Emacs uses a lot of different display attributes; for example, assume
+   that only four fonts are in use (normal, bold, italic, and bold-italic).
+   Then assume that one stipple or background is used for text selections,
+   and another is used for highlighting mousable regions.  That makes 16
+   GCs already.  Add in the fact that another GC may be needed to display
+   the text cursor in any of those regions, and you've got 32.  Add in
+   more fonts, and it keeps increasing exponentially.
+
+   We used to keep these GCs in a cache of merged (fully qualified) faces.
+   However, a lot of other code in xterm.c used XChangeGC of existing GCs,
+   which is kind of slow and kind of random.  Also, managing the face cache
+   was tricky because it was hard to know when a face was no longer visible
+   on the frame -- we had to mark all frames as garbaged whenever a face
+   was changed, which caused an unpleasant amount of flicker (since faces are
+   created/destroyed (= changed) whenever a frame is created/destroyed.
+
+   So this code maintains a cache at the GC level instead of at the face
+   level.  There is an upper limit on the size of the cache, after which we
+   will stop creating GCs and start reusing them (reusing the least-recently-
+   used ones first).  So if faces get changed, their GCs will eventually be
+   recycled.  Also more sharing of GCs is possible.
+
+   This code uses hash tables.  It could be that, if the cache size is small
+   enough, a linear search might be faster; but I doubt it, since we need
+   `equal' comparisons, not `eq', and I expect that the optimal cache size
+   will be ~100.
+
+   Written by jwz, 14 jun 93
+   Hacked by William Perry, apr 2000 for GTK and introduced code
+   duplication (a no-no)
+   Undid code duplication, Ben Wing, Jan 28, 2003.
+ */
+
+#include <config.h>
+#include "lisp.h"
+#include "hash.h"
+
+#ifndef THIS_IS_GTK
+#include <X11/Xlib.h>
+#else /* THIS_IS_GTK */
+#include <gtk/gtk.h>
+#endif /* THIS_IS_GTK */
+
+#define GC_CACHE_SIZE 100
+
+#define GCCACHE_HASH
+
+#ifndef THIS_IS_GTK
+#define ZZGCVALUES XGCValues
+#define ZZGC GC
+#define ZZ(z) x_##z
+#else
+#define ZZGCVALUES GdkGCValues
+#define ZZGC GdkGC *
+#define ZZ(z) gtk_##z
+#endif
+
+struct gcv_and_mask {
+  ZZGCVALUES gcv;
+  unsigned long mask;
+};
+
+struct gc_cache_cell {
+  ZZGC gc;
+  struct gcv_and_mask gcvm;
+  struct gc_cache_cell *prev, *next;
+};
+
+struct gc_cache {
+#ifndef THIS_IS_GTK
+  Display *dpy;		/* used only as arg to XCreateGC/XFreeGC */
+  Window window;	/* used only as arg to XCreateGC */
+#else /* THIS_IS_GTK */
+  GdkWindow *window;	/* used only as arg to XCreateGC */
+#endif /* THIS_IS_GTK */
+  int size;
+  struct gc_cache_cell *head;
+  struct gc_cache_cell *tail;
+#ifdef GCCACHE_HASH
+  struct hash_table *table;
+#endif
+
+  int create_count;
+  int delete_count;
+};
+
+#ifdef GCCACHE_HASH
+static Hashcode
+gc_cache_hash (const void *arg)
+{
+  const struct gcv_and_mask *gcvm = (const struct gcv_and_mask *) arg;
+  unsigned long *longs = (unsigned long *) &gcvm->gcv;
+  Hashcode hash = gcvm->mask;
+  int i;
+  /* This could look at the mask and only use the used slots in the
+     hash code.  That would win in that we wouldn't have to initialize
+     every slot of the gcv when calling gc_cache_lookup.  But we need
+     the hash function to be as fast as possible; some timings should
+     be done. */
+  for (i = 0; i < (int) (sizeof (ZZGCVALUES) /
+			 sizeof (unsigned long)); i++)
+    hash = (hash << 1) ^ *longs++;
+  return hash;
+}
+
+#endif /* GCCACHE_HASH */
+
+static int
+gc_cache_eql (const void *arg1, const void *arg2)
+{
+  /* See comment in gc_cache_hash */
+#ifndef THIS_IS_GTK
+  return !memcmp (arg1, arg2, sizeof (struct gcv_and_mask));
+#else /* THIS_IS_GTK */
+  const struct gcv_and_mask *gcvm1 = (const struct gcv_and_mask *) arg1;
+  const struct gcv_and_mask *gcvm2 = (const struct gcv_and_mask *) arg2;
+
+  return !memcmp (&gcvm1->gcv, &gcvm2->gcv, sizeof (gcvm1->gcv))
+    && gcvm1->mask == gcvm2->mask;
+#endif /* THIS_IS_GTK */
+}
+
+struct gc_cache *
+#ifndef THIS_IS_GTK
+ZZ (make_gc_cache) (Display *dpy, Window window)
+#else /* THIS_IS_GTK */
+ZZ (make_gc_cache) (GtkWidget *widget)
+#endif /* THIS_IS_GTK */
+{
+  struct gc_cache *cache = xnew (struct gc_cache);
+#ifndef THIS_IS_GTK
+  cache->dpy = dpy;
+  cache->window = window;
+#else /* THIS_IS_GTK */
+  cache->window = widget->window;
+#endif /* THIS_IS_GTK */
+  cache->size = 0;
+  cache->head = cache->tail = 0;
+  cache->create_count = cache->delete_count = 0;
+#ifdef GCCACHE_HASH
+  cache->table =
+    make_general_hash_table (GC_CACHE_SIZE, gc_cache_hash, gc_cache_eql);
+#endif
+  return cache;
+}
+
+void
+ZZ (free_gc_cache) (struct gc_cache *cache)
+{
+  struct gc_cache_cell *rest, *next;
+  rest = cache->head;
+  while (rest)
+    {
+#ifndef THIS_IS_GTK
+      XFreeGC (cache->dpy, rest->gc);
+#else /* THIS_IS_GTK */
+      gdk_gc_destroy (rest->gc);
+#endif /* THIS_IS_GTK */
+      next = rest->next;
+      xfree (rest, struct gc_cache_cell *);
+      rest = next;
+    }
+#ifdef GCCACHE_HASH
+  free_hash_table (cache->table);
+#endif
+  xfree (cache, struct gc_cache *);
+}
+
+ZZGC
+ZZ (gc_cache_lookup) (struct gc_cache *cache, ZZGCVALUES *gcv, unsigned long mask)
+{
+  struct gc_cache_cell *cell, *next, *prev;
+  struct gcv_and_mask gcvm;
+
+  if ((!!cache->head) != (!!cache->tail)) ABORT ();
+  if (cache->head && (cache->head->prev || cache->tail->next)) ABORT ();
+
+#ifdef THIS_IS_GTK
+  /* Gdk does not have the equivalent of 'None' for the clip_mask, so
+     we need to check it carefully, or gdk_gc_new_with_values will
+     coredump */
+  if ((mask & GDK_GC_CLIP_MASK) && !gcv->clip_mask)
+    mask = (GdkGCValuesMask) (mask & ~GDK_GC_CLIP_MASK);
+#endif /* THIS_IS_GTK */
+
+  gcvm.mask = mask;
+  gcvm.gcv = *gcv;	/* this copies... */
+
+#ifdef GCCACHE_HASH
+
+  if (gethash (&gcvm, cache->table, (const void **) &cell))
+
+#else /* !GCCACHE_HASH */
+
+  cell = cache->tail;	/* start at the end (most recently used) */
+  while (cell)
+    {
+      if (gc_cache_eql (&gcvm, &cell->gcvm))
+	break;
+      else
+	cell = cell->prev;
+    }
+
+  /* #### This whole file needs some serious overhauling. */
+#ifndef THIS_IS_GTK
+  if (!(mask | GCTile) && cell->gc->values.tile)
+#else /* THIS_IS_GTK */
+  if (!(mask | GDK_GC_TILE) && cell->gcvm.gcv.tile)
+#endif /* THIS_IS_GTK */
+    cell = 0;
+#ifndef THIS_IS_GTK
+  else if (!(mask | GCStipple) && cell->gc->values.stipple)
+#else /* THIS_IS_GTK */
+  else if (!(mask | GDK_GC_STIPPLE) && cell->gcvm.gcv.stipple)
+#endif /* THIS_IS_GTK */
+    cell = 0;
+
+  if (cell)
+
+#endif /* !GCCACHE_HASH */
+
+    {
+      /* Found a cell.  Move this cell to the end of the list, so that it
+	 will be less likely to be collected than a cell that was accessed
+	 less recently.
+       */
+      if (cell == cache->tail)
+	return cell->gc;
+
+      next = cell->next;
+      prev = cell->prev;
+      if (prev) prev->next = next;
+      if (next) next->prev = prev;
+      if (cache->head == cell) cache->head = next;
+      cell->next = 0;
+      cell->prev = cache->tail;
+      cache->tail->next = cell;
+      cache->tail = cell;
+      if (cache->head == cell) ABORT ();
+      if (cell->next) ABORT ();
+      if (cache->head->prev) ABORT ();
+      if (cache->tail->next) ABORT ();
+      return cell->gc;
+    }
+
+  /* else, cache miss. */
+
+  if (cache->size == GC_CACHE_SIZE)
+    /* Reuse the first cell on the list (least-recently-used).
+       Remove it from the list, and unhash it from the table.
+     */
+    {
+      cell = cache->head;
+      cache->head = cell->next;
+      cache->head->prev = 0;
+      if (cache->tail == cell) cache->tail = 0; /* only one */
+#ifndef THIS_IS_GTK
+      XFreeGC (cache->dpy, cell->gc);
+#else /* THIS_IS_GTK */
+      gdk_gc_destroy (cell->gc);
+#endif /* THIS_IS_GTK */
+      cache->delete_count++;
+#ifdef GCCACHE_HASH
+      remhash (&cell->gcvm, cache->table);
+#endif
+    }
+  else if (cache->size > GC_CACHE_SIZE)
+    ABORT ();
+  else
+    {
+      /* Allocate a new cell (don't put it in the list or table yet). */
+      cell = xnew (struct gc_cache_cell);
+      cache->size++;
+    }
+
+  /* Now we've got a cell (new or reused).  Fill it in. */
+  memcpy (&cell->gcvm.gcv, gcv, sizeof (ZZGCVALUES));
+  cell->gcvm.mask = mask;
+
+  /* Put the cell on the end of the list. */
+  cell->next = 0;
+  cell->prev = cache->tail;
+  if (cache->tail) cache->tail->next = cell;
+  cache->tail = cell;
+  if (! cache->head) cache->head = cell;
+
+  cache->create_count++;
+#ifdef GCCACHE_HASH
+  /* Hash it in the table */
+  puthash (&cell->gcvm, cell, cache->table);
+#endif
+
+  /* Now make and return the GC. */
+#ifndef THIS_IS_GTK
+  cell->gc = XCreateGC (cache->dpy, cache->window, mask, gcv);
+#else /* THIS_IS_GTK */
+  cell->gc = gdk_gc_new_with_values (cache->window, gcv, (GdkGCValuesMask) mask);
+#endif /* THIS_IS_GTK */
+
+  /* debug */
+  assert (cell->gc == ZZ (gc_cache_lookup) (cache, gcv, mask));
+
+  return cell->gc;
+}
+#ifndef THIS_IS_GTK
+
+
+#ifdef DEBUG_XEMACS
+
+void x_describe_gc_cache (struct gc_cache *cache);
+void
+x_describe_gc_cache (struct gc_cache *cache)
+{
+  int count = 0;
+  struct gc_cache_cell *cell = cache->head;
+  stderr_out ("\nsize:    %d", cache->size);
+  stderr_out ("\ncreated: %d", cache->create_count);
+  stderr_out ("\ndeleted: %d", cache->delete_count);
+  while (cell)
+  {
+    struct gc_cache_cell *cell2;
+    int i = 0;
+    stderr_out ("\n%d:\t0x%lx  GC: 0x%08lx  hash: 0x%08lx\n",
+	     count, (long) cell, (long) cell->gc, gc_cache_hash (&cell->gcvm));
+    for (cell2 = cache->head; cell2; cell2 = cell2->next, i++)
+      if (count != i &&
+	  gc_cache_hash (&cell->gcvm) == gc_cache_hash (&cell2->gcvm))
+	stderr_out ("\tHASH COLLISION with cell %d\n", i);
+    stderr_out ("\tmask:       %8lx\n", cell->gcvm.mask);
+
+#define FROB(field) do {						\
+  if ((int)cell->gcvm.gcv.field != (~0))				\
+    stderr_out ("\t%-12s%8x\n", #field ":", (int)cell->gcvm.gcv.field);	\
+} while (0)
+    FROB (function);
+    FROB (plane_mask);
+    FROB (foreground);
+    FROB (background);
+    FROB (line_width);
+    FROB (line_style);
+    FROB (cap_style);
+    FROB (join_style);
+    FROB (fill_style);
+    FROB (fill_rule);
+    FROB (arc_mode);
+    FROB (tile);
+    FROB (stipple);
+    FROB (ts_x_origin);
+    FROB (ts_y_origin);
+    FROB (font);
+    FROB (subwindow_mode);
+    FROB (graphics_exposures);
+    FROB (clip_x_origin);
+    FROB (clip_y_origin);
+    FROB (clip_mask);
+    FROB (dash_offset);
+#undef FROB
+
+    count++;
+    if (cell->next && cell == cache->tail)
+      stderr_out ("\nERROR!  tail is here!\n\n");
+    else if (!cell->next && cell != cache->tail)
+      stderr_out ("\nERROR!  tail is not at the end\n\n");
+    cell = cell->next;
+  }
+  if (count != cache->size)
+    stderr_out ("\nERROR!  count should be %d\n\n", cache->size);
+}
+
+#endif /* DEBUG_XEMACS */
+#endif /* ! THIS_IS_GTK */