1 | //Copyright (c) 2011-2012 Mail.RU |
2 | //Copyright (c) 2011-2012 Maksim Kalinchenko |
3 | //Copyright (c) 2012 Sokolov Yura aka funny-falcon |
4 | // |
5 | //MIT License |
6 | // |
7 | //Permission is hereby granted, free of charge, to any person obtaining |
8 | //a copy of this software and associated documentation files (the |
9 | //"Software"), to deal in the Software without restriction, including |
10 | //without limitation the rights to use, copy, modify, merge, publish, |
11 | //distribute, sublicense, and/or sell copies of the Software, and to |
12 | //permit persons to whom the Software is furnished to do so, subject to |
13 | //the following conditions: |
14 | // |
15 | //The above copyright notice and this permission notice shall be |
16 | //included in all copies or substantial portions of the Software. |
17 | // |
18 | //THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
19 | //EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
20 | //MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
21 | //NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
22 | //LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
23 | //OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
24 | //WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
25 | |
26 | #include <stdexcept> |
27 | |
28 | |
29 | #define L 0xFFFFFFFF |
30 | |
31 | static unsigned int L27_38[] = {L / 27, L / 28, L / 29, L / 30, L / 31, L / 32, |
32 | L / 33, L / 34, L / 35, L / 36, L / 37, L / 38, |
33 | L / 39, L / 40, L / 41, L / 42, L / 43, L / 44, |
34 | L / 45, L / 46, L / 47, L / 48, L / 49, L / 50, |
35 | L / 51, L / 52, L / 53, L / 54, L / 55, L / 56, |
36 | L / 57, L / 58, L / 59, L / 60, L / 61, L / 62 |
37 | }; |
38 | static unsigned int LL27_38[] = {L/(26*27), L/(27*28), L/(28*29), L/(29*30), L/(30*31), L/(31*32), |
39 | L/(32*33), L/(33*34), L/(34*35), L/(35*36), L/(36*37), L/(37*38), |
40 | L/(38*39), L/(39*40), L/(40*41), L/(41*42), L/(42*43), L/(43*44), |
41 | L/(44*45), L/(45*46), L/(46*47), L/(47*48), L/(48*49), L/(49*50), |
42 | L/(50*51), L/(51*52), L/(52*53), L/(53*54), L/(54*55), L/(55*56), |
43 | L/(56*57), L/(57*58), L/(58*59), L/(59*60), L/(60*61), L/(61*62) |
44 | }; |
45 | |
46 | unsigned int sumburConsistentHash(unsigned int hashed_int, unsigned int capacity) |
47 | { |
48 | unsigned int h = hashed_int; |
49 | unsigned int capa = capacity; |
50 | unsigned int part, n, i, c; |
51 | |
52 | if (capa == 0) |
53 | throw std::runtime_error("Sumbur is not applicable to empty cluster" ); |
54 | |
55 | part = L / capa; |
56 | |
57 | if (L - h < part) return 0; |
58 | |
59 | n = 1; |
60 | |
61 | do { |
62 | if (h >= L / 2) h -= L / 2; |
63 | else { |
64 | n = 2; |
65 | if (L / 2 - h < part) return 1; |
66 | } |
67 | if (capa == 2) return 1; |
68 | |
69 | #define curslice(i) (L / (i * (i - 1))) |
70 | #define unroll(i) \ |
71 | if (curslice(i) <= h) h -= curslice(i); \ |
72 | else { \ |
73 | h += curslice(i) * (i - n - 1); \ |
74 | n = i; \ |
75 | if (L / i - h < part) return n-1; \ |
76 | } \ |
77 | if (capa == i) return (n-1) |
78 | |
79 | unroll(3); unroll(4); unroll(5); |
80 | unroll(6); unroll(7); unroll(8); |
81 | unroll(9); unroll(10); unroll(11); |
82 | unroll(12); unroll(13); unroll(14); |
83 | unroll(15); unroll(16); unroll(17); |
84 | unroll(18); unroll(19); unroll(20); |
85 | unroll(21); unroll(22); unroll(23); |
86 | unroll(24); unroll(25); unroll(26); |
87 | |
88 | for (i = 27; i <= capa && i <= 62; i++) { |
89 | c = LL27_38[i-27]; |
90 | if (c <= h) { |
91 | h -= c; |
92 | } |
93 | else { |
94 | h += c * (i - n - 1); |
95 | n = i; |
96 | if (L27_38[i-27] - h < part) return n-1; |
97 | } |
98 | } |
99 | |
100 | for(i = 63; i <= capa; i++) { |
101 | c = L / (i * (i - 1)); |
102 | if (c <= h) { |
103 | h -= c; |
104 | } |
105 | else { |
106 | h += c * (i - n - 1); |
107 | n = i; |
108 | if (L / i - h < part) return n - 1; |
109 | } |
110 | } |
111 | } while(0); |
112 | return n - 1; |
113 | } |
114 | |