allocated_btree/
compressed.rs

1#![allow(dead_code)]
2
3use allocated::DropGuard;
4use allocated::FromIteratorIn;
5use core::borrow::Borrow;
6use core::mem::ManuallyDrop;
7use core::ops::Add;
8use core::ops::Mul;
9use core::ptr::NonNull;
10
11extern crate alloc;
12use alloc::vec;
13use alloc::vec::Vec;
14
15use allocator_api2::alloc::Allocator;
16use generic_array::ArrayLength;
17use typenum::Prod;
18use typenum::Sum;
19use typenum::U1;
20use typenum::U2;
21use typenum::U6;
22
23use allocated::AllocResult;
24use allocated::DropGuardResult;
25use allocated::DropIn;
26use allocated::IntoIteratorIn;
27use allocated::RecursiveDropIn;
28
29mod entry;
30mod node;
31mod wrapper;
32
33pub use entry::{Entry, OccupiedEntry, VacantEntry};
34use node::{
35    ChildPtr, IntoIter as NodeIntoIter, Iter as NodeIter, LeafNode, MutNodeRef, Node, NodeEntry,
36    NodeRef, NodeRefT, OccupiedNodeEntry,
37};
38pub use wrapper::CompressedBTreeMap;
39
40/// A compressed B-Tree map implementation using the allocated pattern.
41///
42/// This is the low-level "allocated" type that requires manual allocator passing.
43/// For most use cases, prefer the [`CompressedBTreeMap`] wrapper which owns its allocator
44/// and provides a safe, ergonomic API.
45///
46/// This implementation uses ~30% less memory than the naive implementation by using
47/// specialized node types:
48/// - **Leaf nodes**: Store only keys and values (no child pointers)
49/// - **Interior nodes**: Store keys, values, and child pointers
50///
51/// # Type Parameters
52///
53/// - `K`: Key type, must be `PartialOrd + Debug`
54/// - `V`: Value type
55/// - `B`: Branching factor (defaults to `U6` for 6-way tree). Controls the number
56///   of keys per node (2*B keys maximum).
57///
58/// # Examples
59///
60/// ```
61/// use allocated_btree::AllocatedCompressedBTreeMap;
62/// use allocated::CountingAllocator;
63///
64/// let alloc = CountingAllocator::default();
65/// let mut map = AllocatedCompressedBTreeMap::<u32, String>::new_in(&alloc)?;
66///
67/// unsafe {
68///     map.insert_in(&alloc, 1, "one".to_string())?;
69///     map.insert_in(&alloc, 2, "two".to_string())?;
70/// }
71///
72/// assert_eq!(map.len(), 2);
73/// # Ok::<(), allocated::AllocErrorWithLayout>(())
74/// ```
75pub struct AllocatedBTreeMap<K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength = U6>
76where
77    U2: Mul<B>,
78    Prod<U2, B>: ArrayLength,
79    U1: Add<Prod<U2, B>>,
80    Sum<U1, Prod<U2, B>>: ArrayLength,
81{
82    root: Option<ManuallyDrop<Node<K, V, B>>>,
83    n: usize,
84}
85
86impl<K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength> AllocatedBTreeMap<K, V, B>
87where
88    U2: Mul<B>,
89    Prod<U2, B>: ArrayLength,
90    U1: Add<Prod<U2, B>>,
91    Sum<U1, Prod<U2, B>>: ArrayLength,
92{
93    fn root_node_ref(&self) -> NodeRef<'_, K, V, B> {
94        self.root.as_ref().unwrap().as_ref()
95    }
96
97    fn root_mut_node_ref(&mut self) -> MutNodeRef<'_, K, V, B> {
98        self.root.as_mut().unwrap().as_mut()
99    }
100}
101
102impl<K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength> AllocatedBTreeMap<K, V, B>
103where
104    U2: Mul<B>,
105    Prod<U2, B>: ArrayLength,
106    U1: Add<Prod<U2, B>>,
107    Sum<U1, Prod<U2, B>>: ArrayLength,
108{
109    /// # Errors
110    ///
111    /// Will return `Err` if the allocation fails.
112    pub fn new_in<A: Allocator>(alloc: &A) -> DropGuardResult<Self, &A> {
113        Ok(LeafNode::new_in(alloc).map(|root| AllocatedBTreeMap {
114            root: Some(ManuallyDrop::new(Node::Leaf(root))),
115            n: 0,
116        }))
117    }
118
119    /// Returns `true` if the map contains no elements.
120    pub fn is_empty(&self) -> bool {
121        self.n == 0
122    }
123
124    /// Returns the number of elements in the map.
125    pub fn len(&self) -> usize {
126        self.n
127    }
128
129    /// Returns `true` if the map contains a value for the specified key.
130    pub fn contains_key<Q>(&self, key: &Q) -> bool
131    where
132        K: Borrow<Q> + core::cmp::PartialOrd + core::fmt::Debug,
133        Q: core::cmp::PartialOrd + core::fmt::Debug,
134    {
135        let root = self.root_node_ref();
136        match root.ref_entry(key, vec![]) {
137            NodeEntry::Vacant(_) => false,
138            NodeEntry::Occupied(_) => true,
139        }
140    }
141
142    /// Inserts a key-value pair into the map.
143    ///
144    /// If the map did not have this key present, `None` is returned.
145    /// If the map did have this key present, the value is updated and the old value is returned.
146    ///
147    /// # Safety
148    ///
149    /// `alloc` MUST be the allocator used to allocate this object.
150    ///
151    /// # Errors
152    ///
153    /// Will return `Err` if the allocation fails.
154    pub unsafe fn insert_in<A: Allocator>(
155        &mut self,
156        alloc: &A,
157        key: K,
158        value: V,
159    ) -> AllocResult<Option<V>> {
160        // SAFETY: Caller guarantees `alloc` is the allocator used for this tree
161        let entry = unsafe { self.entry_in(alloc, key) };
162        entry.insert(value)
163    }
164
165    /// Clears the map, removing all elements.
166    ///
167    /// # Safety
168    ///
169    /// `alloc` MUST be the allocator used to allocate this object.
170    ///
171    /// # Errors
172    ///
173    /// Will return `Err` if the allocation fails.
174    pub unsafe fn clear_in<A: Allocator>(&mut self, alloc: &A) -> AllocResult<()> {
175        if let Some(mut r) = self.root.take() {
176            // SAFETY: Caller guarantees `alloc` is the allocator used for this tree
177            unsafe { r.drop_in(alloc) };
178        }
179        self.n = 0;
180        self.root = Some(LeafNode::new_in(alloc).map(|n| Node::Leaf(n)).into_inner());
181        Ok(())
182    }
183
184    /// Returns a reference to the value corresponding to the key.
185    pub fn get<'s, Q>(&'s self, key: &Q) -> Option<&'s V>
186    where
187        K: Borrow<Q> + core::cmp::PartialOrd,
188        Q: core::cmp::PartialOrd + core::fmt::Debug,
189    {
190        let root = self.root_node_ref();
191        match root.ref_entry(key, vec![]) {
192            NodeEntry::Vacant(_) => None,
193            NodeEntry::Occupied(o) => Some(o.into_value()),
194        }
195    }
196
197    /// Returns the key-value pair corresponding to the supplied key.
198    pub fn get_key_value<'s, Q>(&'s self, key: &'s Q) -> Option<(&'s K, &'s V)>
199    where
200        K: Borrow<Q> + core::cmp::PartialOrd,
201        Q: core::cmp::PartialOrd + core::fmt::Debug,
202    {
203        let root = self.root_node_ref();
204        match root.ref_entry(key, vec![]) {
205            NodeEntry::Vacant(_) => None,
206            NodeEntry::Occupied(o) => Some(o.into_key_value()),
207        }
208    }
209
210    /// Returns a mutable reference to the value corresponding to the key.
211    pub fn get_mut<'s, Q>(&'s mut self, key: &'s Q) -> Option<&'s mut V>
212    where
213        K: Borrow<Q> + core::cmp::PartialOrd,
214        Q: core::cmp::PartialOrd + core::fmt::Debug,
215    {
216        let root = self.root_mut_node_ref();
217        match root.ref_entry(key, vec![]) {
218            NodeEntry::Vacant(_) => None,
219            NodeEntry::Occupied(o) => Some(o.into_mut()),
220        }
221    }
222
223    /// Returns an iterator over the key-value pairs of the map, in sorted order by key.
224    pub fn iter(&self) -> Iter<'_, K, V, B> {
225        let mut stack = Vec::new();
226        if self.n > 0 {
227            stack.push((ChildPtr::from_node_ref(self.root_node_ref()), 0));
228        }
229        Iter {
230            inner: NodeIter::<K, V, B, NodeRef<K, V, B>>::new(stack),
231        }
232    }
233
234    /// Returns an iterator over the keys of the map, in sorted order.
235    pub fn keys(&self) -> Keys<'_, K, V, B> {
236        let mut stack = Vec::new();
237        if self.n > 0 {
238            stack.push((ChildPtr::from_node_ref(self.root_node_ref()), 0));
239        }
240        Keys {
241            inner: NodeIter::<K, V, B, NodeRef<K, V, B>>::new(stack),
242        }
243    }
244
245    /// # Safety
246    ///
247    /// `alloc` MUST be the allocator used to allocate this object.
248    unsafe fn into_keys_in<A: Allocator>(self, alloc: &A) -> IntoKeys<'_, K, V, B, A> {
249        IntoKeys {
250            inner: NodeIntoIter::new(alloc, ManuallyDrop::into_inner(self.root.unwrap())),
251        }
252    }
253
254    /// Returns an iterator over the values of the map, in order by key.
255    pub fn values(&self) -> Values<'_, K, V, B> {
256        let mut stack = Vec::new();
257        if self.n > 0 {
258            stack.push((ChildPtr::from_node_ref(self.root_node_ref()), 0));
259        }
260        Values {
261            inner: NodeIter::<K, V, B, NodeRef<K, V, B>>::new(stack),
262        }
263    }
264
265    /// Returns a mutable iterator over the values of the map, in order by key.
266    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, B> {
267        let mut stack = Vec::new();
268        if self.n > 0 {
269            stack.push((
270                ChildPtr::from_mut_node_ref(&mut self.root_mut_node_ref()),
271                0,
272            ));
273        }
274        ValuesMut {
275            inner: NodeIter::<K, V, B, MutNodeRef<K, V, B>>::new(stack),
276        }
277    }
278
279    /// # Safety
280    ///
281    /// `alloc` MUST be the allocator used to allocate this object.
282    unsafe fn into_values_in<A: Allocator>(self, alloc: &A) -> IntoValues<'_, K, V, B, A> {
283        IntoValues {
284            inner: NodeIntoIter::new(alloc, ManuallyDrop::into_inner(self.root.unwrap())),
285        }
286    }
287
288    /// # Safety
289    ///
290    /// `alloc` MUST be the allocator used to allocate this object.
291    pub unsafe fn entry_in<'a, 's, A: Allocator>(
292        &'s mut self,
293        alloc: &'a A,
294        key: K,
295    ) -> Entry<'a, 's, A, K, V, B> {
296        let map: NonNull<AllocatedBTreeMap<K, V, B>> = NonNull::from_mut(self);
297        let node_ref: MutNodeRef<'s, K, V, B> = self.root_mut_node_ref();
298        // SAFETY: We have exclusive mutable access to self and are creating a NodeEntry
299        let inner_entry: NodeEntry<'s, K, K, V, B, MutNodeRef<'s, K, V, B>> =
300            unsafe { node_ref.entry_in(key, vec![]) };
301        Entry::new(alloc, inner_entry, map)
302    }
303
304    /// # Safety
305    ///
306    /// `alloc` MUST be the allocator used to allocate this object.
307    pub unsafe fn first_entry_in<'a, 's, A: Allocator>(
308        &'s mut self,
309        alloc: &'a A,
310    ) -> Option<OccupiedEntry<'a, 's, A, K, V, B>> {
311        if self.n == 0 {
312            return None;
313        }
314
315        let map = NonNull::new(self)?;
316        let root = self.root_mut_node_ref();
317        let inner_entry: OccupiedNodeEntry<'s, K, V, B, MutNodeRef<'s, K, V, B>> =
318            root.first_entry_in(vec![]);
319        // SAFETY: Requirements match function requirements
320        unsafe { Some(OccupiedEntry::new(alloc, inner_entry, map)) }
321    }
322
323    /// Returns a reference to the first key-value pair in the map.
324    /// The key in this pair is the minimum key in the map.
325    pub fn first_key_value<'s>(&'s self) -> Option<(&'s K, &'s V)> {
326        if self.n == 0 {
327            return None;
328        }
329
330        let root = self.root_node_ref();
331        let inner_entry: OccupiedNodeEntry<'s, K, V, B, NodeRef<'s, K, V, B>> =
332            root.first_entry_in(vec![]);
333        Some(inner_entry.into_key_value())
334    }
335
336    /// # Safety
337    ///
338    /// `alloc` MUST be the allocator used to allocate this object.
339    pub unsafe fn last_entry_in<'a, 's, A: Allocator>(
340        &'s mut self,
341        alloc: &'a A,
342    ) -> Option<OccupiedEntry<'a, 's, A, K, V, B>> {
343        if self.n == 0 {
344            return None;
345        }
346
347        let map = NonNull::new(self)?;
348        let root = self.root_mut_node_ref();
349        let inner_entry: OccupiedNodeEntry<'s, K, V, B, MutNodeRef<'s, K, V, B>> =
350            root.last_entry_in(vec![]);
351        // SAFETY: Requirements match function requirements
352        unsafe { Some(OccupiedEntry::new(alloc, inner_entry, map)) }
353    }
354
355    /// Returns a reference to the last key-value pair in the map.
356    /// The key in this pair is the maximum key in the map.
357    pub fn last_key_value<'s>(&'s self) -> Option<(&'s K, &'s V)> {
358        if self.n == 0 {
359            return None;
360        }
361
362        let root = self.root_node_ref();
363        let inner_entry: OccupiedNodeEntry<'s, K, V, B, NodeRef<'s, K, V, B>> =
364            root.last_entry_in(vec![]);
365        Some(inner_entry.into_key_value())
366    }
367
368    /// Returns a reference to the first key in the map.
369    /// This is the minimum key in the map.
370    pub fn first(&self) -> Option<&K> {
371        self.first_key_value().map(|(k, _)| k)
372    }
373
374    /// Returns a reference to the last key in the map.
375    /// This is the maximum key in the map.
376    pub fn last(&self) -> Option<&K> {
377        self.last_key_value().map(|(k, _)| k)
378    }
379
380    /// Gets the given key's corresponding occupied entry in the map for in-place manipulation.
381    ///
382    /// Returns `None` if the key is not present in the map.
383    ///
384    /// The key may be any borrowed form of the map's key type, but the ordering
385    /// on the borrowed form *must* match the ordering on the key type.
386    ///
387    /// # Safety
388    ///
389    /// `alloc` MUST be the allocator used to allocate this object.
390    ///
391    /// # Examples
392    ///
393    /// ```
394    /// use allocated_btree::AllocatedCompressedBTreeMap;
395    /// use allocated::CountingAllocator;
396    ///
397    /// let alloc = CountingAllocator::default();
398    /// let mut map = AllocatedCompressedBTreeMap::<u32, String>::new_in(&alloc)?;
399    ///
400    /// unsafe {
401    ///     map.insert_in(&alloc, 1, "a".to_string())?;
402    ///
403    ///     // Get the entry if it exists
404    ///     if let Some(entry) = map.entry_ref_in(&alloc, &1) {
405    ///         assert_eq!(entry.key(), &1);
406    ///     }
407    ///
408    ///     // Non-existent key returns None
409    ///     assert!(map.entry_ref_in(&alloc, &2).is_none());
410    /// }
411    /// # Ok::<(), allocated::AllocErrorWithLayout>(())
412    /// ```
413    pub unsafe fn entry_ref_in<'a, 's, A: Allocator, Q>(
414        &'s mut self,
415        alloc: &'a A,
416        key: &Q,
417    ) -> Option<OccupiedEntry<'a, 's, A, K, V, B>>
418    where
419        K: Borrow<Q>,
420        Q: PartialOrd + core::fmt::Debug + ?Sized,
421    {
422        let map = NonNull::from_mut(self);
423        let root = self.root_mut_node_ref();
424
425        match root.ref_entry(key, vec![]) {
426            NodeEntry::Vacant(_) => None,
427            NodeEntry::Occupied(inner) => {
428                // SAFETY: Caller guarantees `alloc` is the allocator used for this tree
429                Some(unsafe { OccupiedEntry::new(alloc, inner, map) })
430            }
431        }
432    }
433
434    /// Removes a key from the map, returning the value at the key if the key
435    /// was previously in the map.
436    ///
437    /// The key may be any borrowed form of the map's key type, but the ordering
438    /// on the borrowed form *must* match the ordering on the key type.
439    ///
440    /// # Safety
441    ///
442    /// `alloc` MUST be the allocator used to allocate this object.
443    ///
444    /// # Examples
445    ///
446    /// ```
447    /// use allocated_btree::AllocatedCompressedBTreeMap;
448    /// use allocated::CountingAllocator;
449    ///
450    /// let alloc = CountingAllocator::default();
451    /// let mut map = AllocatedCompressedBTreeMap::<u32, String>::new_in(&alloc)?;
452    ///
453    /// unsafe {
454    ///     map.insert_in(&alloc, 1, "a".to_string())?;
455    ///     assert_eq!(map.remove_in(&alloc, &1), Some("a".to_string()));
456    ///     assert_eq!(map.remove_in(&alloc, &1), None);
457    /// }
458    /// # Ok::<(), allocated::AllocErrorWithLayout>(())
459    /// ```
460    pub unsafe fn remove_in<A: Allocator, Q>(&mut self, alloc: &A, key: &Q) -> Option<V>
461    where
462        K: Borrow<Q>,
463        Q: PartialOrd + core::fmt::Debug + ?Sized,
464    {
465        // SAFETY: Caller guarantees `alloc` is the allocator used for this tree
466        unsafe { self.remove_entry_in(alloc, key).map(|(_, v)| v) }
467    }
468
469    /// Removes a key from the map, returning the stored key and value if the key
470    /// was previously in the map.
471    ///
472    /// The key may be any borrowed form of the map's key type, but the ordering
473    /// on the borrowed form *must* match the ordering on the key type.
474    ///
475    /// # Safety
476    ///
477    /// `alloc` MUST be the allocator used to allocate this object.
478    ///
479    /// # Examples
480    ///
481    /// ```
482    /// use allocated_btree::AllocatedCompressedBTreeMap;
483    /// use allocated::CountingAllocator;
484    ///
485    /// let alloc = CountingAllocator::default();
486    /// let mut map = AllocatedCompressedBTreeMap::<u32, String>::new_in(&alloc)?;
487    ///
488    /// unsafe {
489    ///     map.insert_in(&alloc, 1, "a".to_string())?;
490    ///     assert_eq!(map.remove_entry_in(&alloc, &1), Some((1, "a".to_string())));
491    ///     assert_eq!(map.remove_entry_in(&alloc, &1), None);
492    /// }
493    /// # Ok::<(), allocated::AllocErrorWithLayout>(())
494    /// ```
495    pub unsafe fn remove_entry_in<A: Allocator, Q>(&mut self, alloc: &A, key: &Q) -> Option<(K, V)>
496    where
497        K: Borrow<Q>,
498        Q: PartialOrd + core::fmt::Debug + ?Sized,
499    {
500        // SAFETY: Caller guarantees `alloc` is the allocator used for this tree
501        unsafe {
502            self.entry_ref_in(alloc, key)
503                .map(|entry| entry.remove_entry())
504        }
505    }
506}
507
508// impl<K: core::cmp::PartialOrd + Debug, V: Debug, B: ArrayLength> AllocatedBTreeMap<K, V, B>
509// where
510//     U2: Mul<B>,
511//     Prod<U2, B>: ArrayLength,
512//     U1: Add<Prod<U2, B>>,
513//     Sum<U1, Prod<U2, B>>: ArrayLength,
514// {
515//     fn to_dot(&self) -> Result<String, Box<dyn Error>> {
516//         let mut data = Vec::default();
517
518//         data.write_all(b"digraph G {\n")?;
519//         data.write_all(b"rankdir=\"LR\";\n")?;
520//         self.root.as_ref().unwrap().to_dot(&mut data)?;
521//         data.write_all(b"}\n")?;
522
523//         Ok(String::from_utf8(data)?)
524//     }
525// }
526
527impl<'a, K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength, A: Allocator>
528    FromIteratorIn<'a, (K, V), A> for AllocatedBTreeMap<K, V, B>
529where
530    U2: Mul<B>,
531    Prod<U2, B>: ArrayLength,
532    U1: Add<Prod<U2, B>>,
533    Sum<U1, Prod<U2, B>>: ArrayLength,
534{
535    fn from_iter_in<T>(alloc: &'a A, iter: T) -> DropGuardResult<Self, &'a A>
536    where
537        T: IntoIterator<Item = (K, V)>,
538    {
539        let mut btree: DropGuard<Self, &'a A> = Self::new_in(alloc)?;
540
541        for (k, v) in iter {
542            // SAFETY: alloc is the same allocator used to create btree.
543            unsafe {
544                btree.insert_in(alloc, k, v)?;
545            }
546        }
547
548        Ok(btree)
549    }
550}
551
552impl<K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength> DropIn
553    for AllocatedBTreeMap<K, V, B>
554where
555    U2: Mul<B>,
556    Prod<U2, B>: ArrayLength,
557    U1: Add<Prod<U2, B>>,
558    Sum<U1, Prod<U2, B>>: ArrayLength,
559{
560    /// # Safety
561    ///
562    /// `alloc` must be the allocator used to allocate this object.
563    unsafe fn drop_in<A: Allocator>(&mut self, alloc: &A) {
564        // SAFETY: requirements match function requirements
565        unsafe {
566            if let Some(r) = self.root.as_mut() {
567                r.drop_in(alloc);
568            }
569        }
570    }
571}
572
573impl<K, V, B> RecursiveDropIn for AllocatedBTreeMap<K, V, B>
574where
575    K: core::cmp::PartialOrd + core::fmt::Debug + DropIn,
576    V: DropIn,
577    B: ArrayLength,
578    U2: Mul<B>,
579    Prod<U2, B>: ArrayLength,
580    U1: Add<Prod<U2, B>>,
581    Sum<U1, Prod<U2, B>>: ArrayLength,
582{
583    /// # Safety
584    ///
585    /// `alloc` must be the allocator used to allocate this object.
586    unsafe fn recursive_drop_in<A: Allocator>(&mut self, alloc: &A) {
587        if let Some(root) = self.root.as_mut() {
588            // SAFETY: We're taking ownership of the root to iterate over it.
589            let root_owned = unsafe { ManuallyDrop::take(root) };
590            // Recursively drop all keys and values in the tree
591            for (mut k, mut v) in NodeIntoIter::new(alloc, root_owned) {
592                // SAFETY: alloc is the same allocator used for the B-tree.
593                unsafe { k.drop_in(alloc) };
594                // SAFETY: alloc is the same allocator used for the B-tree.
595                unsafe { v.drop_in(alloc) };
596            }
597        }
598        // SAFETY: alloc is the same allocator used for the B-tree. The tree structure itself is dropped.
599        unsafe { self.drop_in(alloc) };
600    }
601}
602
603impl<'a, K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength, A: Allocator + 'a>
604    IntoIteratorIn<'a, A> for AllocatedBTreeMap<K, V, B>
605where
606    U2: Mul<B>,
607    Prod<U2, B>: ArrayLength,
608    U1: Add<Prod<U2, B>>,
609    Sum<U1, Prod<U2, B>>: ArrayLength,
610{
611    type Item = (K, V);
612    type IntoIter = IntoIter<'a, K, V, B, A>;
613
614    unsafe fn into_iter_in(self, alloc: &'a A) -> Self::IntoIter {
615        IntoIter {
616            inner: NodeIntoIter::new(alloc, ManuallyDrop::into_inner(self.root.unwrap())),
617        }
618    }
619}
620
621impl<'s, K: core::cmp::PartialOrd + core::fmt::Debug, V, B: ArrayLength> IntoIterator
622    for &'s AllocatedBTreeMap<K, V, B>
623where
624    U2: Mul<B>,
625    Prod<U2, B>: ArrayLength,
626    U1: Add<Prod<U2, B>>,
627    Sum<U1, Prod<U2, B>>: ArrayLength,
628{
629    type IntoIter = Iter<'s, K, V, B>;
630    type Item = (&'s K, &'s V);
631
632    fn into_iter(self) -> Self::IntoIter {
633        self.iter()
634    }
635}
636
637mod iters;
638#[cfg(test)]
639mod tests;
640
641pub use iters::{IntoIter, IntoKeys, IntoValues, Iter, Keys, Values, ValuesMut};
allocated_btree/compressed.rs

allocated_btree/
compressed.rs
