hash.h revision 5814
11590Srgrimes/* 25814Sjkh * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 35814Sjkh * Copyright (c) 1988, 1989 by Adam de Boor 41590Srgrimes * Copyright (c) 1989 by Berkeley Softworks 51590Srgrimes * All rights reserved. 61590Srgrimes * 71590Srgrimes * This code is derived from software contributed to Berkeley by 81590Srgrimes * Adam de Boor. 91590Srgrimes * 101590Srgrimes * Redistribution and use in source and binary forms, with or without 111590Srgrimes * modification, are permitted provided that the following conditions 121590Srgrimes * are met: 131590Srgrimes * 1. Redistributions of source code must retain the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer. 151590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 161590Srgrimes * notice, this list of conditions and the following disclaimer in the 171590Srgrimes * documentation and/or other materials provided with the distribution. 181590Srgrimes * 3. All advertising materials mentioning features or use of this software 191590Srgrimes * must display the following acknowledgement: 201590Srgrimes * This product includes software developed by the University of 211590Srgrimes * California, Berkeley and its contributors. 221590Srgrimes * 4. Neither the name of the University nor the names of its contributors 231590Srgrimes * may be used to endorse or promote products derived from this software 241590Srgrimes * without specific prior written permission. 251590Srgrimes * 261590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 271590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 281590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 291590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 301590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 311590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 321590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 331590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 341590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 351590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 361590Srgrimes * SUCH DAMAGE. 371590Srgrimes * 381590Srgrimes * @(#)hash.h 8.1 (Berkeley) 6/6/93 391590Srgrimes */ 401590Srgrimes 411590Srgrimes/* hash.h -- 421590Srgrimes * 431590Srgrimes * This file contains definitions used by the hash module, 441590Srgrimes * which maintains hash tables. 451590Srgrimes */ 461590Srgrimes 471590Srgrimes#ifndef _HASH 481590Srgrimes#define _HASH 491590Srgrimes 501590Srgrimes/* 511590Srgrimes * The following defines one entry in the hash table. 521590Srgrimes */ 531590Srgrimes 541590Srgrimestypedef struct Hash_Entry { 551590Srgrimes struct Hash_Entry *next; /* Used to link together all the 561590Srgrimes * entries associated with the same 571590Srgrimes * bucket. */ 581590Srgrimes ClientData clientData; /* Arbitrary piece of data associated 591590Srgrimes * with key. */ 601590Srgrimes unsigned namehash; /* hash value of key */ 611590Srgrimes char name[1]; /* key string */ 621590Srgrimes} Hash_Entry; 631590Srgrimes 641590Srgrimestypedef struct Hash_Table { 651590Srgrimes struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one 661590Srgrimes * for each bucket in the table. */ 671590Srgrimes int size; /* Actual size of array. */ 681590Srgrimes int numEntries; /* Number of entries in the table. */ 691590Srgrimes int mask; /* Used to select bits for hashing. */ 701590Srgrimes} Hash_Table; 711590Srgrimes 721590Srgrimes/* 731590Srgrimes * The following structure is used by the searching routines 741590Srgrimes * to record where we are in the search. 751590Srgrimes */ 761590Srgrimes 771590Srgrimestypedef struct Hash_Search { 781590Srgrimes Hash_Table *tablePtr; /* Table being searched. */ 791590Srgrimes int nextIndex; /* Next bucket to check (after current). */ 801590Srgrimes Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ 811590Srgrimes} Hash_Search; 821590Srgrimes 831590Srgrimes/* 841590Srgrimes * Macros. 851590Srgrimes */ 861590Srgrimes 871590Srgrimes/* 881590Srgrimes * ClientData Hash_GetValue(h) 891590Srgrimes * Hash_Entry *h; 901590Srgrimes */ 911590Srgrimes 921590Srgrimes#define Hash_GetValue(h) ((h)->clientData) 931590Srgrimes 941590Srgrimes/* 951590Srgrimes * Hash_SetValue(h, val); 961590Srgrimes * Hash_Entry *h; 971590Srgrimes * char *val; 981590Srgrimes */ 991590Srgrimes 1001590Srgrimes#define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val)) 1011590Srgrimes 1021590Srgrimes/* 1031590Srgrimes * Hash_Size(n) returns the number of words in an object of n bytes 1041590Srgrimes */ 1051590Srgrimes 1061590Srgrimes#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) 1071590Srgrimes 1085814Sjkhvoid Hash_InitTable __P((Hash_Table *, int)); 1095814Sjkhvoid Hash_DeleteTable __P((Hash_Table *)); 1105814SjkhHash_Entry *Hash_FindEntry __P((Hash_Table *, char *)); 1115814SjkhHash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *)); 1125814Sjkhvoid Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *)); 1135814SjkhHash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *)); 1145814SjkhHash_Entry *Hash_EnumNext __P((Hash_Search *)); 1151590Srgrimes 1161590Srgrimes#endif /* _HASH */ 117