1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                 Eclipse Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *          http://www.eclipse.org/org/documents/epl-v10.html           *
11 *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
12 *                                                                      *
13 *              Information and Software Systems Research               *
14 *                            AT&T Research                             *
15 *                           Florham Park NJ                            *
16 *                                                                      *
17 *                 Glenn Fowler <gsf@research.att.com>                  *
18 *                  David Korn <dgk@research.att.com>                   *
19 *                   Phong Vo <kpv@research.att.com>                    *
20 *                                                                      *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24  * Glenn Fowler
25  * AT&T Research
26  *
27  * hash table library interface definitions
28  *
29  * NOTE: new code should use the more general <cdt.h>
30  */
31 
32 #ifndef _HASH_H
33 #define _HASH_H
34 
35 #define HASH_ALLOCATE	(1L<<0)		/* allocate new key names	*/
36 #define HASH_FIXED	(1L<<1)		/* fixed table size		*/
37 #define HASH_HASHED	(1L<<6)		/* key names already hashed	*/
38 #define HASH_RESIZE	(1L<<2)		/* table has been resized	*/
39 #define HASH_SCANNING	(1L<<3)		/* currently scanning scope	*/
40 #define HASH_SCOPE	(1L<<4)		/* push scope / create in bot	*/
41 #define HASH_STATIC	(1L<<5)		/* static table allocation	*/
42 
43 #define HASH_CREATE	(1L<<8)		/* create bucket if not found	*/
44 #define HASH_DELETE	(1L<<9)		/* delete bucket if found	*/
45 #define HASH_LOOKUP	0		/* default op			*/
46 #define HASH_RENAME	(1L<<7)		/* rename bucket if found	*/
47 
48 #define HASH_BUCKET	(1L<<11)	/* name is installed bucket	*/
49 #define HASH_INSTALL	(1L<<12)	/* install allocated bucket	*/
50 #define HASH_NOSCOPE	(1L<<13)	/* top scope only		*/
51 #define HASH_OPAQUE	(1L<<14)	/* opaque bucket		*/
52 #define HASH_VALUE	(1L<<15)	/* value bucket field used	*/
53 
54 #define HASH_SIZE(n)	(((long)(n))<<16)  /* fixed bucket size		*/
55 #define HASH_SIZEOF(f)	((((long)(f))>>16)&0xffff) /* extract size	*/
56 
57 #define HASH_DELETED	((unsigned long)1<<(8*sizeof(int)-1)) /* deleted placeholder	*/
58 #define HASH_KEEP	(1L<<(8*sizeof(int)-2))	/* no free on bucket	*/
59 #define HASH_HIDDEN	(1L<<(8*sizeof(int)-3))	/* hidden by scope	*/
60 #define HASH_HIDES	(1L<<(8*sizeof(int)-4))	/* hides lower scope	*/
61 #define HASH_OPAQUED	(1L<<(8*sizeof(int)-5))	/* opaqued placeholder	*/
62 #define HASH_FREENAME	(1L<<(8*sizeof(int)-6))	/* free bucket name	*/
63 
64 #define HASH_RESET	(HASH_RESIZE|HASH_SCOPE|HASH_STATIC|HASH_VALUE)
65 #define HASH_INTERNAL	(HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
66 #define HASH_FLAGS	(HASH_DELETED|HASH_FREENAME|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
67 
68 #define HASH_alloc		1
69 #define HASH_clear		2
70 #define HASH_compare		3
71 #define HASH_free		4
72 #define HASH_hash		5
73 #define HASH_meanchain		6
74 #define HASH_name		7
75 #define HASH_namesize		8
76 #define HASH_set		9
77 #define HASH_size		10
78 #define HASH_table		11
79 #define HASH_va_list		12
80 
81 #define HASH_bucketsize		13
82 
83 #define HASH_region		14
84 
85 #include <hashpart.h>
86 
87 #define hashclear(t,f)		((t)->flags &= ~((f) & ~HASH_INTERNAL))
88 #define hashcover(b)		(((b)->hash&HASH_HIDES)?(Hash_bucket_t*)((b)->name):(Hash_bucket_t*)0)
89 #define hashdel(t,n)		hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
90 #define hashget(t,n)		hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
91 #define hashgetbucket(s)	((Hash_bucket_t*)((s)-((sizeof(Hash_bucket_t)+sizeof(char*)-1)/sizeof(char*))*sizeof(char*)))
92 #define hashkeep(b)		((b)->hash|=HASH_KEEP)
93 #define hashname(b)		((((b)->hash&HASH_HIDES)?((Hash_bucket_t*)((b)->name)):(b))->name)
94 #define hashput(t,n,v)		hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
95 #define hashref(t,n)		hashlook(t, (char*)(n), HASH_LOOKUP|HASH_INTERNAL|HASH_VALUE, (char*)0)
96 #define hashscope(t)		((t)->scope)
97 #define hashset(t,f)		((t)->flags |= ((f) & ~HASH_INTERNAL))
98 
99 /*
100  * DEPRECATED renames for compatibility
101  */
102 
103 #define Hashbin_t		Hash_bucket_t
104 #define HASHBUCKET		Hash_bucket_t
105 #define Hashhdr_t 		Hash_header_t
106 #define HASHHEADER 		Hash_header_t
107 #define Hashpos_t 		Hash_position_t
108 #define HASHPOSITION 		Hash_position_t
109 #define Hashtab_t		Hash_table_t
110 #define HASHTABLE		Hash_table_t
111 
112 #define vhashalloc		hashvalloc
113 #define hashvalloc(t,a)		hashalloc(t,HASH_va_list,a,0)
114 
115 /*
116  * the #define's avoid union tags
117  */
118 
119 typedef struct Hash_bucket Hash_bucket_t;
120 typedef struct Hash_root Hash_root_t;
121 typedef struct Hash_table Hash_table_t;
122 
123 #define HASH_HEADER			/* common bucket header		*/ \
124 	Hash_bucket_t*	next;		/* next in collision chain	*/ \
125 	unsigned int	hash;		/* hash flags and value		*/ \
126 	char*		name		/* key name			*/
127 
128 #define HASH_DEFAULT			/* HASH_VALUE bucket elements	*/ \
129 	char*		value		/* key value			*/
130 
131 typedef struct				/* bucket header		*/
132 {
133 	HASH_HEADER;
134 } Hash_header_t;
135 
136 struct Hash_bucket			/* prototype bucket		*/
137 {
138 	HASH_HEADER;
139 	HASH_DEFAULT;
140 };
141 
142 typedef struct				/* hash scan bucket position	*/
143 {
144 	Hash_bucket_t*	bucket;		/* bucket			*/
145 #ifdef _HASH_POSITION_PRIVATE_
146 	_HASH_POSITION_PRIVATE_
147 #endif
148 } Hash_position_t;
149 
150 typedef struct				/* last lookup cache		*/
151 {
152 	Hash_table_t*	table;		/* last lookup table		*/
153 	Hash_bucket_t*	bucket;		/* last lookup bucket		*/
154 #ifdef _HASH_LAST_PRIVATE_
155 	_HASH_LAST_PRIVATE_
156 #endif
157 } Hash_last_t;
158 
159 struct Hash_root			/* root hash table information	*/
160 {
161 	int		accesses;	/* number of accesses		*/
162 	int		collisions;	/* number of collisions		*/
163 	int		flags;		/* flags: see HASH_[A-Z]*	*/
164 	Hash_last_t	last;		/* last lookup cache		*/
165 	void*		context;	/* user defined context		*/
166 #ifdef _HASH_ROOT_PRIVATE_
167 	_HASH_ROOT_PRIVATE_
168 #endif
169 };
170 
171 struct Hash_table			/* hash table information	*/
172 {
173 	Hash_root_t*	root;		/* root hash table information	*/
174 	int		size;		/* table size			*/
175 	int		buckets;	/* active bucket count		*/
176 	char*		name;		/* table name			*/
177 	Hash_table_t*	scope;		/* scope covered table		*/
178 	short		flags;		/* flags: see HASH_[A-Z]*	*/
179 #ifdef _HASH_TABLE_PRIVATE_
180 	_HASH_TABLE_PRIVATE_
181 #endif
182 };
183 
184 #if _BLD_ast && defined(__EXPORT__)
185 #define extern		__EXPORT__
186 #endif
187 
188 extern Hash_table_t*	hashalloc(Hash_table_t*, ...);
189 extern void		hashdone(Hash_position_t*);
190 extern void		hashdump(Hash_table_t*, int);
191 extern Hash_table_t*	hashfree(Hash_table_t*);
192 extern Hash_bucket_t*	hashlast(Hash_table_t*);
193 extern char*		hashlook(Hash_table_t*, const char*, long, const char*);
194 extern Hash_bucket_t*	hashnext(Hash_position_t*);
195 extern Hash_position_t*	hashscan(Hash_table_t*, int);
196 extern void		hashsize(Hash_table_t*, int);
197 extern Hash_table_t*	hashview(Hash_table_t*, Hash_table_t*);
198 extern int		hashwalk(Hash_table_t*, int, int (*)(const char*, char*, void*), void*);
199 
200 #undef	extern
201 
202 #endif
203