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 = NULL, *next = NULL, *prev = NULL;
 152         struct gcv_and_mask gcvm;
 153
 154         if (cache == NULL)
 155                 abort();
 156         else if ((!!cache->head) != (!!cache->tail))
 157                 abort();
 158         else if (cache->head && cache->tail && (cache->head->prev || cache->tail->next))
 159                 abort();
 160         else {
 161                 gcvm.mask = mask;
 162                 gcvm.gcv = *gcv;        /* this copies... */
 163
 164 #ifdef GCCACHE_HASH
 165
 166                 if (gethash(&gcvm, cache->table,
 167                             (const void **)((void*)&cell)))
 168 #else                           /* !GCCACHE_HASH */
 169
 170                 /* start at the end (most recently used) */
 171                 cell = cache->tail;
 172                 while (cell) {
 173                         if (gc_cache_eql(&gcvm, &cell->gcvm))
 174                                 break;
 175                         else
 176                                 cell = cell->prev;
 177                 }
 178
 179                 /* #### This whole file needs some serious overhauling. */
 180                 if (!(mask | GCTile) && cell->gc->values.tile)
 181                         cell = NULL;
 182                 else if (!(mask | GCStipple) && cell->gc->values.stipple)
 183                         cell = NULL;
 184 #endif                          /* !GCCACHE_HASH */
 185
 186                 {
 187                         /* Found a cell.  Move this cell to the end of
 188                            the list, so that it will be less likely to
 189                            be collected than a cell that was accessed
 190                            less recently.
 191                         */
 192
 193                         if (!cell) {
 194                                 abort();
 195                                 return NULL;
 196                         } else {
 197                                 if (cell == cache->tail)
 198                                         return cell->gc;
 199                                 next = cell->next;
 200                                 prev = cell->prev;
 201                                 if (prev)
 202                                         prev->next = next;
 203                                 if (next)
 204                                         next->prev = prev;
 205                                 if (cache->head == cell)
 206                                         cache->head = next;
 207                                 cell->next = NULL;
 208                                 cell->prev = cache->tail;
 209                                 if (cache->tail)
 210                                         cache->tail->next = cell;
 211                                 else
 212                                         abort();
 213                                 cache->tail = cell;
 214                                 if (cache->head == cell)
 215                                         abort();
 216                                 else if (cell->next)
 217                                         abort();
 218                                 else if (cache->head != NULL && cache->head->prev)
 219                                         abort();
 220                                 else if (cache->tail != NULL && cache->tail->next)
 221                                         abort();
 222                                 return cell->gc;
 223                         }
 224                 }
 225
 226                 /* else, cache miss. */
 227                 if (cache == NULL)
 228                         abort();
 229                 else if (cache->size == GC_CACHE_SIZE)
 230                         /* Reuse the first cell on the list
 231                            (least-recently-used).  Remove it from the
 232                            list, and unhash it from the table.
 233                         */
 234                 {
 235                         cell = cache->head;
 236                         cache->head = cell->next;
 237                         cache->head->prev = 0;
 238                         if (cache->tail == cell)
 239                                 cache->tail = 0;        /* only one */
 240                         XFreeGC(cache->dpy, cell->gc);
 241                         cache->delete_count++;
 242 #ifdef GCCACHE_HASH
 243                         remhash(&cell->gcvm, cache->table);
 244 #endif
 245                 } else if (cache->size > GC_CACHE_SIZE)
 246                         abort();
 247                 else {
 248                         /* Allocate a new cell (don't put it in the
 249                            list or table yet). */
 250                         cell = xnew(struct gc_cache_cell);
 251                         cache->size++;
 252                 }
 253                 if (cell != NULL) {
 254                         /* Now we've got a cell (new or reused).  Fill
 255                            it in. */
 256                         memcpy(&cell->gcvm.gcv, gcv, sizeof(XGCValues));
 257                         cell->gcvm.mask = mask;
 258
 259                         /* Put the cell on the end of the list. */
 260                         cell->next = 0;
 261                         cell->prev = cache->tail;
 262                         if (cache->tail)
 263                                 cache->tail->next = cell;
 264                         cache->tail = cell;
 265                         if (!cache->head)
 266                                 cache->head = cell;
 267                         cache->create_count++;
 268 #ifdef GCCACHE_HASH
 269                         /* Hash it in the table */
 270                         puthash(&cell->gcvm, cell, cache->table);
 271 #endif
 272                         /* Now make and return the GC. */
 273                         cell->gc = XCreateGC(cache->dpy, cache->window,
 274                                              mask, gcv);
 275                         /* debug */
 276                         assert(cell->gc == gc_cache_lookup(cache, gcv, mask));
 277                         return cell->gc;
 278                 }
 279         }
 280         return NULL; /* No cell determined */
 281 }
 282 \f
 283 #ifdef DEBUG_SXEMACS
 284
 285 void describe_gc_cache(struct gc_cache *cache);
 286 void describe_gc_cache(struct gc_cache *cache)
 287 {
 288         int count = 0;
 289         struct gc_cache_cell *cell = cache->head;
 290         stderr_out("\nsize:    %d", cache->size);
 291         stderr_out("\ncreated: %d", cache->create_count);
 292         stderr_out("\ndeleted: %d", cache->delete_count);
 293         while (cell) {
 294                 struct gc_cache_cell *cell2;
 295                 int i = 0;
 296                 stderr_out("\n%d:\t0x%lx  GC: 0x%08lx  hash: 0x%08lx\n",
 297                            count, (long)cell, (long)cell->gc,
 298                            gc_cache_hash(&cell->gcvm));
 299                 for (cell2 = cache->head; cell2; cell2 = cell2->next, i++)
 300                         if (count != i &&
 301                             gc_cache_hash(&cell->gcvm) ==
 302                             gc_cache_hash(&cell2->gcvm))
 303                                 stderr_out("\tHASH COLLISION with cell %d\n",
 304                                            i);
 305                 stderr_out("\tmask:       %8lx\n", cell->gcvm.mask);
 306
 307 #define FROB(field) do {                                                \
 308   if ((int)cell->gcvm.gcv.field != (~0))                                \
 309     stderr_out ("\t%-12s%8x\n", #field ":", (int)cell->gcvm.gcv.field); \
 310 } while (0)
 311                 FROB(function);
 312                 FROB(plane_mask);
 313                 FROB(foreground);
 314                 FROB(background);
 315                 FROB(line_width);
 316                 FROB(line_style);
 317                 FROB(cap_style);
 318                 FROB(join_style);
 319                 FROB(fill_style);
 320                 FROB(fill_rule);
 321                 FROB(arc_mode);
 322                 FROB(tile);
 323                 FROB(stipple);
 324                 FROB(ts_x_origin);
 325                 FROB(ts_y_origin);
 326                 FROB(font);
 327                 FROB(subwindow_mode);
 328                 FROB(graphics_exposures);
 329                 FROB(clip_x_origin);
 330                 FROB(clip_y_origin);
 331                 FROB(clip_mask);
 332                 FROB(dash_offset);
 333 #undef FROB
 334
 335                 count++;
 336                 if (cell->next && cell == cache->tail)
 337                         stderr_out("\nERROR!  tail is here!\n\n");
 338                 else if (!cell->next && cell != cache->tail)
 339                         stderr_out("\nERROR!  tail is not at the end\n\n");
 340                 cell = cell->next;
 341         }
 342         if (count != cache->size)
 343                 stderr_out("\nERROR!  count should be %d\n\n", cache->size);
 344 }
 345
 346 #endif                          /* DEBUG_SXEMACS */