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