summaryrefslogtreecommitdiffstats
path: root/servo/components/style/rule_tree/map.rs
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--servo/components/style/rule_tree/map.rs201
1 files changed, 201 insertions, 0 deletions
diff --git a/servo/components/style/rule_tree/map.rs b/servo/components/style/rule_tree/map.rs
new file mode 100644
index 0000000000..33c470e9c1
--- /dev/null
+++ b/servo/components/style/rule_tree/map.rs
@@ -0,0 +1,201 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+#![forbid(unsafe_code)]
+
+use fxhash::FxHashMap;
+use malloc_size_of::{MallocShallowSizeOf, MallocSizeOfOps};
+use std::collections::hash_map;
+use std::hash::Hash;
+use std::mem;
+
+pub(super) struct Map<K, V> {
+ inner: MapInner<K, V>,
+}
+
+enum MapInner<K, V> {
+ Empty,
+ One(V),
+ Map(Box<FxHashMap<K, V>>),
+}
+
+pub(super) struct MapIter<'a, K, V> {
+ inner: MapIterInner<'a, K, V>,
+}
+
+enum MapIterInner<'a, K, V> {
+ One(std::option::IntoIter<&'a V>),
+ Map(std::collections::hash_map::Values<'a, K, V>),
+}
+
+pub(super) enum Entry<'a, K, V> {
+ Occupied(&'a mut V),
+ Vacant(VacantEntry<'a, K, V>),
+}
+
+pub(super) struct VacantEntry<'a, K, V> {
+ inner: VacantEntryInner<'a, K, V>,
+}
+
+enum VacantEntryInner<'a, K, V> {
+ One(&'a mut MapInner<K, V>),
+ Map(hash_map::VacantEntry<'a, K, V>),
+}
+
+impl<K, V> Default for Map<K, V> {
+ fn default() -> Self {
+ Map {
+ inner: MapInner::Empty,
+ }
+ }
+}
+
+impl<'a, K, V> IntoIterator for &'a Map<K, V> {
+ type Item = &'a V;
+ type IntoIter = MapIter<'a, K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ MapIter {
+ inner: match &self.inner {
+ MapInner::Empty => MapIterInner::One(None.into_iter()),
+ MapInner::One(one) => MapIterInner::One(Some(one).into_iter()),
+ MapInner::Map(map) => MapIterInner::Map(map.values()),
+ },
+ }
+ }
+}
+
+impl<'a, K, V> Iterator for MapIter<'a, K, V> {
+ type Item = &'a V;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ match &mut self.inner {
+ MapIterInner::One(one_iter) => one_iter.next(),
+ MapIterInner::Map(map_iter) => map_iter.next(),
+ }
+ }
+}
+
+impl<K, V> Map<K, V>
+where
+ K: Eq + Hash,
+{
+ pub(super) fn is_empty(&self) -> bool {
+ match &self.inner {
+ MapInner::Empty => true,
+ MapInner::One(_) => false,
+ MapInner::Map(map) => map.is_empty(),
+ }
+ }
+
+ #[cfg(debug_assertions)]
+ pub(super) fn len(&self) -> usize {
+ match &self.inner {
+ MapInner::Empty => 0,
+ MapInner::One(_) => 1,
+ MapInner::Map(map) => map.len(),
+ }
+ }
+
+ pub(super) fn get(&self, key: &K, key_from_value: impl FnOnce(&V) -> K) -> Option<&V> {
+ match &self.inner {
+ MapInner::One(one) if *key == key_from_value(one) => Some(one),
+ MapInner::Map(map) => map.get(key),
+ MapInner::Empty | MapInner::One(_) => None,
+ }
+ }
+
+ pub(super) fn entry(
+ &mut self,
+ key: K,
+ key_from_value: impl FnOnce(&V) -> K,
+ ) -> Entry<'_, K, V> {
+ match self.inner {
+ ref mut inner @ MapInner::Empty => Entry::Vacant(VacantEntry {
+ inner: VacantEntryInner::One(inner),
+ }),
+ MapInner::One(_) => {
+ let one = match mem::replace(&mut self.inner, MapInner::Empty) {
+ MapInner::One(one) => one,
+ _ => unreachable!(),
+ };
+ // If this panics, the child `one` will be lost.
+ let one_key = key_from_value(&one);
+ // Same for the equality test.
+ if key == one_key {
+ self.inner = MapInner::One(one);
+ let one = match &mut self.inner {
+ MapInner::One(one) => one,
+ _ => unreachable!(),
+ };
+ return Entry::Occupied(one);
+ }
+ self.inner = MapInner::Map(Box::new(FxHashMap::with_capacity_and_hasher(
+ 2,
+ Default::default(),
+ )));
+ let map = match &mut self.inner {
+ MapInner::Map(map) => map,
+ _ => unreachable!(),
+ };
+ map.insert(one_key, one);
+ match map.entry(key) {
+ hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
+ inner: VacantEntryInner::Map(entry),
+ }),
+ _ => unreachable!(),
+ }
+ },
+ MapInner::Map(ref mut map) => match map.entry(key) {
+ hash_map::Entry::Occupied(entry) => Entry::Occupied(entry.into_mut()),
+ hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
+ inner: VacantEntryInner::Map(entry),
+ }),
+ },
+ }
+ }
+
+ pub(super) fn remove(&mut self, key: &K, key_from_value: impl FnOnce(&V) -> K) -> Option<V> {
+ match &mut self.inner {
+ MapInner::One(one) if *key == key_from_value(one) => {
+ match mem::replace(&mut self.inner, MapInner::Empty) {
+ MapInner::One(one) => Some(one),
+ _ => unreachable!(),
+ }
+ },
+ MapInner::Map(map) => map.remove(key),
+ MapInner::Empty | MapInner::One(_) => None,
+ }
+ }
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V> {
+ pub(super) fn insert(self, value: V) -> &'a mut V {
+ match self.inner {
+ VacantEntryInner::One(map) => {
+ *map = MapInner::One(value);
+ match map {
+ MapInner::One(one) => one,
+ _ => unreachable!(),
+ }
+ },
+ VacantEntryInner::Map(entry) => entry.insert(value),
+ }
+ }
+}
+
+impl<K, V> MallocShallowSizeOf for Map<K, V>
+where
+ K: Eq + Hash,
+{
+ fn shallow_size_of(&self, ops: &mut MallocSizeOfOps) -> usize {
+ match &self.inner {
+ MapInner::Map(m) => {
+ // We want to account for both the box and the hashmap.
+ m.shallow_size_of(ops) + (**m).shallow_size_of(ops)
+ },
+ MapInner::One(_) | MapInner::Empty => 0,
+ }
+ }
+}