rehashinghashmap/
lib.rs

1use std::borrow::Borrow;
2use std::collections::hash_map;
3use std::collections::HashMap;
4use std::hash::Hash;
5use std::iter::Chain;
6use std::iter::FromIterator;
7use std::ops::Index;
8use std::mem;
9use std::sync::mpsc::channel;
10use std::thread;
11
12#[derive(Debug, Default)]
13pub struct RehashingHashMap<K: Eq + Hash, V> {
14    // NOTE: I tried to make an array of 2 elements, but run into borrowing problems
15    hashmap1: HashMap<K, V>,
16    hashmap2: HashMap<K, V>,
17    is1main: bool,
18    rehashing: bool,
19}
20
21impl<K, V> RehashingHashMap<K, V>
22    where K: Eq + Hash + Clone
23{
24    pub fn new() -> RehashingHashMap<K, V> {
25        RehashingHashMap {
26            hashmap1: HashMap::new(),
27            hashmap2: HashMap::new(),
28            is1main: true,
29            rehashing: false,
30        }
31    }
32
33    pub fn with_capacity(capacity: usize) -> RehashingHashMap<K, V> {
34        RehashingHashMap {
35            hashmap1: HashMap::with_capacity(capacity),
36            hashmap2: HashMap::new(),
37            is1main: true,
38            rehashing: false,
39        }
40    }
41
42    fn get_main(&self) -> &HashMap<K, V> {
43        if self.is1main { &self.hashmap1 } else { &self.hashmap2 }
44    }
45
46    fn get_mut_main(&mut self) -> &mut HashMap<K, V> {
47        if self.is1main { &mut self.hashmap1 } else { &mut self.hashmap2 }
48    }
49
50    fn get_secondary(&self) -> &HashMap<K, V> {
51        if self.is1main { &self.hashmap2 } else { &self.hashmap1 }
52    }
53
54    fn get_mut_secondary(&mut self) -> &mut HashMap<K, V> {
55        if self.is1main { &mut self.hashmap2 } else { &mut self.hashmap1 }
56    }
57
58    pub fn rehash(&mut self) {
59        if self.rehashing {
60            if self.get_secondary().len() == 0 {
61                self.drop_secondary();
62                return;
63            }
64            let (mut main, mut sec) = if self.is1main {
65                (&mut self.hashmap1, &mut self.hashmap2)
66            } else {
67                (&mut self.hashmap2, &mut self.hashmap1)
68            };
69            // unwrap is safe, checked len() > 0 already
70            let k: K = sec.keys().take(1).next().unwrap().clone();
71            // FIXME: I wish I did not have to clone they key
72            // unwrap is safe, we know the key exists in the hashmap
73            let val = sec.remove(&k).unwrap();
74            main.insert(k, val);
75        }
76    }
77
78    pub fn capacity(&self) -> usize {
79        self.get_main().capacity() + self.get_secondary().len()
80    }
81
82    pub fn reserve(&mut self, additional: usize) {
83        self.rehash();
84        self.get_mut_main().reserve(additional)
85    }
86
87    pub fn is_rehashing(&self) -> bool {
88        if !self.rehashing {
89            assert_eq!(self.get_secondary().len(), 0);
90        }
91        self.rehashing
92    }
93
94    pub fn shrink_to_fit(&mut self) {
95        if !self.rehashing {
96            self.rehashing = true;
97            self.is1main = !self.is1main;
98            let len = self.len();
99            self.get_mut_main().reserve(len)
100        }
101    }
102
103    pub fn len(&self) -> usize {
104        self.get_main().len() + self.get_secondary().len()
105    }
106
107    pub fn is_empty(&self) -> bool {
108        self.get_main().is_empty() && self.get_secondary().is_empty()
109    }
110
111    fn drop_secondary(&mut self) {
112        self.rehashing = false;
113        assert_eq!(self.get_secondary().len(), 0);
114        let h = if self.is1main {
115            mem::replace(&mut self.hashmap2, HashMap::new());
116        } else {
117            mem::replace(&mut self.hashmap1, HashMap::new());
118        };
119        let (tx, rx) = channel();
120        thread::spawn(move || drop(rx.recv().unwrap()));
121        tx.send(h).unwrap();
122    }
123
124    fn assert_state(&self) {
125        #![allow(dead_code)]
126        if self.rehashing {
127            assert!(self.get_secondary().capacity() > 0);
128        } else {
129            assert!(self.get_secondary().capacity() == 0);
130        }
131    }
132
133    pub fn clear(&mut self) {
134        self.get_mut_main().clear();
135        self.drop_secondary();
136    }
137
138    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
139        // while rehashing, they key can be in either hashmap1 or hashmap2
140        // but we want to remove them from wherever it is and add it to main
141        let mut ret = None;
142        if self.rehashing || self.is1main {
143            ret = self.hashmap1.remove(&k);
144        }
145        if ret.is_none() && (self.rehashing || !self.is1main) {
146            ret = self.hashmap2.remove(&k);
147        }
148        self.get_mut_main().insert(k, v);
149        self.rehash();
150        ret
151    }
152
153    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
154            where K: Borrow<Q>, Q: Hash + Eq {
155        if self.rehashing {
156            match self.get_main().get(k) {
157                Some(ref v) => Some(v),
158                None => self.get_secondary().get(k),
159            }
160        } else {
161            self.get_main().get(k)
162        }
163    }
164
165    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
166            where K: Borrow<Q>, Q: Hash + Eq {
167        if self.rehashing {
168            self.rehash();
169            if self.get_main().contains_key(k) {
170                self.get_mut_main().get_mut(k)
171            } else {
172                self.get_mut_secondary().get_mut(k)
173            }
174        } else {
175            self.get_mut_main().get_mut(k)
176        }
177    }
178
179    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
180            where K: Borrow<Q>, Q: Hash + Eq {
181        self.get_main().contains_key(k) || self.get_secondary().contains_key(k)
182    }
183
184    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
185        where K: Borrow<Q>, Q: Hash + Eq {
186        if self.rehashing {
187            self.rehash();
188            match self.get_mut_main().remove(k) {
189                Some(v) => Some(v),
190                None => self.get_mut_secondary().remove(k),
191            }
192        } else {
193            self.get_mut_main().remove(k)
194        }
195    }
196
197    pub fn entry(&mut self, key: K) -> hash_map::Entry<K, V> {
198        self.rehash();
199        if self.rehashing {
200            if self.get_secondary().contains_key(&key) {
201                return self.get_mut_secondary().entry(key);
202            }
203        }
204        self.get_mut_main().entry(key)
205    }
206
207    pub fn iter(&self) -> Iter<K, V> {
208        Iter {
209            inner: self.hashmap1.iter().chain(self.hashmap2.iter()),
210            len: self.hashmap1.len() + self.hashmap2.len(),
211        }
212    }
213
214    pub fn iter_mut(&mut self) -> IterMut<K, V> {
215        self.rehash();
216        let len = self.hashmap1.len() + self.hashmap2.len();
217        IterMut {
218            inner: self.hashmap1.iter_mut().chain(self.hashmap2.iter_mut()),
219            len: len,
220        }
221    }
222
223    pub fn keys(&self) -> Keys<K, V> {
224        Keys {
225            inner: self.hashmap1.keys().chain(self.hashmap2.keys()),
226            len: self.hashmap1.len() + self.hashmap2.len(),
227        }
228    }
229
230    pub fn values(&self) -> Values<K, V> {
231        Values {
232            inner: self.hashmap1.values().chain(self.hashmap2.values()),
233            len: self.hashmap1.len() + self.hashmap2.len(),
234        }
235    }
236}
237
238impl<K, V> PartialEq for RehashingHashMap<K, V> where K: Eq + Hash + Clone, V: PartialEq {
239    fn eq(&self, other: &RehashingHashMap<K, V>) -> bool {
240        // we cannot rehash because `self` and `other` are not immutables!
241        // so we should try to see if they are the same manually if they are
242        // rehashing
243        if !self.is_rehashing() && !other.is_rehashing() {
244            return self.get_main().eq(other.get_main());
245        }
246
247        if self.len() != other.len() {
248            return false;
249        }
250
251        for (k, v) in self.iter() {
252            if other.get(k) != Some(v) {
253                return false;
254            }
255        }
256        return true;
257    }
258}
259
260impl<'a, K, Q: ?Sized, V> Index<&'a Q> for RehashingHashMap<K, V>
261    where K: Eq + Hash + Clone + Borrow<Q>,
262    Q: Eq + Hash,
263{
264    type Output = V;
265
266    #[inline]
267    fn index(&self, index: &Q) -> &V {
268        self.get(index).expect("no entry found for key")
269    }
270}
271
272impl<'a, K, V> IntoIterator for &'a RehashingHashMap<K, V>
273    where K: Eq + Hash + Clone
274{
275    type Item = (&'a K, &'a V);
276    type IntoIter = Iter<'a, K, V>;
277
278    fn into_iter(self) -> Iter<'a, K, V> {
279        self.iter()
280    }
281}
282
283impl<'a, K, V> IntoIterator for &'a mut RehashingHashMap<K, V>
284    where K: Eq + Hash + Clone
285{
286    type Item = (&'a K, &'a mut V);
287    type IntoIter = IterMut<'a, K, V>;
288
289    fn into_iter(mut self) -> IterMut<'a, K, V> {
290        self.iter_mut()
291    }
292}
293
294impl<K, V> FromIterator<(K, V)> for RehashingHashMap<K, V>
295    where K: Eq + Hash + Clone
296{
297    fn from_iter<T: IntoIterator<Item=(K, V)>>(iterable: T) -> RehashingHashMap<K, V> {
298        let iter = iterable.into_iter();
299        let lower = iter.size_hint().0;
300        let mut map = RehashingHashMap::with_capacity(lower);
301        map.extend(iter);
302        map
303    }
304}
305
306impl<K, V> Extend<(K, V)> for RehashingHashMap<K, V>
307    where K: Eq + Hash + Clone
308{
309    fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) {
310        for (k, v) in iter {
311            self.insert(k, v);
312        }
313    }
314}
315
316#[derive(Clone)]
317pub struct Iter<'a, K: 'a, V: 'a> {
318    inner: Chain<hash_map::Iter<'a, K, V>, hash_map::Iter<'a, K, V>>,
319    len: usize,
320}
321
322impl<'a, K, V> Iterator for Iter<'a, K, V> {
323    type Item = (&'a K, &'a V);
324
325    #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() }
326    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
327}
328
329impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
330    #[inline] fn len(&self) -> usize { self.len }
331}
332
333pub struct IterMut<'a, K: 'a, V: 'a> {
334    inner: Chain<hash_map::IterMut<'a, K, V>, hash_map::IterMut<'a, K, V>>,
335    len: usize,
336}
337
338impl<'a, K, V> Iterator for IterMut<'a, K, V> {
339    type Item = (&'a K, &'a mut V);
340
341    #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() }
342    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
343}
344
345impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
346    #[inline] fn len(&self) -> usize { self.len }
347}
348
349#[derive(Clone)]
350pub struct Keys<'a, K: 'a, V: 'a> {
351    inner: Chain<hash_map::Keys<'a, K, V>, hash_map::Keys<'a, K, V>>,
352    len: usize,
353}
354
355impl<'a, K, V> Iterator for Keys<'a, K, V> {
356    type Item = &'a K;
357
358    #[inline] fn next(&mut self) -> Option<&'a K> { self.inner.next() }
359    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
360}
361
362impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
363    #[inline] fn len(&self) -> usize { self.len }
364}
365
366#[derive(Clone)]
367pub struct Values<'a, K: 'a, V: 'a> {
368    inner: Chain<hash_map::Values<'a, K, V>, hash_map::Values<'a, K, V>>,
369    len: usize,
370}
371
372impl<'a, K, V> Iterator for Values<'a, K, V> {
373    type Item = &'a V;
374
375    #[inline] fn next(&mut self) -> Option<&'a V> { self.inner.next() }
376    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
377}
378
379impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
380    #[inline] fn len(&self) -> usize { self.len }
381}
382
383#[test]
384fn capacity() {
385    let mut hash:RehashingHashMap<u8, u8> = RehashingHashMap::with_capacity(20);
386    assert!(hash.capacity() >= 20);
387    hash.reserve(40);
388    assert!(hash.capacity() >= 40);
389}
390
391#[test]
392fn insert() {
393    let mut hash = RehashingHashMap::new();
394    let key = 0;
395    let value1 = 2;
396    let value2 = 3;
397
398    assert_eq!(hash.insert(key.clone(), value1.clone()), None);
399    assert_eq!(hash.insert(key.clone(), value2.clone()), Some(value1.clone()));
400    hash.shrink_to_fit();
401    assert!(hash.is_rehashing());
402    assert_eq!(hash.insert(key.clone(), value1.clone()), Some(value2.clone()));
403    assert!(!hash.is_rehashing());
404    hash.assert_state();
405}
406
407#[test]
408fn insert_many_rehash_get() {
409    let mut hash = RehashingHashMap::new();
410
411    let len = 1000;
412
413    for i in 0..len {
414        hash.insert(i.clone(), i.clone());
415    }
416    hash.shrink_to_fit();
417    for _ in 0..(len / 2){
418        hash.rehash();
419    }
420    assert!(hash.is_rehashing());
421
422    assert_eq!(hash.len(), len);
423
424    for i in 0..len {
425        assert_eq!(hash.get(&i).unwrap(), &i);
426    }
427    for i in len..(len * 2) {
428        assert!(hash.get(&i).is_none());
429    }
430
431    for _ in 0..(len / 2 + 1){
432        hash.rehash();
433    }
434    assert!(!hash.is_rehashing());
435    hash.assert_state();
436
437    assert_eq!(hash.len(), len);
438
439    for i in 0..len {
440        assert_eq!(hash.get(&i).unwrap(), &i);
441    }
442    for i in len..(len * 2) {
443        assert!(hash.get(&i).is_none());
444    }
445}
446
447#[test]
448fn is_empty() {
449    let mut hash = RehashingHashMap::new();
450    assert!(hash.is_empty());
451
452    let key = 0;
453    let value = 2;
454    assert_eq!(hash.insert(key.clone(), value.clone()), None);
455    assert!(!hash.is_empty());
456    hash.shrink_to_fit();
457    assert!(hash.is_rehashing());
458    assert!(!hash.is_empty());
459    hash.rehash();
460    hash.rehash();
461    assert!(!hash.is_rehashing());
462    assert!(!hash.is_empty());
463}
464
465#[test]
466fn clear() {
467    let mut hash = RehashingHashMap::with_capacity(1000);
468    let key = 0;
469    let value = 2;
470    assert_eq!(hash.insert(key.clone(), value.clone()), None);
471    hash.clear();
472    hash.assert_state();
473
474    assert!(hash.capacity() >= 1000);
475}
476
477#[test]
478fn remove0() {
479    let mut hash = RehashingHashMap::new();
480    let key = 0;
481    let value = 2;
482    assert_eq!(hash.insert(key.clone(), value.clone()), None);
483    hash.shrink_to_fit();
484    assert!(hash.is_rehashing());
485    assert_eq!(hash.remove(&key).unwrap(), value);
486}
487
488#[test]
489fn remove1() {
490    let mut hash = RehashingHashMap::new();
491    let key = 0;
492    let value = 2;
493    assert_eq!(hash.insert(key.clone(), value.clone()), None);
494    hash.shrink_to_fit();
495    hash.rehash();
496    assert!(hash.is_rehashing());
497    assert_eq!(hash.remove(&key).unwrap(), value);
498}
499
500#[test]
501fn remove2() {
502    let mut hash = RehashingHashMap::new();
503    let key = 0;
504    let value = 2;
505    assert_eq!(hash.insert(key.clone(), value.clone()), None);
506    hash.shrink_to_fit();
507    hash.rehash();
508    hash.rehash();
509    assert!(!hash.is_rehashing());
510    assert_eq!(hash.remove(&key).unwrap(), value);
511}
512
513#[test]
514fn iterator() {
515    let len = 100;
516    let mut hash = RehashingHashMap::with_capacity(len);
517    let mut control = HashMap::new();
518    for i in 0..len {
519        hash.insert(i.clone(), i.clone());
520        control.insert(i.clone(), i.clone());
521    }
522    hash.shrink_to_fit();
523    for _ in 0..(len / 2) {
524        hash.rehash();
525    }
526    assert!(hash.is_rehashing());
527
528    assert_eq!(hash.iter().len(), len);
529    for (_, i) in hash.iter() {
530        control.remove(&i);
531    }
532    assert!(control.is_empty());
533}
534
535#[test]
536fn iter_mut() {
537    let len = 100;
538    let mut hash = RehashingHashMap::with_capacity(len);
539    let mut control = HashMap::new();
540    for i in 0..len {
541        hash.insert(i.clone(), i.clone());
542        control.insert(i.clone(), i.clone());
543    }
544    hash.shrink_to_fit();
545    for _ in 0..(len / 2) {
546        hash.rehash();
547    }
548    assert!(hash.is_rehashing());
549
550    assert_eq!(hash.iter_mut().len(), len);
551    for (_, i) in hash.iter_mut() {
552        control.remove(&i);
553        *i *= 2;
554    }
555    assert!(control.is_empty());
556
557    // make sure mutability was saved
558    for i in 0..len {
559        assert_eq!(hash.get(&i).unwrap().clone(), i * 2);
560    }
561}
562
563#[test]
564fn keys() {
565    let len = 100;
566    let mut hash = RehashingHashMap::with_capacity(len);
567    let mut control = HashMap::new();
568    for i in 0..len {
569        hash.insert(i.clone(), i.clone());
570        control.insert(i.clone(), i.clone());
571    }
572    hash.shrink_to_fit();
573    for _ in 0..(len / 2) {
574        hash.rehash();
575    }
576    assert!(hash.is_rehashing());
577
578    assert_eq!(hash.keys().len(), len);
579    for i in hash.keys() {
580        control.remove(&i);
581    }
582    assert!(control.is_empty());
583}
584
585#[test]
586fn values() {
587    let len = 100;
588    let mut hash = RehashingHashMap::with_capacity(len);
589    let mut control = HashMap::new();
590    for i in 0..len {
591        hash.insert(i.clone(), i.clone());
592        control.insert(i.clone(), i.clone());
593    }
594    hash.shrink_to_fit();
595    for _ in 0..(len / 2) {
596        hash.rehash();
597    }
598    assert!(hash.is_rehashing());
599
600    assert_eq!(hash.values().len(), len);
601    for i in hash.values() {
602        control.remove(&i);
603    }
604    assert!(control.is_empty());
605}
606
607#[test]
608fn entry() {
609    let len = 100;
610    let mut hash = RehashingHashMap::with_capacity(len);
611    for i in 0..len {
612        hash.insert(i.clone(), i.clone());
613    }
614
615    // modifying main
616    {
617        let v = hash.entry(0).or_insert(100); // updating
618        *v += 1;
619    }
620    hash.entry(len).or_insert(len); // inserting
621
622    hash.shrink_to_fit();
623    // modifying secondary
624    assert!(hash.is_rehashing());
625    {
626        let v = hash.entry(1).or_insert(100); // updating
627        *v += 1;
628    }
629    hash.entry(len + 1).or_insert(len + 1); // inserting
630
631    while hash.is_rehashing() {
632        hash.rehash();
633    }
634
635    // modifying the new main
636    {
637        let v = hash.entry(2).or_insert(100); // updating
638        *v += 1;
639    }
640    hash.entry(len + 2).or_insert(len + 2); // inserting
641
642    for i in 0..(len + 3) {
643        assert_eq!(hash.get(&i).unwrap().clone(), if i <= 2 { i + 1 } else { i });
644    }
645}
646
647#[test]
648fn contains_key() {
649    let len = 100;
650    let mut hash = RehashingHashMap::with_capacity(len);
651    for i in 0..len {
652        hash.insert(i.clone(), i.clone());
653    }
654    hash.shrink_to_fit();
655    for _ in 0..(len / 2) {
656        hash.rehash();
657    }
658    assert!(hash.is_rehashing());
659
660    for i in 0..len {
661        assert!(hash.contains_key(&i));
662    }
663    assert!(!hash.contains_key(&(len + 1)));
664}
665
666#[test]
667fn get_mut0() {
668    let mut hash = RehashingHashMap::new();
669    let value = 1;
670    {
671        hash.insert(value.clone(), value.clone());
672        hash.shrink_to_fit();
673        assert!(hash.is_rehashing());
674        let val = hash.get_mut(&value).unwrap();
675        *val += 1;
676    }
677    assert_eq!(hash.get(&value).unwrap().clone(), 2);
678}
679
680#[test]
681fn get_mut1() {
682    let mut hash = RehashingHashMap::new();
683    let value = 1;
684    {
685        hash.insert(value.clone(), value.clone());
686        hash.shrink_to_fit();
687        hash.rehash();
688        assert!(hash.is_rehashing());
689        let val = hash.get_mut(&value).unwrap();
690        *val += 1;
691    }
692    assert_eq!(hash.get(&value).unwrap().clone(), 2);
693}
694
695#[test]
696fn get_mut2() {
697    let mut hash = RehashingHashMap::new();
698    let value = 1;
699    {
700        hash.insert(value.clone(), value.clone());
701        hash.shrink_to_fit();
702        hash.rehash();
703        hash.rehash();
704        assert!(!hash.is_rehashing());
705        let val = hash.get_mut(&value).unwrap();
706        *val += 1;
707    }
708    assert_eq!(hash.get(&value).unwrap().clone(), 2);
709}
710
711#[test]
712fn eq() {
713    let mut hash1 = RehashingHashMap::new();
714    let mut hash2 = RehashingHashMap::new();
715
716    for i in 0..100 {
717        hash1.insert(i.clone(), i.clone());
718        hash2.insert(i.clone(), i.clone());
719    }
720    hash1.shrink_to_fit();
721    hash2.shrink_to_fit();
722    while hash2.is_rehashing() {
723        assert_eq!(hash1, hash2);
724        hash2.rehash();
725    }
726    hash2.shrink_to_fit();
727    hash2.insert(101, 101);
728    assert!(hash1 != hash2);
729}
730
731#[test]
732fn index() {
733    let mut hash = RehashingHashMap::new();
734
735    for i in 0..100 {
736        hash.insert(i.clone(), i.clone());
737    }
738    hash.shrink_to_fit();
739    for i in 0..100 {
740        hash.rehash();
741        assert_eq!(hash[&i], i);
742    }
743}
744
745#[test]
746fn into_iter() {
747    let len = 100;
748    let mut hash = RehashingHashMap::new();
749    let mut control = HashMap::new();
750    for i in 0..len {
751        hash.insert(i.clone(), i.clone());
752        control.insert(i.clone(), i.clone());
753    }
754    hash.shrink_to_fit();
755    for _ in 0..(len / 2) {
756        hash.rehash();
757    }
758
759    for (k, v) in hash.into_iter() {
760        assert_eq!(&control.remove(&k).unwrap(), v);
761    }
762    assert_eq!(control.len(), 0);
763}
764
765#[test]
766fn extend() {
767    let mut hash = RehashingHashMap::new();
768    hash.extend(vec![(1, 1), (2, 2), (3, 3)]);
769    assert_eq!(hash.len(), 3);
770}
771
772#[test]
773fn from_iter() {
774    let hash = RehashingHashMap::from_iter(vec![(1, 1), (2, 2), (3, 3)]);
775    assert_eq!(hash.len(), 3);
776}
rehashinghashmap/lib.rs

rehashinghashmap/
lib.rs
