@@ -27,9 +27,11 @@ struct Slot<T> {
2727///
2828/// This queue allocates a fixed-capacity buffer on construction, which is used to store pushed
2929/// elements. The queue cannot hold more elements than the buffer allows. Attempting to push an
30- /// element into a full queue will fail. Having a buffer allocated upfront makes this queue a bit
31- /// faster than [`SegQueue`].
30+ /// element into a full queue will fail. Alternatively, [`force_push`] makes it possible for
31+ /// this queue to be used as a ring-buffer. Having a buffer allocated upfront makes this queue
32+ /// a bit faster than [`SegQueue`].
3233///
34+ /// [`force_push`]: ArrayQueue::force_push
3335/// [`SegQueue`]: super::SegQueue
3436///
3537/// # Examples
@@ -120,21 +122,10 @@ impl<T> ArrayQueue<T> {
120122 }
121123 }
122124
123- /// Attempts to push an element into the queue.
124- ///
125- /// If the queue is full, the element is returned back as an error.
126- ///
127- /// # Examples
128- ///
129- /// ```
130- /// use crossbeam_queue::ArrayQueue;
131- ///
132- /// let q = ArrayQueue::new(1);
133- ///
134- /// assert_eq!(q.push(10), Ok(()));
135- /// assert_eq!(q.push(20), Err(20));
136- /// ```
137- pub fn push ( & self , value : T ) -> Result < ( ) , T > {
125+ fn push_or_else < F > ( & self , mut value : T , f : F ) -> Result < ( ) , T >
126+ where
127+ F : Fn ( T , usize , usize , & Slot < T > ) -> Result < T , T > ,
128+ {
138129 let backoff = Backoff :: new ( ) ;
139130 let mut tail = self . tail . load ( Ordering :: Relaxed ) ;
140131
@@ -143,23 +134,23 @@ impl<T> ArrayQueue<T> {
143134 let index = tail & ( self . one_lap - 1 ) ;
144135 let lap = tail & !( self . one_lap - 1 ) ;
145136
137+ let new_tail = if index + 1 < self . cap {
138+ // Same lap, incremented index.
139+ // Set to `{ lap: lap, index: index + 1 }`.
140+ tail + 1
141+ } else {
142+ // One lap forward, index wraps around to zero.
143+ // Set to `{ lap: lap.wrapping_add(1), index: 0 }`.
144+ lap. wrapping_add ( self . one_lap )
145+ } ;
146+
146147 // Inspect the corresponding slot.
147148 debug_assert ! ( index < self . buffer. len( ) ) ;
148149 let slot = unsafe { self . buffer . get_unchecked ( index) } ;
149150 let stamp = slot. stamp . load ( Ordering :: Acquire ) ;
150151
151152 // If the tail and the stamp match, we may attempt to push.
152153 if tail == stamp {
153- let new_tail = if index + 1 < self . cap {
154- // Same lap, incremented index.
155- // Set to `{ lap: lap, index: index + 1 }`.
156- tail + 1
157- } else {
158- // One lap forward, index wraps around to zero.
159- // Set to `{ lap: lap.wrapping_add(1), index: 0 }`.
160- lap. wrapping_add ( self . one_lap )
161- } ;
162-
163154 // Try moving the tail.
164155 match self . tail . compare_exchange_weak (
165156 tail,
@@ -182,14 +173,7 @@ impl<T> ArrayQueue<T> {
182173 }
183174 } else if stamp. wrapping_add ( self . one_lap ) == tail + 1 {
184175 atomic:: fence ( Ordering :: SeqCst ) ;
185- let head = self . head . load ( Ordering :: Relaxed ) ;
186-
187- // If the head lags one lap behind the tail as well...
188- if head. wrapping_add ( self . one_lap ) == tail {
189- // ...then the queue is full.
190- return Err ( value) ;
191- }
192-
176+ value = f ( value, tail, new_tail, slot) ?;
193177 backoff. spin ( ) ;
194178 tail = self . tail . load ( Ordering :: Relaxed ) ;
195179 } else {
@@ -200,6 +184,79 @@ impl<T> ArrayQueue<T> {
200184 }
201185 }
202186
187+ /// Attempts to push an element into the queue.
188+ ///
189+ /// If the queue is full, the element is returned back as an error.
190+ ///
191+ /// # Examples
192+ ///
193+ /// ```
194+ /// use crossbeam_queue::ArrayQueue;
195+ ///
196+ /// let q = ArrayQueue::new(1);
197+ ///
198+ /// assert_eq!(q.push(10), Ok(()));
199+ /// assert_eq!(q.push(20), Err(20));
200+ /// ```
201+ pub fn push ( & self , value : T ) -> Result < ( ) , T > {
202+ self . push_or_else ( value, |v, tail, _, _| {
203+ let head = self . head . load ( Ordering :: Relaxed ) ;
204+
205+ // If the head lags one lap behind the tail as well...
206+ if head. wrapping_add ( self . one_lap ) == tail {
207+ // ...then the queue is full.
208+ Err ( v)
209+ } else {
210+ Ok ( v)
211+ }
212+ } )
213+ }
214+
215+ /// Pushes an element into the queue, replacing the oldest element if necessary.
216+ ///
217+ /// If the queue is full, the oldest element is replaced and returned,
218+ /// otherwise `None` is returned.
219+ ///
220+ /// # Examples
221+ ///
222+ /// ```
223+ /// use crossbeam_queue::ArrayQueue;
224+ ///
225+ /// let q = ArrayQueue::new(2);
226+ ///
227+ /// assert_eq!(q.force_push(10), None);
228+ /// assert_eq!(q.force_push(20), None);
229+ /// assert_eq!(q.force_push(30), Some(10));
230+ /// assert_eq!(q.pop(), Some(20));
231+ /// ```
232+ pub fn force_push ( & self , value : T ) -> Option < T > {
233+ self . push_or_else ( value, |v, tail, new_tail, slot| {
234+ let head = tail. wrapping_sub ( self . one_lap ) ;
235+ let new_head = new_tail. wrapping_sub ( self . one_lap ) ;
236+
237+ // Try moving the head.
238+ if self
239+ . head
240+ . compare_exchange_weak ( head, new_head, Ordering :: SeqCst , Ordering :: Relaxed )
241+ . is_ok ( )
242+ {
243+ // Move the tail.
244+ self . tail . store ( new_tail, Ordering :: SeqCst ) ;
245+
246+ // Swap the previous value.
247+ let old = unsafe { slot. value . get ( ) . replace ( MaybeUninit :: new ( v) ) . assume_init ( ) } ;
248+
249+ // Update the stamp.
250+ slot. stamp . store ( tail + 1 , Ordering :: Release ) ;
251+
252+ Err ( old)
253+ } else {
254+ Ok ( v)
255+ }
256+ } )
257+ . err ( )
258+ }
259+
203260 /// Attempts to pop an element from the queue.
204261 ///
205262 /// If the queue is empty, `None` is returned.
0 commit comments