/* AbiSource Program Utilities * * Copyright (C) 2001 Mike Nordell * Copyright (C) 2001 Dom Lachowicz * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA * 02111-1307, USA. */ #include #include "ut_hash.h" #include "ut_string_class.h" #include "ut_vector.h" #include "ut_debugmsg.h" /*********************************************************************/ /*********************************************************************/ const UT_uint32 _Hash_magic_numbers[] = { 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 619, 631, 641, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 829, 839, 853, 859, 863, 877, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1019, 1021, 1031, 1039, 1049, 1051, 1061, 1069, 1087, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1223, 1231, 1237, 1249, 1259, 1277, 1289, 1301, 1307, 1319, 1327, 1361, 1373, 1381, 1399, 1409, 1423, 1433, 1447, 1459, 1471, 1483, 1493, 1499, 1511, 1523, 1531, 1543, 1553, 1567, 1579, 1583, 1597, 1609, 1621, 1637, 1657, 1669, 1693, 1709, 1723, 1733, 1747, 1759, 1777, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1879, 1889, 1907, 1913, 1931, 1949, 1951, 1973, 1987, 2003, 2017, 2029, 2039, 2053, 2069, 2089, 2099, 2113, 2131, 2143, 2161, 2179, 2203, 2221, 2243, 2251, 2273, 2293, 2311, 2333, 2351, 2371, 2393, 2411, 2423, 2447, 2467, 2477, 2503, 2521, 2543, 2557, 2579, 2593, 2617, 2633, 2659, 2683, 2707, 2731, 2753, 2777, 2803, 2819, 2843, 2861, 2887, 2909, 2927, 2953, 2971, 2999, 3023, 3049, 3079, 3109, 3137, 3167, 3191, 3221, 3253, 3271, 3301, 3331, 3361, 3391, 3413, 3433, 3467, 3499, 3533, 3559, 3593, 3623, 3659, 3691, 3727, 3761, 3797, 3833, 3863, 3889, 3923, 3947, 3967, 4003, 4027, 4057, 4093, 4133, 4159, 4177, 4217, 4259, 4297, 4339, 4373, 4409, 4451, 4493, 4523, 4567, 4603, 4649, 4691, 4733, 4759, 4801, 4831, 4877, 4919, 4967, 5011, 5059, 5107, 5153, 5197, 5237, 5281, 5333, 5381, 5431, 5483, 5531, 5581, 5623, 5669, 5717, 5749, 5801, 5857, 5903, 5953, 6011, 6067, 6121, 6173, 6229, 6287, 6343, 6397, 6451, 6491, 6553, 6607, 6673, 6737, 6803, 6871, 6917, 6983, 7043, 7109, 7177, 7247, 7309, 7369, 7433, 7507, 7577, 7649, 7723, 7793, 7867, 7937, 8011, 8089, 8167, 8243, 8317, 8389, 8467, 8543, 8627, 8713, 8783, 8867, 8951, 9029, 9109, 9199, 9283, 9371, 9463, 9551, 9643, 9739, 9833, 9931, 10009, 10103, 10193, 10289, 10391, 10487, 10589, 10691, 10789, 10891, 10993, 11093, 11197, 11299, 11411, 11519, 11633, 11743, 11839, 11953, 12071, 12163, 12281, 12401, 12517, 12641, 12763, 12889, 13009, 13127, 13249, 13381, 13513, 13633, 13763, 13883, 14011, 14149, 14281, 14423, 14563, 14699, 14843, 14983, 15131, 15277, 15427, 15581, 15733, 15889, 16033, 16193, 16349, 16493, 16657, 16823, 16987, 17137, 17299, 17471, 17627, 17791, 17959, 18133, 18313, 18493, 18671, 18839, 19013, 19183, 19373, 19559, 19753, 19949, 20147, 20347, 20549, 20753, 20959, 21163, 21347, 21559, 21773, 21977, 22193, 22409, 22621, 22817, 23041, 23269, 23497, 23719, 23929, 24151, 24391, 24631, 24877, 25121, 25367, 25609, 25849, 26107, 26357, 26597, 26861, 27127, 27397, 27653, 27919, 28183, 28463, 28729, 29009, 29297, 29587, 29881, 30169, 30469, 30773, 31079, 31387, 31699, 32009, 32327, 32647, 32971, 33289, 33619, 33941, 34273, 34613, 34949, 35291, 35617, 35969, 36319, 36677, 37039, 37409, 37783, 38153, 38501, 38873, 39251, 39631, 40013, 40387, 40787, 41189, 41597, 41999, 42409, 42829, 43237, 43669, 44101, 44537, 44971, 45413, 45863, 46309, 46771, 47237, 47701, 48163, 48623, 49109, 49597, 50087, 50587, 51071, 51581, 52081, 52583, 53101, 53629, 54163, 54679, 55219, 55763, 56311, 56873, 57427, 57991, 58567, 59149, 59729, 60317, 60919, 61519, 62131, 62743, 63367, 63997, 64633, 65269, 65921, 66571, 67231, 67901, 68567, 69247, 69931, 70627, 71333, 72043, 72763, 73483, 74209, 74941, 75689, 76441, 77201, 77969, 78737, 79493, 80287, 81083, 81883, 82699, 83497, 84319, 85159, 85999, 86857, 87721, 88591, 89459, 90353, 91253, 92153, 93059, 93983, 94907, 95819, 96769, 97729, 98689, 99667, 100649, 101653, 102667, 103687, 104723, 105769, 106823, 107881, 108959, 110039, 111127, 112237, 113359, 114487, 115631, 116747, 117911, 119089, 120277, 121469, 122663, 123887, 125119, 126359, 127609, 128879, 130147, 131447, 132761, 134087, 135427, 136777, 138143, 139511, 140897, 142297, 143719, 145139, 146581, 148021, 149497, 150991, 152461, 153953, 155473, 157019, 158581, 160163, 161761, 163367, 164999, 166643, 168293, 169957, 171653, 173359, 175081, 176819, 178571, 180347, 182141, 183959, 185797, 187651, 189523, 191413, 193327, 195259, 197207, 199153, 201139, 203141, 205171, 207199, 209269, 211349, 213461, 215587, 217739, 219911, 222109, 224327, 226553, 228799, 231079, 233371, 235699, 238039, 240379, 242779, 245183, 247633, 250109, 252607, 255133, 257671, 260231, 262819, 265427, 268069, 270749, 273433, 276151, 278911, 281683, 284489, 287333, 290201, 293099, 296027, 298943, 301927, 304943, 307969, 311041, 314137, 317269, 320431, 323623, 326831, 330097, 333397, 336727, 340079, 343433, 346867, 350293, 353783, 357319, 360869, 364471, 368111, 371779, 375481, 379207, 382999, 386809, 390673, 394579, 398509, 402487, 406507, 410561, 414653, 418799, 422969, 427181, 431449, 435763, 440101, 444487, 448927, 453379, 457903, 462481, 467101, 471769, 476479, 481231, 486043, 490891, 495799, 500741, 505727, 510773, 515873, 521023, 526231, 531481, 536791, 542153, 547567, 553037, 558563, 564133, 569773, 575441, 581183, 586981, 592849, 598777, 604759, 610801, 616909, 623071, 629281, 635567, 641909, 648317, 654799, 661343, 667949, 674603, 681341, 688147, 695021, 701969, 708979, 716063, 723221, 730451, 737753, 745117, 752527, 760043, 767633, 775309, 783043, 790871, 798773, 806737, 814799, 822907, 831109, 839413, 847789, 856249, 864811, 873437, 882169, 890969, 899863, 908861, 917927, 927097, 936361, 945701, 955153, 964703, 974329, 984059, 993893, 1003819,1013851,1023977, 1034207,1044529,1054957,1065503,1076143,1086901,1097743,1108717, 1119799,1130981,1142287,1153687,1165223,1176871,1188637,1200509, 1212487,1224599,1236827,1249187,1261649,1274249,1286983,1299841, 1312823,1325941,1339199,1352557,1366031,1379681,1393471,1407397, 1421461,1435669,1450021,1464503,1479139,1493929,1508867,1523953, 1539149,1554529,1570073,1585769,1601623,1617619,1633789,1650109, 1666607,1683271,1700099,1717099,1734247,1751587,1769101,1786787, 1804643,1822673,1840877,1859281,1877873,1896647,1915609,1934761, 1954097,1973633,1993367,2013299,2033429,2053757,2074279,2095021, 2115961,2137117,2158483,2180051,2201839,2223857,2246077,2268517, 2291197,2314097,2337233,2360597,2384197,2408011,2432077,2456383, 2480927,2505707,2530751,2556041,2581597,2607403,2633473,2659801, 2686393,2713253,2740379,2767771,2795437,2823389,2851621,2880131, 2908931,2938009,2967389,2997031,3027001,3057253,3087811,3118673, 3149851,3181349,3213151,3245267,3277699,3310469,3343559,3376993, 3410753,3444851,3479249,3514013,3549137,3584617,3620443,3656641, 3693203,3730093,3767389,3805057,3843107,3881509,3920311,3959507, 3999067,4039051,4079431,4120223,4161419,4203019,4245029,4287473, 4330343,4373623,4417351,4461493,4506053,4551103,4596607,4642549, 4688951,4735823,4783169,4830967,4879267,4928029,4977263,5027023, 5077283,5128037,5179303,5231089,5283389,5336209,5389543,5443429, 5497861,5552819,5608331,5664401,5721041,5778251,5836027,5894377, 5953319,6012847,6072973,6133669,6195001,6256951,6319513,6382699, 6446513,6510967,6576067,6641827,6708227,6775273,6843019,6911447, 6980551,7050353,7120847,7192043,7263959,7336577,7409921,7484011, 7558843,7634387,7710719,7787803,7865657,7944301,8023739,8103971, 8184977,8266807,8349433,8432923,8517233,8602397,8688409,8775287, 8863037,8951659,9041173,9131579,9222887,9315109,9408257,9502333, 9597349,9693317,9790229,9888127,9987001 }; const UT_uint32 _Hash_n_magic_numbers = sizeof _Hash_magic_numbers / sizeof *_Hash_magic_numbers; UT_uint32 _Recommended_hash_size(UT_uint32 size) // Verifies reasonably { UT_uint32 lo = 0; UT_uint32 hi = _Hash_n_magic_numbers - 1; while (lo < hi) { UT_uint32 mid = (hi + lo) / 2; UT_uint32 s = _Hash_magic_numbers[mid]; if (s < size) lo = mid + 1; else if (s > size) hi = mid - 1; else return s; } if (_Hash_magic_numbers[lo] < size) lo++; if (lo >= _Hash_n_magic_numbers) return (UT_uint32)-1; return _Hash_magic_numbers[lo]; }