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
10 use lazy_static::lazy_static;
11 use std::borrow::Cow;
12 use std::mem;
13 use std::ptr::NonNull;
14 use std::sync::atomic::AtomicIsize;
15 use std::sync::atomic::Ordering::SeqCst;
16 use std::sync::Mutex;
17
18 const NB_BUCKETS: usize = 1 << 12; // 4096
19 const BUCKET_MASK: u32 = (1 << 12) - 1;
20
21 pub(crate) struct Set {
22 buckets: Box<[Option<Box<Entry>>; NB_BUCKETS]>,
23 }
24
25 pub(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.
34 pub(crate) const ENTRY_ALIGNMENT: usize = 4;
35
36 #[test]
entry_alignment_is_sufficient()37 fn entry_alignment_is_sufficient() {
38 assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
39 }
40
41 lazy_static! {
42 pub(crate) static ref DYNAMIC_SET: Mutex<Set> = Mutex::new({
43 type T = Option<Box<Entry>>;
44 let _static_assert_size_eq = std::mem::transmute::<T, usize>;
45 let vec = std::mem::ManuallyDrop::new(vec![0_usize; NB_BUCKETS]);
46 Set {
47 buckets: unsafe { Box::from_raw(vec.as_ptr() as *mut [T; NB_BUCKETS]) },
48 }
49 });
50 }
51
52 impl Set {
insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry>53 pub(crate) fn insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
54 let bucket_index = (hash & BUCKET_MASK) as usize;
55 {
56 let mut ptr: Option<&mut Box<Entry>> = self.buckets[bucket_index].as_mut();
57
58 while let Some(entry) = ptr.take() {
59 if entry.hash == hash && &*entry.string == &*string {
60 if entry.ref_count.fetch_add(1, SeqCst) > 0 {
61 return NonNull::from(&mut **entry);
62 }
63 // Uh-oh. The pointer's reference count was zero, which means someone may try
64 // to free it. (Naive attempts to defend against this, for example having the
65 // destructor check to see whether the reference count is indeed zero, don't
66 // work due to ABA.) Thus we need to temporarily add a duplicate string to the
67 // list.
68 entry.ref_count.fetch_sub(1, SeqCst);
69 break;
70 }
71 ptr = entry.next_in_bucket.as_mut();
72 }
73 }
74 debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
75 let string = string.into_owned();
76 let mut entry = Box::new(Entry {
77 next_in_bucket: self.buckets[bucket_index].take(),
78 hash,
79 ref_count: AtomicIsize::new(1),
80 string: string.into_boxed_str(),
81 });
82 let ptr = NonNull::from(&mut *entry);
83 self.buckets[bucket_index] = Some(entry);
84
85 ptr
86 }
87
remove(&mut self, ptr: *mut Entry)88 pub(crate) fn remove(&mut self, ptr: *mut Entry) {
89 let bucket_index = {
90 let value: &Entry = unsafe { &*ptr };
91 debug_assert!(value.ref_count.load(SeqCst) == 0);
92 (value.hash & BUCKET_MASK) as usize
93 };
94
95 let mut current: &mut Option<Box<Entry>> = &mut self.buckets[bucket_index];
96
97 loop {
98 let entry_ptr: *mut Entry = match current.as_mut() {
99 Some(entry) => &mut **entry,
100 None => break,
101 };
102 if entry_ptr == ptr {
103 mem::drop(mem::replace(current, unsafe {
104 (*entry_ptr).next_in_bucket.take()
105 }));
106 break;
107 }
108 current = unsafe { &mut (*entry_ptr).next_in_bucket };
109 }
110 }
111 }
112