1 2 /*********************************************************** 3 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard, 4 5 All Rights Reserved 6 7 Permission to use, copy, modify, and distribute this software and its 8 documentation for any purpose and without fee is hereby granted, 9 provided that the above copyright notice appear in all copies and that 10 both that copyright notice and this permission notice appear in 11 supporting documentation, and that the name Digital not be 12 used in advertising or publicity pertaining to distribution of the 13 software without specific, written prior permission. 14 15 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 16 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 17 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 18 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 19 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 20 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 21 SOFTWARE. 22 23 ******************************************************************/ 24 /* 25 26 Copyright 1987, 1988, 1990, 1998 The Open Group 27 28 Permission to use, copy, modify, distribute, and sell this software and its 29 documentation for any purpose is hereby granted without fee, provided that 30 the above copyright notice appear in all copies and that both that 31 copyright notice and this permission notice appear in supporting 32 documentation. 33 34 The above copyright notice and this permission notice shall be included 35 in all copies or substantial portions of the Software. 36 37 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 38 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 39 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 40 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR 41 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 42 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 43 OTHER DEALINGS IN THE SOFTWARE. 44 45 Except as contained in this notice, the name of The Open Group shall 46 not be used in advertising or otherwise to promote the sale, use or 47 other dealings in this Software without prior written authorization 48 from 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 64 typedef unsigned char Bits; 65 #endif 66 typedef unsigned long Entry; /* don't confuse with EntryRec from Xintatom.h */ 67 68 static XrmQuark nextQuark = 1; /* next available quark number */ 69 static unsigned long quarkMask = 0; 70 static Entry zero = 0; 71 static Entry *quarkTable = &zero; /* crock */ 72 static unsigned long quarkRehash; 73 static XrmString **stringTable = NULL; 74 #ifdef PERMQ 75 static Bits **permTable = NULL; 76 #endif 77 static 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)) 114 static char *neverFreeTable = NULL; 115 static int neverFreeTableSize = 0; 116 117 static 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 135 typedef struct {char a; double b;} TestType1; 136 typedef struct {char a; unsigned long b;} TestType2; 137 138 #ifdef XTHREADS 139 static char *_Xpermalloc(unsigned int length); 140 141 char *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 152 static 153 #endif /* XTHREADS */ 154 char *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 174 static Bool 175 ExpandQuarkTable(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 238 XrmQuark 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 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 s2 = NAME(q); 261 if(memcmp((char *)name, s2, len) != 0) { 262 goto nomatch; 263 } 264 s2 += len; 265 if (*s2) { 266 nomatch: 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 s1 = (char*)name; 323 memcpy(s1, s2, (size_t)len); 324 s1[len] = '\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 346 XrmQuark 347 XrmStringToQuark( 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 362 XrmQuark 363 XrmPermStringToQuark( 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 378 XrmQuark 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 391 XrmString 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 forever. 402 */ 403 SETPERM(quark); 404 #endif 405 s = NAME(quark); 406 } 407 _XUnlockMutex(_Xglobal_lock); 408 return s; 409 } 410
Indexes created Fri Aug 14 00:25:39 UTC 2026