Theiling Online: erwin/map.h

1 /*-*- Mode: C -*-*/ 2 /* 3 * Author: Henrik Theiling 4 * Description: 5 * Support functions for the map template parts of the Erwin-- 6 * library. These are basically hash functions for standard types. 7 * 8 * @@Begin: Licencing and Copying@@ 9 * 10 * Copyright (c) Henrik Theiling 11 * Licence Version 2, Special Version for Erwin. 12 * 13 * The term 'this software' used in the following, additional to its 14 * usual usage, also includes the instantiated source files generated by 15 * tools of this package. 16 * 17 * This software is provided 'as-is', without warranty of any kind, 18 * express or implied. In no event will the authors or copyright holders 19 * be held liable for any damages arising from the use of this software. 20 * 21 * Permission is granted to anyone to use this software for any purpose, 22 * including commercial applications, and to alter it and redistribute it 23 * freely, subject to the following restrictions: 24 * 25 * 1. The origin of this software must not be misrepresented; you must 26 * not claim that you wrote the original software. If you use this 27 * software in a product, an acknowledgment in the product documentation 28 * would be appreciated. 29 * 30 * 2. Altered source versions must be plainly marked as such, and must 31 * not be misrepresented as being the original software. 32 * 33 * 3. You must not use any of the names of the authors or copyright 34 * holders of the original software for advertising or publicity 35 * pertaining to distribution without specific, written prior permission. 36 * 37 * 4. If you change this software and redistribute parts or all of it in 38 * any form, you must make the source code of the altered version of this 39 * software available. As an exception, files that were generated by 40 * tools of this package may be used freely, including modification. 41 * 42 * 5. This notice must not be removed or altered from any source 43 * distribution. 44 * 45 * This licence is governed by the Laws of Germany. Disputes shall be 46 * settled by Saarbruecken City Court. 47 * 48 * @@End: Licencing and Copying@@ 49 * 50 * ---------------------------------------------------------------------- */ 51 52 #ifdef ERWIN_DEBUG_INCLUDE 53 #warning "Including map.h." 54 #endif 55 56 #ifndef Global_ERWIN_MAP_H 57 #define Global_ERWIN_MAP_H 58 59 #ifdef ERWIN_DEBUG_INCLUDE 60 #warning "First inclusion of map.h." 61 #endif 62 63 #ifdef Global_ERWIN_COMPILING 64 #include "--INCPREF2B--erwin/defs.h" 65 #else 66 #include <--INCPREF2B--erwin/defs.h> 67 #endif 68 69 #ifdef Global_ERWIN_ADAM_NAME 70 71 #COPYNAME char_to_upper 72 #COPYNAME char_to_lower 73 #COPYNAME erwin_random_table 74 #COPYNAME erwin_mapinitialised 75 #COPYNAME char_hash 76 #COPYNAME char_hash2 77 #COPYNAME char_hash3 78 #COPYNAME char_hash4 79 #COPYNAME char_case_hash 80 #COPYNAME char_case_hash2 81 #COPYNAME char_case_hash3 82 #COPYNAME char_case_hash4 83 #COPYNAME long_hash 84 #COPYNAME int_hash 85 #COPYNAME short_hash 86 #COPYNAME hash_voidp 87 #COPYNAME string_hash 88 #COPYNAME string_case_hash 89 #COPYNAME erwininternalmaperrno 90 #COPYNAME erwininternalmapstrerror 91 #COPYNAME ERWININTERNALMAPOK 92 #COPYNAME ERWININTERNALMAPISOK 93 #COPYNAME ERWININTERNALMAPISERROR 94 #COPYNAME ERWININTERNALMAPISWARNING 95 #COPYNAME ERWININTERNALMAPERRNOMEM 96 #COPYNAME ERWININTERNALMAPERRASSERTIONFAILED 97 #COPYNAME ERWININTERNALMAPWARNEMPTY 98 #COPYNAME ERWININTERNALMAPWARNNOMOREELEMS 99 #COPYNAME ERWININTERNALMAPWARNEXISTINGKEY 100 #COPYNAME ERWININTERNALMAPWARNKEYNOTFOUND 101 #COPYNAME ERWININTERNALMAPREHASHNOMEM 102 #COPYNAME ERWININTERNALMAPREHASHDUPLICATEKEY 103 #COPYNAME ERWININTERNALMAPREHASHRECURSION 104 105 #else /* !defined(Global_ERWIN_ADAM_NAME) */ 106 107 #ifdef __cplusplus 108 extern "C" { 109 #endif 110 111 /* These are in base.c but are needed here already. */ 112 extern char Global_char_to_upper (char) ATTR_CONST; 113 extern char Global_char_to_lower (char) ATTR_CONST; 114 115 #define Global_erwin_toupper Global_char_to_upper 116 #define Global_erwin_tolower Global_char_to_lower 117 118 extern Global_ERWIN_BOOL Global_erwin_mapinitialised; 119 120 /* Hashing */ 121 122 #ifdef Global_ERWIN_REQUIRE_DETERMINISM 123 typedef Global_hashval_t const Global_erwin_random_table_t[256]; 124 #else 125 typedef Global_hashval_t Global_erwin_random_table_t[256]; 126 #endif 127 128 #if Global_ERWIN_HASH_STRENGTH >= 1 129 extern Global_erwin_random_table_t Global_erwin_random_table; 130 extern Global_erwin_random_table_t Global_erwin_random_table2; 131 #if Global_ERWIN_HASH_STRENGTH >= 3 132 extern Global_erwin_random_table_t Global_erwin_random_table3; 133 extern Global_erwin_random_table_t Global_erwin_random_table4; 134 #endif 135 #endif 136 137 /* Convenience definitions for old applications. */ 138 #ifdef Global_ERWIN_COMPAT_2_0_236 139 # define Global_hash_char Global_char_hash 140 # define Global_hash_char_case Global_char_case_hash 141 # define Global_hash_long Global_long_hash 142 # define Global_hash_int Global_int_hash 143 # define Global_hash_short Global_short_hash 144 # define Global_hash_string Global_string_hash 145 # define Global_hash_string_case Global_string_case_hash 146 #endif 147 148 #define Global_erwin_hash0(X) (((((Global_hashval_t)(X)) * 3) + \ 149 (((Global_hashval_t)(X)) * 7131) + \ 150 (((Global_hashval_t)(X)) * 9111371)) ^ \ 151 (((Global_hashval_t)(X)) * 755543)) 152 153 154 ERWIN_WRAPPER Global_hashval_t Global_char_hash(unsigned char x) ATTR_PURE; 155 ERWIN_WRAPPER Global_hashval_t Global_char_hash(unsigned char x) 156 { 157 #if Global_ERWIN_HASH_STRENGTH >= 1 158 return Global_erwin_random_table[x]; 159 #else 160 return Global_erwin_hash0(x); 161 #endif 162 } 163 164 #define Global_unsigned_char_hash Global_char_hash 165 #define Global_signed_char_hash Global_char_hash 166 167 ERWIN_WRAPPER Global_hashval_t Global_char_hash2(unsigned char x) ATTR_PURE; 168 ERWIN_WRAPPER Global_hashval_t Global_char_hash2(unsigned char x) 169 { 170 #if Global_ERWIN_HASH_STRENGTH >= 1 171 return Global_erwin_random_table2[x]; 172 #else 173 return Global_char_hash (x); 174 #endif 175 } 176 177 ERWIN_WRAPPER Global_hashval_t Global_char_hash3(unsigned char x) ATTR_PURE; 178 ERWIN_WRAPPER Global_hashval_t Global_char_hash3(unsigned char x) 179 { 180 #if Global_ERWIN_HASH_STRENGTH >= 3 181 return Global_erwin_random_table3[x]; 182 #else 183 return Global_char_hash (x); 184 #endif 185 } 186 187 ERWIN_WRAPPER Global_hashval_t Global_char_hash4(unsigned char x) ATTR_PURE; 188 ERWIN_WRAPPER Global_hashval_t Global_char_hash4(unsigned char x) 189 { 190 #if Global_ERWIN_HASH_STRENGTH >= 3 191 return Global_erwin_random_table4[x]; 192 #else 193 return Global_char_hash2 (x); 194 #endif 195 } 196 197 /* Internal function, do not use! It may change or disappear without notice! */ 198 ERWIN_WRAPPER Global_hashval_t Global_erwin_mul9 (Global_hashval_t x) ATTR_CONST; 199 ERWIN_WRAPPER Global_hashval_t Global_erwin_mul9 (Global_hashval_t x) 200 { 201 return x + (x << 3); 202 /* i386/x86_64 and probably many: one cycle by using 'lea' */ 203 } 204 205 #ifndef Global_erwin_mul_x1_defined 206 207 /* Internal function, do not use! It may change or disappear without notice! */ 208 ERWIN_WRAPPER Global_hashval_t Global_erwin_mul_x1 (Global_hashval_t x) ATTR_CONST; 209 ERWIN_WRAPPER Global_hashval_t Global_erwin_mul_x1 (Global_hashval_t x) 210 { 211 #if Global_SIZEOF_HASHVAL_T == 8 && defined(ERWIN_U64) 212 return x * ERWIN_U64_C(0x0000800200400081); 213 #else 214 return x * 0x400081; 215 /* i386/x86_64: hardward multiplier, so mul ist fast. 216 * Other architectures may want to use shift & add: 217 * 218 * return x + (x << 7) + (x << 22) 219 */ 220 #endif 221 } 222 223 #endif /* Global_erwin_mul_x1_defined */ 224 225 226 /* Basic hash functions that may be available as assembly versions. 227 * 228 * All of these hash functions are collision-free, except when compiling 229 * with required determinism. In that case, long_hash() is constructed 230 * in such a way that it hashes 'unsigned int' and 'int' in the same 231 * way as int_hash(), which requires artificial introduction of collisions. 232 */ 233 #ifndef Global_erwin_u16_hash_defined 234 235 ERWIN_WRAPPER Global_hashval_t Global_erwin_u16_hash (ERWIN_U16 x) ATTR_PURE; 236 ERWIN_WRAPPER Global_hashval_t Global_erwin_u16_hash (ERWIN_U16 x) 237 { 238 Global_hashval_t y= x; 239 240 y^= Global_erwin_swap16(x) << 1; 241 y+= Global_char_hash ((unsigned char)y); 242 y= Global_erwin_mul_x1 (y); 243 y^= Global_char_hash2 ((unsigned char)(y >> 8)); 244 245 return y; 246 } 247 248 #endif /* Global_erwin_u16_hash_defined */ 249 250 #ifndef Global_erwin_u32_hash_defined 251 252 ERWIN_WRAPPER Global_hashval_t Global_erwin_u32_hash (ERWIN_U32 x) ATTR_PURE; 253 ERWIN_WRAPPER Global_hashval_t Global_erwin_u32_hash (ERWIN_U32 x) 254 { 255 Global_hashval_t y= x; 256 257 y^= Global_erwin_swap_low32(y) << 1; 258 y+= Global_char_hash ((unsigned char)y); 259 y= Global_erwin_mul_x1 (y); 260 y^= Global_char_hash2 ((unsigned char)(y >> 8)); 261 262 /* gcc 4: 263 264 x86_64, 32-bit: 265 movl %edx, %eax 266 bswapl %eax 267 roll $1,%eax 268 xorl %edx, %eax 269 movzbl %al, %edx 270 addl erwin_random_table(,%rdx,4), %eax 271 imull $4194433, %eax, %eax 272 movzbl %ah, %edx 273 xorl erwin_random_table2(,%rdx,4), %eax 274 275 x86_64, 64-bit: 276 mov %edx, %edx 277 movq %rdx, %rax 278 bswapl %eax 279 rolq $1,%rax 280 xorq %rdx, %rax 281 movzbl %al, %edx 282 addq erwin_random_table(,%rdx,8), %rax 283 movabsq $140746082484353, %rdx 284 imulq %rdx, %rax 285 movzbl %ah, %edx 286 xorq erwin_random_table2(,%rdx,8), %rax 287 */ 288 289 return y; 290 } 291 292 #endif /* Global_erwin_u32_hash_defined */ 293 294 #ifdef ERWIN_U64 295 #ifndef Global_erwin_u64_hash_defined 296 297 ERWIN_WRAPPER Global_hashval_t Global_erwin_u64_hash (ERWIN_U64 x) ATTR_PURE; 298 ERWIN_WRAPPER Global_hashval_t Global_erwin_u64_hash (ERWIN_U64 x) 299 { 300 Global_hashval_t y; 301 302 #if defined(Global_ERWIN_REQUIRE_DETERMINISM) 303 /* In this case, this function must hash values in int and unsigned 304 * range in the same way as erwin_u32, otherwise long_hash(x) is 305 * different on 32 vs. 64 bits, despite the same bit width of hashval_t. */ 306 307 y= Global_erwin_u32_hash((ERWIN_U32)x); 308 { 309 ERWIN_U32 x32= (ERWIN_U32)(x >> 32); 310 if (x32 && ~x32) { 311 y^= Global_erwin_swap_low32 (x32) << 1; 312 y+= Global_char_hash3 ((unsigned char)y); 313 y= Global_erwin_mul_x1 (y); 314 y^= Global_char_hash4 ((unsigned char)(y >> 8)); 315 } 316 } 317 318 #else /* !REQUIRE_DETERMINISM */ 319 320 y= (Global_hashval_t)x; 321 322 #if Global_SIZEOF_HASHVAL_T == 8 323 y^= Global_erwin_swap64(y) << 1; 324 #else 325 y^= Global_erwin_swap_low32(y) << 1; 326 y^= Global_erwin_swap_low32((Global_hashval_t)(x >> 32)) << 3; 327 #endif 328 y+= Global_char_hash ((unsigned char)y); 329 y= Global_erwin_mul_x1 (y); 330 y^= Global_char_hash2 ((unsigned char)(y >> 8)); 331 332 #endif /* !REQUIRE_DETERMINISM */ 333 334 return y; 335 } 336 337 #endif /* Global_erwin_u64_hash_defined */ 338 #endif /* ERWIN_U64 */ 339 340 ERWIN_WRAPPER Global_hashval_t Global_short_hash (unsigned short x) ATTR_PURE; 341 ERWIN_WRAPPER Global_hashval_t Global_short_hash (unsigned short x) 342 { 343 return Global_erwin_u16_hash (x); 344 } 345 346 #define Global_unsigned_short_hash Global_short_hash 347 348 ERWIN_WRAPPER Global_hashval_t Global_int_hash(unsigned int x) ATTR_PURE; 349 ERWIN_WRAPPER Global_hashval_t Global_int_hash(unsigned int x) 350 { 351 #if SIZEOF_INT == 8 && defined(ERWIN_U64) 352 return Global_erwin_u64_hash (x); 353 #elif SIZEOF_INT == 2 354 return Global_erwin_u16_hash (x); 355 #else 356 return Global_erwin_u32_hash (x); 357 #endif 358 } 359 360 #define Global_unsigned_hash Global_int_hash 361 362 ERWIN_WRAPPER Global_hashval_t Global_long_hash(unsigned long x) ATTR_PURE; 363 ERWIN_WRAPPER Global_hashval_t Global_long_hash(unsigned long x) 364 { 365 #if SIZEOF_LONG == 8 && defined(ERWIN_U64) 366 return Global_erwin_u64_hash (x); 367 #else 368 return Global_erwin_u32_hash (x); 369 #endif 370 } 371 372 #define Global_unsigned_long_hash Global_long_hash 373 374 #if defined(ERWIN_UNSIGNED_LONG_LONG) && defined(ERWIN_U64) 375 376 ERWIN_WRAPPER Global_hashval_t Global_long_long_hash(ERWIN_UNSIGNED_LONG_LONG x) ATTR_PURE; 377 ERWIN_WRAPPER Global_hashval_t Global_long_long_hash(ERWIN_UNSIGNED_LONG_LONG x) 378 { 379 return Global_erwin_u64_hash (x); 380 } 381 382 #define Global_unsigned_long_long_hash Global_long_long_hash 383 384 #endif 385 386 ERWIN_WRAPPER Global_hashval_t Global_voidp_hash (void const *x) ATTR_PURE; 387 ERWIN_WRAPPER Global_hashval_t Global_voidp_hash (void const *x) 388 { 389 #if SIZEOF_VOIDP == SIZEOF_LONG 390 return Global_long_hash ((unsigned long)x); 391 #else 392 return Global_int_hash ((unsigned int)x); 393 #endif 394 } 395 396 ERWIN_WRAPPER Global_hashval_t Global_size_t_hash(size_t x) ATTR_PURE; 397 ERWIN_WRAPPER Global_hashval_t Global_size_t_hash(size_t x) 398 { 399 #if SIZEOF_SIZE_T == 8 && defined(ERWIN_U64) 400 return Global_erwin_u64_hash (x); 401 #elif SIZEOF_SIZE_T == 2 402 return Global_erwin_u16_hash (x); 403 #else 404 return Global_erwin_u32_hash (x); 405 #endif 406 } 407 408 /* Shoot, this has a bad name. Use voidp_hash() instead. 409 * We keep it for compatibility, but mark it deprecated: */ 410 ERWIN_WRAPPER Global_hashval_t Global_hash_voidp (void const *x) ATTR_PURE ATTR_DEPRECATED; 411 ERWIN_WRAPPER Global_hashval_t Global_hash_voidp (void const *x) 412 { 413 return Global_voidp_hash (x); 414 } 415 416 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash(unsigned char x) ATTR_PURE; 417 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash(unsigned char x) 418 { 419 return Global_char_hash ((unsigned char)Global_char_to_lower((char)x)); 420 } 421 422 #define Global_unsigned_char_case_hash Global_char_case_hash 423 #define Global_signed_char_case_hash Global_char_case_hash 424 425 426 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash2(unsigned char x) ATTR_PURE; 427 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash2(unsigned char x) 428 { 429 return Global_char_hash2 ((unsigned char)Global_char_to_lower((char)x)); 430 } 431 432 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash3(unsigned char x) ATTR_PURE; 433 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash3(unsigned char x) 434 { 435 return Global_char_hash3 ((unsigned char)Global_char_to_lower((char)x)); 436 } 437 438 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash4(unsigned char x) ATTR_PURE; 439 ERWIN_WRAPPER Global_hashval_t Global_char_case_hash4(unsigned char x) 440 { 441 return Global_char_hash4 ((unsigned char)Global_char_to_lower((char)x)); 442 } 443 444 ERWIN_WRAPPER Global_hashval_t Global_erwin_make_hash_result( 445 Global_hashval_t, Global_hashval_t) ATTR_PURE; 446 447 ERWIN_WRAPPER Global_hashval_t Global_erwin_make_hash_result( 448 Global_hashval_t h1, Global_hashval_t h2) 449 { 450 #if Global_SIZEOF_HASHVAL_T == 4 && defined(ERWIN_U64) 451 return Global_erwin_u64_hash (((ERWIN_U64)h1) + (((ERWIN_U64)h2) << 32)); 452 #else 453 Global_hashval_t y; 454 455 y= h1; 456 y^= Global_char_hash4 ((unsigned char)(y >> 8)); 457 y+= h2; 458 y^= Global_erwin_swap (y) << 1; 459 y+= Global_char_hash3 ((unsigned char)y); 460 461 return y; 462 #endif 463 } 464 465 /* And another one for hashing memory areas of a given size (with various sizes). 466 * All functions take the pointer to the array and the number of elements of the array 467 * to be hashed: */ 468 extern Global_hashval_t Global_erwin_u8_array_hash (ERWIN_U8 const *, size_t) ATTR_PURE; 469 extern Global_hashval_t Global_erwin_u8_array_case_hash (ERWIN_U8 const *, size_t) ATTR_PURE; 470 extern Global_hashval_t Global_erwin_u16_array_hash (ERWIN_U16 const *, size_t) ATTR_PURE; 471 extern Global_hashval_t Global_erwin_u32_array_hash (ERWIN_U32 const *, size_t) ATTR_PURE; 472 473 #ifdef ERWIN_U64 474 extern Global_hashval_t Global_erwin_u64_array_hash (ERWIN_U64 const *, size_t) ATTR_PURE; 475 #endif 476 477 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_array_hash (ERWIN_S8 const *x, size_t s) ATTR_PURE; 478 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_array_hash (ERWIN_S8 const *x, size_t s) 479 { 480 return Global_erwin_u8_array_hash((ERWIN_U8*)x,s); 481 } 482 483 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_array_case_hash (ERWIN_S8 const *x, size_t s) ATTR_PURE; 484 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_array_case_hash (ERWIN_S8 const *x, size_t s) 485 { 486 return Global_erwin_u8_array_case_hash ((ERWIN_U8*)x,s); 487 } 488 489 ERWIN_WRAPPER Global_hashval_t Global_erwin_s16_array_hash (ERWIN_S16 const *x, size_t s) ATTR_PURE; 490 ERWIN_WRAPPER Global_hashval_t Global_erwin_s16_array_hash (ERWIN_S16 const *x, size_t s) 491 { 492 return Global_erwin_u16_array_hash((ERWIN_U16*)x,s); 493 } 494 495 ERWIN_WRAPPER Global_hashval_t Global_erwin_s32_array_hash (ERWIN_S32 const *x, size_t s) ATTR_PURE; 496 ERWIN_WRAPPER Global_hashval_t Global_erwin_s32_array_hash (ERWIN_S32 const *x, size_t s) 497 { 498 return Global_erwin_u32_array_hash((ERWIN_U32*)x,s); 499 } 500 501 #if defined(ERWIN_U64) && defined(ERWIN_S64) 502 ERWIN_WRAPPER Global_hashval_t Global_erwin_s64_array_hash (ERWIN_S64 const *x, size_t s) ATTR_PURE; 503 ERWIN_WRAPPER Global_hashval_t Global_erwin_s64_array_hash (ERWIN_S64 const *x, size_t s) 504 { 505 return Global_erwin_u64_array_hash((ERWIN_U64*)x,s); 506 } 507 #endif 508 509 ERWIN_WRAPPER Global_hashval_t Global_erwin_u8_hash (ERWIN_S8 x) ATTR_PURE; 510 ERWIN_WRAPPER Global_hashval_t Global_erwin_u8_hash (ERWIN_S8 x) 511 { 512 return Global_char_hash((ERWIN_U8)x); 513 } 514 515 ERWIN_WRAPPER Global_hashval_t Global_erwin_u8_hash_case (ERWIN_S8 x) ATTR_PURE; 516 ERWIN_WRAPPER Global_hashval_t Global_erwin_u8_hash_case (ERWIN_S8 x) 517 { 518 return Global_char_case_hash ((ERWIN_U8)x); 519 } 520 521 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_hash (ERWIN_S8 x) ATTR_PURE; 522 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_hash (ERWIN_S8 x) 523 { 524 return Global_char_hash((ERWIN_U8)x); 525 } 526 527 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_hash_case (ERWIN_S8 x) ATTR_PURE; 528 ERWIN_WRAPPER Global_hashval_t Global_erwin_s8_hash_case (ERWIN_S8 x) 529 { 530 return Global_char_case_hash ((ERWIN_U8)x); 531 } 532 533 ERWIN_WRAPPER Global_hashval_t Global_erwin_s16_hash (ERWIN_S16 x) ATTR_PURE; 534 ERWIN_WRAPPER Global_hashval_t Global_erwin_s16_hash (ERWIN_S16 x) 535 { 536 return Global_erwin_u16_hash((ERWIN_U16)x); 537 } 538 539 ERWIN_WRAPPER Global_hashval_t Global_erwin_s32_hash (ERWIN_S32 x) ATTR_PURE; 540 ERWIN_WRAPPER Global_hashval_t Global_erwin_s32_hash (ERWIN_S32 x) 541 { 542 return Global_erwin_u32_hash((ERWIN_U32)x); 543 } 544 545 #if defined(ERWIN_U64) && defined(ERWIN_S64) 546 ERWIN_WRAPPER Global_hashval_t Global_erwin_s64_hash (ERWIN_S64 const x) ATTR_PURE; 547 ERWIN_WRAPPER Global_hashval_t Global_erwin_s64_hash (ERWIN_S64 const x) 548 { 549 return Global_erwin_u64_hash((ERWIN_U64)x); 550 } 551 #endif 552 553 554 #define Global_erwin_char_array_hash(x,s) Global_erwin_u8_array_hash((ERWIN_U8 const *)x,s) 555 556 #if SIZEOF_SHORT == 2 557 #define Global_erwin_short_array_hash(x,s) Global_erwin_u16_array_hash((ERWIN_U16 const *)x,s) 558 #endif 559 560 #if SIZEOF_INT == 2 561 #define Global_erwin_int_array_hash(x,s) Global_erwin_u16_array_hash((ERWIN_U16 const *)x,s) 562 #elif SIZEOF_INT == 4 563 #define Global_erwin_int_array_hash(x,s) Global_erwin_u32_array_hash((ERWIN_U32 const *)x,s) 564 #elif SIZEOF_INT == 8 565 #define Global_erwin_int_array_hash(x,s) Global_erwin_u64_array_hash((ERWIN_U64 const *)x,s) 566 #endif 567 568 #if SIZEOF_LONG == 4 569 #define Global_erwin_long_array_hash(x,s) Global_erwin_u32_array_hash((ERWIN_U32 const *)x,s) 570 #elif SIZEOF_LONG == 8 571 #define Global_erwin_long_array_hash(x,s) Global_erwin_u64_array_hash((ERWIN_U64 const *)x,s) 572 #endif 573 574 575 #ifdef __cplusplus 576 /* overloaded versions: */ 577 extern "C++" { 578 579 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (bool x) ATTR_PURE; 580 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (bool x) 581 { 582 return Global_char_hash (x); 583 } 584 585 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (char x) ATTR_PURE; 586 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (char x) 587 { 588 return Global_char_hash (x); 589 } 590 591 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (signed char x) ATTR_PURE; 592 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (signed char x) 593 { 594 return Global_char_hash (x); 595 } 596 597 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned char x) ATTR_PURE; 598 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned char x) 599 { 600 return Global_char_hash (x); 601 } 602 603 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (short x) ATTR_PURE; 604 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (short x) 605 { 606 return Global_short_hash (x); 607 } 608 609 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned short x) ATTR_PURE; 610 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned short x) 611 { 612 return Global_short_hash (x); 613 } 614 615 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (int x) ATTR_PURE; 616 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (int x) 617 { 618 return Global_int_hash (x); 619 } 620 621 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned x) ATTR_PURE; 622 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned x) 623 { 624 return Global_int_hash (x); 625 } 626 627 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (long x) ATTR_PURE; 628 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (long x) 629 { 630 return Global_long_hash (x); 631 } 632 633 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned long x) ATTR_PURE; 634 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (unsigned long x) 635 { 636 return Global_long_hash (x); 637 } 638 639 #ifdef ERWIN_LONG_LONG 640 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (ERWIN_LONG_LONG x) ATTR_PURE; 641 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (ERWIN_LONG_LONG x) 642 { 643 return Global_long_long_hash (x); 644 } 645 646 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (ERWIN_UNSIGNED_LONG_LONG x) ATTR_PURE; 647 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (ERWIN_UNSIGNED_LONG_LONG x) 648 { 649 return Global_long_long_hash (x); 650 } 651 #endif /* defined ERWIN_LONG_LONG */ 652 653 654 /* Pointers */ 655 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (void const *x) ATTR_PURE; 656 ERWIN_WRAPPER Global_hashval_t Global_erwin_hash (void const *x) 657 { 658 return Global_voidp_hash (x); 659 } 660 661 /* Other pointers are not hashed in a default way, because it is up to the 662 * user to decide whether the pointer or the contents are to be hashed. */ 663 664 } /* extern "C++" */ 665 #endif /* C++ */ 666 667 /* NOTE: string_hash and string_case_hash are now in base.h. */ 668 669 /* ********************************************************************** */ 670 /* Combine multiple hash values into one. Use these macros instead of 671 * thinking of something yourself when you write hash functions for your 672 * own macros so that the macros can eventually be improved if necessary 673 * and your code automatically improves, too. 674 * 675 * Use them as follows (example for a struct): 676 * 677 * hashval_t mypair_hash (struct mypair_t const *x) 678 * { 679 * Global_erwin_hash_state_t state; 680 * 681 * Global_ERWIN_STATE_INIT (state); 682 * Global_ERWIN_STATE_MIX_ORDERED2(state, mytype1_hash(x->a), mytype2_hash(x->b)); 683 * 684 * return Global_ERWIN_STATE_GET_HASHVAL(state); 685 * } 686 * 687 * Or a string. You may use ERWIN_HASH_INIT* for quick hash values for special 688 * keys: 689 * 690 * hashval_t mystring_hash (mytype_t const *x) 691 * { 692 * if (x == NULL) 693 * return ERWIN_HASH_INIT; 694 * 695 * Global_erwin_hash_state_t state; 696 * Global_ERWIN_STATE_INIT(state); 697 * 698 * for (; *x; x++) 699 * Global_ERWIN_STATE_MIX_ORDERED (state, mytype_hash(*x)); 700 * 701 * return Global_ERWIN_STATE_GET_HASHVAL(state); 702 * } 703 * 704 * Use the _UNORDERED variants if the iteration is non-deterministic (e.g. in 705 * randomised hash tables). 706 * 707 * To speed up a bit, you can have a slightly faster initialisation (we're talking 708 * about a few machine instructions here), you can ERWIN_STATE_INIT_WITH(s,first_value) 709 * instead of ERWIN_STATE_INIT(s); ERWIN_STATE_MIX_ORDERED(s,first_value). This 710 * is handy since many structure have a size + dynamic set of elements, and for 711 * the size, this comes in handy. Don't bother to optimise too much, though. If 712 * you have two initial values, use the normal ERWIN_STATE_MIX_ORDERED2 instead to 713 * add them too the hash state. 714 * 715 * The result of such a construction of have values via a state will be very good 716 * hash values. No need for another hashval_t_hash(). You can directly use 717 * (hashval % size) or better erwin_hash_into(hashval,size), which uses multiplication 718 * instead of division, to reduce the hashval to a given size. 719 */ 720 721 /* Combine some digits: 722 723 (setq *print-base* 16) 724 (setf (long-float-digits) 800) 725 (integer-decode-float pi) 726 727 32 bits: 728 C90FDAA2 729 2168C234 730 C4C6628B 731 80DC1CD1 732 29024E08 733 8A67CC74 734 020BBEA6 735 3B139B22 736 514A0879 737 8E3404DD 738 EF9519B3 739 CD3A431B 740 ... 741 742 64 bits: 743 C90FDAA22168C234 744 C4C6628B80DC1CD1 745 29024E088A67CC74 746 020BBEA63B139B22 747 514A08798E3404DD 748 EF9519B3CD3A431B 749 302B0A6DF25F1437 750 4FE1356D6D51C245 751 E485B576625E7EC6 752 F44C42E9A637ED6B 753 0BFF5CB6F406B7ED 754 EE386BFB5A899FA5 755 ... 756 */ 757 758 759 /* Some initial hashvalues (quite arbitrary, actually, these are the first 760 * few digits of pi (shifted)): */ 761 #if Global_SIZEOF_HASHVAL_T == 8 762 # define ?Global_ERWIN_HASH_INIT Global_HASHVAL_C(0xC90FDAA22168C234) 763 # define ?Global_ERWIN_HASH_INIT2 Global_HASHVAL_C(0xC4C6628B80DC1CD1) 764 # define ?Global_ERWIN_HASH_INIT3 Global_HASHVAL_C(0x29024E088A67CC74) 765 # define ?Global_ERWIN_HASH_INIT4 Global_HASHVAL_C(0x020BBEA63B139B22) 766 # define ?Global_ERWIN_HASH_INIT5 Global_HASHVAL_C(0x514A08798E3404DD) 767 # define ?Global_ERWIN_HASH_INIT6 Global_HASHVAL_C(0xEF9519B3CD3A431B) 768 # define ?Global_ERWIN_HASH_INIT7 Global_HASHVAL_C(0x302B0A6DF25F1437) 769 # define ?Global_ERWIN_HASH_INIT8 Global_HASHVAL_C(0x4FE1356D6D51C245) 770 # define ?Global_ERWIN_HASH_INIT9 Global_HASHVAL_C(0xE485B576625E7EC6) 771 #else 772 # define ?Global_ERWIN_HASH_INIT Global_HASHVAL_C(0xC90FDAA2) 773 # define ?Global_ERWIN_HASH_INIT2 Global_HASHVAL_C(0x2168C234) 774 # define ?Global_ERWIN_HASH_INIT3 Global_HASHVAL_C(0xC4C6628B) 775 # define ?Global_ERWIN_HASH_INIT4 Global_HASHVAL_C(0x80DC1CD1) 776 # define ?Global_ERWIN_HASH_INIT5 Global_HASHVAL_C(0x29024E08) 777 # define ?Global_ERWIN_HASH_INIT6 Global_HASHVAL_C(0x8A67CC74) 778 # define ?Global_ERWIN_HASH_INIT7 Global_HASHVAL_C(0x020BBEA6) 779 # define ?Global_ERWIN_HASH_INIT8 Global_HASHVAL_C(0x3B139B22) 780 # define ?Global_ERWIN_HASH_INIT9 Global_HASHVAL_C(0x514A0879) 781 #endif 782 783 /* For data structures with deterministic combination order: */ 784 #define ?Global_ERWIN_HASH_MIX_ORDERED(h1,h2,newvalue) \ 785 do{ \ 786 h2^= Global_erwin_ror1(h1) - ((Global_hashval_t)(newvalue)); \ 787 h1+= Global_erwin_mul9(h2); \ 788 }while(0) 789 790 /* Another function for combining two values at once: */ 791 #define ?Global_ERWIN_HASH_MIX_ORDERED2(h1,h2,newvalue1,newvalue2) \ 792 do{ \ 793 h2^= Global_erwin_ror1(h1) - ((Global_hashval_t)(newvalue1)); \ 794 h1+= Global_erwin_mul9(h2) ^ newvalue2; \ 795 }while(0) 796 797 #define ?Global_ERWIN_HASH_MIX_ORDERED3(h1,h2,n1,n2,n3) \ 798 do{ \ 799 Global_ERWIN_HASH_MIX_ORDERED2(h1,h2,n1,n2); \ 800 Global_ERWIN_HASH_MIX_ORDERED (h1,h2,n3); \ 801 }while(0) 802 803 #define ?Global_ERWIN_HASH_MIX_ORDERED4(h1,h2,n1,n2,n3,n4) \ 804 do{ \ 805 Global_ERWIN_HASH_MIX_ORDERED2(h1,h2,n1,n2); \ 806 Global_ERWIN_HASH_MIX_ORDERED2(h1,h2,n3,n4); \ 807 }while(0) 808 809 #define ?Global_ERWIN_HASH_MIX_ORDERED5(h1,h2,n1,n2,n3,n4,n5) \ 810 do{ \ 811 Global_ERWIN_HASH_MIX_ORDERED3(h1,h2,n1,n2,n3); \ 812 Global_ERWIN_HASH_MIX_ORDERED2(h1,h2,n4,n5); \ 813 }while(0) 814 815 #define ?Global_ERWIN_HASH_RESULT_ORDERED(h1,h2) \ 816 Global_erwin_make_hash_result(h1,h2) 817 818 /* For data structures with non-deterministic combination order. 819 * It is assumed that the arguments of these functions are in 820 * deterministic order, i.e., that you hash a non-deterministic 821 * sequence of n record entries each: 822 * MIX(h,i,a,b) ; order of lines non-deterministic, but 823 * MIX(h,i,a,b) ; never b,a instead of a,b 824 * ... 825 * MIX(h,i,a,b) 826 * If this is not the case, the easiest way to mix the result 827 * is to use a simple + or ^. 828 */ 829 830 #define ?Global_ERWIN_HASH_MIX_UNORDERED(h1,h2,newvalue) \ 831 do{ \ 832 h1^= ((Global_hashval_t)(newvalue)); \ 833 }while(0) 834 835 /* Another function for combining two values at once: */ 836 #define ?Global_ERWIN_HASH_MIX_UNORDERED2(h1,h2,newvalue1,newvalue2) \ 837 do{ \ 838 h1^= ((Global_hashval_t)(newvalue1)); \ 839 h2+= newvalue2; \ 840 }while(0) 841 842 #define ?Global_ERWIN_HASH_MIX_UNORDERED3(h1,h2,n1,n2,n3) \ 843 do{ \ 844 Global_ERWIN_HASH_MIX_UNORDERED2(h1,h2,n1,n2); \ 845 Global_ERWIN_HASH_MIX_UNORDERED (h1,h2,n3); \ 846 }while(0) 847 848 #define ?Global_ERWIN_HASH_MIX_UNORDERED4(h1,h2,n1,n2,n3,n4) \ 849 do{ \ 850 Global_ERWIN_HASH_MIX_UNORDERED2(h1,h2,n1,n2); \ 851 Global_ERWIN_HASH_MIX_UNORDERED2(h1,h2,n3,n4); \ 852 }while(0) 853 854 #define ?Global_ERWIN_HASH_MIX_UNORDERED5(h1,h2,n1,n2,n3,n4,n5) \ 855 do{ \ 856 Global_ERWIN_HASH_MIX_UNORDERED3(h1,h2,n1,n2,n3); \ 857 Global_ERWIN_HASH_MIX_UNORDERED2(h1,h2,n4,n5); \ 858 }while(0) 859 860 /* the following function is provided for compatibility with older 861 * versions. It is of no use. */; 862 #define ?Global_ERWIN_HASH_RESULT_UNORDERED \ 863 Global_ERWIN_HASH_RESULT_ORDERED 864 865 /* The more modern state based interface which leaves more space for 866 * future improvements. */ 867 #define ?Global_ERWIN_STATE_INIT(s) \ 868 do{ \ 869 s.h1= Global_ERWIN_HASH_INIT2; \ 870 s.h2= Global_ERWIN_HASH_INIT3; \ 871 }while(0) 872 873 #define ?Global_ERWIN_STATE_INIT_WITH(s,h) \ 874 do{ \ 875 s.h1= Global_ERWIN_HASH_INIT2 - ((Global_hashval_t)h); \ 876 s.h2= Global_ERWIN_HASH_INIT3; \ 877 }while(0) 878 879 880 struct Global_erwin_hash_state_t { 881 Global_hashval_t h1; 882 Global_hashval_t h2; 883 }; 884 885 #ifndef __cplusplus 886 typedef struct Global_erwin_hash_state_t Global_erwin_hash_state_t; 887 #endif 888 889 #define ?Global_ERWIN_STATE_MIX_ORDERED(s,n1) \ 890 Global_ERWIN_HASH_MIX_ORDERED(s.h1,s.h2,n1) 891 892 #define ?Global_ERWIN_STATE_MIX_ORDERED2(s,n1,n2) \ 893 Global_ERWIN_HASH_MIX_ORDERED2(s.h1,s.h2,n1,n2) 894 895 #define ?Global_ERWIN_STATE_MIX_ORDERED3(s,n1,n2,n3) \ 896 Global_ERWIN_HASH_MIX_ORDERED3(s.h1,s.h2,n1,n2,n3) 897 898 #define ?Global_ERWIN_STATE_MIX_ORDERED4(s,n1,n2,n3,n4) \ 899 Global_ERWIN_HASH_MIX_ORDERED4(s.h1,s.h2,n1,n2,n3,n4) 900 901 #define ?Global_ERWIN_STATE_MIX_ORDERED5(s,n1,n2,n3,n4,n5) \ 902 Global_ERWIN_HASH_MIX_ORDERED5(s.h1,s.h2,n1,n2,n3,n4,n5) 903 904 905 #define ?Global_ERWIN_STATE_MIX_UNORDERED(s,n1) \ 906 Global_ERWIN_HASH_MIX_UNORDERED(s.h1,s.h2,n1) 907 908 #define ?Global_ERWIN_STATE_MIX_UNORDERED2(s,n1,n2) \ 909 Global_ERWIN_HASH_MIX_UNORDERED2(s.h1,s.h2,n1,n2) 910 911 #define ?Global_ERWIN_STATE_MIX_UNORDERED3(s,n1,n2,n3) \ 912 Global_ERWIN_HASH_MIX_UNORDERED2(s.h1,s.h2,n1,n2,n3) 913 914 #define ?Global_ERWIN_STATE_MIX_UNORDERED4(s,n1,n2,n3,n4) \ 915 Global_ERWIN_HASH_MIX_UNORDERED2(s.h1,s.h2,n1,n2,n3,n4) 916 917 #define ?Global_ERWIN_STATE_MIX_UNORDERED5(s,n1,n2,n3,n4,n5) \ 918 Global_ERWIN_HASH_MIX_UNORDERED2(s.h1,s.h2,n1,n2,n3,n4,n5) 919 920 921 #define ?Global_ERWIN_STATE_GET_HASHVAL(s) \ 922 Global_ERWIN_HASH_RESULT_ORDERED(s.h1,s.h2) 923 924 925 /* 926 * The implementation of global errno is not straightforward when using 927 * a complex string replacement algorithm like the template mechanism 928 * of Erwin--. E.g. we cannot declare a global map_errno, because 929 * someone might choose to map `map' to `hash'. Then the instantiated 930 * templates would not be able to be liked with this library. Therefore, 931 * we must introduce stupid names which hopefully no-one remaps to 932 * something strange. Then, {map,vector}_errno (or whatever they will 933 * be renamed to) are macros mapping to one of the following variables. 934 * 935 * Another problem is that map_errno is a global variable which is not 936 * thread safe. Therefore, its declaration is not straightforward... 937 */ 938 /* must be in sync with map.c: */ 939 #if !defined(Global_ERWIN_THREAD_SAFE) || Global_ERWIN_USE_THREAD_KEYWORD 940 extern Global_ERWIN_THREAD_LOCAL int Global_erwininternalmaperrno; 941 #elif Global_ERWIN_USE_PTHREAD 942 extern int *Global_erwininternalmaperrnoptr(void); 943 #define Global_erwininternalmaperrno (*Global_erwininternalmaperrnoptr()) 944 #endif 945 946 extern char const *Global_erwininternalmapstrerror (int) ATTR_PURE; 947 948 #define Global_ERWININTERNALMAPOK 1 949 /* The value 0 is not used for error codes because 0 is polymorphic 950 * and can be a pointer. 1 cannot. */ 951 952 #define Global_ERWININTERNALMAPISOK(X) ((X) == Global_ERWININTERNALMAPOK) 953 #define Global_ERWININTERNALMAPISERROR(X) ((X) < Global_ERWININTERNALMAPOK) 954 #define Global_ERWININTERNALMAPISWARNING(X) ((X) > Global_ERWININTERNALMAPOK) 955 956 #define Global_ERWININTERNALMAPERRNOMEM (-2) 957 #define Global_ERWININTERNALMAPERRASSERTIONFAILED (-5) 958 959 #define Global_ERWININTERNALMAPWARNEMPTY 5 960 #define Global_ERWININTERNALMAPWARNNOMOREELEMS 6 961 #define Global_ERWININTERNALMAPWARNEXISTINGKEY 7 962 #define Global_ERWININTERNALMAPWARNKEYNOTFOUND 8 963 964 #define Global_ERWININTERNALMAPREHASHNOMEM 2 965 #define Global_ERWININTERNALMAPREHASHDUPLICATEKEY 3 966 #define Global_ERWININTERNALMAPREHASHRECURSION 4 967 968 #ifdef __cplusplus 969 } 970 #endif 971 972 #endif /* defined(Global_ERWIN_ADAM_NAME) */ 973 974 #endif /* Global_ERWIN_ERWIN_MAP_H */

Index

Conlangs
Cyberspace
- Bünde (East-Westfalia)
- Cubics
- East-Westfalia
- Gifts
- Saarbrücken
- Virtual Restaurant
  - Menu
  - Menu
  - Recipes
  - Wine
    - Bordeaux
    - Dornfelder
    - Greece
    - Merlot
    - Pinot Gris
    - Portugal
    - Sicily
    - Sweet
Docs
Hardware
- e-mage
- Wine Rack
History
- Aromator
- Sinclair ZX Spectrum
Language
Software
Misc
- Animal
- Downloads
- Marriage
- Music
- Sitemap
- Wrong Spellings
Links
- .org Pages
- Recommendations
- University
- Uta
- Work