rudy 0.0.1

Judy array implementation in pure Rust
Documentation 
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

use ::util::locksteparray::LockstepArray;
use ::util::locksteparray;
use ::util::SliceExt;
use super::innerptr::{InnerPtr, IntoPtr};
use ::Key;
use super::traits::JpmNode;
use ::rudymap::results::InsertResult;
use super::branch_bitmap::BranchBitmap;
use std::iter::FromIterator;

pub struct BranchLinear<K: Key, V> {
    array: LockstepArray<[u8; 7], [InnerPtr<K, V>; 7]>
}

impl<K: Key, V> BranchLinear<K, V> {
    pub fn new() -> BranchLinear<K, V> {
        BranchLinear {
            array: Default::default()
        }
    }
}

impl<K: Key, V> JpmNode<K, V> for BranchLinear<K, V> {
    fn get(&self, key: &[u8]) -> Option<&V> {
        let (byte, subkey) = key.split_first().unwrap();
        self.array.array1()
            .iter()
            .position(|b| b == byte)
            .and_then(|index| self.array.array2()[index].get(subkey))
    }

    fn get_mut(&mut self, key: &[u8]) -> Option<&mut V> {
        let (byte, subkey) = key.split_first().unwrap();
        self.array.array1_mut()
            .iter()
            .position(|b| b == byte)
            .and_then(move |index|
                      self.array.array2_mut()[index].get_mut(subkey))
    }

    fn insert(&mut self, key: &[u8], value: V) -> InsertResult<V> {
        let (&byte, subkey) = key.split_first().unwrap();
        match self.array.array1().linear_search(&byte) {
            Ok(found) => {
                InsertResult::Success(
                    self.array.array2_mut()[found].insert(subkey, value))
            },
            Err(insert) => {
                match self.array.insert(insert, byte, InnerPtr::empty()) {
                    Ok(()) => {},
                    Err(locksteparray::InsertError::Overflow(..)) => {
                        return InsertResult::Resize(value);
                    },
                    Err(locksteparray::InsertError::OutOfBounds(..)) => {
                        unreachable!()
                    }
                }
                let node = &mut self.array.array2_mut()[insert];
                InsertResult::Success(node.insert(subkey, value))
            }
        }
    }

    fn expand(self, pop: usize, key: &[u8], value: V) -> InnerPtr<K, V> {
        let mut branch: BranchBitmap<K, V> = self.array
            .into_iter()
            .collect();
        branch.insert(key, value).success();
        IntoPtr::into_ptr(Box::new(branch), pop)
    }
}

impl<K: Key, V> FromIterator<(u8, InnerPtr<K, V>)> for BranchLinear<K, V> {
    fn from_iter<I>(iter: I) -> BranchLinear<K, V>
        where I: IntoIterator<Item=(u8, InnerPtr<K, V>)> {
        let mut node = BranchLinear::new();
        for (k, v) in iter {
            node.array.push(k, v);
        }
        node
    }
}