Quarks.c revision eb411b4b 
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
134typedef struct {char a; double b;} TestType1;
135typedef struct {char a; unsigned long b;} TestType2;
136
137#ifdef XTHREADS
138static char *_Xpermalloc(unsigned int length);
139
140char *Xpermalloc(unsigned int length)
141{
142    char *p;
143
144    _XLockMutex(_Xglobal_lock);
145    p = _Xpermalloc(length);
146    _XUnlockMutex(_Xglobal_lock);
147    return p;
148}
149#define Xpermalloc _Xpermalloc
150
151static
152#endif /* XTHREADS */
153char *Xpermalloc(unsigned int length)
154{
155    int i;
156
157    if (neverFreeTableSize && length < NEVERFREETABLESIZE) {
158	if ((sizeof(TestType1) !=
159	     (sizeof(TestType2) - sizeof(unsigned long) + sizeof(double))) &&
160	    !(length & (DALIGN-1)) &&
161	    ((i = (NEVERFREETABLESIZE - neverFreeTableSize) & (DALIGN-1)))) {
162	    neverFreeTableSize -= DALIGN - i;
163	    neverFreeTable += DALIGN - i;
164	} else
165	    if ((i = (NEVERFREETABLESIZE - neverFreeTableSize) & (WALIGN-1))) {
166		neverFreeTableSize -= WALIGN - i;
167		neverFreeTable += WALIGN - i;
168	    }
169    }
170    return permalloc(length);
171}
172
173static Bool
174ExpandQuarkTable(void)
175{
176    unsigned long oldmask, newmask;
177    register char c, *s;
178    register Entry *oldentries, *entries;
179    register Entry entry;
180    register int oldidx, newidx, rehash;
181    Signature sig;
182    XrmQuark q;
183
184    oldentries = quarkTable;
185    if ((oldmask = quarkMask))
186	newmask = (oldmask << 1) + 1;
187    else {
188	if (!stringTable) {
189	    stringTable = Xmalloc(sizeof(XrmString *) * CHUNKPER);
190	    if (!stringTable)
191		return False;
192	    stringTable[0] = (XrmString *)NULL;
193	}
194#ifdef PERMQ
195	if (!permTable)
196	    permTable = Xmalloc(sizeof(Bits *) * CHUNKPER);
197	if (!permTable)
198	    return False;
199#endif
200	stringTable[0] = (XrmString *)Xpermalloc(QUANTSIZE);
201	if (!stringTable[0])
202	    return False;
203#ifdef PERMQ
204	permTable[0] = (Bits *)((char *)stringTable[0] + STRQUANTSIZE);
205#endif
206	newmask = 0x1ff;
207    }
208    entries = Xcalloc(newmask + 1, sizeof(Entry));
209    if (!entries)
210	return False;
211    quarkTable = entries;
212    quarkMask = newmask;
213    quarkRehash = quarkMask - 2;
214    for (oldidx = 0; oldidx <= oldmask; oldidx++) {
215	if ((entry = oldentries[oldidx])) {
216	    if (entry & LARGEQUARK)
217		q = entry & (LARGEQUARK-1);
218	    else
219		q = (entry >> QUARKSHIFT) & QUARKMASK;
220	    for (sig = 0, s = NAME(q); (c = *s++); )
221		sig = (sig << 1) + c;
222	    newidx = HASH(sig);
223	    if (entries[newidx]) {
224		rehash = REHASHVAL(sig);
225		do {
226		    newidx = REHASH(newidx, rehash);
227		} while (entries[newidx]);
228	    }
229	    entries[newidx] = entry;
230	}
231    }
232    if (oldmask)
233	Xfree((char *)oldentries);
234    return True;
235}
236
237XrmQuark
238_XrmInternalStringToQuark(
239    register _Xconst char *name, register int len, register Signature sig,
240    Bool permstring)
241{
242    register XrmQuark q;
243    register Entry entry;
244    register int idx, rehash;
245    register int i;
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	for (i = len, s1 = (char *)name, s2 = NAME(q); --i >= 0; ) {
261	    if (*s1++ != *s2++)
262		goto nomatch;
263	}
264	if (*s2) {
265nomatch:    if (!rehash)
266		rehash = REHASHVAL(sig);
267	    idx = REHASH(idx, rehash);
268	    continue;
269	}
270#ifdef PERMQ
271	if (permstring && !ISPERM(q)) {
272	    Xfree(NAME(q));
273	    NAME(q) = (char *)name;
274	    SETPERM(q);
275	}
276#endif
277	_XUnlockMutex(_Xglobal_lock);
278	return q;
279    }
280    if (nextUniq == nextQuark)
281	goto fail;
282    if ((nextQuark + (nextQuark >> 2)) > quarkMask) {
283	if (!ExpandQuarkTable())
284	    goto fail;
285	_XUnlockMutex(_Xglobal_lock);
286	return _XrmInternalStringToQuark(name, len, sig, permstring);
287    }
288    q = nextQuark;
289    if (!(q & QUANTUMMASK)) {
290	if (!(q & CHUNKMASK)) {
291	    if (!(new = Xrealloc(stringTable,
292				 sizeof(XrmString *) *
293				 ((q >> QUANTUMSHIFT) + CHUNKPER))))
294		goto fail;
295	    stringTable = (XrmString **)new;
296#ifdef PERMQ
297	    if (!(new = Xrealloc(permTable,
298				 sizeof(Bits *) *
299				 ((q >> QUANTUMSHIFT) + CHUNKPER))))
300		goto fail;
301	    permTable = (Bits **)new;
302#endif
303	}
304	new = Xpermalloc(QUANTSIZE);
305	if (!new)
306	    goto fail;
307	stringTable[q >> QUANTUMSHIFT] = (XrmString *)new;
308#ifdef PERMQ
309	permTable[q >> QUANTUMSHIFT] = (Bits *)(new + STRQUANTSIZE);
310#endif
311    }
312    if (!permstring) {
313	s2 = (char *)name;
314#ifdef PERMQ
315	name = Xmalloc(len+1);
316#else
317	name = permalloc(len+1);
318#endif
319	if (!name)
320	    goto fail;
321	for (i = len, s1 = (char *)name; --i >= 0; )
322	    *s1++ = *s2++;
323	*s1++ = '\0';
324#ifdef PERMQ
325	CLEARPERM(q);
326    }
327    else {
328	SETPERM(q);
329#endif
330    }
331    NAME(q) = (char *)name;
332    if (q <= QUARKMASK)
333	entry = (q << QUARKSHIFT) | (sig & XSIGMASK);
334    else
335	entry = q | LARGEQUARK;
336    quarkTable[idx] = entry;
337    nextQuark++;
338    _XUnlockMutex(_Xglobal_lock);
339    return q;
340 fail:
341    _XUnlockMutex(_Xglobal_lock);
342    return NULLQUARK;
343}
344
345XrmQuark
346XrmStringToQuark(
347    _Xconst char *name)
348{
349    register char c, *tname;
350    register Signature sig = 0;
351
352    if (!name)
353	return (NULLQUARK);
354
355    for (tname = (char *)name; (c = *tname++); )
356	sig = (sig << 1) + c;
357
358    return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, False);
359}
360
361XrmQuark
362XrmPermStringToQuark(
363    _Xconst char *name)
364{
365    register char c, *tname;
366    register Signature sig = 0;
367
368    if (!name)
369	return (NULLQUARK);
370
371    for (tname = (char *)name; (c = *tname++); )
372	sig = (sig << 1) + c;
373
374    return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, True);
375}
376
377XrmQuark XrmUniqueQuark(void)
378{
379    XrmQuark q;
380
381    _XLockMutex(_Xglobal_lock);
382    if (nextUniq == nextQuark)
383	q = NULLQUARK;
384    else
385	q = nextUniq--;
386    _XUnlockMutex(_Xglobal_lock);
387    return q;
388}
389
390XrmString XrmQuarkToString(register XrmQuark quark)
391{
392    XrmString s;
393
394    _XLockMutex(_Xglobal_lock);
395    if (quark <= 0 || quark >= nextQuark)
396    	s = NULLSTRING;
397    else {
398#ifdef PERMQ
399	/* We have to mark the quark as permanent, since the caller might hold
400	 * onto the string pointer forver.
401	 */
402	SETPERM(quark);
403#endif
404	s = NAME(quark);
405    }
406    _XUnlockMutex(_Xglobal_lock);
407    return s;
408}
409