bmake/dist/hash.h

/*      $NetBSD: hash.h,v 1.12 2017/05/31 21:07:03 maya Exp $   */

/*
 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * 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. 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 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.
 *
 *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
 */

/*
 * Copyright (c) 1988, 1989 by Adam de Boor
 * 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, 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.
 *
 * 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.
 *
 *      from: @(#)hash.h        8.1 (Berkeley) 6/6/93
 */

/* hash.h --
 *
 *      This file contains definitions used by the hash module,
 *      which maintains hash tables.
 */

#ifndef _HASH_H
#define _HASH_H

/*
 * The following defines one entry in the hash table.
 */

typedef struct Hash_Entry {
    struct Hash_Entry *next;            /* Used to link together all the
                                         * entries associated with the same
                                         * bucket. */
    void              *clientPtr;       /* Arbitrary pointer */
    unsigned          namehash;         /* hash value of key */
    char              name[1];          /* key string */
} Hash_Entry;

typedef struct Hash_Table {
    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         mask;           /* Used to select bits for hashing. */
} Hash_Table;

/*
 * The following structure is used by the searching routines
 * to record where we are in the search.
 */

typedef struct Hash_Search {
    Hash_Table  *tablePtr;      /* Table being searched. */
    int         nextIndex;      /* Next bucket to check (after current). */
    Hash_Entry  *hashEntryPtr;  /* Next entry to check in current bucket. */
} Hash_Search;

/*
 * Macros.
 */

/*
 * void * Hash_GetValue(h)
 *     Hash_Entry *h;
 */

#define Hash_GetValue(h) ((h)->clientPtr)

/*
 * Hash_SetValue(h, val);
 *     Hash_Entry *h;
 *     char *val;
 */

#define Hash_SetValue(h, val) ((h)->clientPtr = (val))

/*
 * Hash_Size(n) returns the number of words in an object of n bytes
 */

#define Hash_Size(n)    (((n) + sizeof (int) - 1) / sizeof (int))

void Hash_InitTable(Hash_Table *, int);
void Hash_DeleteTable(Hash_Table *);
Hash_Entry *Hash_FindEntry(Hash_Table *, const char *);
Hash_Entry *Hash_CreateEntry(Hash_Table *, const char *, Boolean *);
void Hash_DeleteEntry(Hash_Table *, Hash_Entry *);
Hash_Entry *Hash_EnumFirst(Hash_Table *, Hash_Search *);
Hash_Entry *Hash_EnumNext(Hash_Search *);

#endif /* _HASH_H */
Revision:	11138
Committed:	Wed Jun 27 00:17:22 2018 UTC (5 years, 10 months ago) by laffer1
Content type:	text/plain
File size:	5692 byte(s)
Log Message:	update bmake to 20170720
#	Content
1	/* $NetBSD: hash.h,v 1.12 2017/05/31 21:07:03 maya Exp $ */
2
3	/*
4	* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
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	/*
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	*
72	* from: @(#)hash.h 8.1 (Berkeley) 6/6/93
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_H
82	#define _HASH_H
83
84	/*
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. */
92	void clientPtr; / Arbitrary pointer */
93	unsigned namehash; /* hash value of key */
94	char name[1]; /* key string */
95	} Hash_Entry;
96
97	typedef struct Hash_Table {
98	struct Hash_Entry *bucketPtr;/ Pointers to Hash_Entry, one
99	* for each bucket in the table. */
100	int size; /* Actual size of array. */
101	int numEntries; /* Number of entries in the table. */
102	int mask; /* Used to select bits for hashing. */
103	} Hash_Table;
104
105	/*
106	* The following structure is used by the searching routines
107	* to record where we are in the search.
108	*/
109
110	typedef struct Hash_Search {
111	Hash_Table tablePtr; / Table being searched. */
112	int nextIndex; /* Next bucket to check (after current). */
113	Hash_Entry hashEntryPtr; / Next entry to check in current bucket. */
114	} Hash_Search;
115
116	/*
117	* Macros.
118	*/
119
120	/*
121	* void * Hash_GetValue(h)
122	* Hash_Entry *h;
123	*/
124
125	#define Hash_GetValue(h) ((h)->clientPtr)
126
127	/*
128	* Hash_SetValue(h, val);
129	* Hash_Entry *h;
130	* char *val;
131	*/
132
133	#define Hash_SetValue(h, val) ((h)->clientPtr = (val))
134
135	/*
136	* Hash_Size(n) returns the number of words in an object of n bytes
137	*/
138
139	#define Hash_Size(n) (((n) + sizeof (int) - 1) / sizeof (int))
140
141	void Hash_InitTable(Hash_Table *, int);
142	void Hash_DeleteTable(Hash_Table *);
143	Hash_Entry Hash_FindEntry(Hash_Table , const char *);
144	Hash_Entry Hash_CreateEntry(Hash_Table , const char , Boolean );
145	void Hash_DeleteEntry(Hash_Table , Hash_Entry );
146	Hash_Entry Hash_EnumFirst(Hash_Table , Hash_Search *);
147	Hash_Entry Hash_EnumNext(Hash_Search );
148
149	#endif /* _HASH_H */