hash.h

   1 /*      $NetBSD: hash.h,v 1.46 2022/01/31 22:58:26 rillig Exp $ */
   2
   3 /*
   4  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
   5  *
   6  * This code is derived from software contributed to Berkeley by
   7  * Adam de Boor.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
  34  */
  35
  36 /*
  37  * Copyright (c) 1988, 1989 by Adam de Boor
  38  * Copyright (c) 1989 by Berkeley Softworks
  39  * All rights reserved.
  40  *
  41  * This code is derived from software contributed to Berkeley by
  42  * Adam de Boor.
  43  *
  44  * Redistribution and use in source and binary forms, with or without
  45  * modification, are permitted provided that the following conditions
  46  * are met:
  47  * 1. Redistributions of source code must retain the above copyright
  48  *    notice, this list of conditions and the following disclaimer.
  49  * 2. Redistributions in binary form must reproduce the above copyright
  50  *    notice, this list of conditions and the following disclaimer in the
  51  *    documentation and/or other materials provided with the distribution.
  52  * 3. All advertising materials mentioning features or use of this software
  53  *    must display the following acknowledgement:
  54  *      This product includes software developed by the University of
  55  *      California, Berkeley and its contributors.
  56  * 4. Neither the name of the University nor the names of its contributors
  57  *    may be used to endorse or promote products derived from this software
  58  *    without specific prior written permission.
  59  *
  60  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  61  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  62  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  63  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  64  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  65  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  66  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  67  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  68  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  69  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  70  * SUCH DAMAGE.
  71  *
  72  *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
  73  */
  74
  75 /* Hash tables with strings as keys and arbitrary pointers as values. */
  76
  77 #ifndef MAKE_HASH_H
  78 #define MAKE_HASH_H
  79
  80 /* A single key-value entry in the hash table. */
  81 typedef struct HashEntry {
  82         struct HashEntry *next; /* Used to link together all the entries
  83                                  * associated with the same bucket. */
  84         void *value;
  85         unsigned int key_hash;  /* hash value of the key */
  86         char key[1];            /* key string, variable length */
  87 } HashEntry;
  88
  89 /* The hash table containing the entries. */
  90 typedef struct HashTable {
  91         HashEntry **buckets;    /* Pointers to HashEntry, one for each bucket
  92                                  * in the table. */
  93         unsigned int bucketsSize;
  94         unsigned int numEntries; /* Number of entries in the table. */
  95         unsigned int bucketsMask; /* Used to select the bucket for a hash. */
  96         unsigned int maxchain;  /* max length of chain detected */
  97 } HashTable;
  98
  99 /* State of an iteration over all entries in a table. */
 100 typedef struct HashIter {
 101         HashTable *table;       /* Table being searched. */
 102         unsigned int nextBucket; /* Next bucket to check (after current). */
 103         HashEntry *entry;       /* Next entry to check in current bucket. */
 104 } HashIter;
 105
 106 /* A set of strings. */
 107 typedef struct HashSet {
 108         HashTable tbl;
 109 } HashSet;
 110
 111 MAKE_INLINE void * MAKE_ATTR_USE
 112 HashEntry_Get(HashEntry *h)
 113 {
 114         return h->value;
 115 }
 116
 117 MAKE_INLINE void
 118 HashEntry_Set(HashEntry *h, void *datum)
 119 {
 120         h->value = datum;
 121 }
 122
 123 /* Set things up for iterating over all entries in the hash table. */
 124 MAKE_INLINE void
 125 HashIter_Init(HashIter *hi, HashTable *t)
 126 {
 127         hi->table = t;
 128         hi->nextBucket = 0;
 129         hi->entry = NULL;
 130 }
 131
 132 void HashTable_Init(HashTable *);
 133 void HashTable_Done(HashTable *);
 134 HashEntry *HashTable_FindEntry(HashTable *, const char *) MAKE_ATTR_USE;
 135 void *HashTable_FindValue(HashTable *, const char *) MAKE_ATTR_USE;
 136 unsigned int Hash_Substring(Substring) MAKE_ATTR_USE;
 137 void *HashTable_FindValueBySubstringHash(HashTable *, Substring, unsigned int)
 138     MAKE_ATTR_USE;
 139 HashEntry *HashTable_CreateEntry(HashTable *, const char *, bool *);
 140 void HashTable_Set(HashTable *, const char *, void *);
 141 void HashTable_DeleteEntry(HashTable *, HashEntry *);
 142 void HashTable_DebugStats(HashTable *, const char *);
 143
 144 HashEntry *HashIter_Next(HashIter *);
 145
 146 MAKE_INLINE void
 147 HashSet_Init(HashSet *set)
 148 {
 149         HashTable_Init(&set->tbl);
 150 }
 151
 152 MAKE_INLINE void
 153 HashSet_Done(HashSet *set)
 154 {
 155         HashTable_Done(&set->tbl);
 156 }
 157
 158 MAKE_INLINE bool
 159 HashSet_Add(HashSet *set, const char *key)
 160 {
 161         bool isNew;
 162
 163         (void)HashTable_CreateEntry(&set->tbl, key, &isNew);
 164         return isNew;
 165 }
 166
 167 MAKE_INLINE bool MAKE_ATTR_USE
 168 HashSet_Contains(HashSet *set, const char *key)
 169 {
 170         return HashTable_FindEntry(&set->tbl, key) != NULL;
 171 }
 172
 173 MAKE_INLINE void
 174 HashIter_InitSet(HashIter *hi, HashSet *set)
 175 {
 176         HashIter_Init(hi, &set->tbl);
 177 }
 178
 179 #endif