hash.h revision 5814
1193323Sed/* 2193323Sed * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 3193323Sed * Copyright (c) 1988, 1989 by Adam de Boor 4193323Sed * Copyright (c) 1989 by Berkeley Softworks 5193323Sed * All rights reserved. 6193323Sed * 7193323Sed * This code is derived from software contributed to Berkeley by 8193323Sed * Adam de Boor. 9193323Sed * 10193323Sed * Redistribution and use in source and binary forms, with or without 11193323Sed * modification, are permitted provided that the following conditions 12193323Sed * are met: 13193323Sed * 1. Redistributions of source code must retain the above copyright 14193323Sed * notice, this list of conditions and the following disclaimer. 15193323Sed * 2. Redistributions in binary form must reproduce the above copyright 16218885Sdim * notice, this list of conditions and the following disclaimer in the 17193323Sed * documentation and/or other materials provided with the distribution. 18193323Sed * 3. All advertising materials mentioning features or use of this software 19193323Sed * must display the following acknowledgement: 20198090Srdivacky * This product includes software developed by the University of 21198090Srdivacky * California, Berkeley and its contributors. 22193323Sed * 4. Neither the name of the University nor the names of its contributors 23193323Sed * may be used to endorse or promote products derived from this software 24193323Sed * without specific prior written permission. 25193323Sed * 26198090Srdivacky * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27198090Srdivacky * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28198090Srdivacky * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29198090Srdivacky * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30198090Srdivacky * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31193323Sed * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32193323Sed * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33193323Sed * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34193323Sed * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35193323Sed * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36193323Sed * SUCH DAMAGE. 37193323Sed * 38193323Sed * @(#)hash.h 8.1 (Berkeley) 6/6/93 39193323Sed */ 40193323Sed 41198090Srdivacky/* hash.h -- 42198090Srdivacky * 43198090Srdivacky * This file contains definitions used by the hash module, 44198090Srdivacky * which maintains hash tables. 45193323Sed */ 46193323Sed 47193323Sed#ifndef _HASH 48193323Sed#define _HASH 49193323Sed 50193323Sed/* 51193323Sed * The following defines one entry in the hash table. 52193323Sed */ 53198090Srdivacky 54198090Srdivackytypedef struct Hash_Entry { 55207618Srdivacky struct Hash_Entry *next; /* Used to link together all the 56193323Sed * entries associated with the same 57193323Sed * bucket. */ 58193323Sed ClientData clientData; /* Arbitrary piece of data associated 59193323Sed * with key. */ 60193323Sed unsigned namehash; /* hash value of key */ 61193323Sed char name[1]; /* key string */ 62218885Sdim} Hash_Entry; 63218885Sdim 64193323Sedtypedef struct Hash_Table { 65193323Sed struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one 66193323Sed * for each bucket in the table. */ 67193323Sed int size; /* Actual size of array. */ 68198090Srdivacky int numEntries; /* Number of entries in the table. */ 69198090Srdivacky int mask; /* Used to select bits for hashing. */ 70198090Srdivacky} Hash_Table; 71198090Srdivacky 72193323Sed/* 73198090Srdivacky * The following structure is used by the searching routines 74198090Srdivacky * to record where we are in the search. 75193323Sed */ 76198090Srdivacky 77193323Sedtypedef struct Hash_Search { 78193323Sed Hash_Table *tablePtr; /* Table being searched. */ 79193323Sed int nextIndex; /* Next bucket to check (after current). */ 80218885Sdim Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ 81193323Sed} Hash_Search; 82193323Sed 83198090Srdivacky/* 84198090Srdivacky * Macros. 85198090Srdivacky */ 86198090Srdivacky 87198090Srdivacky/* 88207618Srdivacky * ClientData Hash_GetValue(h) 89198090Srdivacky * Hash_Entry *h; 90198090Srdivacky */ 91198090Srdivacky 92198090Srdivacky#define Hash_GetValue(h) ((h)->clientData) 93198090Srdivacky 94198090Srdivacky/* 95198090Srdivacky * Hash_SetValue(h, val); 96198090Srdivacky * Hash_Entry *h; 97198090Srdivacky * char *val; 98198090Srdivacky */ 99198090Srdivacky 100193323Sed#define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val)) 101198090Srdivacky 102198090Srdivacky/* 103198090Srdivacky * Hash_Size(n) returns the number of words in an object of n bytes 104198090Srdivacky */ 105198090Srdivacky 106198090Srdivacky#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) 107198090Srdivacky 108198090Srdivackyvoid Hash_InitTable __P((Hash_Table *, int)); 109193323Sedvoid Hash_DeleteTable __P((Hash_Table *)); 110198090SrdivackyHash_Entry *Hash_FindEntry __P((Hash_Table *, char *)); 111198090SrdivackyHash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *)); 112198090Srdivackyvoid Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *)); 113198090SrdivackyHash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *)); 114198090SrdivackyHash_Entry *Hash_EnumNext __P((Hash_Search *)); 115198090Srdivacky 116198090Srdivacky#endif /* _HASH */ 117198090Srdivacky