1/* Sequential list data type implemented by a hash table with another list. 2 Copyright (C) 2006 Free Software Foundation, Inc. 3 Written by Bruno Haible <bruno@clisp.org>, 2006. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 17 18/* Common code of 19 gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ 20 21/* Array of primes, approximately in steps of factor 1.2. 22 This table was computed by executing the Common Lisp expression 23 (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i)))) 24 and feeding the result to PARI/gp. */ 25static const size_t primes[] = 26 { 27 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199, 28 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543, 29 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899, 30 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849, 31 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887, 32 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277, 33 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307, 34 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233, 35 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469, 36 171731387, 206077643, 247293161, 296751781, 356102141, 427322587, 37 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331, 38 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL, 39 3810050851UL, 40#if SIZE_MAX > 4294967295UL 41 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL, 42 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL, 43 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL, 44 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL, 45 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL, 46 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL, 47 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL, 48 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL, 49 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL, 50 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL, 51 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL, 52 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL, 53 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL, 54 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL, 55 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL, 56 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL, 57 923114351670013UL, 1107737222003791UL, 1329284666404567UL, 58 1595141599685509UL, 1914169919622551UL, 2297003903547091UL, 59 2756404684256459UL, 3307685621107757UL, 3969222745329323UL, 60 4763067294395177UL, 5715680753274209UL, 6858816903929113UL, 61 8230580284714831UL, 9876696341657791UL, 11852035609989371UL, 62 14222442731987227UL, 17066931278384657UL, 20480317534061597UL, 63 24576381040873903UL, 29491657249048679UL, 35389988698858471UL, 64 42467986438630267UL, 50961583726356109UL, 61153900471627387UL, 65 73384680565952851UL, 88061616679143347UL, 105673940014972061UL, 66 126808728017966413UL, 152170473621559703UL, 182604568345871671UL, 67 219125482015045997UL, 262950578418055169UL, 315540694101666193UL, 68 378648832921999397UL, 454378599506399233UL, 545254319407679131UL, 69 654305183289214771UL, 785166219947057701UL, 942199463936469157UL, 70 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL, 71 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL, 72 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL, 73 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL, 74 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL, 75 17419784962119465179UL, 76#endif 77 SIZE_MAX /* sentinel, to ensure the search terminates */ 78 }; 79 80/* Return a suitable prime >= ESTIMATE. */ 81static size_t 82next_prime (size_t estimate) 83{ 84 size_t i; 85 86 for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++) 87 if (primes[i] >= estimate) 88 return primes[i]; 89 return SIZE_MAX; /* not a prime, but better than nothing */ 90} 91 92/* Resize the hash table with a new estimated size. */ 93static void 94hash_resize (gl_list_t list, size_t estimate) 95{ 96 size_t new_size = next_prime (estimate); 97 98 if (new_size > list->table_size) 99 { 100 gl_hash_entry_t *old_table = list->table; 101 /* Allocate the new table. */ 102 gl_hash_entry_t *new_table = XCALLOC (new_size, gl_hash_entry_t); 103 size_t i; 104 105 /* Iterate through the entries of the old table. */ 106 for (i = list->table_size; i > 0; ) 107 { 108 gl_hash_entry_t node = old_table[--i]; 109 110 while (node != NULL) 111 { 112 gl_hash_entry_t next = node->hash_next; 113 /* Add the entry to the new table. */ 114 size_t bucket = node->hashcode % new_size; 115 node->hash_next = new_table[bucket]; 116 new_table[bucket] = node; 117 118 node = next; 119 } 120 } 121 122 list->table = new_table; 123 list->table_size = new_size; 124 free (old_table); 125 } 126} 127