From ccb9dac5ed65341bf8d9ce01a83b9aad02f42526 Mon Sep 17 00:00:00 2001 From: Taiki Endo Date: Sat, 4 May 2019 23:48:57 +0900 Subject: Fix intra-doc link resolution failure on re-exporting libstd --- src/liballoc/alloc.rs | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) (limited to 'src/liballoc') diff --git a/src/liballoc/alloc.rs b/src/liballoc/alloc.rs index ddc6481eec7..41ff06d70ff 100644 --- a/src/liballoc/alloc.rs +++ b/src/liballoc/alloc.rs @@ -37,6 +37,8 @@ extern "Rust" { /// /// Note: while this type is unstable, the functionality it provides can be /// accessed through the [free functions in `alloc`](index.html#functions). +/// +/// [`Alloc`]: trait.Alloc.html #[unstable(feature = "allocator_api", issue = "32838")] #[derive(Copy, Clone, Default, Debug)] pub struct Global; @@ -54,6 +56,10 @@ pub struct Global; /// /// See [`GlobalAlloc::alloc`]. /// +/// [`Global`]: struct.Global.html +/// [`Alloc`]: trait.Alloc.html +/// [`GlobalAlloc::alloc`]: trait.GlobalAlloc.html#tymethod.alloc +/// /// # Examples /// /// ``` @@ -87,6 +93,10 @@ pub unsafe fn alloc(layout: Layout) -> *mut u8 { /// # Safety /// /// See [`GlobalAlloc::dealloc`]. +/// +/// [`Global`]: struct.Global.html +/// [`Alloc`]: trait.Alloc.html +/// [`GlobalAlloc::dealloc`]: trait.GlobalAlloc.html#tymethod.dealloc #[stable(feature = "global_alloc", since = "1.28.0")] #[inline] pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) { @@ -105,6 +115,10 @@ pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) { /// # Safety /// /// See [`GlobalAlloc::realloc`]. +/// +/// [`Global`]: struct.Global.html +/// [`Alloc`]: trait.Alloc.html +/// [`GlobalAlloc::realloc`]: trait.GlobalAlloc.html#method.realloc #[stable(feature = "global_alloc", since = "1.28.0")] #[inline] pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 { @@ -124,6 +138,10 @@ pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 /// /// See [`GlobalAlloc::alloc_zeroed`]. /// +/// [`Global`]: struct.Global.html +/// [`Alloc`]: trait.Alloc.html +/// [`GlobalAlloc::alloc_zeroed`]: trait.GlobalAlloc.html#method.alloc_zeroed +/// /// # Examples /// /// ``` -- cgit 1.4.1-3-g733a5 From ea7aa76911b6b896d503a812b26bfd6227fa90d9 Mon Sep 17 00:00:00 2001 From: David Tolnay Date: Sat, 18 May 2019 20:25:15 -0700 Subject: Document BinaryHeap time complexity I went into some detail on the time complexity of `push` because it is relevant for using BinaryHeap efficiently -- specifically that you should avoid pushing many elements in ascending order when possible. --- src/liballoc/collections/binary_heap.rs | 43 +++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) (limited to 'src/liballoc') diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs index 39fcfaa7893..c5a0b6e877b 100644 --- a/src/liballoc/collections/binary_heap.rs +++ b/src/liballoc/collections/binary_heap.rs @@ -231,6 +231,20 @@ use super::SpecExtend; /// assert_eq!(heap.pop(), Some(Reverse(5))); /// assert_eq!(heap.pop(), None); /// ``` +/// +/// # Time complexity +/// +/// | [push] | [pop] | [peek]/[peek\_mut] | +/// |--------|----------|--------------------| +/// | O(1)~ | O(log n) | O(1) | +/// +/// The value for `push` is an expected cost; the method documentation gives a +/// more detailed analysis. +/// +/// [push]: #method.push +/// [pop]: #method.pop +/// [peek]: #method.peek +/// [peek\_mut]: #method.peek_mut #[stable(feature = "rust1", since = "1.0.0")] pub struct BinaryHeap { data: Vec, @@ -384,6 +398,10 @@ impl BinaryHeap { /// } /// assert_eq!(heap.peek(), Some(&2)); /// ``` + /// + /// # Time complexity + /// + /// Cost is O(1) in the worst case. #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub fn peek_mut(&mut self) -> Option> { if self.is_empty() { @@ -411,6 +429,11 @@ impl BinaryHeap { /// assert_eq!(heap.pop(), Some(1)); /// assert_eq!(heap.pop(), None); /// ``` + /// + /// # Time complexity + /// + /// The worst case cost of `pop` on a heap containing *n* elements is O(log + /// n). #[stable(feature = "rust1", since = "1.0.0")] pub fn pop(&mut self) -> Option { self.data.pop().map(|mut item| { @@ -438,6 +461,22 @@ impl BinaryHeap { /// assert_eq!(heap.len(), 3); /// assert_eq!(heap.peek(), Some(&5)); /// ``` + /// + /// # Time complexity + /// + /// The expected cost of `push`, averaged over every possible ordering of + /// the elements being pushed, and over a sufficiently large number of + /// pushes, is O(1). This is the most meaningful cost metric when pushing + /// elements that are *not* already in any sorted pattern. + /// + /// The time complexity degrades if elements are pushed in predominantly + /// ascending order. In the worst case, elements are pushed in ascending + /// sorted order and the amortized cost per push is O(log n) against a heap + /// containing *n* elements. + /// + /// The worst case cost of a *single* call to `push` is O(n). The worst case + /// occurs when capacity is exhausted and needs a resize. The resize cost + /// has been amortized in the previous figures. #[stable(feature = "rust1", since = "1.0.0")] pub fn push(&mut self, item: T) { let old_len = self.len(); @@ -650,6 +689,10 @@ impl BinaryHeap { /// assert_eq!(heap.peek(), Some(&5)); /// /// ``` + /// + /// # Time complexity + /// + /// Cost is O(1) in the worst case. #[stable(feature = "rust1", since = "1.0.0")] pub fn peek(&self) -> Option<&T> { self.data.get(0) -- cgit 1.4.1-3-g733a5