/
map.rs
1617 lines (1483 loc) · 62.7 KB
/
map.rs
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
// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
// This implementation is largely based on the high-level description and analysis of B-Trees
// found in *Open Data Structures* (ODS). Although our implementation does not use any of
// the source found in ODS, if one wishes to review the high-level design of this structure, it
// can be freely downloaded at http://opendatastructures.org/. Its contents are as of this
// writing (August 2014) freely licensed under the following Creative Commons Attribution
// License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/).
use self::Entry::*;
use core::prelude::*;
use core::cmp::Ordering;
use core::default::Default;
use core::fmt::Debug;
use core::hash::{Hash, Hasher};
use core::iter::{Map, FromIterator, IntoIterator};
use core::ops::Index;
use core::{iter, fmt, mem, usize};
use Bound::{self, Included, Excluded, Unbounded};
use borrow::Borrow;
use vec_deque::VecDeque;
use self::Continuation::{Continue, Finished};
use self::StackOp::*;
use super::node::ForceResult::{Leaf, Internal};
use super::node::TraversalItem::{self, Elem, Edge};
use super::node::{Traversal, MutTraversal, MoveTraversal};
use super::node::{self, Node, Found, GoDown};
/// A map based on a B-Tree.
///
/// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
/// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
/// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
/// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
/// is done is *very* inefficient for modern computer architectures. In particular, every element
/// is stored in its own individually heap-allocated node. This means that every single insertion
/// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
/// are both notably expensive things to do in practice, we are forced to at very least reconsider
/// the BST strategy.
///
/// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
/// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
/// searches. However, this does mean that searches will have to do *more* comparisons on average.
/// The precise number of comparisons depends on the node search strategy used. For optimal cache
/// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
/// the node using binary search. As a compromise, one could also perform a linear search
/// that initially only checks every i<sup>th</sup> element for some choice of i.
///
/// Currently, our implementation simply performs naive linear search. This provides excellent
/// performance on *small* nodes of elements which are cheap to compare. However in the future we
/// would like to further explore choosing the optimal search strategy based on the choice of B,
/// and possibly other factors. Using linear search, searching for a random element is expected
/// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
/// however, performance is excellent.
///
/// It is a logic error for a key to be modified in such a way that the key's ordering relative to
/// any other key, as determined by the `Ord` trait, changes while it is in the map. This is
/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct BTreeMap<K, V> {
root: Node<K, V>,
length: usize,
depth: usize,
b: usize,
}
/// An abstract base over-which all other BTree iterators are built.
#[derive(Clone)]
struct AbsIter<T> {
traversals: VecDeque<T>,
size: usize,
}
/// An iterator over a BTreeMap's entries.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Iter<'a, K: 'a, V: 'a> {
inner: AbsIter<Traversal<'a, K, V>>
}
/// A mutable iterator over a BTreeMap's entries.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IterMut<'a, K: 'a, V: 'a> {
inner: AbsIter<MutTraversal<'a, K, V>>
}
/// An owning iterator over a BTreeMap's entries.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<K, V> {
inner: AbsIter<MoveTraversal<K, V>>
}
/// An iterator over a BTreeMap's keys.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Keys<'a, K: 'a, V: 'a> {
inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a K>
}
/// An iterator over a BTreeMap's values.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Values<'a, K: 'a, V: 'a> {
inner: Map<Iter<'a, K, V>, fn((&'a K, &'a V)) -> &'a V>
}
/// An iterator over a sub-range of BTreeMap's entries.
pub struct Range<'a, K: 'a, V: 'a> {
inner: AbsIter<Traversal<'a, K, V>>
}
/// A mutable iterator over a sub-range of BTreeMap's entries.
pub struct RangeMut<'a, K: 'a, V: 'a> {
inner: AbsIter<MutTraversal<'a, K, V>>
}
/// A view into a single entry in a map, which may either be vacant or occupied.
#[stable(feature = "rust1", since = "1.0.0")]
pub enum Entry<'a, K:'a, V:'a> {
/// A vacant Entry
#[stable(feature = "rust1", since = "1.0.0")]
Vacant(VacantEntry<'a, K, V>),
/// An occupied Entry
#[stable(feature = "rust1", since = "1.0.0")]
Occupied(OccupiedEntry<'a, K, V>),
}
/// A vacant Entry.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct VacantEntry<'a, K:'a, V:'a> {
key: K,
stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>,
}
/// An occupied Entry.
#[stable(feature = "rust1", since = "1.0.0")]
pub struct OccupiedEntry<'a, K:'a, V:'a> {
stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>,
}
impl<K: Ord, V> BTreeMap<K, V> {
/// Makes a new empty BTreeMap with a reasonable choice for B.
#[stable(feature = "rust1", since = "1.0.0")]
pub fn new() -> BTreeMap<K, V> {
//FIXME(Gankro): Tune this as a function of size_of<K/V>?
BTreeMap::with_b(6)
}
/// Makes a new empty BTreeMap with the given B.
///
/// B cannot be less than 2.
pub fn with_b(b: usize) -> BTreeMap<K, V> {
assert!(b > 1, "B must be greater than 1");
BTreeMap {
length: 0,
depth: 1,
root: Node::make_leaf_root(b),
b: b,
}
}
/// Clears the map, removing all values.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut a = BTreeMap::new();
/// a.insert(1, "a");
/// a.clear();
/// assert!(a.is_empty());
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn clear(&mut self) {
let b = self.b;
// avoid recursive destructors by manually traversing the tree
for _ in mem::replace(self, BTreeMap::with_b(b)) {};
}
// Searching in a B-Tree is pretty straightforward.
//
// Start at the root. Try to find the key in the current node. If we find it, return it.
// If it's not in there, follow the edge *before* the smallest key larger than
// the search key. If no such key exists (they're *all* smaller), then just take the last
// edge in the node. If we're in a leaf and we don't find our key, then it's not
// in the tree.
/// Returns a reference to the value corresponding to the key.
///
/// The key may be any borrowed form of the map's key type, but the ordering
/// on the borrowed form *must* match the ordering on the key type.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
/// map.insert(1, "a");
/// assert_eq!(map.get(&1), Some(&"a"));
/// assert_eq!(map.get(&2), None);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord {
let mut cur_node = &self.root;
loop {
match Node::search(cur_node, key) {
Found(handle) => return Some(handle.into_kv().1),
GoDown(handle) => match handle.force() {
Leaf(_) => return None,
Internal(internal_handle) => {
cur_node = internal_handle.into_edge();
continue;
}
}
}
}
}
/// Returns true if the map contains a value for the specified key.
///
/// The key may be any borrowed form of the map's key type, but the ordering
/// on the borrowed form *must* match the ordering on the key type.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
/// map.insert(1, "a");
/// assert_eq!(map.contains_key(&1), true);
/// assert_eq!(map.contains_key(&2), false);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord {
self.get(key).is_some()
}
/// Returns a mutable reference to the value corresponding to the key.
///
/// The key may be any borrowed form of the map's key type, but the ordering
/// on the borrowed form *must* match the ordering on the key type.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
/// map.insert(1, "a");
/// match map.get_mut(&1) {
/// Some(x) => *x = "b",
/// None => (),
/// }
/// assert_eq!(map[&1], "b");
/// ```
// See `get` for implementation notes, this is basically a copy-paste with mut's added
#[stable(feature = "rust1", since = "1.0.0")]
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord {
// temp_node is a Borrowck hack for having a mutable value outlive a loop iteration
let mut temp_node = &mut self.root;
loop {
let cur_node = temp_node;
match Node::search(cur_node, key) {
Found(handle) => return Some(handle.into_kv_mut().1),
GoDown(handle) => match handle.force() {
Leaf(_) => return None,
Internal(internal_handle) => {
temp_node = internal_handle.into_edge_mut();
continue;
}
}
}
}
}
// Insertion in a B-Tree is a bit complicated.
//
// First we do the same kind of search described in `find`. But we need to maintain a stack of
// all the nodes/edges in our search path. If we find a match for the key we're trying to
// insert, just swap the vals and return the old ones. However, when we bottom out in a leaf,
// we attempt to insert our key-value pair at the same location we would want to follow another
// edge.
//
// If the node has room, then this is done in the obvious way by shifting elements. However,
// if the node itself is full, we split node into two, and give its median key-value
// pair to its parent to insert the new node with. Of course, the parent may also be
// full, and insertion can propagate until we reach the root. If we reach the root, and
// it is *also* full, then we split the root and place the two nodes under a newly made root.
//
// Note that we subtly deviate from Open Data Structures in our implementation of split.
// ODS describes inserting into the node *regardless* of its capacity, and then
// splitting *afterwards* if it happens to be overfull. However, this is inefficient.
// Instead, we split beforehand, and then insert the key-value pair into the appropriate
// result node. This has two consequences:
//
// 1) While ODS produces a left node of size B-1, and a right node of size B,
// we may potentially reverse this. However, this shouldn't effect the analysis.
//
// 2) While ODS may potentially return the pair we *just* inserted after
// the split, we will never do this. Again, this shouldn't effect the analysis.
/// Inserts a key-value pair from the map. If the key already had a value
/// present in the map, that value is returned. Otherwise, `None` is returned.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
/// assert_eq!(map.insert(37, "a"), None);
/// assert_eq!(map.is_empty(), false);
///
/// map.insert(37, "b");
/// assert_eq!(map.insert(37, "c"), Some("b"));
/// assert_eq!(map[&37], "c");
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn insert(&mut self, mut key: K, mut value: V) -> Option<V> {
// This is a stack of rawptrs to nodes paired with indices, respectively
// representing the nodes and edges of our search path. We have to store rawptrs
// because as far as Rust is concerned, we can mutate aliased data with such a
// stack. It is of course correct, but what it doesn't know is that we will only
// be popping and using these ptrs one at a time in child-to-parent order. The alternative
// to doing this is to take the Nodes from their parents. This actually makes
// borrowck *really* happy and everything is pretty smooth. However, this creates
// *tons* of pointless writes, and requires us to always walk all the way back to
// the root after an insertion, even if we only needed to change a leaf. Therefore,
// we accept this potential unsafety and complexity in the name of performance.
//
// Regardless, the actual dangerous logic is completely abstracted away from BTreeMap
// by the stack module. All it can do is immutably read nodes, and ask the search stack
// to proceed down some edge by index. This makes the search logic we'll be reusing in a
// few different methods much neater, and of course drastically improves safety.
let mut stack = stack::PartialSearchStack::new(self);
loop {
let result = stack.with(move |pusher, node| {
// Same basic logic as found in `find`, but with PartialSearchStack mediating the
// actual nodes for us
match Node::search(node, &key) {
Found(mut handle) => {
// Perfect match, swap the values and return the old one
mem::swap(handle.val_mut(), &mut value);
Finished(Some(value))
},
GoDown(handle) => {
// We need to keep searching, try to get the search stack
// to go down further
match handle.force() {
Leaf(leaf_handle) => {
// We've reached a leaf, perform the insertion here
pusher.seal(leaf_handle).insert(key, value);
Finished(None)
}
Internal(internal_handle) => {
// We've found the subtree to insert this key/value pair in,
// keep searching
Continue((pusher.push(internal_handle), key, value))
}
}
}
}
});
match result {
Finished(ret) => return ret,
Continue((new_stack, renewed_key, renewed_val)) => {
stack = new_stack;
key = renewed_key;
value = renewed_val;
}
}
}
}
// Deletion is the most complicated operation for a B-Tree.
//
// First we do the same kind of search described in
// `find`. But we need to maintain a stack of all the nodes/edges in our search path.
// If we don't find the key, then we just return `None` and do nothing. If we do find the
// key, we perform two operations: remove the item, and then possibly handle underflow.
//
// # removing the item
// If the node is a leaf, we just remove the item, and shift
// any items after it back to fill the hole.
//
// If the node is an internal node, we *swap* the item with the smallest item in
// in its right subtree (which must reside in a leaf), and then revert to the leaf
// case
//
// # handling underflow
// After removing an item, there may be too few items in the node. We want nodes
// to be mostly full for efficiency, although we make an exception for the root, which
// may have as few as one item. If this is the case, we may first try to steal
// an item from our left or right neighbour.
//
// To steal from the left (right) neighbour,
// we take the largest (smallest) item and child from it. We then swap the taken item
// with the item in their mutual parent that separates them, and then insert the
// parent's item and the taken child into the first (last) index of the underflowed node.
//
// However, stealing has the possibility of underflowing our neighbour. If this is the
// case, we instead *merge* with our neighbour. This of course reduces the number of
// children in the parent. Therefore, we also steal the item that separates the now
// merged nodes, and insert it into the merged node.
//
// Merging may cause the parent to underflow. If this is the case, then we must repeat
// the underflow handling process on the parent. If merging merges the last two children
// of the root, then we replace the root with the merged node.
/// Removes a key from the map, returning the value at the key if the key
/// was previously in the map.
///
/// The key may be any borrowed form of the map's key type, but the ordering
/// on the borrowed form *must* match the ordering on the key type.
///
/// # Examples
///
/// ```
/// use std::collections::BTreeMap;
///
/// let mut map = BTreeMap::new();
/// map.insert(1, "a");
/// assert_eq!(map.remove(&1), Some("a"));
/// assert_eq!(map.remove(&1), None);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord {
// See `swap` for a more thorough description of the stuff going on in here
let mut stack = stack::PartialSearchStack::new(self);
loop {
let result = stack.with(move |pusher, node| {
match Node::search(node, key) {
Found(handle) => {
// Perfect match. Terminate the stack here, and remove the entry
Finished(Some(pusher.seal(handle).remove()))
},
GoDown(handle) => {
// We need to keep searching, try to go down the next edge
match handle.force() {
// We're at a leaf; the key isn't in here
Leaf(_) => Finished(None),
Internal(internal_handle) => Continue(pusher.push(internal_handle))
}
}
}
});
match result {
Finished(ret) => return ret,
Continue(new_stack) => stack = new_stack
}
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K, V> IntoIterator for BTreeMap<K, V> {
type Item = (K, V);
type IntoIter = IntoIter<K, V>;
fn into_iter(self) -> IntoIter<K, V> {
self.into_iter()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
fn into_iter(mut self) -> IterMut<'a, K, V> {
self.iter_mut()
}
}
/// A helper enum useful for deciding whether to continue a loop since we can't
/// return from a closure
enum Continuation<A, B> {
Continue(A),
Finished(B)
}
/// The stack module provides a safe interface for constructing and manipulating a stack of ptrs
/// to nodes. By using this module much better safety guarantees can be made, and more search
/// boilerplate gets cut out.
mod stack {
use core::prelude::*;
use core::marker;
use core::mem;
use core::ops::{Deref, DerefMut};
use super::BTreeMap;
use super::super::node::{self, Node, Fit, Split, Internal, Leaf};
use super::super::node::handle;
use vec::Vec;
struct InvariantLifetime<'id>(
marker::PhantomData<::core::cell::Cell<&'id ()>>);
impl<'id> InvariantLifetime<'id> {
fn new() -> InvariantLifetime<'id> {
InvariantLifetime(marker::PhantomData)
}
}
/// A generic mutable reference, identical to `&mut` except for the fact that its lifetime
/// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef`
/// with the exact requested lifetime can be used. This is in contrast to normal references,
/// where `&'static` can be used in any function expecting any lifetime reference.
pub struct IdRef<'id, T: 'id> {
inner: &'id mut T,
_marker: InvariantLifetime<'id>,
}
impl<'id, T> Deref for IdRef<'id, T> {
type Target = T;
fn deref(&self) -> &T {
&*self.inner
}
}
impl<'id, T> DerefMut for IdRef<'id, T> {
fn deref_mut(&mut self) -> &mut T {
&mut *self.inner
}
}
type StackItem<K, V> = node::Handle<*mut Node<K, V>, handle::Edge, handle::Internal>;
type Stack<K, V> = Vec<StackItem<K, V>>;
/// A `PartialSearchStack` handles the construction of a search stack.
pub struct PartialSearchStack<'a, K:'a, V:'a> {
map: &'a mut BTreeMap<K, V>,
stack: Stack<K, V>,
next: *mut Node<K, V>,
}
/// A `SearchStack` represents a full path to an element or an edge of interest. It provides
/// methods depending on the type of what the path points to for removing an element, inserting
/// a new element, and manipulating to element at the top of the stack.
pub struct SearchStack<'a, K:'a, V:'a, Type, NodeType> {
map: &'a mut BTreeMap<K, V>,
stack: Stack<K, V>,
top: node::Handle<*mut Node<K, V>, Type, NodeType>,
}
/// A `PartialSearchStack` that doesn't hold a a reference to the next node, and is just
/// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with`
/// for more details.
pub struct Pusher<'id, 'a, K:'a, V:'a> {
map: &'a mut BTreeMap<K, V>,
stack: Stack<K, V>,
_marker: InvariantLifetime<'id>,
}
impl<'a, K, V> PartialSearchStack<'a, K, V> {
/// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the
/// root of the tree.
pub fn new(map: &'a mut BTreeMap<K, V>) -> PartialSearchStack<'a, K, V> {
let depth = map.depth;
PartialSearchStack {
next: &mut map.root as *mut _,
map: map,
stack: Vec::with_capacity(depth),
}
}
/// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure
/// to interact with, search, and finally push the `Node` onto the stack. The passed in
/// closure must be polymorphic on the `'id` lifetime parameter, as this statically
/// ensures that only `Handle`s from the correct `Node` can be pushed.
///
/// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept
/// handles with the same `'id`. The closure could only get references with that lifetime
/// through its arguments or through some other `IdRef` that it has lying around. However,
/// no other `IdRef` could possibly work - because the `'id` is held in an invariant
/// parameter, it would need to have precisely the correct lifetime, which would mean that
/// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a
/// specific lifetime instead of the one that `with` chooses to give it.
///
/// See also Haskell's `ST` monad, which uses a similar trick.
pub fn with<T, F: for<'id> FnOnce(Pusher<'id, 'a, K, V>,
IdRef<'id, Node<K, V>>) -> T>(self, closure: F) -> T {
let pusher = Pusher {
map: self.map,
stack: self.stack,
_marker: InvariantLifetime::new(),
};
let node = IdRef {
inner: unsafe { &mut *self.next },
_marker: InvariantLifetime::new(),
};
closure(pusher, node)
}
}
impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> {
/// Pushes the requested child of the stack's current top on top of the stack. If the child
/// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is
/// yielded.
pub fn push(mut self, mut edge: node::Handle<IdRef<'id, Node<K, V>>,
handle::Edge,
handle::Internal>)
-> PartialSearchStack<'a, K, V> {
self.stack.push(edge.as_raw());
PartialSearchStack {
map: self.map,
stack: self.stack,
next: edge.edge_mut() as *mut _,
}
}
/// Converts the PartialSearchStack into a SearchStack.
pub fn seal<Type, NodeType>
(self, mut handle: node::Handle<IdRef<'id, Node<K, V>>, Type, NodeType>)
-> SearchStack<'a, K, V, Type, NodeType> {
SearchStack {
map: self.map,
stack: self.stack,
top: handle.as_raw(),
}
}
}
impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> {
/// Gets a reference to the value the stack points to.
pub fn peek(&self) -> &V {
unsafe { self.top.from_raw().into_kv().1 }
}
/// Gets a mutable reference to the value the stack points to.
pub fn peek_mut(&mut self) -> &mut V {
unsafe { self.top.from_raw_mut().into_kv_mut().1 }
}
/// Converts the stack into a mutable reference to the value it points to, with a lifetime
/// tied to the original tree.
pub fn into_top(mut self) -> &'a mut V {
unsafe {
mem::copy_mut_lifetime(
self.map,
self.top.from_raw_mut().val_mut()
)
}
}
}
impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
/// Removes the key and value in the top element of the stack, then handles underflows as
/// described in BTree's pop function.
fn remove_leaf(mut self) -> V {
self.map.length -= 1;
// Remove the key-value pair from the leaf that this search stack points to.
// Then, note if the leaf is underfull, and promptly forget the leaf and its ptr
// to avoid ownership issues.
let (value, mut underflow) = unsafe {
let (_, value) = self.top.from_raw_mut().remove_as_leaf();
let underflow = self.top.from_raw().node().is_underfull();
(value, underflow)
};
loop {
match self.stack.pop() {
None => {
// We've reached the root, so no matter what, we're done. We manually
// access the root via the tree itself to avoid creating any dangling
// pointers.
if self.map.root.len() == 0 && !self.map.root.is_leaf() {
// We've emptied out the root, so make its only child the new root.
// If it's a leaf, we just let it become empty.
self.map.depth -= 1;
self.map.root.hoist_lone_child();
}
return value;
}
Some(mut handle) => {
if underflow {
// Underflow! Handle it!
unsafe {
handle.from_raw_mut().handle_underflow();
underflow = handle.from_raw().node().is_underfull();
}
} else {
// All done!
return value;
}
}
}
}
}
}
impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> {
/// Removes the key and value in the top element of the stack, then handles underflows as
/// described in BTree's pop function.
pub fn remove(self) -> V {
// Ensure that the search stack goes to a leaf. This is necessary to perform deletion
// in a BTree. Note that this may put the tree in an inconsistent state (further
// described in into_leaf's comments), but this is immediately fixed by the
// removing the value we want to remove
self.into_leaf().remove_leaf()
}
/// Subroutine for removal. Takes a search stack for a key that might terminate at an
/// internal node, and mutates the tree and search stack to *make* it a search stack
/// for that same key that *does* terminates at a leaf. If the mutation occurs, then this
/// leaves the tree in an inconsistent state that must be repaired by the caller by
/// removing the entry in question. Specifically the key-value pair and its successor will
/// become swapped.
fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> {
unsafe {
let mut top_raw = self.top;
let mut top = top_raw.from_raw_mut();
let key_ptr = top.key_mut() as *mut _;
let val_ptr = top.val_mut() as *mut _;
// Try to go into the right subtree of the found key to find its successor
match top.force() {
Leaf(mut leaf_handle) => {
// We're a proper leaf stack, nothing to do
return SearchStack {
map: self.map,
stack: self.stack,
top: leaf_handle.as_raw()
}
}
Internal(mut internal_handle) => {
let mut right_handle = internal_handle.right_edge();
//We're not a proper leaf stack, let's get to work.
self.stack.push(right_handle.as_raw());
let mut temp_node = right_handle.edge_mut();
loop {
// Walk into the smallest subtree of this node
let node = temp_node;
match node.kv_handle(0).force() {
Leaf(mut handle) => {
// This node is a leaf, do the swap and return
mem::swap(handle.key_mut(), &mut *key_ptr);
mem::swap(handle.val_mut(), &mut *val_ptr);
return SearchStack {
map: self.map,
stack: self.stack,
top: handle.as_raw()
}
},
Internal(kv_handle) => {
// This node is internal, go deeper
let mut handle = kv_handle.into_left_edge();
self.stack.push(handle.as_raw());
temp_node = handle.into_edge_mut();
}
}
}
}
}
}
}
}
impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> {
/// Inserts the key and value into the top element in the stack, and if that node has to
/// split recursively inserts the split contents into the next element stack until
/// splits stop.
///
/// Assumes that the stack represents a search path from the root to a leaf.
///
/// An &mut V is returned to the inserted value, for callers that want a reference to this.
pub fn insert(mut self, key: K, val: V) -> &'a mut V {
unsafe {
self.map.length += 1;
// Insert the key and value into the leaf at the top of the stack
let (mut insertion, inserted_ptr) = self.top.from_raw_mut()
.insert_as_leaf(key, val);
loop {
match insertion {
Fit => {
// The last insertion went off without a hitch, no splits! We can stop
// inserting now.
return &mut *inserted_ptr;
}
Split(key, val, right) => match self.stack.pop() {
// The last insertion triggered a split, so get the next element on the
// stack to recursively insert the split node into.
None => {
// The stack was empty; we've split the root, and need to make a
// a new one. This is done in-place because we can't move the
// root out of a reference to the tree.
Node::make_internal_root(&mut self.map.root, self.map.b,
key, val, right);
self.map.depth += 1;
return &mut *inserted_ptr;
}
Some(mut handle) => {
// The stack wasn't empty, do the insertion and recurse
insertion = handle.from_raw_mut()
.insert_as_internal(key, val, right);
continue;
}
}
}
}
}
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> {
let mut map = BTreeMap::new();
map.extend(iter);
map
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
#[inline]
fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
for (k, v) in iter {
self.insert(k, v);
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
fn hash<H: Hasher>(&self, state: &mut H) {
for elt in self {
elt.hash(state);
}
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Ord, V> Default for BTreeMap<K, V> {
#[stable(feature = "rust1", since = "1.0.0")]
fn default() -> BTreeMap<K, V> {
BTreeMap::new()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
fn eq(&self, other: &BTreeMap<K, V>) -> bool {
self.len() == other.len() &&
self.iter().zip(other.iter()).all(|(a, b)| a == b)
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
#[inline]
fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
iter::order::partial_cmp(self.iter(), other.iter())
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
#[inline]
fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
iter::order::cmp(self.iter(), other.iter())
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.iter().fold(f.debug_map(), |b, (k, v)| b.entry(k, v)).finish()
}
}
#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap<K, V>
where K: Borrow<Q>, Q: Ord
{
type Output = V;
#[inline]
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
}
}
/// Genericises over how to get the correct type of iterator from the correct type
/// of Node ownership.
trait Traverse<N> {
fn traverse(node: N) -> Self;
}
impl<'a, K, V> Traverse<&'a Node<K, V>> for Traversal<'a, K, V> {
fn traverse(node: &'a Node<K, V>) -> Traversal<'a, K, V> {
node.iter()
}
}
impl<'a, K, V> Traverse<&'a mut Node<K, V>> for MutTraversal<'a, K, V> {
fn traverse(node: &'a mut Node<K, V>) -> MutTraversal<'a, K, V> {
node.iter_mut()
}
}
impl<K, V> Traverse<Node<K, V>> for MoveTraversal<K, V> {
fn traverse(node: Node<K, V>) -> MoveTraversal<K, V> {
node.into_iter()
}
}
/// Represents an operation to perform inside the following iterator methods.
/// This is necessary to use in `next` because we want to modify `self.traversals` inside
/// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note
/// what we want to do, and do it after the match.
enum StackOp<T> {
Push(T),
Pop,
}
impl<K, V, E, T> Iterator for AbsIter<T> where
T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
{
type Item = (K, V);
// Our iterator represents a queue of all ancestors of elements we have
// yet to yield, from smallest to largest. Note that the design of these
// iterators permits an *arbitrary* initial pair of min and max, making
// these arbitrary sub-range iterators.
fn next(&mut self) -> Option<(K, V)> {
loop {
// We want the smallest element, so try to get the back of the queue
let op = match self.traversals.back_mut() {
None => return None,
// The queue wasn't empty, so continue along the node in its head
Some(iter) => match iter.next() {
// The head is empty, so Pop it off and continue the process
None => Pop,
// The head yielded an edge, so make that the new head
Some(Edge(next)) => Push(Traverse::traverse(next)),
// The head yielded an entry, so yield that
Some(Elem(kv)) => {
self.size -= 1;
return Some(kv)
}
}
};
// Handle any operation as necessary, without a conflicting borrow of the queue
match op {
Push(item) => { self.traversals.push_back(item); },
Pop => { self.traversals.pop_back(); },
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.size, Some(self.size))
}
}
impl<K, V, E, T> DoubleEndedIterator for AbsIter<T> where
T: DoubleEndedIterator<Item=TraversalItem<K, V, E>> + Traverse<E>,
{
// next_back is totally symmetric to next
#[inline]