Commit | Line | Data |
---|---|---|
b0ff1758 KB |
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. | |
fe902645 | 6 | * |
b0ff1758 KB |
7 | * This code is derived from software contributed to Berkeley by |
8 | * Adam de Boor. | |
fe902645 | 9 | * |
af359dea C |
10 | * Redistribution and use in source and binary forms, with or without |
11 | * modification, are permitted provided that the following conditions | |
12 | * are met: | |
13 | * 1. Redistributions of source code must retain the above copyright | |
14 | * notice, this list of conditions and the following disclaimer. | |
15 | * 2. Redistributions in binary form must reproduce the above copyright | |
16 | * notice, this list of conditions and the following disclaimer in the | |
17 | * documentation and/or other materials provided with the distribution. | |
18 | * 3. All advertising materials mentioning features or use of this software | |
19 | * must display the following acknowledgement: | |
20 | * This product includes software developed by the University of | |
21 | * California, Berkeley and its contributors. | |
22 | * 4. Neither the name of the University nor the names of its contributors | |
23 | * may be used to endorse or promote products derived from this software | |
24 | * without specific prior written permission. | |
fe902645 | 25 | * |
af359dea C |
26 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
27 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
28 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
29 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
30 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
31 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
32 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
33 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
34 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
35 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
36 | * SUCH DAMAGE. | |
37 | * | |
38 | * @(#)hash.h 5.4 (Berkeley) 12/28/90 | |
fe902645 KB |
39 | */ |
40 | ||
b0ff1758 KB |
41 | /* hash.h -- |
42 | * | |
43 | * This file contains definitions used by the hash module, | |
44 | * which maintains hash tables. | |
45 | */ | |
fe902645 KB |
46 | |
47 | #ifndef _HASH | |
48 | #define _HASH | |
49 | ||
fe902645 KB |
50 | /* |
51 | * The following defines one entry in the hash table. | |
52 | */ | |
53 | ||
54 | typedef struct Hash_Entry { | |
fc46faab | 55 | struct Hash_Entry *next; /* Used to link together all the |
fe902645 KB |
56 | * entries associated with the same |
57 | * bucket. */ | |
58 | ClientData clientData; /* Arbitrary piece of data associated | |
59 | * with key. */ | |
fc46faab KB |
60 | unsigned namehash; /* hash value of key */ |
61 | char name[1]; /* key string */ | |
fe902645 KB |
62 | } Hash_Entry; |
63 | ||
fe902645 | 64 | typedef struct Hash_Table { |
fc46faab | 65 | struct Hash_Entry **bucketPtr;/* Pointers to Hash_Entry, one |
fe902645 KB |
66 | * for each bucket in the table. */ |
67 | int size; /* Actual size of array. */ | |
68 | int numEntries; /* Number of entries in the table. */ | |
fe902645 | 69 | int mask; /* Used to select bits for hashing. */ |
fe902645 KB |
70 | } Hash_Table; |
71 | ||
72 | /* | |
73 | * The following structure is used by the searching routines | |
74 | * to record where we are in the search. | |
75 | */ | |
76 | ||
77 | typedef struct Hash_Search { | |
78 | Hash_Table *tablePtr; /* Table being searched. */ | |
79 | int nextIndex; /* Next bucket to check (after current). */ | |
80 | Hash_Entry *hashEntryPtr; /* Next entry to check in current bucket. */ | |
fe902645 KB |
81 | } Hash_Search; |
82 | ||
83 | /* | |
84 | * Macros. | |
85 | */ | |
86 | ||
87 | /* | |
88 | * ClientData Hash_GetValue(h) | |
89 | * Hash_Entry *h; | |
90 | */ | |
91 | ||
92 | #define Hash_GetValue(h) ((h)->clientData) | |
93 | ||
94 | /* | |
95 | * Hash_SetValue(h, val); | |
fc46faab | 96 | * Hash_Entry *h; |
fe902645 KB |
97 | * char *val; |
98 | */ | |
99 | ||
100 | #define Hash_SetValue(h, val) ((h)->clientData = (ClientData) (val)) | |
101 | ||
102 | /* | |
103 | * Hash_Size(n) returns the number of words in an object of n bytes | |
104 | */ | |
105 | ||
106 | #define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int)) | |
107 | ||
108 | /* | |
109 | * The following procedure declarations and macros | |
110 | * are the only things that should be needed outside | |
111 | * the implementation code. | |
112 | */ | |
113 | ||
114 | extern Hash_Entry * Hash_CreateEntry(); | |
115 | extern void Hash_DeleteTable(); | |
116 | extern void Hash_DeleteEntry(); | |
117 | extern void Hash_DeleteTable(); | |
118 | extern Hash_Entry * Hash_EnumFirst(); | |
119 | extern Hash_Entry * Hash_EnumNext(); | |
120 | extern Hash_Entry * Hash_FindEntry(); | |
121 | extern void Hash_InitTable(); | |
122 | extern void Hash_PrintStats(); | |
123 | ||
124 | #endif _HASH |