git.sesse.net Git - rdpsrv/blob - Xserver/lib/font/util/patcache.c

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