hash.h revision 138264
11590Srgrimes/* 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: head/usr.bin/make/hash.h 138264 2004-12-01 10:29:20Z harti $ 411590Srgrimes */ 421590Srgrimes 431590Srgrimes/* hash.h -- 441590Srgrimes * 451590Srgrimes * This file contains definitions used by the hash module, 461590Srgrimes * which maintains hash tables. 471590Srgrimes */ 481590Srgrimes 491590Srgrimes#ifndef _HASH 501590Srgrimes#define _HASH 511590Srgrimes 528874Srgrimes/* 531590Srgrimes * The following defines one entry in the hash table. 541590Srgrimes */ 551590Srgrimes 561590Srgrimestypedef struct Hash_Entry { 571590Srgrimes struct Hash_Entry *next; /* Used to link together all the 581590Srgrimes * entries associated with the same 591590Srgrimes * bucket. */ 6069531Swill void * clientData; /* Arbitrary piece of data associated 611590Srgrimes * with key. */ 621590Srgrimes unsigned namehash; /* hash value of key */ 631590Srgrimes char name[1]; /* key string */ 641590Srgrimes} Hash_Entry; 651590Srgrimes 661590Srgrimestypedef struct Hash_Table { 671590Srgrimes struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one 681590Srgrimes * for each bucket in the table. */ 691590Srgrimes int size; /* Actual size of array. */ 701590Srgrimes int numEntries; /* Number of entries in the table. */ 711590Srgrimes int mask; /* Used to select bits for hashing. */ 721590Srgrimes} Hash_Table; 731590Srgrimes 748874Srgrimes/* 751590Srgrimes * The following structure is used by the searching routines 761590Srgrimes * to record where we are in the search. 771590Srgrimes */ 781590Srgrimes 791590Srgrimestypedef struct Hash_Search { 801590Srgrimes Hash_Table *tablePtr; /* Table being searched. */ 811590Srgrimes int nextIndex; /* Next bucket to check (after current). */ 821590Srgrimes Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ 831590Srgrimes} Hash_Search; 841590Srgrimes 851590Srgrimes/* 861590Srgrimes * Macros. 871590Srgrimes */ 881590Srgrimes 891590Srgrimes/* 9069531Swill * void * Hash_GetValue(h) 918874Srgrimes * Hash_Entry *h; 921590Srgrimes */ 931590Srgrimes 94103503Sjmallett#define Hash_GetValue(h) ((h)->clientData) 951590Srgrimes 968874Srgrimes/* 978874Srgrimes * Hash_SetValue(h, val); 988874Srgrimes * Hash_Entry *h; 998874Srgrimes * char *val; 1001590Srgrimes */ 1011590Srgrimes 102138264Sharti#define Hash_SetValue(h, val) ((h)->clientData = (val)) 1031590Srgrimes 1048874Srgrimes/* 1058874Srgrimes * Hash_Size(n) returns the number of words in an object of n bytes 1061590Srgrimes */ 1071590Srgrimes 108138232Sharti#define Hash_Size(n) (((n) + sizeof(int) - 1) / sizeof(int)) 1091590Srgrimes 11092921Simpvoid Hash_InitTable(Hash_Table *, int); 11192921Simpvoid Hash_DeleteTable(Hash_Table *); 11292921SimpHash_Entry *Hash_FindEntry(Hash_Table *, char *); 11392921SimpHash_Entry *Hash_CreateEntry(Hash_Table *, char *, Boolean *); 11492921Simpvoid Hash_DeleteEntry(Hash_Table *, Hash_Entry *); 11592921SimpHash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *); 11692921SimpHash_Entry *Hash_EnumNext(Hash_Search *); 1171590Srgrimes 1181590Srgrimes#endif /* _HASH */ 119