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