2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these libraries and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* Quarks.c 1.1 - Fujitsu source for CDEnext 95/11/06 20:31:17 */
24 /* $XConsortium: _falQuarks.c /main/2 1996/09/09 13:20:21 rswiston $ */
26 /***********************************************************
27 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
31 Permission to use, copy, modify, and distribute this software and its
32 documentation for any purpose and without fee is hereby granted,
33 provided that the above copyright notice appear in all copies and that
34 both that copyright notice and this permission notice appear in
35 supporting documentation, and that the name Digital not be
36 used in advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
47 ******************************************************************/
50 Copyright (c) 1987, 1988, 1990 X Consortium
52 Permission is hereby granted, free of charge, to any person obtaining
53 a copy of this software and associated documentation files (the
54 "Software"), to deal in the Software without restriction, including
55 without limitation the rights to use, copy, modify, merge, publish,
56 distribute, sublicense, and/or sell copies of the Software, and to
57 permit persons to whom the Software is furnished to do so, subject to
58 the following conditions:
60 The above copyright notice and this permission notice shall be included
61 in all copies or substantial portions of the Software.
63 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
64 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
65 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
66 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
67 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
68 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
69 OTHER DEALINGS IN THE SOFTWARE.
71 Except as contained in this notice, the name of the X Consortium shall
72 not be used in advertising or otherwise to promote the sale, use or
73 other dealings in this Software without prior written authorization
74 from the X Consortium.
78 #include "_fallibint.h"
79 #include <X11/Xresource.h>
81 /* Not cost effective, at least for vanilla MIT clients */
84 typedef unsigned long Signature;
85 typedef unsigned long Entry;
87 typedef unsigned char Bits;
90 static XrmQuark nextQuark = 1; /* next available quark number */
91 static unsigned long quarkMask = 0;
92 static Entry zero = 0;
93 static Entry *quarkTable = &zero; /* crock */
94 static unsigned long quarkRehash;
95 static XrmString **stringTable = NULL;
97 static Bits **permTable = NULL;
99 static XrmQuark nextUniq = -1; /* next quark from falrmUniqueQuark */
101 #define QUANTUMSHIFT 8
102 #define QUANTUMMASK ((1 << QUANTUMSHIFT) - 1)
104 #define CHUNKMASK ((CHUNKPER << QUANTUMSHIFT) - 1)
106 #define LARGEQUARK ((Entry)0x80000000L)
107 #define QUARKSHIFT 18
108 #define QUARKMASK ((LARGEQUARK - 1) >> QUARKSHIFT)
109 #define XSIGMASK ((1L << QUARKSHIFT) - 1)
111 #define STRQUANTSIZE (sizeof(XrmString) * (QUANTUMMASK + 1))
113 #define QUANTSIZE (STRQUANTSIZE + \
114 (sizeof(Bits) * ((QUANTUMMASK + 1) >> 3))
116 #define QUANTSIZE STRQUANTSIZE
119 #define HASH(sig) ((sig) & quarkMask)
120 #define REHASHVAL(sig) ((((sig) % quarkRehash) + 2) | 1)
121 #define REHASH(idx,rehash) ((idx + rehash) & quarkMask)
122 #define NAME(q) stringTable[(q) >> QUANTUMSHIFT][(q) & QUANTUMMASK]
124 #define BYTEREF(q) permTable[(q) >> QUANTUMSHIFT][((q) & QUANTUMMASK) >> 3]
125 #define ISPERM(q) (BYTEREF(q) & (1 << ((q) & 7)))
126 #define SETPERM(q) BYTEREF(q) |= (1 << ((q) & 7))
127 #define CLEARPERM(q) BYTEREF(q) &= ~(1 << ((q) & 7))
130 /* Permanent memory allocation */
132 #define WALIGN sizeof(unsigned long)
133 #define DALIGN sizeof(double)
135 #define NEVERFREETABLESIZE ((8192-12) & ~(DALIGN-1))
136 static char *neverFreeTable = NULL;
137 static int neverFreeTableSize = 0;
139 static char *permalloc(length)
140 register unsigned int length;
144 if (neverFreeTableSize < length) {
145 if (length >= NEVERFREETABLESIZE)
146 return Xmalloc(length);
147 if (! (ret = Xmalloc(NEVERFREETABLESIZE)))
148 return (char *) NULL;
149 neverFreeTableSize = NEVERFREETABLESIZE;
150 neverFreeTable = ret;
152 ret = neverFreeTable;
153 neverFreeTable += length;
154 neverFreeTableSize -= length;
159 typedef struct {char a; double b;} TestType1;
160 typedef struct {char a; unsigned long b;} TestType2;
164 static char *_falpermalloc();
166 char *falpermalloc(length)
171 _XLockMutex(_Xglobal_lock);
172 p = _falpermalloc(length);
173 _XUnlockMutex(_Xglobal_lock);
176 #define falpermalloc _falpermalloc
179 #endif /* XTHREADS */
180 char *falpermalloc(length)
185 if (neverFreeTableSize && length < NEVERFREETABLESIZE) {
187 if ((sizeof(TestType1) !=
188 (sizeof(TestType2) - sizeof(unsigned long) + sizeof(double))) &&
189 !(length & (DALIGN-1)) &&
190 (i = (NEVERFREETABLESIZE - neverFreeTableSize) & (DALIGN-1))) {
191 neverFreeTableSize -= DALIGN - i;
192 neverFreeTable += DALIGN - i;
195 if (i = (NEVERFREETABLESIZE - neverFreeTableSize) & (WALIGN-1)) {
196 neverFreeTableSize -= WALIGN - i;
197 neverFreeTable += WALIGN - i;
200 return permalloc(length);
206 unsigned long oldmask, newmask;
208 register Entry *oldentries, *entries;
209 register Entry entry;
210 register int oldidx, newidx, rehash;
214 oldentries = quarkTable;
215 if (oldmask = quarkMask)
216 newmask = (oldmask << 1) + 1;
219 stringTable = (XrmString **)Xmalloc(sizeof(XrmString *) *
223 stringTable[0] = (XrmString *)NULL;
227 permTable = (Bits **)Xmalloc(sizeof(Bits *) * CHUNKPER);
231 stringTable[0] = (XrmString *)falpermalloc(QUANTSIZE);
235 permTable[0] = (Bits *)((char *)stringTable[0] + STRQUANTSIZE);
239 entries = (Entry *)Xmalloc(sizeof(Entry) * (newmask + 1));
242 bzero((char *)entries, sizeof(Entry) * (newmask + 1));
243 quarkTable = entries;
245 quarkRehash = quarkMask - 2;
246 for (oldidx = 0; oldidx <= oldmask; oldidx++) {
247 if (entry = oldentries[oldidx]) {
248 if (entry & LARGEQUARK)
249 q = entry & (LARGEQUARK-1);
251 q = (entry >> QUARKSHIFT) & QUARKMASK;
252 for (sig = 0, s = NAME(q); c = *s++; )
253 sig = (sig << 1) + c;
255 if (entries[newidx]) {
256 rehash = REHASHVAL(sig);
258 newidx = REHASH(newidx, rehash);
259 } while (entries[newidx]);
261 entries[newidx] = entry;
265 Xfree((char *)oldentries);
269 #if NeedFunctionPrototypes
270 XrmQuark _falrmInternalStringToQuark(
271 register _Xconst char *name, register int len, register Signature sig,
274 XrmQuark _falrmInternalStringToQuark(name, len, sig, permstring)
275 register XrmString name;
277 register Signature sig;
282 register Entry entry;
283 register int idx, rehash;
285 register char *s1, *s2;
290 _XLockMutex(_Xglobal_lock);
291 while (entry = quarkTable[idx]) {
292 if (entry & LARGEQUARK)
293 q = entry & (LARGEQUARK-1);
295 if ((entry - sig) & XSIGMASK)
297 q = (entry >> QUARKSHIFT) & QUARKMASK;
299 for (i = len, s1 = (char *)name, s2 = NAME(q); --i >= 0; ) {
304 nomatch: if (!rehash)
305 rehash = REHASHVAL(sig);
306 idx = REHASH(idx, rehash);
310 if (permstring && !ISPERM(q)) {
312 NAME(q) = (char *)name;
316 _XUnlockMutex(_Xglobal_lock);
319 if (nextUniq == nextQuark)
321 if ((nextQuark + (nextQuark >> 2)) > quarkMask) {
322 if (!ExpandQuarkTable())
324 _XUnlockMutex(_Xglobal_lock);
325 return _falrmInternalStringToQuark(name, len, sig, permstring);
328 if (!(q & QUANTUMMASK)) {
329 if (!(q & CHUNKMASK)) {
330 if (!(new = Xrealloc((char *)stringTable,
331 sizeof(XrmString *) *
332 ((q >> QUANTUMSHIFT) + CHUNKPER))))
334 stringTable = (XrmString **)new;
336 if (!(new = Xrealloc((char *)permTable,
338 ((q >> QUANTUMSHIFT) + CHUNKPER))))
340 permTable = (Bits **)new;
343 new = falpermalloc(QUANTSIZE);
346 stringTable[q >> QUANTUMSHIFT] = (XrmString *)new;
348 permTable[q >> QUANTUMSHIFT] = (Bits *)(new + STRQUANTSIZE);
354 name = Xmalloc(len+1);
356 name = permalloc(len+1);
360 for (i = len, s1 = (char *)name; --i >= 0; )
370 NAME(q) = (char *)name;
372 entry = (q << QUARKSHIFT) | (sig & XSIGMASK);
374 entry = q | LARGEQUARK;
375 quarkTable[idx] = entry;
377 _XUnlockMutex(_Xglobal_lock);
380 _XUnlockMutex(_Xglobal_lock);
384 #if NeedFunctionPrototypes
385 XrmQuark falrmStringToQuark(
388 XrmQuark falrmStringToQuark(name)
392 register char c, *tname;
393 register Signature sig = 0;
398 for (tname = (char *)name; c = *tname++; )
399 sig = (sig << 1) + c;
401 return _falrmInternalStringToQuark(name, tname-(char *)name-1, sig, False);
404 #if NeedFunctionPrototypes
405 XrmQuark falrmPermStringToQuark(
408 XrmQuark falrmPermStringToQuark(name)
412 register char c, *tname;
413 register Signature sig = 0;
418 for (tname = (char *)name; c = *tname++; )
419 sig = (sig << 1) + c;
421 return _falrmInternalStringToQuark(name, tname-(char *)name-1, sig, True);
424 XrmQuark falrmUniqueQuark()
428 _XLockMutex(_Xglobal_lock);
429 if (nextUniq == nextQuark)
433 _XUnlockMutex(_Xglobal_lock);
437 XrmString falrmQuarkToString(quark)
438 register XrmQuark quark;
442 _XLockMutex(_Xglobal_lock);
443 if (quark <= 0 || quark >= nextQuark)
447 /* We have to mark the quark as permanent, since the caller might hold
448 * onto the string pointer forver.
454 _XUnlockMutex(_Xglobal_lock);