src/util/patcache.c

   1 /*
   2
   3 Copyright 1991, 1998  The Open Group
   4
   5 Permission to use, copy, modify, distribute, and sell this software and its
   6 documentation for any purpose is hereby granted without fee, provided that
   7 the above copyright notice appear in all copies and that both that
   8 copyright notice and this permission notice appear in supporting
   9 documentation.
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20
  21 Except as contained in this notice, the name of The Open Group shall not be
  22 used in advertising or otherwise to promote the sale, use or other dealings
  23 in this Software without prior written authorization from The Open Group.
  24
  25 */
  26
  27 /*
  28  * Author:  Keith Packard, MIT X Consortium
  29  */
  30
  31 #ifdef HAVE_CONFIG_H
  32 #include <config.h>
  33 #endif
  34 #include    <X11/fonts/fontmisc.h>
  35 #include    <X11/fonts/fontstruct.h>
  36
  37 /*
  38  * Static sized hash table for looking up font name patterns
  39  *
  40  * LRU entries, reusing old entries
  41  */
  42
  43 #define NBUCKETS        16
  44 #define NENTRIES        64
  45
  46 #define UNSET           (NENTRIES+1)
  47
  48 typedef unsigned char   EntryPtr;
  49
  50 typedef struct _FontPatternCacheEntry {
  51     struct _FontPatternCacheEntry   *next, **prev;
  52     short                           patlen;
  53     char                            *pattern;
  54     int                             hash;
  55     FontPtr                         pFont;      /* associated font */
  56 } FontPatternCacheEntryRec, *FontPatternCacheEntryPtr;
  57
  58 typedef struct _FontPatternCache {
  59     FontPatternCacheEntryPtr    buckets[NBUCKETS];
  60     FontPatternCacheEntryRec    entries[NENTRIES];
  61     FontPatternCacheEntryPtr    free;
  62 } FontPatternCacheRec;
  63
  64 /* Empty cache (for rehash) */
  65 void
  66 EmptyFontPatternCache (FontPatternCachePtr cache)
  67 {
  68     int     i;
  69
  70     for (i = 0; i < NBUCKETS; i++)
  71         cache->buckets[i] = 0;
  72     for (i = 0; i < NENTRIES; i++)
  73     {
  74         cache->entries[i].next = &cache->entries[i+1];
  75         cache->entries[i].prev = 0;
  76         cache->entries[i].pFont = 0;
  77         free (cache->entries[i].pattern);
  78         cache->entries[i].pattern = 0;
  79         cache->entries[i].patlen = 0;
  80     }
  81     cache->free = &cache->entries[0];
  82     cache->entries[NENTRIES - 1].next = 0;
  83 }
  84
  85 /* Create and initialize cache */
  86 FontPatternCachePtr
  87 MakeFontPatternCache (void)
  88 {
  89     FontPatternCachePtr cache;
  90     int                 i;
  91     cache = malloc (sizeof *cache);
  92     if (!cache)
  93         return 0;
  94     for (i = 0; i < NENTRIES; i++) {
  95         cache->entries[i].patlen = 0;
  96         cache->entries[i].pattern = 0;
  97         cache->entries[i].pFont = 0;
  98     }
  99     EmptyFontPatternCache (cache);
 100     return cache;
 101 }
 102
 103 /* toss cache */
 104 void
 105 FreeFontPatternCache (FontPatternCachePtr cache)
 106 {
 107     int     i;
 108
 109     for (i = 0; i < NENTRIES; i++)
 110         free (cache->entries[i].pattern);
 111     free (cache);
 112 }
 113
 114 /* compute id for string */
 115 static int
 116 Hash (const char *string, int len)
 117 {
 118     int hash;
 119
 120     hash = 0;
 121     while (len--)
 122         hash = (hash << 1) ^ *string++;
 123     if (hash < 0)
 124         hash = -hash;
 125     return hash;
 126 }
 127
 128 /* add entry */
 129 void
 130 CacheFontPattern (FontPatternCachePtr cache,
 131                   char *pattern,
 132                   int patlen,
 133                   FontPtr pFont)
 134 {
 135     FontPatternCacheEntryPtr    e;
 136     char                        *newpat;
 137     int                         i;
 138
 139     newpat = malloc (patlen);
 140     if (!newpat)
 141         return;
 142     if (cache->free)
 143     {
 144         e = cache->free;
 145         cache->free = e->next;
 146     }
 147     else
 148     {
 149         i = rand ();
 150         if (i < 0)
 151             i = -i;
 152         i %= NENTRIES;
 153         e = &cache->entries[i];
 154         if (e->next)
 155             e->next->prev = e->prev;
 156         *e->prev = e->next;
 157         free (e->pattern);
 158     }
 159     /* set pattern */
 160     memcpy (newpat, pattern, patlen);
 161     e->pattern = newpat;
 162     e->patlen = patlen;
 163     /* link to new hash chain */
 164     e->hash = Hash (pattern, patlen);
 165     i = e->hash % NBUCKETS;
 166     e->next = cache->buckets[i];
 167     if (e->next)
 168         e->next->prev = &(e->next);
 169     cache->buckets[i] = e;
 170     e->prev = &(cache->buckets[i]);
 171     e->pFont = pFont;
 172 }
 173
 174 /* find matching entry */
 175 FontPtr
 176 FindCachedFontPattern (FontPatternCachePtr cache,
 177                        char *pattern,
 178                        int patlen)
 179 {
 180     int                         hash;
 181     int                         i;
 182     FontPatternCacheEntryPtr    e;
 183
 184     hash = Hash (pattern, patlen);
 185     i = hash % NBUCKETS;
 186     for (e = cache->buckets[i]; e; e = e->next)
 187     {
 188         if (e->patlen == patlen && e->hash == hash &&
 189             !memcmp (e->pattern, pattern, patlen))
 190         {
 191             return e->pFont;
 192         }
 193     }
 194     return 0;
 195 }
 196
 197 void
 198 RemoveCachedFontPattern (FontPatternCachePtr cache,
 199                          FontPtr pFont)
 200 {
 201     FontPatternCacheEntryPtr    e;
 202     int                         i;
 203
 204     for (i = 0; i < NENTRIES; i++)
 205     {
 206         if ((e = &cache->entries[i])->pFont == pFont)
 207         {
 208             e->pFont = 0;
 209             if (e->next)
 210                 e->next->prev = e->prev;
 211             *e->prev = e->next;
 212             e->next = cache->free;
 213             cache->free = e;
 214             free (e->pattern);
 215             e->pattern = 0;
 216         }
 217     }
 218 }