cde/programs/dtudcfonted/libfal/_falQuarks.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   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)
  10  * any later version.
  11  *
  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
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  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 $ */
  25
  26 /***********************************************************
  27 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
  28
  29                         All Rights Reserved
  30
  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.
  38
  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
  45 SOFTWARE.
  46
  47 ******************************************************************/
  48 /*
  49
  50 Copyright (c) 1987, 1988, 1990  X Consortium
  51
  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:
  59
  60 The above copyright notice and this permission notice shall be included
  61 in all copies or substantial portions of the Software.
  62
  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.
  70
  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.
  75
  76 */
  77
  78 #include "_fallibint.h"
  79 #include <X11/Xresource.h>
  80
  81 /* Not cost effective, at least for vanilla MIT clients */
  82 /* #define PERMQ */
  83
  84 typedef unsigned long Signature;
  85 typedef unsigned long Entry;
  86 #ifdef PERMQ
  87 typedef unsigned char Bits;
  88 #endif
  89
  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;
  96 #ifdef PERMQ
  97 static Bits **permTable = NULL;
  98 #endif
  99 static XrmQuark nextUniq = -1;  /* next quark from falrmUniqueQuark */
 100
 101 #define QUANTUMSHIFT    8
 102 #define QUANTUMMASK     ((1 << QUANTUMSHIFT) - 1)
 103 #define CHUNKPER        8
 104 #define CHUNKMASK       ((CHUNKPER << QUANTUMSHIFT) - 1)
 105
 106 #define LARGEQUARK      ((Entry)0x80000000L)
 107 #define QUARKSHIFT      18
 108 #define QUARKMASK       ((LARGEQUARK - 1) >> QUARKSHIFT)
 109 #define XSIGMASK        ((1L << QUARKSHIFT) - 1)
 110
 111 #define STRQUANTSIZE    (sizeof(XrmString) * (QUANTUMMASK + 1))
 112 #ifdef PERMQ
 113 #define QUANTSIZE       (STRQUANTSIZE + \
 114                          (sizeof(Bits) * ((QUANTUMMASK + 1) >> 3))
 115 #else
 116 #define QUANTSIZE       STRQUANTSIZE
 117 #endif
 118
 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]
 123 #ifdef PERMQ
 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))
 128 #endif
 129
 130 /* Permanent memory allocation */
 131
 132 #define WALIGN sizeof(unsigned long)
 133 #define DALIGN sizeof(double)
 134
 135 #define NEVERFREETABLESIZE ((8192-12) & ~(DALIGN-1))
 136 static char *neverFreeTable = NULL;
 137 static int  neverFreeTableSize = 0;
 138
 139 static char *permalloc(length)
 140     register unsigned int length;
 141 {
 142     char *ret;
 143
 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;
 151     }
 152     ret = neverFreeTable;
 153     neverFreeTable += length;
 154     neverFreeTableSize -= length;
 155     return(ret);
 156 }
 157
 158 #ifndef WORD64
 159 typedef struct {char a; double b;} TestType1;
 160 typedef struct {char a; unsigned long b;} TestType2;
 161 #endif
 162
 163 #ifdef XTHREADS
 164 static char *_falpermalloc();
 165
 166 char *falpermalloc(length)
 167     unsigned int length;
 168 {
 169     char *p;
 170
 171     _XLockMutex(_Xglobal_lock);
 172     p = _falpermalloc(length);
 173     _XUnlockMutex(_Xglobal_lock);
 174     return p;
 175 }
 176 #define falpermalloc _falpermalloc
 177
 178 static
 179 #endif /* XTHREADS */
 180 char *falpermalloc(length)
 181     unsigned int length;
 182 {
 183     int i;
 184
 185     if (neverFreeTableSize && length < NEVERFREETABLESIZE) {
 186 #ifndef WORD64
 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;
 193         } else
 194 #endif
 195             if (i = (NEVERFREETABLESIZE - neverFreeTableSize) & (WALIGN-1)) {
 196                 neverFreeTableSize -= WALIGN - i;
 197                 neverFreeTable += WALIGN - i;
 198             }
 199     }
 200     return permalloc(length);
 201 }
 202
 203 static Bool
 204 ExpandQuarkTable()
 205 {
 206     unsigned long oldmask, newmask;
 207     register char c, *s;
 208     register Entry *oldentries, *entries;
 209     register Entry entry;
 210     register int oldidx, newidx, rehash;
 211     Signature sig;
 212     XrmQuark q;
 213
 214     oldentries = quarkTable;
 215     if (oldmask = quarkMask)
 216         newmask = (oldmask << 1) + 1;
 217     else {
 218         if (!stringTable) {
 219             stringTable = (XrmString **)Xmalloc(sizeof(XrmString *) *
 220                                                 CHUNKPER);
 221             if (!stringTable)
 222                 return False;
 223             stringTable[0] = (XrmString *)NULL;
 224         }
 225 #ifdef PERMQ
 226         if (!permTable)
 227             permTable = (Bits **)Xmalloc(sizeof(Bits *) * CHUNKPER);
 228         if (!permTable)
 229             return False;
 230 #endif
 231         stringTable[0] = (XrmString *)falpermalloc(QUANTSIZE);
 232         if (!stringTable[0])
 233             return False;
 234 #ifdef PERMQ
 235         permTable[0] = (Bits *)((char *)stringTable[0] + STRQUANTSIZE);
 236 #endif
 237         newmask = 0x1ff;
 238     }
 239     entries = (Entry *)Xmalloc(sizeof(Entry) * (newmask + 1));
 240     if (!entries)
 241         return False;
 242     bzero((char *)entries, sizeof(Entry) * (newmask + 1));
 243     quarkTable = entries;
 244     quarkMask = newmask;
 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);
 250             else
 251                 q = (entry >> QUARKSHIFT) & QUARKMASK;
 252             for (sig = 0, s = NAME(q); c = *s++; )
 253                 sig = (sig << 1) + c;
 254             newidx = HASH(sig);
 255             if (entries[newidx]) {
 256                 rehash = REHASHVAL(sig);
 257                 do {
 258                     newidx = REHASH(newidx, rehash);
 259                 } while (entries[newidx]);
 260             }
 261             entries[newidx] = entry;
 262         }
 263     }
 264     if (oldmask)
 265         Xfree((char *)oldentries);
 266     return True;
 267 }
 268
 269 #if NeedFunctionPrototypes
 270 XrmQuark _falrmInternalStringToQuark(
 271     register _Xconst char *name, register int len, register Signature sig,
 272     Bool permstring)
 273 #else
 274 XrmQuark _falrmInternalStringToQuark(name, len, sig, permstring)
 275     register XrmString name;
 276     register int len;
 277     register Signature sig;
 278     Bool permstring;
 279 #endif
 280 {
 281     register XrmQuark q;
 282     register Entry entry;
 283     register int idx, rehash;
 284     register int i;
 285     register char *s1, *s2;
 286     char *new;
 287
 288     rehash = 0;
 289     idx = HASH(sig);
 290     _XLockMutex(_Xglobal_lock);
 291     while (entry = quarkTable[idx]) {
 292         if (entry & LARGEQUARK)
 293             q = entry & (LARGEQUARK-1);
 294         else {
 295             if ((entry - sig) & XSIGMASK)
 296                 goto nomatch;
 297             q = (entry >> QUARKSHIFT) & QUARKMASK;
 298         }
 299         for (i = len, s1 = (char *)name, s2 = NAME(q); --i >= 0; ) {
 300             if (*s1++ != *s2++)
 301                 goto nomatch;
 302         }
 303         if (*s2) {
 304 nomatch:    if (!rehash)
 305                 rehash = REHASHVAL(sig);
 306             idx = REHASH(idx, rehash);
 307             continue;
 308         }
 309 #ifdef PERMQ
 310         if (permstring && !ISPERM(q)) {
 311             Xfree(NAME(q));
 312             NAME(q) = (char *)name;
 313             SETPERM(q);
 314         }
 315 #endif
 316         _XUnlockMutex(_Xglobal_lock);
 317         return q;
 318     }
 319     if (nextUniq == nextQuark)
 320         goto fail;
 321     if ((nextQuark + (nextQuark >> 2)) > quarkMask) {
 322         if (!ExpandQuarkTable())
 323             goto fail;
 324         _XUnlockMutex(_Xglobal_lock);
 325         return _falrmInternalStringToQuark(name, len, sig, permstring);
 326     }
 327     q = nextQuark;
 328     if (!(q & QUANTUMMASK)) {
 329         if (!(q & CHUNKMASK)) {
 330             if (!(new = Xrealloc((char *)stringTable,
 331                                  sizeof(XrmString *) *
 332                                  ((q >> QUANTUMSHIFT) + CHUNKPER))))
 333                 goto fail;
 334             stringTable = (XrmString **)new;
 335 #ifdef PERMQ
 336             if (!(new = Xrealloc((char *)permTable,
 337                                  sizeof(Bits *) *
 338                                  ((q >> QUANTUMSHIFT) + CHUNKPER))))
 339                 goto fail;
 340             permTable = (Bits **)new;
 341 #endif
 342         }
 343         new = falpermalloc(QUANTSIZE);
 344         if (!new)
 345             goto fail;
 346         stringTable[q >> QUANTUMSHIFT] = (XrmString *)new;
 347 #ifdef PERMQ
 348         permTable[q >> QUANTUMSHIFT] = (Bits *)(new + STRQUANTSIZE);
 349 #endif
 350     }
 351     if (!permstring) {
 352         s2 = (char *)name;
 353 #ifdef PERMQ
 354         name = Xmalloc(len+1);
 355 #else
 356         name = permalloc(len+1);
 357 #endif
 358         if (!name)
 359             goto fail;
 360         for (i = len, s1 = (char *)name; --i >= 0; )
 361             *s1++ = *s2++;
 362         *s1++ = '\0';
 363 #ifdef PERMQ
 364         CLEARPERM(q);
 365     }
 366     else {
 367         SETPERM(q);
 368 #endif
 369     }
 370     NAME(q) = (char *)name;
 371     if (q <= QUARKMASK)
 372         entry = (q << QUARKSHIFT) | (sig & XSIGMASK);
 373     else
 374         entry = q | LARGEQUARK;
 375     quarkTable[idx] = entry;
 376     nextQuark++;
 377     _XUnlockMutex(_Xglobal_lock);
 378     return q;
 379  fail:
 380     _XUnlockMutex(_Xglobal_lock);
 381     return NULLQUARK;
 382 }
 383
 384 #if NeedFunctionPrototypes
 385 XrmQuark falrmStringToQuark(
 386     _Xconst char *name)
 387 #else
 388 XrmQuark falrmStringToQuark(name)
 389     XrmString name;
 390 #endif
 391 {
 392     register char c, *tname;
 393     register Signature sig = 0;
 394
 395     if (!name)
 396         return (NULLQUARK);
 397
 398     for (tname = (char *)name; c = *tname++; )
 399         sig = (sig << 1) + c;
 400
 401     return _falrmInternalStringToQuark(name, tname-(char *)name-1, sig, False);
 402 }
 403
 404 #if NeedFunctionPrototypes
 405 XrmQuark falrmPermStringToQuark(
 406     _Xconst char *name)
 407 #else
 408 XrmQuark falrmPermStringToQuark(name)
 409     XrmString name;
 410 #endif
 411 {
 412     register char c, *tname;
 413     register Signature sig = 0;
 414
 415     if (!name)
 416         return (NULLQUARK);
 417
 418     for (tname = (char *)name; c = *tname++; )
 419         sig = (sig << 1) + c;
 420
 421     return _falrmInternalStringToQuark(name, tname-(char *)name-1, sig, True);
 422 }
 423
 424 XrmQuark falrmUniqueQuark()
 425 {
 426     XrmQuark q;
 427
 428     _XLockMutex(_Xglobal_lock);
 429     if (nextUniq == nextQuark)
 430         q = NULLQUARK;
 431     else
 432         q = nextUniq--;
 433     _XUnlockMutex(_Xglobal_lock);
 434     return q;
 435 }
 436
 437 XrmString falrmQuarkToString(quark)
 438     register XrmQuark quark;
 439 {
 440     XrmString s;
 441
 442     _XLockMutex(_Xglobal_lock);
 443     if (quark <= 0 || quark >= nextQuark)
 444         s = NULLSTRING;
 445     else {
 446 #ifdef PERMQ
 447         /* We have to mark the quark as permanent, since the caller might hold
 448          * onto the string pointer forver.
 449          */
 450         SETPERM(quark);
 451 #endif
 452         s = NAME(quark);
 453     }
 454     _XUnlockMutex(_Xglobal_lock);
 455     return s;
 456 }