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

   1 /* $XConsortium: atom.c,v 1.4 94/04/17 20:17:31 gildea Exp $ */
   2
   3 /*
   4
   5 Copyright (c) 1990, 1994  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
  30 /*
  31  * Author:  Keith Packard, MIT X Consortium
  32  */
  33
  34 /* lame atom replacement routines for font applications */
  35
  36 #include "fontmisc.h"
  37
  38 typedef struct _AtomList {
  39     char                *name;
  40     int                 len;
  41     int                 hash;
  42     Atom                atom;
  43 } AtomListRec, *AtomListPtr;
  44
  45 static AtomListPtr  *hashTable;
  46
  47 static int          hashSize, hashUsed;
  48 static int          hashMask;
  49 static int          rehash;
  50
  51 static AtomListPtr  *reverseMap;
  52 static int          reverseMapSize;
  53 static Atom         lastAtom;
  54
  55 static
  56 Hash(string, len)
  57     char    *string;
  58 {
  59     int h;
  60
  61     h = 0;
  62     while (len--)
  63         h = (h << 3) ^ *string++;
  64     if (h < 0)
  65         return -h;
  66     return h;
  67 }
  68
  69 static
  70 ResizeHashTable ()
  71 {
  72     int         newHashSize;
  73     int         newHashMask;
  74     AtomListPtr *newHashTable;
  75     int         i;
  76     int         h;
  77     int         newRehash;
  78     int         r;
  79
  80     if (hashSize == 0)
  81         newHashSize = 1024;
  82     else
  83         newHashSize = hashSize * 2;
  84     newHashTable = (AtomListPtr *) xalloc (newHashSize * sizeof (AtomListPtr));
  85     if (!newHashTable)
  86         return FALSE;
  87     bzero ((char *) newHashTable, newHashSize * sizeof (AtomListPtr));
  88     newHashMask = newHashSize - 1;
  89     newRehash = (newHashMask - 2);
  90     for (i = 0; i < hashSize; i++)
  91     {
  92         if (hashTable[i])
  93         {
  94             h = (hashTable[i]->hash) & newHashMask;
  95             if (newHashTable[h])
  96             {
  97                 r = hashTable[i]->hash % newRehash | 1;
  98                 do {
  99                     h += r;
 100                     if (h >= newHashSize)
 101                         h -= newHashSize;
 102                 } while (newHashTable[h]);
 103             }
 104             newHashTable[h] = hashTable[i];
 105         }
 106     }
 107     xfree (hashTable);
 108     hashTable = newHashTable;
 109     hashSize = newHashSize;
 110     hashMask = newHashMask;
 111     rehash = newRehash;
 112     return TRUE;
 113 }
 114
 115 static
 116 ResizeReverseMap ()
 117 {
 118     if (reverseMapSize == 0)
 119         reverseMapSize = 1000;
 120     else
 121         reverseMapSize *= 2;
 122     reverseMap = (AtomListPtr *) xrealloc (reverseMap, reverseMapSize * sizeof (AtomListPtr));
 123     if (!reverseMap)
 124         return FALSE;
 125 }
 126
 127 static
 128 NameEqual (a, b, l)
 129     char    *a, *b;
 130 {
 131     while (l--)
 132         if (*a++ != *b++)
 133             return FALSE;
 134     return TRUE;
 135 }
 136
 137 Atom
 138 MakeAtom(string, len, makeit)
 139     char *string;
 140     unsigned len;
 141     int makeit;
 142 {
 143     AtomListPtr a;
 144     int         hash;
 145     int         h;
 146     int         r;
 147
 148     hash = Hash (string, len);
 149     if (hashTable)
 150     {
 151         h = hash & hashMask;
 152         if (hashTable[h])
 153         {
 154             if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
 155                 NameEqual (hashTable[h]->name, string, len))
 156             {
 157                 return hashTable[h]->atom;
 158             }
 159             r = (hash % rehash) | 1;
 160             for (;;)
 161             {
 162                 h += r;
 163                 if (h >= hashSize)
 164                     h -= hashSize;
 165                 if (!hashTable[h])
 166                     break;
 167                 if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
 168                     NameEqual (hashTable[h]->name, string, len))
 169                 {
 170                     return hashTable[h]->atom;
 171                 }
 172             }
 173         }
 174     }
 175     if (!makeit)
 176         return None;
 177     a = (AtomListPtr) xalloc (sizeof (AtomListRec) + len + 1);
 178     a->name = (char *) (a + 1);
 179     a->len = len;
 180     strncpy (a->name, string, len);
 181     a->name[len] = '\0';
 182     a->atom = ++lastAtom;
 183     a->hash = hash;
 184     if (hashUsed >= hashSize / 2)
 185     {
 186         ResizeHashTable ();
 187         h = hash & hashMask;
 188         if (hashTable[h])
 189         {
 190             r = (hash % rehash) | 1;
 191             do {
 192                 h += r;
 193                 if (h >= hashSize)
 194                     h -= hashSize;
 195             } while (hashTable[h]);
 196         }
 197     }
 198     hashTable[h] = a;
 199     hashUsed++;
 200     if (reverseMapSize <= a->atom)
 201         ResizeReverseMap();
 202     reverseMap[a->atom] = a;
 203     return a->atom;
 204 }
 205
 206 ValidAtom(atom)
 207     Atom atom;
 208 {
 209     return (atom != None) && (atom <= lastAtom);
 210 }
 211
 212 char *
 213 NameForAtom(atom)
 214     Atom atom;
 215 {
 216     if (atom != None && atom <= lastAtom)
 217         return reverseMap[atom]->name;
 218     return 0;
 219 }