diff options
Diffstat (limited to '')
| -rw-r--r-- | third_party/rust/range-alloc/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/range-alloc/Cargo.toml | 23 | ||||
| -rw-r--r-- | third_party/rust/range-alloc/LICENSE.APACHE | 176 | ||||
| -rw-r--r-- | third_party/rust/range-alloc/LICENSE.MIT | 21 | ||||
| -rw-r--r-- | third_party/rust/range-alloc/src/lib.rs | 329 |
5 files changed, 550 insertions, 0 deletions
diff --git a/third_party/rust/range-alloc/.cargo-checksum.json b/third_party/rust/range-alloc/.cargo-checksum.json new file mode 100644 index 0000000000..187cb6cb08 --- /dev/null +++ b/third_party/rust/range-alloc/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"2b0e7d63d79821d7a1515971a75adefaa96acef117e15fcdf50b49dda71acd6a","LICENSE.APACHE":"a6cba85bc92e0cff7a450b1d873c0eaa2e9fc96bf472df0247a26bec77bf3ff9","LICENSE.MIT":"ba00052102ed87948bb8822d6e1c496260c83042887b22bb5caad922ec025a60","src/lib.rs":"a62600cbf426d2469333c0ccee16041cf63588cdeb8dad78387e7ab18e70d29e"},"package":"9c8a99fddc9f0ba0a85884b8d14e3592853e787d581ca1816c91349b10e4eeab"}
\ No newline at end of file diff --git a/third_party/rust/range-alloc/Cargo.toml b/third_party/rust/range-alloc/Cargo.toml new file mode 100644 index 0000000000..c03c7d2111 --- /dev/null +++ b/third_party/rust/range-alloc/Cargo.toml @@ -0,0 +1,23 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2018" +name = "range-alloc" +version = "0.1.3" +authors = ["the gfx-rs Developers"] +description = "Generic range allocator" +homepage = "https://github.com/gfx-rs/range-alloc" +documentation = "https://docs.rs/range-alloc" +keywords = ["allocator"] +categories = ["memory-management"] +license = "MIT OR Apache-2.0" +repository = "https://github.com/gfx-rs/range-alloc" diff --git a/third_party/rust/range-alloc/LICENSE.APACHE b/third_party/rust/range-alloc/LICENSE.APACHE new file mode 100644 index 0000000000..d9a10c0d8e --- /dev/null +++ b/third_party/rust/range-alloc/LICENSE.APACHE @@ -0,0 +1,176 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS diff --git a/third_party/rust/range-alloc/LICENSE.MIT b/third_party/rust/range-alloc/LICENSE.MIT new file mode 100644 index 0000000000..c706b62c79 --- /dev/null +++ b/third_party/rust/range-alloc/LICENSE.MIT @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2023 The gfx-rs developers + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/third_party/rust/range-alloc/src/lib.rs b/third_party/rust/range-alloc/src/lib.rs new file mode 100644 index 0000000000..767d31e909 --- /dev/null +++ b/third_party/rust/range-alloc/src/lib.rs @@ -0,0 +1,329 @@ +use std::{ + fmt::Debug, + iter::Sum, + ops::{Add, AddAssign, Range, Sub}, +}; + +#[derive(Debug)] +pub struct RangeAllocator<T> { + /// The range this allocator covers. + initial_range: Range<T>, + /// A Vec of ranges in this heap which are unused. + /// Must be ordered with ascending range start to permit short circuiting allocation. + /// No two ranges in this vec may overlap. + free_ranges: Vec<Range<T>>, +} + +#[derive(Clone, Debug, PartialEq)] +pub struct RangeAllocationError<T> { + pub fragmented_free_length: T, +} + +impl<T> RangeAllocator<T> +where + T: Clone + Copy + Add<Output = T> + AddAssign + Sub<Output = T> + Eq + PartialOrd + Debug, +{ + pub fn new(range: Range<T>) -> Self { + RangeAllocator { + initial_range: range.clone(), + free_ranges: vec![range], + } + } + + pub fn initial_range(&self) -> &Range<T> { + &self.initial_range + } + + pub fn grow_to(&mut self, new_end: T) { + if let Some(last_range) = self.free_ranges.last_mut() { + last_range.end = new_end; + } else { + self.free_ranges.push(self.initial_range.end..new_end); + } + + self.initial_range.end = new_end; + } + + pub fn allocate_range(&mut self, length: T) -> Result<Range<T>, RangeAllocationError<T>> { + assert_ne!(length + length, length); + let mut best_fit: Option<(usize, Range<T>)> = None; + + // This is actually correct. With the trait bound as it is, we have + // no way to summon a value of 0 directly, so we make one by subtracting + // something from itself. Once the trait bound can be changed, this can + // be fixed. + #[allow(clippy::eq_op)] + let mut fragmented_free_length = length - length; + for (index, range) in self.free_ranges.iter().cloned().enumerate() { + let range_length = range.end - range.start; + fragmented_free_length += range_length; + if range_length < length { + continue; + } else if range_length == length { + // Found a perfect fit, so stop looking. + best_fit = Some((index, range)); + break; + } + best_fit = Some(match best_fit { + Some((best_index, best_range)) => { + // Find best fit for this allocation to reduce memory fragmentation. + if range_length < best_range.end - best_range.start { + (index, range) + } else { + (best_index, best_range.clone()) + } + } + None => (index, range), + }); + } + match best_fit { + Some((index, range)) => { + if range.end - range.start == length { + self.free_ranges.remove(index); + } else { + self.free_ranges[index].start += length; + } + Ok(range.start..(range.start + length)) + } + None => Err(RangeAllocationError { + fragmented_free_length, + }), + } + } + + pub fn free_range(&mut self, range: Range<T>) { + assert!(self.initial_range.start <= range.start && range.end <= self.initial_range.end); + assert!(range.start < range.end); + + // Get insertion position. + let i = self + .free_ranges + .iter() + .position(|r| r.start > range.start) + .unwrap_or(self.free_ranges.len()); + + // Try merging with neighboring ranges in the free list. + // Before: |left|-(range)-|right| + if i > 0 && range.start == self.free_ranges[i - 1].end { + // Merge with |left|. + self.free_ranges[i - 1].end = + if i < self.free_ranges.len() && range.end == self.free_ranges[i].start { + // Check for possible merge with |left| and |right|. + let right = self.free_ranges.remove(i); + right.end + } else { + range.end + }; + + return; + } else if i < self.free_ranges.len() && range.end == self.free_ranges[i].start { + // Merge with |right|. + self.free_ranges[i].start = if i > 0 && range.start == self.free_ranges[i - 1].end { + // Check for possible merge with |left| and |right|. + let left = self.free_ranges.remove(i - 1); + left.start + } else { + range.start + }; + + return; + } + + // Debug checks + assert!( + (i == 0 || self.free_ranges[i - 1].end < range.start) + && (i >= self.free_ranges.len() || range.end < self.free_ranges[i].start) + ); + + self.free_ranges.insert(i, range); + } + + /// Returns an iterator over allocated non-empty ranges + pub fn allocated_ranges(&self) -> impl Iterator<Item = Range<T>> + '_ { + let first = match self.free_ranges.first() { + Some(Range { ref start, .. }) if *start > self.initial_range.start => { + Some(self.initial_range.start..*start) + } + None => Some(self.initial_range.clone()), + _ => None, + }; + + let last = match self.free_ranges.last() { + Some(Range { end, .. }) if *end < self.initial_range.end => { + Some(*end..self.initial_range.end) + } + _ => None, + }; + + let mid = self + .free_ranges + .iter() + .zip(self.free_ranges.iter().skip(1)) + .map(|(ra, rb)| ra.end..rb.start); + + first.into_iter().chain(mid).chain(last) + } + + pub fn reset(&mut self) { + self.free_ranges.clear(); + self.free_ranges.push(self.initial_range.clone()); + } + + pub fn is_empty(&self) -> bool { + self.free_ranges.len() == 1 && self.free_ranges[0] == self.initial_range + } +} + +impl<T: Copy + Sub<Output = T> + Sum> RangeAllocator<T> { + pub fn total_available(&self) -> T { + self.free_ranges + .iter() + .map(|range| range.end - range.start) + .sum() + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_basic_allocation() { + let mut alloc = RangeAllocator::new(0..10); + // Test if an allocation works + assert_eq!(alloc.allocate_range(4), Ok(0..4)); + assert!(alloc.allocated_ranges().eq(std::iter::once(0..4))); + // Free the prior allocation + alloc.free_range(0..4); + // Make sure the free actually worked + assert_eq!(alloc.free_ranges, vec![0..10]); + assert!(alloc.allocated_ranges().eq(std::iter::empty())); + } + + #[test] + fn test_out_of_space() { + let mut alloc = RangeAllocator::new(0..10); + // Test if the allocator runs out of space correctly + assert_eq!(alloc.allocate_range(10), Ok(0..10)); + assert!(alloc.allocated_ranges().eq(std::iter::once(0..10))); + assert!(alloc.allocate_range(4).is_err()); + alloc.free_range(0..10); + } + + #[test] + fn test_grow() { + let mut alloc = RangeAllocator::new(0..11); + // Test if the allocator runs out of space correctly + assert_eq!(alloc.allocate_range(10), Ok(0..10)); + assert!(alloc.allocated_ranges().eq(std::iter::once(0..10))); + assert!(alloc.allocate_range(4).is_err()); + alloc.grow_to(20); + assert_eq!(alloc.allocate_range(4), Ok(10..14)); + alloc.free_range(0..14); + } + + #[test] + fn test_dont_use_block_that_is_too_small() { + let mut alloc = RangeAllocator::new(0..10); + // Allocate three blocks then free the middle one and check for correct state + assert_eq!(alloc.allocate_range(3), Ok(0..3)); + assert_eq!(alloc.allocate_range(3), Ok(3..6)); + assert_eq!(alloc.allocate_range(3), Ok(6..9)); + alloc.free_range(3..6); + assert_eq!(alloc.free_ranges, vec![3..6, 9..10]); + assert_eq!( + alloc.allocated_ranges().collect::<Vec<Range<i32>>>(), + vec![0..3, 6..9] + ); + // Now request space that the middle block can fill, but the end one can't. + assert_eq!(alloc.allocate_range(3), Ok(3..6)); + } + + #[test] + fn test_free_blocks_in_middle() { + let mut alloc = RangeAllocator::new(0..100); + // Allocate many blocks then free every other block. + assert_eq!(alloc.allocate_range(10), Ok(0..10)); + assert_eq!(alloc.allocate_range(10), Ok(10..20)); + assert_eq!(alloc.allocate_range(10), Ok(20..30)); + assert_eq!(alloc.allocate_range(10), Ok(30..40)); + assert_eq!(alloc.allocate_range(10), Ok(40..50)); + assert_eq!(alloc.allocate_range(10), Ok(50..60)); + assert_eq!(alloc.allocate_range(10), Ok(60..70)); + assert_eq!(alloc.allocate_range(10), Ok(70..80)); + assert_eq!(alloc.allocate_range(10), Ok(80..90)); + assert_eq!(alloc.allocate_range(10), Ok(90..100)); + assert_eq!(alloc.free_ranges, vec![]); + assert!(alloc.allocated_ranges().eq(std::iter::once(0..100))); + alloc.free_range(10..20); + alloc.free_range(30..40); + alloc.free_range(50..60); + alloc.free_range(70..80); + alloc.free_range(90..100); + // Check that the right blocks were freed. + assert_eq!( + alloc.free_ranges, + vec![10..20, 30..40, 50..60, 70..80, 90..100] + ); + assert_eq!( + alloc.allocated_ranges().collect::<Vec<Range<i32>>>(), + vec![0..10, 20..30, 40..50, 60..70, 80..90] + ); + // Fragment the memory on purpose a bit. + assert_eq!(alloc.allocate_range(6), Ok(10..16)); + assert_eq!(alloc.allocate_range(6), Ok(30..36)); + assert_eq!(alloc.allocate_range(6), Ok(50..56)); + assert_eq!(alloc.allocate_range(6), Ok(70..76)); + assert_eq!(alloc.allocate_range(6), Ok(90..96)); + // Check for fragmentation. + assert_eq!( + alloc.free_ranges, + vec![16..20, 36..40, 56..60, 76..80, 96..100] + ); + assert_eq!( + alloc.allocated_ranges().collect::<Vec<Range<i32>>>(), + vec![0..16, 20..36, 40..56, 60..76, 80..96] + ); + // Fill up the fragmentation + assert_eq!(alloc.allocate_range(4), Ok(16..20)); + assert_eq!(alloc.allocate_range(4), Ok(36..40)); + assert_eq!(alloc.allocate_range(4), Ok(56..60)); + assert_eq!(alloc.allocate_range(4), Ok(76..80)); + assert_eq!(alloc.allocate_range(4), Ok(96..100)); + // Check that nothing is free. + assert_eq!(alloc.free_ranges, vec![]); + assert!(alloc.allocated_ranges().eq(std::iter::once(0..100))); + } + + #[test] + fn test_ignore_block_if_another_fits_better() { + let mut alloc = RangeAllocator::new(0..10); + // Allocate blocks such that the only free spaces available are 3..6 and 9..10 + // in order to prepare for the next test. + assert_eq!(alloc.allocate_range(3), Ok(0..3)); + assert_eq!(alloc.allocate_range(3), Ok(3..6)); + assert_eq!(alloc.allocate_range(3), Ok(6..9)); + alloc.free_range(3..6); + assert_eq!(alloc.free_ranges, vec![3..6, 9..10]); + assert_eq!( + alloc.allocated_ranges().collect::<Vec<Range<i32>>>(), + vec![0..3, 6..9] + ); + // Now request space that can be filled by 3..6 but should be filled by 9..10 + // because 9..10 is a perfect fit. + assert_eq!(alloc.allocate_range(1), Ok(9..10)); + } + + #[test] + fn test_merge_neighbors() { + let mut alloc = RangeAllocator::new(0..9); + assert_eq!(alloc.allocate_range(3), Ok(0..3)); + assert_eq!(alloc.allocate_range(3), Ok(3..6)); + assert_eq!(alloc.allocate_range(3), Ok(6..9)); + alloc.free_range(0..3); + alloc.free_range(6..9); + alloc.free_range(3..6); + assert_eq!(alloc.free_ranges, vec![0..9]); + assert!(alloc.allocated_ranges().eq(std::iter::empty())); + } +} |