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 shrink_to_fit(&mut self, storage: &mut Storage<D>) -> Result<(), DbError> {
323 self.data.shrink_to_fit(storage)
324 }
325
326 pub fn value(&self, storage: &Storage<D>, key: &K) -> Result<Option<T>, DbError> {
327 if self.capacity() == 0 {
328 return Ok(None);
329 }
330
331 let hash = key.stable_hash();
332 let mut pos = hash % self.capacity();
333
334 loop {
335 match self.data.state(storage, pos)? {
336 MapValueState::Empty => {
337 return Ok(None);
338 }
339 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
340 return Ok(Some(self.data.value(storage, pos)?));
341 }
342 MapValueState::Valid | MapValueState::Deleted => pos = self.next_pos(pos),
343 }
344 }
345 }
346
347 pub fn values(&self, storage: &Storage<D>, key: &K) -> Result<Vec<T>, DbError> {
348 if self.capacity() == 0 {
349 return Ok(vec![]);
350 }
351
352 let hash = key.stable_hash();
353 let mut pos = hash % self.capacity();
354 let mut values = Vec::<T>::new();
355
356 loop {
357 match self.data.state(storage, pos)? {
358 MapValueState::Empty => break,
359 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
360 values.push(self.data.value(storage, pos)?)
361 }
362 MapValueState::Valid | MapValueState::Deleted => {}
363 }
364
365 pos = self.next_pos(pos)
366 }
367
368 Ok(values)
369 }
370
371 #[allow(dead_code)]
372 pub fn values_count(&self, storage: &Storage<D>, key: &K) -> Result<u64, DbError> {
373 if self.capacity() == 0 {
374 return Ok(0);
375 }
376
377 let hash = key.stable_hash();
378 let mut pos = hash % self.capacity();
379 let mut result = 0;
380
381 loop {
382 match self.data.state(storage, pos)? {
383 MapValueState::Empty => break,
384 MapValueState::Valid if self.data.key(storage, pos)? == *key => {
385 result += 1;
386 }
387 MapValueState::Valid | MapValueState::Deleted => {}
388 }
389
390 pos = self.next_pos(pos)
391 }
392
393 Ok(result)
394 }
395
396 fn do_insert(
397 &mut self,
398 storage: &mut Storage<D>,
399 index: u64,
400 key: &K,
401 value: &T,
402 ) -> Result<(), DbError> {
403 self.data.set_state(storage, index, MapValueState::Valid)?;
404 self.data.set_key(storage, index, key)?;
405 self.data.set_value(storage, index, value)?;
406 self.data.set_len(storage, self.len() + 1)
407 }
408
409 fn drop_value(&mut self, storage: &mut Storage<D>, pos: u64) -> Result<(), DbError> {
410 self.data.set_state(storage, pos, MapValueState::Deleted)?;
411 self.data.set_key(storage, pos, &K::default())?;
412 self.data.set_value(storage, pos, &T::default())
413 }
414
415 fn free_index(&mut self, storage: &mut Storage<D>, key: &K) -> Result<u64, DbError> {
416 if self.len() >= self.max_len() {
417 self.rehash(storage, self.capacity() * 2)?;
418 }
419
420 let hash = key.stable_hash();
421 let mut pos = hash % self.capacity();
422
423 loop {
424 match self.data.state(storage, pos)? {
425 MapValueState::Empty | MapValueState::Deleted => break,
426 MapValueState::Valid => pos = self.next_pos(pos),
427 }
428 }
429
430 Ok(pos)
431 }
432
433 fn grow(
434 &mut self,
435 storage: &mut Storage<D>,
436 current_capacity: u64,
437 new_capacity: u64,
438 ) -> Result<(), DbError> {
439 self.data.resize(storage, new_capacity)?;
440 self.rehash_values(storage, current_capacity, new_capacity)
441 }
442
443 fn max_len(&self) -> u64 {
444 self.capacity() * 15 / 16
445 }
446
447 fn min_len(&self) -> u64 {
448 self.capacity() * 7 / 16
449 }
450
451 fn next_pos(&self, pos: u64) -> u64 {
452 if pos == self.capacity() - 1 {
453 0
454 } else {
455 pos + 1
456 }
457 }
458
459 fn rehash(&mut self, storage: &mut Storage<D>, capacity: u64) -> Result<(), DbError> {
460 let current_capacity = self.capacity();
461 let new_capacity = std::cmp::max(capacity, 64_u64);
462
463 match current_capacity.cmp(&new_capacity) {
464 std::cmp::Ordering::Less => self.grow(storage, current_capacity, new_capacity),
465 std::cmp::Ordering::Greater => self.shrink(storage, current_capacity, new_capacity),
466 std::cmp::Ordering::Equal => Ok(()),
467 }
468 }
469
470 fn rehash_deleted(
471 &mut self,
472 storage: &mut Storage<D>,
473 i: &mut u64,
474 new_capacity: u64,
475 ) -> Result<(), DbError> {
476 if *i < new_capacity {
477 self.data.set_state(storage, *i, MapValueState::Empty)?;
478 }
479
480 *i += 1;
481 Ok(())
482 }
483
484 fn rehash_empty(&mut self, i: &mut u64) -> Result<(), DbError> {
485 *i += 1;
486 Ok(())
487 }
488
489 fn rehash_valid(
490 &mut self,
491 storage: &mut Storage<D>,
492 i: &mut u64,
493 new_capacity: u64,
494 occupancy: &mut BitSet,
495 ) -> Result<(), DbError> {
496 if *i < new_capacity && occupancy.value(*i) {
497 *i += 1;
498 return Ok(());
499 }
500
501 let key = self.data.key(storage, *i)?;
502 let hash = key.stable_hash();
503 let mut pos = hash % new_capacity;
504
505 loop {
506 if !occupancy.value(pos) {
507 occupancy.set(pos);
508 self.data.swap(storage, *i, pos)?;
509
510 if *i == pos {
511 *i += 1;
512 }
513
514 break;
515 }
516
517 pos += 1;
518
519 if pos == new_capacity {
520 pos = 0;
521 }
522 }
523
524 Ok(())
525 }
526
527 fn rehash_value(
528 &mut self,
529 storage: &mut Storage<D>,
530 state: MapValueState,
531 i: &mut u64,
532 new_capacity: u64,
533 occupancy: &mut BitSet,
534 ) -> Result<(), DbError> {
535 match state {
536 MapValueState::Empty => self.rehash_empty(i),
537 MapValueState::Deleted => self.rehash_deleted(storage, i, new_capacity),
538 MapValueState::Valid => self.rehash_valid(storage, i, new_capacity, occupancy),
539 }
540 }
541
542 fn rehash_values(
543 &mut self,
544 storage: &mut Storage<D>,
545 current_capacity: u64,
546 new_capacity: u64,
547 ) -> Result<(), DbError> {
548 let mut i = 0_u64;
549 let mut occupancy = BitSet::with_capacity(new_capacity);
550
551 while i != current_capacity {
552 let state = self.data.state(storage, i)?;
553 self.rehash_value(storage, state, &mut i, new_capacity, &mut occupancy)?;
554 }
555
556 Ok(())
557 }
558
559 fn remove_index(&mut self, storage: &mut Storage<D>, index: u64) -> Result<(), DbError> {
560 self.drop_value(storage, index)?;
561 self.data.set_len(storage, self.len() - 1)?;
562
563 if self.len() <= self.min_len() {
564 self.rehash(storage, self.capacity() / 2)?;
565 }
566
567 Ok(())
568 }
569
570 fn shrink(
571 &mut self,
572 storage: &mut Storage<D>,
573 current_capacity: u64,
574 new_capacity: u64,
575 ) -> Result<(), DbError> {
576 self.rehash_values(storage, current_capacity, new_capacity)?;
577 self.data.resize(storage, new_capacity)
578 }
579}
580
581pub type MultiMapStorage<K, T, D> = MultiMapImpl<K, T, D, DbMapData<K, T, D>>;
582
583impl<K, T, D> MultiMapStorage<K, T, D>
584where
585 K: Clone + Default + PartialEq + VecValue<D>,
586 T: Clone + Default + PartialEq + VecValue<D>,
587 D: StorageData,
588{
589 pub fn new(storage: &mut Storage<D>) -> Result<Self, DbError> {
590 Ok(Self {
591 data: DbMapData::<K, T, D>::new(storage)?,
592 phantom_marker: PhantomData,
593 })
594 }
595
596 pub fn from_storage(storage: &Storage<D>, index: StorageIndex) -> Result<Self, DbError> {
597 Ok(Self {
598 data: DbMapData::<K, T, D>::from_storage(storage, index)?,
599 phantom_marker: PhantomData,
600 })
601 }
602
603 pub fn storage_index(&self) -> StorageIndex {
604 self.data.storage_index()
605 }
606}
607
608#[cfg(test)]
609mod tests {
610 use super::*;
611 use crate::MemoryStorage;
612 use crate::storage::file_storage_memory_mapped::FileStorageMemoryMapped;
613 use crate::test_utilities::test_file::TestFile;
614
615 #[test]
616 fn new() {
617 let test_file = TestFile::new();
618 let mut storage = Storage::new(test_file.file_name()).unwrap();
619 let mut map =
620 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
621 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
622 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
623 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
624
625 let mut values = Vec::<(u64, String)>::with_capacity(3);
626
627 for (key, value) in map.iter(&storage) {
628 values.push((key, value));
629 }
630
631 values.sort();
632
633 assert_eq!(
634 values,
635 vec![
636 (1, "!".to_string()),
637 (1, "Hello".to_string()),
638 (1, "World".to_string())
639 ]
640 );
641 }
642
643 #[test]
644 fn iter_key() {
645 let test_file = TestFile::new();
646 let mut storage = Storage::new(test_file.file_name()).unwrap();
647 let mut map =
648 MultiMapStorage::<u64, u64, FileStorageMemoryMapped>::new(&mut storage).unwrap();
649
650 assert_eq!(map.iter_key(&storage, &1).count(), 0);
651
652 map.insert(&mut storage, &3, &30).unwrap();
653 map.insert(&mut storage, &1, &10).unwrap();
654 map.insert(&mut storage, &1, &20).unwrap();
655 map.insert(&mut storage, &1, &30).unwrap();
656 map.insert(&mut storage, &4, &40).unwrap();
657 map.remove_value(&mut storage, &1, &10).unwrap();
658
659 let value = map.iter_key(&storage, &1).find(|v| v.1 == 20).unwrap();
660 assert_eq!(value, (1, 20));
661
662 let mut values = Vec::<(u64, u64)>::with_capacity(2);
663
664 for (key, value) in map.iter_key(&storage, &1) {
665 values.push((key, value));
666 }
667
668 values.sort();
669
670 assert_eq!(values, vec![(1, 20), (1, 30)]);
671 }
672
673 #[test]
674 fn remove_value_empty_map() {
675 let test_file = TestFile::new();
676 let mut storage = Storage::new(test_file.file_name()).unwrap();
677 let mut map =
678 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
679
680 assert!(
681 map.remove_value(&mut storage, &10, &"Hello".to_string())
682 .is_ok()
683 );
684 }
685
686 #[test]
687 fn remove_missing_value() {
688 let test_file = TestFile::new();
689 let mut storage = Storage::new(test_file.file_name()).unwrap();
690 let mut map =
691 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
692 map.insert(&mut storage, &11, &"Hello".to_string()).unwrap();
693
694 assert!(
695 map.remove_value(&mut storage, &10, &"Hello".to_string())
696 .is_ok()
697 );
698 }
699
700 #[test]
701 fn remove_value_shrinks_capacity() {
702 let test_file = TestFile::new();
703 let mut storage = Storage::new(test_file.file_name()).unwrap();
704 let mut map =
705 MultiMapStorage::<u64, u64, FileStorageMemoryMapped>::new(&mut storage).unwrap();
706
707 for i in 0..100 {
708 map.insert(&mut storage, &i, &i).unwrap();
709 }
710
711 assert_eq!(map.len(), 100);
712 assert_eq!(map.capacity(), 128);
713
714 for i in (0..100).rev() {
715 map.remove_value(&mut storage, &i, &i).unwrap();
716 }
717
718 assert_eq!(map.len(), 0);
719 assert_eq!(map.capacity(), 64);
720 }
721
722 #[test]
723 fn replace_empty_map() {
724 let test_file = TestFile::new();
725 let mut storage = Storage::new(test_file.file_name()).unwrap();
726 let mut map =
727 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
728 let p = |v: &String| v == "Hello";
729 assert!(
730 map.insert_or_replace(&mut storage, &10, p, &"World".to_string())
731 .is_ok()
732 );
733 p(&"".to_string());
734 }
735
736 #[test]
737 fn replace_missing_value() {
738 let test_file = TestFile::new();
739 let mut storage = Storage::new(test_file.file_name()).unwrap();
740 let mut map =
741 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
742 map.insert(&mut storage, &10, &"World".to_string()).unwrap();
743 map.insert(&mut storage, &11, &"Hello".to_string()).unwrap();
744
745 assert!(
746 map.insert_or_replace(&mut storage, &10, |v| v == "Hello", &"World".to_string())
747 .is_ok()
748 );
749 }
750
751 #[test]
752 fn replace_deleted() {
753 let test_file = TestFile::new();
754 let mut storage = Storage::new(test_file.file_name()).unwrap();
755 let mut map =
756 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
757 map.insert(&mut storage, &10, &"Hello".to_string()).unwrap();
758 map.insert(&mut storage, &10, &"World".to_string()).unwrap();
759 map.remove_value(&mut storage, &10, &"Hello".to_string())
760 .unwrap();
761
762 assert!(
763 map.insert_or_replace(&mut storage, &10, |v| v == "Hello", &"World".to_string())
764 .is_ok()
765 );
766 }
767
768 #[test]
769 fn values_count() {
770 let test_file = TestFile::new();
771 let mut storage = Storage::new(test_file.file_name()).unwrap();
772
773 let mut map =
774 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
775
776 assert_eq!(map.values_count(&storage, &4), Ok(0));
777
778 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
779 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
780 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
781 map.insert(&mut storage, &2, &"a".to_string()).unwrap();
782 map.insert(&mut storage, &3, &"b".to_string()).unwrap();
783 map.remove_value(&mut storage, &1, &"World".to_string())
784 .unwrap();
785
786 assert_eq!(map.values_count(&storage, &1), Ok(2));
787 assert_eq!(map.values_count(&storage, &2), Ok(1));
788 assert_eq!(map.values_count(&storage, &3), Ok(1));
789 assert_eq!(map.values_count(&storage, &4), Ok(0));
790 }
791
792 #[test]
793 fn from_storage() {
794 let test_file = TestFile::new();
795 let mut storage = Storage::new(test_file.file_name()).unwrap();
796
797 let storage_index;
798
799 {
800 let mut map =
801 MultiMapStorage::<u64, String, FileStorageMemoryMapped>::new(&mut storage).unwrap();
802 map.insert(&mut storage, &1, &"Hello".to_string()).unwrap();
803 map.insert(&mut storage, &1, &"World".to_string()).unwrap();
804 map.insert(&mut storage, &1, &"!".to_string()).unwrap();
805 storage_index = map.storage_index();
806 }
807
808 let map = MultiMapStorage::<u64, String, FileStorageMemoryMapped>::from_storage(
809 &storage,
810 storage_index,
811 )
812 .unwrap();
813
814 let mut values = Vec::<(u64, String)>::with_capacity(3);
815
816 for (key, value) in map.iter(&storage) {
817 values.push((key, value));
818 }
819
820 values.sort();
821
822 assert_eq!(
823 values,
824 vec![
825 (1, "!".to_string()),
826 (1, "Hello".to_string()),
827 (1, "World".to_string())
828 ]
829 );
830 }
831
832 #[test]
833 fn remove_from_storage() {
834 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
835 let mut map = MultiMapStorage::<String, String, MemoryStorage>::new(&mut storage).unwrap();
836
837 map.insert(
838 &mut storage,
839 &"key".to_string(),
840 &"This is a long string that does not fit into small value".to_string(),
841 )
842 .unwrap();
843
844 map.insert(
845 &mut storage,
846 &"key".to_string(),
847 &"Some other value that is also longish".to_string(),
848 )
849 .unwrap();
850
851 map.remove_from_storage(&mut storage).unwrap();
852 let len = storage.len();
853 storage.optimize_storage().unwrap();
854 assert!(storage.len() < len)
855 }
856
857 #[test]
858 fn empty_pos_after_rehash() {
859 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
860 let mut map = MultiMapStorage::<String, String, MemoryStorage>::new(&mut storage).unwrap();
861 let range = 1..200;
862
863 let users: Vec<(String, String)> = range
864 .clone()
865 .rev()
866 .map(|i| (format!("db_user{i}"), i.to_string()))
867 .collect();
868
869 for (user, value) in users {
870 map.insert(&mut storage, &user, &value).unwrap();
871 }
872
873 for i in range {
874 let value = map.value(&storage, &format!("db_user{i}")).unwrap();
875 assert_eq!(value, Some(i.to_string()));
876 }
877 }
878
879 #[test]
880 fn deadlock_test_key() {
881 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
882 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
883
884 for i in 0_u64..60 {
885 map.insert(&mut storage, &i, &i).unwrap();
886 }
887
888 map.remove_key(&mut storage, &0).unwrap();
889 map.remove_key(&mut storage, &1).unwrap();
890 map.remove_key(&mut storage, &2).unwrap();
891 map.remove_key(&mut storage, &3).unwrap();
892
893 map.insert(&mut storage, &60, &60).unwrap();
894 map.insert(&mut storage, &61, &61).unwrap();
895 map.insert(&mut storage, &62, &62).unwrap();
896 map.insert(&mut storage, &63, &63).unwrap();
897
898 map.remove_key(&mut storage, &32).unwrap();
899 map.remove_key(&mut storage, &0).unwrap();
900 }
901
902 #[test]
903 fn deadlock_test_value() {
904 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
905 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
906
907 for i in 0_u64..60 {
908 map.insert(&mut storage, &i, &i).unwrap();
909 }
910
911 map.remove_key(&mut storage, &0).unwrap();
912 map.remove_key(&mut storage, &1).unwrap();
913 map.remove_key(&mut storage, &2).unwrap();
914 map.remove_key(&mut storage, &3).unwrap();
915
916 map.insert(&mut storage, &60, &60).unwrap();
917 map.insert(&mut storage, &61, &61).unwrap();
918 map.insert(&mut storage, &62, &62).unwrap();
919 map.insert(&mut storage, &63, &63).unwrap();
920
921 map.remove_value(&mut storage, &32, &32).unwrap();
922 map.remove_value(&mut storage, &32, &0).unwrap();
923 }
924
925 #[test]
926 fn iterate_over_deleted() {
927 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
928 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
929
930 for i in 0_u64..20 {
931 map.insert(&mut storage, &i, &i).unwrap();
932 map.insert(&mut storage, &i, &(i + 1)).unwrap();
933 map.insert(&mut storage, &i, &(i + 2)).unwrap();
934 }
935
936 map.remove_value(&mut storage, &10, &10).unwrap();
937 map.remove_value(&mut storage, &10, &11).unwrap();
938
939 assert!(map.contains(&storage, &10).unwrap());
940 assert!(map.contains_value(&storage, &10, &12).unwrap());
941
942 let values = map.iter(&storage).collect::<Vec<(u64, u64)>>();
943
944 assert!(!values.contains(&(10, 10)));
945 assert!(!values.contains(&(10, 11)));
946 assert!(values.contains(&(10, 12)));
947
948 let keys = map.iter_key(&storage, &10).collect::<Vec<(u64, u64)>>();
949 assert_eq!(keys, vec![(10, 12)]);
950 }
951
952 #[test]
953 fn insert_or_replace_over_deleted() {
954 let mut storage: Storage<MemoryStorage> = Storage::new("test").unwrap();
955 let mut map = MultiMapStorage::<u64, u64, MemoryStorage>::new(&mut storage).unwrap();
956
957 map.insert(&mut storage, &1, &10).unwrap();
958 map.insert(&mut storage, &1, &20).unwrap();
959 map.insert(&mut storage, &1, &21).unwrap();
960 map.insert(&mut storage, &1, &30).unwrap();
961
962 map.remove_value(&mut storage, &1, &20).unwrap();
963 map.remove_value(&mut storage, &1, &21).unwrap();
964
965 map.insert_or_replace(&mut storage, &1, |v| *v == 30, &30)
966 .unwrap();
967
968 let values = map.values(&storage, &1).unwrap();
969
970 assert_eq!(values, vec![10, 30]);
971 }
972}