1173412Skevlo/* $FreeBSD: releng/10.3/sbin/rcorder/hash.h 173412 2007-11-07 10:53:41Z kevlo $ */ 278344Sobrien/* $NetBSD: hash.h,v 1.1.1.1 1999/11/19 04:30:56 mrg Exp $ */ 378344Sobrien 478344Sobrien/* 578344Sobrien * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 678344Sobrien * Copyright (c) 1988, 1989 by Adam de Boor 778344Sobrien * Copyright (c) 1989 by Berkeley Softworks 878344Sobrien * All rights reserved. 978344Sobrien * 1078344Sobrien * This code is derived from software contributed to Berkeley by 1178344Sobrien * Adam de Boor. 1278344Sobrien * 1378344Sobrien * Redistribution and use in source and binary forms, with or without 1478344Sobrien * modification, are permitted provided that the following conditions 1578344Sobrien * are met: 1678344Sobrien * 1. Redistributions of source code must retain the above copyright 1778344Sobrien * notice, this list of conditions and the following disclaimer. 1878344Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1978344Sobrien * notice, this list of conditions and the following disclaimer in the 2078344Sobrien * documentation and/or other materials provided with the distribution. 2178344Sobrien * 3. All advertising materials mentioning features or use of this software 2278344Sobrien * must display the following acknowledgement: 2378344Sobrien * This product includes software developed by the University of 2478344Sobrien * California, Berkeley and its contributors. 2578344Sobrien * 4. Neither the name of the University nor the names of its contributors 2678344Sobrien * may be used to endorse or promote products derived from this software 2778344Sobrien * without specific prior written permission. 2878344Sobrien * 2978344Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 3078344Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 3178344Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 3278344Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 3378344Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 3478344Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3578344Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3678344Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3778344Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3878344Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3978344Sobrien * SUCH DAMAGE. 4078344Sobrien * 4178344Sobrien * from: @(#)hash.h 8.1 (Berkeley) 6/6/93 4278344Sobrien */ 4378344Sobrien 4478344Sobrien/* hash.h -- 4578344Sobrien * 4678344Sobrien * This file contains definitions used by the hash module, 4778344Sobrien * which maintains hash tables. 4878344Sobrien */ 4978344Sobrien 5078344Sobrien#ifndef _HASH 5178344Sobrien#define _HASH 5278344Sobrien 5378344Sobrien/* 5478344Sobrien * The following defines one entry in the hash table. 5578344Sobrien */ 5678344Sobrien 5778344Sobrientypedef struct Hash_Entry { 5878344Sobrien struct Hash_Entry *next; /* Used to link together all the 5978344Sobrien * entries associated with the same 6078344Sobrien * bucket. */ 6178344Sobrien ClientData clientData; /* Arbitrary piece of data associated 6278344Sobrien * with key. */ 6378344Sobrien unsigned namehash; /* hash value of key */ 6478344Sobrien char name[1]; /* key string */ 6578344Sobrien} Hash_Entry; 6678344Sobrien 6778344Sobrientypedef struct Hash_Table { 6878344Sobrien struct Hash_Entry **bucketPtr; 6978344Sobrien /* Pointers to Hash_Entry, one 7078344Sobrien * for each bucket in the table. */ 7178344Sobrien int size; /* Actual size of array. */ 7278344Sobrien int numEntries; /* Number of entries in the table. */ 7378344Sobrien int mask; /* Used to select bits for hashing. */ 7478344Sobrien} Hash_Table; 7578344Sobrien 7678344Sobrien/* 7778344Sobrien * The following structure is used by the searching routines 7878344Sobrien * to record where we are in the search. 7978344Sobrien */ 8078344Sobrien 8178344Sobrientypedef struct Hash_Search { 8278344Sobrien Hash_Table *tablePtr; /* Table being searched. */ 8378344Sobrien int nextIndex; /* Next bucket to check (after 8478344Sobrien * current). */ 8578344Sobrien Hash_Entry *hashEntryPtr; /* Next entry to check in current 8678344Sobrien * bucket. */ 8778344Sobrien} Hash_Search; 8878344Sobrien 8978344Sobrien/* 9078344Sobrien * Macros. 9178344Sobrien */ 9278344Sobrien 9378344Sobrien/* 9478344Sobrien * ClientData Hash_GetValue(h) 9578344Sobrien * Hash_Entry *h; 9678344Sobrien */ 9778344Sobrien 9878344Sobrien#define Hash_GetValue(h) ((h)->clientData) 9978344Sobrien 10078344Sobrien/* 10178344Sobrien * Hash_SetValue(h, val); 10278344Sobrien * Hash_Entry *h; 10378344Sobrien * char *val; 10478344Sobrien */ 10578344Sobrien 10678344Sobrien#define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val)) 10778344Sobrien 10878344Sobrien#ifdef ORDER 10978344Sobrien/* 11078344Sobrien * Hash_GetKey(h); 11178344Sobrien * Hash_Entry *h; 11278344Sobrien */ 11378344Sobrien 11478344Sobrien#define Hash_GetKey(h) ((h)->name) 11578344Sobrien#endif /* ORDER */ 11678344Sobrien 11778344Sobrien/* 11878344Sobrien * Hash_Size(n) returns the number of words in an object of n bytes 11978344Sobrien */ 12078344Sobrien 12178344Sobrien#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) 12278344Sobrien 123173412Skevlovoid Hash_InitTable(Hash_Table *, int); 124173412Skevlovoid Hash_DeleteTable(Hash_Table *); 125173412SkevloHash_Entry *Hash_FindEntry(Hash_Table *, char *); 126173412SkevloHash_Entry *Hash_CreateEntry(Hash_Table *, char *, Boolean *); 127173412Skevlovoid Hash_DeleteEntry(Hash_Table *, Hash_Entry *); 128173412SkevloHash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *); 129173412SkevloHash_Entry *Hash_EnumNext(Hash_Search *); 13078344Sobrien 13178344Sobrien#endif /* _HASH */ 132