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