core_json/stack/
const.rs

1use crate::{State, Stack};
2
3/// An array of `State`, using `u2` for each value.
4#[derive(Debug)]
5struct PackedStates<const ONE_FOURTH_OF_MAX_DEPTH: usize>([u8; ONE_FOURTH_OF_MAX_DEPTH]);
6impl<const ONE_FOURTH_OF_MAX_DEPTH: usize> PackedStates<ONE_FOURTH_OF_MAX_DEPTH> {
7  #[inline(always)]
8  fn get(&self, i: usize) -> State {
9    let mut entry = self.0[i / 4];
10    entry >>= (i & 0b11) * 2;
11    entry &= 0b11;
12    match entry {
13      0 => State::Object,
14      1 => State::Array,
15      2 => State::Unknown,
16      3 => panic!("`PackedStates` was written to with a non-existent `State`"),
17      _ => unreachable!("masked by 0b11"),
18    }
19  }
20
21  #[inline(always)]
22  fn set(&mut self, i: usize, kind: State) {
23    let two_bits = match kind {
24      State::Object => 0,
25      State::Array => 1,
26      State::Unknown => 2,
27    };
28    let shift = (i & 0b11) * 2;
29    // Clear the existing value in this slot
30    self.0[i / 4] &= !(0b00000011 << shift);
31    // Set the new value
32    self.0[i / 4] |= two_bits << shift;
33  }
34}
35
36/// An error with the stack.
37#[derive(Clone, Copy, Debug)]
38#[allow(dead_code)]
39pub enum StackError {
40  /// The stack's depth limit was exceeded.
41  StackTooDeep,
42}
43
44/// A non-allocating `Stack`.
45#[derive(Debug)]
46pub struct ConstStack<const ONE_FOURTH_OF_MAX_DEPTH: usize> {
47  /// The current items on the stack.
48  items: PackedStates<{ ONE_FOURTH_OF_MAX_DEPTH }>,
49
50  /// The current depth of the stack.
51  ///
52  /// This is analogous to the length of a `Vec`.
53  depth: usize,
54}
55
56impl<const ONE_FOURTH_OF_MAX_DEPTH: usize> Stack for ConstStack<ONE_FOURTH_OF_MAX_DEPTH> {
57  type Error = StackError;
58
59  #[inline(always)]
60  fn empty() -> Self {
61    Self { items: PackedStates([0; ONE_FOURTH_OF_MAX_DEPTH]), depth: 0 }
62  }
63
64  #[inline(always)]
65  fn depth(&self) -> usize {
66    self.depth
67  }
68
69  #[inline(always)]
70  fn peek(&self) -> Option<State> {
71    let i = self.depth.checked_sub(1)?;
72    Some(self.items.get(i))
73  }
74
75  #[inline(always)]
76  fn pop(&mut self) -> Option<State> {
77    let i = self.depth.checked_sub(1)?;
78    // This will not panic as we know depth can have `1` subtracted.
79    self.depth -= 1;
80
81    Some(self.items.get(i))
82  }
83
84  #[inline(always)]
85  fn push(&mut self, state: State) -> Result<(), StackError> {
86    if self.depth == (4 * ONE_FOURTH_OF_MAX_DEPTH) {
87      Err(StackError::StackTooDeep)?;
88    }
89    self.items.set(self.depth, state);
90    self.depth += 1;
91    Ok(())
92  }
93}
core_json/stack/const.rs

core_json/stack/
const.rs
