arctic/sequential/map.rs
1//! Auxiliary types for use with [`SequentialMap`].
2
3use core::convert::Infallible;
4use core::marker::PhantomData;
5use core::ops::ControlFlow;
6use core::ops::RangeFull;
7use core::ptr::NonNull;
8#[cfg_attr(not(doc), expect(unused))]
9use std::collections::btree_map;
10
11#[cfg_attr(not(doc), expect(unused))]
12use crate::SequentialMap;
13use crate::raw;
14use crate::raw::Cursor;
15use crate::raw::Edge;
16use crate::raw::Key;
17use crate::raw::cursor;
18use crate::raw::cursor::path;
19use crate::raw::edge;
20use crate::raw::iter::Order;
21use crate::sequential::EntryIter;
22use crate::sequential::EntryIterMut;
23use crate::sequential::Shard;
24use crate::sequential::ShardMut;
25use crate::sequential::Value;
26use crate::stat;
27
28/// Non-concurrent map that supports lexicographically ordered range and prefix scans.
29///
30/// # Usage
31///
32/// [`SequentialMap`] supports both point and scan operations, and tries to be roughly
33/// compatible with the standard library's [`BTreeMap`][std::collections::BTreeMap].
34///
35/// In general, radix trees do not explicitly store keys; they are implicitly
36/// encoded in the structure of the tree. This means that operations on [`SequentialMap`]
37/// generally take references to keys (see [`Key`]). Operations that insert and typically
38/// would take an owned key, like [`BTreeMap::insert`][std::collections::BTreeMap::insert],
39/// instead take a [`Key::Insert<'_>`][crate::Key::Insert]. Operations that
40/// do not insert a new key take a [`&Key::Borrowed`][crate::Key::Borrowed].
41///
42/// ## Point operations
43///
44/// The main caveat here is that [`SequentialMap::insert`] errors if the key is present,
45/// whereas [`BTreeMap::insert`][std::collections::BTreeMap::insert]
46/// updates. (To match the standard library behavior, use [`SequentialMap::upsert`] instead.)
47/// For more complex conditional logic, the [`SequentialMap::entry`] API mimics
48/// [`BTreeMap::entry`][std::collections::BTreeMap::entry].
49///
50/// ## Scan operations
51///
52/// For scan operations, [`SequentialMap`] exposes a two-phase API: the caller first selects
53/// a subtree (e.g., [`SequentialMap::prefix`] or [`SequentialMap::range_mut`]). This returns
54/// a [`Shard`] or [`ShardMut`], which can then be iterated over
55/// (e.g., [`Shard::entries`] or [`ShardMut::values_mut`]).
56/// This is in contrast to the standard library, where [`BTreeMap::range`][std::collections::BTreeMap::range]
57/// directly returns an iterator.
58///
59/// If the key type (see [`Key`]) is dynamically allocated, like [`BoxedStr`][crate::key::BoxedStr],
60/// iterating over keys can be expensive, as a key buffer must be updated
61/// during traversal, and then cloned once per key. This can be mitigated by
62/// (a) iterating over values instead of entries, (b) using the lending API
63/// (e.g., [`EntryIter::lend`]), which borrows from the iterator's internal
64/// buffer, or (c) using the internal iteration API[^iter] (e.g., [`EntryIterMut::try_fold`]),
65/// which also borrows from the iterator and can be much faster.
66///
67/// [^iter]: Should ideally replace with custom [`Iterator::try_fold`] implementation,
68/// but this currently uses the unstable Try trait.
69/// See also [this issue](https://github.com/nnethercote/perf-book/issues/70).
70#[repr(transparent)]
71pub struct Map<K: Key, V: Value> {
72 pub(crate) raw: raw::Map<K>,
73 _value: PhantomData<V>,
74}
75
76impl<K, V> Default for Map<K, V>
77where
78 K: Key,
79 V: Value,
80{
81 fn default() -> Self {
82 Self::new()
83 }
84}
85
86/// # Basic operations
87impl<K, V> Map<K, V>
88where
89 K: Key,
90 V: Value,
91{
92 /// Constructs a new empty map. Does not allocate.
93 #[inline]
94 pub const fn new() -> Self {
95 Self {
96 raw: raw::Map::new(),
97 _value: PhantomData,
98 }
99 }
100}
101
102/// # Point operations
103///
104/// This set of operations operates on a single key-value pair.
105impl<K, V> Map<K, V>
106where
107 K: Key,
108 V: Value,
109{
110 /// Returns whether `key` has an associated value.
111 ///
112 /// # Examples
113 ///
114 /// ```rust
115 /// use arctic::SequentialMap;
116 ///
117 /// let mut map = SequentialMap::<u64, u64>::new();
118 /// map.insert(1, 2).expect("Key is not present");
119 /// assert!(map.contains_key(&1));
120 /// assert!(!map.contains_key(&2));
121 /// ```
122 pub fn contains_key(&self, key: &K::Borrowed) -> bool {
123 self.get(key).is_some()
124 }
125
126 /// Returns an immutable reference to the value associated with `key`.
127 ///
128 /// For a mutable reference, see [`Map::get_mut`].
129 ///
130 /// # Examples
131 ///
132 /// ```rust
133 /// use arctic::SequentialMap;
134 ///
135 /// let mut map = SequentialMap::<u64, u64>::new();
136 /// map.insert(1, 2).expect("Key is not present");
137 /// assert_eq!(map.get(&1), Some(&2));
138 /// assert_eq!(map.get(&2), None);
139 /// ```
140 pub fn get(&self, key: &K::Borrowed) -> Option<&V> {
141 let reader = K::Read::from(key);
142 self.get_raw(reader)
143 .map(|value| unsafe { value.cast::<V>().as_ref() })
144 }
145
146 /// Returns a mutable reference to the value associated with `key`.
147 ///
148 /// For an immutable reference, see [`Map::get`].
149 ///
150 /// # Examples
151 ///
152 /// ```rust
153 /// use arctic::SequentialMap;
154 ///
155 /// let mut map = SequentialMap::<u64, u64>::new();
156 /// let key = 1;
157 /// map.insert(key, 2).expect("Key is not present");
158 /// let value = map.get_mut(&key).expect("Key is present");
159 /// *value = 3;
160 /// assert_eq!(map.get(&key), Some(&3));
161 /// ```
162 pub fn get_mut(&mut self, key: &K::Borrowed) -> Option<&mut V> {
163 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(key) };
164 let walk = unsafe { *cursor.edge_mut().get_mut_packed() };
165 unsafe { cursor.traverse_value(walk) }?;
166 Some(unsafe { cursor.as_value_unchecked().cast::<V>().as_mut() })
167 }
168
169 /// If there is no value associated with `key`, associate it with `value`.
170 ///
171 /// <div class="warning">
172 ///
173 /// This is **not** the same behavior as the standard library
174 /// (e.g., [`std::collections::BTreeMap::insert`]); see [`Map::upsert`] if
175 /// an existing value should be updated instead.
176 ///
177 /// </div>
178 ///
179 /// Returns `Ok(&mut new_value)` if the insert succeeded,
180 /// or else `Err((&mut old_value, new_value))` if there is an existing
181 /// `old_value` associated with the key.
182 ///
183 /// # Examples
184 ///
185 /// ```rust
186 /// use arctic::key::BoxedStr;
187 /// use arctic::key::NonNull;
188 /// use arctic::key::Str;
189 /// use arctic::SequentialMap;
190 ///
191 /// let mut map = SequentialMap::<BoxedStr<NonNull>, Box<u64>>::new();
192 /// let key = Str::<NonNull>::new("regent").expect("No null byte");
193 ///
194 /// // Key not present, insert succeeds
195 /// match map.insert(key, Box::new(3)) {
196 /// Ok(new) => assert_eq!(**new, 3),
197 /// Err(_) => unreachable!(),
198 /// }
199 ///
200 /// // Key not present, insert fails
201 /// match map.insert(key, Box::new(26)) {
202 /// Ok(_) => unreachable!(),
203 /// Err((old, new)) => {
204 /// assert_eq!(**old, 3);
205 /// assert_eq!(*new, 26);
206 /// },
207 /// }
208 /// ```
209 pub fn insert<'k>(&mut self, key: K::Insert<'k>, value: V) -> Result<&mut V, (&mut V, V)> {
210 match self.entry(key) {
211 Entry::Vacant(entry) => Ok(entry.insert(value)),
212 Entry::Occupied(entry) => Err((entry.into_mut(), value)),
213 }
214 }
215
216 /// Unconditionally associate `key` with `value`.
217 ///
218 /// Returns `Ok((old_value, &mut new_value))` if this updated `old_value`,
219 /// or `Err(&mut new_value)` if there was no value associated with `key`.
220 ///
221 /// # Examples
222 ///
223 /// ```rust
224 /// use arctic::key::BoxedStr;
225 /// use arctic::key::Terminated;
226 /// use arctic::key::Str;
227 /// use arctic::SequentialMap;
228 ///
229 /// let mut map = SequentialMap::<BoxedStr<Terminated<b'\n'>>, u64>::new();
230 /// let key = Str::new("silent\n").expect("Newline terminated");
231 ///
232 /// // Key not present, upsert performs insert
233 /// match map.upsert(key, 2) {
234 /// Ok(_) => unreachable!(),
235 /// Err(new) => assert_eq!(*new, 2),
236 /// }
237 ///
238 /// // Key present, upsert performs update
239 /// match map.upsert(key, 26) {
240 /// Ok((old, new)) => {
241 /// assert_eq!(old, 2);
242 /// assert_eq!(*new, 26);
243 /// },
244 /// Err(_) => unreachable!(),
245 /// }
246 /// ```
247 pub fn upsert<'k>(&mut self, key: K::Insert<'k>, value: V) -> Result<(V, &mut V), &mut V> {
248 match self.entry(key) {
249 Entry::Vacant(entry) => Err(entry.insert(value)),
250 Entry::Occupied(mut entry) => {
251 let old = entry.update(value);
252 Ok((old, entry.into_mut()))
253 }
254 }
255 }
256
257 /// If there is a value associated with `key`, update it to `value`.
258 ///
259 /// Returns `Ok((old_value, &mut new_value))` if the update succeeded,
260 /// or else `Err(new_value)` if there was no old value associated with `key`.
261 ///
262 /// # Examples
263 ///
264 /// ```rust
265 /// use arctic::SequentialMap;
266 ///
267 /// let mut map = SequentialMap::<[u8; 3], Box<u64>>::new();
268 /// let key = [0, 1, 2];
269 ///
270 /// // Key not present, update fails
271 /// match map.update(&key, Box::new(5)) {
272 /// Ok(_) => unreachable!(),
273 /// Err(new) => assert_eq!(*new, 5),
274 /// }
275 ///
276 /// map.insert(&key, Box::new(9));
277 ///
278 /// // Key present, update succeeds
279 /// match map.update(&key, Box::new(10)) {
280 /// Ok((old, new)) => {
281 /// assert_eq!(*old, 9);
282 /// assert_eq!(**new, 10);
283 /// },
284 /// Err(_) => unreachable!(),
285 /// }
286 /// ```
287 pub fn update(&mut self, key: &K::Borrowed, value: V) -> Result<(V, &mut V), V> {
288 unsafe { self.update_raw(K::Read::from(key), value.into_raw()) }
289 .map(|(old, new)| unsafe { (V::from_raw_unchecked(old), new.cast::<V>().as_mut()) })
290 .map_err(|new| unsafe { V::from_raw_unchecked(new) })
291 }
292
293 /// If there is a value associated with `key`, remove it from the map,
294 /// recursively removing empty tree nodes.
295 ///
296 /// This method is slow because it must keep a traversal stack, and scan and
297 /// delete empty nodes. See [`Map::remove_non_recursive`] for a faster,
298 /// but potentially memory-intensive alternative.
299 ///
300 /// Returns `Some(old_value)` if the remove succeeded, or else `None` if
301 /// there was no old value associated with `key`.
302 ///
303 /// # Examples
304 ///
305 /// ```rust
306 /// use arctic::SequentialMap;
307 ///
308 /// let mut map = SequentialMap::<u16, u64>::new();
309 /// let key = 100;
310 ///
311 /// // Key not present, remove fails
312 /// assert!(map.remove(&key).is_none());
313 ///
314 /// map.insert(key, 7);
315 ///
316 /// // Key present, remove succeeds
317 /// assert_eq!(map.remove(&key), Some(7));
318 ///
319 /// // Key no longer present
320 /// assert!(map.get(&key).is_none());
321 /// ```
322 pub fn remove(&mut self, key: &K::Borrowed) -> Option<V> {
323 unsafe { self.remove_raw::<path::Full<_>>(K::Read::from(key)) }
324 .map(|value| unsafe { V::from_raw_unchecked(value) })
325 }
326
327 /// If there is a value associated with `key`, remove it from the map,
328 /// **without** recursively removing empty tree nodes.
329 ///
330 /// <div class="warning">
331 ///
332 /// This method is much faster than [`Map::remove`], because no traversal
333 /// stack or node scanning and replacement is necessary; however, it means
334 /// the memory usage of the tree is no longer correlated with the number of
335 /// keys and values it contains.
336 ///
337 /// This method should only be used if removals are rare or removed keys
338 /// are expected to be reinserted.
339 //
340 /// </div>
341 ///
342 /// Returns `Some(old_value)` if the remove succeeded, or else `None` if
343 /// there was no old value associated with `key`.
344 pub fn remove_non_recursive(&mut self, key: &K::Borrowed) -> Option<V> {
345 unsafe { self.remove_raw::<path::Discard<_>>(K::Read::from(key)) }
346 .map(|value| unsafe { V::from_raw_unchecked(value) })
347 }
348
349 /// Get a logical entry associated with `key` (see also [`std::collections::BTreeMap::entry`]).
350 ///
351 /// This is a lazy operation, and does not allocate or modify the tree structure.
352 ///
353 /// # Examples
354 ///
355 /// ```rust
356 /// use arctic::key::Str;
357 /// use arctic::key::NonNull;
358 /// use arctic::SequentialMap;
359 ///
360 /// let mut counter = SequentialMap::<&'static Str<NonNull>, u64>::new();
361 /// let claw = Str::new("claw").expect("No null byte");
362 /// let hotfix = Str::new("hotfix").expect("No null byte");
363 /// let hologram = Str::new("hologram").expect("No null byte");
364 ///
365 /// for key in [claw, claw, hotfix, hologram, claw] {
366 /// *counter.entry(key).or_default() += 1;
367 /// }
368 ///
369 /// assert_eq!(*counter.get(hologram).unwrap(), 1);
370 /// assert_eq!(*counter.get(hotfix).unwrap(), 1);
371 /// assert_eq!(*counter.get(claw).unwrap(), 3);
372 /// ```
373 pub fn entry<'k>(&mut self, key: K::Insert<'k>) -> Entry<'_, 'k, K, V> {
374 unsafe { self.entry_raw(K::insert_as_read(key)) }
375 }
376}
377
378/// # Scan operations
379///
380/// This set of operations allows the caller to select a subtree
381/// (by prefix or range) for iteration.
382impl<K, V> Map<K, V>
383where
384 K: Key,
385 V: Value,
386{
387 /// Get an immutable reference to the entire tree.
388 #[inline]
389 pub fn all(&self) -> Shard<'_, 'static, K, V, RangeFull> {
390 unsafe { Shard::new(self.raw.all()) }
391 }
392
393 /// Get an immutable reference to the subtree of keys beginning with `prefix`.
394 #[inline]
395 pub fn prefix<'k>(&self, prefix: K::Read<'k>) -> Shard<'_, 'k, K, V, RangeFull> {
396 unsafe { Shard::new(self.raw.prefix(prefix)) }
397 }
398
399 /// Get an immutable reference to the subtree of keys within `range`.
400 #[inline]
401 pub fn range<'k, R>(&self, range: R) -> Shard<'_, 'k, K, V, R>
402 where
403 R: raw::iter::Range<K::Read<'k>>,
404 {
405 let prefix = range.common_prefix();
406 unsafe { Shard::new(self.raw.range(range, prefix)) }
407 }
408
409 /// Get a mutable reference to the entire tree.
410 #[inline]
411 pub fn all_mut(&mut self) -> ShardMut<'_, 'static, K, V, RangeFull> {
412 unsafe { ShardMut::new(self.all()) }
413 }
414
415 /// Get a mutable reference to the subtree of keys beginning with `prefix`.
416 #[inline]
417 pub fn prefix_mut<'k>(&mut self, prefix: K::Read<'k>) -> ShardMut<'_, 'k, K, V, RangeFull> {
418 unsafe { ShardMut::new(self.prefix(prefix)) }
419 }
420
421 /// Get a mutable reference to the subtree of keys within `range`.
422 #[inline]
423 pub fn range_mut<'k, R>(&mut self, range: R) -> ShardMut<'_, 'k, K, V, R>
424 where
425 R: raw::iter::Range<K::Read<'k>>,
426 {
427 unsafe { ShardMut::new(self.range(range)) }
428 }
429}
430
431/// # Private implementations
432///
433/// These methods erase value types and accept arbitrary key readers
434/// This reduces monomorphization and allows the `sequential::Set` implementation
435/// to reuse this logic, at the cost of reducing type safety.
436///
437/// # Safety
438///
439/// - When inserting, caller must guarantee `reader` preserves the prefix property.
440/// - All values are created via `V::into_raw`.
441impl<K, V> Map<K, V>
442where
443 K: Key,
444 V: Value,
445{
446 // NOTE: this method is safe because it does not insert a key or insert/update a value.
447 #[inline]
448 pub(super) fn get_raw(&self, reader: K::Read<'_>) -> Option<NonNull<u64>> {
449 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(reader) };
450 let walk = unsafe { *cursor.edge_mut().get_mut_packed() };
451 unsafe { cursor.traverse_value(walk) }?;
452 Some(unsafe { cursor.as_value_unchecked() })
453 }
454
455 pub(super) unsafe fn update_raw(
456 &mut self,
457 reader: K::Read<'_>,
458 value: u64,
459 ) -> Result<(u64, NonNull<u64>), u64> {
460 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(reader) };
461 let walk = unsafe { *cursor.edge_mut().get_mut_packed() };
462 match unsafe { cursor.traverse_value(walk) } {
463 None => Err(value),
464 Some(update) => {
465 let edge = unsafe { cursor.edge_mut() };
466 *edge.get_mut_packed() = Edge::new_value(update.edge.meta(), value.into_raw());
467 Ok((update.value, unsafe {
468 Edge::as_value_unchecked(NonNull::from(edge))
469 }))
470 }
471 }
472 }
473
474 pub(super) unsafe fn remove_raw<'k, P: cursor::Path<K::Read<'k>>>(
475 &mut self,
476 reader: K::Read<'k>,
477 ) -> Option<u64> {
478 let mut cursor = unsafe { self.raw.cursor::<path::Full<_>>(reader) };
479 let walk = unsafe { *cursor.edge_mut().get_mut_packed() };
480
481 let update = unsafe { cursor.traverse_value(walk) }?;
482
483 unsafe {
484 *cursor.edge_mut().get_mut_packed() = Edge::<K::Edge>::NULL;
485 }
486
487 while let Ok(Some((_, target))) = cursor.pop() {
488 if unsafe { target.len::<K::Edge>() } > 1 {
489 break;
490 }
491
492 let old = unsafe { cursor.edge_mut() }.get_mut_packed();
493 validate_eq!(old.child(), Some(edge::Child::Node(target)));
494
495 let (_smo, new) = unsafe { target.replace::<K::Edge>(old.meta()) };
496 *unsafe { cursor.edge_mut() }.get_mut_packed() = new;
497 unsafe { target.deallocate() };
498 }
499
500 Some(update.value)
501 }
502
503 #[inline]
504 pub(super) unsafe fn entry_raw<'k>(&mut self, reader: K::Read<'k>) -> Entry<'_, 'k, K, V> {
505 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(reader) };
506 let walk = unsafe { *cursor.edge_mut().get_mut_packed() };
507 match unsafe { cursor.traverse_insert(walk) } {
508 raw::cursor::Insert::Value {
509 value: Some(_),
510 edge: _,
511 } => Entry::Occupied(Occupied {
512 value: unsafe { cursor.as_value_unchecked().cast::<V>() },
513 _value: PhantomData,
514 }),
515
516 raw::cursor::Insert::Value {
517 value: None,
518 edge: _,
519 } => Entry::Vacant(Vacant {
520 cursor,
521 replace: false,
522 _value: PhantomData,
523 }),
524
525 raw::cursor::Insert::Replace { .. } => Entry::Vacant(Vacant {
526 cursor,
527 replace: true,
528 _value: PhantomData,
529 }),
530 }
531 }
532}
533
534impl<'k, K, V> FromIterator<(K::Insert<'k>, V)> for Map<K, V>
535where
536 K: Key,
537 V: Value,
538{
539 fn from_iter<T: IntoIterator<Item = (K::Insert<'k>, V)>>(iter: T) -> Self {
540 let mut map = Map::default();
541 for (key, value) in iter {
542 let _ = map.upsert(key, value);
543 }
544 map
545 }
546}
547
548impl<'g, K, V> IntoIterator for &'g Map<K, V>
549where
550 K: Key,
551 V: Value,
552{
553 type Item = (K, &'g V);
554 type IntoIter = EntryIter<'g, 'static, K, V, RangeFull>;
555 fn into_iter(self) -> Self::IntoIter {
556 self.all().entries(Order::Ascend)
557 }
558}
559
560impl<'g, K, V> IntoIterator for &'g mut Map<K, V>
561where
562 K: Key,
563 V: Value,
564{
565 type Item = (K, &'g mut V);
566 type IntoIter = EntryIterMut<'g, 'static, K, V, RangeFull>;
567 fn into_iter(self) -> Self::IntoIter {
568 self.all_mut().entries_mut(Order::Ascend)
569 }
570}
571
572impl<K, V> Drop for Map<K, V>
573where
574 K: Key,
575 V: Value,
576{
577 fn drop(&mut self) {
578 let ControlFlow::Continue(()) = self.raw.postorder(None).try_fold((), |(), (_, child)| {
579 stat::increment(stat::Counter::FreeDrop);
580
581 // SAFETY: we have exclusive access to nodes and values in destructor
582 match child {
583 edge::Child::Value(value) => drop(unsafe { V::from_raw_unchecked(value) }),
584 edge::Child::Node(node) => unsafe {
585 stat::increment(stat::Counter::FreeDrop);
586 node.deallocate();
587 },
588 };
589
590 ControlFlow::<Infallible>::Continue(())
591 });
592 }
593}
594
595/// A logical entry in a [`SequentialMap`] that may be vacant or occupied.
596///
597/// See: [`btree_map::Entry`].
598pub enum Entry<'g, 'k, K, V>
599where
600 K: Key,
601 V: Value + 'g,
602{
603 /// A vacant entry.
604 Vacant(Vacant<'g, 'k, K, V>),
605 /// An occupied entry.
606 Occupied(Occupied<'g, V>),
607}
608
609impl<'g, 'k, K: Key, V: Value + 'g> Entry<'g, 'k, K, V> {
610 /// Insert `default` if there is no value associated with this
611 /// entry, then return a mutable reference to the current value.
612 ///
613 /// See: [`btree_map::Entry::or_insert`].
614 #[inline]
615 pub fn or_insert(self, default: V) -> &'g mut V {
616 match self {
617 Self::Occupied(entry) => entry.into_mut(),
618 Self::Vacant(entry) => entry.insert(default),
619 }
620 }
621
622 /// Like [`or_insert`][Self::or_insert], but lazily evaluates
623 /// `default`.
624 ///
625 /// See: [`btree_map::Entry::or_insert_with`].
626 #[inline]
627 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'g mut V {
628 match self {
629 Self::Occupied(entry) => entry.into_mut(),
630 Self::Vacant(entry) => entry.insert(default()),
631 }
632 }
633
634 /// If there is a value associated with this entry, then apply `modify` to it.
635 ///
636 /// See: [`btree_map::Entry::and_modify`].
637 #[inline]
638 pub fn and_modify<F>(self, modify: F) -> Self
639 where
640 F: FnOnce(&mut V),
641 {
642 match self {
643 Self::Occupied(mut entry) => {
644 modify(entry.get_mut());
645 Self::Occupied(entry)
646 }
647 Self::Vacant(entry) => Self::Vacant(entry),
648 }
649 }
650}
651
652impl<'g, 'k, K: Key, V: Value + Default + 'g> Entry<'g, 'k, K, V> {
653 /// Call [`or_insert_with`][Self::or_insert_with] with [`Default::default`].
654 ///
655 /// See: [`btree_map::Entry::or_default`]
656 #[inline]
657 pub fn or_default(self) -> &'g mut V {
658 self.or_insert_with(V::default)
659 }
660}
661
662/// A vacant entry in a [`SequentialMap`].
663pub struct Vacant<'g, 'k, K: Key, V: Value + 'g> {
664 pub(super) cursor: Cursor<'g, K::Read<'k>, path::Discard<K::Read<'k>>>,
665 pub(super) replace: bool,
666 pub(super) _value: PhantomData<&'g mut V>,
667}
668
669impl<'g, 'k, K: Key, V: Value + 'g> Vacant<'g, 'k, K, V> {
670 /// Insert `value` into this entry and return a mutable reference to it.
671 ///
672 /// See: [`btree_map::VacantEntry::insert`].
673 #[inline]
674 pub fn insert(self, value: V) -> &'g mut V {
675 self.insert_entry(value).into_mut()
676 }
677
678 /// Insert `value` into this entry and return an occupied entry.
679 ///
680 /// See: [`btree_map::VacantEntry::insert_entry`].
681 pub fn insert_entry(mut self, value: V) -> Occupied<'g, V> {
682 let new_value = V::into_raw(value);
683 let mut old_edge = unsafe { *self.cursor.edge_mut().get_mut_packed() };
684
685 if self.replace {
686 let old_node = old_edge.as_node().expect("Replace implies node");
687 let (_smo, new_edge) = unsafe { old_node.replace(old_edge.meta()) };
688 *unsafe { self.cursor.edge_mut() }.get_mut_packed() = new_edge;
689 old_edge = new_edge;
690 stat::increment(stat::Counter::FreeRetire);
691 unsafe { old_node.deallocate() };
692 }
693
694 match unsafe { self.cursor.traverse_insert(old_edge) } {
695 crate::raw::cursor::Insert::Value {
696 value: Some(_),
697 edge: _,
698 }
699 | crate::raw::cursor::Insert::Replace { .. } => unreachable!(),
700 crate::raw::cursor::Insert::Value {
701 value: None,
702 edge: old,
703 } => {
704 let (head, tail) = self.cursor.create_path(old, new_value);
705 *unsafe { self.cursor.edge_mut() }.get_mut_packed() = head;
706
707 let value = match tail {
708 None => unsafe { self.cursor.as_value_unchecked() },
709 Some(tail) => unsafe { Edge::as_value_unchecked(tail) },
710 };
711
712 Occupied {
713 value: value.cast::<V>(),
714 _value: PhantomData,
715 }
716 }
717 }
718 }
719}
720
721/// An occupied entry in a [`SequentialMap`].
722pub struct Occupied<'g, V: Value + 'g> {
723 pub(super) value: NonNull<V>,
724 pub(super) _value: PhantomData<&'g mut V>,
725}
726
727impl<'g, V: Value> Occupied<'g, V> {
728 /// Get an immutable reference to the value in this entry.
729 ///
730 /// See: [`btree_map::OccupiedEntry::get`].
731 #[inline]
732 pub fn get(&self) -> &V {
733 unsafe { self.value.as_ref() }
734 }
735
736 /// Get a mutable reference to the value in this entry.
737 ///
738 /// See: [`btree_map::OccupiedEntry::get_mut`].
739 #[inline]
740 pub fn get_mut(&mut self) -> &mut V {
741 unsafe { self.value.as_mut() }
742 }
743
744 /// Update the value in this entry to `value`.
745 ///
746 /// See: [`btree_map::OccupiedEntry::insert`].
747 #[inline]
748 pub fn update(&mut self, value: V) -> V {
749 unsafe { core::mem::replace(self.value.as_mut(), value) }
750 }
751
752 /// Convert this entry into a mutable reference,
753 /// preserving the lifetime.
754 ///
755 /// See: [`btree_map::OccupiedEntry::into_mut`].
756 #[inline]
757 pub fn into_mut(mut self) -> &'g mut V {
758 unsafe { self.value.as_mut() }
759 }
760}