Line data Source code
1 : /* fd_map_perfect defines a few macros and functions for building
2 : ultra high performance compile-time perfect hash tables.
3 :
4 : If C's preprocessor were more powerful, it might be possible to do
5 : this all automatically and fully generically, but it's not. The good
6 : thing this does provide is that it will fail to compile (with errors
7 : about override-init in GCC and initializer-overrides in Clang) if
8 : your hash function doesn't result in a perfect hash table. It takes
9 : abusing the preprocessor a little and jumping through some hoops in
10 : order to get that property.
11 :
12 : This file also supports tables with no value, in which case it is
13 : essentially a set (quickly answering containment queries). */
14 :
15 : /*
16 : Example usage:
17 :
18 : struct __attribute__((aligned(32))) key_prio {
19 : ulong key;
20 : ulong prio;
21 : };
22 : typedef struct key_prio key_prio_t;
23 :
24 : #define MAP_PERFECT_NAME key_prio_tbl // Name of the table and function prefix
25 : #define MAP_PERFECT_LG_TBL_SZ 3 // Table can fit at most 8 elements
26 : #define MAP_PERFECT_T key_prio_t // The type of each element
27 : #define MAP_PERFECT_HASH_C 650148382U // A random uint, see below for details
28 : #define MAP_PERFECT_KEY key // Name of the key field
29 : #define MAP_PERFECT_KEY_T ulong // Type of the query (typically key type)
30 : #define MAP_PERFECT_ZERO_KEY 0UL // Must be the key that's all zero bytes
31 :
32 : To add elements, just define MAP_PERFECT_i to be key, value (or values).
33 : This will eventually expand to something like
34 : { MAP_PERFECT_KEY = key, values }
35 : so using the .fieldname=value syntax is supported. Otherwise
36 : the fields will be initialized in the order they are declared in the
37 : struct.
38 :
39 : The ordering of these declarations does not matter, but you
40 : must declare at least MAP_PERFECT_0. This implies that there must be at
41 : least one element in the map, but if you know at compile time that the
42 : map is empty, why use a map in the first place? The other limitations
43 : are that the number of elements cannot exceed 1000, and the number of
44 : values in each definition line cannot exceed 100. If you're getting
45 : close to either of these limits, this file is probably not the right
46 : solution to your problem.
47 :
48 : #define MAP_PERFECT_0 44, 12
49 : #define MAP_PERFECT_1 45, .prio = 19
50 : #define MAP_PERFECT_2 17, 0
51 :
52 : #include "fd_map_perfect.c"
53 :
54 : will declare the following static inline functions in the compilation unit:
55 :
56 : // Returns 1 if the key is contained in the table, or 0 if not.
57 :
58 : static inline int key_prio_tbl_contains( ulong key );
59 :
60 : // Returns a pointer to the element in the table that has key `key` if
61 : // one exists, or the value provided as null if one doesn't.
62 :
63 : static inline key_prio_t const * key_prio_tbl_query( ulong key, key_prio_t const * null );
64 :
65 : // Returns the hash of key (using the provided perfect hash) if key is
66 : // in the table. If key is not in the table, returns UINT_MAX.
67 : static inline uint key_prio_tbl_hash_or_default( ulong key );
68 :
69 :
70 : You can do this multiple times within a compilation unit as long as
71 : MAP_PERFECT_NAME differs for the different instantiations. It's also
72 : fine to use it in a header. There are many options (detailed below) to
73 : customize the behavior.
74 :
75 : It's also totally fine to make the element type a struct containing just
76 : the key if you only need a set (containment queries). To do so, just
77 : then append a comma to the elements in the normal way, e.g.
78 : #define MAP_PERFECT_0 44,
79 : adds 44 to the set.
80 :
81 : One advanced usage is with multi-element keys (e.g. arrays). They are
82 : fully supported, but require #define MAP_PERFECT_COMPLEX_KEY 1. See
83 : below for more details. */
84 :
85 : #ifndef MAP_PERFECT_NAME
86 : #error "Define MAP_PERFECT_NAME"
87 : #endif
88 :
89 : /* MAP_PERFECT_LG_TBL_SZ is the base-2 log of the table size. See the
90 : note about MAP_PERFECT_HASH_C below for guidance on how to choose
91 : this value. It must be at least 1. */
92 :
93 : #ifndef MAP_PERFECT_LG_TBL_SZ
94 : #error "Define MAP_PERFECT_LG_TBL_SZ"
95 : #endif
96 :
97 : /* MAP_PERFECT_T is the type of each element in the perfect hash table.
98 : There are no requirements on it other than that it must contain the
99 : key. Large structs are okay, since they never get copied, but they
100 : might be a pain to const initialize. */
101 :
102 : #ifndef MAP_PERFECT_T
103 : #error "Define MAP_PERFECT_T"
104 : #endif
105 :
106 : /* MAP_PERFECT_KEY is the name of the key field in the struct. It
107 : defaults to key. */
108 : #ifndef MAP_PERFECT_KEY
109 : #define MAP_PERFECT_KEY key
110 : #endif
111 :
112 : /* MAP_PERFECT_KEY_T is the type of the query, which should typically be
113 : the key type. When using an array as a key, you may want to make
114 : this a const pointer instead of an array though. For example, if
115 : the key is uchar key[32], #define MAP_PERFECT_KEY_T uchar const * is
116 : pretty reasonable. */
117 :
118 : #ifndef MAP_PERFECT_KEY_T
119 : #error "Define MAP_PERFECT_KEY_T"
120 : #endif
121 :
122 : /* MAP_PERFECT_COMPLEX_KEY controls whether the key type is a scalar
123 : (COMPLEX_KEY==0) or an array (COMPLEX_KEY==1). If a complex key, the
124 : key should be surrounded by parenthesis, e.g.
125 : #define MAP_PERFECT_0 (1,1,1), .value=7, .other_value=8
126 :
127 : In this case, when HASH_PP is invoked, each value in the key will be
128 : a different argument to the macro. The hash of the above example
129 : will be calculated by expanding MAP_PERFECT_HASH_PP( 1, 1, 1 ), not
130 : MAP_PERFECT_HASH_PP( (1,1,1) ). */
131 :
132 : #ifndef MAP_PERFECT_COMPLEX_KEY
133 : # define MAP_PERFECT_COMPLEX_KEY 0
134 : #endif
135 :
136 : /* MAP_PERFECT_ZERO_KEY must be set to the key of all 0s. In the
137 : non-complex case, the code below probably does the right thing. The
138 : reason for this is a little strange: keys in the table that don't
139 : have a value get default initialized, which means set to all 0 bytes.
140 : We have to be able to distinguish that case from the case in which
141 : the zero key was actually inserted into the table, and we need to be
142 : able to do that at preprocessor time. Especially in the complex key
143 : case, this is not easy, so we just require specifying it manually. */
144 :
145 : #ifndef MAP_PERFECT_ZERO_KEY
146 : # if !MAP_PERFECT_COMPLEX_KEY
147 : # define MAP_PERFECT_ZERO_KEY 0
148 : # else
149 : # error "Define MAP_PERFECT_ZERO_KEY to be the key of all zero bytes"
150 : # endif
151 : #endif
152 :
153 : /* MAP_PERFECT_KEYS_EQUAL takes two key arguments, where the second has
154 : type MAP_PERFECT_KEY_T, and returns 1 if they are equal and 0 if they
155 : are not. */
156 :
157 : #ifndef MAP_PERFECT_KEYS_EQUAL
158 : # if !MAP_PERFECT_COMPLEX_KEY
159 0 : # define MAP_PERFECT_KEYS_EQUAL(k1,k2) ((k1)==(k2))
160 : # else
161 : # error "Define MAP_PERFECT_KEYS_EQUAL"
162 : # endif
163 : #endif
164 :
165 :
166 : /* By default, this file uses a family of hash functions of the form
167 :
168 : ((uint)k * (uint)MAP_PERFECT_HASH_C)>>(32-MAP_PERFECT_LG_TBL_SZ)
169 :
170 : where k is the key. I'm not too sure about the theory of this
171 : function, but it seems to work decently well in practice, and it's
172 : extremely cheap (2 instructions, 4 cycles of latency, 1 cycle inverse
173 : throughput).
174 : Of course, this is customizable, but you need to provide the hash
175 : function in two forms: One that is executed by the preprocessor, and
176 : one that is executed at runtime.
177 :
178 : IMPORTANT GOTCHA: the preprocessor only kind of understands types.
179 : It seems like it can differentiate between signed and unsigned, but
180 : everything is either a long or a ulong. It's probably easiest to
181 : treat everything as a ulong.
182 :
183 : The other difference is only apparent with complex keys:
184 : MAP_PERFECT_HASH_PP takes as many arguments as the array length,
185 : while MAP_PERFECT_HASH_R takes one argument of type
186 : MAP_PERFECT_KEY_T. They must return identical hashes for equivalent
187 : values. One good way to do that is to make them identical or to have
188 : them both invoke a common macro with the core hash logic.
189 :
190 : The hash must be simple enough that the preprocessor can execute it.
191 : */
192 :
193 : #ifdef MAP_PERFECT_HASH_PP
194 : # ifndef MAP_PERFECT_HASH_R
195 : # error "If you're using a custom hash function, you must define both MAP_PERFECT_HASH_PP and MAP_PERFECT_HASH_R"
196 : # endif
197 : #else
198 : # ifndef MAP_PERFECT_HASH_C
199 : # error "Define MAP_PERFECT_HASH_C"
200 : # endif
201 : # define MAP_PERFECT_HASH_PP( u ) ((( MAP_PERFECT_HASH_C * (u))&UINT_MAX)>>(32-(MAP_PERFECT_LG_TBL_SZ)))
202 0 : # define MAP_PERFECT_HASH_R( u ) (( MAP_PERFECT_HASH_C * (uint)(u) )>>(32-(MAP_PERFECT_LG_TBL_SZ)))
203 : #endif
204 :
205 : /* A note on picking MAP_PERFECT_HASH_C: I don't know a better way to
206 : find the constant other than brute force. If we model the hash
207 : function as a random map, then the probability any given constant
208 : results in no collisions is:
209 : N!/((N-m)!*N^m)
210 : where N is 2^MAP_PERFECT_LG_TBL_SZ and m is the number of elements in the
211 : table. The simple estimate of the number of constants you need to
212 : try is then ((N-m)! N^m)/N!. This function grows faster than
213 : exponential as a function of m. The only real downside to a larger
214 : table is increased cache utilization and cache misses.
215 :
216 : Here is some example Python code for finding a hash for prime numbers
217 : under 100:
218 :
219 : import numpy as np
220 : import random
221 : import math
222 :
223 : arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
224 : PMP_LG_TBL_SZ = 5
225 : nn = np.array(arr)
226 : best = 0
227 :
228 : estimated_cnt = int(math.factorial( (1<<PMP_LG_TBL_SZ)-len(arr) ) * ((1<<PMP_LG_TBL_SZ)**len(arr)) / math.factorial((1<<PMP_LG_TBL_SZ)))
229 : if estimated_cnt > 2**32:
230 : print(f"Warning: the table is likely too full. Estimated {estimated_cnt} random values needed")
231 : print(f"Trying {2*estimated_cnt} random constants")
232 :
233 : for k in range(2*estimated_cnt):
234 : r = random.randint(0,2**32-1)
235 : cur = len(set( ((nn*r)>>(32-PMP_LG_TBL_SZ))&((1<<PMP_LG_TBL_SZ) - 1) ))
236 : if cur == len(arr):
237 : print(f"Success! Use {r} as the hash constant")
238 : break
239 : if cur>best:
240 : best = cur
241 : print(f"Progress: found projection onto {best} entries.") */
242 :
243 : #if defined(MAP_PERFECT_1000)
244 : # error "fd_map_perfect only supports up to 1000 elements."
245 : #endif
246 :
247 : /* Implementation: */
248 : #include "../bits/fd_bits.h"
249 :
250 : #define MAP_PERFECT_(n) FD_EXPAND_THEN_CONCAT3(MAP_PERFECT_NAME,_,n)
251 :
252 : /* Step 1: Define macros that can kinda distinguish between whether
253 : something has been defined or not. The actual preprocessor function
254 : "defined" only works in #if expressions, so it's no good. Instead we
255 : determine whether the token in question expands to something with a
256 : comma in it (this is why even in the no-value case, the elements need
257 : a comma). This is mostly taken from the Internet. */
258 :
259 : #define FD_MP_EXPAND(x) x
260 :
261 : #define FD_MP_ARG_100(_,\
262 : _100,_99,_98,_97,_96,_95,_94,_93,_92,_91,_90,_89,_88,_87,_86,_85,_84,_83,_82,_81, \
263 : _80,_79,_78,_77,_76,_75,_74,_73,_72,_71,_70,_69,_68,_67,_66,_65,_64,_63,_62,_61, \
264 : _60,_59,_58,_57,_56,_55,_54,_53,_52,_51,_50,_49,_48,_47,_46,_45,_44,_43,_42,_41, \
265 : _40,_39,_38,_37,_36,_35,_34,_33,_32,_31,_30,_29,_28,_27,_26,_25,_24,_23,_22,_21, \
266 : _20,_19,_18,_17,_16,_15,_14,_13,_12,_11,_10,_9,_8,_7,_6,_5,_4,_3,_2,X_,...) X_
267 :
268 : /* Returns whether __VA_ARGS__ has a comma (up to 100 arguments). */
269 : #define FD_MP_HAS_COMMA(...) FD_MP_EXPAND(FD_MP_ARG_100(__VA_ARGS__, \
270 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
271 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
272 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \
273 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, \
274 : 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1))
275 :
276 :
277 :
278 : /* Step 2: Define macros that will generate the sequence of integers
279 : 0, 1, ... 999. */
280 :
281 : /* This set of recursive macros expands f with argument p0 concatenated
282 : with successive sequential integers from 0 to 999 (inclusive). The
283 : invocations are joined with j. z1 and z2 are helper arguments that
284 : must start with z1 as empty and z2 as 0. When the leading digit is
285 : not zero, they will be flipped.
286 :
287 : Solving something close to this is not hard: you just concat a digit
288 : onto the prefix (p) and then recurse. The tricky part comes from
289 : leading 0s. To solve that, we use z1 which is empty when it's a
290 : leading zero and a literal zero when not. That almost solves it, but
291 : then the very first call to FD_MP_RECURSE1 has p="" instead of p="0" (not
292 : actually strings), since it's entirely leading zeros. z2 solves
293 : that. */
294 : #define FD_MP_RECURSE4(p0, p, j, z1, z2, f) FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,z1), j, z1, z2, f ) j() \
295 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,1), j, 0, , f ) j() \
296 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,2), j, 0, , f ) j() \
297 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,3), j, 0, , f ) j() \
298 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,4), j, 0, , f ) j() \
299 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,5), j, 0, , f ) j() \
300 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,6), j, 0, , f ) j() \
301 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,7), j, 0, , f ) j() \
302 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,8), j, 0, , f ) j() \
303 : FD_MP_RECURSE3( p0, FD_EXPAND_THEN_CONCAT2(p,9), j, 0, , f )
304 : #define FD_MP_RECURSE3(p0, p, j, z1, z2, f) FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,z1), j, z1, z2, f ) j() \
305 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,1), j, 0, , f ) j() \
306 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,2), j, 0, , f ) j() \
307 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,3), j, 0, , f ) j() \
308 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,4), j, 0, , f ) j() \
309 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,5), j, 0, , f ) j() \
310 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,6), j, 0, , f ) j() \
311 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,7), j, 0, , f ) j() \
312 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,8), j, 0, , f ) j() \
313 : FD_MP_RECURSE2( p0, FD_EXPAND_THEN_CONCAT2(p,9), j, 0, , f )
314 : #define FD_MP_RECURSE2(p0, p, j, z1, z2, f) FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,z1), j, z1, z2, f ) j() \
315 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,1), j, 0, , f ) j() \
316 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,2), j, 0, , f ) j() \
317 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,3), j, 0, , f ) j() \
318 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,4), j, 0, , f ) j() \
319 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,5), j, 0, , f ) j() \
320 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,6), j, 0, , f ) j() \
321 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,7), j, 0, , f ) j() \
322 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,8), j, 0, , f ) j() \
323 : FD_MP_RECURSE1( p0, FD_EXPAND_THEN_CONCAT2(p,9), j, 0, , f )
324 :
325 : #define FD_MP_RECURSE1(p0, p, j, z1, z2, f) f( FD_EXPAND_THEN_CONCAT3(p0, p, z2) )
326 : #define FD_MP_EMPTY()
327 : #define FD_MP_AND() &&
328 :
329 : /* Step 3: Define macros for turning a table element into an array
330 : declaration, and also whether it has a key that hashes to something
331 : other than what the zero key hashes to. */
332 :
333 : #if MAP_PERFECT_COMPLEX_KEY
334 : /* Consume the first and last parenthesis */
335 : # define FD_MP_EAT_PARENS( ... ) __VA_ARGS__
336 : # define FD_MP_FORMAT_KEY( K ) { FD_MP_EAT_PARENS K }
337 : /* Various macro expansion tricks */
338 : # define FD_MP_HASH_PP_1( KEY ) FD_MP_HASH_PP_2( KEY )
339 : # define FD_MP_HASH_PP_2( KEY ) MAP_PERFECT_HASH_PP KEY
340 : #else
341 : # define FD_MP_FORMAT_KEY( K ) K
342 : # define FD_MP_HASH_PP_1( KEY ) MAP_PERFECT_HASH_PP( KEY )
343 : #endif
344 :
345 : #define FD_MP_VAL( K, ... ) __VA_ARGS__
346 : #define FD_MP_KEY( K, ... ) K
347 :
348 : #define FD_MP_ADD_ELE( ... ) \
349 : [ FD_MP_HASH_PP_1( FD_MP_KEY( __VA_ARGS__ ) ) ] = \
350 : { . MAP_PERFECT_KEY = FD_MP_FORMAT_KEY( FD_MP_KEY(__VA_ARGS__) ), FD_MP_VAL(__VA_ARGS__) },
351 :
352 : #define FD_MP_MAKE_ELE_0(...)
353 : #define FD_MP_MAKE_ELE_1(K, ...) FD_MP_ADD_ELE(K, __VA_ARGS__)
354 :
355 : #define FD_MP_CHOOSE_MAKE(...) FD_EXPAND_THEN_CONCAT2( FD_MP_MAKE_ELE_, FD_MP_HAS_COMMA(__VA_ARGS__) )(__VA_ARGS__)
356 :
357 :
358 :
359 : #define FD_MP_HASH_PP_3( ... ) FD_MP_HASH_PP_1( FD_MP_KEY( __VA_ARGS__ ) )
360 :
361 : /* If nothing maps to the same entry as the zero key, then we need to
362 : insert a dummy element. We insert MAP_PERFECT_0 at the index that
363 : the zero key would map to. In this case, nothing maps to the same
364 : entry as the zero key, which means MAP_PERFECT_0 certainly doesn't,
365 : which means the zero key's index is the wrong index for it. Thus it
366 : won't match any queries that hit the zero key's index, as desired. */
367 :
368 : #define FD_MP_NONZERO_ELE_0(...) 1
369 : #define FD_MP_NONZERO_ELE_1(K, ...) (FD_MP_HASH_PP_1(MAP_PERFECT_ZERO_KEY) != FD_MP_HASH_PP_1(K))
370 :
371 : #define FD_MP_CHOOSE_NONZERO(...) FD_EXPAND_THEN_CONCAT2( FD_MP_NONZERO_ELE_, FD_MP_HAS_COMMA(__VA_ARGS__) )(__VA_ARGS__)
372 :
373 : #if FD_MP_RECURSE4( MAP_PERFECT_, , FD_MP_AND, FD_MP_EMPTY(), 0, FD_MP_CHOOSE_NONZERO)
374 : #define FD_MP_ZERO_KEY_VAL_1( ... ) \
375 : { . MAP_PERFECT_KEY = FD_MP_FORMAT_KEY( FD_MP_KEY(__VA_ARGS__) ), \
376 : FD_MP_VAL(__VA_ARGS__) }
377 : #define FD_MP_ZERO_KEY_ELE [ FD_MP_HASH_PP_1(MAP_PERFECT_ZERO_KEY) ] = \
378 : FD_MP_ZERO_KEY_VAL_1(MAP_PERFECT_0),
379 : #else
380 : #define FD_MP_ZERO_KEY_ELE
381 : #endif
382 :
383 : static const MAP_PERFECT_T MAP_PERFECT_(tbl)[ 1<<MAP_PERFECT_LG_TBL_SZ ] = {
384 : FD_MP_RECURSE4( MAP_PERFECT_, , FD_MP_EMPTY, FD_MP_EMPTY(), 0, FD_MP_CHOOSE_MAKE )
385 : FD_MP_ZERO_KEY_ELE
386 : };
387 :
388 :
389 : static inline int
390 25570608 : MAP_PERFECT_(contains)( MAP_PERFECT_KEY_T key ) {
391 25570608 : uint hash = MAP_PERFECT_HASH_R( key );
392 25570608 : return MAP_PERFECT_KEYS_EQUAL( MAP_PERFECT_(tbl)[ hash ].MAP_PERFECT_KEY, key );
393 25570608 : }
394 :
395 : static inline MAP_PERFECT_T const *
396 8132832 : MAP_PERFECT_(query)( MAP_PERFECT_KEY_T key, MAP_PERFECT_T const * null ) {
397 8132832 : uint hash = MAP_PERFECT_HASH_R( key );
398 8132832 : int contained = MAP_PERFECT_KEYS_EQUAL( MAP_PERFECT_(tbl)[ hash ].MAP_PERFECT_KEY, key );
399 8132832 : return fd_ptr_if( contained, MAP_PERFECT_(tbl)+hash, null );
400 8132832 : }
401 :
402 : static inline uint
403 66 : MAP_PERFECT_(hash_or_default)( MAP_PERFECT_KEY_T key ) {
404 66 : uint hash = MAP_PERFECT_HASH_R( key );
405 66 : int contained = MAP_PERFECT_KEYS_EQUAL( MAP_PERFECT_(tbl)[ hash ].MAP_PERFECT_KEY, key );
406 66 : return fd_uint_if( contained, hash, UINT_MAX );
407 66 : }
408 :
409 : #undef FD_MP_ZERO_KEY_ELE
410 : #undef FD_MP_ZERO_KEY_VAL_1
411 : #undef FD_MP_CHOOSE_NONZERO
412 : #undef FD_MP_NONZERO_ELE_1
413 : #undef FD_MP_NONZERO_ELE_0
414 : #undef FD_MP_CHOOSE_MAKE
415 : #undef FD_MP_MAKE_ELE_0
416 : #undef FD_MP_MAKE_ELE_1
417 : #undef FD_MP_ADD_ELE
418 : #undef FD_MP_VAL
419 : #undef FD_MP_KEY
420 : #undef FD_MP_HASH_PP_3
421 : #undef FD_MP_HASH_PP_2
422 : #undef FD_MP_HASH_PP_1
423 : #undef FD_MP_FORMAT_KEY
424 : #undef FD_MP_EAT_PARENS
425 : #undef FD_MP_AND
426 : #undef FD_MP_EMPTY
427 : #undef FD_MP_RECURSE_1
428 : #undef FD_MP_RECURSE_2
429 : #undef FD_MP_RECURSE_3
430 : #undef FD_MP_RECURSE_4
431 : #undef FD_MP_HAS_COMMA
432 : #undef FD_MP_ARG_100
433 : #undef FD_MP_EXPAND
434 : #undef MAP_PERFECT_
435 : #undef MAP_PERFECT_HASH_R
436 : #undef MAP_PERFECT_HASH_PP
437 : #undef MAP_PERFECT_HASH_C
438 : #undef MAP_PERFECT_KEYS_EQUAL
439 : #undef MAP_PERFECT_ZERO_KEY
440 : #undef MAP_PERFECT_COMPLEX_KEY
441 : #undef MAP_PERFECT_KEY_T
442 : #undef MAP_PERFECT_KEY
443 : #undef MAP_PERFECT_T
444 : #undef MAP_PERFECT_LG_TBL_SZ
445 : #undef MAP_PERFECT_NAME
446 :
447 : /* Finally, undefine all the 1000 possible entries... It's not possible to
448 : make a macro emit an undef command. Nothing else follows this section. */
449 : #undef MAP_PERFECT_999
450 : #undef MAP_PERFECT_998
451 : #undef MAP_PERFECT_997
452 : #undef MAP_PERFECT_996
453 : #undef MAP_PERFECT_995
454 : #undef MAP_PERFECT_994
455 : #undef MAP_PERFECT_993
456 : #undef MAP_PERFECT_992
457 : #undef MAP_PERFECT_991
458 : #undef MAP_PERFECT_990
459 : #undef MAP_PERFECT_989
460 : #undef MAP_PERFECT_988
461 : #undef MAP_PERFECT_987
462 : #undef MAP_PERFECT_986
463 : #undef MAP_PERFECT_985
464 : #undef MAP_PERFECT_984
465 : #undef MAP_PERFECT_983
466 : #undef MAP_PERFECT_982
467 : #undef MAP_PERFECT_981
468 : #undef MAP_PERFECT_980
469 : #undef MAP_PERFECT_979
470 : #undef MAP_PERFECT_978
471 : #undef MAP_PERFECT_977
472 : #undef MAP_PERFECT_976
473 : #undef MAP_PERFECT_975
474 : #undef MAP_PERFECT_974
475 : #undef MAP_PERFECT_973
476 : #undef MAP_PERFECT_972
477 : #undef MAP_PERFECT_971
478 : #undef MAP_PERFECT_970
479 : #undef MAP_PERFECT_969
480 : #undef MAP_PERFECT_968
481 : #undef MAP_PERFECT_967
482 : #undef MAP_PERFECT_966
483 : #undef MAP_PERFECT_965
484 : #undef MAP_PERFECT_964
485 : #undef MAP_PERFECT_963
486 : #undef MAP_PERFECT_962
487 : #undef MAP_PERFECT_961
488 : #undef MAP_PERFECT_960
489 : #undef MAP_PERFECT_959
490 : #undef MAP_PERFECT_958
491 : #undef MAP_PERFECT_957
492 : #undef MAP_PERFECT_956
493 : #undef MAP_PERFECT_955
494 : #undef MAP_PERFECT_954
495 : #undef MAP_PERFECT_953
496 : #undef MAP_PERFECT_952
497 : #undef MAP_PERFECT_951
498 : #undef MAP_PERFECT_950
499 : #undef MAP_PERFECT_949
500 : #undef MAP_PERFECT_948
501 : #undef MAP_PERFECT_947
502 : #undef MAP_PERFECT_946
503 : #undef MAP_PERFECT_945
504 : #undef MAP_PERFECT_944
505 : #undef MAP_PERFECT_943
506 : #undef MAP_PERFECT_942
507 : #undef MAP_PERFECT_941
508 : #undef MAP_PERFECT_940
509 : #undef MAP_PERFECT_939
510 : #undef MAP_PERFECT_938
511 : #undef MAP_PERFECT_937
512 : #undef MAP_PERFECT_936
513 : #undef MAP_PERFECT_935
514 : #undef MAP_PERFECT_934
515 : #undef MAP_PERFECT_933
516 : #undef MAP_PERFECT_932
517 : #undef MAP_PERFECT_931
518 : #undef MAP_PERFECT_930
519 : #undef MAP_PERFECT_929
520 : #undef MAP_PERFECT_928
521 : #undef MAP_PERFECT_927
522 : #undef MAP_PERFECT_926
523 : #undef MAP_PERFECT_925
524 : #undef MAP_PERFECT_924
525 : #undef MAP_PERFECT_923
526 : #undef MAP_PERFECT_922
527 : #undef MAP_PERFECT_921
528 : #undef MAP_PERFECT_920
529 : #undef MAP_PERFECT_919
530 : #undef MAP_PERFECT_918
531 : #undef MAP_PERFECT_917
532 : #undef MAP_PERFECT_916
533 : #undef MAP_PERFECT_915
534 : #undef MAP_PERFECT_914
535 : #undef MAP_PERFECT_913
536 : #undef MAP_PERFECT_912
537 : #undef MAP_PERFECT_911
538 : #undef MAP_PERFECT_910
539 : #undef MAP_PERFECT_909
540 : #undef MAP_PERFECT_908
541 : #undef MAP_PERFECT_907
542 : #undef MAP_PERFECT_906
543 : #undef MAP_PERFECT_905
544 : #undef MAP_PERFECT_904
545 : #undef MAP_PERFECT_903
546 : #undef MAP_PERFECT_902
547 : #undef MAP_PERFECT_901
548 : #undef MAP_PERFECT_900
549 : #undef MAP_PERFECT_899
550 : #undef MAP_PERFECT_898
551 : #undef MAP_PERFECT_897
552 : #undef MAP_PERFECT_896
553 : #undef MAP_PERFECT_895
554 : #undef MAP_PERFECT_894
555 : #undef MAP_PERFECT_893
556 : #undef MAP_PERFECT_892
557 : #undef MAP_PERFECT_891
558 : #undef MAP_PERFECT_890
559 : #undef MAP_PERFECT_889
560 : #undef MAP_PERFECT_888
561 : #undef MAP_PERFECT_887
562 : #undef MAP_PERFECT_886
563 : #undef MAP_PERFECT_885
564 : #undef MAP_PERFECT_884
565 : #undef MAP_PERFECT_883
566 : #undef MAP_PERFECT_882
567 : #undef MAP_PERFECT_881
568 : #undef MAP_PERFECT_880
569 : #undef MAP_PERFECT_879
570 : #undef MAP_PERFECT_878
571 : #undef MAP_PERFECT_877
572 : #undef MAP_PERFECT_876
573 : #undef MAP_PERFECT_875
574 : #undef MAP_PERFECT_874
575 : #undef MAP_PERFECT_873
576 : #undef MAP_PERFECT_872
577 : #undef MAP_PERFECT_871
578 : #undef MAP_PERFECT_870
579 : #undef MAP_PERFECT_869
580 : #undef MAP_PERFECT_868
581 : #undef MAP_PERFECT_867
582 : #undef MAP_PERFECT_866
583 : #undef MAP_PERFECT_865
584 : #undef MAP_PERFECT_864
585 : #undef MAP_PERFECT_863
586 : #undef MAP_PERFECT_862
587 : #undef MAP_PERFECT_861
588 : #undef MAP_PERFECT_860
589 : #undef MAP_PERFECT_859
590 : #undef MAP_PERFECT_858
591 : #undef MAP_PERFECT_857
592 : #undef MAP_PERFECT_856
593 : #undef MAP_PERFECT_855
594 : #undef MAP_PERFECT_854
595 : #undef MAP_PERFECT_853
596 : #undef MAP_PERFECT_852
597 : #undef MAP_PERFECT_851
598 : #undef MAP_PERFECT_850
599 : #undef MAP_PERFECT_849
600 : #undef MAP_PERFECT_848
601 : #undef MAP_PERFECT_847
602 : #undef MAP_PERFECT_846
603 : #undef MAP_PERFECT_845
604 : #undef MAP_PERFECT_844
605 : #undef MAP_PERFECT_843
606 : #undef MAP_PERFECT_842
607 : #undef MAP_PERFECT_841
608 : #undef MAP_PERFECT_840
609 : #undef MAP_PERFECT_839
610 : #undef MAP_PERFECT_838
611 : #undef MAP_PERFECT_837
612 : #undef MAP_PERFECT_836
613 : #undef MAP_PERFECT_835
614 : #undef MAP_PERFECT_834
615 : #undef MAP_PERFECT_833
616 : #undef MAP_PERFECT_832
617 : #undef MAP_PERFECT_831
618 : #undef MAP_PERFECT_830
619 : #undef MAP_PERFECT_829
620 : #undef MAP_PERFECT_828
621 : #undef MAP_PERFECT_827
622 : #undef MAP_PERFECT_826
623 : #undef MAP_PERFECT_825
624 : #undef MAP_PERFECT_824
625 : #undef MAP_PERFECT_823
626 : #undef MAP_PERFECT_822
627 : #undef MAP_PERFECT_821
628 : #undef MAP_PERFECT_820
629 : #undef MAP_PERFECT_819
630 : #undef MAP_PERFECT_818
631 : #undef MAP_PERFECT_817
632 : #undef MAP_PERFECT_816
633 : #undef MAP_PERFECT_815
634 : #undef MAP_PERFECT_814
635 : #undef MAP_PERFECT_813
636 : #undef MAP_PERFECT_812
637 : #undef MAP_PERFECT_811
638 : #undef MAP_PERFECT_810
639 : #undef MAP_PERFECT_809
640 : #undef MAP_PERFECT_808
641 : #undef MAP_PERFECT_807
642 : #undef MAP_PERFECT_806
643 : #undef MAP_PERFECT_805
644 : #undef MAP_PERFECT_804
645 : #undef MAP_PERFECT_803
646 : #undef MAP_PERFECT_802
647 : #undef MAP_PERFECT_801
648 : #undef MAP_PERFECT_800
649 : #undef MAP_PERFECT_799
650 : #undef MAP_PERFECT_798
651 : #undef MAP_PERFECT_797
652 : #undef MAP_PERFECT_796
653 : #undef MAP_PERFECT_795
654 : #undef MAP_PERFECT_794
655 : #undef MAP_PERFECT_793
656 : #undef MAP_PERFECT_792
657 : #undef MAP_PERFECT_791
658 : #undef MAP_PERFECT_790
659 : #undef MAP_PERFECT_789
660 : #undef MAP_PERFECT_788
661 : #undef MAP_PERFECT_787
662 : #undef MAP_PERFECT_786
663 : #undef MAP_PERFECT_785
664 : #undef MAP_PERFECT_784
665 : #undef MAP_PERFECT_783
666 : #undef MAP_PERFECT_782
667 : #undef MAP_PERFECT_781
668 : #undef MAP_PERFECT_780
669 : #undef MAP_PERFECT_779
670 : #undef MAP_PERFECT_778
671 : #undef MAP_PERFECT_777
672 : #undef MAP_PERFECT_776
673 : #undef MAP_PERFECT_775
674 : #undef MAP_PERFECT_774
675 : #undef MAP_PERFECT_773
676 : #undef MAP_PERFECT_772
677 : #undef MAP_PERFECT_771
678 : #undef MAP_PERFECT_770
679 : #undef MAP_PERFECT_769
680 : #undef MAP_PERFECT_768
681 : #undef MAP_PERFECT_767
682 : #undef MAP_PERFECT_766
683 : #undef MAP_PERFECT_765
684 : #undef MAP_PERFECT_764
685 : #undef MAP_PERFECT_763
686 : #undef MAP_PERFECT_762
687 : #undef MAP_PERFECT_761
688 : #undef MAP_PERFECT_760
689 : #undef MAP_PERFECT_759
690 : #undef MAP_PERFECT_758
691 : #undef MAP_PERFECT_757
692 : #undef MAP_PERFECT_756
693 : #undef MAP_PERFECT_755
694 : #undef MAP_PERFECT_754
695 : #undef MAP_PERFECT_753
696 : #undef MAP_PERFECT_752
697 : #undef MAP_PERFECT_751
698 : #undef MAP_PERFECT_750
699 : #undef MAP_PERFECT_749
700 : #undef MAP_PERFECT_748
701 : #undef MAP_PERFECT_747
702 : #undef MAP_PERFECT_746
703 : #undef MAP_PERFECT_745
704 : #undef MAP_PERFECT_744
705 : #undef MAP_PERFECT_743
706 : #undef MAP_PERFECT_742
707 : #undef MAP_PERFECT_741
708 : #undef MAP_PERFECT_740
709 : #undef MAP_PERFECT_739
710 : #undef MAP_PERFECT_738
711 : #undef MAP_PERFECT_737
712 : #undef MAP_PERFECT_736
713 : #undef MAP_PERFECT_735
714 : #undef MAP_PERFECT_734
715 : #undef MAP_PERFECT_733
716 : #undef MAP_PERFECT_732
717 : #undef MAP_PERFECT_731
718 : #undef MAP_PERFECT_730
719 : #undef MAP_PERFECT_729
720 : #undef MAP_PERFECT_728
721 : #undef MAP_PERFECT_727
722 : #undef MAP_PERFECT_726
723 : #undef MAP_PERFECT_725
724 : #undef MAP_PERFECT_724
725 : #undef MAP_PERFECT_723
726 : #undef MAP_PERFECT_722
727 : #undef MAP_PERFECT_721
728 : #undef MAP_PERFECT_720
729 : #undef MAP_PERFECT_719
730 : #undef MAP_PERFECT_718
731 : #undef MAP_PERFECT_717
732 : #undef MAP_PERFECT_716
733 : #undef MAP_PERFECT_715
734 : #undef MAP_PERFECT_714
735 : #undef MAP_PERFECT_713
736 : #undef MAP_PERFECT_712
737 : #undef MAP_PERFECT_711
738 : #undef MAP_PERFECT_710
739 : #undef MAP_PERFECT_709
740 : #undef MAP_PERFECT_708
741 : #undef MAP_PERFECT_707
742 : #undef MAP_PERFECT_706
743 : #undef MAP_PERFECT_705
744 : #undef MAP_PERFECT_704
745 : #undef MAP_PERFECT_703
746 : #undef MAP_PERFECT_702
747 : #undef MAP_PERFECT_701
748 : #undef MAP_PERFECT_700
749 : #undef MAP_PERFECT_699
750 : #undef MAP_PERFECT_698
751 : #undef MAP_PERFECT_697
752 : #undef MAP_PERFECT_696
753 : #undef MAP_PERFECT_695
754 : #undef MAP_PERFECT_694
755 : #undef MAP_PERFECT_693
756 : #undef MAP_PERFECT_692
757 : #undef MAP_PERFECT_691
758 : #undef MAP_PERFECT_690
759 : #undef MAP_PERFECT_689
760 : #undef MAP_PERFECT_688
761 : #undef MAP_PERFECT_687
762 : #undef MAP_PERFECT_686
763 : #undef MAP_PERFECT_685
764 : #undef MAP_PERFECT_684
765 : #undef MAP_PERFECT_683
766 : #undef MAP_PERFECT_682
767 : #undef MAP_PERFECT_681
768 : #undef MAP_PERFECT_680
769 : #undef MAP_PERFECT_679
770 : #undef MAP_PERFECT_678
771 : #undef MAP_PERFECT_677
772 : #undef MAP_PERFECT_676
773 : #undef MAP_PERFECT_675
774 : #undef MAP_PERFECT_674
775 : #undef MAP_PERFECT_673
776 : #undef MAP_PERFECT_672
777 : #undef MAP_PERFECT_671
778 : #undef MAP_PERFECT_670
779 : #undef MAP_PERFECT_669
780 : #undef MAP_PERFECT_668
781 : #undef MAP_PERFECT_667
782 : #undef MAP_PERFECT_666
783 : #undef MAP_PERFECT_665
784 : #undef MAP_PERFECT_664
785 : #undef MAP_PERFECT_663
786 : #undef MAP_PERFECT_662
787 : #undef MAP_PERFECT_661
788 : #undef MAP_PERFECT_660
789 : #undef MAP_PERFECT_659
790 : #undef MAP_PERFECT_658
791 : #undef MAP_PERFECT_657
792 : #undef MAP_PERFECT_656
793 : #undef MAP_PERFECT_655
794 : #undef MAP_PERFECT_654
795 : #undef MAP_PERFECT_653
796 : #undef MAP_PERFECT_652
797 : #undef MAP_PERFECT_651
798 : #undef MAP_PERFECT_650
799 : #undef MAP_PERFECT_649
800 : #undef MAP_PERFECT_648
801 : #undef MAP_PERFECT_647
802 : #undef MAP_PERFECT_646
803 : #undef MAP_PERFECT_645
804 : #undef MAP_PERFECT_644
805 : #undef MAP_PERFECT_643
806 : #undef MAP_PERFECT_642
807 : #undef MAP_PERFECT_641
808 : #undef MAP_PERFECT_640
809 : #undef MAP_PERFECT_639
810 : #undef MAP_PERFECT_638
811 : #undef MAP_PERFECT_637
812 : #undef MAP_PERFECT_636
813 : #undef MAP_PERFECT_635
814 : #undef MAP_PERFECT_634
815 : #undef MAP_PERFECT_633
816 : #undef MAP_PERFECT_632
817 : #undef MAP_PERFECT_631
818 : #undef MAP_PERFECT_630
819 : #undef MAP_PERFECT_629
820 : #undef MAP_PERFECT_628
821 : #undef MAP_PERFECT_627
822 : #undef MAP_PERFECT_626
823 : #undef MAP_PERFECT_625
824 : #undef MAP_PERFECT_624
825 : #undef MAP_PERFECT_623
826 : #undef MAP_PERFECT_622
827 : #undef MAP_PERFECT_621
828 : #undef MAP_PERFECT_620
829 : #undef MAP_PERFECT_619
830 : #undef MAP_PERFECT_618
831 : #undef MAP_PERFECT_617
832 : #undef MAP_PERFECT_616
833 : #undef MAP_PERFECT_615
834 : #undef MAP_PERFECT_614
835 : #undef MAP_PERFECT_613
836 : #undef MAP_PERFECT_612
837 : #undef MAP_PERFECT_611
838 : #undef MAP_PERFECT_610
839 : #undef MAP_PERFECT_609
840 : #undef MAP_PERFECT_608
841 : #undef MAP_PERFECT_607
842 : #undef MAP_PERFECT_606
843 : #undef MAP_PERFECT_605
844 : #undef MAP_PERFECT_604
845 : #undef MAP_PERFECT_603
846 : #undef MAP_PERFECT_602
847 : #undef MAP_PERFECT_601
848 : #undef MAP_PERFECT_600
849 : #undef MAP_PERFECT_599
850 : #undef MAP_PERFECT_598
851 : #undef MAP_PERFECT_597
852 : #undef MAP_PERFECT_596
853 : #undef MAP_PERFECT_595
854 : #undef MAP_PERFECT_594
855 : #undef MAP_PERFECT_593
856 : #undef MAP_PERFECT_592
857 : #undef MAP_PERFECT_591
858 : #undef MAP_PERFECT_590
859 : #undef MAP_PERFECT_589
860 : #undef MAP_PERFECT_588
861 : #undef MAP_PERFECT_587
862 : #undef MAP_PERFECT_586
863 : #undef MAP_PERFECT_585
864 : #undef MAP_PERFECT_584
865 : #undef MAP_PERFECT_583
866 : #undef MAP_PERFECT_582
867 : #undef MAP_PERFECT_581
868 : #undef MAP_PERFECT_580
869 : #undef MAP_PERFECT_579
870 : #undef MAP_PERFECT_578
871 : #undef MAP_PERFECT_577
872 : #undef MAP_PERFECT_576
873 : #undef MAP_PERFECT_575
874 : #undef MAP_PERFECT_574
875 : #undef MAP_PERFECT_573
876 : #undef MAP_PERFECT_572
877 : #undef MAP_PERFECT_571
878 : #undef MAP_PERFECT_570
879 : #undef MAP_PERFECT_569
880 : #undef MAP_PERFECT_568
881 : #undef MAP_PERFECT_567
882 : #undef MAP_PERFECT_566
883 : #undef MAP_PERFECT_565
884 : #undef MAP_PERFECT_564
885 : #undef MAP_PERFECT_563
886 : #undef MAP_PERFECT_562
887 : #undef MAP_PERFECT_561
888 : #undef MAP_PERFECT_560
889 : #undef MAP_PERFECT_559
890 : #undef MAP_PERFECT_558
891 : #undef MAP_PERFECT_557
892 : #undef MAP_PERFECT_556
893 : #undef MAP_PERFECT_555
894 : #undef MAP_PERFECT_554
895 : #undef MAP_PERFECT_553
896 : #undef MAP_PERFECT_552
897 : #undef MAP_PERFECT_551
898 : #undef MAP_PERFECT_550
899 : #undef MAP_PERFECT_549
900 : #undef MAP_PERFECT_548
901 : #undef MAP_PERFECT_547
902 : #undef MAP_PERFECT_546
903 : #undef MAP_PERFECT_545
904 : #undef MAP_PERFECT_544
905 : #undef MAP_PERFECT_543
906 : #undef MAP_PERFECT_542
907 : #undef MAP_PERFECT_541
908 : #undef MAP_PERFECT_540
909 : #undef MAP_PERFECT_539
910 : #undef MAP_PERFECT_538
911 : #undef MAP_PERFECT_537
912 : #undef MAP_PERFECT_536
913 : #undef MAP_PERFECT_535
914 : #undef MAP_PERFECT_534
915 : #undef MAP_PERFECT_533
916 : #undef MAP_PERFECT_532
917 : #undef MAP_PERFECT_531
918 : #undef MAP_PERFECT_530
919 : #undef MAP_PERFECT_529
920 : #undef MAP_PERFECT_528
921 : #undef MAP_PERFECT_527
922 : #undef MAP_PERFECT_526
923 : #undef MAP_PERFECT_525
924 : #undef MAP_PERFECT_524
925 : #undef MAP_PERFECT_523
926 : #undef MAP_PERFECT_522
927 : #undef MAP_PERFECT_521
928 : #undef MAP_PERFECT_520
929 : #undef MAP_PERFECT_519
930 : #undef MAP_PERFECT_518
931 : #undef MAP_PERFECT_517
932 : #undef MAP_PERFECT_516
933 : #undef MAP_PERFECT_515
934 : #undef MAP_PERFECT_514
935 : #undef MAP_PERFECT_513
936 : #undef MAP_PERFECT_512
937 : #undef MAP_PERFECT_511
938 : #undef MAP_PERFECT_510
939 : #undef MAP_PERFECT_509
940 : #undef MAP_PERFECT_508
941 : #undef MAP_PERFECT_507
942 : #undef MAP_PERFECT_506
943 : #undef MAP_PERFECT_505
944 : #undef MAP_PERFECT_504
945 : #undef MAP_PERFECT_503
946 : #undef MAP_PERFECT_502
947 : #undef MAP_PERFECT_501
948 : #undef MAP_PERFECT_500
949 : #undef MAP_PERFECT_499
950 : #undef MAP_PERFECT_498
951 : #undef MAP_PERFECT_497
952 : #undef MAP_PERFECT_496
953 : #undef MAP_PERFECT_495
954 : #undef MAP_PERFECT_494
955 : #undef MAP_PERFECT_493
956 : #undef MAP_PERFECT_492
957 : #undef MAP_PERFECT_491
958 : #undef MAP_PERFECT_490
959 : #undef MAP_PERFECT_489
960 : #undef MAP_PERFECT_488
961 : #undef MAP_PERFECT_487
962 : #undef MAP_PERFECT_486
963 : #undef MAP_PERFECT_485
964 : #undef MAP_PERFECT_484
965 : #undef MAP_PERFECT_483
966 : #undef MAP_PERFECT_482
967 : #undef MAP_PERFECT_481
968 : #undef MAP_PERFECT_480
969 : #undef MAP_PERFECT_479
970 : #undef MAP_PERFECT_478
971 : #undef MAP_PERFECT_477
972 : #undef MAP_PERFECT_476
973 : #undef MAP_PERFECT_475
974 : #undef MAP_PERFECT_474
975 : #undef MAP_PERFECT_473
976 : #undef MAP_PERFECT_472
977 : #undef MAP_PERFECT_471
978 : #undef MAP_PERFECT_470
979 : #undef MAP_PERFECT_469
980 : #undef MAP_PERFECT_468
981 : #undef MAP_PERFECT_467
982 : #undef MAP_PERFECT_466
983 : #undef MAP_PERFECT_465
984 : #undef MAP_PERFECT_464
985 : #undef MAP_PERFECT_463
986 : #undef MAP_PERFECT_462
987 : #undef MAP_PERFECT_461
988 : #undef MAP_PERFECT_460
989 : #undef MAP_PERFECT_459
990 : #undef MAP_PERFECT_458
991 : #undef MAP_PERFECT_457
992 : #undef MAP_PERFECT_456
993 : #undef MAP_PERFECT_455
994 : #undef MAP_PERFECT_454
995 : #undef MAP_PERFECT_453
996 : #undef MAP_PERFECT_452
997 : #undef MAP_PERFECT_451
998 : #undef MAP_PERFECT_450
999 : #undef MAP_PERFECT_449
1000 : #undef MAP_PERFECT_448
1001 : #undef MAP_PERFECT_447
1002 : #undef MAP_PERFECT_446
1003 : #undef MAP_PERFECT_445
1004 : #undef MAP_PERFECT_444
1005 : #undef MAP_PERFECT_443
1006 : #undef MAP_PERFECT_442
1007 : #undef MAP_PERFECT_441
1008 : #undef MAP_PERFECT_440
1009 : #undef MAP_PERFECT_439
1010 : #undef MAP_PERFECT_438
1011 : #undef MAP_PERFECT_437
1012 : #undef MAP_PERFECT_436
1013 : #undef MAP_PERFECT_435
1014 : #undef MAP_PERFECT_434
1015 : #undef MAP_PERFECT_433
1016 : #undef MAP_PERFECT_432
1017 : #undef MAP_PERFECT_431
1018 : #undef MAP_PERFECT_430
1019 : #undef MAP_PERFECT_429
1020 : #undef MAP_PERFECT_428
1021 : #undef MAP_PERFECT_427
1022 : #undef MAP_PERFECT_426
1023 : #undef MAP_PERFECT_425
1024 : #undef MAP_PERFECT_424
1025 : #undef MAP_PERFECT_423
1026 : #undef MAP_PERFECT_422
1027 : #undef MAP_PERFECT_421
1028 : #undef MAP_PERFECT_420
1029 : #undef MAP_PERFECT_419
1030 : #undef MAP_PERFECT_418
1031 : #undef MAP_PERFECT_417
1032 : #undef MAP_PERFECT_416
1033 : #undef MAP_PERFECT_415
1034 : #undef MAP_PERFECT_414
1035 : #undef MAP_PERFECT_413
1036 : #undef MAP_PERFECT_412
1037 : #undef MAP_PERFECT_411
1038 : #undef MAP_PERFECT_410
1039 : #undef MAP_PERFECT_409
1040 : #undef MAP_PERFECT_408
1041 : #undef MAP_PERFECT_407
1042 : #undef MAP_PERFECT_406
1043 : #undef MAP_PERFECT_405
1044 : #undef MAP_PERFECT_404
1045 : #undef MAP_PERFECT_403
1046 : #undef MAP_PERFECT_402
1047 : #undef MAP_PERFECT_401
1048 : #undef MAP_PERFECT_400
1049 : #undef MAP_PERFECT_399
1050 : #undef MAP_PERFECT_398
1051 : #undef MAP_PERFECT_397
1052 : #undef MAP_PERFECT_396
1053 : #undef MAP_PERFECT_395
1054 : #undef MAP_PERFECT_394
1055 : #undef MAP_PERFECT_393
1056 : #undef MAP_PERFECT_392
1057 : #undef MAP_PERFECT_391
1058 : #undef MAP_PERFECT_390
1059 : #undef MAP_PERFECT_389
1060 : #undef MAP_PERFECT_388
1061 : #undef MAP_PERFECT_387
1062 : #undef MAP_PERFECT_386
1063 : #undef MAP_PERFECT_385
1064 : #undef MAP_PERFECT_384
1065 : #undef MAP_PERFECT_383
1066 : #undef MAP_PERFECT_382
1067 : #undef MAP_PERFECT_381
1068 : #undef MAP_PERFECT_380
1069 : #undef MAP_PERFECT_379
1070 : #undef MAP_PERFECT_378
1071 : #undef MAP_PERFECT_377
1072 : #undef MAP_PERFECT_376
1073 : #undef MAP_PERFECT_375
1074 : #undef MAP_PERFECT_374
1075 : #undef MAP_PERFECT_373
1076 : #undef MAP_PERFECT_372
1077 : #undef MAP_PERFECT_371
1078 : #undef MAP_PERFECT_370
1079 : #undef MAP_PERFECT_369
1080 : #undef MAP_PERFECT_368
1081 : #undef MAP_PERFECT_367
1082 : #undef MAP_PERFECT_366
1083 : #undef MAP_PERFECT_365
1084 : #undef MAP_PERFECT_364
1085 : #undef MAP_PERFECT_363
1086 : #undef MAP_PERFECT_362
1087 : #undef MAP_PERFECT_361
1088 : #undef MAP_PERFECT_360
1089 : #undef MAP_PERFECT_359
1090 : #undef MAP_PERFECT_358
1091 : #undef MAP_PERFECT_357
1092 : #undef MAP_PERFECT_356
1093 : #undef MAP_PERFECT_355
1094 : #undef MAP_PERFECT_354
1095 : #undef MAP_PERFECT_353
1096 : #undef MAP_PERFECT_352
1097 : #undef MAP_PERFECT_351
1098 : #undef MAP_PERFECT_350
1099 : #undef MAP_PERFECT_349
1100 : #undef MAP_PERFECT_348
1101 : #undef MAP_PERFECT_347
1102 : #undef MAP_PERFECT_346
1103 : #undef MAP_PERFECT_345
1104 : #undef MAP_PERFECT_344
1105 : #undef MAP_PERFECT_343
1106 : #undef MAP_PERFECT_342
1107 : #undef MAP_PERFECT_341
1108 : #undef MAP_PERFECT_340
1109 : #undef MAP_PERFECT_339
1110 : #undef MAP_PERFECT_338
1111 : #undef MAP_PERFECT_337
1112 : #undef MAP_PERFECT_336
1113 : #undef MAP_PERFECT_335
1114 : #undef MAP_PERFECT_334
1115 : #undef MAP_PERFECT_333
1116 : #undef MAP_PERFECT_332
1117 : #undef MAP_PERFECT_331
1118 : #undef MAP_PERFECT_330
1119 : #undef MAP_PERFECT_329
1120 : #undef MAP_PERFECT_328
1121 : #undef MAP_PERFECT_327
1122 : #undef MAP_PERFECT_326
1123 : #undef MAP_PERFECT_325
1124 : #undef MAP_PERFECT_324
1125 : #undef MAP_PERFECT_323
1126 : #undef MAP_PERFECT_322
1127 : #undef MAP_PERFECT_321
1128 : #undef MAP_PERFECT_320
1129 : #undef MAP_PERFECT_319
1130 : #undef MAP_PERFECT_318
1131 : #undef MAP_PERFECT_317
1132 : #undef MAP_PERFECT_316
1133 : #undef MAP_PERFECT_315
1134 : #undef MAP_PERFECT_314
1135 : #undef MAP_PERFECT_313
1136 : #undef MAP_PERFECT_312
1137 : #undef MAP_PERFECT_311
1138 : #undef MAP_PERFECT_310
1139 : #undef MAP_PERFECT_309
1140 : #undef MAP_PERFECT_308
1141 : #undef MAP_PERFECT_307
1142 : #undef MAP_PERFECT_306
1143 : #undef MAP_PERFECT_305
1144 : #undef MAP_PERFECT_304
1145 : #undef MAP_PERFECT_303
1146 : #undef MAP_PERFECT_302
1147 : #undef MAP_PERFECT_301
1148 : #undef MAP_PERFECT_300
1149 : #undef MAP_PERFECT_299
1150 : #undef MAP_PERFECT_298
1151 : #undef MAP_PERFECT_297
1152 : #undef MAP_PERFECT_296
1153 : #undef MAP_PERFECT_295
1154 : #undef MAP_PERFECT_294
1155 : #undef MAP_PERFECT_293
1156 : #undef MAP_PERFECT_292
1157 : #undef MAP_PERFECT_291
1158 : #undef MAP_PERFECT_290
1159 : #undef MAP_PERFECT_289
1160 : #undef MAP_PERFECT_288
1161 : #undef MAP_PERFECT_287
1162 : #undef MAP_PERFECT_286
1163 : #undef MAP_PERFECT_285
1164 : #undef MAP_PERFECT_284
1165 : #undef MAP_PERFECT_283
1166 : #undef MAP_PERFECT_282
1167 : #undef MAP_PERFECT_281
1168 : #undef MAP_PERFECT_280
1169 : #undef MAP_PERFECT_279
1170 : #undef MAP_PERFECT_278
1171 : #undef MAP_PERFECT_277
1172 : #undef MAP_PERFECT_276
1173 : #undef MAP_PERFECT_275
1174 : #undef MAP_PERFECT_274
1175 : #undef MAP_PERFECT_273
1176 : #undef MAP_PERFECT_272
1177 : #undef MAP_PERFECT_271
1178 : #undef MAP_PERFECT_270
1179 : #undef MAP_PERFECT_269
1180 : #undef MAP_PERFECT_268
1181 : #undef MAP_PERFECT_267
1182 : #undef MAP_PERFECT_266
1183 : #undef MAP_PERFECT_265
1184 : #undef MAP_PERFECT_264
1185 : #undef MAP_PERFECT_263
1186 : #undef MAP_PERFECT_262
1187 : #undef MAP_PERFECT_261
1188 : #undef MAP_PERFECT_260
1189 : #undef MAP_PERFECT_259
1190 : #undef MAP_PERFECT_258
1191 : #undef MAP_PERFECT_257
1192 : #undef MAP_PERFECT_256
1193 : #undef MAP_PERFECT_255
1194 : #undef MAP_PERFECT_254
1195 : #undef MAP_PERFECT_253
1196 : #undef MAP_PERFECT_252
1197 : #undef MAP_PERFECT_251
1198 : #undef MAP_PERFECT_250
1199 : #undef MAP_PERFECT_249
1200 : #undef MAP_PERFECT_248
1201 : #undef MAP_PERFECT_247
1202 : #undef MAP_PERFECT_246
1203 : #undef MAP_PERFECT_245
1204 : #undef MAP_PERFECT_244
1205 : #undef MAP_PERFECT_243
1206 : #undef MAP_PERFECT_242
1207 : #undef MAP_PERFECT_241
1208 : #undef MAP_PERFECT_240
1209 : #undef MAP_PERFECT_239
1210 : #undef MAP_PERFECT_238
1211 : #undef MAP_PERFECT_237
1212 : #undef MAP_PERFECT_236
1213 : #undef MAP_PERFECT_235
1214 : #undef MAP_PERFECT_234
1215 : #undef MAP_PERFECT_233
1216 : #undef MAP_PERFECT_232
1217 : #undef MAP_PERFECT_231
1218 : #undef MAP_PERFECT_230
1219 : #undef MAP_PERFECT_229
1220 : #undef MAP_PERFECT_228
1221 : #undef MAP_PERFECT_227
1222 : #undef MAP_PERFECT_226
1223 : #undef MAP_PERFECT_225
1224 : #undef MAP_PERFECT_224
1225 : #undef MAP_PERFECT_223
1226 : #undef MAP_PERFECT_222
1227 : #undef MAP_PERFECT_221
1228 : #undef MAP_PERFECT_220
1229 : #undef MAP_PERFECT_219
1230 : #undef MAP_PERFECT_218
1231 : #undef MAP_PERFECT_217
1232 : #undef MAP_PERFECT_216
1233 : #undef MAP_PERFECT_215
1234 : #undef MAP_PERFECT_214
1235 : #undef MAP_PERFECT_213
1236 : #undef MAP_PERFECT_212
1237 : #undef MAP_PERFECT_211
1238 : #undef MAP_PERFECT_210
1239 : #undef MAP_PERFECT_209
1240 : #undef MAP_PERFECT_208
1241 : #undef MAP_PERFECT_207
1242 : #undef MAP_PERFECT_206
1243 : #undef MAP_PERFECT_205
1244 : #undef MAP_PERFECT_204
1245 : #undef MAP_PERFECT_203
1246 : #undef MAP_PERFECT_202
1247 : #undef MAP_PERFECT_201
1248 : #undef MAP_PERFECT_200
1249 : #undef MAP_PERFECT_199
1250 : #undef MAP_PERFECT_198
1251 : #undef MAP_PERFECT_197
1252 : #undef MAP_PERFECT_196
1253 : #undef MAP_PERFECT_195
1254 : #undef MAP_PERFECT_194
1255 : #undef MAP_PERFECT_193
1256 : #undef MAP_PERFECT_192
1257 : #undef MAP_PERFECT_191
1258 : #undef MAP_PERFECT_190
1259 : #undef MAP_PERFECT_189
1260 : #undef MAP_PERFECT_188
1261 : #undef MAP_PERFECT_187
1262 : #undef MAP_PERFECT_186
1263 : #undef MAP_PERFECT_185
1264 : #undef MAP_PERFECT_184
1265 : #undef MAP_PERFECT_183
1266 : #undef MAP_PERFECT_182
1267 : #undef MAP_PERFECT_181
1268 : #undef MAP_PERFECT_180
1269 : #undef MAP_PERFECT_179
1270 : #undef MAP_PERFECT_178
1271 : #undef MAP_PERFECT_177
1272 : #undef MAP_PERFECT_176
1273 : #undef MAP_PERFECT_175
1274 : #undef MAP_PERFECT_174
1275 : #undef MAP_PERFECT_173
1276 : #undef MAP_PERFECT_172
1277 : #undef MAP_PERFECT_171
1278 : #undef MAP_PERFECT_170
1279 : #undef MAP_PERFECT_169
1280 : #undef MAP_PERFECT_168
1281 : #undef MAP_PERFECT_167
1282 : #undef MAP_PERFECT_166
1283 : #undef MAP_PERFECT_165
1284 : #undef MAP_PERFECT_164
1285 : #undef MAP_PERFECT_163
1286 : #undef MAP_PERFECT_162
1287 : #undef MAP_PERFECT_161
1288 : #undef MAP_PERFECT_160
1289 : #undef MAP_PERFECT_159
1290 : #undef MAP_PERFECT_158
1291 : #undef MAP_PERFECT_157
1292 : #undef MAP_PERFECT_156
1293 : #undef MAP_PERFECT_155
1294 : #undef MAP_PERFECT_154
1295 : #undef MAP_PERFECT_153
1296 : #undef MAP_PERFECT_152
1297 : #undef MAP_PERFECT_151
1298 : #undef MAP_PERFECT_150
1299 : #undef MAP_PERFECT_149
1300 : #undef MAP_PERFECT_148
1301 : #undef MAP_PERFECT_147
1302 : #undef MAP_PERFECT_146
1303 : #undef MAP_PERFECT_145
1304 : #undef MAP_PERFECT_144
1305 : #undef MAP_PERFECT_143
1306 : #undef MAP_PERFECT_142
1307 : #undef MAP_PERFECT_141
1308 : #undef MAP_PERFECT_140
1309 : #undef MAP_PERFECT_139
1310 : #undef MAP_PERFECT_138
1311 : #undef MAP_PERFECT_137
1312 : #undef MAP_PERFECT_136
1313 : #undef MAP_PERFECT_135
1314 : #undef MAP_PERFECT_134
1315 : #undef MAP_PERFECT_133
1316 : #undef MAP_PERFECT_132
1317 : #undef MAP_PERFECT_131
1318 : #undef MAP_PERFECT_130
1319 : #undef MAP_PERFECT_129
1320 : #undef MAP_PERFECT_128
1321 : #undef MAP_PERFECT_127
1322 : #undef MAP_PERFECT_126
1323 : #undef MAP_PERFECT_125
1324 : #undef MAP_PERFECT_124
1325 : #undef MAP_PERFECT_123
1326 : #undef MAP_PERFECT_122
1327 : #undef MAP_PERFECT_121
1328 : #undef MAP_PERFECT_120
1329 : #undef MAP_PERFECT_119
1330 : #undef MAP_PERFECT_118
1331 : #undef MAP_PERFECT_117
1332 : #undef MAP_PERFECT_116
1333 : #undef MAP_PERFECT_115
1334 : #undef MAP_PERFECT_114
1335 : #undef MAP_PERFECT_113
1336 : #undef MAP_PERFECT_112
1337 : #undef MAP_PERFECT_111
1338 : #undef MAP_PERFECT_110
1339 : #undef MAP_PERFECT_109
1340 : #undef MAP_PERFECT_108
1341 : #undef MAP_PERFECT_107
1342 : #undef MAP_PERFECT_106
1343 : #undef MAP_PERFECT_105
1344 : #undef MAP_PERFECT_104
1345 : #undef MAP_PERFECT_103
1346 : #undef MAP_PERFECT_102
1347 : #undef MAP_PERFECT_101
1348 : #undef MAP_PERFECT_100
1349 : #undef MAP_PERFECT_99
1350 : #undef MAP_PERFECT_98
1351 : #undef MAP_PERFECT_97
1352 : #undef MAP_PERFECT_96
1353 : #undef MAP_PERFECT_95
1354 : #undef MAP_PERFECT_94
1355 : #undef MAP_PERFECT_93
1356 : #undef MAP_PERFECT_92
1357 : #undef MAP_PERFECT_91
1358 : #undef MAP_PERFECT_90
1359 : #undef MAP_PERFECT_89
1360 : #undef MAP_PERFECT_88
1361 : #undef MAP_PERFECT_87
1362 : #undef MAP_PERFECT_86
1363 : #undef MAP_PERFECT_85
1364 : #undef MAP_PERFECT_84
1365 : #undef MAP_PERFECT_83
1366 : #undef MAP_PERFECT_82
1367 : #undef MAP_PERFECT_81
1368 : #undef MAP_PERFECT_80
1369 : #undef MAP_PERFECT_79
1370 : #undef MAP_PERFECT_78
1371 : #undef MAP_PERFECT_77
1372 : #undef MAP_PERFECT_76
1373 : #undef MAP_PERFECT_75
1374 : #undef MAP_PERFECT_74
1375 : #undef MAP_PERFECT_73
1376 : #undef MAP_PERFECT_72
1377 : #undef MAP_PERFECT_71
1378 : #undef MAP_PERFECT_70
1379 : #undef MAP_PERFECT_69
1380 : #undef MAP_PERFECT_68
1381 : #undef MAP_PERFECT_67
1382 : #undef MAP_PERFECT_66
1383 : #undef MAP_PERFECT_65
1384 : #undef MAP_PERFECT_64
1385 : #undef MAP_PERFECT_63
1386 : #undef MAP_PERFECT_62
1387 : #undef MAP_PERFECT_61
1388 : #undef MAP_PERFECT_60
1389 : #undef MAP_PERFECT_59
1390 : #undef MAP_PERFECT_58
1391 : #undef MAP_PERFECT_57
1392 : #undef MAP_PERFECT_56
1393 : #undef MAP_PERFECT_55
1394 : #undef MAP_PERFECT_54
1395 : #undef MAP_PERFECT_53
1396 : #undef MAP_PERFECT_52
1397 : #undef MAP_PERFECT_51
1398 : #undef MAP_PERFECT_50
1399 : #undef MAP_PERFECT_49
1400 : #undef MAP_PERFECT_48
1401 : #undef MAP_PERFECT_47
1402 : #undef MAP_PERFECT_46
1403 : #undef MAP_PERFECT_45
1404 : #undef MAP_PERFECT_44
1405 : #undef MAP_PERFECT_43
1406 : #undef MAP_PERFECT_42
1407 : #undef MAP_PERFECT_41
1408 : #undef MAP_PERFECT_40
1409 : #undef MAP_PERFECT_39
1410 : #undef MAP_PERFECT_38
1411 : #undef MAP_PERFECT_37
1412 : #undef MAP_PERFECT_36
1413 : #undef MAP_PERFECT_35
1414 : #undef MAP_PERFECT_34
1415 : #undef MAP_PERFECT_33
1416 : #undef MAP_PERFECT_32
1417 : #undef MAP_PERFECT_31
1418 : #undef MAP_PERFECT_30
1419 : #undef MAP_PERFECT_29
1420 : #undef MAP_PERFECT_28
1421 : #undef MAP_PERFECT_27
1422 : #undef MAP_PERFECT_26
1423 : #undef MAP_PERFECT_25
1424 : #undef MAP_PERFECT_24
1425 : #undef MAP_PERFECT_23
1426 : #undef MAP_PERFECT_22
1427 : #undef MAP_PERFECT_21
1428 : #undef MAP_PERFECT_20
1429 : #undef MAP_PERFECT_19
1430 : #undef MAP_PERFECT_18
1431 : #undef MAP_PERFECT_17
1432 : #undef MAP_PERFECT_16
1433 : #undef MAP_PERFECT_15
1434 : #undef MAP_PERFECT_14
1435 : #undef MAP_PERFECT_13
1436 : #undef MAP_PERFECT_12
1437 : #undef MAP_PERFECT_11
1438 : #undef MAP_PERFECT_10
1439 : #undef MAP_PERFECT_9
1440 : #undef MAP_PERFECT_8
1441 : #undef MAP_PERFECT_7
1442 : #undef MAP_PERFECT_6
1443 : #undef MAP_PERFECT_5
1444 : #undef MAP_PERFECT_4
1445 : #undef MAP_PERFECT_3
1446 : #undef MAP_PERFECT_2
1447 : #undef MAP_PERFECT_1
1448 : #undef MAP_PERFECT_0
|
