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