Add serde support

[bit-set.git] / src / lib.rs

diff --git a/src/lib.rs b/src/lib.rs
index 10846c6a1611c83cabb7a2d9bc5fcc7eb18b3d30..bd3835f0602c04232eb819633254c23afc1f3728 100644 (file)
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -52,6 +52,8 @@
 extern crate bit_vec;
 #[cfg(all(test, feature = "nightly"))]
 extern crate rand;
+#[cfg(feature = "serde")]
+extern crate serde2;
 #[cfg(all(test, feature = "nightly"))]
 extern crate test;
 
@@ -66,6 +68,9 @@ use core::fmt;
 use core::hash;
 use core::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};
 
+#[cfg(feature = "serde")]
+use serde2::{Deserialize, Deserializer, Serialize, Serializer};
+
 type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
 
 /// Computes how many blocks are needed to store that many bits
@@ -236,7 +241,7 @@ impl BitSet<u32> {
     /// ```
     #[inline]
     pub fn from_bit_vec(bit_vec: BitVec) -> Self {
-        BitSet { bit_vec: bit_vec }
+        BitSet { bit_vec }
     }
 
     pub fn from_bytes(bytes: &[u8]) -> Self {
@@ -412,11 +417,12 @@ impl<B: BitBlock> BitSet<B> {
             .rev()
             .take_while(|&&n| n == B::zero())
             .count();
-        // Truncate
-        let trunc_len = cmp::max(old_len - n, 1);
+        // Truncate away all empty trailing blocks, then shrink_to_fit
+        let trunc_len = old_len - n;
         unsafe {
             bit_vec.storage_mut().truncate(trunc_len);
             bit_vec.set_len(trunc_len * B::bits());
+            bit_vec.shrink_to_fit();
         }
     }
 
@@ -816,7 +822,7 @@ impl<B: BitBlock> BitSet<B> {
         }
 
         self.bit_vec.set(value, true);
-        return true;
+        true
     }
 
     /// Removes a value from the set. Returns `true` if the value was
@@ -828,7 +834,7 @@ impl<B: BitBlock> BitSet<B> {
 
         self.bit_vec.set(value, false);
 
-        return true;
+        true
     }
 }
 
@@ -846,6 +852,22 @@ impl<B: BitBlock> hash::Hash for BitSet<B> {
     }
 }
 
+#[cfg(feature = "serde")]
+impl<B: BitBlock + Serialize> Serialize for BitSet<B> {
+    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
+        self.bit_vec.serialize(serializer)
+    }
+}
+
+#[cfg(feature = "serde")]
+impl<'de, B: BitBlock + Deserialize<'de>> Deserialize<'de> for BitSet<B> {
+    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
+        Ok(Self {
+            bit_vec: BitVec::deserialize(deserializer)?,
+        })
+    }
+}
+
 #[derive(Clone)]
 struct BlockIter<T, B> {
     head: B,
@@ -858,7 +880,7 @@ where
     T: Iterator<Item = B>,
 {
     fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
-        let h = blocks.next().unwrap_or(B::zero());
+        let h = blocks.next().unwrap_or_else(B::zero);
         BlockIter {
             tail: blocks,
             head: h,
@@ -930,7 +952,7 @@ impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> {
             (Some(a), Some(b)) => Some((self.merge)(a, b)),
             (Some(a), None) => Some((self.merge)(a, B::zero())),
             (None, Some(b)) => Some((self.merge)(B::zero(), b)),
-            _ => return None,
+            _ => None,
         }
     }
 
@@ -1073,7 +1095,7 @@ mod tests {
             for &l in &lengths {
                 let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
                 assert_eq!(bitset.contains(1), b);
-                assert_eq!(bitset.contains((l - 1)), b);
+                assert_eq!(bitset.contains(l - 1), b);
                 assert!(!bitset.contains(l));
             }
         }
@@ -1371,6 +1393,91 @@ mod tests {
         assert_eq!(c.cmp(&b), Equal);
     }
 
+    #[test]
+    fn test_bit_set_shrink_to_fit_new() {
+        // There was a strange bug where we refused to truncate to 0
+        // and this would end up actually growing the array in a way
+        // that (safely corrupted the state).
+        let mut a = BitSet::new();
+        assert_eq!(a.len(), 0);
+        assert_eq!(a.capacity(), 0);
+        a.shrink_to_fit();
+        assert_eq!(a.len(), 0);
+        assert_eq!(a.capacity(), 0);
+        assert!(!a.contains(1));
+        a.insert(3);
+        assert!(a.contains(3));
+        assert_eq!(a.len(), 1);
+        assert!(a.capacity() > 0);
+        a.shrink_to_fit();
+        assert!(a.contains(3));
+        assert_eq!(a.len(), 1);
+        assert!(a.capacity() > 0);
+    }
+
+    #[test]
+    fn test_bit_set_shrink_to_fit() {
+        let mut a = BitSet::new();
+        assert_eq!(a.len(), 0);
+        assert_eq!(a.capacity(), 0);
+        a.insert(259);
+        a.insert(98);
+        a.insert(3);
+        assert_eq!(a.len(), 3);
+        assert!(a.capacity() > 0);
+        assert!(!a.contains(1));
+        assert!(a.contains(259));
+        assert!(a.contains(98));
+        assert!(a.contains(3));
+
+        a.shrink_to_fit();
+        assert!(!a.contains(1));
+        assert!(a.contains(259));
+        assert!(a.contains(98));
+        assert!(a.contains(3));
+        assert_eq!(a.len(), 3);
+        assert!(a.capacity() > 0);
+
+        let old_cap = a.capacity();
+        assert!(a.remove(259));
+        a.shrink_to_fit();
+        assert!(a.capacity() < old_cap, "{} {}", a.capacity(), old_cap);
+        assert!(!a.contains(1));
+        assert!(!a.contains(259));
+        assert!(a.contains(98));
+        assert!(a.contains(3));
+        assert_eq!(a.len(), 2);
+
+        let old_cap2 = a.capacity();
+        a.clear();
+        assert_eq!(a.capacity(), old_cap2);
+        assert_eq!(a.len(), 0);
+        assert!(!a.contains(1));
+        assert!(!a.contains(259));
+        assert!(!a.contains(98));
+        assert!(!a.contains(3));
+
+        a.insert(512);
+        assert!(a.capacity() > 0);
+        assert_eq!(a.len(), 1);
+        assert!(a.contains(512));
+        assert!(!a.contains(1));
+        assert!(!a.contains(259));
+        assert!(!a.contains(98));
+        assert!(!a.contains(3));
+
+        a.remove(512);
+        a.shrink_to_fit();
+        assert_eq!(a.capacity(), 0);
+        assert_eq!(a.len(), 0);
+        assert!(!a.contains(512));
+        assert!(!a.contains(1));
+        assert!(!a.contains(259));
+        assert!(!a.contains(98));
+        assert!(!a.contains(3));
+        assert!(!a.contains(0));
+    }
+
     #[test]
     fn test_bit_vec_remove() {
         let mut a = BitSet::new();