1
2 /***********************************************************
3 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
4
5 All Rights Reserved
6
7 Permission to use, copy, modify, and distribute this software and its
8 documentation for any purpose and without fee is hereby granted,
9 provided that the above copyright notice appear in all copies and that
10 both that copyright notice and this permission notice appear in
11 supporting documentation, and that the name Digital not be
12 used in advertising or publicity pertaining to distribution of the
13 software without specific, written prior permission.
14
15 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
16 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
17 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
18 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
20 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
21 SOFTWARE.
22
23 ******************************************************************/
24 /*
25
26 Copyright 1987, 1988, 1990, 1998 The Open Group
27
28 Permission to use, copy, modify, distribute, and sell this software and its
29 documentation for any purpose is hereby granted without fee, provided that
30 the above copyright notice appear in all copies and that both that
31 copyright notice and this permission notice appear in supporting
32 documentation.
33
34 The above copyright notice and this permission notice shall be included
35 in all copies or substantial portions of the Software.
36
37 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
38 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
39 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
40 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
41 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
42 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
43 OTHER DEALINGS IN THE SOFTWARE.
44
45 Except as contained in this notice, the name of The Open Group shall
46 not be used in advertising or otherwise to promote the sale, use or
47 other dealings in this Software without prior written authorization
48 from The Open Group.
49
50 */
51
52 #ifdef HAVE_CONFIG_H
53 #include <config.h>
54 #endif
55 #include "Xlibint.h"
56 #include <X11/Xresource.h>
57 #include "Xresinternal.h"
58 #include "reallocarray.h"
59
60 /* Not cost effective, at least for vanilla MIT clients */
61 /* #define PERMQ */
62
63 #ifdef PERMQ
64 typedef unsigned char Bits;
65 #endif
66 typedef unsigned long Entry; /* don't confuse with EntryRec from Xintatom.h */
67
68 static XrmQuark nextQuark = 1; /* next available quark number */
69 static unsigned long quarkMask = 0;
70 static Entry zero = 0;
71 static Entry *quarkTable = &zero; /* crock */
72 static unsigned long quarkRehash;
73 static XrmString **stringTable = NULL;
74 #ifdef PERMQ
75 static Bits **permTable = NULL;
76 #endif
77 static XrmQuark nextUniq = -1; /* next quark from XrmUniqueQuark */
78
79 #define QUANTUMSHIFT 8
80 #define QUANTUMMASK ((1 << QUANTUMSHIFT) - 1)
81 #define CHUNKPER 8
82 #define CHUNKMASK ((CHUNKPER << QUANTUMSHIFT) - 1)
83
84 #define LARGEQUARK ((Entry)0x80000000L)
85 #define QUARKSHIFT 18
86 #define QUARKMASK ((LARGEQUARK - 1) >> QUARKSHIFT)
87 #define XSIGMASK ((1L << QUARKSHIFT) - 1)
88
89 #define STRQUANTSIZE (sizeof(XrmString) * (QUANTUMMASK + 1))
90 #ifdef PERMQ
91 #define QUANTSIZE (STRQUANTSIZE + \
92 (sizeof(Bits) * ((QUANTUMMASK + 1) >> 3))
93 #else
94 #define QUANTSIZE STRQUANTSIZE
95 #endif
96
97 #define HASH(sig) ((sig) & quarkMask)
98 #define REHASHVAL(sig) ((((sig) % quarkRehash) + 2) | 1)
99 #define REHASH(idx,rehash) ((idx + rehash) & quarkMask)
100 #define NAME(q) stringTable[(q) >> QUANTUMSHIFT][(q) & QUANTUMMASK]
101 #ifdef PERMQ
102 #define BYTEREF(q) permTable[(q) >> QUANTUMSHIFT][((q) & QUANTUMMASK) >> 3]
103 #define ISPERM(q) (BYTEREF(q) & (1 << ((q) & 7)))
104 #define SETPERM(q) BYTEREF(q) |= (1 << ((q) & 7))
105 #define CLEARPERM(q) BYTEREF(q) &= ~(1 << ((q) & 7))
106 #endif
107
108 /* Permanent memory allocation */
109
110 #define WALIGN sizeof(unsigned long)
111 #define DALIGN sizeof(double)
112
113 #define NEVERFREETABLESIZE ((8192-12) & ~(DALIGN-1))
114 static char *neverFreeTable = NULL;
115 static int neverFreeTableSize = 0;
116
permalloc(unsigned int length)117 static char *permalloc(unsigned int length)
118 {
119 char *ret;
120
121 if (neverFreeTableSize < length) {
122 if (length >= NEVERFREETABLESIZE)
123 return Xmalloc(length);
124 if (! (ret = Xmalloc(NEVERFREETABLESIZE)))
125 return (char *) NULL;
126 neverFreeTableSize = NEVERFREETABLESIZE;
127 neverFreeTable = ret;
128 }
129 ret = neverFreeTable;
130 neverFreeTable += length;
131 neverFreeTableSize -= length;
132 return(ret);
133 }
134
135 typedef struct {char a; double b;} TestType1;
136 typedef struct {char a; unsigned long b;} TestType2;
137
138 #ifdef XTHREADS
139 static char *_Xpermalloc(unsigned int length);
140
Xpermalloc(unsigned int length)141 char *Xpermalloc(unsigned int length)
142 {
143 char *p;
144
145 _XLockMutex(_Xglobal_lock);
146 p = _Xpermalloc(length);
147 _XUnlockMutex(_Xglobal_lock);
148 return p;
149 }
150 #define Xpermalloc _Xpermalloc
151
152 static
153 #endif /* XTHREADS */
Xpermalloc(unsigned int length)154 char *Xpermalloc(unsigned int length)
155 {
156 int i;
157
158 if (neverFreeTableSize && length < NEVERFREETABLESIZE) {
159 if ((sizeof(TestType1) !=
160 (sizeof(TestType2) - sizeof(unsigned long) + sizeof(double))) &&
161 !(length & (DALIGN-1)) &&
162 ((i = (NEVERFREETABLESIZE - neverFreeTableSize) & (DALIGN-1)))) {
163 neverFreeTableSize -= DALIGN - i;
164 neverFreeTable += DALIGN - i;
165 } else
166 if ((i = (NEVERFREETABLESIZE - neverFreeTableSize) & (WALIGN-1))) {
167 neverFreeTableSize -= WALIGN - i;
168 neverFreeTable += WALIGN - i;
169 }
170 }
171 return permalloc(length);
172 }
173
174 static Bool
ExpandQuarkTable(void)175 ExpandQuarkTable(void)
176 {
177 unsigned long oldmask, newmask;
178 register char c, *s;
179 register Entry *oldentries, *entries;
180 register Entry entry;
181 register int oldidx, newidx, rehash;
182 Signature sig;
183 XrmQuark q;
184
185 oldentries = quarkTable;
186 if ((oldmask = quarkMask))
187 newmask = (oldmask << 1) + 1;
188 else {
189 if (!stringTable) {
190 stringTable = Xmalloc(sizeof(XrmString *) * CHUNKPER);
191 if (!stringTable)
192 return False;
193 stringTable[0] = (XrmString *)NULL;
194 }
195 #ifdef PERMQ
196 if (!permTable)
197 permTable = Xmalloc(sizeof(Bits *) * CHUNKPER);
198 if (!permTable)
199 return False;
200 #endif
201 stringTable[0] = (XrmString *)Xpermalloc(QUANTSIZE);
202 if (!stringTable[0])
203 return False;
204 #ifdef PERMQ
205 permTable[0] = (Bits *)((char *)stringTable[0] + STRQUANTSIZE);
206 #endif
207 newmask = 0x1ff;
208 }
209 entries = Xcalloc(newmask + 1, sizeof(Entry));
210 if (!entries)
211 return False;
212 quarkTable = entries;
213 quarkMask = newmask;
214 quarkRehash = quarkMask - 2;
215 for (oldidx = 0; oldidx <= oldmask; oldidx++) {
216 if ((entry = oldentries[oldidx])) {
217 if (entry & LARGEQUARK)
218 q = entry & (LARGEQUARK-1);
219 else
220 q = (entry >> QUARKSHIFT) & QUARKMASK;
221 for (sig = 0, s = NAME(q); (c = *s++); )
222 sig = (sig << 1) + c;
223 newidx = HASH(sig);
224 if (entries[newidx]) {
225 rehash = REHASHVAL(sig);
226 do {
227 newidx = REHASH(newidx, rehash);
228 } while (entries[newidx]);
229 }
230 entries[newidx] = entry;
231 }
232 }
233 if (oldmask)
234 Xfree(oldentries);
235 return True;
236 }
237
238 XrmQuark
_XrmInternalStringToQuark(register _Xconst char * name,register int len,register Signature sig,Bool permstring)239 _XrmInternalStringToQuark(
240 register _Xconst char *name, register int len, register Signature sig,
241 Bool permstring)
242 {
243 register XrmQuark q;
244 register Entry entry;
245 register int idx, rehash;
246 register char *s1, *s2;
247 char *new;
248
249 rehash = 0;
250 idx = HASH(sig);
251 _XLockMutex(_Xglobal_lock);
252 while ((entry = quarkTable[idx])) {
253 if (entry & LARGEQUARK)
254 q = entry & (LARGEQUARK-1);
255 else {
256 if ((entry - sig) & XSIGMASK)
257 goto nomatch;
258 q = (entry >> QUARKSHIFT) & QUARKMASK;
259 }
260 s2 = NAME(q);
261 if(memcmp((char *)name, s2, len) != 0) {
262 goto nomatch;
263 }
264 s2 += len;
265 if (*s2) {
266 nomatch: if (!rehash)
267 rehash = REHASHVAL(sig);
268 idx = REHASH(idx, rehash);
269 continue;
270 }
271 #ifdef PERMQ
272 if (permstring && !ISPERM(q)) {
273 Xfree(NAME(q));
274 NAME(q) = (char *)name;
275 SETPERM(q);
276 }
277 #endif
278 _XUnlockMutex(_Xglobal_lock);
279 return q;
280 }
281 if (nextUniq == nextQuark)
282 goto fail;
283 if ((nextQuark + (nextQuark >> 2)) > quarkMask) {
284 if (!ExpandQuarkTable())
285 goto fail;
286 _XUnlockMutex(_Xglobal_lock);
287 return _XrmInternalStringToQuark(name, len, sig, permstring);
288 }
289 q = nextQuark;
290 if (!(q & QUANTUMMASK)) {
291 if (!(q & CHUNKMASK)) {
292 if (!(new = Xreallocarray(stringTable,
293 (q >> QUANTUMSHIFT) + CHUNKPER,
294 sizeof(XrmString *))))
295 goto fail;
296 stringTable = (XrmString **)new;
297 #ifdef PERMQ
298 if (!(new = Xreallocarray(permTable,
299 (q >> QUANTUMSHIFT) + CHUNKPER,
300 sizeof(Bits *))))
301 goto fail;
302 permTable = (Bits **)new;
303 #endif
304 }
305 new = Xpermalloc(QUANTSIZE);
306 if (!new)
307 goto fail;
308 stringTable[q >> QUANTUMSHIFT] = (XrmString *)new;
309 #ifdef PERMQ
310 permTable[q >> QUANTUMSHIFT] = (Bits *)(new + STRQUANTSIZE);
311 #endif
312 }
313 if (!permstring) {
314 s2 = (char *)name;
315 #ifdef PERMQ
316 name = Xmalloc(len+1);
317 #else
318 name = permalloc(len+1);
319 #endif
320 if (!name)
321 goto fail;
322 s1 = (char*)name;
323 memcpy(s1, s2, (size_t)len);
324 s1[len] = '\0';
325 #ifdef PERMQ
326 CLEARPERM(q);
327 }
328 else {
329 SETPERM(q);
330 #endif
331 }
332 NAME(q) = (char *)name;
333 if (q <= QUARKMASK)
334 entry = (q << QUARKSHIFT) | (sig & XSIGMASK);
335 else
336 entry = q | LARGEQUARK;
337 quarkTable[idx] = entry;
338 nextQuark++;
339 _XUnlockMutex(_Xglobal_lock);
340 return q;
341 fail:
342 _XUnlockMutex(_Xglobal_lock);
343 return NULLQUARK;
344 }
345
346 XrmQuark
XrmStringToQuark(_Xconst char * name)347 XrmStringToQuark(
348 _Xconst char *name)
349 {
350 register char c, *tname;
351 register Signature sig = 0;
352
353 if (!name)
354 return (NULLQUARK);
355
356 for (tname = (char *)name; (c = *tname++); )
357 sig = (sig << 1) + c;
358
359 return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, False);
360 }
361
362 XrmQuark
XrmPermStringToQuark(_Xconst char * name)363 XrmPermStringToQuark(
364 _Xconst char *name)
365 {
366 register char c, *tname;
367 register Signature sig = 0;
368
369 if (!name)
370 return (NULLQUARK);
371
372 for (tname = (char *)name; (c = *tname++); )
373 sig = (sig << 1) + c;
374
375 return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, True);
376 }
377
XrmUniqueQuark(void)378 XrmQuark XrmUniqueQuark(void)
379 {
380 XrmQuark q;
381
382 _XLockMutex(_Xglobal_lock);
383 if (nextUniq == nextQuark)
384 q = NULLQUARK;
385 else
386 q = nextUniq--;
387 _XUnlockMutex(_Xglobal_lock);
388 return q;
389 }
390
XrmQuarkToString(register XrmQuark quark)391 XrmString XrmQuarkToString(register XrmQuark quark)
392 {
393 XrmString s;
394
395 _XLockMutex(_Xglobal_lock);
396 if (quark <= 0 || quark >= nextQuark)
397 s = NULLSTRING;
398 else {
399 #ifdef PERMQ
400 /* We have to mark the quark as permanent, since the caller might hold
401 * onto the string pointer forever.
402 */
403 SETPERM(quark);
404 #endif
405 s = NAME(quark);
406 }
407 _XUnlockMutex(_Xglobal_lock);
408 return s;
409 }
410