112904384SSimon J. Gerraty /* $NetBSD: hash.h,v 1.41 2021/12/07 21:58:01 rillig Exp $ */ 23955d011SMarcel Moolenaar 33955d011SMarcel Moolenaar /* 43955d011SMarcel Moolenaar * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 53955d011SMarcel Moolenaar * 63955d011SMarcel Moolenaar * This code is derived from software contributed to Berkeley by 73955d011SMarcel Moolenaar * Adam de Boor. 83955d011SMarcel Moolenaar * 93955d011SMarcel Moolenaar * Redistribution and use in source and binary forms, with or without 103955d011SMarcel Moolenaar * modification, are permitted provided that the following conditions 113955d011SMarcel Moolenaar * are met: 123955d011SMarcel Moolenaar * 1. Redistributions of source code must retain the above copyright 133955d011SMarcel Moolenaar * notice, this list of conditions and the following disclaimer. 143955d011SMarcel Moolenaar * 2. Redistributions in binary form must reproduce the above copyright 153955d011SMarcel Moolenaar * notice, this list of conditions and the following disclaimer in the 163955d011SMarcel Moolenaar * documentation and/or other materials provided with the distribution. 173955d011SMarcel Moolenaar * 3. Neither the name of the University nor the names of its contributors 183955d011SMarcel Moolenaar * may be used to endorse or promote products derived from this software 193955d011SMarcel Moolenaar * without specific prior written permission. 203955d011SMarcel Moolenaar * 213955d011SMarcel Moolenaar * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 223955d011SMarcel Moolenaar * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 233955d011SMarcel Moolenaar * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 243955d011SMarcel Moolenaar * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 253955d011SMarcel Moolenaar * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 263955d011SMarcel Moolenaar * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 273955d011SMarcel Moolenaar * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 283955d011SMarcel Moolenaar * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 293955d011SMarcel Moolenaar * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 303955d011SMarcel Moolenaar * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 313955d011SMarcel Moolenaar * SUCH DAMAGE. 323955d011SMarcel Moolenaar * 333955d011SMarcel Moolenaar * from: @(#)hash.h 8.1 (Berkeley) 6/6/93 343955d011SMarcel Moolenaar */ 353955d011SMarcel Moolenaar 363955d011SMarcel Moolenaar /* 373955d011SMarcel Moolenaar * Copyright (c) 1988, 1989 by Adam de Boor 383955d011SMarcel Moolenaar * Copyright (c) 1989 by Berkeley Softworks 393955d011SMarcel Moolenaar * All rights reserved. 403955d011SMarcel Moolenaar * 413955d011SMarcel Moolenaar * This code is derived from software contributed to Berkeley by 423955d011SMarcel Moolenaar * Adam de Boor. 433955d011SMarcel Moolenaar * 443955d011SMarcel Moolenaar * Redistribution and use in source and binary forms, with or without 453955d011SMarcel Moolenaar * modification, are permitted provided that the following conditions 463955d011SMarcel Moolenaar * are met: 473955d011SMarcel Moolenaar * 1. Redistributions of source code must retain the above copyright 483955d011SMarcel Moolenaar * notice, this list of conditions and the following disclaimer. 493955d011SMarcel Moolenaar * 2. Redistributions in binary form must reproduce the above copyright 503955d011SMarcel Moolenaar * notice, this list of conditions and the following disclaimer in the 513955d011SMarcel Moolenaar * documentation and/or other materials provided with the distribution. 523955d011SMarcel Moolenaar * 3. All advertising materials mentioning features or use of this software 533955d011SMarcel Moolenaar * must display the following acknowledgement: 543955d011SMarcel Moolenaar * This product includes software developed by the University of 553955d011SMarcel Moolenaar * California, Berkeley and its contributors. 563955d011SMarcel Moolenaar * 4. Neither the name of the University nor the names of its contributors 573955d011SMarcel Moolenaar * may be used to endorse or promote products derived from this software 583955d011SMarcel Moolenaar * without specific prior written permission. 593955d011SMarcel Moolenaar * 603955d011SMarcel Moolenaar * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 613955d011SMarcel Moolenaar * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 623955d011SMarcel Moolenaar * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 633955d011SMarcel Moolenaar * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 643955d011SMarcel Moolenaar * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 653955d011SMarcel Moolenaar * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 663955d011SMarcel Moolenaar * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 673955d011SMarcel Moolenaar * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 683955d011SMarcel Moolenaar * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 693955d011SMarcel Moolenaar * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 703955d011SMarcel Moolenaar * SUCH DAMAGE. 713955d011SMarcel Moolenaar * 723955d011SMarcel Moolenaar * from: @(#)hash.h 8.1 (Berkeley) 6/6/93 733955d011SMarcel Moolenaar */ 743955d011SMarcel Moolenaar 752c3632d1SSimon J. Gerraty /* Hash tables with strings as keys and arbitrary pointers as values. */ 763955d011SMarcel Moolenaar 772c3632d1SSimon J. Gerraty #ifndef MAKE_HASH_H 782c3632d1SSimon J. Gerraty #define MAKE_HASH_H 793955d011SMarcel Moolenaar 802c3632d1SSimon J. Gerraty /* A single key-value entry in the hash table. */ 81956e45f6SSimon J. Gerraty typedef struct HashEntry { 82956e45f6SSimon J. Gerraty struct HashEntry *next; /* Used to link together all the entries 832c3632d1SSimon J. Gerraty * associated with the same bucket. */ 842c3632d1SSimon J. Gerraty void *value; 85956e45f6SSimon J. Gerraty unsigned int key_hash; /* hash value of the key */ 86956e45f6SSimon J. Gerraty char key[1]; /* key string, variable length */ 87956e45f6SSimon J. Gerraty } HashEntry; 883955d011SMarcel Moolenaar 892c3632d1SSimon J. Gerraty /* The hash table containing the entries. */ 90956e45f6SSimon J. Gerraty typedef struct HashTable { 91956e45f6SSimon J. Gerraty HashEntry **buckets; /* Pointers to HashEntry, one 923955d011SMarcel Moolenaar * for each bucket in the table. */ 93956e45f6SSimon J. Gerraty unsigned int bucketsSize; 94956e45f6SSimon J. Gerraty unsigned int numEntries; /* Number of entries in the table. */ 95956e45f6SSimon J. Gerraty unsigned int bucketsMask; /* Used to select the bucket for a hash. */ 96956e45f6SSimon J. Gerraty unsigned int maxchain; /* max length of chain detected */ 97956e45f6SSimon J. Gerraty } HashTable; 983955d011SMarcel Moolenaar 99956e45f6SSimon J. Gerraty /* State of an iteration over all entries in a table. */ 100956e45f6SSimon J. Gerraty typedef struct HashIter { 101956e45f6SSimon J. Gerraty HashTable *table; /* Table being searched. */ 102956e45f6SSimon J. Gerraty unsigned int nextBucket; /* Next bucket to check (after current). */ 103956e45f6SSimon J. Gerraty HashEntry *entry; /* Next entry to check in current bucket. */ 104956e45f6SSimon J. Gerraty } HashIter; 1053955d011SMarcel Moolenaar 10606b9b3e0SSimon J. Gerraty /* A set of strings. */ 10706b9b3e0SSimon J. Gerraty typedef struct HashSet { 10806b9b3e0SSimon J. Gerraty HashTable tbl; 10906b9b3e0SSimon J. Gerraty } HashSet; 11006b9b3e0SSimon J. Gerraty 111e2eeea75SSimon J. Gerraty MAKE_INLINE void * 112956e45f6SSimon J. Gerraty HashEntry_Get(HashEntry *h) 1132c3632d1SSimon J. Gerraty { 1142c3632d1SSimon J. Gerraty return h->value; 1152c3632d1SSimon J. Gerraty } 1163955d011SMarcel Moolenaar 117e2eeea75SSimon J. Gerraty MAKE_INLINE void 118956e45f6SSimon J. Gerraty HashEntry_Set(HashEntry *h, void *datum) 1192c3632d1SSimon J. Gerraty { 1202c3632d1SSimon J. Gerraty h->value = datum; 1212c3632d1SSimon J. Gerraty } 1223955d011SMarcel Moolenaar 12312904384SSimon J. Gerraty /* Set things up for iterating over all entries in the hash table. */ 12412904384SSimon J. Gerraty MAKE_INLINE void 12512904384SSimon J. Gerraty HashIter_Init(HashIter *hi, HashTable *t) 12612904384SSimon J. Gerraty { 12712904384SSimon J. Gerraty hi->table = t; 12812904384SSimon J. Gerraty hi->nextBucket = 0; 12912904384SSimon J. Gerraty hi->entry = NULL; 13012904384SSimon J. Gerraty } 13112904384SSimon J. Gerraty 132956e45f6SSimon J. Gerraty void HashTable_Init(HashTable *); 133956e45f6SSimon J. Gerraty void HashTable_Done(HashTable *); 134956e45f6SSimon J. Gerraty HashEntry *HashTable_FindEntry(HashTable *, const char *); 135956e45f6SSimon J. Gerraty void *HashTable_FindValue(HashTable *, const char *); 136b0c40a00SSimon J. Gerraty unsigned int Hash_Substring(Substring); 137b0c40a00SSimon J. Gerraty void *HashTable_FindValueBySubstringHash(HashTable *, Substring, unsigned int); 138b0c40a00SSimon J. Gerraty HashEntry *HashTable_CreateEntry(HashTable *, const char *, bool *); 139e2eeea75SSimon J. Gerraty HashEntry *HashTable_Set(HashTable *, const char *, void *); 140956e45f6SSimon J. Gerraty void HashTable_DeleteEntry(HashTable *, HashEntry *); 141956e45f6SSimon J. Gerraty void HashTable_DebugStats(HashTable *, const char *); 142956e45f6SSimon J. Gerraty 143956e45f6SSimon J. Gerraty void HashIter_Init(HashIter *, HashTable *); 144956e45f6SSimon J. Gerraty HashEntry *HashIter_Next(HashIter *); 1453955d011SMarcel Moolenaar 14606b9b3e0SSimon J. Gerraty MAKE_INLINE void 14706b9b3e0SSimon J. Gerraty HashSet_Init(HashSet *set) 14806b9b3e0SSimon J. Gerraty { 14906b9b3e0SSimon J. Gerraty HashTable_Init(&set->tbl); 15006b9b3e0SSimon J. Gerraty } 15106b9b3e0SSimon J. Gerraty 15206b9b3e0SSimon J. Gerraty MAKE_INLINE void 15306b9b3e0SSimon J. Gerraty HashSet_Done(HashSet *set) 15406b9b3e0SSimon J. Gerraty { 15506b9b3e0SSimon J. Gerraty HashTable_Done(&set->tbl); 15606b9b3e0SSimon J. Gerraty } 15706b9b3e0SSimon J. Gerraty 158b0c40a00SSimon J. Gerraty MAKE_INLINE bool 15906b9b3e0SSimon J. Gerraty HashSet_Add(HashSet *set, const char *key) 16006b9b3e0SSimon J. Gerraty { 161b0c40a00SSimon J. Gerraty bool isNew; 16206b9b3e0SSimon J. Gerraty 16306b9b3e0SSimon J. Gerraty (void)HashTable_CreateEntry(&set->tbl, key, &isNew); 16406b9b3e0SSimon J. Gerraty return isNew; 16506b9b3e0SSimon J. Gerraty } 16606b9b3e0SSimon J. Gerraty 167b0c40a00SSimon J. Gerraty MAKE_INLINE bool 16806b9b3e0SSimon J. Gerraty HashSet_Contains(HashSet *set, const char *key) 16906b9b3e0SSimon J. Gerraty { 17006b9b3e0SSimon J. Gerraty return HashTable_FindEntry(&set->tbl, key) != NULL; 17106b9b3e0SSimon J. Gerraty } 17206b9b3e0SSimon J. Gerraty 17306b9b3e0SSimon J. Gerraty MAKE_INLINE void 17406b9b3e0SSimon J. Gerraty HashIter_InitSet(HashIter *hi, HashSet *set) 17506b9b3e0SSimon J. Gerraty { 17606b9b3e0SSimon J. Gerraty HashIter_Init(hi, &set->tbl); 17706b9b3e0SSimon J. Gerraty } 17806b9b3e0SSimon J. Gerraty 1792c3632d1SSimon J. Gerraty #endif /* MAKE_HASH_H */ 180