1 /* 2 * Copyright (C) 2024 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 use crossbeam_queue::ArrayQueue; 18 19 /// A thread-safe storage that allows non-blocking attempts to store and visit elements. 20 pub struct Storage<T, const N: usize> { 21 insertion_buffer: ArrayQueue<T>, 22 } 23 24 impl<T, const N: usize> Storage<T, N> { 25 /// Creates a new Storage with the specified size. new() -> Self26 pub fn new() -> Self { 27 Self { insertion_buffer: ArrayQueue::new(N) } 28 } 29 30 /// Inserts a value into the storage, returning an error if the lock cannot be acquired. insert(&self, value: T)31 pub fn insert(&self, value: T) { 32 self.insertion_buffer.force_push(value); 33 } 34 35 /// Folds over the elements in the storage in reverse order using the provided function. rfold<U, F>(&self, init: U, mut func: F) -> U where F: FnMut(U, &T) -> U,36 pub fn rfold<U, F>(&self, init: U, mut func: F) -> U 37 where 38 F: FnMut(U, &T) -> U, 39 { 40 let mut items = Vec::new(); 41 while let Some(value) = self.insertion_buffer.pop() { 42 items.push(value); 43 } 44 let mut acc = init; 45 for value in items.iter().rev() { 46 acc = func(acc, value); 47 } 48 acc 49 } 50 51 /// Returns the number of elements that have been inserted into the storage. len(&self) -> usize52 pub fn len(&self) -> usize { 53 self.insertion_buffer.len() 54 } 55 } 56 57 #[cfg(test)] 58 mod tests { 59 use super::*; 60 61 #[test] test_insert_and_retrieve()62 fn test_insert_and_retrieve() { 63 let storage = Storage::<i32, 10>::new(); 64 storage.insert(7); 65 66 let sum = storage.rfold(0, |acc, &x| acc + x); 67 assert_eq!(sum, 7, "The sum of the elements should be equal to the inserted value."); 68 } 69 70 #[test] test_rfold_functionality()71 fn test_rfold_functionality() { 72 let storage = Storage::<i32, 5>::new(); 73 storage.insert(1); 74 storage.insert(2); 75 storage.insert(3); 76 77 let sum = storage.rfold(0, |acc, &x| acc + x); 78 assert_eq!( 79 sum, 6, 80 "The sum of the elements should be equal to the sum of inserted values." 81 ); 82 } 83 84 #[test] test_insert_and_retrieve_multiple_values()85 fn test_insert_and_retrieve_multiple_values() { 86 let storage = Storage::<i32, 10>::new(); 87 storage.insert(1); 88 storage.insert(2); 89 storage.insert(5); 90 91 let first_sum = storage.rfold(0, |acc, &x| acc + x); 92 assert_eq!(first_sum, 8, "The sum of the elements should be equal to the inserted values."); 93 94 storage.insert(30); 95 storage.insert(22); 96 97 let second_sum = storage.rfold(0, |acc, &x| acc + x); 98 assert_eq!( 99 second_sum, 52, 100 "The sum of the elements should be equal to the inserted values." 101 ); 102 } 103 104 #[test] test_storage_limit()105 fn test_storage_limit() { 106 let storage = Storage::<i32, 1>::new(); 107 storage.insert(1); 108 // This value should overwrite the previously inserted value (1). 109 storage.insert(4); 110 let sum = storage.rfold(0, |acc, &x| acc + x); 111 assert_eq!(sum, 4, "The sum of the elements should be equal to the inserted values."); 112 } 113 114 #[test] test_concurrent_insertions()115 fn test_concurrent_insertions() { 116 use std::sync::Arc; 117 use std::thread; 118 119 let storage = Arc::new(Storage::<i32, 100>::new()); 120 let threads: Vec<_> = (0..10) 121 .map(|_| { 122 let storage_clone = Arc::clone(&storage); 123 thread::spawn(move || { 124 for i in 0..10 { 125 storage_clone.insert(i); 126 } 127 }) 128 }) 129 .collect(); 130 131 for thread in threads { 132 thread.join().expect("Thread should finish without panicking"); 133 } 134 135 let count = storage.rfold(0, |acc, _| acc + 1); 136 assert_eq!(count, 100, "Storage should be filled to its limit with concurrent insertions."); 137 } 138 139 #[test] test_rfold_order()140 fn test_rfold_order() { 141 let storage = Storage::<i32, 5>::new(); 142 storage.insert(1); 143 storage.insert(2); 144 storage.insert(3); 145 146 let mut result = Vec::new(); 147 storage.rfold((), |_, &x| result.push(x)); 148 149 assert_eq!( 150 result, 151 vec![3, 2, 1], 152 "Elements should be processed in reverse order of insertion" 153 ); 154 } 155 } 156