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;
8use core::sync::atomic::Ordering;
9#[cfg_attr(not(doc), expect(unused))]
10use std::collections::btree_map;
11
12#[cfg_attr(not(doc), expect(unused))]
13use crate::SequentialMap;
14use crate::raw;
15use crate::raw::Cursor;
16use crate::raw::Edge;
17use crate::raw::Key;
18use crate::raw::cursor;
19use crate::raw::cursor::path;
20use crate::raw::edge;
21use crate::raw::iter::Order;
22use crate::sequential::EntryIter;
23use crate::sequential::EntryIterMut;
24use crate::sequential::Shard;
25use crate::sequential::ShardMut;
26use crate::sequential::Value;
27use crate::stat;
28
29/// Non-concurrent map that supports lexicographically ordered range and prefix scans.
30///
31/// # Usage
32///
33/// [`SequentialMap`] supports both point and scan operations, and tries to be roughly
34/// compatible with the standard library's [`BTreeMap`][std::collections::BTreeMap].
35///
36/// In general, radix trees do not explicitly store keys; they are implicitly
37/// encoded in the structure of the tree. This means that operations on [`SequentialMap`]
38/// generally take references to keys (see [`Key`]). Operations that insert and typically
39/// would take an owned key, like [`BTreeMap::insert`][std::collections::BTreeMap::insert],
40/// instead take a [`Key::Insert<'_>`][crate::Key::Insert]. Operations that
41/// do not insert a new key take a [`&Key::Borrowed`][crate::Key::Borrowed].
42///
43/// ## Point operations
44///
45/// The main caveat here is that [`SequentialMap::insert`] errors if the key is present,
46/// whereas [`BTreeMap::insert`][std::collections::BTreeMap::insert]
47/// updates. (To match the standard library behavior, use [`SequentialMap::upsert`] instead.)
48/// For more complex conditional logic, the [`SequentialMap::entry`] API mimics
49/// [`BTreeMap::entry`][std::collections::BTreeMap::entry].
50///
51/// ## Scan operations
52///
53/// For scan operations, [`SequentialMap`] exposes a two-phase API: the caller first selects
54/// a subtree (e.g., [`SequentialMap::prefix`] or [`SequentialMap::range_mut`]). This returns
55/// a [`Shard`] or [`ShardMut`], which can then be iterated over
56/// (e.g., [`Shard::entries`] or [`ShardMut::values_mut`]).
57/// This is in contrast to the standard library, where [`BTreeMap::range`][std::collections::BTreeMap::range]
58/// directly returns an iterator.
59///
60/// If the key type (see [`Key`]) is dynamically allocated, like [`BoxedStr`][crate::key::BoxedStr],
61/// iterating over keys can be expensive, as a key buffer must be updated
62/// during traversal, and then cloned once per key. This can be mitigated by
63/// (a) iterating over values instead of entries, (b) using the lending API
64/// (e.g., [`EntryIter::lend`]), which borrows from the iterator's internal
65/// buffer, or (c) using the internal iteration API[^iter] (e.g., [`EntryIterMut::try_fold`]),
66/// which also borrows from the iterator and can be much faster.
67///
68/// [^iter]: Should ideally replace with custom [`Iterator::try_fold`] implementation,
69/// but this currently uses the unstable Try trait.
70/// See also [this issue](https://github.com/nnethercote/perf-book/issues/70).
71#[repr(transparent)]
72pub struct Map<K: Key, V: Value> {
73 pub(crate) raw: raw::Map<K>,
74 _value: PhantomData<V>,
75}
76
77impl<K, V> Default for Map<K, V>
78where
79 K: Key,
80 V: Value,
81{
82 fn default() -> Self {
83 Self::new()
84 }
85}
86
87/// # Basic operations
88impl<K, V> Map<K, V>
89where
90 K: Key,
91 V: Value,
92{
93 /// Constructs a new empty map. Does not allocate.
94 #[inline]
95 pub const fn new() -> Self {
96 Self {
97 raw: raw::Map::new(),
98 _value: PhantomData,
99 }
100 }
101}
102
103/// # Point operations
104///
105/// This set of operations operates on a single key-value pair.
106impl<K, V> Map<K, V>
107where
108 K: Key,
109 V: Value,
110{
111 /// Returns whether `key` has an associated value.
112 ///
113 /// # Examples
114 ///
115 /// ```rust
116 /// use arctic::SequentialMap;
117 ///
118 /// let mut map = SequentialMap::<u64, u64>::new();
119 /// map.insert(1, 2).expect("Key is not present");
120 /// assert!(map.contains_key(&1));
121 /// assert!(!map.contains_key(&2));
122 /// ```
123 pub fn contains_key(&self, key: &K::Borrowed) -> bool {
124 self.get(key).is_some()
125 }
126
127 /// Returns an immutable reference to the value associated with `key`.
128 ///
129 /// For a mutable reference, see [`Map::get_mut`].
130 ///
131 /// # Examples
132 ///
133 /// ```rust
134 /// use arctic::SequentialMap;
135 ///
136 /// let mut map = SequentialMap::<u64, u64>::new();
137 /// map.insert(1, 2).expect("Key is not present");
138 /// assert_eq!(map.get(&1), Some(&2));
139 /// assert_eq!(map.get(&2), None);
140 /// ```
141 pub fn get(&self, key: &K::Borrowed) -> Option<&V> {
142 let reader = K::Read::from(key);
143 self.get_raw(reader)
144 .map(|value| unsafe { value.cast::<V>().as_ref() })
145 }
146
147 /// Returns a mutable reference to the value associated with `key`.
148 ///
149 /// For an immutable reference, see [`Map::get`].
150 ///
151 /// # Examples
152 ///
153 /// ```rust
154 /// use arctic::SequentialMap;
155 ///
156 /// let mut map = SequentialMap::<u64, u64>::new();
157 /// let key = 1;
158 /// map.insert(key, 2).expect("Key is not present");
159 /// let value = map.get_mut(&key).expect("Key is present");
160 /// *value = 3;
161 /// assert_eq!(map.get(&key), Some(&3));
162 /// ```
163 pub fn get_mut(&mut self, key: &K::Borrowed) -> Option<&mut V> {
164 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(key) };
165 cursor.traverse_value()?;
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 cursor.traverse_value()?;
451 Some(unsafe { cursor.as_value_unchecked() })
452 }
453
454 pub(super) unsafe fn update_raw(
455 &mut self,
456 reader: K::Read<'_>,
457 value: u64,
458 ) -> Result<(u64, NonNull<u64>), u64> {
459 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(reader) };
460 match cursor.traverse_value() {
461 None => Err(value),
462 Some(update) => {
463 let edge = unsafe { cursor.edge_mut() };
464 *edge.get_mut_packed() = Edge::new_value(update.edge.meta(), value.into_raw());
465 Ok((update.value, unsafe {
466 Edge::as_value_unchecked(NonNull::from(edge))
467 }))
468 }
469 }
470 }
471
472 pub(super) unsafe fn remove_raw<'k, P: cursor::Path<K::Read<'k>>>(
473 &mut self,
474 reader: K::Read<'k>,
475 ) -> Option<u64> {
476 let mut cursor = unsafe { self.raw.cursor::<path::Full<_>>(reader) };
477
478 let update = cursor.traverse_value()?;
479
480 unsafe {
481 cursor
482 .edge_mut()
483 .store_packed(Edge::<K::Edge>::NULL, Ordering::Relaxed);
484 }
485
486 while let Ok(Some((_, target))) = cursor.pop() {
487 if unsafe { target.len::<K::Edge>() } > 1 {
488 break;
489 }
490
491 let old = unsafe { cursor.edge_mut() }.get_mut_packed();
492 validate_eq!(old.child(), Some(edge::Child::Node(target)));
493
494 let (_smo, new) = unsafe { target.replace::<K::Edge>(old.meta()) };
495 *unsafe { cursor.edge_mut() }.get_mut_packed() = new;
496 unsafe { target.deallocate() };
497 }
498
499 Some(update.value)
500 }
501
502 #[inline]
503 pub(super) unsafe fn entry_raw<'k>(&mut self, reader: K::Read<'k>) -> Entry<'_, 'k, K, V> {
504 let mut cursor = unsafe { self.raw.cursor::<path::Discard<_>>(reader) };
505
506 match cursor.traverse_insert() {
507 raw::cursor::Insert::Value {
508 value: Some(_),
509 edge: _,
510 } => Entry::Occupied(Occupied {
511 value: unsafe { cursor.as_value_unchecked().cast::<V>() },
512 _value: PhantomData,
513 }),
514
515 raw::cursor::Insert::Value {
516 value: None,
517 edge: _,
518 } => Entry::Vacant(Vacant {
519 cursor,
520 replace: false,
521 _value: PhantomData,
522 }),
523
524 raw::cursor::Insert::Replace { .. } => Entry::Vacant(Vacant {
525 cursor,
526 replace: true,
527 _value: PhantomData,
528 }),
529 }
530 }
531}
532
533impl<'k, K, V> FromIterator<(K::Insert<'k>, V)> for Map<K, V>
534where
535 K: Key,
536 V: Value,
537{
538 fn from_iter<T: IntoIterator<Item = (K::Insert<'k>, V)>>(iter: T) -> Self {
539 let mut map = Map::default();
540 for (key, value) in iter {
541 let _ = map.upsert(key, value);
542 }
543 map
544 }
545}
546
547impl<'g, K, V> IntoIterator for &'g Map<K, V>
548where
549 K: Key,
550 V: Value,
551{
552 type Item = (K, &'g V);
553 type IntoIter = EntryIter<'g, 'static, K, V, RangeFull>;
554 fn into_iter(self) -> Self::IntoIter {
555 self.all().entries(Order::Ascend)
556 }
557}
558
559impl<'g, K, V> IntoIterator for &'g mut Map<K, V>
560where
561 K: Key,
562 V: Value,
563{
564 type Item = (K, &'g mut V);
565 type IntoIter = EntryIterMut<'g, 'static, K, V, RangeFull>;
566 fn into_iter(self) -> Self::IntoIter {
567 self.all_mut().entries_mut(Order::Ascend)
568 }
569}
570
571impl<K, V> Drop for Map<K, V>
572where
573 K: Key,
574 V: Value,
575{
576 fn drop(&mut self) {
577 let ControlFlow::Continue(()) = self.raw.postorder(None).try_fold((), |(), (_, child)| {
578 stat::increment(stat::Counter::FreeDrop);
579
580 // SAFETY: we have exclusive access to nodes and values in destructor
581 match child {
582 edge::Child::Value(value) => drop(unsafe { V::from_raw_unchecked(value) }),
583 edge::Child::Node(node) => unsafe {
584 stat::increment(stat::Counter::FreeDrop);
585 node.deallocate();
586 },
587 };
588
589 ControlFlow::<Infallible>::Continue(())
590 });
591 }
592}
593
594/// A logical entry in a [`SequentialMap`] that may be vacant or occupied.
595///
596/// See: [`btree_map::Entry`].
597pub enum Entry<'g, 'k, K, V>
598where
599 K: Key,
600 V: Value + 'g,
601{
602 /// A vacant entry.
603 Vacant(Vacant<'g, 'k, K, V>),
604 /// An occupied entry.
605 Occupied(Occupied<'g, V>),
606}
607
608impl<'g, 'k, K: Key, V: Value + 'g> Entry<'g, 'k, K, V> {
609 /// Insert `default` if there is no value associated with this
610 /// entry, then return a mutable reference to the current value.
611 ///
612 /// See: [`btree_map::Entry::or_insert`].
613 #[inline]
614 pub fn or_insert(self, default: V) -> &'g mut V {
615 match self {
616 Self::Occupied(entry) => entry.into_mut(),
617 Self::Vacant(entry) => entry.insert(default),
618 }
619 }
620
621 /// Like [`or_insert`][Self::or_insert], but lazily evaluates
622 /// `default`.
623 ///
624 /// See: [`btree_map::Entry::or_insert_with`].
625 #[inline]
626 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'g mut V {
627 match self {
628 Self::Occupied(entry) => entry.into_mut(),
629 Self::Vacant(entry) => entry.insert(default()),
630 }
631 }
632
633 /// If there is a value associated with this entry, then apply `modify` to it.
634 ///
635 /// See: [`btree_map::Entry::and_modify`].
636 #[inline]
637 pub fn and_modify<F>(self, modify: F) -> Self
638 where
639 F: FnOnce(&mut V),
640 {
641 match self {
642 Self::Occupied(mut entry) => {
643 modify(entry.get_mut());
644 Self::Occupied(entry)
645 }
646 Self::Vacant(entry) => Self::Vacant(entry),
647 }
648 }
649}
650
651impl<'g, 'k, K: Key, V: Value + Default + 'g> Entry<'g, 'k, K, V> {
652 /// Call [`or_insert_with`][Self::or_insert_with] with [`Default::default`].
653 ///
654 /// See: [`btree_map::Entry::or_default`]
655 #[inline]
656 pub fn or_default(self) -> &'g mut V {
657 self.or_insert_with(V::default)
658 }
659}
660
661/// A vacant entry in a [`SequentialMap`].
662pub struct Vacant<'g, 'k, K: Key, V: Value + 'g> {
663 pub(super) cursor: Cursor<'g, K::Read<'k>, path::Discard<K::Read<'k>>>,
664 pub(super) replace: bool,
665 pub(super) _value: PhantomData<&'g mut V>,
666}
667
668impl<'g, 'k, K: Key, V: Value + 'g> Vacant<'g, 'k, K, V> {
669 /// Insert `value` into this entry and return a mutable reference to it.
670 ///
671 /// See: [`btree_map::VacantEntry::insert`].
672 #[inline]
673 pub fn insert(self, value: V) -> &'g mut V {
674 self.insert_entry(value).into_mut()
675 }
676
677 /// Insert `value` into this entry and return an occupied entry.
678 ///
679 /// See: [`btree_map::VacantEntry::insert_entry`].
680 pub fn insert_entry(mut self, value: V) -> Occupied<'g, V> {
681 let new_value = V::into_raw(value);
682
683 if self.replace {
684 let old = unsafe { *self.cursor.edge_mut().get_mut_packed() };
685 let old_node = old.as_node().expect("Replace implies node");
686 let (_smo, new) = unsafe { old_node.replace(old.meta()) };
687 *unsafe { self.cursor.edge_mut() }.get_mut_packed() = new;
688 stat::increment(stat::Counter::FreeRetire);
689 unsafe { old_node.deallocate() };
690 }
691
692 match self.cursor.traverse_insert() {
693 crate::raw::cursor::Insert::Value {
694 value: Some(_),
695 edge: _,
696 }
697 | crate::raw::cursor::Insert::Replace { .. } => unreachable!(),
698 crate::raw::cursor::Insert::Value {
699 value: None,
700 edge: old,
701 } => {
702 let (head, tail) = self.cursor.create_path(old, new_value);
703 *unsafe { self.cursor.edge_mut() }.get_mut_packed() = head;
704
705 let value = match tail {
706 None => unsafe { self.cursor.as_value_unchecked() },
707 Some(tail) => unsafe { Edge::as_value_unchecked(tail) },
708 };
709
710 Occupied {
711 value: value.cast::<V>(),
712 _value: PhantomData,
713 }
714 }
715 }
716 }
717}
718
719/// An occupied entry in a [`SequentialMap`].
720pub struct Occupied<'g, V: Value + 'g> {
721 pub(super) value: NonNull<V>,
722 pub(super) _value: PhantomData<&'g mut V>,
723}
724
725impl<'g, V: Value> Occupied<'g, V> {
726 /// Get an immutable reference to the value in this entry.
727 ///
728 /// See: [`btree_map::OccupiedEntry::get`].
729 #[inline]
730 pub fn get(&self) -> &V {
731 unsafe { self.value.as_ref() }
732 }
733
734 /// Get a mutable reference to the value in this entry.
735 ///
736 /// See: [`btree_map::OccupiedEntry::get_mut`].
737 #[inline]
738 pub fn get_mut(&mut self) -> &mut V {
739 unsafe { self.value.as_mut() }
740 }
741
742 /// Update the value in this entry to `value`.
743 ///
744 /// See: [`btree_map::OccupiedEntry::insert`].
745 #[inline]
746 pub fn update(&mut self, value: V) -> V {
747 unsafe { core::mem::replace(self.value.as_mut(), value) }
748 }
749
750 /// Convert this entry into a mutable reference,
751 /// preserving the lifetime.
752 ///
753 /// See: [`btree_map::OccupiedEntry::into_mut`].
754 #[inline]
755 pub fn into_mut(mut self) -> &'g mut V {
756 unsafe { self.value.as_mut() }
757 }
758}