cde/lib/DtSvc/DtUtil2/Hash.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 /* $XConsortium: Hash.c /main/4 1995/10/26 15:22:41 rswiston $ */
  24 /*
  25  * (c) Copyright 1993, 1994 Hewlett-Packard Company                     *
  26  * (c) Copyright 1993, 1994 International Business Machines Corp.       *
  27  * (c) Copyright 1993, 1994 Sun Microsystems, Inc.                      *
  28  * (c) Copyright 1993, 1994 Novell, Inc.                                *
  29  */
  30 /***********************************************************
  31 Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
  32 Massachusetts, and the Massachusetts Institute of Technology, Cambridge,
  33 Massachusetts.
  34
  35                         All Rights Reserved
  36
  37 Permission to use, copy, modify, and distribute this software and its
  38 documentation for any purpose and without fee is hereby granted,
  39 provided that the above copyright notice appear in all copies and that
  40 both that copyright notice and this permission notice appear in
  41 supporting documentation, and that the names of Digital or MIT not be
  42 used in advertising or publicity pertaining to distribution of the
  43 software without specific, written prior permission.
  44
  45 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  46 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  47 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  48 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  49 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  50 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  51 SOFTWARE.
  52
  53 ******************************************************************/
  54
  55 #include "HashP.h"
  56
  57 /********    Static Function Declarations    ********/
  58
  59 static unsigned int GetTableIndex(
  60                         register DtHashTable tab,
  61                         register DtHashKey key,
  62 #if NeedWidePrototypes
  63                         register int new) ;
  64 #else
  65                         register Boolean new) ;
  66 #endif /* NeedWidePrototypes */
  67 static void ExpandHashTable(
  68                         register DtHashTable tab) ;
  69
  70 /********    End Static Function Declarations    ********/
  71
  72
  73 typedef unsigned long   Signature;
  74
  75 typedef struct _DtHashTableRec {
  76     unsigned int mask;          /* size of hash table - 1 */
  77     unsigned int rehash;        /* mask - 2 */
  78     unsigned int occupied;      /* number of occupied entries */
  79     unsigned int fakes;         /* number occupied by DTHASHfake */
  80     DtHashEntryType *types;     /* lookup methods for key       */
  81     unsigned short numTypes;    /* number of lookup methods     */
  82     Boolean      keyIsString;   /* whether the hash key is a string */
  83     DtHashEntry *entries;       /* the entries */
  84 }DtHashTableRec;
  85
  86 static DtHashEntryRec DtHashfake;       /* placeholder for deletions */
  87
  88 #define HASH(tab,sig) ((sig) & tab->mask)
  89 #define REHASHVAL(tab, idx) ((((idx) % tab->rehash) + 2) | 1)
  90 #define REHASH(tab,idx,rehash) ((idx + rehash) & tab->mask)
  91 #define KEY(tab, entry) \
  92   ((*  (tab->types[entry->hash.type]->hash.getKeyFunc) ) \
  93    (entry, tab->types[entry->hash.type]->hash.getKeyClientData))
  94
  95 #define RELEASE_KEY(tab, entry, key) \
  96 {\
  97    if (tab->types[entry->hash.type]->hash.releaseKeyProc) \
  98      (*  (tab->types[entry->hash.type]->hash.releaseKeyProc)) \
  99        (entry, key); \
 100      }
 101
 102 static unsigned int
 103 GetTableIndex(
 104               register DtHashTable tab,
 105               register DtHashKey key,
 106 #if NeedWidePrototypes
 107               register int new)
 108 #else
 109               register Boolean new)
 110 #endif /* NeedWidePrototypes */
 111 {
 112     register DtHashEntry        *entries = tab->entries;
 113     register int                len, idx, i, rehash = 0;
 114     register char               c;
 115     register Signature          sig = 0;
 116     register DtHashEntry        entry;
 117     String                      s1, s2;
 118     DtHashKey                   compKey;
 119
 120     if (tab->keyIsString) {
 121         s1 = (String)key;
 122         for (s2 = (char *)s1; c = *s2++; )
 123           sig = (sig << 1) + c;
 124         len = s2 - s1 - 1;
 125     }
 126     else
 127       sig = (Signature)key;
 128
 129     idx = HASH(tab, sig);
 130     while (entry = entries[idx]) {
 131         if (entries[idx] == &DtHashfake) {
 132             if (new)
 133               return idx;
 134             else
 135               goto nomatch;
 136         }
 137         if (tab->keyIsString) {
 138             compKey = KEY(tab, entry);
 139             for (i = len, s1 = (String)key, s2 = (String) compKey;
 140                  --i >= 0; ) {
 141                 if (*s1++ != *s2++)
 142                   goto nomatch;
 143             }
 144         }
 145         else {
 146             if ((compKey = KEY(tab, entry)) != key)
 147               s2 = " ";
 148             else
 149               s2 = "";
 150         }
 151
 152         if (*s2) {
 153 nomatch:
 154             RELEASE_KEY(tab, entry, compKey);
 155             if (!rehash)
 156               rehash = REHASHVAL(tab, idx);
 157             idx = REHASH(tab, idx, rehash);
 158             continue;
 159         }
 160         else
 161           RELEASE_KEY(tab, entry, compKey);
 162         break;
 163     }
 164     return idx;
 165 }
 166
 167
 168
 169 void
 170 _DtRegisterHashEntry(
 171         register DtHashTable tab,
 172         register DtHashKey key,
 173         register DtHashEntry entry )
 174 {
 175     unsigned int idx;
 176
 177     if ((tab->occupied + (tab->occupied >> 2)) > tab->mask)
 178         ExpandHashTable(tab);
 179
 180     idx = GetTableIndex(tab, key, True);
 181     if (tab->entries[idx] == &DtHashfake)
 182       tab->fakes--;
 183     tab->occupied++;
 184     tab->entries[idx] = entry;
 185 }
 186
 187 void
 188 _DtUnregisterHashEntry(
 189         register DtHashTable tab,
 190         register DtHashEntry entry )
 191 {
 192     register int                idx, rehash;
 193     register DtHashEntry        *entries = tab->entries;
 194     DtHashKey                   key = KEY(tab, entry);
 195
 196     idx = GetTableIndex(tab, key, False);
 197     RELEASE_KEY(tab, entry, key);
 198     entries[idx] = &DtHashfake;
 199     tab->fakes++;
 200     tab->occupied--;
 201 }
 202
 203
 204 static void
 205 ExpandHashTable(
 206         register DtHashTable tab )
 207 {
 208     unsigned int oldmask;
 209     register DtHashEntry *oldentries, *entries;
 210     register int oldidx, newidx, rehash, len;
 211     register DtHashEntry entry;
 212     register DtHashKey key;
 213
 214     oldmask = tab->mask;
 215     oldentries = tab->entries;
 216     tab->fakes = 0;
 217     if ((tab->occupied + (tab->occupied >> 2)) > tab->mask) {
 218         tab->mask = (tab->mask << 1) + 1;
 219         tab->rehash = tab->mask - 2;
 220     }
 221     entries = tab->entries = (DtHashEntry *) XtCalloc(tab->mask+1, sizeof(DtHashEntry));
 222     for (oldidx = 0; oldidx <= oldmask; oldidx++) {
 223         if ((entry = oldentries[oldidx]) && entry != &DtHashfake) {
 224             newidx = GetTableIndex(tab, key = KEY(tab, entry), True);
 225             RELEASE_KEY(tab, entry, key);
 226             entries[newidx] = entry;
 227         }
 228     }
 229     XtFree((char *)oldentries);
 230 }
 231
 232
 233 DtHashEntry
 234 _DtEnumerateHashTable(
 235         register DtHashTable tab,
 236         register DtHashEnumerateFunc enumFunc,
 237         register XtPointer clientData )
 238 {
 239     register unsigned int i;
 240
 241     for (i = 0; i <= tab->mask; i++)
 242       if (tab->entries[i] &&
 243           tab->entries[i] != &DtHashfake &&
 244           ((*enumFunc) (tab->entries[i], clientData)))
 245         return tab->entries[i];
 246     return NULL;
 247 }
 248
 249
 250 DtHashEntry
 251 _DtKeyToHashEntry(
 252         register DtHashTable tab,
 253         register DtHashKey key )
 254 {
 255     register int idx, rehash, len;
 256     register DtHashEntry entry, *entries = tab->entries;
 257
 258     if (!key) return NULL;
 259     idx = GetTableIndex(tab, key, False);
 260     return entries[idx];
 261 }
 262
 263 DtHashTable
 264 _DtAllocHashTable(DtHashEntryType       *hashEntryTypes,
 265                    Cardinal             numHashEntryTypes,
 266 #if NeedWidePrototypes
 267                    int                  keyIsString)
 268 #else
 269                    Boolean              keyIsString)
 270 #endif /* NeedWidePrototypes */
 271 {
 272     register DtHashTable tab;
 273
 274     tab = (DtHashTable) XtMalloc(sizeof(struct _DtHashTableRec));
 275     tab->types = hashEntryTypes;
 276     tab->numTypes = numHashEntryTypes;
 277     tab->keyIsString = keyIsString;
 278     tab->mask = 0x7f;
 279     tab->rehash = tab->mask - 2;
 280     tab->entries = (DtHashEntry *) XtCalloc(tab->mask+1, sizeof(DtHashEntry));
 281     tab->occupied = 0;
 282     tab->fakes = 0;
 283     return tab;
 284 }
 285
 286 void
 287 _DtFreeHashTable(
 288         DtHashTable hashTable )
 289 {
 290     XtFree((char *)hashTable->entries);
 291     XtFree((char *)hashTable);
 292 }