1 /* 2 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. 3 * Copyright (c) 1988, 1989 by Adam de Boor 4 * Copyright (c) 1989 by Berkeley Softworks 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Adam de Boor. 9 * 10 * %sccs.include.redist.c% 11 * 12 * @(#)hash.h 5.3 (Berkeley) 06/01/90 13 */ 14 15 /* hash.h -- 16 * 17 * This file contains definitions used by the hash module, 18 * which maintains hash tables. 19 */ 20 21 #ifndef _HASH 22 #define _HASH 23 24 #include "list.h" 25 /* 26 * The following defines one entry in the hash table. 27 */ 28 29 typedef struct Hash_Entry { 30 List_Links links; /* Used to link together all the 31 * entries associated with the same 32 * bucket. */ 33 ClientData clientData; /* Arbitrary piece of data associated 34 * with key. */ 35 union { 36 Address ptr; /* One-word key value to identify 37 * entry. */ 38 int words[1]; /* N-word key value. Note: the actual 39 * size may be longer if necessary to 40 * hold the entire key. */ 41 char name[4]; /* Text name of this entry. Note: the 42 * actual size may be longer if 43 * necessary to hold the whole string. 44 * This MUST be the last entry in the 45 * structure!!! */ 46 } key; 47 } Hash_Entry; 48 49 /* 50 * A hash table consists of an array of pointers to hash 51 * lists. Tables can be organized in either of three ways, depending 52 * on the type of comparison keys: 53 * 54 * Strings: these are NULL-terminated; their address 55 * is passed to HashFind as a (char *). 56 * Single-word keys: these may be anything, but must be passed 57 * to Hash_Find as an Address. 58 * Multi-word keys: these may also be anything; their address 59 * is passed to HashFind as an Address. 60 * 61 * Single-word keys are fastest, but most restrictive. 62 */ 63 64 #define HASH_STRING_KEYS 0 65 #define HASH_ONE_WORD_KEYS 1 66 67 typedef struct Hash_Table { 68 List_Links *bucketPtr; /* Pointer to array of List_Links, one 69 * for each bucket in the table. */ 70 int size; /* Actual size of array. */ 71 int numEntries; /* Number of entries in the table. */ 72 int downShift; /* Shift count, used in hashing function. */ 73 int mask; /* Used to select bits for hashing. */ 74 int keyType; /* Type of keys used in table: 75 * HASH_STRING_KEYS, HASH_ONE-WORD_KEYS, 76 * or >1 menas keyType gives number of words 77 * in keys. 78 */ 79 } Hash_Table; 80 81 /* 82 * The following structure is used by the searching routines 83 * to record where we are in the search. 84 */ 85 86 typedef struct Hash_Search { 87 Hash_Table *tablePtr; /* Table being searched. */ 88 int nextIndex; /* Next bucket to check (after current). */ 89 Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ 90 List_Links *hashList; /* Hash chain currently being checked. */ 91 } Hash_Search; 92 93 /* 94 * Macros. 95 */ 96 97 /* 98 * ClientData Hash_GetValue(h) 99 * Hash_Entry *h; 100 */ 101 102 #define Hash_GetValue(h) ((h)->clientData) 103 104 /* 105 * Hash_SetValue(h, val); 106 * HashEntry *h; 107 * char *val; 108 */ 109 110 #define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val)) 111 112 /* 113 * Hash_Size(n) returns the number of words in an object of n bytes 114 */ 115 116 #define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) 117 118 /* 119 * The following procedure declarations and macros 120 * are the only things that should be needed outside 121 * the implementation code. 122 */ 123 124 extern Hash_Entry * Hash_CreateEntry(); 125 extern void Hash_DeleteTable(); 126 extern void Hash_DeleteEntry(); 127 extern void Hash_DeleteTable(); 128 extern Hash_Entry * Hash_EnumFirst(); 129 extern Hash_Entry * Hash_EnumNext(); 130 extern Hash_Entry * Hash_FindEntry(); 131 extern void Hash_InitTable(); 132 extern void Hash_PrintStats(); 133 134 #endif _HASH 135