git.chise.org Git - chise/xemacs-chise.git-/blob - src/xgccache.c

   1 /* Efficient caching of X GCs (graphics contexts).
   2    Copyright (C) 1993 Free Software Foundation, Inc.
   3    Copyright (C) 1994, 1995 Board of Trustees, University of Illinois.
   4
   5 This file is part of XEmacs.
   6
   7 XEmacs is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 2, or (at your option) any
  10 later version.
  11
  12 XEmacs is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with XEmacs; see the file COPYING.  If not, write to
  19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 /* Synched up with: Not in FSF. */
  23
  24 /* Emacs uses a lot of different display attributes; for example, assume
  25    that only four fonts are in use (normal, bold, italic, and bold-italic).
  26    Then assume that one stipple or background is used for text selections,
  27    and another is used for highlighting mousable regions.  That makes 16
  28    GCs already.  Add in the fact that another GC may be needed to display
  29    the text cursor in any of those regions, and you've got 32.  Add in
  30    more fonts, and it keeps increasing exponentially.
  31
  32    We used to keep these GCs in a cache of merged (fully qualified) faces.
  33    However, a lot of other code in xterm.c used XChangeGC of existing GCs,
  34    which is kind of slow and kind of random.  Also, managing the face cache
  35    was tricky because it was hard to know when a face was no longer visible
  36    on the frame -- we had to mark all frames as garbaged whenever a face
  37    was changed, which caused an unpleasant amount of flicker (since faces are
  38    created/destroyed (= changed) whenever a frame is created/destroyed.
  39
  40    So this code maintains a cache at the GC level instead of at the face
  41    level.  There is an upper limit on the size of the cache, after which we
  42    will stop creating GCs and start reusing them (reusing the least-recently-
  43    used ones first).  So if faces get changed, their GCs will eventually be
  44    recycled.  Also more sharing of GCs is possible.
  45
  46    This code uses hash tables.  It could be that, if the cache size is small
  47    enough, a linear search might be faster; but I doubt it, since we need
  48    `equal' comparisons, not `eq', and I expect that the optimal cache size
  49    will be ~100.
  50
  51    Written by jwz, 14 jun 93
  52  */
  53
  54 #include <config.h>
  55 #include <X11/Xlib.h>
  56 #include "xgccache.h"
  57
  58
  59 #define GC_CACHE_SIZE 100
  60
  61 #define GCCACHE_HASH
  62
  63
  64 #ifdef GCCACHE_HASH
  65 #include "lisp.h"
  66 #include "hash.h"
  67 #endif
  68
  69 struct gcv_and_mask {
  70   XGCValues gcv;
  71   unsigned long mask;
  72 };
  73
  74 struct gc_cache_cell {
  75   GC gc;
  76   struct gcv_and_mask gcvm;
  77   struct gc_cache_cell *prev, *next;
  78 };
  79
  80 struct gc_cache {
  81   Display *dpy;         /* used only as arg to XCreateGC/XFreeGC */
  82   Window window;        /* used only as arg to XCreateGC */
  83   int size;
  84   struct gc_cache_cell *head;
  85   struct gc_cache_cell *tail;
  86 #ifdef GCCACHE_HASH
  87   struct hash_table *table;
  88 #endif
  89
  90   int create_count;
  91   int delete_count;
  92 };
  93
  94 #ifdef GCCACHE_HASH
  95 static unsigned long
  96 gc_cache_hash (const void *arg)
  97 {
  98   const struct gcv_and_mask *gcvm = (const struct gcv_and_mask *) arg;
  99   unsigned long *longs = (unsigned long *) &gcvm->gcv;
 100   unsigned long hash = gcvm->mask;
 101   size_t i;
 102   /* This could look at the mask and only use the used slots in the
 103      hash code.  That would win in that we wouldn't have to initialize
 104      every slot of the gcv when calling gc_cache_lookup.  But we need
 105      the hash function to be as fast as possible; some timings should
 106      be done. */
 107   for (i = 0; i < (sizeof (XGCValues) / sizeof (unsigned long)); i++)
 108     hash = (hash<<1) ^ *longs++;
 109   return hash;
 110 }
 111
 112 #endif /* GCCACHE_HASH */
 113
 114 static int
 115 gc_cache_eql (const void *arg1, const void *arg2)
 116 {
 117   /* See comment in gc_cache_hash */
 118   return !memcmp (arg1, arg2, sizeof (struct gcv_and_mask));
 119 }
 120
 121 struct gc_cache *
 122 make_gc_cache (Display *dpy, Window window)
 123 {
 124   struct gc_cache *cache = xnew (struct gc_cache);
 125   cache->dpy = dpy;
 126   cache->window = window;
 127   cache->size = 0;
 128   cache->head = cache->tail = 0;
 129   cache->create_count = cache->delete_count = 0;
 130 #ifdef GCCACHE_HASH
 131   cache->table =
 132     make_general_hash_table (GC_CACHE_SIZE, gc_cache_hash, gc_cache_eql);
 133 #endif
 134   return cache;
 135 }
 136
 137 void
 138 free_gc_cache (struct gc_cache *cache)
 139 {
 140   struct gc_cache_cell *rest, *next;
 141   rest = cache->head;
 142   while (rest)
 143     {
 144       XFreeGC (cache->dpy, rest->gc);
 145       next = rest->next;
 146       xfree (rest);
 147       rest = next;
 148     }
 149 #ifdef GCCACHE_HASH
 150   free_hash_table (cache->table);
 151 #endif
 152   xfree (cache);
 153 }
 154
 155 GC
 156 gc_cache_lookup (struct gc_cache *cache, XGCValues *gcv, unsigned long mask)
 157 {
 158   struct gc_cache_cell *cell, *next, *prev;
 159   struct gcv_and_mask gcvm;
 160
 161   if ((!!cache->head) != (!!cache->tail)) ABORT ();
 162   if (cache->head && (cache->head->prev || cache->tail->next)) ABORT ();
 163
 164   gcvm.mask = mask;
 165   gcvm.gcv = *gcv;      /* this copies... */
 166
 167 #ifdef GCCACHE_HASH
 168
 169   if (gethash (&gcvm, cache->table, (const void **) &cell))
 170
 171 #else /* !GCCACHE_HASH */
 172
 173   cell = cache->tail;   /* start at the end (most recently used) */
 174   while (cell)
 175     {
 176       if (gc_cache_eql (&gcvm, &cell->gcvm))
 177         break;
 178       else
 179         cell = cell->prev;
 180     }
 181
 182   /* #### This whole file needs some serious overhauling. */
 183   if (!(mask | GCTile) && cell->gc->values.tile)
 184     cell = 0;
 185   else if (!(mask | GCStipple) && cell->gc->values.stipple)
 186     cell = 0;
 187
 188   if (cell)
 189
 190 #endif /* !GCCACHE_HASH */
 191
 192     {
 193       /* Found a cell.  Move this cell to the end of the list, so that it
 194          will be less likely to be collected than a cell that was accessed
 195          less recently.
 196        */
 197       if (cell == cache->tail)
 198         return cell->gc;
 199
 200       next = cell->next;
 201       prev = cell->prev;
 202       if (prev) prev->next = next;
 203       if (next) next->prev = prev;
 204       if (cache->head == cell) cache->head = next;
 205       cell->next = 0;
 206       cell->prev = cache->tail;
 207       cache->tail->next = cell;
 208       cache->tail = cell;
 209       if (cache->head == cell) ABORT ();
 210       if (cell->next) ABORT ();
 211       if (cache->head->prev) ABORT ();
 212       if (cache->tail->next) ABORT ();
 213       return cell->gc;
 214     }
 215
 216   /* else, cache miss. */
 217
 218   if (cache->size == GC_CACHE_SIZE)
 219     /* Reuse the first cell on the list (least-recently-used).
 220        Remove it from the list, and unhash it from the table.
 221      */
 222     {
 223       cell = cache->head;
 224       cache->head = cell->next;
 225       cache->head->prev = 0;
 226       if (cache->tail == cell) cache->tail = 0; /* only one */
 227       XFreeGC (cache->dpy, cell->gc);
 228       cache->delete_count++;
 229 #ifdef GCCACHE_HASH
 230       remhash (&cell->gcvm, cache->table);
 231 #endif
 232     }
 233   else if (cache->size > GC_CACHE_SIZE)
 234     ABORT ();
 235   else
 236     {
 237       /* Allocate a new cell (don't put it in the list or table yet). */
 238       cell = xnew (struct gc_cache_cell);
 239       cache->size++;
 240     }
 241
 242   /* Now we've got a cell (new or reused).  Fill it in. */
 243   memcpy (&cell->gcvm.gcv, gcv, sizeof (XGCValues));
 244   cell->gcvm.mask = mask;
 245
 246   /* Put the cell on the end of the list. */
 247   cell->next = 0;
 248   cell->prev = cache->tail;
 249   if (cache->tail) cache->tail->next = cell;
 250   cache->tail = cell;
 251   if (! cache->head) cache->head = cell;
 252
 253   cache->create_count++;
 254 #ifdef GCCACHE_HASH
 255   /* Hash it in the table */
 256   puthash (&cell->gcvm, cell, cache->table);
 257 #endif
 258
 259   /* Now make and return the GC. */
 260   cell->gc = XCreateGC (cache->dpy, cache->window, mask, gcv);
 261
 262   /* debug */
 263   assert (cell->gc == gc_cache_lookup (cache, gcv, mask));
 264
 265   return cell->gc;
 266 }
 267
 268 \f
 269 #ifdef DEBUG_XEMACS
 270
 271 void describe_gc_cache (struct gc_cache *cache);
 272 void
 273 describe_gc_cache (struct gc_cache *cache)
 274 {
 275   int count = 0;
 276   struct gc_cache_cell *cell = cache->head;
 277   stderr_out ("\nsize:    %d", cache->size);
 278   stderr_out ("\ncreated: %d", cache->create_count);
 279   stderr_out ("\ndeleted: %d", cache->delete_count);
 280   while (cell)
 281   {
 282     struct gc_cache_cell *cell2;
 283     int i = 0;
 284     stderr_out ("\n%d:\t0x%lx  GC: 0x%08lx  hash: 0x%08lx\n",
 285              count, (long) cell, (long) cell->gc, gc_cache_hash (&cell->gcvm));
 286     for (cell2 = cache->head; cell2; cell2 = cell2->next, i++)
 287       if (count != i &&
 288           gc_cache_hash (&cell->gcvm) == gc_cache_hash (&cell2->gcvm))
 289         stderr_out ("\tHASH COLLISION with cell %d\n", i);
 290     stderr_out ("\tmask:       %8lx\n", cell->gcvm.mask);
 291
 292 #define FROB(field) do {                                                \
 293   if ((int)cell->gcvm.gcv.field != (~0))                                \
 294     stderr_out ("\t%-12s%8x\n", #field ":", (int)cell->gcvm.gcv.field); \
 295 } while (0)
 296     FROB (function);
 297     FROB (plane_mask);
 298     FROB (foreground);
 299     FROB (background);
 300     FROB (line_width);
 301     FROB (line_style);
 302     FROB (cap_style);
 303     FROB (join_style);
 304     FROB (fill_style);
 305     FROB (fill_rule);
 306     FROB (arc_mode);
 307     FROB (tile);
 308     FROB (stipple);
 309     FROB (ts_x_origin);
 310     FROB (ts_y_origin);
 311     FROB (font);
 312     FROB (subwindow_mode);
 313     FROB (graphics_exposures);
 314     FROB (clip_x_origin);
 315     FROB (clip_y_origin);
 316     FROB (clip_mask);
 317     FROB (dash_offset);
 318 #undef FROB
 319
 320     count++;
 321     if (cell->next && cell == cache->tail)
 322       stderr_out ("\nERROR!  tail is here!\n\n");
 323     else if (!cell->next && cell != cache->tail)
 324       stderr_out ("\nERROR!  tail is not at the end\n\n");
 325     cell = cell->next;
 326   }
 327   if (count != cache->size)
 328     stderr_out ("\nERROR!  count should be %d\n\n", cache->size);
 329 }
 330
 331 #endif /* DEBUG_XEMACS */