1141104Sharti/*- 294589Sobrien * Copyright (c) 1988, 1989, 1990, 1993 394589Sobrien * The Regents of the University of California. All rights reserved. 45814Sjkh * Copyright (c) 1988, 1989 by Adam de Boor 51590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 61590Srgrimes * All rights reserved. 71590Srgrimes * 81590Srgrimes * This code is derived from software contributed to Berkeley by 91590Srgrimes * Adam de Boor. 101590Srgrimes * 111590Srgrimes * Redistribution and use in source and binary forms, with or without 121590Srgrimes * modification, are permitted provided that the following conditions 131590Srgrimes * are met: 141590Srgrimes * 1. Redistributions of source code must retain the above copyright 151590Srgrimes * notice, this list of conditions and the following disclaimer. 161590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 171590Srgrimes * notice, this list of conditions and the following disclaimer in the 181590Srgrimes * documentation and/or other materials provided with the distribution. 191590Srgrimes * 3. All advertising materials mentioning features or use of this software 201590Srgrimes * must display the following acknowledgement: 211590Srgrimes * This product includes software developed by the University of 221590Srgrimes * California, Berkeley and its contributors. 231590Srgrimes * 4. Neither the name of the University nor the names of its contributors 241590Srgrimes * may be used to endorse or promote products derived from this software 251590Srgrimes * without specific prior written permission. 261590Srgrimes * 271590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 281590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 291590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 301590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 311590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 321590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 331590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 341590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 351590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 361590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 371590Srgrimes * SUCH DAMAGE. 381590Srgrimes * 3994589Sobrien * @(#)hash.h 8.1 (Berkeley) 6/6/93 4050477Speter * $FreeBSD: releng/10.3/usr.bin/make/hash.h 146177 2005-05-13 08:53:00Z harti $ 411590Srgrimes */ 421590Srgrimes 43141104Sharti#ifndef hash_h_f6312f46 44141104Sharti#define hash_h_f6312f46 45141104Sharti 461590Srgrimes/* hash.h -- 471590Srgrimes * 481590Srgrimes * This file contains definitions used by the hash module, 491590Srgrimes * which maintains hash tables. 501590Srgrimes */ 511590Srgrimes 52146177Sharti#include "util.h" 531590Srgrimes 548874Srgrimes/* 551590Srgrimes * The following defines one entry in the hash table. 561590Srgrimes */ 571590Srgrimestypedef struct Hash_Entry { 58138433Sharti struct Hash_Entry *next; /* Link entries within same bucket. */ 59138433Sharti void *clientData; /* Data associated with key. */ 60138433Sharti unsigned namehash; /* hash value of key */ 61138433Sharti char name[1]; /* key string */ 621590Srgrimes} Hash_Entry; 631590Srgrimes 641590Srgrimestypedef struct Hash_Table { 65138433Sharti struct Hash_Entry **bucketPtr; /* Buckets in the table */ 66138433Sharti int size; /* Actual size of array. */ 67138433Sharti int numEntries; /* Number of entries in the table. */ 68138433Sharti int mask; /* Used to select bits for hashing. */ 691590Srgrimes} Hash_Table; 701590Srgrimes 718874Srgrimes/* 721590Srgrimes * The following structure is used by the searching routines 731590Srgrimes * to record where we are in the search. 741590Srgrimes */ 751590Srgrimestypedef struct Hash_Search { 76138455Sharti const Hash_Table *tablePtr; /* Table being searched. */ 77138433Sharti int nextIndex; /* Next bucket to check */ 78138433Sharti Hash_Entry *hashEntryPtr; /* Next entry in current bucket */ 791590Srgrimes} Hash_Search; 801590Srgrimes 811590Srgrimes/* 821590Srgrimes * Macros. 831590Srgrimes */ 841590Srgrimes 851590Srgrimes/* 86138433Sharti * void *Hash_GetValue(const Hash_Entry *h) 871590Srgrimes */ 88103503Sjmallett#define Hash_GetValue(h) ((h)->clientData) 891590Srgrimes 908874Srgrimes/* 91138433Sharti * Hash_SetValue(Hash_Entry *h, void *val); 921590Srgrimes */ 93138264Sharti#define Hash_SetValue(h, val) ((h)->clientData = (val)) 941590Srgrimes 9592921Simpvoid Hash_InitTable(Hash_Table *, int); 9692921Simpvoid Hash_DeleteTable(Hash_Table *); 97138435ShartiHash_Entry *Hash_FindEntry(const Hash_Table *, const char *); 98138435ShartiHash_Entry *Hash_CreateEntry(Hash_Table *, const char *, Boolean *); 9992921Simpvoid Hash_DeleteEntry(Hash_Table *, Hash_Entry *); 100138455ShartiHash_Entry *Hash_EnumFirst(const Hash_Table *, Hash_Search *); 10192921SimpHash_Entry *Hash_EnumNext(Hash_Search *); 1021590Srgrimes 103141104Sharti#endif /* hash_h_f6312f46 */ 104