| blob | 50797c2e443d23e6f3b2151263078f2f65676fe9 |
1 // Copyright (c) Facebook, Inc. and its affiliates.
2 //
3 // This source code is licensed under the MIT license found in the
4 // LICENSE file in the "hack" directory of this source tree.
6 //! Associative array types.
7 //!
8 //! At the moment, we are using the bumpalo allocator for arena allocation.
9 //! Because the stdlib types do not yet provide the ability to choose the
10 //! allocator used when they are allocated or resized, the bumpalo library
11 //! provides its own growable Vec and String types. Since bumpalo does not
12 //! provide its own map or set types, we must define our own if we want to
13 //! control where they are allocated.
14 //!
15 //! This module defines map types backed by bumpalo's Vec. It is useful for maps
16 //! which are built all at once, and never modified thereafter (e.g., maps in
17 //! ASTs). When immutable semantics are desired, but updating is necessary,
18 //! consider the `arena_collections::map` submodule instead, for an immutable
19 //! balanced binary tree. The Vec-backed maps in this module may benefit from
20 //! better cache efficiency, and so may outperform the balanced tree
21 //! implementation in some circumstances.
23 use std::borrow::Borrow;
24 use std::fmt::Debug;
26 use bumpalo::Bump;
27 use serde::{Deserialize, Serialize};
29 use arena_trait::TrivialDrop;
30 use ocamlrep::{FromOcamlRepIn, ToOcamlRep};
32 /// Perform a linear search for the last entry in the slice with the given key.
33 #[inline(always)]
34 fn get_last_entry<'a, K, V, Q: ?Sized>(entries: &'a [(K, V)], key: &Q) -> Option<&'a (K, V)>
35 where
36 K: Borrow<Q>,
37 Q: PartialEq,
38 {
39 entries.iter().rev().find(|(k, _)| key == k.borrow())
40 }
42 /// Perform a linear search for the last entry in the slice with the given key
43 /// and return its index in the slice.
44 #[inline(always)]
45 fn get_last_index<'a, K, V, Q: ?Sized>(entries: &'a [(K, V)], key: &Q) -> Option<usize>
46 where
47 K: Borrow<Q>,
48 Q: PartialEq,
49 {
50 entries
51 .iter()
52 .enumerate()
53 .rev()
54 .find(|(_, (k, _))| key == k.borrow())
55 .map(|(idx, _)| idx)
56 }
58 /// A readonly associative array.
59 ///
60 /// * Lookups run in linear time
61 /// * Entries with duplicate keys are permitted (but only observable using iterators)
62 #[derive(Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
63 pub struct AssocList<'a, K, V> {
64 entries: &'a [(K, V)],
65 }
67 impl<'a, K, V> AssocList<'a, K, V> {
68 /// Make a new `AssocList` containing the given key-value pairs.
69 ///
70 /// # Examples
71 ///
72 /// ```
73 /// use arena_collections::AssocList;
74 ///
75 /// let entries = [(1, "a")];
76 /// let alist = AssocList::new(&entries[..]);
77 /// ```
78 #[inline]
79 pub const fn new(entries: &'a [(K, V)]) -> Self {
80 Self { entries }
81 }
83 /// Returns a reference to the value corresponding to the key.
84 ///
85 /// The key may be any borrowed form of the list's key type, but the
86 /// ordering on the borrowed form *must* match the ordering on the key type.
87 ///
88 /// If multiple entries in the map have keys equal to the given key, the
89 /// value corresponding to the last entry (the one with the larger index in
90 /// the slice passed to `AssocList::new`) will be returned.
91 ///
92 /// # Examples
93 ///
94 /// ```
95 /// use arena_collections::AssocList;
96 ///
97 /// let entries = [(1, "a")];
98 /// let alist = AssocList::new(&entries[..]);
99 /// assert_eq!(alist.get(&1), Some(&"a"));
100 /// assert_eq!(alist.get(&2), None);
101 /// ```
102 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
103 where
104 K: Borrow<Q>,
105 Q: PartialEq,
106 {
107 get_last_entry(self.entries, key).map(|(_, v)| v)
108 }
110 /// Returns the key-value pair corresponding to the supplied key.
111 ///
112 /// The key may be any borrowed form of the list's key type, but the
113 /// ordering on the borrowed form *must* match the ordering on the key type.
114 ///
115 /// If multiple entries in the map have keys equal to the given key, the
116 /// last entry (the one with the larger index in the slice passed to
117 /// `AssocList::new`) will be returned.
118 ///
119 /// # Examples
120 ///
121 /// ```
122 /// use arena_collections::AssocList;
123 ///
124 /// let entries = [(1, "a")];
125 /// let alist = AssocList::new(&entries[..]);
126 /// assert_eq!(alist.get_key_value(&1), Some((&1, &"a")));
127 /// assert_eq!(alist.get_key_value(&2), None);
128 /// ```
129 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
130 where
131 K: Borrow<Q>,
132 Q: PartialEq,
133 {
134 get_last_entry(self.entries, key).map(|(k, v)| (k, v))
135 }
137 /// Returns `true` if the list contains a value for the specified key.
138 ///
139 /// The key may be any borrowed form of the list's key type, but the
140 /// ordering on the borrowed form *must* match the ordering on the key type.
141 ///
142 /// # Examples
143 ///
144 /// ```
145 /// use arena_collections::AssocList;
146 ///
147 /// let entries = [(1, "a")];
148 /// let alist = AssocList::new(&entries[..]);
149 /// assert_eq!(alist.contains_key(&1), true);
150 /// assert_eq!(alist.contains_key(&2), false);
151 /// ```
152 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
153 where
154 K: Borrow<Q>,
155 Q: PartialEq,
156 {
157 get_last_entry(self.entries, key).is_some()
158 }
160 /// Gets an iterator over the entries of the association list.
161 ///
162 /// # Examples
163 ///
164 /// ```
165 /// use arena_collections::AssocList;
166 ///
167 /// let entries = [(1, "a"), (2, "b")];
168 /// let alist = AssocList::new(&entries[..]);
169 ///
170 /// for (key, value) in alist.iter() {
171 /// println!("{}: {}", key, value);
172 /// }
173 ///
174 /// let (first_key, first_value) = alist.iter().next().unwrap();
175 /// assert_eq!((*first_key, *first_value), (1, "a"));
176 /// ```
177 pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
178 self.entries.iter().map(|(k, v)| (k, v))
179 }
181 /// Gets an iterator over the keys of the association list.
182 ///
183 /// # Examples
184 ///
185 /// ```
186 /// use arena_collections::AssocList;
187 ///
188 /// let entries = [(1, "a"), (2, "b")];
189 /// let alist = AssocList::new(&entries[..]);
190 ///
191 /// let keys: Vec<_> = alist.keys().copied().collect();
192 /// assert_eq!(keys, [1, 2]);
193 /// ```
194 pub fn keys(&self) -> impl Iterator<Item = &K> {
195 self.entries.iter().map(|(k, _)| k)
196 }
198 /// Gets an iterator over the values of the association list.
199 ///
200 /// # Examples
201 ///
202 /// ```
203 /// use arena_collections::AssocList;
204 ///
205 /// let entries = [(1, "hello"), (2, "goodbye")];
206 /// let alist = AssocList::new(&entries[..]);
207 ///
208 /// let values: Vec<&str> = alist.values().copied().collect();
209 /// assert_eq!(values, ["hello", "goodbye"]);
210 /// ```
211 pub fn values(&self) -> impl Iterator<Item = &V> {
212 self.entries.iter().map(|(_, v)| v)
213 }
215 /// Returns the number of entries in the list.
216 ///
217 /// # Examples
218 ///
219 /// ```
220 /// use arena_collections::AssocList;
221 ///
222 /// let entries = [(1, "a")];
223 /// let alist = AssocList::new(&entries[0..entries]);
224 /// assert_eq!(alist.len(), 0);
225 /// let alist = AssocList::new(&entries[0..1]);
226 /// assert_eq!(alist.len(), 1);
227 /// ```
228 pub fn len(&self) -> usize {
229 self.entries.len()
230 }
232 /// Returns `true` if the list contains no entries.
233 ///
234 /// # Examples
235 ///
236 /// ```
237 /// use arena_collections::AssocList;
238 ///
239 /// let entries = [(1, "a")];
240 /// let alist = AssocList::new(&entries[0..entries]);
241 /// assert!(alist.is_empty());
242 /// let alist = AssocList::new(&entries[0..1]);
243 /// assert!(!alist.is_empty());
244 /// ```
245 pub fn is_empty(&self) -> bool {
246 self.entries.is_empty()
247 }
248 }
250 impl<K, V> TrivialDrop for AssocList<'_, K, V> {}
251 impl<K, V> Copy for AssocList<'_, K, V> {}
252 impl<K, V> Clone for AssocList<'_, K, V> {
253 fn clone(&self) -> Self {
254 *self
255 }
256 }
258 impl<K: Debug, V: Debug> Debug for AssocList<'_, K, V> {
259 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
260 fmt.debug_map().entries(self.iter()).finish()
261 }
262 }
264 impl<'a, K, V> From<AssocListMut<'a, K, V>> for AssocList<'a, K, V> {
265 #[inline]
266 fn from(alist: AssocListMut<'a, K, V>) -> Self {
267 AssocList::new(alist.entries.into_bump_slice())
268 }
269 }
271 /// A mutable associative array, allocated in a given arena.
272 ///
273 /// * Lookups, replacements, and removals run in linear time
274 /// * Insertions run in constant time
275 /// * Entries with duplicate keys are permitted (but only observable using iterators)
276 #[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
277 pub struct AssocListMut<'bump, K, V> {
278 entries: bumpalo::collections::Vec<'bump, (K, V)>,
279 }
281 impl<'bump, K, V> AssocListMut<'bump, K, V> {
282 /// Constructs a new, empty `AssocListMut`.
283 ///
284 /// The list will not allocate until entries are inserted.
285 ///
286 /// # Examples
287 ///
288 /// ```
289 /// use bumpalo::Bump;
290 /// use arena_collections::AssocListMut;
291 ///
292 /// let b = Bump::new();
293 /// let mut alist: AssocListMut<i32> = AssocListMut::new_in(&b);
294 /// ```
295 #[inline]
296 pub fn new_in(bump: &'bump Bump) -> Self {
297 AssocListMut {
298 entries: bumpalo::collections::Vec::new_in(bump),
299 }
300 }
302 /// Constructs a new, empty `AssocListMut` with the specified capacity.
303 ///
304 /// The list will be able to hold exactly `capacity` elements without
305 /// reallocating. If `capacity` is 0, the list will not allocate.
306 ///
307 /// It is important to note that although the returned list has the
308 /// *capacity* specified, the list will have a zero *length*.
309 ///
310 /// # Examples
311 ///
312 /// ```
313 /// use bumpalo::Bump;
314 /// use arena_collections::AssocListMut;
315 ///
316 /// let b = Bump::new();
317 ///
318 /// let mut alist = AssocListMut::with_capacity_in(10, &b);
319 ///
320 /// // The list contains no items, even though it has capacity for more
321 /// assert_eq!(alist.len(), 0);
322 ///
323 /// // These are all done without reallocating...
324 /// for i in 0..10 {
325 /// alist.insert(i, i);
326 /// }
327 ///
328 /// // ...but this may make the list reallocate
329 /// alist.insert(11, 11);
330 /// ```
331 #[inline]
332 pub fn with_capacity_in(capacity: usize, bump: &'bump Bump) -> Self {
333 AssocListMut {
334 entries: bumpalo::collections::Vec::with_capacity_in(capacity, bump),
335 }
336 }
338 /// Insert the given key-value pair into the association list.
339 ///
340 /// If an entry with the given key already exists in the list, it will
341 /// remain there, but future calls to `AssocListMut::get` will return the
342 /// newly-inserted value instead of the extant one.
343 ///
344 /// # Examples
345 ///
346 /// ```
347 /// use bumpalo::Bump;
348 /// use arena_collections::AssocListMut;
349 ///
350 /// let b = Bump::new();
351 /// let mut alist = AssocListMut::new_in(&b);
352 /// alist.insert(1, "a");
353 /// assert_eq!(alist.get(&1), Some(&"a"));
354 /// alist.insert(1, "b");
355 /// assert_eq!(alist.get(&1), Some(&"b"));
356 /// assert_eq!(alist.len(), 2);
357 /// ```
358 #[inline]
359 pub fn insert(&mut self, key: K, value: V) {
360 self.entries.push((key, value))
361 }
363 /// Insert the given key-value pair into the association list.
364 ///
365 /// If one entry with the given key already exists in the list, it will be
366 /// removed, and its value will be returned. If multiple entries with the
367 /// given key already exist in the list, only the most recently inserted one
368 /// will be removed.
369 ///
370 /// # Examples
371 ///
372 /// ```
373 /// use bumpalo::Bump;
374 /// use arena_collections::AssocListMut;
375 ///
376 /// let b = Bump::new();
377 /// let mut alist = AssocListMut::new_in(&b);
378 /// alist.insert_or_replace(1, "a");
379 /// assert_eq!(alist.get(&1), Some(&"a"));
380 /// alist.insert_or_replace(1, "b");
381 /// assert_eq!(alist.get(&1), Some(&"b"));
382 /// assert_eq!(alist.len(), 1);
383 /// ```
384 pub fn insert_or_replace(&mut self, key: K, value: V) -> Option<V>
385 where
386 K: PartialEq,
387 {
388 match get_last_index(&self.entries, &key) {
389 None => {
390 self.insert(key, value);
391 None
392 }
393 Some(idx) => {
394 let mut entry = (key, value);
395 std::mem::swap(&mut self.entries[idx], &mut entry);
396 Some(entry.1)
397 }
398 }
399 }
401 /// Remove a key from the list, returning the value at the key if the key
402 /// was previously in the list.
403 ///
404 /// The key may be any borrowed form of the list's key type, but the
405 /// ordering on the borrowed form *must* match the ordering on the key type.
406 ///
407 /// If multiple entries with the given key exist in the list, only the last
408 /// will be removed (the one which would b returned by
409 /// `AssocListMut::get`).
410 ///
411 /// # Examples
412 ///
413 /// ```
414 /// use bumpalo::Bump;
415 /// use arena_collections::AssocListMut;
416 ///
417 /// let b = Bump::new();
418 /// let mut alist = AssocListMut::new_in(&b);
419 /// alist.insert(1, "a");
420 /// alist.insert(1, "b");
421 /// assert_eq!(alist.get(&1), Some(&"b"));
422 /// alist.remove(&1);
423 /// assert_eq!(alist.get(&1), Some(&"a"));
424 /// alist.remove(&1);
425 /// assert_eq!(alist.get(&1), None);
426 /// ```
427 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
428 where
429 K: Borrow<Q>,
430 Q: PartialEq,
431 {
432 match get_last_index(&self.entries, key) {
433 None => None,
434 Some(idx) => Some(self.entries.remove(idx).1),
435 }
436 }
438 /// Removes all entries with the given key from the list. Returns true if
439 /// any entries were removed.
440 ///
441 /// The key may be any borrowed form of the list's key type, but the
442 /// ordering on the borrowed form *must* match the ordering on the key type.
443 ///
444 /// # Examples
445 ///
446 /// ```
447 /// use bumpalo::Bump;
448 /// use arena_collections::AssocListMut;
449 ///
450 /// let b = Bump::new();
451 /// let mut alist = AssocListMut::new_in(&b);
452 /// alist.insert(1, "a");
453 /// alist.insert(1, "b");
454 /// assert_eq!(alist.get(&1), Some(&"b"));
455 /// alist.remove_all(&1);
456 /// assert_eq!(alist.get(&1), None);
457 /// ```
458 pub fn remove_all<Q: ?Sized>(&mut self, key: &Q) -> bool
459 where
460 K: Borrow<Q>,
461 Q: PartialEq,
462 {
463 let len_before = self.len();
464 self.entries.retain(|(k, _)| key != k.borrow());
465 let len_after = self.len();
466 len_before != len_after
467 }
469 /// Returns a reference to the value corresponding to the key.
470 ///
471 /// The key may be any borrowed form of the list's key type, but the
472 /// ordering on the borrowed form *must* match the ordering on the key type.
473 ///
474 /// If multiple entries in the map have keys equal to the given key, the
475 /// value in the most recently inserted entry will be returned.
476 ///
477 /// # Examples
478 ///
479 /// ```
480 /// use bumpalo::Bump;
481 /// use arena_collections::AssocListMut;
482 ///
483 /// let b = Bump::new();
484 /// let mut alist = AssocListMut::new_in(&b);
485 /// alist.insert(1, "a");
486 /// assert_eq!(alist.get(&1), Some(&"a"));
487 /// assert_eq!(alist.get(&2), None);
488 /// ```
489 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
490 where
491 K: Borrow<Q>,
492 Q: PartialEq,
493 {
494 get_last_entry(&self.entries, key).map(|(_, v)| v)
495 }
497 /// Returns the key-value pair corresponding to the supplied key.
498 ///
499 /// The key may be any borrowed form of the list's key type, but the
500 /// ordering on the borrowed form *must* match the ordering on the key type.
501 ///
502 /// If multiple entries in the map have keys equal to the given key, the
503 /// most recently inserted entry will be returned.
504 ///
505 /// # Examples
506 ///
507 /// ```
508 /// use bumpalo::Bump;
509 /// use arena_collections::AssocListMut;
510 ///
511 /// let b = Bump::new();
512 /// let mut alist = AssocListMut::new_in(&b);
513 /// alist.insert(1, "a");
514 /// assert_eq!(alist.get_key_value(&1), Some((&1, &"a")));
515 /// assert_eq!(alist.get_key_value(&2), None);
516 /// ```
517 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
518 where
519 K: Borrow<Q>,
520 Q: PartialEq,
521 {
522 get_last_entry(&self.entries, key).map(|(k, v)| (k, v))
523 }
525 /// Returns `true` if the list contains a value for the specified key.
526 ///
527 /// The key may be any borrowed form of the list's key type, but the
528 /// ordering on the borrowed form *must* match the ordering on the key type.
529 ///
530 /// # Examples
531 ///
532 /// ```
533 /// use bumpalo::Bump;
534 /// use arena_collections::AssocListMut;
535 ///
536 /// let b = Bump::new();
537 /// let mut alist = AssocListMut::new_in(&b);
538 /// alist.insert(1, "a");
539 /// assert_eq!(alist.contains_key(&1), true);
540 /// assert_eq!(alist.contains_key(&2), false);
541 /// ```
542 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
543 where
544 K: Borrow<Q>,
545 Q: PartialEq,
546 {
547 self.get(key).is_some()
548 }
550 /// Gets an iterator over the entries of the association list.
551 ///
552 /// # Examples
553 ///
554 /// ```
555 /// use bumpalo::Bump;
556 /// use arena_collections::AssocListMut;
557 ///
558 /// let b = Bump::new();
559 /// let mut alist = AssocListMut::new_in(&b);
560 /// alist.insert(1, "a");
561 /// alist.insert(2, "b");
562 ///
563 /// for (key, value) in alist.iter() {
564 /// println!("{}: {}", key, value);
565 /// }
566 ///
567 /// let (first_key, first_value) = alist.iter().next().unwrap();
568 /// assert_eq!((*first_key, *first_value), (1, "a"));
569 /// ```
570 pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
571 self.entries.iter().map(|(k, v)| (k, v))
572 }
574 /// Gets an iterator over the keys of the association list.
575 ///
576 /// # Examples
577 ///
578 /// ```
579 /// use bumpalo::Bump;
580 /// use arena_collections::AssocListMut;
581 ///
582 /// let b = Bump::new();
583 /// let mut alist = AssocListMut::new_in(&b);
584 /// alist.insert(1, "a");
585 /// alist.insert(2, "b");
586 ///
587 /// let keys: Vec<_> = alist.keys().copied().collect();
588 /// assert_eq!(keys, [1, 2]);
589 /// ```
590 pub fn keys(&self) -> impl Iterator<Item = &K> {
591 self.entries.iter().map(|(k, _)| k)
592 }
594 /// Gets an iterator over the values of the association list.
595 ///
596 /// # Examples
597 ///
598 /// ```
599 /// use bumpalo::Bump;
600 /// use arena_collections::AssocListMut;
601 ///
602 /// let b = Bump::new();
603 /// let mut alist = AssocListMut::new_in(&b);
604 /// alist.insert(1, "hello");
605 /// alist.insert(2, "goodbye");
606 ///
607 /// let values: Vec<&str> = alist.values().copied().collect();
608 /// assert_eq!(values, ["hello", "goodbye"]);
609 /// ```
610 pub fn values(&self) -> impl Iterator<Item = &V> {
611 self.entries.iter().map(|(_, v)| v)
612 }
614 /// Returns the number of entries in the list.
615 ///
616 /// # Examples
617 ///
618 /// ```
619 /// use bumpalo::Bump;
620 /// use arena_collections::AssocListMut;
621 ///
622 /// let b = Bump::new();
623 /// let mut alist = AssocListMut::new_in(&b);
624 /// assert_eq!(alist.len(), 0);
625 /// alist.insert(1, "a");
626 /// assert_eq!(alist.len(), 1);
627 /// ```
628 pub fn len(&self) -> usize {
629 self.entries.len()
630 }
632 /// Returns `true` if the list contains no entries.
633 ///
634 /// # Examples
635 ///
636 /// ```
637 /// use bumpalo::Bump;
638 /// use arena_collections::AssocListMut;
639 ///
640 /// let b = Bump::new();
641 /// let mut alist = AssocListMut::new_in(&b);
642 /// assert!(alist.is_empty());
643 /// alist.insert(1, "a");
644 /// assert!(!alist.is_empty());
645 /// ```
646 pub fn is_empty(&self) -> bool {
647 self.entries.is_empty()
648 }
649 }
651 impl<K: Debug, V: Debug> Debug for AssocListMut<'_, K, V> {
652 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
653 fmt.debug_map().entries(self.iter()).finish()
654 }
655 }
657 /// Get an entry in the slice with the given key. Performs a linear search on
658 /// small slices, and a binary search otherwise.
659 #[inline(always)]
660 fn get_sorted_entry<'a, K, V, Q: ?Sized>(entries: &'a [(K, V)], key: &Q) -> Option<&'a (K, V)>
661 where
662 K: Borrow<Q>,
663 Q: Ord,
664 {
665 // TODO: tune this threshold based on perf results
666 const BINARY_SEARCH_LEN_THRESHOLD: usize = 32;
668 if entries.len() < BINARY_SEARCH_LEN_THRESHOLD {
669 entries.iter().find(|(k, _)| key == k.borrow())
670 } else {
671 let index = entries
672 .binary_search_by(|(k, _)| k.borrow().cmp(key))
673 .ok()?;
674 Some(&entries[index])
675 }
676 }
678 /// A readonly associative array, sorted by key, containing no duplicate keys.
679 ///
680 /// * Lookups run in log(n) time
681 /// * Entries with duplicate keys are not permitted. When constructing a
682 /// `SortedAssocList` from an `AssocListMut`, entries will be deduplicated by
683 /// key, and only the most recently inserted entry for each key will be
684 /// retained.
685 #[derive(Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
686 #[serde(bound(
687 deserialize = "K: 'de + arena_deserializer::DeserializeInArena<'de>, V: 'de + arena_deserializer::DeserializeInArena<'de>"
688 ))]
689 pub struct SortedAssocList<'a, K, V> {
690 #[serde(deserialize_with = "arena_deserializer::arena", borrow)]
691 entries: &'a [(K, V)],
692 }
694 arena_deserializer::impl_deserialize_in_arena!(SortedAssocList<'arena, K, V>);
696 impl<'a, K, V> SortedAssocList<'a, K, V> {
697 /// Returns the empty association list.
698 pub fn empty() -> Self {
699 SortedAssocList { entries: &[] }
700 }
702 /// Returns a reference to the value corresponding to the key.
703 ///
704 /// The key may be any borrowed form of the list's key type, but the
705 /// ordering on the borrowed form *must* match the ordering on the key type.
706 ///
707 /// # Examples
708 ///
709 /// ```
710 /// use bumpalo::Bump;
711 /// use arena_collections::{AssocListMut, SortedAssocList};
712 ///
713 /// let b = Bump::new();
714 /// let mut alist = AssocListMut::new_in(&b);
715 /// alist.insert(1, "a");
716 /// let alist = SortedAssocList::from(alist);
717 /// assert_eq!(alist.get(&1), Some(&"a"));
718 /// assert_eq!(alist.get(&2), None);
719 /// ```
720 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
721 where
722 K: Borrow<Q>,
723 Q: Ord,
724 {
725 get_sorted_entry(self.entries, key).map(|(_, v)| v)
726 }
728 /// Returns the key-value pair corresponding to the supplied key.
729 ///
730 /// The key may be any borrowed form of the list's key type, but the
731 /// ordering on the borrowed form *must* match the ordering on the key type.
732 ///
733 /// # Examples
734 ///
735 /// ```
736 /// use bumpalo::Bump;
737 /// use arena_collections::{AssocListMut, SortedAssocList};
738 ///
739 /// let b = Bump::new();
740 /// let mut alist = AssocListMut::new_in(&b);
741 /// alist.insert(1, "a");
742 /// let alist = SortedAssocList::from(alist);
743 /// assert_eq!(alist.get_key_value(&1), Some((&1, &"a")));
744 /// assert_eq!(alist.get_key_value(&2), None);
745 /// ```
746 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
747 where
748 K: Borrow<Q>,
749 Q: Ord,
750 {
751 get_sorted_entry(self.entries, key).map(|(k, v)| (k, v))
752 }
754 /// Returns `true` if the list contains a value for the specified key.
755 ///
756 /// The key may be any borrowed form of the list's key type, but the
757 /// ordering on the borrowed form *must* match the ordering on the key type.
758 ///
759 /// # Examples
760 ///
761 /// ```
762 /// use bumpalo::Bump;
763 /// use arena_collections::{AssocListMut, SortedAssocList};
764 ///
765 /// let b = Bump::new();
766 /// let mut alist = AssocListMut::new_in(&b);
767 /// alist.insert(1, "a");
768 /// let alist = SortedAssocList::from(alist);
769 /// assert_eq!(alist.contains_key(&1), true);
770 /// assert_eq!(alist.contains_key(&2), false);
771 /// ```
772 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
773 where
774 K: Borrow<Q>,
775 Q: Ord,
776 {
777 get_sorted_entry(self.entries, key).is_some()
778 }
780 /// Gets an iterator over the entries of the association list, sorted by
781 /// key.
782 ///
783 /// # Examples
784 ///
785 /// ```
786 /// use bumpalo::Bump;
787 /// use arena_collections::{AssocListMut, SortedAssocList};
788 ///
789 /// let b = Bump::new();
790 /// let mut alist = AssocListMut::new_in(&b);
791 ///
792 /// alist.insert(1, "a");
793 /// alist.insert(2, "b");
794 ///
795 /// let alist = SortedAssocList::from(alist);
796 ///
797 /// for (key, value) in alist.iter() {
798 /// println!("{}: {}", key, value);
799 /// }
800 ///
801 /// let (first_key, first_value) = alist.iter().next().unwrap();
802 /// assert_eq!((*first_key, *first_value), (1, "a"));
803 /// ```
804 pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
805 self.entries.iter().map(|(k, v)| (k, v))
806 }
808 /// Gets an iterator over the keys of the association list, in sorted order.
809 ///
810 /// # Examples
811 ///
812 /// ```
813 /// use bumpalo::Bump;
814 /// use arena_collections::{AssocListMut, SortedAssocList};
815 ///
816 /// let b = Bump::new();
817 /// let mut alist = AssocListMut::new_in(&b);
818 ///
819 /// alist.insert(1, "a");
820 /// alist.insert(2, "b");
821 ///
822 /// let alist = SortedAssocList::from(alist);
823 /// let keys: Vec<_> = alist.keys().copied().collect();
824 /// assert_eq!(keys, [1, 2]);
825 /// ```
826 pub fn keys(&self) -> impl Iterator<Item = &K> {
827 self.entries.iter().map(|(k, _)| k)
828 }
830 /// Gets an iterator over the values of the association list, in order by
831 /// key.
832 ///
833 /// # Examples
834 ///
835 /// ```
836 /// use bumpalo::Bump;
837 /// use arena_collections::{AssocListMut, SortedAssocList};
838 ///
839 /// let b = Bump::new();
840 /// let mut alist = AssocListMut::new_in(&b);
841 ///
842 /// alist.insert(1, "hello");
843 /// alist.insert(2, "goodbye");
844 ///
845 /// let alist = SortedAssocList::from(alist);
846 /// let values: Vec<&str> = alist.values().copied().collect();
847 /// assert_eq!(values, ["hello", "goodbye"]);
848 /// ```
849 pub fn values(&self) -> impl Iterator<Item = &V> {
850 self.entries.iter().map(|(_, v)| v)
851 }
853 /// Returns the number of entries in the list.
854 ///
855 /// # Examples
856 ///
857 /// ```
858 /// use bumpalo::Bump;
859 /// use arena_collections::{AssocListMut, SortedAssocList};
860 ///
861 /// let b = Bump::new();
862 /// let mut alist = AssocListMut::new_in(&b);
863 /// alist.insert(1, "a");
864 /// alist.insert(1, "b");
865 /// let alist = SortedAssocList::from(alist);
866 /// assert_eq!(alist.len(), 1);
867 /// ```
868 pub fn len(&self) -> usize {
869 self.entries.len()
870 }
872 /// Returns `true` if the list contains no entries.
873 ///
874 /// # Examples
875 ///
876 /// ```
877 /// use bumpalo::Bump;
878 /// use arena_collections::{AssocListMut, SortedAssocList};
879 ///
880 /// let b = Bump::new();
881 /// let mut alist = AssocListMut::new_in(&b);
882 /// let alist = SortedAssocList::from(alist);
883 /// assert!(alist.is_empty());
884 /// ```
885 pub fn is_empty(&self) -> bool {
886 self.entries.is_empty()
887 }
889 /// Make a new `SortedAssocList` containing the given key-value pairs.
890 ///
891 /// Provided for the sake of creating empty const lists. Passing non-empty
892 /// slices is not recommended.
893 ///
894 /// The values in the slice must be in ascending sorted order (by `K`'s
895 /// implementation of `Ord`). There must be no duplicate keys in the slice.
896 ///
897 /// # Examples
898 ///
899 /// ```
900 /// use bumpalo::Bump;
901 /// use arena_collections::{AssocListMut, SortedAssocList};
902 ///
903 /// let b = Bump::new();
904 /// let mut alist = AssocListMut::new_in(&b);
905 ///
906 /// const EMPTY_ALIST: SortedAssocList<'_, usize> = SortedAssocList::from_slice(&[]);
907 /// assert!(EMPTY_ALIST.is_empty());
908 /// ```
909 pub const fn from_slice(entries: &'a [(K, V)]) -> Self {
910 Self { entries }
911 }
912 }
914 impl<K, V> TrivialDrop for SortedAssocList<'_, K, V> {}
915 impl<K, V> Copy for SortedAssocList<'_, K, V> {}
916 impl<K, V> Clone for SortedAssocList<'_, K, V> {
917 fn clone(&self) -> Self {
918 *self
919 }
920 }
922 impl<K, V> Default for SortedAssocList<'_, K, V> {
923 fn default() -> Self {
924 Self::from_slice(&[])
925 }
926 }
928 impl<K: Debug, V: Debug> Debug for SortedAssocList<'_, K, V> {
929 fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
930 fmt.debug_map().entries(self.iter()).finish()
931 }
932 }
934 impl<'a, K: Ord, V> From<AssocListMut<'a, K, V>> for SortedAssocList<'a, K, V> {
935 #[inline]
936 fn from(mut alist: AssocListMut<'a, K, V>) -> Self {
937 let entries_mut = alist.entries.as_mut_slice();
938 // Reverse the slice so the most recently inserted pairs appear first.
939 entries_mut.reverse();
940 // Keep recently-inserted pairs first with a stable sort. Allocates
941 // temporary storage half the size of the slice using the global
942 // allocator if the slice is larger than some threshold (20 elements at
943 // time of writing).
944 entries_mut.sort_by(|(k1, _), (k2, _)| k1.cmp(k2));
945 // Remove all but the most recently inserted pair for each key.
946 alist.entries.dedup_by(|(k1, _), (k2, _)| k1 == k2);
947 SortedAssocList {
948 entries: alist.entries.into_bump_slice(),
949 }
950 }
951 }
953 impl<K: ToOcamlRep + Ord, V: ToOcamlRep> ToOcamlRep for SortedAssocList<'_, K, V> {
954 fn to_ocamlrep<'a, A: ocamlrep::Allocator>(
955 &'a self,
956 alloc: &'a A,
957 ) -> ocamlrep::OpaqueValue<'a> {
958 let len = self.len();
959 let mut iter = self.iter();
960 let (value, _) = ocamlrep::sorted_iter_to_ocaml_map(&mut iter, alloc, len);
961 value
962 }
963 }
965 impl<'a, K, V> FromOcamlRepIn<'a> for SortedAssocList<'a, K, V>
966 where
967 K: FromOcamlRepIn<'a> + Ord,
968 V: FromOcamlRepIn<'a>,
969 {
970 fn from_ocamlrep_in(
971 value: ocamlrep::Value<'_>,
972 alloc: &'a bumpalo::Bump,
973 ) -> Result<Self, ocamlrep::FromError> {
974 let mut entries = bumpalo::collections::Vec::new_in(alloc);
975 ocamlrep::vec_from_ocaml_map_in(value, &mut entries, alloc)?;
976 let entries = entries.into_bump_slice();
977 Ok(Self { entries })
978 }
979 }