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 "libxfontint.h"
37#include "src/util/replace.h"
38#include <X11/fonts/fontmisc.h>
39
40typedef struct _AtomList {
41    char *name;
42    int len;
43    int hash;
44    Atom atom;
45} AtomListRec, *AtomListPtr;
46
47static AtomListPtr *hashTable;
48
49static unsigned hashSize, hashUsed;
50static unsigned hashMask;
51static unsigned rehash;
52
53static AtomListPtr *reverseMap;
54static int reverseMapSize;
55static Atom lastAtom;
56
57static unsigned
58Hash(const char *string, unsigned len)
59{
60    unsigned h = 0;
61
62    while (len--)
63        h = (h << 3) ^ *string++;
64
65    return h;
66}
67
68static int
69ResizeHashTable(void)
70{
71    unsigned newHashSize;
72    unsigned newHashMask;
73    AtomListPtr *newHashTable;
74    unsigned i;
75    unsigned h;
76    unsigned newRehash;
77    unsigned r;
78
79    if (hashSize == 0)
80        newHashSize = 1024;
81    else
82        newHashSize = hashSize * 2;
83    newHashTable = calloc(newHashSize, sizeof(AtomListPtr));
84    if (!newHashTable) {
85        fprintf(stderr, "ResizeHashTable(): Error: Couldn't allocate"
86                " newHashTable (%ld)\n",
87                newHashSize * (unsigned long) sizeof(AtomListPtr));
88        return FALSE;
89    }
90    newHashMask = newHashSize - 1;
91    newRehash = (newHashMask - 2);
92    for (i = 0; i < hashSize; i++) {
93        if (hashTable[i]) {
94            h = (hashTable[i]->hash) & newHashMask;
95            if (newHashTable[h]) {
96                r = hashTable[i]->hash % newRehash | 1;
97                do {
98                    h += r;
99                    if (h >= newHashSize)
100                        h -= newHashSize;
101                } while (newHashTable[h]);
102            }
103            newHashTable[h] = hashTable[i];
104        }
105    }
106    free(hashTable);
107    hashTable = newHashTable;
108    hashSize = newHashSize;
109    hashMask = newHashMask;
110    rehash = newRehash;
111    return TRUE;
112}
113
114static int
115ResizeReverseMap(void)
116{
117    AtomListPtr *newMap;
118    int newMapSize;
119
120    if (reverseMapSize == 0)
121        newMapSize = 1000;
122    else
123        newMapSize = reverseMapSize * 2;
124    newMap = reallocarray(reverseMap, newMapSize, sizeof(AtomListPtr));
125    if (newMap == NULL) {
126        fprintf(stderr, "ResizeReverseMap(): Error: Couldn't reallocate"
127                " reverseMap (%ld)\n",
128                newMapSize * (unsigned long) sizeof(AtomListPtr));
129        return FALSE;
130    }
131    reverseMap = newMap;
132    reverseMapSize = newMapSize;
133    return TRUE;
134}
135
136static int
137NameEqual(const char *a, const char *b, int l)
138{
139    while (l--)
140        if (*a++ != *b++)
141            return FALSE;
142    return TRUE;
143}
144
145Atom
146__libxfont_internal__MakeAtom(const char *string, unsigned len, int makeit)
147{
148    AtomListPtr a;
149    unsigned hash;
150    unsigned h = 0;
151    unsigned r;
152
153    hash = Hash(string, len);
154    if (hashTable) {
155        h = hash & hashMask;
156        if (hashTable[h]) {
157            if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
158                NameEqual(hashTable[h]->name, string, len)) {
159                return hashTable[h]->atom;
160            }
161            r = (hash % rehash) | 1;
162            for (;;) {
163                h += r;
164                if (h >= hashSize)
165                    h -= hashSize;
166                if (!hashTable[h])
167                    break;
168                if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
169                    NameEqual(hashTable[h]->name, string, len)) {
170                    return hashTable[h]->atom;
171                }
172            }
173        }
174    }
175    if (!makeit)
176        return None;
177    a = malloc(sizeof(AtomListRec) + len + 1);
178    if (a == NULL) {
179        fprintf(stderr, "MakeAtom(): Error: Couldn't allocate AtomListRec"
180                " (%ld)\n", (unsigned long) sizeof(AtomListRec) + len + 1);
181        return None;
182    }
183    a->name = (char *) (a + 1);
184    a->len = len;
185    strncpy(a->name, string, len);
186    a->name[len] = '\0';
187    a->atom = ++lastAtom;
188    a->hash = hash;
189    if (hashUsed >= hashSize / 2) {
190        if ((ResizeHashTable() == FALSE) &&
191	    ((hashTable == NULL) || (hashUsed == hashSize))) {
192	    free(a);
193	    return None;
194        }
195        h = hash & hashMask;
196        if (hashTable[h]) {
197            r = (hash % rehash) | 1;
198            do {
199                h += r;
200                if (h >= hashSize)
201                    h -= hashSize;
202            } while (hashTable[h]);
203        }
204    }
205    hashTable[h] = a;
206    hashUsed++;
207    if (reverseMapSize <= a->atom) {
208        if (!ResizeReverseMap())
209            return None;
210    }
211    reverseMap[a->atom] = a;
212    return a->atom;
213}
214
215int
216__libxfont_internal__ValidAtom(Atom atom)
217{
218    return (atom != None) && (atom <= lastAtom);
219}
220
221const char *
222__libxfont_internal__NameForAtom(Atom atom)
223{
224    if (atom != None && atom <= lastAtom)
225        return reverseMap[atom]->name;
226    return NULL;
227}
228