coca/collections/list_map.rs
1//! A map based on an [association list](https://en.wikipedia.org/wiki/Association_list).
2
3use core::alloc::{Layout, LayoutError};
4use core::borrow::Borrow;
5use core::fmt::Debug;
6use core::iter::FusedIterator;
7use core::marker::PhantomData;
8use core::mem::MaybeUninit;
9
10use crate::storage::{Capacity, LayoutSpec, Storage};
11
12use self::Entry::{Occupied, Vacant};
13
14/// The [`LayoutSpec`] for a [`ListMap`].
15pub struct ListMapLayout<K, V>(PhantomData<(K, V)>);
16impl<K, V> LayoutSpec for ListMapLayout<K, V> {
17 fn layout_with_capacity(items: usize) -> Result<Layout, LayoutError> {
18 let keys_array = Layout::array::<K>(items)?;
19 let values_array = Layout::array::<V>(items)?;
20 let (extended, _) = keys_array.extend(values_array)?;
21 Ok(extended.pad_to_align())
22 }
23}
24
25/// A map based on an [association list](https://en.wikipedia.org/wiki/Association_list).
26///
27/// Conventionally, this refers to a linked list of key-value pairs, using a
28/// linear scan to find the value associated with a given key. This is simple,
29/// though inefficient, particularly on modern computer architectures, where
30/// traversing each link in the list is likely to cause a cache miss.
31///
32/// For this reason, this implementation uses arrays instead, one for the keys,
33/// one for the values. This way, unrelated values need not be fetched into the
34/// cache during the key lookup. Nonetheless, this search is *O*(*n*), i.e. it
35/// takes time linear in the number of entries, which can be problematic for
36/// large maps.
37///
38/// Newly inserted entries are appended to the arrays, and a removed entry is
39/// replaced by the last one in the list, meaning modifications have constant
40/// overhead after the initial lookup. This also means insertion order is **not**
41/// preserved.
42///
43/// As key search is the primary cost of these operations, care should be taken
44/// to avoid redundant lookups. Use the [`Entry` API](ListMap::try_entry) where
45/// applicable.
46///
47/// It is required that the keys implement the [`Eq`] trait, although this can
48/// frequently be achieved using `#[derive(PartialEq, Eq)]`.
49///
50/// It is a logic error for a key to be modified in such a way that its equality,
51/// as determined by the `Eq` trait, changes while it is in the map. This is
52/// normally only possible through [`Cell`](core::cell::Cell),
53/// [`RefCell`](core::cell::RefCell), global state, I/O, or unsafe code. The
54/// behavior resulting from such a logic error is not specified, but will not
55/// result in undefined behavior. This could include panics, incorrect results,
56/// aborts, memory leaks, and non-termination.
57pub struct ListMap<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
58 buf: S,
59 len: I,
60 pairs: PhantomData<(K, V)>,
61}
62
63impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> From<S> for ListMap<K, V, S, I> {
64 fn from(buf: S) -> Self {
65 ListMap { buf, len: I::from_usize(0), pairs: PhantomData }
66 }
67}
68
69impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ListMap<K, V, S, I> {
70 /// Returns the number of entries the map can hold.
71 #[inline]
72 pub fn capacity(&self) -> usize {
73 self.buf.capacity()
74 }
75
76 /// Returns a slice of all keys in the map in arbitrary order.
77 ///
78 /// # Examples
79 /// ```
80 /// use coca::collections::InlineListMap;
81 ///
82 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
83 /// map.insert("a", 1);
84 /// map.insert("b", 2);
85 /// map.insert("c", 3);
86 ///
87 /// for key in map.keys() {
88 /// println!("{}", key);
89 /// }
90 /// ```
91 #[inline]
92 pub fn keys(&self) -> &[K] {
93 let ptr = self.buf.get_ptr().cast();
94 unsafe { core::slice::from_raw_parts(ptr, self.len.as_usize()) }
95 }
96
97 #[inline(always)]
98 fn values_offset(&self) -> usize {
99 let cap = self.capacity();
100 let keys_array = Layout::array::<K>(cap).unwrap();
101 let values_array = Layout::array::<V>(cap).unwrap();
102 let (_, offset) = keys_array.extend(values_array).unwrap();
103 offset
104 }
105
106 /// Returns a slice of all values in the map in arbitrary order.
107 ///
108 /// # Examples
109 /// ```
110 /// use coca::collections::InlineListMap;
111 ///
112 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
113 /// map.insert("a", 1);
114 /// map.insert("b", 2);
115 /// map.insert("c", 3);
116 ///
117 /// for val in map.values() {
118 /// println!("{}", val);
119 /// }
120 /// ```
121 #[inline]
122 pub fn values(&self) -> &[V] {
123 unsafe {
124 let ptr = self.buf.get_ptr().add(self.values_offset()).cast();
125 core::slice::from_raw_parts(ptr, self.len())
126 }
127 }
128
129 /// Returns a mutable slice of all values in the map in arbitrary order.
130 ///
131 /// # Examples
132 /// ```
133 /// use coca::collections::InlineListMap;
134 ///
135 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
136 /// map.insert("a", 1);
137 /// map.insert("b", 2);
138 /// map.insert("c", 3);
139 ///
140 /// for val in map.values_mut() {
141 /// *val = *val * 2;
142 /// }
143 ///
144 /// assert_eq!(map.get("a"), Some(&2));
145 /// assert_eq!(map.get("b"), Some(&4));
146 /// assert_eq!(map.get("c"), Some(&6));
147 /// ```
148 #[inline]
149 pub fn values_mut(&mut self) -> &mut [V] {
150 unsafe {
151 let ptr = self.buf.get_mut_ptr().add(self.values_offset()).cast();
152 core::slice::from_raw_parts_mut(ptr, self.len())
153 }
154 }
155
156 /// An iterator visiting all key-value pairs in arbitrary order.
157 /// The iterator element type is `(&'a K, &'a V)`.
158 ///
159 /// # Examples
160 /// ```
161 /// use coca::collections::InlineListMap;
162 ///
163 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
164 /// map.insert("a", 1);
165 /// map.insert("b", 2);
166 /// map.insert("c", 3);
167 ///
168 /// for (key, val) in map.iter() {
169 /// println!("{} -> {}", key, val);
170 /// }
171 /// ```
172 pub fn iter(&self) -> Iter<'_, K, V, S, I> {
173 Iter { map: self, front: I::from_usize(0) }
174 }
175
176 /// An iterator visiting all key-value pairs in arbitrary order, with
177 /// mutable references to the values. The iterator element type is
178 /// `(&'a K, &'a mut V)`.
179 ///
180 /// # Examples
181 /// ```
182 /// use coca::collections::InlineListMap;
183 ///
184 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
185 /// map.insert("a", 1);
186 /// map.insert("b", 2);
187 /// map.insert("c", 3);
188 ///
189 /// for (_, val) in map.iter_mut() {
190 /// *val *= 2;
191 /// }
192 ///
193 /// assert_eq!(map.get("a"), Some(&2));
194 /// assert_eq!(map.get("b"), Some(&4));
195 /// assert_eq!(map.get("c"), Some(&6));
196 pub fn iter_mut(&mut self) -> IterMut<'_, K, V, S, I> {
197 IterMut { map: self, front: I::from_usize(0) }
198 }
199
200 /// Returns the number of entries in the map.
201 #[inline]
202 pub fn len(&self) -> usize {
203 self.len.as_usize()
204 }
205
206 /// Returns `true` if the map contains no entries, or `false` otherwise.
207 #[inline]
208 pub fn is_empty(&self) -> bool {
209 self.len.as_usize() == 0
210 }
211
212 /// Returns `true` if the map contains the maximum number of entries it can hold, or `false` otherwise.
213 #[inline]
214 pub fn is_full(&self) -> bool {
215 self.len.as_usize() == self.buf.capacity()
216 }
217
218 /// Clears the map without taking ownership, and returns all key-value pairs as an iterator.
219 ///
220 /// If the iterator is only partially consumed, or not consumed at all,
221 /// all remaining key-value pairs will still be removed.
222 ///
223 /// It is unspecified how many pairs will be removed if a panic occurs while
224 /// dropping an element, or if the [`Drain`] value is leaked.
225 ///
226 /// # Examples
227 /// ```
228 /// use coca::collections::InlineListMap;
229 ///
230 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
231 /// map.insert("a", 1);
232 /// map.insert("b", 2);
233 ///
234 /// for (k, v) in map.drain().take(1) {
235 /// let a = k == "a" && v == 1;
236 /// let b = k == "b" && v == 2;
237 /// assert!(a || b);
238 /// }
239 ///
240 /// assert!(map.is_empty());
241 /// ```
242 pub fn drain(&mut self) -> Drain<'_, K, V, S, I> {
243 Drain { map: self }
244 }
245
246 /// Creates an iterator which uses a closure to determine if an element should be removed.
247 ///
248 /// If the closure returns `true`, the element is removed from the map and
249 /// yielded. If the closure returns `false`, or panics, the element remains
250 /// in the map and will not be yielded.
251 ///
252 /// Note that `drain_filter` lets you mutate every value in the filter
253 /// closure, regardless of whether you choose to keep or remove it.
254 ///
255 /// If the iterator is only partially consumed, or not consumed at all,
256 /// all remaining key-value pairs will still be subjected to the closure
257 /// and removed and dropped if it returns true.
258 ///
259 /// It is unspecified how many pairs will be subjected to the closure if a
260 /// panic occurs in the closure, or a panic occurs while dropping an element,
261 /// or if the [`DrainFilter`] value is leaked.
262 ///
263 /// # Examples
264 /// ```
265 /// use coca::collections::{InlineListMap, InlineVec};
266 ///
267 /// let mut map = InlineListMap::<u32, u32, 8>::new();
268 /// (0..8).for_each(|x| { map.insert(x, x); });
269 /// let drained = map.drain_filter(|k, v| { *v = *v * *v; k % 2 == 0 });
270 ///
271 /// let mut evens = InlineVec::<u32, 4>::new();
272 /// let mut odds = InlineVec::<u32, 4>::new();
273 ///
274 /// evens.extend(drained.map(|(_x, x_squared)| x_squared));
275 /// evens.sort_unstable();
276 /// assert_eq!(evens, [0, 4, 16, 36]);
277 ///
278 /// odds.extend(map.into_values());
279 /// odds.sort_unstable();
280 /// assert_eq!(odds, [1, 9, 25, 49]);
281 /// ```
282 pub fn drain_filter<F: FnMut(&K, &mut V) -> bool>(&mut self, pred: F) -> DrainFilter<'_, K, V, S, I, F> {
283 DrainFilter { map: self, should_remove: pred, front: I::from_usize(0) }
284 }
285
286 /// Clears the map, removing all key-value pairs.
287 ///
288 /// # Examples
289 /// ```
290 /// use coca::collections::InlineListMap;
291 ///
292 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
293 ///
294 /// map.insert("a", 1);
295 /// map.insert("b", 2);
296 /// map.insert("c", 3);
297 /// map.insert("d", 4);
298 /// assert!(map.is_full());
299 ///
300 /// map.clear();
301 /// assert!(map.is_empty());
302 /// ```
303 pub fn clear(&mut self) {
304 unsafe {
305 let keys = self.buf.get_mut_ptr().cast::<K>();
306 let values = self.buf.get_mut_ptr().add(self.values_offset()).cast::<V>();
307
308 for i in 0..self.len() {
309 keys.add(i).drop_in_place();
310 values.add(i).drop_in_place();
311 }
312
313 self.len = I::from_usize(0);
314 }
315 }
316
317 /// Gets the given key's corresponding [`Entry`] in the map for in-place manipulation.
318 ///
319 /// # Panics
320 /// Panics if the map is full and does not contain the given key.
321 /// See [`try_entry`](ListMap::try_entry) for a checked version that never panics.
322 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, I>
323 where
324 K: Eq
325 {
326 self.try_entry(key).ok().expect("map is already at capacity")
327 }
328
329 /// Gets the given key's corresponding [`Entry`] in the map for in-place manipulation.
330 ///
331 /// Returns [`Err(key)`] if the map is full and does not contain the given key.
332 ///
333 /// # Examples
334 /// ```
335 /// use coca::collections::InlineListMap;
336 ///
337 /// let mut letters = InlineListMap::<char, u32, 32>::new();
338 ///
339 /// for ch in "i am, therefore i'm coded".chars() {
340 /// let counter = letters.try_entry(ch).unwrap().or_insert(0);
341 /// *counter += 1;
342 /// }
343 ///
344 /// assert_eq!(letters.get(&'a'), Some(&1));
345 /// assert_eq!(letters.get(&'e'), Some(&4));
346 /// assert_eq!(letters.get(&'i'), Some(&2));
347 /// assert_eq!(letters.get(&'o'), Some(&2));
348 /// assert_eq!(letters.get(&'u'), None);
349 /// ```
350 pub fn try_entry(&mut self, key: K) -> Result<Entry<'_, K, V, S, I>, K>
351 where
352 K: Eq
353 {
354 if let Some((idx, _)) = self.lookup(&key) {
355 Ok(Occupied(OccupiedEntry { key, idx, map: self, }))
356 } else if self.is_full() {
357 Err(key)
358 } else {
359 Ok(Vacant(VacantEntry { key, map: self }))
360 }
361 }
362
363 #[inline(always)]
364 fn lookup<Q>(&self, key: &Q) -> Option<(usize, &K)>
365 where
366 K: Borrow<Q> + Eq,
367 Q: Eq + ?Sized,
368 {
369 self.keys().iter().enumerate().find(|(_, k)| (*k).borrow() == key)
370 }
371
372 /// Returns a reference to the value associated with the given key.
373 ///
374 /// The key may be any borrowed form of the map's key type,
375 /// but `Eq` on the borrowed form *must* match that for the key type.
376 ///
377 /// # Examples
378 /// ```
379 /// use coca::collections::InlineListMap;
380 ///
381 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
382 /// map.insert("a", 1);
383 ///
384 /// assert_eq!(map.get("a"), Some(&1));
385 /// assert_eq!(map.get("b"), None);
386 /// ```
387 pub fn get<Q>(&self, key: &Q) -> Option<&V>
388 where
389 K: Borrow<Q> + Eq,
390 Q: Eq + ?Sized,
391 {
392 let (idx, _) = self.lookup(key)?;
393 Some(&self.values()[idx])
394 }
395
396 /// Returns the key-value pair corresponding to the given key.
397 ///
398 /// The key may be any borrowed form of the map's key type,
399 /// but `Eq` on the borrowed form *must* match that for the key type.
400 ///
401 /// # Examples
402 /// ```
403 /// use coca::collections::InlineListMap;
404 ///
405 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
406 /// map.insert("a", 1);
407 ///
408 /// assert_eq!(map.get_key_value("a"), Some((&"a", &1)));
409 /// assert_eq!(map.get_key_value("b"), None);
410 /// ```
411 pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
412 where
413 K: Borrow<Q> + Eq,
414 Q: Eq + ?Sized,
415 {
416 let (idx, k) = self.lookup(key)?;
417 Some((k, &self.values()[idx]))
418 }
419
420 /// Returns `true` if the map contains a value for the given key, or `false` otherwise.
421 ///
422 /// The key may be any borrowed form of the map's key type,
423 /// but `Eq` on the borrowed form *must* match that for the key type.
424 ///
425 /// # Examples
426 /// ```
427 /// use coca::collections::InlineListMap;
428 ///
429 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
430 /// map.insert("a", 1);
431 ///
432 /// assert_eq!(map.contains_key("a"), true);
433 /// assert_eq!(map.contains_key("b"), false);
434 /// ```
435 pub fn contains_key<Q>(&self, key: &Q) -> bool
436 where
437 K: Borrow<Q> + Eq,
438 Q: Eq + ?Sized,
439 {
440 self.lookup(key).is_some()
441 }
442
443 /// Returns a mutable reference to the value associated with the given key.
444 ///
445 /// The key may be any borrowed form of the map's key type,
446 /// but `Eq` on the borrowed form *must* match that for the key type.
447 ///
448 /// # Examples
449 /// ```
450 /// use coca::collections::InlineListMap;
451 ///
452 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
453 /// map.insert("a", 1);
454 ///
455 /// if let Some(x) = map.get_mut(&"a") {
456 /// *x = *x + 2;
457 /// }
458 ///
459 /// assert_eq!(map.get("a"), Some(&3));
460 /// ```
461 pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
462 where
463 K: Borrow<Q> + Eq,
464 Q: Eq + ?Sized,
465 {
466 let (idx, _) = self.lookup(key)?;
467 Some(&mut self.values_mut()[idx])
468 }
469
470 /// Inserts a key-value pair into the map.
471 ///
472 /// If the map did not have this key present, [`None`] is returned.
473 ///
474 /// If the map did have this key present, the value is updated, and the
475 /// old value is returned. The key is not updated though; this matters for
476 /// types that can be `==` without being identical.
477 ///
478 /// # Panics
479 /// Panics if the map is full and the given key is not present. See
480 /// [`try_insert`](ListMap::try_insert) for a checked version that never panics.
481 #[inline]
482 #[track_caller]
483 pub fn insert(&mut self, key: K, value: V) -> Option<V> where K: Eq {
484 self.try_insert(key, value).ok().expect("map is already at capacity")
485 }
486
487 /// Inserts a key-value pair into the map.
488 ///
489 /// If the map did not have this key present, `Ok(None)` is returned if the
490 /// key-value pair is inserted, or [`Err((key, value))`] if the map is full.
491 ///
492 /// If the map did have this key present, the value is updated, and the
493 /// old value is returned. The key is not updated though; this matters for
494 /// types that can be `==` without being identical.
495 ///
496 /// # Examples
497 /// ```
498 /// use coca::collections::InlineListMap;
499 ///
500 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
501 /// assert_eq!(map.try_insert("a", 37), Ok(None));
502 /// assert_eq!(map.try_insert("a", 42), Ok(Some(37)));
503 ///
504 /// map.insert("b", 23);
505 /// map.insert("c", 19);
506 /// map.insert("d", 8);
507 /// assert_eq!(map.is_full(), true);
508 /// assert_eq!(map.try_insert("e", 0), Err(("e", 0)));
509 /// ```
510 pub fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> where K: Eq {
511 if let Some((idx, _)) = self.lookup(&key) {
512 return Ok(Some(core::mem::replace(&mut self.values_mut()[idx], value)));
513 } else if self.is_full() {
514 return Err((key, value));
515 }
516
517 let idx = self.len();
518
519 unsafe {
520 let buf_ptr = self.buf.get_mut_ptr();
521
522 let key_ptr = buf_ptr.cast::<K>().add(idx);
523 key_ptr.write(key);
524
525 let value_ptr = buf_ptr.add(self.values_offset()).cast::<V>().add(idx);
526 value_ptr.write(value);
527 }
528
529 self.len = I::from_usize(idx + 1);
530 Ok(None)
531 }
532
533 /// Removes a key from the map, returning the value associated with the key
534 /// if it was previously in the map.
535 ///
536 /// The key may be any borrowed form of the map's key type,
537 /// but [`Eq`] on the borrowed form *must* match that for the key type.
538 ///
539 /// # Examples
540 /// ```
541 /// use coca::collections::InlineListMap;
542 ///
543 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
544 /// map.insert("a", 1);
545 ///
546 /// assert_eq!(map.remove("a"), Some(1));
547 /// assert_eq!(map.remove("a"), None);
548 /// ```
549 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
550 where
551 K: Borrow<Q> + Eq,
552 Q: Eq + ?Sized,
553 {
554 let (idx, _) = self.lookup(key)?;
555 let new_len = self.len() - 1;
556
557 unsafe {
558 let buf_ptr = self.buf.get_mut_ptr();
559
560 let keys = buf_ptr.cast::<K>();
561 keys.add(idx).drop_in_place();
562
563 let values = buf_ptr.add(self.values_offset()).cast::<V>();
564 let result = values.add(idx).read();
565
566 if idx != new_len {
567 core::ptr::copy_nonoverlapping(keys.add(new_len), keys.add(idx), 1);
568 core::ptr::copy_nonoverlapping(values.add(new_len), values.add(idx), 1);
569 }
570
571 self.len = I::from_usize(new_len);
572 Some(result)
573 }
574 }
575
576 /// Removes a key from the map, returning the stored key and associated
577 /// value if the key was previously in the map.
578 ///
579 /// The key may be any borrowed form of the map's key type,
580 /// but [`Eq`] on the borrowed form *must* match that for the key type.
581 ///
582 /// # Examples
583 /// ```
584 /// use coca::collections::InlineListMap;
585 ///
586 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
587 /// map.insert("a", 1);
588 ///
589 /// assert_eq!(map.remove_entry("a"), Some(("a", 1)));
590 /// assert_eq!(map.remove_entry("a"), None);
591 /// ```
592 pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
593 where
594 K: Borrow<Q> + Eq,
595 Q: Eq + ?Sized,
596 {
597 let (idx, _) = self.lookup(key)?;
598 let new_len = self.len() - 1;
599
600 unsafe {
601 let buf_ptr = self.buf.get_mut_ptr();
602
603 let keys = buf_ptr.cast::<K>();
604 let k = keys.add(idx).read();
605
606 let values = buf_ptr.add(self.values_offset()).cast::<V>();
607 let v = values.add(idx).read();
608
609 if idx != new_len {
610 core::ptr::copy_nonoverlapping(keys.add(new_len), keys.add(idx), 1);
611 core::ptr::copy_nonoverlapping(values.add(new_len), values.add(idx), 1);
612 }
613
614 self.len = I::from_usize(new_len);
615 Some((k, v))
616 }
617 }
618
619 /// Retains only the elements specified by the predicate.
620 ///
621 /// In other words, remove all key-value pairs `(k, v)` such that `pred(&k, &mut v)`
622 /// returns `false`. The elements are visited in arbitrary (and unspecified) order.
623 ///
624 /// # Examples
625 /// ```
626 /// use coca::collections::InlineListMap;
627 ///
628 /// let mut map = InlineListMap::<u32, u32, 8>::new();
629 /// (0..8).for_each(|x| { map.insert(x, x*10); });
630 /// assert_eq!(map.len(), 8);
631 ///
632 /// map.retain(|&k, _| k % 2 == 0);
633 /// assert_eq!(map.len(), 4);
634 /// ```
635 pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, mut pred: F) {
636 self.drain_filter(|k, v| !(pred)(k, v)).for_each(drop);
637 }
638
639 /// Creates a consuming iterator visiting all keys in arbitrary order.
640 /// The map cannot be used after calling this. The iterator element type is `K`.
641 ///
642 /// # Examples
643 /// ```
644 /// use coca::collections::{InlineListMap, InlineVec};
645 ///
646 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
647 /// map.insert("a", 1);
648 /// map.insert("b", 2);
649 /// map.insert("c", 3);
650 ///
651 /// let mut vec = InlineVec::<&'static str, 4>::new();
652 /// vec.extend(map.into_keys());
653 /// // The keys are visited in arbitrary order,
654 /// // so they must be sorted for this test.
655 /// vec.sort_unstable();
656 /// assert_eq!(vec, ["a", "b", "c"]);
657 /// ```
658 pub fn into_keys(self) -> IntoKeys<K, V, S, I> {
659 IntoKeys { base: self.into_iter() }
660 }
661
662 /// Creates a consuming iterator visiting all values in arbitrary order.
663 /// The map cannot be used after calling this. The iterator element type is `K`.
664 ///
665 /// # Examples
666 /// ```
667 /// use coca::collections::{InlineListMap, InlineVec};
668 ///
669 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
670 /// map.insert("a", 1);
671 /// map.insert("b", 2);
672 /// map.insert("c", 3);
673 ///
674 /// let mut vec = InlineVec::<u32, 4>::new();
675 /// vec.extend(map.into_values());
676 /// // The values are visited in arbitrary order,
677 /// // so they must be sorted for this test.
678 /// vec.sort_unstable();
679 /// assert_eq!(vec, [1, 2, 3]);
680 /// ```
681 pub fn into_values(self) -> IntoValues<K, V, S, I> {
682 IntoValues { base: self.into_iter() }
683 }
684}
685
686impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Drop for ListMap<K, V, S, I> {
687 fn drop(&mut self) {
688 self.clear();
689 }
690}
691
692impl<K: Debug, V: Debug, S: Storage<ListMapLayout<K, V>>, I: Capacity> Debug for ListMap<K, V, S, I> {
693 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
694 f.debug_map().entries(self.iter()).finish()
695 }
696}
697
698impl<Q, K, V, S, I> core::ops::Index<&'_ Q> for ListMap<K, V, S, I>
699where
700 Q: Eq + ?Sized,
701 K: Eq + Borrow<Q>,
702 S: Storage<ListMapLayout<K, V>>,
703 I: Capacity,
704{
705 type Output = V;
706
707 fn index(&self, key: &Q) -> &V {
708 self.get(key).expect("no entry found for key")
709 }
710}
711
712impl<K, V, S, I> Extend<(K, V)> for ListMap<K, V, S, I>
713where
714 K: Eq,
715 S: Storage<ListMapLayout<K, V>>,
716 I: Capacity
717{
718 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
719 let iter = iter.into_iter();
720 iter.for_each(move |(k, v)| { self.insert(k, v); });
721 }
722}
723
724impl<'a, K, V, S, I> Extend<(&'a K, &'a V)> for ListMap<K, V, S, I>
725where
726 K: Clone + Eq,
727 V: Clone,
728 S: Storage<ListMapLayout<K, V>>,
729 I: Capacity
730{
731 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
732 let iter = iter.into_iter();
733 iter.for_each(|(k, v)| {
734 self.insert(k.clone(), v.clone());
735 });
736 }
737}
738
739impl<K, V, S1, I1, S2, I2> PartialEq<ListMap<K, V, S2, I2>> for ListMap<K, V, S1, I1>
740where
741 K: Eq,
742 V: PartialEq,
743 S1: Storage<ListMapLayout<K, V>>,
744 S2: Storage<ListMapLayout<K, V>>,
745 I1: Capacity,
746 I2: Capacity,
747{
748 /// Tests for `self` and `other` to be equal, and is used by `==`.
749 ///
750 /// Note that this is *O*(1) if the two maps have different sizes,
751 /// but *O*(*n*²) if they are the same size.
752 fn eq(&self, other: &ListMap<K, V, S2, I2>) -> bool {
753 if self.len() != other.len() {
754 return false;
755 }
756
757 self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
758 }
759}
760
761impl<K: Eq, V: Eq, S: Storage<ListMapLayout<K, V>>, I: Capacity> Eq for ListMap<K, V, S, I> {}
762
763#[cfg(feature = "alloc")]
764#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
765impl<K, V, I: Capacity> crate::collections::AllocListMap<K, V, I> {
766 /// Constructs a new, empty [`AllocListMap`](crate::collections::AllocListMap)
767 /// with the specified capacity.
768 pub fn with_capacity(capacity: usize) -> Self {
769 Self::from(crate::storage::AllocStorage::with_capacity(capacity))
770 }
771}
772
773#[cfg(feature = "alloc")]
774#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
775impl<K: Clone, V: Clone, I: Capacity> Clone for crate::collections::AllocListMap<K, V, I> {
776 fn clone(&self) -> Self {
777 let buf = crate::storage::AllocStorage::with_capacity(self.capacity());
778 let mut result = ListMap {
779 buf, len: self.len, pairs: PhantomData
780 };
781
782 unsafe {
783 let base_ptr = result.buf.get_mut_ptr();
784 let keys_ptr = base_ptr.cast::<K>();
785 let values_ptr = base_ptr.add(result.values_offset()).cast::<V>();
786
787 for (idx, (k, v)) in self.iter().enumerate() {
788 keys_ptr.add(idx).write(k.clone());
789 values_ptr.add(idx).write(v.clone());
790 }
791 }
792
793 result
794 }
795}
796
797/// A statically-sized storage block for a [`ListMap`].
798#[repr(C)]
799pub struct InlineStorage<K, V, const N: usize> {
800 keys: [MaybeUninit<K>; N],
801 values: [MaybeUninit<V>; N],
802}
803
804unsafe impl<K, V, const N: usize> Storage<ListMapLayout<K, V>> for InlineStorage<K, V, N> {
805 fn get_ptr(&self) -> *const u8 {
806 (self as *const Self).cast()
807 }
808
809 fn get_mut_ptr(&mut self) -> *mut u8 {
810 (self as *mut Self).cast()
811 }
812
813 fn capacity(&self) -> usize {
814 N
815 }
816}
817
818impl<K, V, I: Capacity, const N: usize> ListMap<K, V, InlineStorage<K, V, N>, I> {
819 /// Constructs a new, empty [`InlineListMap`](crate::collections::InlineListMap).
820 pub fn new() -> Self {
821 let buf = unsafe { InlineStorage {
822 keys: MaybeUninit::uninit().assume_init(),
823 values: MaybeUninit::uninit().assume_init(),
824 }};
825
826 Self::from(buf)
827 }
828}
829
830impl<K, V, I: Capacity, const N: usize> Default for ListMap<K, V, InlineStorage<K, V, N>, I> {
831 fn default() -> Self {
832 Self::new()
833 }
834}
835
836impl<K: Clone, V: Clone, I: Capacity, const N: usize> Clone for ListMap<K, V, InlineStorage<K, V, N>, I> {
837 fn clone(&self) -> Self {
838 let buf = unsafe { InlineStorage {
839 keys: MaybeUninit::uninit().assume_init(),
840 values: MaybeUninit::uninit().assume_init(),
841 }};
842
843 let mut result = ListMap {
844 buf, len: self.len, pairs: PhantomData,
845 };
846
847 unsafe {
848 let base_ptr = result.buf.get_mut_ptr();
849 let keys_ptr = base_ptr.cast::<K>();
850 let values_ptr = base_ptr.add(result.values_offset()).cast::<V>();
851
852 for (idx, (k, v)) in self.iter().enumerate() {
853 keys_ptr.add(idx).write(k.clone());
854 values_ptr.add(idx).write(v.clone());
855 }
856 }
857
858 result
859 }
860}
861
862/// A view into an occupied entry in a [`ListMap`]. It is part of the [`Entry`] enum.
863pub struct OccupiedEntry<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
864 key: K,
865 idx: usize,
866 map: &'a mut ListMap<K, V, S, I>,
867}
868
869impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> OccupiedEntry<'a, K, V, S, I> {
870 /// Gets a reference to the key used to create the entry.
871 pub fn key(&self) -> &K {
872 &self.key
873 }
874
875 /// Take the ownership of the key and value from the map.
876 ///
877 /// # Examples
878 /// ```
879 /// use coca::collections::InlineListMap;
880 /// use coca::collections::list_map::Entry;
881 ///
882 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
883 ///
884 /// map.entry("foobar").or_insert(12);
885 /// assert_eq!(map.get("foobar"), Some(&12));
886 ///
887 /// if let Entry::Occupied(o) = map.entry("foobar") {
888 /// o.remove_entry();
889 /// }
890 ///
891 /// assert_eq!(map.contains_key("foobar"), false);
892 /// ```
893 pub fn remove_entry(self) -> (K, V) {
894 unsafe {
895 let base_ptr = self.map.buf.get_mut_ptr();
896
897 let keys_ptr = base_ptr.cast::<K>();
898 let k = keys_ptr.add(self.idx).read();
899
900 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
901 let v = values_ptr.add(self.idx).read();
902
903 let new_len = self.map.len() - 1;
904 if self.idx != new_len {
905 core::ptr::copy_nonoverlapping(keys_ptr.add(new_len), keys_ptr.add(self.idx), 1);
906 core::ptr::copy_nonoverlapping(values_ptr.add(new_len), values_ptr.add(self.idx), 1);
907 }
908
909 self.map.len = I::from_usize(new_len);
910 (k , v)
911 }
912 }
913
914 /// Gets a reference to the value in the entry.
915 ///
916 /// # Examples
917 /// ```
918 /// use coca::collections::InlineListMap;
919 /// use coca::collections::list_map::Entry;
920 ///
921 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
922 ///
923 /// map.entry("foobar").or_insert(12);
924 /// assert_eq!(map.get("foobar"), Some(&12));
925 ///
926 /// if let Entry::Occupied(o) = map.entry("foobar") {
927 /// assert_eq!(o.get(), &12);
928 /// }
929 /// ```
930 pub fn get(&self) -> &V {
931 unsafe {
932 let base_ptr = self.map.buf.get_ptr();
933 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
934 &*values_ptr.add(self.idx)
935 }
936 }
937
938 /// Gets a mutable reference to the value in the entry.
939 ///
940 /// If you need a reference to the value which may outlive the `Entry`,
941 /// see [`into_mut`](OccupiedEntry::into_mut).
942 ///
943 /// # Examples
944 /// ```
945 /// use coca::collections::InlineListMap;
946 /// use coca::collections::list_map::Entry;
947 ///
948 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
949 ///
950 /// map.entry("foobar").or_insert(12);
951 /// assert_eq!(map.get("foobar"), Some(&12));
952 ///
953 /// if let Entry::Occupied(mut o) = map.entry("foobar") {
954 /// *o.get_mut() += 10;
955 /// assert_eq!(*o.get(), 22);
956 ///
957 /// // You can use the same Entry multiple times:
958 /// *o.get_mut() += 2;
959 /// }
960 ///
961 /// assert_eq!(map.get("foobar"), Some(&24));
962 /// ```
963 pub fn get_mut(&mut self) -> &mut V {
964 unsafe {
965 let base_ptr = self.map.buf.get_mut_ptr();
966 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
967 &mut *values_ptr.add(self.idx)
968 }
969 }
970
971 /// Converts the `OccupiedEntry` into a mutable reference to the value
972 /// in the entry with a lifetime bound to the map itself.
973 ///
974 /// If you need multiple references to the `OccupiedEntry`,
975 /// see [`get_mut`](OccupiedEntry::get_mut).
976 ///
977 /// # Examples
978 /// ```
979 /// use coca::collections::InlineListMap;
980 /// use coca::collections::list_map::Entry;
981 ///
982 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
983 ///
984 /// map.entry("foobar").or_insert(12);
985 /// assert_eq!(map.get("foobar"), Some(&12));
986 ///
987 /// if let Entry::Occupied(o) = map.entry("foobar") {
988 /// *o.into_mut() += 10;
989 /// }
990 ///
991 /// assert_eq!(map.get("foobar"), Some(&22));
992 /// ```
993 pub fn into_mut(self) -> &'a mut V {
994 unsafe {
995 let base_ptr = self.map.buf.get_mut_ptr();
996 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
997 &mut *values_ptr.add(self.idx)
998 }
999 }
1000
1001 /// Sets the value of the entry, and returns the entry's old value.
1002 ///
1003 /// # Examples
1004 /// ```
1005 /// use coca::collections::InlineListMap;
1006 /// use coca::collections::list_map::Entry;
1007 ///
1008 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1009 ///
1010 /// map.entry("foobar").or_insert(12);
1011 /// assert_eq!(map.get("foobar"), Some(&12));
1012 ///
1013 /// if let Entry::Occupied(mut o) = map.entry("foobar") {
1014 /// assert_eq!(o.insert(15), 12);
1015 /// }
1016 ///
1017 /// assert_eq!(map.get("foobar"), Some(&15));
1018 /// ```
1019 pub fn insert(&mut self, value: V) -> V {
1020 unsafe {
1021 let base_ptr = self.map.buf.get_mut_ptr();
1022 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1023 values_ptr.add(self.idx).replace(value)
1024 }
1025 }
1026
1027 /// Takes the value out of the entry, and returns it.
1028 ///
1029 /// # Examples
1030 /// ```
1031 /// use coca::collections::InlineListMap;
1032 /// use coca::collections::list_map::Entry;
1033 ///
1034 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1035 ///
1036 /// map.entry("foobar").or_insert(12);
1037 /// assert_eq!(map.get("foobar"), Some(&12));
1038 ///
1039 /// if let Entry::Occupied(o) = map.entry("foobar") {
1040 /// assert_eq!(o.remove(), 12);
1041 /// }
1042 ///
1043 /// assert_eq!(map.contains_key("foobar"), false);
1044 /// ```
1045 pub fn remove(self) -> V {
1046 unsafe {
1047 let base_ptr = self.map.buf.get_mut_ptr();
1048
1049 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1050 let value = values_ptr.add(self.idx).read();
1051
1052 let new_len = self.map.len() - 1;
1053 if self.idx != new_len {
1054 let keys_ptr = base_ptr.cast::<K>();
1055 core::ptr::copy_nonoverlapping(keys_ptr.add(new_len), keys_ptr.add(self.idx), 1);
1056 core::ptr::copy_nonoverlapping(values_ptr.add(new_len), values_ptr.add(self.idx), 1);
1057 }
1058
1059 self.map.len = I::from_usize(new_len);
1060 value
1061 }
1062 }
1063
1064 /// Replaces the entry, returning the old key-value pair. The new key in the map will be the key used to create the entry.
1065 ///
1066 /// # Examples
1067 /// ```
1068 /// use coca::collections::InlineListMap;
1069 /// use coca::collections::list_map::Entry;
1070 ///
1071 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1072 /// map.insert("foobar", 15);
1073 ///
1074 /// if let Entry::Occupied(entry) = map.entry("foobar") {
1075 /// let (old_key, old_value) = entry.replace_entry(16);
1076 ///
1077 /// assert_eq!(old_key, "foobar");
1078 /// assert_eq!(old_value, 15);
1079 /// }
1080 ///
1081 /// assert_eq!(map.get("foobar"), Some(&16));
1082 /// ```
1083 pub fn replace_entry(self, value: V) -> (K, V) {
1084 unsafe {
1085 let base_ptr = self.map.buf.get_mut_ptr();
1086
1087 let keys_ptr = base_ptr.cast::<K>();
1088 let k = keys_ptr.add(self.idx).replace(self.key);
1089
1090 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1091 let v = values_ptr.add(self.idx).replace(value);
1092
1093 (k, v)
1094 }
1095 }
1096
1097 /// Replaces the key in the map with the one used to create the entry.
1098 ///
1099 /// This matters for key types that can be `==` without being identical.
1100 pub fn replace_key(self) -> K {
1101 unsafe {
1102 let keys_ptr = self.map.buf.get_mut_ptr().cast::<K>();
1103 keys_ptr.add(self.idx).replace(self.key)
1104 }
1105 }
1106}
1107
1108impl<K: Debug, V: Debug, S: Storage<ListMapLayout<K, V>>, I: Capacity> Debug for OccupiedEntry<'_, K, V, S, I> {
1109 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1110 f.debug_struct("OccupiedEntry")
1111 .field("key", &self.key)
1112 .field("value", self.get())
1113 .finish()
1114 }
1115}
1116
1117/// A view into a vacant entry in a [`ListMap`]. It is part of the [`Entry`] enum.
1118pub struct VacantEntry<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1119 key: K,
1120 map: &'a mut ListMap<K, V, S, I>,
1121}
1122
1123impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> VacantEntry<'a, K, V, S, I> {
1124 /// Gets a reference to the key that would be used when inserting through the `VacantEntry`.
1125 pub fn key(&self) -> &K {
1126 &self.key
1127 }
1128
1129 /// Take ownership of the key.
1130 pub fn into_key(self) -> K {
1131 self.key
1132 }
1133
1134 /// Sets the value of the entry with the `VacantEntry`'s key, and returns a mutable reference to it.
1135 pub fn insert(self, value: V) -> &'a mut V {
1136 unsafe {
1137 let len = self.map.len();
1138 let base_ptr = self.map.buf.get_mut_ptr();
1139
1140 let keys_ptr = base_ptr.cast::<K>();
1141 keys_ptr.add(len).write(self.key);
1142
1143 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1144 let v_ptr = values_ptr.add(len);
1145 v_ptr.write(value);
1146
1147 self.map.len = I::from_usize(len + 1);
1148 &mut *v_ptr
1149 }
1150 }
1151}
1152
1153impl<K: Debug, V: Debug, S: Storage<ListMapLayout<K, V>>, I: Capacity> Debug for VacantEntry<'_, K, V, S, I> {
1154 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1155 f.debug_tuple("VacantEntry").field(&self.key).finish()
1156 }
1157}
1158
1159/// A view into a single entry in a map, which may be either vacant or occupied.
1160///
1161/// This `enum` is constructed from the [`try_entry`](ListMap::try_entry) method on [`ListMap`].
1162pub enum Entry<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1163 /// An occupied entry.
1164 Occupied(OccupiedEntry<'a, K, V, S, I>),
1165 /// A vacant entry.
1166 Vacant(VacantEntry<'a, K, V, S, I>),
1167}
1168
1169impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Entry<'a, K, V, S, I> {
1170 /// Ensures a value is in the entry by inserting the `default` if empty,
1171 /// and returns a mutable reference to the value in the entry.
1172 ///
1173 /// # Examples
1174 /// ```
1175 /// use coca::collections::InlineListMap;
1176 ///
1177 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1178 ///
1179 /// map.entry("foobar").or_insert(3);
1180 /// assert_eq!(map.get("foobar"), Some(&3));
1181 ///
1182 /// *map.entry("foobar").or_insert(5) *= 2;
1183 /// assert_eq!(map.get("foobar"), Some(&6));
1184 /// ```
1185 pub fn or_insert(self, default: V) -> &'a mut V {
1186 match self {
1187 Occupied(entry) => entry.into_mut(),
1188 Vacant(entry) => entry.insert(default),
1189 }
1190 }
1191
1192 /// Ensures a value is in the entry by inserting the result of the `default`
1193 /// function if empty, and returns a mutable reference to the value in the entry.
1194 ///
1195 /// # Examples
1196 /// ```
1197 /// use coca::collections::InlineListMap;
1198 ///
1199 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1200 /// let bazz = 0xDEADBEEF;
1201 ///
1202 /// map.entry("foobar").or_insert_with(|| bazz);
1203 /// assert_eq!(map.get("foobar"), Some(&bazz));
1204 /// ```
1205 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
1206 match self {
1207 Occupied(entry) => entry.into_mut(),
1208 Vacant(entry) => entry.insert(default()),
1209 }
1210 }
1211
1212 /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
1213 /// This method allows for generating key-derived values for insertion by providing the default
1214 /// function a reference to the key that was moved during the `.entry(key)` method call.
1215 ///
1216 /// The reference to the moved key is provided so that cloning or copying the key is
1217 /// unnecessary, unlike with `.or_insert_with(|| ... )`.
1218 ///
1219 /// # Examples
1220 /// ```
1221 /// use coca::collections::InlineListMap;
1222 ///
1223 /// let mut map = InlineListMap::<&'static str, usize, 4>::new();
1224 ///
1225 /// map.entry("foobar").or_insert_with_key(|key| key.chars().count());
1226 ///
1227 /// assert_eq!(map.get("foobar"), Some(&6));
1228 /// ```
1229 pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
1230 match self {
1231 Occupied(entry) => entry.into_mut(),
1232 Vacant(entry) => {
1233 let value = default(entry.key());
1234 entry.insert(value)
1235 }
1236 }
1237 }
1238
1239 /// Returns a reference to the key used to create the entry.
1240 pub fn key(&self) -> &K {
1241 match *self {
1242 Occupied(ref entry) => entry.key(),
1243 Vacant(ref entry) => entry.key(),
1244 }
1245 }
1246
1247 /// Provides in-place mutable access to an occupied entry before any
1248 /// potential inserts into the map.
1249 ///
1250 /// # Examples
1251 /// ```
1252 /// use coca::collections::InlineListMap;
1253 ///
1254 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1255 ///
1256 /// map.entry("foobar")
1257 /// .and_modify(|v| { *v += 1 })
1258 /// .or_insert(37);
1259 /// assert_eq!(map.get("foobar"), Some(&37));
1260 ///
1261 /// map.entry("foobar")
1262 /// .and_modify(|v| { *v += 1 })
1263 /// .or_insert(42);
1264 /// assert_eq!(map.get("foobar"), Some(&38));
1265 /// ```
1266 #[must_use]
1267 pub fn and_modify<F: FnOnce(&mut V)>(self, f: F) -> Self {
1268 match self {
1269 Occupied(mut entry) => {
1270 f(entry.get_mut());
1271 Occupied(entry)
1272 },
1273 Vacant(entry) => Vacant(entry),
1274 }
1275 }
1276}
1277
1278impl<'a, K, V: Default, S: Storage<ListMapLayout<K, V>>, I: Capacity> Entry<'a, K, V, S, I> {
1279 /// Ensures a value is in the entry by inserting the default value if empty,
1280 /// and returns a mutable reference to the value in the entry.
1281 ///
1282 /// # Examples
1283 /// ```
1284 /// use coca::collections::InlineListMap;
1285 ///
1286 /// let mut map = InlineListMap::<&'static str, u32, 4>::new();
1287 /// map.entry("foobar").or_default();
1288 ///
1289 /// assert_eq!(map.get("foobar"), Some(&0));
1290 /// ```
1291 pub fn or_default(self) -> &'a mut V {
1292 match self {
1293 Occupied(entry) => entry.into_mut(),
1294 Vacant(entry) => entry.insert(V::default())
1295 }
1296 }
1297}
1298
1299impl<K: Debug, V: Debug, S: Storage<ListMapLayout<K, V>>, I: Capacity> Debug for Entry<'_, K, V, S, I> {
1300 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1301 match *self {
1302 Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
1303 Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
1304 }
1305 }
1306}
1307
1308/// An iterator over the entries of a [`ListMap`].
1309///
1310/// This `struct` is created by the [`iter`](ListMap::iter) method on `ListMap`.
1311/// See its documentation for more.
1312pub struct Iter<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1313 map: &'a ListMap<K, V, S, I>,
1314 front: I,
1315}
1316
1317impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for Iter<'a, K, V, S, I> {
1318 type Item = (&'a K, &'a V);
1319
1320 fn next(&mut self) -> Option<Self::Item> {
1321 let front = self.front.as_usize();
1322 if front >= self.map.len() { return None; }
1323
1324 let k = &self.map.keys()[front];
1325 let v = &self.map.values()[front];
1326 self.front = I::from_usize(front + 1);
1327
1328 Some((k, v))
1329 }
1330
1331 fn size_hint(&self) -> (usize, Option<usize>) {
1332 let front = self.front.as_usize();
1333 let len = self.map.len() - front;
1334 (len, Some(len))
1335 }
1336}
1337
1338impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for Iter<'_, K, V, S, I> {}
1339impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for Iter<'_, K, V, S, I> {}
1340
1341impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for &'a ListMap<K, V, S, I> {
1342 type Item = (&'a K, &'a V);
1343 type IntoIter = Iter<'a, K, V, S, I>;
1344
1345 fn into_iter(self) -> Self::IntoIter {
1346 self.iter()
1347 }
1348}
1349
1350/// A mutable iterator over the entries of a [`ListMap`].
1351///
1352/// This `struct` is created by the [`iter_mut`](ListMap::iter_mut)
1353/// method on `ListMap`. See its documentation for more.
1354pub struct IterMut<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1355 map: &'a mut ListMap<K, V, S, I>,
1356 front: I,
1357}
1358
1359impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for IterMut<'a, K, V, S, I> {
1360 type Item = (&'a K, &'a mut V);
1361
1362 fn next(&mut self) -> Option<Self::Item> {
1363 let front = self.front.as_usize();
1364 if front >= self.map.len() { return None; }
1365
1366 let (k, v) = unsafe {
1367 let base_ptr = self.map.buf.get_mut_ptr();
1368
1369 let keys_ptr = base_ptr.cast::<K>();
1370 let k = keys_ptr.add(front).as_ref().unwrap();
1371
1372 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1373 let v = values_ptr.add(front).as_mut().unwrap();
1374
1375 (k, v)
1376 };
1377
1378 self.front = I::from_usize(front + 1);
1379 Some((k, v))
1380 }
1381
1382 fn size_hint(&self) -> (usize, Option<usize>) {
1383 let front = self.front.as_usize();
1384 let len = self.map.len() - front;
1385 (len, Some(len))
1386 }
1387}
1388
1389impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for IterMut<'_, K, V, S, I> {}
1390impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for IterMut<'_, K, V, S, I> {}
1391
1392impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for &'a mut ListMap<K, V, S, I> {
1393 type Item = (&'a K, &'a mut V);
1394 type IntoIter = IterMut<'a, K, V, S, I>;
1395
1396 fn into_iter(self) -> Self::IntoIter {
1397 self.iter_mut()
1398 }
1399}
1400
1401/// An owning iterator over the entries of a [`ListMap`].
1402///
1403/// This `struct` is created by the [`into_iter`](IntoIterator::into_iter)
1404/// method on `ListMap` (provided by the [`IntoIterator`] trait). See its
1405/// documentation for more.
1406pub struct IntoIter<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1407 map: ListMap<K, V, S, I>,
1408}
1409
1410impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for IntoIter<K, V, S, I> {
1411 type Item = (K, V);
1412
1413 fn next(&mut self) -> Option<Self::Item> {
1414 if self.map.is_empty() { return None; }
1415
1416 let new_len = self.map.len() - 1;
1417 self.map.len = I::from_usize(new_len);
1418
1419 unsafe {
1420 let base_ptr = self.map.buf.get_ptr();
1421
1422 let keys_ptr = base_ptr.cast::<K>();
1423 let k = keys_ptr.add(new_len).read();
1424
1425 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1426 let v = values_ptr.add(new_len).read();
1427
1428 Some((k, v))
1429 }
1430 }
1431
1432 fn size_hint(&self) -> (usize, Option<usize>) {
1433 let len = self.map.len();
1434 (len, Some(len))
1435 }
1436}
1437
1438impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for IntoIter<K, V, S, I> {}
1439impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for IntoIter<K, V, S, I> {}
1440
1441impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for ListMap<K, V, S, I> {
1442 type Item = (K, V);
1443 type IntoIter = IntoIter<K, V, S, I>;
1444
1445 fn into_iter(self) -> Self::IntoIter {
1446 IntoIter { map: self }
1447 }
1448}
1449
1450/// An owning iterator over the keys of a [`ListMap`].
1451///
1452/// This `struct` is created by the [`into_keys`](ListMap::into_keys) method on `ListMap`.
1453/// See its documentation for more.
1454pub struct IntoKeys<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1455 base: IntoIter<K, V, S, I>,
1456}
1457
1458impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for IntoKeys<K, V, S, I> {
1459 type Item = K;
1460
1461 fn next(&mut self) -> Option<Self::Item> {
1462 self.base.next().map(|(k, _)| k)
1463 }
1464
1465 fn size_hint(&self) -> (usize, Option<usize>) {
1466 self.base.size_hint()
1467 }
1468}
1469
1470impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for IntoKeys<K, V, S, I> {}
1471impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for IntoKeys<K, V, S, I> {}
1472
1473/// An owning iterator over the values of a [`ListMap`].
1474///
1475/// This `struct` is created by the [`into_values`](ListMap::into_values) method on `ListMap`.
1476/// See its documentation for more.
1477pub struct IntoValues<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1478 base: IntoIter<K, V, S, I>,
1479}
1480
1481impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for IntoValues<K, V, S, I> {
1482 type Item = V;
1483
1484 fn next(&mut self) -> Option<Self::Item> {
1485 self.base.next().map(|(_, v)| v)
1486 }
1487
1488 fn size_hint(&self) -> (usize, Option<usize>) {
1489 self.base.size_hint()
1490 }
1491}
1492
1493impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for IntoValues<K, V, S, I> {}
1494impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for IntoValues<K, V, S, I> {}
1495
1496/// A draining iterator over the entries of a [`ListMap`].
1497///
1498/// This `struct` is created by the [`drain`](ListMap::drain) method on `ListMap`.
1499/// See its documentation for more.
1500pub struct Drain<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> {
1501 map: &'a mut ListMap<K, V, S, I>,
1502}
1503
1504impl<'a, K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Iterator for Drain<'a, K, V, S, I> {
1505 type Item = (K, V);
1506
1507 fn next(&mut self) -> Option<Self::Item> {
1508 let len = self.map.len();
1509 if len == 0 { return None; }
1510
1511 let new_len = len - 1;
1512 self.map.len = I::from_usize(new_len);
1513
1514 unsafe {
1515 let base_ptr = self.map.buf.get_ptr();
1516
1517 let keys_ptr = base_ptr.cast::<K>();
1518 let k = keys_ptr.add(new_len).read();
1519
1520 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1521 let v = values_ptr.add(new_len).read();
1522
1523 Some((k, v))
1524 }
1525 }
1526
1527 fn size_hint(&self) -> (usize, Option<usize>) {
1528 let len = self.map.len();
1529 (len, Some(len))
1530 }
1531}
1532
1533impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ExactSizeIterator for Drain<'_, K, V, S, I> {}
1534impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> FusedIterator for Drain<'_, K, V, S, I> {}
1535
1536impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Drop for Drain<'_, K, V, S, I> {
1537 fn drop(&mut self) {
1538 self.for_each(drop);
1539 }
1540}
1541
1542/// A draining, filtering iterator over the entries of a [`ListMap`].
1543///
1544/// This `struct` is created by the [`drain_filter`](ListMap::drain_filter)
1545/// method on `ListMap`. See its documentation for more.
1546pub struct DrainFilter<'a, K, V, S, I, F>
1547where
1548 S: Storage<ListMapLayout<K, V>>,
1549 I: Capacity,
1550 F: FnMut(&K, &mut V) -> bool,
1551{
1552 map: &'a mut ListMap<K, V, S, I>,
1553 should_remove: F,
1554 front: I,
1555}
1556
1557impl<'a, K, V, S, I, F> Iterator for DrainFilter<'a, K, V, S, I, F>
1558where
1559 S: Storage<ListMapLayout<K, V>>,
1560 I: Capacity,
1561 F: FnMut(&K, &mut V) -> bool
1562{
1563 type Item = (K, V);
1564
1565 fn next(&mut self) -> Option<Self::Item> {
1566 let mut front = self.front.as_usize();
1567 while front < self.map.len() {
1568 unsafe {
1569 let base_ptr = self.map.buf.get_mut_ptr();
1570 let keys_ptr = base_ptr.cast::<K>();
1571 let values_ptr = base_ptr.add(self.map.values_offset()).cast::<V>();
1572
1573 let k = keys_ptr.add(front).as_ref().unwrap();
1574 let v = values_ptr.add(front).as_mut().unwrap();
1575
1576 if (self.should_remove)(k, v) {
1577 let new_len = self.map.len() - 1;
1578 self.map.len = I::from_usize(new_len);
1579
1580 let k = keys_ptr.add(front).read();
1581 let v = values_ptr.add(front).read();
1582
1583 if front < new_len {
1584 core::ptr::copy_nonoverlapping(keys_ptr.add(new_len), keys_ptr.add(front), 1);
1585 core::ptr::copy_nonoverlapping(values_ptr.add(new_len), values_ptr.add(front), 1);
1586 }
1587
1588 self.front = I::from_usize(front);
1589 return Some((k, v));
1590 }
1591 }
1592
1593 front += 1;
1594 }
1595
1596 self.front = I::from_usize(front);
1597 None
1598 }
1599
1600 fn size_hint(&self) -> (usize, Option<usize>) {
1601 let max_len = self.map.len() - self.front.as_usize();
1602 (0, Some(max_len))
1603 }
1604}
1605
1606impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity, F: FnMut(&K, &mut V) -> bool> FusedIterator for DrainFilter<'_, K, V, S, I, F> {}
1607
1608impl<'a, K, V, S, I, F> Drop for DrainFilter<'a, K, V, S, I, F>
1609where
1610 S: Storage<ListMapLayout<K, V>>,
1611 I: Capacity,
1612 F: FnMut(&K, &mut V) -> bool
1613{
1614 fn drop(&mut self) {
1615 self.for_each(drop);
1616 }
1617}