contrib/bmake/hash.h

   1 /*      $NetBSD: hash.h,v 1.33 2020/11/14 21:29:44 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
  92                                  * for each bucket 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 MAKE_INLINE void *
 107 HashEntry_Get(HashEntry *h)
 108 {
 109     return h->value;
 110 }
 111
 112 MAKE_INLINE void
 113 HashEntry_Set(HashEntry *h, void *datum)
 114 {
 115     h->value = datum;
 116 }
 117
 118 void HashTable_Init(HashTable *);
 119 void HashTable_Done(HashTable *);
 120 HashEntry *HashTable_FindEntry(HashTable *, const char *);
 121 void *HashTable_FindValue(HashTable *, const char *);
 122 unsigned int Hash_Hash(const char *);
 123 void *HashTable_FindValueHash(HashTable *, const char *, unsigned int);
 124 HashEntry *HashTable_CreateEntry(HashTable *, const char *, Boolean *);
 125 HashEntry *HashTable_Set(HashTable *, const char *, void *);
 126 void HashTable_DeleteEntry(HashTable *, HashEntry *);
 127 void HashTable_DebugStats(HashTable *, const char *);
 128
 129 void HashIter_Init(HashIter *, HashTable *);
 130 HashEntry *HashIter_Next(HashIter *);
 131
 132 #endif /* MAKE_HASH_H */