/*
- * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
- * Copyright (c) 1988, 1989 by Adam de Boor
+ * Copyright (c) 1988, 1989, 1990, 1993
+ * The Regents of the University of California. All rights reserved.
* Copyright (c) 1989 by Berkeley Softworks
* All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Adam de Boor.
*
- * Redistribution and use in source and binary forms are permitted
- * provided that: (1) source distributions retain this entire copyright
- * notice and comment, and (2) distributions including binaries display
- * the following acknowledgement: ``This product includes software
- * developed by the University of California, Berkeley and its contributors''
- * in the documentation or other materials provided with the distribution
- * and in all advertising materials mentioning features or use of this
- * software. Neither the name of the University nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
*
- * @(#)hash.h 5.3 (Berkeley) 6/1/90
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * @(#)hash.h 8.1 (Berkeley) 6/6/93
*/
/* hash.h --
#ifndef _HASH
#define _HASH
-#include "list.h"
/*
* The following defines one entry in the hash table.
*/
typedef struct Hash_Entry {
- List_Links links; /* Used to link together all the
+ struct Hash_Entry *next; /* Used to link together all the
* entries associated with the same
* bucket. */
ClientData clientData; /* Arbitrary piece of data associated
* with key. */
- union {
- Address ptr; /* One-word key value to identify
- * entry. */
- int words[1]; /* N-word key value. Note: the actual
- * size may be longer if necessary to
- * hold the entire key. */
- char name[4]; /* Text name of this entry. Note: the
- * actual size may be longer if
- * necessary to hold the whole string.
- * This MUST be the last entry in the
- * structure!!! */
- } key;
+ unsigned namehash; /* hash value of key */
+ char name[1]; /* key string */
} Hash_Entry;
-/*
- * A hash table consists of an array of pointers to hash
- * lists. Tables can be organized in either of three ways, depending
- * on the type of comparison keys:
- *
- * Strings: these are NULL-terminated; their address
- * is passed to HashFind as a (char *).
- * Single-word keys: these may be anything, but must be passed
- * to Hash_Find as an Address.
- * Multi-word keys: these may also be anything; their address
- * is passed to HashFind as an Address.
- *
- * Single-word keys are fastest, but most restrictive.
- */
-
-#define HASH_STRING_KEYS 0
-#define HASH_ONE_WORD_KEYS 1
-
typedef struct Hash_Table {
- List_Links *bucketPtr; /* Pointer to array of List_Links, one
+ struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one
* for each bucket in the table. */
int size; /* Actual size of array. */
int numEntries; /* Number of entries in the table. */
- int downShift; /* Shift count, used in hashing function. */
int mask; /* Used to select bits for hashing. */
- int keyType; /* Type of keys used in table:
- * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS,
- * or >1 menas keyType gives number of words
- * in keys.
- */
} Hash_Table;
/*
Hash_Table *tablePtr; /* Table being searched. */
int nextIndex; /* Next bucket to check (after current). */
Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */
- List_Links *hashList; /* Hash chain currently being checked. */
} Hash_Search;
/*
/*
* Hash_SetValue(h, val);
- * HashEntry *h;
+ * Hash_Entry *h;
* char *val;
*/
#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int))
-/*
- * The following procedure declarations and macros
- * are the only things that should be needed outside
- * the implementation code.
- */
+Hash_Entry *Hash_CreateEntry __P((Hash_Table *, char *, Boolean *));
+void Hash_DeleteEntry __P((Hash_Table *, Hash_Entry *));
+void Hash_DeleteTable __P((Hash_Table *));
+Hash_Entry *Hash_EnumFirst __P((Hash_Table *, Hash_Search *));
+Hash_Entry *Hash_EnumNext __P((Hash_Search *));
+Hash_Entry *Hash_FindEntry __P((Hash_Table *, char *));
+void Hash_InitTable __P((Hash_Table *, int));
-extern Hash_Entry * Hash_CreateEntry();
-extern void Hash_DeleteTable();
-extern void Hash_DeleteEntry();
-extern void Hash_DeleteTable();
-extern Hash_Entry * Hash_EnumFirst();
-extern Hash_Entry * Hash_EnumNext();
-extern Hash_Entry * Hash_FindEntry();
-extern void Hash_InitTable();
-extern void Hash_PrintStats();
-
-#endif _HASH
+#endif /* _HASH */