Quarks.c revision 258a0ebe 
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#include "reallocarray.h"
59
60/* Not cost effective, at least for vanilla MIT clients */
61/* #define PERMQ */
62
63#ifdef PERMQ
64typedef unsigned char Bits;
65#endif
66typedef unsigned long Entry; /* dont confuse with EntryRec from Xintatom.h */
67
68static XrmQuark nextQuark = 1;	/* next available quark number */
69static unsigned long quarkMask = 0;
70static Entry zero = 0;
71static Entry *quarkTable = &zero; /* crock */
72static unsigned long quarkRehash;
73static XrmString **stringTable = NULL;
74#ifdef PERMQ
75static Bits **permTable = NULL;
76#endif
77static 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))
114static char *neverFreeTable = NULL;
115static int  neverFreeTableSize = 0;
116
117static 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
135typedef struct {char a; double b;} TestType1;
136typedef struct {char a; unsigned long b;} TestType2;
137
138#ifdef XTHREADS
139static char *_Xpermalloc(unsigned int length);
140
141char *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
152static
153#endif /* XTHREADS */
154char *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
174static Bool
175ExpandQuarkTable(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
238XrmQuark
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 int i;
247    register char *s1, *s2;
248    char *new;
249
250    rehash = 0;
251    idx = HASH(sig);
252    _XLockMutex(_Xglobal_lock);
253    while ((entry = quarkTable[idx])) {
254	if (entry & LARGEQUARK)
255	    q = entry & (LARGEQUARK-1);
256	else {
257	    if ((entry - sig) & XSIGMASK)
258		goto nomatch;
259	    q = (entry >> QUARKSHIFT) & QUARKMASK;
260	}
261	for (i = len, s1 = (char *)name, s2 = NAME(q); --i >= 0; ) {
262	    if (*s1++ != *s2++)
263		goto nomatch;
264	}
265	if (*s2) {
266nomatch:    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	for (i = len, s1 = (char *)name; --i >= 0; )
323	    *s1++ = *s2++;
324	*s1++ = '\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
346XrmQuark
347XrmStringToQuark(
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
362XrmQuark
363XrmPermStringToQuark(
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
378XrmQuark 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
391XrmString 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 forver.
402	 */
403	SETPERM(quark);
404#endif
405	s = NAME(quark);
406    }
407    _XUnlockMutex(_Xglobal_lock);
408    return s;
409}
410