1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376
//! 切片分类
//!
//! 该模块包含基于 Orson Peters 的模式失败快速排序的排序算法,发布于: <https://github.com/orlp/pdqsort>
//!
//!
//! 不稳定排序与核心兼容,因为它不分配内存,这与我们的稳定排序实现不同。
//!
//! 此外还包含了 `slice::sort` 基于 TimSort 使用的稳定排序的核心逻辑。
//!
//!
use crate::cmp;
use crate::mem::{self, MaybeUninit, SizedTypeProperties};
use crate::ptr;
// 丢弃时,从 `src` 复制到 `dest`。
struct InsertionHole<T> {
src: *const T,
dest: *mut T,
}
impl<T> Drop for InsertionHole<T> {
fn drop(&mut self) {
// SAFETY: 这是一个帮助程序类。请参考其用法以确保正确性。
// 即,必须确保 `src` 和 `dst` 没有按照 `ptr::copy_nonoverlapping` 的要求重叠并且都对写入有效。
//
unsafe {
ptr::copy_nonoverlapping(self.src, self.dest, 1);
}
}
}
/// 将 `v[v.len() - 1]` 插入到预排序序列 `v[..v.len() - 1]` 中,以便整个 `v[..]` 都已排序。
///
unsafe fn insert_tail<T, F>(v: &mut [T], is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
debug_assert!(v.len() >= 2);
let arr_ptr = v.as_mut_ptr();
let i = v.len() - 1;
// SAFETY: 调用者必须确保 v 至少为 len 2.
unsafe {
// 请参见 insert_head,其中讨论了为什么这种方法是有益的。
let i_ptr = arr_ptr.add(i);
// 我们在这里使用 i_ptr 很重要。
// 如果此检查是肯定的并且我们继续,我们要确保 is_less 没有看到该值的其他副本。
// 否则我们将不得不将其复制回去。
if is_less(&*i_ptr, &*i_ptr.sub(1)) {
// 重要的是,我们从现在开始使用 tmp 进行比较。
// 因为它是将被复制回的值。
// 从理论上讲,如果我们复制回错误的值,我们可能会产生分歧。
let tmp = mem::ManuallyDrop::new(ptr::read(i_ptr));
// `hole` 始终跟踪插入过程的中间状态,这有两个目的:
// 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
// 2. 最后将 `v` 中剩余的 hole 填充。
//
// Panic 安全:
//
// 如果在此过程中的任何时候 `is_less` panics,`hole` 都会被丢弃,并用 `tmp` 填充 `v` 中的 hole,从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
//
//
//
let mut hole = InsertionHole { src: &*tmp, dest: i_ptr.sub(1) };
ptr::copy_nonoverlapping(hole.dest, i_ptr, 1);
// SAFETY: 我们知道我至少 1.
for j in (0..(i - 1)).rev() {
let j_ptr = arr_ptr.add(j);
if !is_less(&*tmp, &*j_ptr) {
break;
}
ptr::copy_nonoverlapping(j_ptr, hole.dest, 1);
hole.dest = j_ptr;
}
// `hole` 被丢弃,因此将 `tmp` 复制到 `v` 中剩余的 hole 中。
}
}
}
/// 将 `v[0]` 插入到预排序序列 `v[1..]` 中,以便整个 `v[..]` 都被排序。
///
/// 这是插入排序的必不可少的子例程。
unsafe fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
debug_assert!(v.len() >= 2);
// SAFETY: 调用者必须确保 v 至少为 len 2.
unsafe {
if is_less(v.get_unchecked(1), v.get_unchecked(0)) {
let arr_ptr = v.as_mut_ptr();
// 这里有三种实现插入的方法:
//
// 1. 交换相邻的元素,直到第一个到达其最终目的地。
// 但是,这样一来,我们就可以复制不必要的数据。
// 如果元素是大型结构 (复制成本很高),则此方法的速度会很慢。
//
// 2. 迭代直到找到第一个元素的正确位置。
// 然后,移动后继的元素为其腾出空间,最后将其放入剩余的 hole 中。
// 这是一个好方法。
//
// 3. 将第一个元素复制到一个临时变量中。迭代直到找到正确的位置。
// 在继续操作时,将每个遍历的元素复制到它前面的插槽中。
// 最后,将数据从临时变量复制到剩余的 hole 中。
// 这个方法很好。
// 基准测试显示出比第二种方法更好的性能。
//
// 所有方法均进行了基准测试,第 3 种方法显示最佳结果。因此,我们选择了那个。
let tmp = mem::ManuallyDrop::new(ptr::read(arr_ptr));
// `hole` 始终跟踪插入过程的中间状态,这有两个目的:
// 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
// 2. 最后将 `v` 中剩余的 hole 填充。
//
// Panic 安全:
//
// 如果在此过程中的任何时候 `is_less` panics,`hole` 都会被丢弃,并用 `tmp` 填充 `v` 中的 hole,从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
//
//
//
let mut hole = InsertionHole { src: &*tmp, dest: arr_ptr.add(1) };
ptr::copy_nonoverlapping(arr_ptr.add(1), arr_ptr.add(0), 1);
for i in 2..v.len() {
if !is_less(&v.get_unchecked(i), &*tmp) {
break;
}
ptr::copy_nonoverlapping(arr_ptr.add(i), arr_ptr.add(i - 1), 1);
hole.dest = arr_ptr.add(i);
}
// `hole` 被丢弃,因此将 `tmp` 复制到 `v` 中剩余的 hole 中。
}
}
}
/// 假设 `v[..offset]` 已经排序,则对 `v` 进行排序。
///
/// 切勿内联此函数以避免代码膨胀。它仍然可以很好地优化并且几乎没有性能影响。
/// 在某些情况下甚至可以提高性能。
#[inline(never)]
pub(super) fn insertion_sort_shift_left<T, F>(v: &mut [T], offset: usize, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
// 此处使用断言可提高性能。
assert!(offset != 0 && offset <= len);
// 将未排序区域 v [i..] 的每个元素尽可能向左移动以使 v 排序。
for i in offset..len {
// SAFETY: 我们测试了 `offset` 必须至少为 1,所以只有在 len >= 时才进入这个循环 2.
// 范围是排他的,我们知道 `i` 必须至少为 1,所以这个切片至少有 > least 2.
//
unsafe {
insert_tail(&mut v[..=i], is_less);
}
}
}
/// 假设 `v[offset..]` 已经排序,则对 `v` 进行排序。
///
/// 切勿内联此函数以避免代码膨胀。它仍然可以很好地优化并且几乎没有性能影响。
/// 在某些情况下甚至可以提高性能。
#[inline(never)]
fn insertion_sort_shift_right<T, F>(v: &mut [T], offset: usize, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
// 此处使用断言可提高性能。
assert!(offset != 0 && offset <= len && len >= 2);
// 将未排序区域 v [..i] 的每个元素尽可能向左移动以使 v 排序。
for i in (0..offset).rev() {
// SAFETY: 我们测试过 `offset` 必须至少为 1,因此只有在 len >= 2.We 确保切片长度始终至少为 2 时才进入此循环。
// 我们知道 start_found 至少会比 end 少一位,并且范围是独占的。
// 这给了我们我总是 <= (end-2)。
//
unsafe {
insert_head(&mut v[i..len], is_less);
}
}
}
/// 通过移动几个乱序的元素来对切片进行部分排序。
///
/// 如果切片末尾排序,则返回 `true`。该函数是 *O*(*n*) 最坏的情况。
#[cold]
fn partial_insertion_sort<T, F>(v: &mut [T], is_less: &mut F) -> bool
where
F: FnMut(&T, &T) -> bool,
{
// 将移位的相邻无序对的最大数量。
const MAX_STEPS: usize = 5;
// 如果切片短于此,请勿移动任何元素。
const SHORTEST_SHIFTING: usize = 50;
let len = v.len();
let mut i = 1;
for _ in 0..MAX_STEPS {
// SAFETY: 我们已经用 `i < len` 明确地进行了边界检查。
// 我们所有的后续索引仅在 `0 <= index < len` 范围内
unsafe {
// 查找下一对相邻的乱序元素。
while i < len && !is_less(v.get_unchecked(i), v.get_unchecked(i - 1)) {
i += 1;
}
}
// 我们完成了吗?
if i == len {
return true;
}
// 不要在短数组上移动元素,这会降低性能。
if len < SHORTEST_SHIFTING {
return false;
}
// 交换找到的一对元素。这使它们处于正确的顺序。
v.swap(i - 1, i);
if i >= 2 {
// 将较小的元素向左移动。
insertion_sort_shift_left(&mut v[..i], i - 1, is_less);
// 将较大的元素向右移动。
insertion_sort_shift_right(&mut v[..i], 1, is_less);
}
}
// 未能在有限的步骤中对切片进行排序。
false
}
/// 使用堆排序对 `v` 进行排序,这保证了 *O*(*n*\*log(* n*)) 最坏的情况。
#[cold]
#[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")]
pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
where
F: FnMut(&T, &T) -> bool,
{
// 该二进制堆遵守不变量 `parent >= child`。
let mut sift_down = |v: &mut [T], mut node| {
loop {
// `node` 的子节点。
let mut child = 2 * node + 1;
if child >= v.len() {
break;
}
// 选择更大的子节点。
if child + 1 < v.len() {
// 我们需要一个分支来确保索引不会越界,但它是高度可预测的。
//
// 然而,比较最好是无分支的,特别是对于,原语。
child += is_less(&v[child], &v[child + 1]) as usize;
}
// 如果不变量位于 `node`,则停止。
if !is_less(&v[node], &v[child]) {
break;
}
// 与更大的子节点交换 `node`,向下移动一步,然后继续筛分。
v.swap(node, child);
node = child;
}
};
// 在线性时间内构建堆。
for i in (0..v.len() / 2).rev() {
sift_down(v, i);
}
// 从堆中弹出最大元素。
for i in (1..v.len()).rev() {
v.swap(0, i);
sift_down(&mut v[..i], 0);
}
}
/// 将 `v` 划分为小于 `pivot` 的元素,然后划分为大于或等于 `pivot` 的元素。
///
///
/// 返回小于 `pivot` 的元素数。
///
/// 为了最小化分支操作的成本,逐块执行分区。
/// [块快速排序][pdf] 论文中提出了这个想法。
///
/// [pdf]: https://drops.dagstuhl.de/opus/volltexte/2016/6389/pdf/LIPIcs-ESA-2016-38.pdf
fn partition_in_blocks<T, F>(v: &mut [T], pivot: &T, is_less: &mut F) -> usize
where
F: FnMut(&T, &T) -> bool,
{
// 典型块中的元素数。
const BLOCK: usize = 128;
// 分区算法重复以下步骤,直到完成:
//
// 1. 从左侧跟踪一个块,以识别大于或等于枢轴的元素。
// 2. 从右侧跟踪一个块,以识别小于枢轴的元素。
// 3. 在左侧和右侧之间交换已标识的元素。
//
// 我们为元素块保留以下变量:
//
// 1. `block` - 块中的元素数。
// 2. `start` - 指向 `offsets` 数组的起始指针。
// 3. `end` - 指向 `offsets` 数组的结束指针。
// 4. `offsets` - 块内乱序元素的索引。
// 左侧的当前块 (从 `l` 到 `l.add(block_l)`)。
let mut l = v.as_mut_ptr();
let mut block_l = BLOCK;
let mut start_l = ptr::null_mut();
let mut end_l = ptr::null_mut();
let mut offsets_l = [MaybeUninit::<u8>::uninit(); BLOCK];
// 右侧的当前块 (从 `r.sub(block_r)` 到 `r`)。
// SAFETY: .add() 的文档特别提到 `vec.as_ptr().add(vec.len())` 总是安全的
let mut r = unsafe { l.add(v.len()) };
let mut block_r = BLOCK;
let mut start_r = ptr::null_mut();
let mut end_r = ptr::null_mut();
let mut offsets_r = [MaybeUninit::<u8>::uninit(); BLOCK];
// FIXME: 当我们得到 VLA 时,请尝试创建一个长度为 `min(v.len(), 2 * BLOCK)` 的数组,而不是两个长度为 `BLOCK` 的固定大小的数组。
// VLA 可能会提高缓存效率。
// 返回指针 `l` (inclusive) 和 `r` (exclusive) 之间的元素数。
fn width<T>(l: *mut T, r: *mut T) -> usize {
assert!(mem::size_of::<T>() > 0);
// FIXME: 这应该可能使用 `offset_from`,但需要进行更多调查 (包括在 miri 中运行测试)。
//
(r.addr() - l.addr()) / mem::size_of::<T>()
}
loop {
// 当 `l` 和 `r` 非常接近时,我们将逐块进行分区。
// 然后,我们进行一些修补工作,以便在其余元素之间进行划分。
let is_done = width(l, r) <= 2 * BLOCK;
if is_done {
// 剩余元素数 (仍未与枢轴进行比较)。
let mut rem = width(l, r);
if start_l < end_l || start_r < end_r {
rem -= BLOCK;
}
// 调整块大小,以使左右块不重叠,但要完全对齐以覆盖整个剩余间隙。
//
if start_l < end_l {
block_r = rem;
} else if start_r < end_r {
block_l = rem;
} else {
// 在上次迭代期间要在两个块上切换的元素数量相同,因此任何一个块上都没有剩余的元素。
// 用大致相同大小的块覆盖剩余的项。
//
block_l = rem / 2;
block_r = rem - block_l;
}
debug_assert!(block_l <= BLOCK && block_r <= BLOCK);
debug_assert!(width(l, r) == block_l + block_r);
}
if start_l == end_l {
// 从左侧跟踪 `block_l` 元素。
start_l = MaybeUninit::slice_as_mut_ptr(&mut offsets_l);
end_l = start_l;
let mut elem = l;
for i in 0..block_l {
// SAFETY: 以下不安全操作涉及 `offset` 的使用。
// 根据函数所需的条件,我们满足它们,因为:
// 1. `offsets_l` 是栈分配的,因此被视为单独分配的对象。
// 2. 函数 `is_less` 返回 `bool`。
// 转换 `bool` 不会使 `isize` 溢出。
// 3. 我们保证 `block_l` 将是 `<= BLOCK`。
// 另外,`end_l` 最初设置为在栈上声明的 `offsets_` 的开始指针。
// 因此,我们知道即使在最坏的情况下 (`is_less` 的所有调用都返回 false),我们最多只能有 1 个字节通过结尾。
// 这里的另一个不安全操作是解引用 `elem`。
// 但是,`elem` 最初是指向切片的 begin 指针,始终有效。
unsafe {
// 无分支比较。
*end_l = i as u8;
end_l = end_l.add(!is_less(&*elem, pivot) as usize);
elem = elem.add(1);
}
}
}
if start_r == end_r {
// 从右侧跟踪 `block_r` 元素。
start_r = MaybeUninit::slice_as_mut_ptr(&mut offsets_r);
end_r = start_r;
let mut elem = r;
for i in 0..block_r {
// SAFETY: 以下不安全操作涉及 `offset` 的使用。
// 根据函数所需的条件,我们满足它们,因为:
// 1. `offsets_r` 是栈分配的,因此被视为单独分配的对象。
// 2. 函数 `is_less` 返回 `bool`。
// 转换 `bool` 不会使 `isize` 溢出。
// 3. 我们保证 `block_r` 将是 `<= BLOCK`。
// 另外,`end_r` 最初设置为在栈上声明的 `offsets_` 的开始指针。
// 因此,我们知道即使在最坏的情况下 (`is_less` 的所有调用都返回 true),我们最多只能将 1 个字节传递到末尾。
// 这里的另一个不安全操作是解引用 `elem`。
// 但是,`elem` 最初是末尾的 `1 *sizeof(T)`,在访问它之前,我们先将其递减 `1* sizeof(T)`。
// 另外,断言 `block_r` 小于 `BLOCK`,因此 `elem` 至多将指向切片的开头。
unsafe {
// 无分支比较。
elem = elem.sub(1);
*end_r = i as u8;
end_r = end_r.add(is_less(&*elem, pivot) as usize);
}
}
}
// 要在左侧和右侧之间交换的乱序元素的数量。
let count = cmp::min(width(start_l, end_l), width(start_r, end_r));
if count > 0 {
macro_rules! left {
() => {
l.add(usize::from(*start_l))
};
}
macro_rules! right {
() => {
r.sub(usize::from(*start_r) + 1)
};
}
// 与一次交换一对相比,执行循环置换更为有效。
// 这并不严格等同于交换,但是使用较少的内存操作即可产生类似的结果。
//
// SAFETY: `ptr::read` 的使用是有效的,因为在 `offsets_l` 和 `offsets_r` 中至少有一个元素,所以 `left!` 是一个有效的读取指针。
//
// `left!` 的使用涉及在 `l` 上调用 `offset`,它指向 `v` 的开头。`start_l` 指向的所有偏移量最多为 `block_l`,因此这些 `offset` 调用是安全的,因为所有读取都在块内。相同的参数也适用于 `right!` 的用法。
//
// 对 `start_l.offset` 的调用是有效的,因为它们最多有 `count-1` 个,加上不安全块末尾的最后一个,其中 `count` 是 `offsets_l` 和 `offsets_r` 中收集的最小偏移量,因此不存在不存在的风险足够的元素。
// 同样的推理适用于对 `start_r.offset` 的调用。
//
// 对 `copy_nonoverlapping` 的调用是安全的,因为 `left!` 和 `right!` 保证不重叠,并且由于上述推理是有效的。
//
//
//
//
//
//
//
unsafe {
let tmp = ptr::read(left!());
ptr::copy_nonoverlapping(right!(), left!(), 1);
for _ in 1..count {
start_l = start_l.add(1);
ptr::copy_nonoverlapping(left!(), right!(), 1);
start_r = start_r.add(1);
ptr::copy_nonoverlapping(right!(), left!(), 1);
}
ptr::copy_nonoverlapping(&tmp, right!(), 1);
mem::forget(tmp);
start_l = start_l.add(1);
start_r = start_r.add(1);
}
}
if start_l == end_l {
// 左侧块中的所有乱序元素均已移动。移至下一个块。
// block-width-guarantee
// SAFETY: 如果 `!is_done` 那么至少保证宽度为 `2*BLOCK` 宽。由于 `offsets_l` 的大小,`offsets_l` 中最多有 `BLOCK` 个元素,所以 `offset` 操作是安全的。
// 否则,`is_done` 情况下的调试断言保证 `width(l, r) == block_l + block_r`,即块大小已被调整以考虑较少数量的剩余元素。
//
//
//
l = unsafe { l.add(block_l) };
}
if start_r == end_r {
// 右侧块中的所有乱序元素均已移动。移至上一个块。
// SAFETY: 与 [block-width-guarantee] 的参数相同。
// 这是一个完整的 `2*BLOCK` 块,或者 `block_r` 已针对最后少数元素进行了调整。
r = unsafe { r.sub(block_r) };
}
if is_done {
break;
}
}
// 现在剩下的全部是至多一个块 (左侧或右侧),其中需要移动的乱序元素。
// 这些剩余的元素可以简单地移到其块内的末尾。
//
if start_l < end_l {
// 剩下的方块仍然保留。
// 将其剩余的乱序元素移到最右边。
debug_assert_eq!(width(l, r), block_l);
while start_l < end_l {
// remaining-elements-safety
// SAFETY: 当循环条件成立时 `offsets_l` 中仍有元素,因此将 `end_l` 指向前一个元素是安全的。
//
// 如果 `ptr::swap` 的参数对读和写都有效,则它是安全的:
// - 根据上面的调试断言,`l` 和 `r` 之间的距离是 `block_l` 元素,因此 `start_l` 和 `end_l` 之间最多可以有 `block_l` 剩余偏移量。
// 这意味着 `r` 最多将向后移动 `block_l` 步,这使得 `r.offset` 调用有效 (在那个时候 `l == r`)。
// - `offsets_l` 包含在最后一个块的分区期间收集到的 `v` 的有效偏移量,因此 `l.offset` 调用是有效的。
//
//
//
//
unsafe {
end_l = end_l.sub(1);
ptr::swap(l.add(usize::from(*end_l)), r.sub(1));
r = r.sub(1);
}
}
width(v.as_mut_ptr(), r)
} else if start_r < end_r {
// 右边的块仍然存在。
// 将其剩余的乱序元素移到最左边。
debug_assert_eq!(width(l, r), block_r);
while start_r < end_r {
// SAFETY: 请参见 [剩余元素安全][remaining-elements-safety] 中的推理。
unsafe {
end_r = end_r.sub(1);
ptr::swap(l, r.sub(usize::from(*end_r) + 1));
l = l.add(1);
}
}
width(v.as_mut_ptr(), l)
} else {
// 没什么可做的,我们已经完成。
width(v.as_mut_ptr(), l)
}
}
/// 将 `v` 划分为小于 `v[pivot]` 的元素,然后划分为大于或等于 `v[pivot]` 的元素。
///
///
/// 返回一个元组:
///
/// 1. 小于 `v[pivot]` 的元素数。
/// 2. 如果 `v` 已经分区,则为 True。
pub(super) fn partition<T, F>(v: &mut [T], pivot: usize, is_less: &mut F) -> (usize, bool)
where
F: FnMut(&T, &T) -> bool,
{
let (mid, was_partitioned) = {
// 将枢轴放置在切片的开头。
v.swap(0, pivot);
let (pivot, v) = v.split_at_mut(1);
let pivot = &mut pivot[0];
// 将枢轴读取到栈分配的变量中以提高效率。
// 如果执行以下比较操作 panics,则枢轴将自动写回到切片中。
// SAFETY: `pivot` 是对 `v` 第一个元素的引用,所以 `ptr::read` 是安全的。
let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot };
let pivot = &*tmp;
// 查找第一对乱序元素。
let mut l = 0;
let mut r = v.len();
// SAFETY: 下面的不安全性涉及对数组进行索引。
// 对于第一个:我们已经在这里使用 `l < r` 进行了边界检查。
// 对于第二个:我们最初有 `l == 0` 和 `r == v.len()`,我们在每次索引操作中都检查了 `l < r`。
// 从这里我们知道 `r` 必须至少是 `r == l`,这从第一个开始就被证明是有效的。
unsafe {
// 找到大于或等于枢轴的第一个元素。
while l < r && is_less(v.get_unchecked(l), pivot) {
l += 1;
}
// 找到比枢轴更小的最后一个元素。
while l < r && !is_less(v.get_unchecked(r - 1), pivot) {
r -= 1;
}
}
(l + partition_in_blocks(&mut v[l..r], pivot, is_less), l >= r)
// `_pivot_guard` 离开作用域并将 pivot (这是一个栈分配的变量) 写回到它原来所在的切片中。
// 这一步对于确保安全至关重要!
//
};
// 将枢轴放置在两个分区之间。
v.swap(0, mid);
(mid, was_partitioned)
}
/// 将 `v` 划分为等于 `v[pivot]` 的元素,后跟大于 `v[pivot]` 的元素。
///
/// 返回等于枢轴的元素数。
/// 假定 `v` 不包含小于枢轴的元素。
pub(super) fn partition_equal<T, F>(v: &mut [T], pivot: usize, is_less: &mut F) -> usize
where
F: FnMut(&T, &T) -> bool,
{
// 将枢轴放置在切片的开头。
v.swap(0, pivot);
let (pivot, v) = v.split_at_mut(1);
let pivot = &mut pivot[0];
// 将枢轴读取到栈分配的变量中以提高效率。
// 如果执行以下比较操作 panics,则枢轴将自动写回到切片中。
// SAFETY: 此处的指针是有效的,因为它是从引用到切片获得的。
let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot };
let pivot = &*tmp;
// 现在对切片进行分区。
let mut l = 0;
let mut r = v.len();
loop {
// SAFETY: 下面的不安全性涉及对数组进行索引。
// 对于第一个:我们已经在这里使用 `l < r` 进行了边界检查。
// 对于第二个:我们最初有 `l == 0` 和 `r == v.len()`,我们在每次索引操作中都检查了 `l < r`。
// 从这里我们知道 `r` 必须至少是 `r == l`,这从第一个开始就被证明是有效的。
unsafe {
// 找到第一个大于枢轴的元素。
while l < r && !is_less(pivot, v.get_unchecked(l)) {
l += 1;
}
// 找到等于枢轴的最后一个元素。
while l < r && is_less(pivot, v.get_unchecked(r - 1)) {
r -= 1;
}
// 我们完成了吗?
if l >= r {
break;
}
// 交换找到的一对乱序元素。
r -= 1;
let ptr = v.as_mut_ptr();
ptr::swap(ptr.add(l), ptr.add(r));
l += 1;
}
}
// 我们发现 `l` 元素等于 pivot。为 pivot 本身加 1。
l + 1
// `_pivot_guard` 离开作用域并将 pivot (这是一个栈分配的变量) 写回到它原来所在的切片中。
// 这一步对于确保安全至关重要!
}
/// 散布一些元素,以尝试破坏可能导致快速排序中的分区不平衡的模式。
///
#[cold]
pub(super) fn break_patterns<T>(v: &mut [T]) {
let len = v.len();
if len >= 8 {
let mut seed = len;
let mut gen_usize = || {
// George Marsaglia 撰写的 "Xorshift RNGs" 论文中的伪随机数生成器。
if usize::BITS <= 32 {
let mut r = seed as u32;
r ^= r << 13;
r ^= r >> 17;
r ^= r << 5;
seed = r as usize;
seed
} else {
let mut r = seed as u64;
r ^= r << 13;
r ^= r >> 7;
r ^= r << 17;
seed = r as usize;
seed
}
};
// 取该数字取模的随机数。
// 该数字适合 `usize`,因为 `len` 不大于 `isize::MAX`。
let modulus = len.next_power_of_two();
// 一些关键候选人将在该指数附近。让我们随机化它们。
let pos = len / 4 * 2;
for i in 0..3 {
// 生成一个以 `len` 为模的随机数。
// 但是,为了避免昂贵的操作,我们首先将其取模为 2 的幂,然后减小 `len` 直到它适合 `[0, len - 1]` 范围。
//
let mut other = gen_usize() & (modulus - 1);
// `other` 保证小于 `2 * len`。
if other >= len {
other -= len;
}
v.swap(pos - 1 + i, other);
}
}
}
/// 在 `v` 中选择一个枢轴,如果切片可能已经排序,则返回索引和 `true`。
///
/// `v` 中的元素可能会在此过程中重新排序。
pub(super) fn choose_pivot<T, F>(v: &mut [T], is_less: &mut F) -> (usize, bool)
where
F: FnMut(&T, &T) -> bool,
{
// 选择中位数中位数方法的最小长度。
// 较短的切片使用简单的三位数中位数方法。
const SHORTEST_MEDIAN_OF_MEDIANS: usize = 50;
// 在此函数中可以执行的最大交换次数。
const MAX_SWAPS: usize = 4 * 3;
let len = v.len();
// 我们将在附近选择一个枢轴的三个指数。
let mut a = len / 4 * 1;
let mut b = len / 4 * 2;
let mut c = len / 4 * 3;
// 计算在对索引进行排序时我们将要执行的交换总数。
let mut swaps = 0;
if len >= 8 {
// 交换索引,以便 `v[a] <= v[b]`。
// SAFETY: `len >= 8` 所以在 `a`、`b` 和 `c` 的邻域中至少有两个元素。
// 这意味着对 `sort_adjacent` 的三个调用导致对 `sort3` 的相应调用以及每个指针周围的有效 3 项邻域,这反过来意味着对 `sort2` 的调用是通过有效的引用完成的。
//
// 因此 `v.get_unchecked` 调用是安全的,`ptr::swap` 调用也是安全的。
//
//
let mut sort2 = |a: &mut usize, b: &mut usize| unsafe {
if is_less(v.get_unchecked(*b), v.get_unchecked(*a)) {
ptr::swap(a, b);
swaps += 1;
}
};
// 交换索引,以便 `v[a] <= v[b] <= v[c]`。
let mut sort3 = |a: &mut usize, b: &mut usize, c: &mut usize| {
sort2(a, b);
sort2(b, c);
sort2(a, b);
};
if len >= SHORTEST_MEDIAN_OF_MEDIANS {
// 查找 `v[a - 1], v[a], v[a + 1]` 的中位数,并将索引存储到 `a` 中。
let mut sort_adjacent = |a: &mut usize| {
let tmp = *a;
sort3(&mut (tmp - 1), a, &mut (tmp + 1));
};
// 查找 `a`,`b` 和 `c` 附近的中位数。
sort_adjacent(&mut a);
sort_adjacent(&mut b);
sort_adjacent(&mut c);
}
// 在 `a`,`b` 和 `c` 中找到中位数。
sort3(&mut a, &mut b, &mut c);
}
if swaps < MAX_SWAPS {
(b, swaps == 0)
} else {
// 已执行最大交换次数。
// 切片可能是降序的,或者大多是降序的,因此反转可能有助于更快地对其进行排序。
v.reverse();
(len - 1 - b, true)
}
}
/// 递归排序 `v`。
///
/// 如果切片在原始数组中具有前身,则将其指定为 `pred`。
///
/// `limit` 是切换到 `heapsort` 之前允许的不平衡分区数。
/// 如果为零,则此函数将立即切换到 heapsort。
fn recurse<'a, T, F>(mut v: &'a mut [T], is_less: &mut F, mut pred: Option<&'a T>, mut limit: u32)
where
F: FnMut(&T, &T) -> bool,
{
// 长度不超过此长度的切片将使用插入排序进行排序。
const MAX_INSERTION: usize = 20;
// 如果最后一个分区合理平衡,则为 true。
let mut was_balanced = true;
// 如果最后一个分区没有重排元素 (切片已分区),则为 true。
let mut was_partitioned = true;
loop {
let len = v.len();
// 非常短的切片使用插入排序进行排序。
if len <= MAX_INSERTION {
if len >= 2 {
insertion_sort_shift_left(v, 1, is_less);
}
return;
}
// 如果做出了太多错误的枢轴选择,则只需回退到 heapsort 以确保 `O(n * log(n))` 最坏的情况。
//
if limit == 0 {
heapsort(v, is_less);
return;
}
// 如果最后一个分区不平衡,请尝试通过改组一些元素来破坏切片中的模式。
// 希望这次我们选择一个更好的支点。
if !was_balanced {
break_patterns(v);
limit -= 1;
}
// 选择一个枢轴,然后尝试猜测切片是否已排序。
let (pivot, likely_sorted) = choose_pivot(v, is_less);
// 如果最后一个分区是平衡的并且没有打乱元素,并且如果 pivot 选择预测切片可能已经排序...
//
if was_balanced && was_partitioned && likely_sorted {
// 尝试识别几个乱序的元素,然后将它们移到正确的位置。
// 如果切片最终被完全排序,那么我们就完成了。
if partial_insertion_sort(v, is_less) {
return;
}
}
// 如果选择的枢轴等于前一个枢轴,则它是切片中的最小元素。
// 将切片划分为等于和大于枢轴的元素。
// 当切片包含许多重复元素时,通常会遇到这种情况。
if let Some(p) = pred {
if !is_less(p, &v[pivot]) {
let mid = partition_equal(v, pivot, is_less);
// 继续对大于枢轴的元素进行排序。
v = &mut v[mid..];
continue;
}
}
// 对切片进行分区。
let (mid, was_p) = partition(v, pivot, is_less);
was_balanced = cmp::min(mid, len - mid) >= len / 8;
was_partitioned = was_p;
// 将切片分为 `left`,`pivot` 和 `right`。
let (left, right) = v.split_at_mut(mid);
let (pivot, right) = right.split_at_mut(1);
let pivot = &pivot[0];
// 递归到较短的一侧只是为了最大程度地减少递归调用的总数并占用较少的栈空间。
// 然后,继续较长的那一面 (这类似于尾部递归)。
//
if left.len() < right.len() {
recurse(left, is_less, pred, limit);
v = right;
pred = Some(pivot);
} else {
recurse(right, is_less, Some(pivot), limit);
v = left;
}
}
}
/// 使用模式破坏快速排序对 `v` 进行排序,这是 *O*(*n*\*log(* n*)) 最坏的情况。
pub fn quicksort<T, F>(v: &mut [T], mut is_less: F)
where
F: FnMut(&T, &T) -> bool,
{
// 零大小类型的排序没有有意义的行为。
if T::IS_ZST {
return;
}
// 将不平衡分区的数量限制为 `floor(log2(len)) + 1`。
let limit = usize::BITS - v.len().leading_zeros();
recurse(v, &mut is_less, None, limit);
}
/// 使用 `buf` 作为临时存储合并非递减运行 `v[..mid]` 和 `v[mid..]`,并将结果存储到 `v[..]` 中。
///
/// # Safety
///
/// 这两个片必须是非空的,并且 `mid` 必须在范围之内。
/// 缓冲区 `buf` 必须足够长才能容纳较短切片的副本。
/// 另外,`T` 不能为零大小类型。
unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
let v = v.as_mut_ptr();
// SAFETY: mid 和 len 必须在范围内 v.
let (v_mid, v_end) = unsafe { (v.add(mid), v.add(len)) };
// 合并过程首先将较短的运行复制到 `buf` 中。
// 然后,它将跟踪新复制的运行,以及向前运行 (或向后运行) 的较长运行,比较它们的下一个未消耗元素,并将较小 (或较大) 的运行复制到 `v` 中。
//
// 一旦较短的运行时间被完全用尽,该过程就完成了。如果较长的运行首先被消耗,那么我们必须将较短的运行剩下的任何内容复制到 `v` 中剩余的 hole 中。
//
// `hole` 始终跟踪过程的中间状态,这有两个目的:
// 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
// 2. 如果较长时间的运行首先被消耗,则将 `v` 中剩余的 hole 填充。
//
// Panic 安全:
//
// 如果在此过程中的任何时候 `is_less` panics,`hole` 都会丢弃并用 `buf` 中的未消耗范围填充 `v` 中的 hole,从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
//
//
//
//
//
let mut hole;
if mid <= len - mid {
// 左边的运行更短。
// SAFETY: buf 必须有足够的容量用于 `v[..mid]`。
unsafe {
ptr::copy_nonoverlapping(v, buf, mid);
hole = MergeHole { start: buf, end: buf.add(mid), dest: v };
}
// 最初,这些指针指向其数组的开头。
let left = &mut hole.start;
let mut right = v_mid;
let out = &mut hole.dest;
while *left < hole.end && right < v_end {
// 消耗较小的一面。
// 如果相等,则选择左旋以保持稳定性。
// SAFETY: left 和 right 必须有效并且 v 的一部分对于 out 相同。
unsafe {
let is_l = is_less(&*right, &**left);
let to_copy = if is_l { right } else { *left };
ptr::copy_nonoverlapping(to_copy, *out, 1);
*out = out.add(1);
right = right.add(is_l as usize);
*left = left.add(!is_l as usize);
}
}
} else {
// 右边的运行更短
// SAFETY: buf 必须有足够的容量用于 `v[mid..]`。
unsafe {
ptr::copy_nonoverlapping(v_mid, buf, len - mid);
hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };
}
// 最初,这些指针指向其数组的两端。
let left = &mut hole.dest;
let right = &mut hole.end;
let mut out = v_end;
while v < *left && buf < *right {
// 消耗更大的一面。
// 如果相等,则选择正确的行程以保持稳定性。
// SAFETY: left 和 right 必须有效并且 v 的一部分对于 out 相同。
unsafe {
let is_l = is_less(&*right.sub(1), &*left.sub(1));
*left = left.sub(is_l as usize);
*right = right.sub(!is_l as usize);
let to_copy = if is_l { *left } else { *right };
out = out.sub(1);
ptr::copy_nonoverlapping(to_copy, out, 1);
}
}
}
// 最后,`hole` 被丢弃。
// 如果较短的运行没有被完全消耗,则其剩余的任何内容现在都将被复制到 `v` 的 hole 中。
// 丢弃时,将范围 `start..end` 复制到 `dest..`。
struct MergeHole<T> {
start: *mut T,
end: *mut T,
dest: *mut T,
}
impl<T> Drop for MergeHole<T> {
fn drop(&mut self) {
// SAFETY: `T` 不是零大小的类型,它们是指向切片元素的指针。
unsafe {
let len = self.end.sub_ptr(self.start);
ptr::copy_nonoverlapping(self.start, self.dest, len);
}
}
}
}
/// 这个归并排序借用了一些 (但不是全部) 来自 TimSort 的想法,它曾经被详细描述在 [这里](https://github.com/python/cpython/blob/main/Objects/listsort.txt)。
/// 但是 Python 已经切换到基于 Powersort 的实现。
///
/// 该算法识别严格降序和非降序的子序列,这些子序列称为自然行程。有待合并的待处理运行栈。
/// 将每个新发现的运行推入栈中,然后合并一些相邻的运行对,直到这两个不变量得到满足:
///
/// 1. 对于 `1..runs.len()` 中的每个 `i`: `runs[i - 1].len > runs[i].len`
/// 2. 对于 `2..runs.len()` 中的每个 `i`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
///
/// 不变量确保最坏情况下的总运行时间为 *O*(*n*\*log(* n*))。
///
///
///
pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>(
v: &mut [T],
is_less: &mut CmpF,
elem_alloc_fn: ElemAllocF,
elem_dealloc_fn: ElemDeallocF,
run_alloc_fn: RunAllocF,
run_dealloc_fn: RunDeallocF,
) where
CmpF: FnMut(&T, &T) -> bool,
ElemAllocF: Fn(usize) -> *mut T,
ElemDeallocF: Fn(*mut T, usize),
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
// 长度不超过此长度的切片将使用插入排序进行排序。
const MAX_INSERTION: usize = 20;
// 调用者应该已经检查过了。
debug_assert!(!T::IS_ZST);
let len = v.len();
// 短数组通过插入排序进行就地排序,以避免分配。
if len <= MAX_INSERTION {
if len >= 2 {
insertion_sort_shift_left(v, 1, is_less);
}
return;
}
// 分配缓冲区以用作暂存器。我们将长度保持为 0,这样就可以在其中保留 `v` 内容的浅表副本,而不会冒 `is_less` panics 在副本上运行 dtor 的风险。
//
// 合并两个已排序的运行时,此缓冲区将保存一个较短运行的副本,该副本的长度始终最多为 `len / 2`。
//
let buf = BufGuard::new(len / 2, elem_alloc_fn, elem_dealloc_fn);
let buf_ptr = buf.buf_ptr.as_ptr();
let mut runs = RunVec::new(run_alloc_fn, run_dealloc_fn);
let mut end = 0;
let mut start = 0;
// 向前扫描。内存预取更喜欢向前扫描而不是向后扫描,代码生成通常更好。
// 对于最敏感的类型 (如整数),它们会立即双向合并。
// 所以向后扫描没有任何好处。
while end < len {
let (streak_end, was_reversed) = find_streak(&v[start..], is_less);
end += streak_end;
if was_reversed {
v[start..end].reverse();
}
// 如果过短,请在运行中插入更多元素。
// 插入排序比短序列上的合并排序要快,因此可以显着提高性能。
end = provide_sorted_batch(v, start, end, is_less);
// 将此运行推入栈。
runs.push(TimSortRun { start, len: end - start });
start = end;
// 合并一些成对的相邻行程以满足不变性。
while let Some(r) = collapse(runs.as_slice(), len) {
let left = runs[r];
let right = runs[r + 1];
let merge_slice = &mut v[left.start..right.start + right.len];
// SAFETY: `buf_ptr` 必须为两侧中较短的一侧提供足够的容量,并且任何一侧都不能超过长度 0.
//
unsafe {
merge(merge_slice, left.len, buf_ptr, is_less);
}
runs[r + 1] = TimSortRun { start: left.start, len: left.len + right.len };
runs.remove(r);
}
}
// 最后,必须在栈中仅保留一次运行。
debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
// 检查运行栈,并确定要合并的下一对运行。
// 更具体地说,如果返回 `Some(r)`,则意味着接下来必须合并 `runs[r]` 和 `runs[r + 1]`。
// 如果算法应继续构建新的运行,则返回 `None`。
//
// TimSort 因其 buggy 实现而臭名昭著,如下所述:
// http://envisage-project.eu/timsort-specification-and-verification/
//
// 这个故事的重点是:我们必须在栈的前四次运行中强制执行不变量。
// 仅在前三个上强制执行它们不足以确保不变量仍然适用于栈中的所有运行。
//
// 此函数正确检查前四次运行的不变量。
// 另外,如果最高运行从索引 0 开始,它将始终要求合并操作,直到栈完全展开为止,以完成排序。
//
//
#[inline]
fn collapse(runs: &[TimSortRun], stop: usize) -> Option<usize> {
let n = runs.len();
if n >= 2
&& (runs[n - 1].start + runs[n - 1].len == stop
|| runs[n - 2].len <= runs[n - 1].len
|| (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)
|| (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))
{
if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }
} else {
None
}
}
// Vec 的极其基本的版本。
// 它们的使用非常有限,通过在此处提供代码,它允许在排序实现之间重用。
//
struct BufGuard<T, ElemDeallocF>
where
ElemDeallocF: Fn(*mut T, usize),
{
buf_ptr: ptr::NonNull<T>,
capacity: usize,
elem_dealloc_fn: ElemDeallocF,
}
impl<T, ElemDeallocF> BufGuard<T, ElemDeallocF>
where
ElemDeallocF: Fn(*mut T, usize),
{
fn new<ElemAllocF>(
len: usize,
elem_alloc_fn: ElemAllocF,
elem_dealloc_fn: ElemDeallocF,
) -> Self
where
ElemAllocF: Fn(usize) -> *mut T,
{
Self {
buf_ptr: ptr::NonNull::new(elem_alloc_fn(len)).unwrap(),
capacity: len,
elem_dealloc_fn,
}
}
}
impl<T, ElemDeallocF> Drop for BufGuard<T, ElemDeallocF>
where
ElemDeallocF: Fn(*mut T, usize),
{
fn drop(&mut self) {
(self.elem_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity);
}
}
struct RunVec<RunAllocF, RunDeallocF>
where
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
buf_ptr: ptr::NonNull<TimSortRun>,
capacity: usize,
len: usize,
run_alloc_fn: RunAllocF,
run_dealloc_fn: RunDeallocF,
}
impl<RunAllocF, RunDeallocF> RunVec<RunAllocF, RunDeallocF>
where
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
fn new(run_alloc_fn: RunAllocF, run_dealloc_fn: RunDeallocF) -> Self {
// 大多数切片最多可以进行 16 次运行排序。
const START_RUN_CAPACITY: usize = 16;
Self {
buf_ptr: ptr::NonNull::new(run_alloc_fn(START_RUN_CAPACITY)).unwrap(),
capacity: START_RUN_CAPACITY,
len: 0,
run_alloc_fn,
run_dealloc_fn,
}
}
fn push(&mut self, val: TimSortRun) {
if self.len == self.capacity {
let old_capacity = self.capacity;
let old_buf_ptr = self.buf_ptr.as_ptr();
self.capacity = self.capacity * 2;
self.buf_ptr = ptr::NonNull::new((self.run_alloc_fn)(self.capacity)).unwrap();
// SAFETY: buf_ptr new 和 old 被正确分配并且 old_buf_ptr 具有 old_capacity 有效元素。
//
unsafe {
ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr.as_ptr(), old_capacity);
}
(self.run_dealloc_fn)(old_buf_ptr, old_capacity);
}
// SAFETY: 刚刚检查了不变体。
unsafe {
self.buf_ptr.as_ptr().add(self.len).write(val);
}
self.len += 1;
}
fn remove(&mut self, index: usize) {
if index >= self.len {
panic!("Index out of bounds");
}
// SAFETY: buf_ptr 需要有效并且 len 不变。
unsafe {
// 我们要去的地方。
let ptr = self.buf_ptr.as_ptr().add(index);
// 向下移动所有内容以填充该位置。
ptr::copy(ptr.add(1), ptr, self.len - index - 1);
}
self.len -= 1;
}
fn as_slice(&self) -> &[TimSortRun] {
// SAFETY: 只要 buf_ptr 有效并且 len 不变性得到支持,它就是安全的。
unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr.as_ptr(), self.len) }
}
fn len(&self) -> usize {
self.len
}
}
impl<RunAllocF, RunDeallocF> core::ops::Index<usize> for RunVec<RunAllocF, RunDeallocF>
where
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
type Output = TimSortRun;
fn index(&self, index: usize) -> &Self::Output {
if index < self.len {
// SAFETY: 必须坚持 buf_ptr 和 len 不,变体。
unsafe {
return &*(self.buf_ptr.as_ptr().add(index));
}
}
panic!("Index out of bounds");
}
}
impl<RunAllocF, RunDeallocF> core::ops::IndexMut<usize> for RunVec<RunAllocF, RunDeallocF>
where
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
if index < self.len {
// SAFETY: 必须坚持 buf_ptr 和 len 不,变体。
unsafe {
return &mut *(self.buf_ptr.as_ptr().add(index));
}
}
panic!("Index out of bounds");
}
}
impl<RunAllocF, RunDeallocF> Drop for RunVec<RunAllocF, RunDeallocF>
where
RunAllocF: Fn(usize) -> *mut TimSortRun,
RunDeallocF: Fn(*mut TimSortRun, usize),
{
fn drop(&mut self) {
// 只要 TimSortRun 是 Copy,我们就不需要单独丢弃它们,而只需丢弃整个分配。
//
(self.run_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity);
}
}
}
/// merge_sort 使用的内部类型。
#[derive(Clone, Copy, Debug)]
pub struct TimSortRun {
len: usize,
start: usize,
}
/// 采用由开始和结束表示的范围,该范围已经排序,并在必要时将其扩展到右侧,并使用针对较小范围 (例如插入排序) 优化的排序。
///
fn provide_sorted_batch<T, F>(v: &mut [T], start: usize, mut end: usize, is_less: &mut F) -> usize
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
assert!(end >= start && end <= len);
// 该值是最少比较和最佳性能之间的平衡,例如受缓存位置的影响。
//
const MIN_INSERTION_RUN: usize = 10;
// 如果过短,请在运行中插入更多元素。
// 插入排序比短序列上的合并排序要快,因此可以显着提高性能。
let start_end_diff = end - start;
if start_end_diff < MIN_INSERTION_RUN && end < len {
// v [start_found..end] 是已经在输入中排序的元素。
// 我们想将排序区域向左扩展,因此我们将 MIN_INSERTION_RUN-1 推向右侧。
// 这比试图将那些已经排序的元素推到左边更有效。
end = cmp::min(start + MIN_INSERTION_RUN, len);
let presorted_start = cmp::max(start_end_diff, 1);
insertion_sort_shift_left(&mut v[start..end], presorted_start, is_less);
}
end
}
/// 查找从切片开头开始的一系列预排序元素。
/// 返回不属于所述连胜的第一个值,以及表示连胜是否被反转的 bool。
/// 条纹可以增加或减少。
fn find_streak<T, F>(v: &[T], is_less: &mut F) -> (usize, bool)
where
F: FnMut(&T, &T) -> bool,
{
let len = v.len();
if len < 2 {
return (len, false);
}
let mut end = 2;
// SAFETY: 具体见下文。
unsafe {
// SAFETY: 我们检查了 len >= 2,因此 0 和 1 是有效索引。
let assume_reverse = is_less(v.get_unchecked(1), v.get_unchecked(0));
// SAFETY: 我们知道 end >= 2 并检查 end < len。
// 由此可见,在 end 和 end-1 处访问 v 是安全的。
if assume_reverse {
while end < len && is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) {
end += 1;
}
(end, true)
} else {
while end < len && !is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) {
end += 1;
}
(end, false)
}
}
}