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
|
use std::ops;
use rustc_hash::FxBuildHasher;
use crate::accumulator::accumulated::Accumulated;
use crate::accumulator::{Accumulator, AnyAccumulated};
use crate::sync::atomic::{AtomicBool, Ordering};
use crate::IngredientIndex;
#[derive(Default)]
pub struct AccumulatedMap {
map: hashbrown::HashMap<IngredientIndex, Box<dyn AnyAccumulated>, FxBuildHasher>,
}
impl std::fmt::Debug for AccumulatedMap {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("AccumulatedMap")
.field("map", &self.map.keys())
.finish()
}
}
impl AccumulatedMap {
pub fn accumulate<A: Accumulator>(&mut self, index: IngredientIndex, value: A) {
self.map
.entry(index)
.or_insert_with(|| <Box<Accumulated<A>>>::default())
.accumulate(value);
}
pub fn extend_with_accumulated<'slf, A: Accumulator>(
&'slf self,
index: IngredientIndex,
output: &mut Vec<&'slf A>,
) {
let Some(a) = self.map.get(&index) else {
return;
};
a.as_dyn_any()
.downcast_ref::<Accumulated<A>>()
.unwrap()
.extend_with_accumulated(output);
}
pub fn is_empty(&self) -> bool {
self.map.is_empty()
}
pub fn clear(&mut self) {
self.map.clear()
}
pub fn allocation_size(&self) -> usize {
// allocation_size() is not available in older hashbrown versions
// Return an approximation based on capacity
self.map.capacity() * std::mem::size_of::<(IngredientIndex, Box<dyn AnyAccumulated>)>()
}
}
/// Tracks whether any input read during a query's execution has any accumulated values.
///
/// Knowning whether any input has accumulated values makes aggregating the accumulated values
/// cheaper because we can skip over entire subtrees.
#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
pub enum InputAccumulatedValues {
/// The query nor any of its inputs have any accumulated values.
#[default]
Empty,
/// The query or any of its inputs have at least one accumulated value.
Any,
}
impl InputAccumulatedValues {
pub const fn is_any(self) -> bool {
matches!(self, Self::Any)
}
pub const fn is_empty(self) -> bool {
matches!(self, Self::Empty)
}
pub fn or_else(self, other: impl FnOnce() -> Self) -> Self {
if self.is_any() {
Self::Any
} else {
other()
}
}
}
impl ops::BitOr for InputAccumulatedValues {
type Output = Self;
fn bitor(self, rhs: Self) -> Self::Output {
match (self, rhs) {
(Self::Any, _) | (_, Self::Any) => Self::Any,
(Self::Empty, Self::Empty) => Self::Empty,
}
}
}
impl ops::BitOrAssign for InputAccumulatedValues {
fn bitor_assign(&mut self, rhs: Self) {
*self = *self | rhs;
}
}
#[derive(Debug, Default)]
pub struct AtomicInputAccumulatedValues(AtomicBool);
impl Clone for AtomicInputAccumulatedValues {
fn clone(&self) -> Self {
Self(AtomicBool::new(self.0.load(Ordering::Relaxed)))
}
}
impl AtomicInputAccumulatedValues {
pub(crate) fn new(accumulated_inputs: InputAccumulatedValues) -> Self {
Self(AtomicBool::new(accumulated_inputs.is_any()))
}
pub(crate) fn store(&self, accumulated: InputAccumulatedValues) {
self.0.store(accumulated.is_any(), Ordering::Release);
}
pub(crate) fn load(&self) -> InputAccumulatedValues {
if self.0.load(Ordering::Acquire) {
InputAccumulatedValues::Any
} else {
InputAccumulatedValues::Empty
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn atomic_input_accumulated_values() {
let val = AtomicInputAccumulatedValues::new(InputAccumulatedValues::Empty);
assert_eq!(val.load(), InputAccumulatedValues::Empty);
val.store(InputAccumulatedValues::Any);
assert_eq!(val.load(), InputAccumulatedValues::Any);
let val = AtomicInputAccumulatedValues::new(InputAccumulatedValues::Any);
assert_eq!(val.load(), InputAccumulatedValues::Any);
val.store(InputAccumulatedValues::Empty);
assert_eq!(val.load(), InputAccumulatedValues::Empty);
}
}
|
