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