34 struct RBTreeNode<K: Ord, V> {
36     left: NodePtr<K, V>,
37     right: NodePtr<K, V>,
38     parent: NodePtr<K, V>,
39     key: K,
43 impl<K: Ord, V> RBTreeNode<K, V> {
45     fn pair(self) -> (K, V) {  in pair()  argument
50 impl<K, V> Debug for RBTreeNode<K, V>
52     K: Ord + Debug,
62 struct NodePtr<K: Ord, V>(*mut RBTreeNode<K, V>);
64 impl<K: Ord, V> Clone for NodePtr<K, V> {
65     fn clone(&self) -> NodePtr<K, V> {  in clone()  argument
70 impl<K: Ord, V> Copy for NodePtr<K, V> {}
72 impl<K: Ord, V> Ord for NodePtr<K, V> {
73     fn cmp(&self, other: &NodePtr<K, V>) -> Ordering {  in cmp()  argument
78 impl<K: Ord, V> PartialOrd for NodePtr<K, V> {
79     fn partial_cmp(&self, other: &NodePtr<K, V>) -> Option<Ordering> {  in partial_cmp()  argument
84 impl<K: Ord, V> PartialEq for NodePtr<K, V> {
85     fn eq(&self, other: &NodePtr<K, V>) -> bool {  in eq()  argument
90 impl<K: Ord, V> Eq for NodePtr<K, V> {}
92 impl<K: Ord, V> NodePtr<K, V> {
93     fn new(k: K, v: V) -> NodePtr<K, V> {  in new()  argument
160     fn min_node(self) -> NodePtr<K, V> {  in min_node()  argument
169     fn max_node(self) -> NodePtr<K, V> {  in max_node()  argument
178     fn next(self) -> NodePtr<K, V> {  in next()  argument
196     fn prev(self) -> NodePtr<K, V> {  in prev()  argument
214     fn set_parent(&mut self, parent: NodePtr<K, V>) {  in set_parent()  argument
222     fn set_left(&mut self, left: NodePtr<K, V>) {  in set_left()  argument
230     fn set_right(&mut self, right: NodePtr<K, V>) {  in set_right()  argument
238     fn parent(&self) -> NodePtr<K, V> {  in parent()  argument
246     fn left(&self) -> NodePtr<K, V> {  in left()  argument
254     fn right(&self) -> NodePtr<K, V> {  in right()  argument
262     fn null() -> NodePtr<K, V> {  in null()
272 impl<K: Ord + Clone, V: Clone> NodePtr<K, V> {
273     unsafe fn deep_clone(&self) -> NodePtr<K, V> {  in deep_clone()  argument
341 pub struct RBTree<K: Ord, V> {
342     root: NodePtr<K, V>,
347 impl<K: Ord, V> Drop for RBTree<K, V> {
355 impl<K: Ord + Clone, V: Clone> Clone for RBTree<K, V> {
356     fn clone(&self) -> RBTree<K, V> {  in clone()  argument
366 impl<K, V> Debug for RBTree<K, V>
368     K: Ord + Debug,
377 impl<K: Ord + Debug, V: Debug> RBTree<K, V> {
378     fn tree_print(&self, node: NodePtr<K, V>, direction: i32) {  in tree_print()  argument
413 impl<K, V> PartialEq for RBTree<K, V>
415     K: Eq + Ord,
418     fn eq(&self, other: &RBTree<K, V>) -> bool {  in eq()  argument
428 impl<K, V> Eq for RBTree<K, V>
430     K: Eq + Ord,
435 impl<'a, K, V> Index<&'a K> for RBTree<K, V>
437     K: Ord,
442     fn index(&self, index: &K) -> &V {  in index()
447 impl<K: Ord, V> FromIterator<(K, V)> for RBTree<K, V> {
448     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V> {  in from_iter()  argument
456 impl<K: Ord, V> Extend<(K, V)> for RBTree<K, V> {
457     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {  in extend()
477 pub struct Keys<'a, K: Ord + 'a, V: 'a> {
478     inner: Iter<'a, K, V>,
481 impl<'a, K: Ord, V> Clone for Keys<'a, K, V> {
482     fn clone(&self) -> Keys<'a, K, V> {  in clone()  argument
489 impl<'a, K: Ord + Debug, V> fmt::Debug for Keys<'a, K, V> {
495 impl<'a, K: Ord, V> Iterator for Keys<'a, K, V> {
496     type Item = &'a K;
499     fn next(&mut self) -> Option<&'a K> {  in next()  argument
522 pub struct Values<'a, K: 'a + Ord, V: 'a> {
523     inner: Iter<'a, K, V>,
526 impl<'a, K: Ord, V> Clone for Values<'a, K, V> {
527     fn clone(&self) -> Values<'a, K, V> {  in clone()  argument
534 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for Values<'a, K, V> {
540 impl<'a, K: Ord, V> Iterator for Values<'a, K, V> {
570 pub struct ValuesMut<'a, K: 'a + Ord, V: 'a> {
571     inner: IterMut<'a, K, V>,
574 impl<'a, K: Ord, V> Clone for ValuesMut<'a, K, V> {
575     fn clone(&self) -> ValuesMut<'a, K, V> {  in clone()  argument
582 impl<'a, K: Ord + Debug, V: Debug> fmt::Debug for ValuesMut<'a, K, V> {
588 impl<'a, K: Ord, V> Iterator for ValuesMut<'a, K, V> {
603 pub struct IntoIter<K: Ord, V> {
604     head: NodePtr<K, V>,
605     tail: NodePtr<K, V>,
610 impl<K: Ord, V> Drop for IntoIter<K, V> {
617 impl<K: Ord, V> Iterator for IntoIter<K, V> {
618     type Item = (K, V);
620     fn next(&mut self) -> Option<(K, V)> {  in next()  argument
646 impl<K: Ord, V> DoubleEndedIterator for IntoIter<K, V> {
648     fn next_back(&mut self) -> Option<(K, V)> {  in next_back()  argument
682 pub struct Iter<'a, K: Ord + 'a, V: 'a> {
683     head: NodePtr<K, V>,
684     tail: NodePtr<K, V>,
689 impl<'a, K: Ord + 'a, V: 'a> Clone for Iter<'a, K, V> {
690     fn clone(&self) -> Iter<'a, K, V> {  in clone()  argument
700 impl<'a, K: Ord + 'a, V: 'a> Iterator for Iter<'a, K, V> {
701     type Item = (&'a K, &'a V);
703     fn next(&mut self) -> Option<(&'a K, &'a V)> {  in next()  argument
723 impl<'a, K: Ord + 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
725     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {  in next_back()  argument
758 pub struct IterMut<'a, K: Ord + 'a, V: 'a> {
759     head: NodePtr<K, V>,
760     tail: NodePtr<K, V>,
765 impl<'a, K: Ord + 'a, V: 'a> Clone for IterMut<'a, K, V> {
766     fn clone(&self) -> IterMut<'a, K, V> {  in clone()  argument
776 impl<'a, K: Ord + 'a, V: 'a> Iterator for IterMut<'a, K, V> {
777     type Item = (&'a K, &'a mut V);
779     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {  in next()  argument
799 impl<'a, K: Ord + 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
801     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {  in next_back()  argument
817 impl<K: Ord, V> IntoIterator for RBTree<K, V> {
818     type Item = (K, V);
819     type IntoIter = IntoIter<K, V>;
822     fn into_iter(mut self) -> IntoIter<K, V> {  in into_iter()  argument
841 impl<K: Ord, V> RBTree<K, V> {
843     pub fn new() -> RBTree<K, V> {  in new()
877     unsafe fn left_rotate(&mut self, mut node: NodePtr<K, V>) {  in left_rotate()  argument
912     unsafe fn right_rotate(&mut self, mut node: NodePtr<K, V>) {  in right_rotate()  argument
946     pub fn replace_or_insert(&mut self, k: K, mut v: V) -> Option<V> {  in replace_or_insert()  argument
961     unsafe fn insert_fixup(&mut self, mut node: NodePtr<K, V>) {  in insert_fixup()  argument
1021     pub fn insert(&mut self, k: K, v: V) {  in insert()  argument
1060     fn find_node(&self, k: &K) -> NodePtr<K, V> {  in find_node()  argument
1082     fn first_child(&self) -> NodePtr<K, V> {  in first_child()  argument
1095     fn last_child(&self) -> NodePtr<K, V> {  in last_child()  argument
1108     pub fn get_first(&self) -> Option<(&K, &V)> {  in get_first()  argument
1117     pub fn get_last(&self) -> Option<(&K, &V)> {  in get_last()  argument
1126     pub fn pop_first(&mut self) -> Option<(K, V)> {  in pop_first()  argument
1135     pub fn pop_last(&mut self) -> Option<(K, V)> {  in pop_last()  argument
1144     pub fn get_first_mut(&mut self) -> Option<(&K, &mut V)> {  in get_first_mut()  argument
1153     pub fn get_last_mut(&mut self) -> Option<(&K, &mut V)> {  in get_last_mut()  argument
1162     pub fn get(&self, k: &K) -> Option<&V> {  in get()
1172     pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {  in get_mut()
1182     pub fn contains_key(&self, k: &K) -> bool {  in contains_key()
1191     fn clear_recurse(&mut self, current: NodePtr<K, V>) {  in clear_recurse()  argument
1215     pub fn remove(&mut self, k: &K) -> Option<V> {  in remove()
1224     unsafe fn delete_fixup(&mut self, mut node: NodePtr<K, V>, mut parent: NodePtr<K, V>) {  in delete_fixup()  argument
1296     unsafe fn delete(&mut self, node: NodePtr<K, V>) -> (K, V) {  in delete()  argument
1378     pub fn keys(&self) -> Keys<K, V> {  in keys()  argument
1384     pub fn values(&self) -> Values<K, V> {  in values()  argument
1390     pub fn values_mut(&mut self) -> ValuesMut<K, V> {  in values_mut()  argument
1398     pub fn iter(&self) -> Iter<K, V> {  in iter()  argument
1409     pub fn iter_mut(&mut self) -> IterMut<K, V> {  in iter_mut()  argument