1// Copyright 2014 The Servo Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution.
3//
4// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. This file may not be copied, modified, or distributed
8// except according to those terms.
9
10use parking_lot::Mutex;
11use std::borrow::Cow;
12use std::mem;
13use std::ptr::NonNull;
14use std::sync::atomic::AtomicIsize;
15use std::sync::atomic::Ordering::SeqCst;
16use std::sync::OnceLock;
17
18const NB_BUCKETS: usize = 1 << 12; // 4096
19const BUCKET_MASK: u32 = (1 << 12) - 1;
20
21pub(crate) struct Set {
22 buckets: Box<[Mutex<Option<Box<Entry>>>]>,
23}
24
25pub(crate) struct Entry {
26 pub(crate) string: Box<str>,
27 pub(crate) hash: u32,
28 pub(crate) ref_count: AtomicIsize,
29 next_in_bucket: Option<Box<Entry>>,
30}
31
32// Addresses are a multiples of this,
33// and therefore have have TAG_MASK bits unset, available for tagging.
34pub(crate) const ENTRY_ALIGNMENT: usize = 4;
35
36#[test]
37fn entry_alignment_is_sufficient() {
38 assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
39}
40
41pub(crate) fn dynamic_set() -> &'static Set {
42 // NOTE: Using const initialization for buckets breaks the small-stack test.
43 // ```
44 // // buckets: [Mutex<Option<Box<Entry>>>; NB_BUCKETS],
45 // const MUTEX: Mutex<Option<Box<Entry>>> = Mutex::new(None);
46 // let buckets = Box::new([MUTEX; NB_BUCKETS]);
47 // ```
48 static DYNAMIC_SET: OnceLock<Set> = OnceLock::new();
49
50 DYNAMIC_SET.get_or_init(|| {
51 let buckets: Box<[Mutex>]> = (0..NB_BUCKETS).map(|_| Mutex::new(val:None)).collect();
52 Set { buckets }
53 })
54}
55
56impl Set {
57 pub(crate) fn insert(&self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
58 let bucket_index = (hash & BUCKET_MASK) as usize;
59 let mut linked_list = self.buckets[bucket_index].lock();
60
61 {
62 let mut ptr: Option<&mut Box<Entry>> = linked_list.as_mut();
63
64 while let Some(entry) = ptr.take() {
65 if entry.hash == hash && *entry.string == *string {
66 if entry.ref_count.fetch_add(1, SeqCst) > 0 {
67 return NonNull::from(&mut **entry);
68 }
69 // Uh-oh. The pointer's reference count was zero, which means someone may try
70 // to free it. (Naive attempts to defend against this, for example having the
71 // destructor check to see whether the reference count is indeed zero, don't
72 // work due to ABA.) Thus we need to temporarily add a duplicate string to the
73 // list.
74 entry.ref_count.fetch_sub(1, SeqCst);
75 break;
76 }
77 ptr = entry.next_in_bucket.as_mut();
78 }
79 }
80 debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
81 let string = string.into_owned();
82 let mut entry = Box::new(Entry {
83 next_in_bucket: linked_list.take(),
84 hash,
85 ref_count: AtomicIsize::new(1),
86 string: string.into_boxed_str(),
87 });
88 let ptr = NonNull::from(&mut *entry);
89 *linked_list = Some(entry);
90 ptr
91 }
92
93 pub(crate) fn remove(&self, ptr: *mut Entry) {
94 let value: &Entry = unsafe { &*ptr };
95 let bucket_index = (value.hash & BUCKET_MASK) as usize;
96
97 let mut linked_list = self.buckets[bucket_index].lock();
98 debug_assert!(value.ref_count.load(SeqCst) == 0);
99 let mut current: &mut Option<Box<Entry>> = &mut linked_list;
100
101 while let Some(entry_ptr) = current.as_mut() {
102 let entry_ptr: *mut Entry = &mut **entry_ptr;
103 if entry_ptr == ptr {
104 mem::drop(mem::replace(current, unsafe {
105 (*entry_ptr).next_in_bucket.take()
106 }));
107 break;
108 }
109 current = unsafe { &mut (*entry_ptr).next_in_bucket };
110 }
111 }
112}
113