1956e45f6SSimon J. Gerraty /* $NetBSD: hash.h,v 1.31 2020/10/25 19:19:07 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 106956e45f6SSimon J. Gerraty static inline MAKE_ATTR_UNUSED void * 107956e45f6SSimon J. Gerraty HashEntry_Get(HashEntry *h) 1082c3632d1SSimon J. Gerraty { 1092c3632d1SSimon J. Gerraty return h->value; 1102c3632d1SSimon J. Gerraty } 1113955d011SMarcel Moolenaar 112956e45f6SSimon J. Gerraty static inline MAKE_ATTR_UNUSED void 113956e45f6SSimon J. Gerraty HashEntry_Set(HashEntry *h, void *datum) 1142c3632d1SSimon J. Gerraty { 1152c3632d1SSimon J. Gerraty h->value = datum; 1162c3632d1SSimon J. Gerraty } 1173955d011SMarcel Moolenaar 118956e45f6SSimon J. Gerraty void HashTable_Init(HashTable *); 119956e45f6SSimon J. Gerraty void HashTable_Done(HashTable *); 120956e45f6SSimon J. Gerraty HashEntry *HashTable_FindEntry(HashTable *, const char *); 121956e45f6SSimon J. Gerraty void *HashTable_FindValue(HashTable *, const char *); 122956e45f6SSimon J. Gerraty unsigned int Hash_Hash(const char *); 123956e45f6SSimon J. Gerraty void *HashTable_FindValueHash(HashTable *, const char *, unsigned int); 124956e45f6SSimon J. Gerraty HashEntry *HashTable_CreateEntry(HashTable *, const char *, Boolean *); 125956e45f6SSimon J. Gerraty void HashTable_DeleteEntry(HashTable *, HashEntry *); 126956e45f6SSimon J. Gerraty void HashTable_DebugStats(HashTable *, const char *); 127956e45f6SSimon J. Gerraty 128956e45f6SSimon J. Gerraty void HashIter_Init(HashIter *, HashTable *); 129956e45f6SSimon J. Gerraty HashEntry *HashIter_Next(HashIter *); 1303955d011SMarcel Moolenaar 1312c3632d1SSimon J. Gerraty #endif /* MAKE_HASH_H */ 132