src/util/atom.c

   1 /*
   2
   3 Copyright 1990, 1994, 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 /* lame atom replacement routines for font applications */
  32
  33 #ifdef HAVE_CONFIG_H
  34 #include <config.h>
  35 #endif
  36 #include <X11/fonts/fontmisc.h>
  37 #include "stubs.h"
  38
  39 typedef struct _AtomList {
  40     char                *name;
  41     int                 len;
  42     int                 hash;
  43     Atom                atom;
  44 } AtomListRec, *AtomListPtr;
  45
  46 static AtomListPtr  *hashTable;
  47
  48 static int          hashSize, hashUsed;
  49 static int          hashMask;
  50 static int          rehash;
  51
  52 static AtomListPtr  *reverseMap;
  53 static int          reverseMapSize;
  54 static Atom         lastAtom;
  55
  56 static int
  57 Hash(const char *string, int len)
  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 int
  70 ResizeHashTable (void)
  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 = calloc (newHashSize, sizeof (AtomListPtr));
  85     if (!newHashTable) {
  86         fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
  87                 " newHashTable (%ld)\n",
  88                 newHashSize * (unsigned long)sizeof (AtomListPtr));
  89         return FALSE;
  90     }
  91     newHashMask = newHashSize - 1;
  92     newRehash = (newHashMask - 2);
  93     for (i = 0; i < hashSize; i++)
  94     {
  95         if (hashTable[i])
  96         {
  97             h = (hashTable[i]->hash) & newHashMask;
  98             if (newHashTable[h])
  99             {
 100                 r = hashTable[i]->hash % newRehash | 1;
 101                 do {
 102                     h += r;
 103                     if (h >= newHashSize)
 104                         h -= newHashSize;
 105                 } while (newHashTable[h]);
 106             }
 107             newHashTable[h] = hashTable[i];
 108         }
 109     }
 110     free (hashTable);
 111     hashTable = newHashTable;
 112     hashSize = newHashSize;
 113     hashMask = newHashMask;
 114     rehash = newRehash;
 115     return TRUE;
 116 }
 117
 118 static int
 119 ResizeReverseMap (void)
 120 {
 121     int ret = TRUE;
 122     if (reverseMapSize == 0)
 123         reverseMapSize = 1000;
 124     else
 125         reverseMapSize *= 2;
 126     reverseMap = realloc (reverseMap, reverseMapSize * sizeof (AtomListPtr));
 127     if (!reverseMap) {
 128         fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
 129                 " reverseMap (%ld)\n",
 130                 reverseMapSize * (unsigned long)sizeof(AtomListPtr));
 131         ret = FALSE;
 132     }
 133     return ret;
 134 }
 135
 136 static int
 137 NameEqual (const char *a, const char *b, int l)
 138 {
 139     while (l--)
 140         if (*a++ != *b++)
 141             return FALSE;
 142     return TRUE;
 143 }
 144
 145 #ifdef __SUNPRO_C
 146 #pragma weak MakeAtom
 147 #endif
 148
 149 weak Atom
 150 MakeAtom(const char *string, unsigned len, int makeit)
 151 {
 152     AtomListPtr a;
 153     int         hash;
 154     int         h = 0;
 155     int         r;
 156
 157     hash = Hash (string, len);
 158     if (hashTable)
 159     {
 160         h = hash & hashMask;
 161         if (hashTable[h])
 162         {
 163             if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
 164                 NameEqual (hashTable[h]->name, string, len))
 165             {
 166                 return hashTable[h]->atom;
 167             }
 168             r = (hash % rehash) | 1;
 169             for (;;)
 170             {
 171                 h += r;
 172                 if (h >= hashSize)
 173                     h -= hashSize;
 174                 if (!hashTable[h])
 175                     break;
 176                 if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
 177                     NameEqual (hashTable[h]->name, string, len))
 178                 {
 179                     return hashTable[h]->atom;
 180                 }
 181             }
 182         }
 183     }
 184     if (!makeit)
 185         return None;
 186     a = malloc (sizeof (AtomListRec) + len + 1);
 187     if (a == NULL) {
 188         fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
 189                 " (%ld)\n", (unsigned long)sizeof (AtomListRec) + len + 1);
 190         return None;
 191     }
 192     a->name = (char *) (a + 1);
 193     a->len = len;
 194     strncpy (a->name, string, len);
 195     a->name[len] = '\0';
 196     a->atom = ++lastAtom;
 197     a->hash = hash;
 198     if (hashUsed >= hashSize / 2)
 199     {
 200         ResizeHashTable ();
 201         h = hash & hashMask;
 202         if (hashTable[h])
 203         {
 204             r = (hash % rehash) | 1;
 205             do {
 206                 h += r;
 207                 if (h >= hashSize)
 208                     h -= hashSize;
 209             } while (hashTable[h]);
 210         }
 211     }
 212     hashTable[h] = a;
 213     hashUsed++;
 214     if (reverseMapSize <= a->atom) {
 215         if (!ResizeReverseMap())
 216             return None;
 217     }
 218     reverseMap[a->atom] = a;
 219     return a->atom;
 220 }
 221
 222 #ifdef __SUNPRO_C
 223 #pragma weak ValidAtom
 224 #endif
 225
 226 weak int
 227 ValidAtom(Atom atom)
 228 {
 229     return (atom != None) && (atom <= lastAtom);
 230 }
 231
 232 #ifdef __SUNPRO_C
 233 #pragma weak NameForAtom
 234 #endif
 235
 236 weak char *
 237 NameForAtom(Atom atom)
 238 {
 239     if (atom != None && atom <= lastAtom)
 240         return reverseMap[atom]->name;
 241     return NULL;
 242 }