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