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