1/*
2
3Copyright 1990, 1994, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in 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 "fontmisc.h"
37
38typedef struct _AtomList {
39    char        *name;
40    unsigned int len;
41    int          hash;
42    Atom         atom;
43} AtomListRec, *AtomListPtr;
44
45static AtomListPtr *hashTable;
46
47static unsigned hashSize, hashUsed;
48static unsigned hashMask;
49static unsigned rehash;
50
51static AtomListPtr *reverseMap;
52static size_t reverseMapSize;
53static Atom lastAtom;
54
55static unsigned
56Hash(const char *string, unsigned len)
57{
58    unsigned h = 0;
59
60    while (len--)
61        h = (h << 3) ^ *string++;
62
63    return h;
64}
65
66static int
67ResizeHashTable(void)
68{
69    unsigned newHashSize;
70    unsigned newHashMask;
71    AtomListPtr *newHashTable;
72    unsigned newRehash;
73
74    if (hashSize == 0)
75        newHashSize = 1024;
76    else
77        newHashSize = hashSize * 2;
78    newHashTable = calloc(newHashSize, sizeof(AtomListPtr));
79    if (!newHashTable) {
80        fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
81                " newHashTable (%ld)\n",
82                newHashSize * (unsigned long) sizeof(AtomListPtr));
83        return FALSE;
84    }
85    newHashMask = newHashSize - 1;
86    newRehash = (newHashMask - 2);
87    for (int i = 0; i < hashSize; i++) {
88        if (hashTable[i]) {
89            unsigned h = (hashTable[i]->hash) & newHashMask;
90            if (newHashTable[h]) {
91                unsigned r = hashTable[i]->hash % newRehash | 1;
92                do {
93                    h += r;
94                    if (h >= newHashSize)
95                        h -= newHashSize;
96                } while (newHashTable[h]);
97            }
98            newHashTable[h] = hashTable[i];
99        }
100    }
101    free(hashTable);
102    hashTable = newHashTable;
103    hashSize = newHashSize;
104    hashMask = newHashMask;
105    rehash = newRehash;
106    return TRUE;
107}
108
109static int
110ResizeReverseMap(void)
111{
112    AtomListPtr *newMap;
113    size_t newMapSize;
114
115    if (reverseMapSize == 0)
116        newMapSize = 1000;
117    else
118        newMapSize = reverseMapSize * 2;
119    newMap = realloc(reverseMap, newMapSize * sizeof(AtomListPtr));
120    if (newMap == NULL) {
121        fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
122                " reverseMap (%ld)\n",
123                newMapSize * (unsigned long) sizeof(AtomListPtr));
124        return FALSE;
125    }
126    reverseMap = newMap;
127    reverseMapSize = newMapSize;
128    return TRUE;
129}
130
131static int
132NameEqual(const char *a, const char *b, int l)
133{
134    while (l--)
135        if (*a++ != *b++)
136            return FALSE;
137    return TRUE;
138}
139
140Atom
141MakeAtom(const char *string, unsigned len, int makeit)
142{
143    AtomListPtr a;
144    unsigned hash;
145    unsigned h = 0;
146    unsigned r;
147
148    hash = Hash(string, len);
149    if (hashTable) {
150        h = hash & hashMask;
151        if (hashTable[h]) {
152            if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
153                NameEqual(hashTable[h]->name, string, len)) {
154                return hashTable[h]->atom;
155            }
156            r = (hash % rehash) | 1;
157            for (;;) {
158                h += r;
159                if (h >= hashSize)
160                    h -= hashSize;
161                if (!hashTable[h])
162                    break;
163                if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
164                    NameEqual(hashTable[h]->name, string, len)) {
165                    return hashTable[h]->atom;
166                }
167            }
168        }
169    }
170    if (!makeit)
171        return None;
172    a = malloc(sizeof(AtomListRec) + len + 1);
173    if (a == NULL) {
174        fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
175                " (%ld)\n", (unsigned long) sizeof(AtomListRec) + len + 1);
176        return None;
177    }
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        ResizeHashTable();
186        h = hash & hashMask;
187        if (hashTable[h]) {
188            r = (hash % rehash) | 1;
189            do {
190                h += r;
191                if (h >= hashSize)
192                    h -= hashSize;
193            } while (hashTable[h]);
194        }
195    }
196    hashTable[h] = a;
197    hashUsed++;
198    if (reverseMapSize <= a->atom) {
199        if (!ResizeReverseMap())
200            return None;
201    }
202    reverseMap[a->atom] = a;
203    return a->atom;
204}
205
206char *
207NameForAtom(Atom atom)
208{
209    if (atom != None && atom <= lastAtom)
210        return reverseMap[atom]->name;
211    return NULL;
212}
213