osom_lib_hash/hash_set/
quadratic_index_sequence.rs

1use core::num::NonZero;
2
3/// A quadratic index sequence for probing.
4///
5/// Basically it is a way of generating a pseudo-random permutation of
6/// `0..data_len` sequence. In an efficient way.
7#[derive(Debug)]
8#[must_use]
9pub struct QuadraticIndexSequence {
10    hash: u64,
11    i: u32,
12    data_len: u32,
13    modulus: u32,
14    calls_count: u32,
15}
16
17impl QuadraticIndexSequence {
18    #[inline(always)]
19    pub const fn new(hash: u64, data_len: NonZero<u32>) -> Self {
20        let data_len = data_len.get();
21        debug_assert!(data_len < i32::MAX as u32);
22        let modulus = data_len.next_power_of_two();
23        Self {
24            hash,
25            i: 0,
26            data_len: data_len,
27            modulus,
28            calls_count: 0,
29        }
30    }
31
32    /// Returns the next index in the sequence.
33    ///
34    /// # Notes
35    ///
36    /// This generates a permutation of `0..data_len` sequence. It can be called
37    /// at most `data_len` times, after which it will return `None`.
38    #[inline(always)]
39    pub const fn next(&mut self) -> Option<u32> {
40        if self.calls_count >= self.data_len {
41            return None;
42        }
43        self.calls_count += 1;
44
45        let modulus = self.modulus;
46        let mut i = self.i;
47        let data_len = self.data_len;
48        let hash = self.hash;
49
50        loop {
51            // Quadratic probing is bijective over sets of size `2^n`.
52            // Therefore, by taking `modulus` to be the next power of two
53            // we get such bijection. However some of the values may go outside
54            // of `0..data_len` range. We discard them, and try to pick a new index
55            // again. In worst theoretical case this loop spins for `data_len/2`
56            // times. But in practice it rarely loops more than twice.
57            let new_index = Self::calculate_index(hash, i, modulus);
58            i += 1;
59            if new_index < data_len {
60                self.i = i;
61                return Some(new_index);
62            }
63        }
64    }
65
66    #[allow(clippy::cast_possible_truncation, clippy::manual_midpoint)]
67    #[inline(always)]
68    const fn calculate_index(hash: u64, i: u32, modulus: u32) -> u32 {
69        // Basically we calculate `(hash + (i^2 + i) / 2) % modulus`.
70        let i = i as u64;
71
72        // `idx` calculation cannot overflow, because `i` is at most `modulus`
73        // which is at most `i32::MAX`(because `data_len < i32::MAX`).
74        // Meaning `i` is at most `2^31` and thus `i*i+i` is less than `2^63`.
75        let idx = (i * i + i) / 2;
76        let modulus = modulus as u64;
77        let result = (hash + idx) % modulus;
78        result as u32
79    }
80}
81
82impl Iterator for QuadraticIndexSequence {
83    type Item = u32;
84
85    #[inline(always)]
86    fn next(&mut self) -> Option<Self::Item> {
87        self.next()
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    use rstest::rstest;
94
95    use osom_lib_arrays::InlineDynamicArray;
96
97    use super::*;
98
99    #[rstest]
100    #[case(1, 1, &[0])]
101    #[case(0, 3, &[ 0, 1, 2])]
102    #[case(1, 3, &[ 1, 2, 0])]
103    #[case(2, 3, &[ 2, 1, 0])]
104    #[case(730, 3, &[ 2, 1, 0])]
105    #[case(3, 3, &[ 0, 2, 1])]
106    #[case(1, 10, &[1, 2, 4, 7, 0, 6, 5, 8, 3, 9])]
107    #[case(15, 10, &[0, 2, 5, 9, 4, 3, 6, 1, 8, 7])]
108    #[case(1, 11, &[1, 2, 4, 7, 0, 6, 5, 8, 3, 10, 9])]
109    #[case(327, 23, &[7, 8, 10, 13, 17, 22, 3, 11, 20, 9, 21, 2, 16, 15, 0, 18, 5, 14, 4, 19, 12, 6, 1])]
110    #[case(0, 23, &[0, 1, 3, 6, 10, 15, 21, 4, 13, 2, 14, 9, 8, 11, 18, 7, 20, 12, 5, 22, 19, 17, 16])]
111    #[case(1234, 1234, &[6, 47, 89, 132, 176, 221, 267, 314, 362, 411, 461, 512, 564, 617, 671, 726, 782, 839, 897, 956, 1016, 1077, 1139, 1202, 64, 141, 219, 298, 378, 459, 541, 624, 708, 793, 879, 966, 1054, 1143, 1233, 40, 140, 241, 343, 446, 550, 655, 761, 868, 976, 1085, 1195, 63, 182, 302, 423, 545, 668, 792, 917, 1043, 1170, 39, 174, 310, 447, 585, 724, 864, 1005, 1147, 121, 271, 422, 574, 727, 881, 1036, 1192, 101, 264, 428, 593, 759, 926, 1094, 75, 250, 426, 603, 781, 960, 1140, 7, 193, 380, 568, 757, 947, 1138, 60, 257, 455, 654, 854, 1055, 27, 234, 442, 651, 861, 1072, 94, 311, 529, 748, 968, 1189, 35, 261, 488, 716, 945, 1175, 57, 292, 528, 765, 1003, 160, 404, 649, 895, 1142, 92, 344, 597, 851, 1106, 88, 348, 609, 871, 1134, 148, 416, 685, 955, 1226, 272, 548, 825, 1103, 177, 460, 744, 1029, 131, 421, 712, 1004, 134, 431, 729, 1028, 186, 490, 795, 1101, 287, 598, 910, 1223, 120, 437, 755, 1074, 312, 636, 961, 223, 553, 884, 1216, 170, 506, 843, 1181, 153, 495, 838, 1182, 172, 520, 869, 1219, 227, 581, 936, 318, 678, 1039, 80, 445, 811, 1178, 237, 608, 980, 54, 430, 807, 1185, 277, 659, 1042, 149, 536, 924, 46, 438, 831, 1225, 365, 763, 1162, 317, 720, 1124, 294, 702, 1111, 296, 709, 1123, 323, 741, 1160, 375, 798, 1222, 25, 452, 880, 122, 554, 987, 244, 681, 1119, 391, 833, 117, 563, 1010, 309, 760, 1212, 71, 526, 982, 308, 768, 1229, 106, 570, 1035, 388, 857, 222, 695, 1169, 72, 549, 1027, 419, 901, 305, 791, 207, 697, 1188, 125, 619, 1114, 59, 557, 1056, 9, 511, 1014, 481, 988, 467, 978, 469, 984, 487, 1006, 521, 1044, 45, 571, 1098, 107, 637, 1168, 185, 719, 279, 817, 389, 931, 515, 1061, 108, 657, 1207, 262, 815, 432, 989, 58, 618, 1179, 256, 820, 470, 1038, 129, 700, 371, 946, 51, 629, 1208, 321, 903, 22, 607, 1193, 320, 909, 42, 634, 1227, 368, 964, 111, 710, 465, 1068, 229, 835, 2, 611, 1221, 396, 1009, 190, 806, 612, 1232, 427, 1050, 251, 877, 84, 713, 558, 1191, 412, 1048, 275, 914, 147, 789, 28, 673, 566, 1215, 468, 1120, 379, 1034, 299, 957, 228, 889, 166, 830, 113, 780, 69, 739, 34, 707, 8, 684, 670, 665, 669, 682, 13, 704, 41, 735, 78, 775, 124, 824, 179, 882, 243, 949, 316, 1025, 398, 1110, 489, 1204, 589, 698, 93, 816, 217, 943, 350, 1079, 492, 1224, 643, 66, 803, 232, 972, 407, 1150, 591, 36, 784, 235, 986, 443, 1197, 660, 127, 886, 359, 1121, 600, 83, 850, 339, 1109, 604, 103, 878, 383, 1161, 672, 187, 970, 491, 16, 804, 335, 1126, 663, 204, 1000, 547, 98, 899, 456, 17, 823, 390, 1199, 772, 349, 1163, 746, 333, 1152, 745, 342, 1166, 769, 376, 1205, 818, 435, 56, 892, 519, 150, 991, 628, 269, 1115, 762, 413, 68, 921, 582, 247, 1105, 776, 451, 130, 995, 680, 369, 62, 934, 633, 336, 1213, 43, 922, 635, 352, 73, 959, 686, 417, 152, 1045, 786, 531, 280, 1180, 33, 935, 694, 457, 224, 1133, 906, 683, 464, 249, 1167, 38, 958, 753, 552, 355, 162, 1091, 904, 721, 542, 367, 196, 1136, 29, 971, 810, 653, 500, 351, 206, 1159, 65, 1020, 885, 754, 627, 504, 385, 270, 159, 1129, 52, 1024, 923, 826, 733, 644, 559, 478, 401, 328, 259, 194, 1187, 133, 1128, 76, 1073, 23, 1022, 975, 932, 893, 858, 827, 800, 777, 758, 743, 732, 725, 722, 723, 728, 737, 750, 767, 788, 813, 842, 875, 912, 953, 998, 1047, 49, 1100, 104, 1157, 163, 1218, 226, 293, 364, 439, 518, 601, 688, 779, 874, 973, 0, 1076, 105, 1183, 214, 327, 444, 565, 690, 819, 952, 1089, 135, 1230, 278, 425, 576, 731, 890, 1053, 112, 1220, 281, 454, 631, 812, 997, 67, 1186, 258, 453, 652, 855, 1062, 143, 356, 573, 794, 1019, 109, 340, 575, 814, 1057, 156, 405, 658, 915, 21, 1176, 284, 551, 822, 1097, 212, 493, 778, 1067, 189, 484, 783, 1086, 215, 524, 837, 1154, 290, 613, 940, 81, 414, 751, 1092, 240, 587, 938, 91, 448, 809, 1174, 334, 705, 1080, 245, 626, 1011, 181, 572, 967, 142, 543, 948, 128, 539, 954, 139, 560, 985, 175, 606, 1041, 236, 677, 1122, 322, 773, 1228, 433, 894, 102, 569, 1040, 253, 730, 1211, 429, 916, 137, 630, 1127, 353, 856, 85, 594, 1107, 341, 860, 97, 622, 1151, 393, 928, 173, 714, 509, 1060, 313, 870, 126, 689, 517, 1090, 354, 933, 200, 785, 55, 646, 516, 1117, 395, 1002, 283, 896, 180, 799, 86, 711, 1, 632, 562, 1203, 501, 1148, 449, 1102, 406, 1065, 372, 1037, 347, 1018, 331, 1008, 324, 1007, 326, 1015, 337, 1032, 357, 1058, 386, 1093, 424, 1137, 471, 1190, 527, 592, 666, 10, 749, 96, 841, 191, 942, 295, 1052, 408, 1171, 530, 661, 24, 801, 167, 950, 319, 1108, 480, 650, 26, 829, 208, 1017, 399, 1214, 599, 808, 197, 1026, 418, 648, 44, 887, 286, 1135, 537, 797, 203, 1066, 475, 756, 169, 1046, 462, 764, 184, 1075, 498, 821, 248, 1153, 583, 14, 927, 361, 717, 155, 1082, 523, 900, 345, 734, 183, 1132, 584, 37, 994, 450, 872, 332, 766, 230, 1209, 676, 144, 1131, 602, 74, 1069, 544, 20, 1023, 502, 993, 476, 979, 466, 981, 472, 999, 494, 1033, 532, 32, 1083, 586, 90, 1149, 656, 164, 1231, 742, 254, 844, 360, 962, 482, 3, 1096, 620, 145, 774, 303, 944, 477, 11, 1130, 667, 205, 873, 415, 1095, 641, 188, 883, 434, 1141, 696, 252, 974, 534, 95, 832, 397, 1146, 715, 285, 1049, 623, 198, 977, 556, 136, 930, 514, 99, 908, 497, 87, 911, 505, 100, 939, 538, 138, 992, 596, 201, 1070, 679, 289, 1173, 787, 402, 18, 920, 540, 161, 1078, 703, 329, 891, 522, 154, 1104, 740, 377, 15, 983, 625, 268, 898, 546, 195, 1196, 849, 503, 158, 1177, 836, 496, 157, 1194, 859, 525, 192, 918, 590, 263, 1013, 691, 370, 50, 1144, 828, 513, 199, 1001, 692, 384, 77, 1210, 907, 605, 304, 4, 1158, 862, 567, 273, 1155, 866, 578, 291, 5, 1201, 919, 638, 358, 79, 1021, 747, 474, 202, 1172, 905, 639, 374, 110, 1112, 853, 595, 338, 82, 1116, 865, 615, 366, 118, 1184, 941, 699, 458, 218, 1081, 847, 614, 382, 151, 1059, 834, 610, 387, 165, 1118, 902, 687, 473, 260, 48, 1051, 845, 640, 436, 233, 31, 1084, 888, 693, 499, 306, 114, 1217, 1031, 846, 662, 479, 297, 116, 1099, 925, 752, 580, 409, 239, 70, 1125, 963, 802, 642, 483, 325, 168, 12, 1145, 996, 848, 701, 555, 410, 266, 123, 1198, 1063, 929, 796, 664, 533, 403, 274, 146, 19, 1206, 1087, 969, 852, 736, 621, 507, 394, 282, 171, 61, 1164, 1064, 965, 867, 770, 674, 579, 485, 392, 300, 209, 119, 30, 1165, 1088, 1012, 937, 863, 790, 718, 647, 577, 508, 440, 373, 307, 242, 178, 115, 53, 1200, 1156, 1113, 1071, 1030, 990, 951, 913, 876, 840, 805, 771, 738, 706, 675, 645, 616, 588, 561, 535, 510, 486, 463, 441, 420, 400, 381, 363, 346, 330, 315, 301, 288, 276, 265, 255, 246, 238, 231, 225, 220, 216, 213, 211, 210])]
112    fn test_quadratic_index_sequence(#[case] hash: u64, #[case] data_len: u32, #[case] expected: &[u32]) {
113        let mut sequence = QuadraticIndexSequence::new(hash, NonZero::new(data_len).unwrap());
114        let mut array = InlineDynamicArray::<100, u32>::new();
115
116        for _ in 0..data_len {
117            array.push(sequence.next().unwrap()).unwrap();
118        }
119        // Check that values are expected.
120        assert_eq!(array.as_slice(), expected);
121        assert_eq!(array.len().value() as u32, data_len);
122
123        // We didn't actually verified those const arrays,
124        // so just in case verify that these are correct, i.e.
125        // that the smallest number is `0`, highets `data_len - 1`,
126        // and that there are no duplicates.
127        let slice_mut = array.as_slice_mut();
128        slice_mut.sort();
129        let len = slice_mut.len();
130        for i in 0..(len - 1) {
131            let left = slice_mut[i] as i64;
132            let right = slice_mut[i + 1] as i64;
133            assert_eq!(right - left, 1);
134        }
135        assert_eq!(slice_mut[0], 0);
136        assert_eq!(slice_mut[len - 1], data_len - 1);
137
138        // Lets verify iteration as well.
139        let sequence = QuadraticIndexSequence::new(hash, NonZero::new(data_len).unwrap());
140
141        for (i, value) in sequence.enumerate() {
142            assert_eq!(value, expected[i]);
143        }
144    }
145}
osom_lib_hash/hash_set/quadratic_index_sequence.rs

osom_lib_hash/hash_set/
quadratic_index_sequence.rs
