1use crate::DbError;
2use crate::StorageData;
3use crate::collections::bit_set::BitSet;
4use crate::collections::map::DbMapData;
5use crate::collections::map::MapData;
6use crate::collections::map::MapIterator;
7use crate::collections::map::MapValueState;
8use crate::collections::vec::VecValue;
9use crate::storage::Storage;
10use crate::storage::StorageIndex;
11use crate::utilities::stable_hash::StableHash;
12use std::marker::PhantomData;
13
14pub struct MultiMapImpl<K, T, D, Data>
15where
16 D: StorageData,
17 Data: MapData<K, T, D>,
18{
19 pub(crate) data: Data,
20 pub(crate) phantom_marker: PhantomData<(K, T, D)>,
21}
22
23pub struct MultiMapIterator<'a, K, T, D, Data>
24where
25 D: StorageData,
26 Data: MapData<K, T, D>,
27{
28 pub pos: u64,
29 pub key: &'a K,
30 pub data: &'a Data,
31 pub storage: &'a Storage<D>,
32 pub phantom_data: PhantomData<(T, D)>,
33}
34
35impl<K, T, D, Data> Iterator for MultiMapIterator<'_, K, T, D, Data>
36where
37 K: Default + PartialEq,
38 T: Default,
39 D: StorageData,
40 Data: MapData<K, T, D>,
41{
42 type Item = (K, T);
43
44 fn next(&mut self) -> Option<Self::Item> {
45 loop {
46 let current_pos = self.pos;
47 self.pos = if self.data.capacity() == 0 || self.pos == self.data.capacity() - 1 {
48 0
49 } else {
50 self.pos + 1
51 };
52
53 match self
54 .data
55 .state(self.storage, current_pos)
56 .unwrap_or_default()
57 {
58 MapValueState::Empty => break,
59 MapValueState::Deleted => {}
60 MapValueState::Valid => {
61 let key = self.data.key(self.storage, current_pos).unwrap_or_default();
62
63 if key == *self.key {
64 let value = self
65 .data
66 .value(self.storage, current_pos)
67 .unwrap_or_default();
68 return Some((key, value));
69 }
70 }
71 }
72 }
73
74 None
75 }
76}
77
78impl<K, T, D, Data> MultiMapImpl<K, T, D, Data>
79where
80 K: Default + PartialEq + StableHash,
81 T: Default + PartialEq,
82 D: StorageData,
83 Data: MapData<K, T, D>,
84{
85 pub fn capacity(&self) -> u64 {
86 self.data.capacity()
87 }
88
89 pub fn contains(&self, storage: &Storage<D>, key: &K) -> Result<bool, DbError> {
90 if self.capacity() == 0 {
91 return Ok(false);
92 }
93
94 let hash = key.stable_hash();
95 let mut pos = hash % self.capacity();
96
97 loop {
98 match self.data.state(storage, pos)? {
99 MapValueState::Empty => return Ok(false),
100 MapValueState::Valid if self.data.key(storage, pos)? == *key => return Ok(true),
101 MapValueState::Valid | MapValueState::Deleted => pos = self.next_pos(pos),
102 }
103 }
104 }
105
106 pub fn contains_value(
107 &self,
108 storage: &Storage<D>,
109 key: &K,
110 value: &T,
111 ) -> Result<bool, DbError> {
112 if self.capacity() == 0 {
113 return Ok(false);
114 }
115
116 let hash = key.stable_hash();
117 let mut pos = hash % self.capacity();
118
119 loop {
120 match self.data.state(storage, pos)? {
121 MapValueState::Empty => return Ok(false),
122 MapValueState::Valid
123 if self.data.key(storage, pos)? == *key
124 && self.data.value(storage, pos)? == *value =>
125 {
126 return Ok(true);
127 }
128 MapValueState::Valid | MapValueState::Deleted => pos = self.next_pos(pos),
129 }
130 }
131 }
132
133 pub fn insert(&mut self, storage: &mut Storage<D>, key: &K, value: &T) -> Result<(), DbError> {
134 let id = self.data.transaction(storage);
135 let index = self.free_index(storage, key)?;
136 self.do_insert(storage, index, key, value)?;
137 self.data.commit(storage, id)
138 }
139
140 pub fn insert_or_replace<P: Fn(&T) -> bool>(
141 &mut self,
142 storage: &mut Storage<D>,
143 key: &K,
144 predicate: P,
145 new_value: &T,
146 ) -> Result<Option<T>, DbError> {
147 let id = self.data.transaction(storage);
148
149 if self.len() >= self.max_len() {
150 self.rehash(storage, self.capacity() * 2)?;
151 }
152
153 let hash = key.stable_hash();
154 let mut pos = hash % self.capacity();
155 let mut free_pos = None;
156 let mut ret = None;
157
158 loop {
159 match self.data.state(storage, pos)? {
160 MapValueState::Empty => {
161 free_pos = Some(pos);
162 break;
163 }
164 MapValueState::Deleted => {
165 if free_pos.is_none() {
166 free_pos = Some(pos);
167 }
168 }
169 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
170 let old_value = self.data.value(storage, pos)?;
171 if predicate(&old_value) {
172 self.data.set_value(storage, pos, new_value)?;
173 ret = Some(old_value);
174 free_pos = None;
175 break;
176 }
177 }
178 MapValueState::Valid => {}
179 }
180
181 pos = self.next_pos(pos)
182 }
183
184 if let Some(pos) = free_pos {
185 self.do_insert(storage, pos, key, new_value)?;
186 }
187
188 self.data.commit(storage, id)?;
189 Ok(ret)
190 }
191
192 pub fn is_empty(&self) -> bool {
193 self.len() == 0
194 }
195
196 pub fn iter<'a>(&'a self, storage: &'a Storage<D>) -> MapIterator<'a, K, T, D, Data> {
197 MapIterator {
198 pos: 0,
199 data: &self.data,
200 storage,
201 phantom_data: PhantomData,
202 }
203 }
204
205 #[allow(dead_code)]
206 pub fn iter_key<'a>(
207 &'a self,
208 storage: &'a Storage<D>,
209 key: &'a K,
210 ) -> MultiMapIterator<'a, K, T, D, Data> {
211 let pos = if self.capacity() == 0 {
212 0
213 } else {
214 key.stable_hash() % self.capacity()
215 };
216
217 MultiMapIterator {
218 pos,
219 key,
220 data: &self.data,
221 storage,
222 phantom_data: PhantomData,
223 }
224 }
225
226 pub fn len(&self) -> u64 {
227 self.data.len()
228 }
229
230 pub fn remove_key(&mut self, storage: &mut Storage<D>, key: &K) -> Result<(), DbError> {
231 if self.capacity() == 0 {
232 return Ok(());
233 }
234
235 let hash = key.stable_hash();
236 let mut pos = hash % self.capacity();
237 let start_pos = pos;
238 let mut len = self.len();
239
240 let id = self.data.transaction(storage);
241
242 loop {
243 match self.data.state(storage, pos)? {
244 MapValueState::Empty => break,
245 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
246 self.drop_value(storage, pos)?;
247 len -= 1;
248 }
249 MapValueState::Valid | MapValueState::Deleted => {}
250 }
251
252 pos = self.next_pos(pos);
253
254 if pos == start_pos {
255 if len == self.len() {
256 self.rehash(storage, self.capacity())?;
257 }
258 break;
259 }
260 }
261
262 if len != self.len() {
263 self.data.set_len(storage, len)?;
264
265 if self.len() <= self.min_len() {
266 self.rehash(storage, self.capacity() / 2)?;
267 }
268 }
269
270 self.data.commit(storage, id)
271 }
272
273 pub fn remove_value(
274 &mut self,
275 storage: &mut Storage<D>,
276 key: &K,
277 value: &T,
278 ) -> Result<(), DbError> {
279 if self.capacity() == 0 {
280 return Ok(());
281 }
282
283 let hash = key.stable_hash();
284 let mut pos = hash % self.capacity();
285 let start_pos = pos;
286 let id = self.data.transaction(storage);
287
288 loop {
289 match self.data.state(storage, pos)? {
290 MapValueState::Empty => break,
291 MapValueState::Valid
292 if self.data.key(storage, pos)? == *key
293 && self.data.value(storage, pos)? == *value =>
294 {
295 self.remove_index(storage, pos)?;
296 break;
297 }
298 MapValueState::Valid | MapValueState::Deleted => pos = self.next_pos(pos),
299 }
300
301 if pos == start_pos {
302 self.rehash(storage, self.capacity())?;
303 break;
304 }
305 }
306
307 self.data.commit(storage, id)
308 }
309
310 pub fn remove_from_storage(self, storage: &mut Storage<D>) -> Result<(), DbError> {
311 self.data.remove_from_storage(storage)
312 }
313
314 pub fn reserve(&mut self, storage: &mut Storage<D>, capacity: u64) -> Result<(), DbError> {
315 if self.capacity() < capacity {
316 self.rehash(storage, capacity)?;
317 }
318
319 Ok(())
320 }
321
322 pub fn value(&self, storage: &Storage<D>, key: &K) -> Result<Option<T>, DbError> {
323 if self.capacity() == 0 {
324 return Ok(None);
325 }
326
327 let hash = key.stable_hash();
328 let mut pos = hash % self.capacity();
329
330 loop {
331 match self.data.state(storage, pos)? {
332 MapValueState::Empty => {
333 return Ok(None);
334 }
335 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
336 return Ok(Some(self.data.value(storage, pos)?));
337 }
338 MapValueState::Valid | MapValueState::Deleted => pos = self.next_pos(pos),
339 }
340 }
341 }
342
343 pub fn values(&self, storage: &Storage<D>, key: &K) -> Result<Vec<T>, DbError> {
344 if self.capacity() == 0 {
345 return Ok(vec![]);
346 }
347
348 let hash = key.stable_hash();
349 let mut pos = hash % self.capacity();
350 let mut values = Vec::<T>::new();
351
352 loop {
353 match self.data.state(storage, pos)? {
354 MapValueState::Empty => break,
355 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
356 values.push(self.data.value(storage, pos)?)
357 }
358 MapValueState::Valid | MapValueState::Deleted => {}
359 }
360
361 pos = self.next_pos(pos)
362 }
363
364 Ok(values)
365 }
366
367 #[allow(dead_code)]
368 pub fn values_count(&self, storage: &Storage<D>, key: &K) -> Result<u64, DbError> {
369 if self.capacity() == 0 {
370 return Ok(0);
371 }
372
373 let hash = key.stable_hash();
374 let mut pos = hash % self.capacity();
375 let mut result = 0;
376
377 loop {
378 match self.data.state(storage, pos)? {
379 MapValueState::Empty => break,
380 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
381 result += 1;
382 }
383 MapValueState::Valid | MapValueState::Deleted => {}
384 }
385
386 pos = self.next_pos(pos)
387 }
388
389 Ok(result)
390 }
391
392 fn do_insert(
393 &mut self,
394 storage: &mut Storage<D>,
395 index: u64,
396 key: &K,
397 value: &T,
398 ) -> Result<(), DbError> {
399 self.data.set_state(storage, index, MapValueState::Valid)?;
400 self.data.set_key(storage, index, key)?;
401 self.data.set_value(storage, index, value)?;
402 self.data.set_len(storage, self.len() + 1)
403 }
404
405 fn drop_value(&mut self, storage: &mut Storage<D>, pos: u64) -> Result<(), DbError> {
406 self.data.set_state(storage, pos, MapValueState::Deleted)?;
407 self.data.set_key(storage, pos, &K::default())?;
408 self.data.set_value(storage, pos, &T::default())
409 }
410
411 fn free_index(&mut self, storage: &mut Storage<D>, key: &K) -> Result<u64, DbError> {
412 if self.len() >= self.max_len() {
413 self.rehash(storage, self.capacity() * 2)?;
414 }
415
416 let hash = key.stable_hash();
417 let mut pos = hash % self.capacity();
418
419 loop {
420 match self.data.state(storage, pos)? {
421 MapValueState::Empty | MapValueState::Deleted => break,
422 MapValueState::Valid => pos = self.next_pos(pos),
423 }
424 }
425
426 Ok(pos)
427 }
428
429 fn grow(
430 &mut self,
431 storage: &mut Storage<D>,
432 current_capacity: u64,
433 new_capacity: u64,
434 ) -> Result<(), DbError> {
435 self.data.resize(storage, new_capacity)?;
436 self.rehash_values(storage, current_capacity, new_capacity)
437 }
438
439 fn max_len(&self) -> u64 {
440 self.capacity() * 15 / 16
441 }
442
443 fn min_len(&self) -> u64 {
444 self.capacity() * 7 / 16
445 }
446
447 fn next_pos(&self, pos: u64) -> u64 {
448 if pos == self.capacity() - 1 {
449 0
450 } else {
451 pos + 1
452 }
453 }
454
455 fn rehash(&mut self, storage: &mut Storage<D>, capacity: u64) -> Result<(), DbError> {
456 let current_capacity = self.capacity();
457 let new_capacity = std::cmp::max(capacity, 64_u64);
458
459 match current_capacity.cmp(&new_capacity) {
460 std::cmp::Ordering::Less => self.grow(storage, current_capacity, new_capacity),
461 std::cmp::Ordering::Greater => self.shrink(storage, current_capacity, new_capacity),
462 std::cmp::Ordering::Equal => Ok(()),
463 }
464 }
465
466 fn rehash_deleted(
467 &mut self,
468 storage: &mut Storage<D>,
469 i: &mut u64,
470 new_capacity: u64,
471 ) -> Result<(), DbError> {
472 if *i < new_capacity {
473 self.data.set_state(storage, *i, MapValueState::Empty)?;
474 }
475
476 *i += 1;
477 Ok(())
478 }
479
480 fn rehash_empty(&mut self, i: &mut u64) -> Result<(), DbError> {
481 *i += 1;
482 Ok(())
483 }
484
485 fn rehash_valid(
486 &mut self,
487 storage: &mut Storage<D>,
488 i: &mut u64,
489 new_capacity: u64,
490 occupancy: &mut BitSet,
491 ) -> Result<(), DbError> {
492 if *i < new_capacity && occupancy.value(*i) {
493 *i += 1;
494 return Ok(());
495 }
496
497 let key = self.data.key(storage, *i)?;
498 let hash = key.stable_hash();
499 let mut pos = hash % new_capacity;
500
501 loop {
502 if !occupancy.value(pos) {
503 occupancy.set(pos);
504 self.data.swap(storage, *i, pos)?;
505
506 if *i == pos {
507 *i += 1;
508 }
509
510 break;
511 }
512
513 pos += 1;
514
515 if pos == new_capacity {
516 pos = 0;
517 }
518 }
519
520 Ok(())
521 }
522
523 fn rehash_value(
524 &mut self,
525 storage: &mut Storage<D>,
526 state: MapValueState,
527 i: &mut u64,
528 new_capacity: u64,
529 occupancy: &mut BitSet,
530 ) -> Result<(), DbError> {
531 match state {
532 MapValueState::Empty => self.rehash_empty(i),
533 MapValueState::Deleted => self.rehash_deleted(storage, i, new_capacity),
534 MapValueState::Valid => self.rehash_valid(storage, i, new_capacity, occupancy),
535 }
536 }
537
538 fn rehash_values(
539 &mut self,
540 storage: &mut Storage<D>,
541 current_capacity: u64,
542 new_capacity: u64,
543 ) -> Result<(), DbError> {
544 let mut i = 0_u64;
545 let mut occupancy = BitSet::with_capacity(new_capacity);
546
547 while i != current_capacity {
548 let state = self.data.state(storage, i)?;
549 self.rehash_value(storage, state, &mut i, new_capacity, &mut occupancy)?;
550 }
551
552 Ok(())
553 }
554
555 fn remove_index(&mut self, storage: &mut Storage<D>, index: u64) -> Result<(), DbError> {
556 self.drop_value(storage, index)?;
557 self.data.set_len(storage, self.len() - 1)?;
558
559 if self.len() <= self.min_len() {
560 self.rehash(storage, self.capacity() / 2)?;
561 }
562
563 Ok(())
564 }
565
566 fn shrink(
567 &mut self,
568 storage: &mut Storage<D>,
569 current_capacity: u64,
570 new_capacity: u64,
571 ) -> Result<(), DbError> {
572 self.rehash_values(storage, current_capacity, new_capacity)?;
573 self.data.resize(storage, new_capacity)
574 }
575}
576
577pub type MultiMapStorage<K, T, D> = MultiMapImpl<K, T, D, DbMapData<K, T, D>>;
578
579impl<K, T, D> MultiMapStorage<K, T, D>
580where
581 K: Clone + Default + PartialEq + VecValue<D>,
582 T: Clone + Default + PartialEq + VecValue<D>,
583 D: StorageData,
584{
585 pub fn new(storage: &mut Storage<D>) -> Result<Self, DbError> {
586 Ok(Self {
587 data: DbMapData::<K, T, D>::new(storage)?,
588 phantom_marker: PhantomData,
589 })
590 }
591
592 pub fn from_storage(storage: &Storage<D>, index: StorageIndex) -> Result<Self, DbError> {
593 Ok(Self {
594 data: DbMapData::<K, T, D>::from_storage(storage, index)?,
595 phantom_marker: PhantomData,
596 })
597 }
598
599 pub fn storage_index(&self) -> StorageIndex {
600 self.data.storage_index()
601 }
602}
603
604#[cfg(test)]
605mod tests {
606 use super::*;
607 use crate::MemoryStorage;
608 use crate::storage::file_storage_memory_mapped::FileStorageMemoryMapped;
609 use crate::test_utilities::test_file::TestFile;
610
611 #[test]
612 fn new() {
613 let test_file = TestFile::new();
614 let mut storage = Storage::new(test_file.file_name()).unwrap();
615 let mut map =
616 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
617 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
618 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
619 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
620
621 let mut values = Vec::<(u64, String)>::with_capacity(3);
622
623 for (key, value) in map.iter(&storage) {
624 values.push((key, value));
625 }
626
627 values.sort();
628
629 assert_eq!(
630 values,
631 vec![
632 (1, "!".to_string()),
633 (1, "Hello".to_string()),
634 (1, "World".to_string())
635 ]
636 );
637 }
638
639 #[test]
640 fn iter_key() {
641 let test_file = TestFile::new();
642 let mut storage = Storage::new(test_file.file_name()).unwrap();
643 let mut map =
644 MultiMapStorage::<u64, u64, FileStorageMemoryMapped>::new(&mut storage).unwrap();
645
646 assert_eq!(map.iter_key(&storage, &1).count(), 0);
647
648 map.insert(&mut storage, &3, &30).unwrap();
649 map.insert(&mut storage, &1, &10).unwrap();
650 map.insert(&mut storage, &1, &20).unwrap();
651 map.insert(&mut storage, &1, &30).unwrap();
652 map.insert(&mut storage, &4, &40).unwrap();
653 map.remove_value(&mut storage, &1, &10).unwrap();
654
655 let value = map.iter_key(&storage, &1).find(|v| v.1 == 20).unwrap();
656 assert_eq!(value, (1, 20));
657
658 let mut values = Vec::<(u64, u64)>::with_capacity(2);
659
660 for (key, value) in map.iter_key(&storage, &1) {
661 values.push((key, value));
662 }
663
664 values.sort();
665
666 assert_eq!(values, vec![(1, 20), (1, 30)]);
667 }
668
669 #[test]
670 fn remove_value_empty_map() {
671 let test_file = TestFile::new();
672 let mut storage = Storage::new(test_file.file_name()).unwrap();
673 let mut map =
674 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
675
676 assert!(
677 map.remove_value(&mut storage, &10, &"Hello".to_string())
678 .is_ok()
679 );
680 }
681
682 #[test]
683 fn remove_missing_value() {
684 let test_file = TestFile::new();
685 let mut storage = Storage::new(test_file.file_name()).unwrap();
686 let mut map =
687 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
688 map.insert(&mut storage, &11, &"Hello".to_string()).unwrap();
689
690 assert!(
691 map.remove_value(&mut storage, &10, &"Hello".to_string())
692 .is_ok()
693 );
694 }
695
696 #[test]
697 fn remove_value_shrinks_capacity() {
698 let test_file = TestFile::new();
699 let mut storage = Storage::new(test_file.file_name()).unwrap();
700 let mut map =
701 MultiMapStorage::<u64, u64, FileStorageMemoryMapped>::new(&mut storage).unwrap();
702
703 for i in 0..100 {
704 map.insert(&mut storage, &i, &i).unwrap();
705 }
706
707 assert_eq!(map.len(), 100);
708 assert_eq!(map.capacity(), 128);
709
710 for i in (0..100).rev() {
711 map.remove_value(&mut storage, &i, &i).unwrap();
712 }
713
714 assert_eq!(map.len(), 0);
715 assert_eq!(map.capacity(), 64);
716 }
717
718 #[test]
719 fn replace_empty_map() {
720 let test_file = TestFile::new();
721 let mut storage = Storage::new(test_file.file_name()).unwrap();
722 let mut map =
723 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
724 let p = |v: &String| v == "Hello";
725 assert!(
726 map.insert_or_replace(&mut storage, &10, p, &"World".to_string())
727 .is_ok()
728 );
729 p(&"".to_string());
730 }
731
732 #[test]
733 fn replace_missing_value() {
734 let test_file = TestFile::new();
735 let mut storage = Storage::new(test_file.file_name()).unwrap();
736 let mut map =
737 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
738 map.insert(&mut storage, &10, &"World".to_string()).unwrap();
739 map.insert(&mut storage, &11, &"Hello".to_string()).unwrap();
740
741 assert!(
742 map.insert_or_replace(&mut storage, &10, |v| v == "Hello", &"World".to_string())
743 .is_ok()
744 );
745 }
746
747 #[test]
748 fn replace_deleted() {
749 let test_file = TestFile::new();
750 let mut storage = Storage::new(test_file.file_name()).unwrap();
751 let mut map =
752 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
753 map.insert(&mut storage, &10, &"Hello".to_string()).unwrap();
754 map.insert(&mut storage, &10, &"World".to_string()).unwrap();
755 map.remove_value(&mut storage, &10, &"Hello".to_string())
756 .unwrap();
757
758 assert!(
759 map.insert_or_replace(&mut storage, &10, |v| v == "Hello", &"World".to_string())
760 .is_ok()
761 );
762 }
763
764 #[test]
765 fn values_count() {
766 let test_file = TestFile::new();
767 let mut storage = Storage::new(test_file.file_name()).unwrap();
768
769 let mut map =
770 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
771
772 assert_eq!(map.values_count(&storage, &4), Ok(0));
773
774 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
775 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
776 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
777 map.insert(&mut storage, &2, &"a".to_string()).unwrap();
778 map.insert(&mut storage, &3, &"b".to_string()).unwrap();
779 map.remove_value(&mut storage, &1, &"World".to_string())
780 .unwrap();
781
782 assert_eq!(map.values_count(&storage, &1), Ok(2));
783 assert_eq!(map.values_count(&storage, &2), Ok(1));
784 assert_eq!(map.values_count(&storage, &3), Ok(1));
785 assert_eq!(map.values_count(&storage, &4), Ok(0));
786 }
787
788 #[test]
789 fn from_storage() {
790 let test_file = TestFile::new();
791 let mut storage = Storage::new(test_file.file_name()).unwrap();
792
793 let storage_index;
794
795 {
796 let mut map =
797 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
798 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
799 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
800 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
801 storage_index = map.storage_index();
802 }
803
804 let map = MultiMapStorage::<u64, String, FileStorageMemoryMapped>::from_storage(
805 &storage,
806 storage_index,
807 )
808 .unwrap();
809
810 let mut values = Vec::<(u64, String)>::with_capacity(3);
811
812 for (key, value) in map.iter(&storage) {
813 values.push((key, value));
814 }
815
816 values.sort();
817
818 assert_eq!(
819 values,
820 vec![
821 (1, "!".to_string()),
822 (1, "Hello".to_string()),
823 (1, "World".to_string())
824 ]
825 );
826 }
827
828 #[test]
829 fn remove_from_storage() {
830 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
831 let mut map = MultiMapStorage::<String, String, MemoryStorage>::new(&mut storage).unwrap();
832
833 map.insert(
834 &mut storage,
835 &"key".to_string(),
836 &"This is a long string that does not fit into small value".to_string(),
837 )
838 .unwrap();
839
840 map.insert(
841 &mut storage,
842 &"key".to_string(),
843 &"Some other value that is also longish".to_string(),
844 )
845 .unwrap();
846
847 map.remove_from_storage(&mut storage).unwrap();
848 let len = storage.len();
849 storage.shrink_to_fit().unwrap();
850 assert!(storage.len() < len)
851 }
852
853 #[test]
854 fn empty_pos_after_rehash() {
855 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
856 let mut map = MultiMapStorage::<String, String, MemoryStorage>::new(&mut storage).unwrap();
857 let range = 1..200;
858
859 let users: Vec<(String, String)> = range
860 .clone()
861 .rev()
862 .map(|i| (format!("db_user{i}"), i.to_string()))
863 .collect();
864
865 for (user, value) in users {
866 map.insert(&mut storage, &user, &value).unwrap();
867 }
868
869 for i in range {
870 let value = map.value(&storage, &format!("db_user{i}")).unwrap();
871 assert_eq!(value, Some(i.to_string()));
872 }
873 }
874
875 #[test]
876 fn deadlock_test_key() {
877 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
878 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
879
880 for i in 0_u64..60 {
881 map.insert(&mut storage, &i, &i).unwrap();
882 }
883
884 map.remove_key(&mut storage, &0).unwrap();
885 map.remove_key(&mut storage, &1).unwrap();
886 map.remove_key(&mut storage, &2).unwrap();
887 map.remove_key(&mut storage, &3).unwrap();
888
889 map.insert(&mut storage, &60, &60).unwrap();
890 map.insert(&mut storage, &61, &61).unwrap();
891 map.insert(&mut storage, &62, &62).unwrap();
892 map.insert(&mut storage, &63, &63).unwrap();
893
894 map.remove_key(&mut storage, &32).unwrap();
895 map.remove_key(&mut storage, &0).unwrap();
896 }
897
898 #[test]
899 fn deadlock_test_value() {
900 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
901 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
902
903 for i in 0_u64..60 {
904 map.insert(&mut storage, &i, &i).unwrap();
905 }
906
907 map.remove_key(&mut storage, &0).unwrap();
908 map.remove_key(&mut storage, &1).unwrap();
909 map.remove_key(&mut storage, &2).unwrap();
910 map.remove_key(&mut storage, &3).unwrap();
911
912 map.insert(&mut storage, &60, &60).unwrap();
913 map.insert(&mut storage, &61, &61).unwrap();
914 map.insert(&mut storage, &62, &62).unwrap();
915 map.insert(&mut storage, &63, &63).unwrap();
916
917 map.remove_value(&mut storage, &32, &32).unwrap();
918 map.remove_value(&mut storage, &32, &0).unwrap();
919 }
920
921 #[test]
922 fn iterate_over_deleted() {
923 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
924 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
925
926 for i in 0_u64..20 {
927 map.insert(&mut storage, &i, &i).unwrap();
928 map.insert(&mut storage, &i, &(i + 1)).unwrap();
929 map.insert(&mut storage, &i, &(i + 2)).unwrap();
930 }
931
932 map.remove_value(&mut storage, &10, &10).unwrap();
933 map.remove_value(&mut storage, &10, &11).unwrap();
934
935 assert!(map.contains(&storage, &10).unwrap());
936 assert!(map.contains_value(&storage, &10, &12).unwrap());
937
938 let values = map.iter(&storage).collect::<Vec<(u64, u64)>>();
939
940 assert!(!values.contains(&(10, 10)));
941 assert!(!values.contains(&(10, 11)));
942 assert!(values.contains(&(10, 12)));
943
944 let keys = map.iter_key(&storage, &10).collect::<Vec<(u64, u64)>>();
945 assert_eq!(keys, vec![(10, 12)]);
946 }
947
948 #[test]
949 fn insert_or_replace_over_deleted() {
950 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
951 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
952
953 map.insert(&mut storage, &1, &10).unwrap();
954 map.insert(&mut storage, &1, &20).unwrap();
955 map.insert(&mut storage, &1, &21).unwrap();
956 map.insert(&mut storage, &1, &30).unwrap();
957
958 map.remove_value(&mut storage, &1, &20).unwrap();
959 map.remove_value(&mut storage, &1, &21).unwrap();
960
961 map.insert_or_replace(&mut storage, &1, |v| *v == 30, &30)
962 .unwrap();
963
964 let values = map.values(&storage, &1).unwrap();
965
966 assert_eq!(values, vec![10, 30]);
967 }
968}