1 use core::fmt; 2 use core::marker::PhantomData; 3 4 use serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; 5 use serde::ser::{Serialize, SerializeMap, Serializer}; 6 7 use super::{Entry, Slab}; 8 9 impl<T> Serialize for Slab<T> 10 where 11 T: Serialize, 12 { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer,13 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 14 where 15 S: Serializer, 16 { 17 let mut map_serializer = serializer.serialize_map(Some(self.len()))?; 18 for (key, value) in self { 19 map_serializer.serialize_key(&key)?; 20 map_serializer.serialize_value(value)?; 21 } 22 map_serializer.end() 23 } 24 } 25 26 struct SlabVisitor<T>(PhantomData<T>); 27 28 impl<'de, T> Visitor<'de> for SlabVisitor<T> 29 where 30 T: Deserialize<'de>, 31 { 32 type Value = Slab<T>; 33 expecting(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result34 fn expecting(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { 35 write!(fmt, "a map") 36 } 37 visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error> where A: MapAccess<'de>,38 fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error> 39 where 40 A: MapAccess<'de>, 41 { 42 let mut slab = Slab::with_capacity(map.size_hint().unwrap_or(0)); 43 44 // same as FromIterator impl 45 let mut vacant_list_broken = false; 46 let mut first_vacant_index = None; 47 while let Some((key, value)) = map.next_entry()? { 48 if key < slab.entries.len() { 49 // iterator is not sorted, might need to recreate vacant list 50 if let Entry::Vacant(_) = slab.entries[key] { 51 vacant_list_broken = true; 52 slab.len += 1; 53 } 54 // if an element with this key already exists, replace it. 55 // This is consistent with HashMap and BtreeMap 56 slab.entries[key] = Entry::Occupied(value); 57 } else { 58 if first_vacant_index.is_none() && slab.entries.len() < key { 59 first_vacant_index = Some(slab.entries.len()); 60 } 61 // insert holes as necessary 62 while slab.entries.len() < key { 63 // add the entry to the start of the vacant list 64 let next = slab.next; 65 slab.next = slab.entries.len(); 66 slab.entries.push(Entry::Vacant(next)); 67 } 68 slab.entries.push(Entry::Occupied(value)); 69 slab.len += 1; 70 } 71 } 72 if slab.len == slab.entries.len() { 73 // no vacant entries, so next might not have been updated 74 slab.next = slab.entries.len(); 75 } else if vacant_list_broken { 76 slab.recreate_vacant_list(); 77 } else if let Some(first_vacant_index) = first_vacant_index { 78 let next = slab.entries.len(); 79 match &mut slab.entries[first_vacant_index] { 80 Entry::Vacant(n) => *n = next, 81 _ => unreachable!(), 82 } 83 } else { 84 unreachable!() 85 } 86 87 Ok(slab) 88 } 89 } 90 91 impl<'de, T> Deserialize<'de> for Slab<T> 92 where 93 T: Deserialize<'de>, 94 { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>,95 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 96 where 97 D: Deserializer<'de>, 98 { 99 deserializer.deserialize_map(SlabVisitor(PhantomData)) 100 } 101 } 102