Quarks.c revision 6cc2b21f 
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 = Xcalloc(newmask + 1, sizeof(Entry));
214    if (!entries)
215	return False;
216    quarkTable = entries;
217    quarkMask = newmask;
218    quarkRehash = quarkMask - 2;
219    for (oldidx = 0; oldidx <= oldmask; oldidx++) {
220	if ((entry = oldentries[oldidx])) {
221	    if (entry & LARGEQUARK)
222		q = entry & (LARGEQUARK-1);
223	    else
224		q = (entry >> QUARKSHIFT) & QUARKMASK;
225	    for (sig = 0, s = NAME(q); (c = *s++); )
226		sig = (sig << 1) + c;
227	    newidx = HASH(sig);
228	    if (entries[newidx]) {
229		rehash = REHASHVAL(sig);
230		do {
231		    newidx = REHASH(newidx, rehash);
232		} while (entries[newidx]);
233	    }
234	    entries[newidx] = entry;
235	}
236    }
237    if (oldmask)
238	Xfree((char *)oldentries);
239    return True;
240}
241
242XrmQuark
243_XrmInternalStringToQuark(
244    register _Xconst char *name, register int len, register Signature sig,
245    Bool permstring)
246{
247    register XrmQuark q;
248    register Entry entry;
249    register int idx, rehash;
250    register int i;
251    register char *s1, *s2;
252    char *new;
253
254    rehash = 0;
255    idx = HASH(sig);
256    _XLockMutex(_Xglobal_lock);
257    while ((entry = quarkTable[idx])) {
258	if (entry & LARGEQUARK)
259	    q = entry & (LARGEQUARK-1);
260	else {
261	    if ((entry - sig) & XSIGMASK)
262		goto nomatch;
263	    q = (entry >> QUARKSHIFT) & QUARKMASK;
264	}
265	for (i = len, s1 = (char *)name, s2 = NAME(q); --i >= 0; ) {
266	    if (*s1++ != *s2++)
267		goto nomatch;
268	}
269	if (*s2) {
270nomatch:    if (!rehash)
271		rehash = REHASHVAL(sig);
272	    idx = REHASH(idx, rehash);
273	    continue;
274	}
275#ifdef PERMQ
276	if (permstring && !ISPERM(q)) {
277	    Xfree(NAME(q));
278	    NAME(q) = (char *)name;
279	    SETPERM(q);
280	}
281#endif
282	_XUnlockMutex(_Xglobal_lock);
283	return q;
284    }
285    if (nextUniq == nextQuark)
286	goto fail;
287    if ((nextQuark + (nextQuark >> 2)) > quarkMask) {
288	if (!ExpandQuarkTable())
289	    goto fail;
290	_XUnlockMutex(_Xglobal_lock);
291	return _XrmInternalStringToQuark(name, len, sig, permstring);
292    }
293    q = nextQuark;
294    if (!(q & QUANTUMMASK)) {
295	if (!(q & CHUNKMASK)) {
296	    if (!(new = Xrealloc((char *)stringTable,
297				 sizeof(XrmString *) *
298				 ((q >> QUANTUMSHIFT) + CHUNKPER))))
299		goto fail;
300	    stringTable = (XrmString **)new;
301#ifdef PERMQ
302	    if (!(new = Xrealloc((char *)permTable,
303				 sizeof(Bits *) *
304				 ((q >> QUANTUMSHIFT) + CHUNKPER))))
305		goto fail;
306	    permTable = (Bits **)new;
307#endif
308	}
309	new = Xpermalloc(QUANTSIZE);
310	if (!new)
311	    goto fail;
312	stringTable[q >> QUANTUMSHIFT] = (XrmString *)new;
313#ifdef PERMQ
314	permTable[q >> QUANTUMSHIFT] = (Bits *)(new + STRQUANTSIZE);
315#endif
316    }
317    if (!permstring) {
318	s2 = (char *)name;
319#ifdef PERMQ
320	name = Xmalloc(len+1);
321#else
322	name = permalloc(len+1);
323#endif
324	if (!name)
325	    goto fail;
326	for (i = len, s1 = (char *)name; --i >= 0; )
327	    *s1++ = *s2++;
328	*s1++ = '\0';
329#ifdef PERMQ
330	CLEARPERM(q);
331    }
332    else {
333	SETPERM(q);
334#endif
335    }
336    NAME(q) = (char *)name;
337    if (q <= QUARKMASK)
338	entry = (q << QUARKSHIFT) | (sig & XSIGMASK);
339    else
340	entry = q | LARGEQUARK;
341    quarkTable[idx] = entry;
342    nextQuark++;
343    _XUnlockMutex(_Xglobal_lock);
344    return q;
345 fail:
346    _XUnlockMutex(_Xglobal_lock);
347    return NULLQUARK;
348}
349
350XrmQuark
351XrmStringToQuark(
352    _Xconst char *name)
353{
354    register char c, *tname;
355    register Signature sig = 0;
356
357    if (!name)
358	return (NULLQUARK);
359
360    for (tname = (char *)name; (c = *tname++); )
361	sig = (sig << 1) + c;
362
363    return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, False);
364}
365
366XrmQuark
367XrmPermStringToQuark(
368    _Xconst char *name)
369{
370    register char c, *tname;
371    register Signature sig = 0;
372
373    if (!name)
374	return (NULLQUARK);
375
376    for (tname = (char *)name; (c = *tname++); )
377	sig = (sig << 1) + c;
378
379    return _XrmInternalStringToQuark(name, tname-(char *)name-1, sig, True);
380}
381
382XrmQuark XrmUniqueQuark(void)
383{
384    XrmQuark q;
385
386    _XLockMutex(_Xglobal_lock);
387    if (nextUniq == nextQuark)
388	q = NULLQUARK;
389    else
390	q = nextUniq--;
391    _XUnlockMutex(_Xglobal_lock);
392    return q;
393}
394
395XrmString XrmQuarkToString(register XrmQuark quark)
396{
397    XrmString s;
398
399    _XLockMutex(_Xglobal_lock);
400    if (quark <= 0 || quark >= nextQuark)
401    	s = NULLSTRING;
402    else {
403#ifdef PERMQ
404	/* We have to mark the quark as permanent, since the caller might hold
405	 * onto the string pointer forver.
406	 */
407	SETPERM(quark);
408#endif
409	s = NAME(quark);
410    }
411    _XUnlockMutex(_Xglobal_lock);
412    return s;
413}
414