sparse-bitfield 0.5.0

Bitfield that allocates a series of small buffers
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
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

#![cfg_attr(feature = "nightly", deny(missing_docs))]
#![cfg_attr(feature = "nightly", feature(external_doc))]
#![cfg_attr(feature = "nightly", doc(include = "../README.md"))]
#![cfg_attr(test, deny(warnings))]

extern crate memory_pager;

mod change;
mod iter;

pub use change::Change;
pub use iter::Iter;
use memory_pager::Pager;

/// Bitfield instance.
#[derive(Debug)]
pub struct Bitfield {
  /// A [memory-pager] instance.
  ///
  /// [memory-pager]: https://docs.rs/memory-pager/
  pub pages: Pager,

  length: usize,
  page_length: usize,
}

/// Create a new instance with a `page_size` of `1kb`.
impl Default for Bitfield {
  #[inline]
  fn default() -> Self {
    let page_size = 1024;
    Bitfield::new(page_size)
  }
}

impl Bitfield {
  /// Create a new instance.
  ///
  /// ## Panics
  /// Panics if the page size is not a power of two (2, 4, 8, etc.)
  pub fn new(page_size: usize) -> Self {
    assert!(is_power_of_two(page_size));
    Bitfield {
      pages: Pager::new(page_size),
      page_length: 0,
      length: 0,
    }
  }

  /// Set a byte to true or false. Returns a boolean indicating if the value was
  /// changed.
  #[inline]
  pub fn set(&mut self, index: usize, value: bool) -> Change {
    let masked_index = index & 7;
    let j = (index - masked_index) / 8;
    let b = self.get_byte(j);

    if value {
      self.set_byte(j, b | (128 >> masked_index))
    } else {
      self.set_byte(j, b & (255 ^ (128 >> masked_index)))
    }
  }

  /// Get the value of a bit.
  #[inline]
  pub fn get(&mut self, index: usize) -> bool {
    let masked_index = index & 7;
    let j = (index - masked_index) / 8;

    let num = self.get_byte(j) & (128 >> masked_index);
    match num {
      0 => false,
      _ => true,
    }
  }

  /// Get a byte from our internal buffers.
  #[inline]
  pub fn get_byte(&self, index: usize) -> u8 {
    let masked_index = self.page_mask(index);
    let page_num = index / self.page_size();
    match self.pages.get(page_num) {
      Some(page) => page[masked_index],
      None => 0,
    }
  }

  /// Set a byte to the right value inside our internal buffers.
  #[inline]
  pub fn set_byte(&mut self, index: usize, byte: u8) -> Change {
    let masked_index = self.page_mask(index);
    let page_num = (index - masked_index) / self.page_size();
    let page = self.pages.get_mut_or_alloc(page_num);

    if index >= self.length {
      self.length = index + 1;
    }
    if page[masked_index] == byte {
      return Change::Unchanged;
    }

    page[masked_index] = byte;
    if index >= self.length {
      self.length = index + 1;
    }

    Change::Changed
  }

  /// Get the memory page size in bytes.
  #[inline]
  pub fn page_size(&self) -> usize {
    self.pages.page_size()
  }

  /// Get the amount of bits in the bitfield.
  #[inline]
  pub fn len(&self) -> usize {
    self.length
  }

  /// Returns `true` if no bits are stored.
  #[inline]
  pub fn is_empty(&self) -> bool {
    self.len() == 0
  }

  /// Create an `Iterator` that iterates over all pages.
  pub fn iter(&mut self) -> Iter {
    Iter {
      inner: self,
      cursor: 0,
    }
  }

  #[inline]
  fn page_mask(&self, index: usize) -> usize {
    index & self.page_size() - 1
  }
}

#[inline]
fn is_power_of_two(x: usize) -> bool {
  x.count_ones() == 1
}