spacepaste

Paste details

reply | raw

  1.  
  2. #include <cstdint>
  3. #include <cstddef>
  4. #include <functional>
  5. #include <vector>
  6. #include <cmath>
  7. #include <array>
  8. #include <algorithm>
  9. #include <iterator>
  10. #include <utility>
  11. #include <type_traits>
  12. struct prime_number_hash_policy
  13. {
  14. size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const
  15. {
  16. switch(prime_index)
  17. {
  18. case 0:
  19. return 0llu;
  20. case 1:
  21. return hash % 2llu;
  22. case 2:
  23. return hash % 3llu;
  24. case 3:
  25. return hash % 5llu;
  26. case 4:
  27. return hash % 7llu;
  28. case 5:
  29. return hash % 11llu;
  30. case 6:
  31. return hash % 13llu;
  32. case 7:
  33. return hash % 17llu;
  34. case 8:
  35. return hash % 23llu;
  36. case 9:
  37. return hash % 29llu;
  38. case 10:
  39. return hash % 37llu;
  40. case 11:
  41. return hash % 47llu;
  42. case 12:
  43. return hash % 59llu;
  44. case 13:
  45. return hash % 73llu;
  46. case 14:
  47. return hash % 97llu;
  48. case 15:
  49. return hash % 127llu;
  50. case 16:
  51. return hash % 151llu;
  52. case 17:
  53. return hash % 197llu;
  54. case 18:
  55. return hash % 251llu;
  56. case 19:
  57. return hash % 313llu;
  58. case 20:
  59. return hash % 397llu;
  60. case 21:
  61. return hash % 499llu;
  62. case 22:
  63. return hash % 631llu;
  64. case 23:
  65. return hash % 797llu;
  66. case 24:
  67. return hash % 1009llu;
  68. case 25:
  69. return hash % 1259llu;
  70. case 26:
  71. return hash % 1597llu;
  72. case 27:
  73. return hash % 2011llu;
  74. case 28:
  75. return hash % 2539llu;
  76. case 29:
  77. return hash % 3203llu;
  78. case 30:
  79. return hash % 4027llu;
  80. case 31:
  81. return hash % 5087llu;
  82. case 32:
  83. return hash % 6421llu;
  84. case 33:
  85. return hash % 8089llu;
  86. case 34:
  87. return hash % 10193llu;
  88. case 35:
  89. return hash % 12853llu;
  90. case 36:
  91. return hash % 16193llu;
  92. case 37:
  93. return hash % 20399llu;
  94. case 38:
  95. return hash % 25717llu;
  96. case 39:
  97. return hash % 32401llu;
  98. case 40:
  99. return hash % 40823llu;
  100. case 41:
  101. return hash % 51437llu;
  102. case 42:
  103. return hash % 64811llu;
  104. case 43:
  105. return hash % 81649llu;
  106. case 44:
  107. return hash % 102877llu;
  108. case 45:
  109. return hash % 129607llu;
  110. case 46:
  111. return hash % 163307llu;
  112. case 47:
  113. return hash % 205759llu;
  114. case 48:
  115. return hash % 259229llu;
  116. case 49:
  117. return hash % 326617llu;
  118. case 50:
  119. return hash % 411527llu;
  120. case 51:
  121. return hash % 518509llu;
  122. case 52:
  123. return hash % 653267llu;
  124. case 53:
  125. return hash % 823117llu;
  126. case 54:
  127. return hash % 1037059llu;
  128. case 55:
  129. return hash % 1306601llu;
  130. case 56:
  131. return hash % 1646237llu;
  132. case 57:
  133. return hash % 2074129llu;
  134. case 58:
  135. return hash % 2613229llu;
  136. case 59:
  137. return hash % 3292489llu;
  138. case 60:
  139. return hash % 4148279llu;
  140. case 61:
  141. return hash % 5226491llu;
  142. case 62:
  143. return hash % 6584983llu;
  144. case 63:
  145. return hash % 8296553llu;
  146. case 64:
  147. return hash % 10453007llu;
  148. case 65:
  149. return hash % 13169977llu;
  150. case 66:
  151. return hash % 16593127llu;
  152. case 67:
  153. return hash % 20906033llu;
  154. case 68:
  155. return hash % 26339969llu;
  156. case 69:
  157. return hash % 33186281llu;
  158. case 70:
  159. return hash % 41812097llu;
  160. case 71:
  161. return hash % 52679969llu;
  162. case 72:
  163. return hash % 66372617llu;
  164. case 73:
  165. return hash % 83624237llu;
  166. case 74:
  167. return hash % 105359939llu;
  168. case 75:
  169. return hash % 132745199llu;
  170. case 76:
  171. return hash % 167248483llu;
  172. case 77:
  173. return hash % 210719881llu;
  174. case 78:
  175. return hash % 265490441llu;
  176. case 79:
  177. return hash % 334496971llu;
  178. case 80:
  179. return hash % 421439783llu;
  180. case 81:
  181. return hash % 530980861llu;
  182. case 82:
  183. return hash % 668993977llu;
  184. case 83:
  185. return hash % 842879579llu;
  186. case 84:
  187. return hash % 1061961721llu;
  188. case 85:
  189. return hash % 1337987929llu;
  190. case 86:
  191. return hash % 1685759167llu;
  192. case 87:
  193. return hash % 2123923447llu;
  194. case 88:
  195. return hash % 2675975881llu;
  196. case 89:
  197. return hash % 3371518343llu;
  198. case 90:
  199. return hash % 4247846927llu;
  200. case 91:
  201. return hash % 5351951779llu;
  202. case 92:
  203. return hash % 6743036717llu;
  204. case 93:
  205. return hash % 8495693897llu;
  206. case 94:
  207. return hash % 10703903591llu;
  208. case 95:
  209. return hash % 13486073473llu;
  210. case 96:
  211. return hash % 16991387857llu;
  212. case 97:
  213. return hash % 21407807219llu;
  214. case 98:
  215. return hash % 26972146961llu;
  216. case 99:
  217. return hash % 33982775741llu;
  218. case 100:
  219. return hash % 42815614441llu;
  220. case 101:
  221. return hash % 53944293929llu;
  222. case 102:
  223. return hash % 67965551447llu;
  224. case 103:
  225. return hash % 85631228929llu;
  226. case 104:
  227. return hash % 107888587883llu;
  228. case 105:
  229. return hash % 135931102921llu;
  230. case 106:
  231. return hash % 171262457903llu;
  232. case 107:
  233. return hash % 215777175787llu;
  234. case 108:
  235. return hash % 271862205833llu;
  236. case 109:
  237. return hash % 342524915839llu;
  238. case 110:
  239. return hash % 431554351609llu;
  240. case 111:
  241. return hash % 543724411781llu;
  242. case 112:
  243. return hash % 685049831731llu;
  244. case 113:
  245. return hash % 863108703229llu;
  246. case 114:
  247. return hash % 1087448823553llu;
  248. case 115:
  249. return hash % 1370099663459llu;
  250. case 116:
  251. return hash % 1726217406467llu;
  252. case 117:
  253. return hash % 2174897647073llu;
  254. case 118:
  255. return hash % 2740199326961llu;
  256. case 119:
  257. return hash % 3452434812973llu;
  258. case 120:
  259. return hash % 4349795294267llu;
  260. case 121:
  261. return hash % 5480398654009llu;
  262. case 122:
  263. return hash % 6904869625999llu;
  264. case 123:
  265. return hash % 8699590588571llu;
  266. case 124:
  267. return hash % 10960797308051llu;
  268. case 125:
  269. return hash % 13809739252051llu;
  270. case 126:
  271. return hash % 17399181177241llu;
  272. case 127:
  273. return hash % 21921594616111llu;
  274. case 128:
  275. return hash % 27619478504183llu;
  276. case 129:
  277. return hash % 34798362354533llu;
  278. case 130:
  279. return hash % 43843189232363llu;
  280. case 131:
  281. return hash % 55238957008387llu;
  282. case 132:
  283. return hash % 69596724709081llu;
  284. case 133:
  285. return hash % 87686378464759llu;
  286. case 134:
  287. return hash % 110477914016779llu;
  288. case 135:
  289. return hash % 139193449418173llu;
  290. case 136:
  291. return hash % 175372756929481llu;
  292. case 137:
  293. return hash % 220955828033581llu;
  294. case 138:
  295. return hash % 278386898836457llu;
  296. case 139:
  297. return hash % 350745513859007llu;
  298. case 140:
  299. return hash % 441911656067171llu;
  300. case 141:
  301. return hash % 556773797672909llu;
  302. case 142:
  303. return hash % 701491027718027llu;
  304. case 143:
  305. return hash % 883823312134381llu;
  306. case 144:
  307. return hash % 1113547595345903llu;
  308. case 145:
  309. return hash % 1402982055436147llu;
  310. case 146:
  311. return hash % 1767646624268779llu;
  312. case 147:
  313. return hash % 2227095190691797llu;
  314. case 148:
  315. return hash % 2805964110872297llu;
  316. case 149:
  317. return hash % 3535293248537579llu;
  318. case 150:
  319. return hash % 4454190381383713llu;
  320. case 151:
  321. return hash % 5611928221744609llu;
  322. case 152:
  323. return hash % 7070586497075177llu;
  324. case 153:
  325. return hash % 8908380762767489llu;
  326. case 154:
  327. return hash % 11223856443489329llu;
  328. case 155:
  329. return hash % 14141172994150357llu;
  330. case 156:
  331. return hash % 17816761525534927llu;
  332. case 157:
  333. return hash % 22447712886978529llu;
  334. case 158:
  335. return hash % 28282345988300791llu;
  336. case 159:
  337. return hash % 35633523051069991llu;
  338. case 160:
  339. return hash % 44895425773957261llu;
  340. case 161:
  341. return hash % 56564691976601587llu;
  342. case 162:
  343. return hash % 71267046102139967llu;
  344. case 163:
  345. return hash % 89790851547914507llu;
  346. case 164:
  347. return hash % 113129383953203213llu;
  348. case 165:
  349. return hash % 142534092204280003llu;
  350. case 166:
  351. return hash % 179581703095829107llu;
  352. case 167:
  353. return hash % 226258767906406483llu;
  354. case 168:
  355. return hash % 285068184408560057llu;
  356. case 169:
  357. return hash % 359163406191658253llu;
  358. case 170:
  359. return hash % 452517535812813007llu;
  360. case 171:
  361. return hash % 570136368817120201llu;
  362. case 172:
  363. return hash % 718326812383316683llu;
  364. case 173:
  365. return hash % 905035071625626043llu;
  366. case 174:
  367. return hash % 1140272737634240411llu;
  368. case 175:
  369. return hash % 1436653624766633509llu;
  370. case 176:
  371. return hash % 1810070143251252131llu;
  372. case 177:
  373. return hash % 2280545475268481167llu;
  374. case 178:
  375. return hash % 2873307249533267101llu;
  376. case 179:
  377. return hash % 3620140286502504283llu;
  378. case 180:
  379. return hash % 4561090950536962147llu;
  380. case 181:
  381. return hash % 5746614499066534157llu;
  382. case 182:
  383. return hash % 7240280573005008577llu;
  384. case 183:
  385. return hash % 9122181901073924329llu;
  386. case 184:
  387. return hash % 11493228998133068689llu;
  388. case 185:
  389. return hash % 14480561146010017169llu;
  390. case 186:
  391. return hash % 18446744073709551557llu;
  392. default:
  393. return hash;
  394. }
  395. }
  396. size_t index_for_hash_2(size_t hash, size_t /*num_slots_minus_one*/) const
  397. {
  398. static constexpr const size_t prime_list[] =
  399. {
  400. 2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu,
  401. 59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu,
  402. 499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu,
  403. 3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu,
  404. 20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu,
  405. 102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu,
  406. 411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu,
  407. 1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu,
  408. 6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu,
  409. 26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu,
  410. 83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu,
  411. 265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu,
  412. 842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu,
  413. 2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu,
  414. 8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu,
  415. 21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu,
  416. 53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu,
  417. 135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu,
  418. 342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu,
  419. 863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu,
  420. 2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu,
  421. 5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu,
  422. 13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu,
  423. 34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu,
  424. 87686378464759llu, 110477914016779llu, 139193449418173llu,
  425. 175372756929481llu, 220955828033581llu, 278386898836457llu,
  426. 350745513859007llu, 441911656067171llu, 556773797672909llu,
  427. 701491027718027llu, 883823312134381llu, 1113547595345903llu,
  428. 1402982055436147llu, 1767646624268779llu, 2227095190691797llu,
  429. 2805964110872297llu, 3535293248537579llu, 4454190381383713llu,
  430. 5611928221744609llu, 7070586497075177llu, 8908380762767489llu,
  431. 11223856443489329llu, 14141172994150357llu, 17816761525534927llu,
  432. 22447712886978529llu, 28282345988300791llu, 35633523051069991llu,
  433. 44895425773957261llu, 56564691976601587llu, 71267046102139967llu,
  434. 89790851547914507llu, 113129383953203213llu, 142534092204280003llu,
  435. 179581703095829107llu, 226258767906406483llu, 285068184408560057llu,
  436. 359163406191658253llu, 452517535812813007llu, 570136368817120201llu,
  437. 718326812383316683llu, 905035071625626043llu, 1140272737634240411llu,
  438. 1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu,
  439. 2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu,
  440. 5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu,
  441. 11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu
  442. };
  443. if (prime_index == 0) {
  444. return 0llu;
  445. } else if (prime_index > sizeof(prime_list)) {
  446. return hash;
  447. } else {
  448. return hash % prime_list[prime_index - 1];
  449. }
  450. }
  451. uint8_t next_size_over(size_t & size) const
  452. {
  453. // prime numbers generated by the following method:
  454. // 1. start with a prime p = 2
  455. // 2. go to wolfram alpha and get p = NextPrime(2 * p)
  456. // 3. repeat 2. until you overflow 64 bits
  457. // you now have large gaps which you would hit if somebody called reserve() with an unlucky number.
  458. // 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps
  459. // 5. get PrevPrime(2^64) and put it at the end
  460. static constexpr const size_t prime_list[] =
  461. {
  462. 2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu,
  463. 59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu,
  464. 499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu,
  465. 3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu,
  466. 20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu,
  467. 102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu,
  468. 411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu,
  469. 1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu,
  470. 6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu,
  471. 26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu,
  472. 83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu,
  473. 265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu,
  474. 842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu,
  475. 2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu,
  476. 8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu,
  477. 21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu,
  478. 53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu,
  479. 135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu,
  480. 342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu,
  481. 863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu,
  482. 2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu,
  483. 5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu,
  484. 13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu,
  485. 34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu,
  486. 87686378464759llu, 110477914016779llu, 139193449418173llu,
  487. 175372756929481llu, 220955828033581llu, 278386898836457llu,
  488. 350745513859007llu, 441911656067171llu, 556773797672909llu,
  489. 701491027718027llu, 883823312134381llu, 1113547595345903llu,
  490. 1402982055436147llu, 1767646624268779llu, 2227095190691797llu,
  491. 2805964110872297llu, 3535293248537579llu, 4454190381383713llu,
  492. 5611928221744609llu, 7070586497075177llu, 8908380762767489llu,
  493. 11223856443489329llu, 14141172994150357llu, 17816761525534927llu,
  494. 22447712886978529llu, 28282345988300791llu, 35633523051069991llu,
  495. 44895425773957261llu, 56564691976601587llu, 71267046102139967llu,
  496. 89790851547914507llu, 113129383953203213llu, 142534092204280003llu,
  497. 179581703095829107llu, 226258767906406483llu, 285068184408560057llu,
  498. 359163406191658253llu, 452517535812813007llu, 570136368817120201llu,
  499. 718326812383316683llu, 905035071625626043llu, 1140272737634240411llu,
  500. 1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu,
  501. 2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu,
  502. 5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu,
  503. 11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu
  504. };
  505. const size_t * found = std::lower_bound(std::begin(prime_list), std::end(prime_list) - 1, size);
  506. size = *found;
  507. return static_cast<uint8_t>(1 + found - prime_list);
  508. }
  509. void commit(uint8_t new_prime_index)
  510. {
  511. prime_index = new_prime_index;
  512. }
  513. void reset()
  514. {
  515. prime_index = 0;
  516. }
  518. private:
  519. uint8_t prime_index = 0;
  520. };
  521. int main(int argc, char **argv, char **environ)
  522. {
  523. prime_number_hash_policy h;
  524. h.commit((uint8_t)argc);
  525. printf("%zu\n", h.index_for_hash((size_t)argv, (size_t)environ));
  526. printf("%zu\n", h.index_for_hash_2((size_t)argv, (size_t)environ));
  527. return 0;
  528. }
  529.  
Powered by spacepaste. Paste removal.