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