frodo_ring/
lib.rs

1//! Предоставляет реализацию очереди FIFO на кольцевом буфере, не использующем аллокации.
2
3use core::mem::MaybeUninit;
4
5/// Кольцевая очередь с порядком FIFO и не использующая аллокации.
6///
7/// У данной кольцевой очереди следующие ключевые особенности:
8///
9/// - два API: привычный (`get`/`len`/`iter`/`remove` с небольшим оверхедом `O(n)` на возможный поиск) и местный (`at`/`used`/`remove_at`)
10/// - элементы могут быть изъяты из середины очереди без перемещения объектов в памяти, пока не достигнута максимальная ёмкость очереди
11/// - смысл очереди - иметь возможность найти элемент с нужными предикатами, отсортированный в порядке очереди, в `no_std`-окружении.
12pub struct FrodoRing<T, const N: usize> {
13    /// Используется `MaybeUninit`, чтобы избежать инициализации и `Option`.
14    buffer: [MaybeUninit<T>; N],
15    /// При использовании отдельного массива `occupied` вместо `Option` мы можем рассчитывать на меньшую раскладку памяти.
16    occupied: [bool; N],
17    /// Указатель на начало очереди.
18    head: usize,
19    /// Используемая ёмкость очереди.
20    ///
21    /// В очереди всегда будут элементы `self.get(0)` и `self.get(self.used() - 1)`, если cap > 0.
22    cap: usize,
23}
24
25impl<T: std::fmt::Debug, const N: usize> std::fmt::Debug for FrodoRing<T, N> {
26    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
27        writeln!(
28            f,
29            "Ring: occupied = {}, head = {}, capacity = {}",
30            self.occupied.iter().filter(|v| **v).count(),
31            self.head,
32            self.cap
33        )?;
34        writeln!(f, "Elements: [")?;
35        for i in 0..N {
36            if self.occupied[i] {
37                writeln!(f, "\t{:?},", unsafe { self.buffer[i].assume_init_ref() })?;
38            } else {
39                writeln!(f, "\tNone,")?;
40            }
41        }
42        writeln!(f, "]")?;
43
44        Ok(())
45    }
46}
47
48impl<T, const N: usize> Default for FrodoRing<T, N> {
49    fn default() -> Self {
50        Self {
51            buffer: unsafe { MaybeUninit::uninit().assume_init() },
52            occupied: [false; N],
53            head: 0,
54            cap: 0,
55        }
56    }
57}
58
59impl<T, const N: usize> FrodoRing<T, N> {
60    /// Возвращает позицию N-ного элемента в кольце.
61    fn real_pos(&self, naive_pos: usize) -> usize {
62        (self.head + naive_pos) % N
63    }
64
65    /// Можно также передавать позицию с конца; например, `1` - это последний элемент.
66    fn neg_pos(&self, naive_pos: usize) -> usize {
67        (self.head + N - naive_pos) % N
68    }
69
70    /// Создаёт новую кольцевую очередь.
71    pub fn new() -> Self {
72        Self::default()
73    }
74
75    /// Возвращает использованное число ячеек кольцевой очереди.
76    pub fn used(&self) -> usize {
77        self.cap
78    }
79
80    /// Возвращает число элементов, находящихся в очереди.
81    pub fn len(&self) -> usize {
82        self.occupied.iter().filter(|v| **v).count()
83    }
84
85    /// Сообщает, есть ли в очереди элементы.
86    pub fn is_empty(&self) -> bool {
87        self.cap == 0
88    }
89
90    /// Получает элемент по ячейке (наивной позиции).
91    ///
92    /// Примеры:
93    ///
94    /// - `ring.at(0)` - получить первый элемент в очереди
95    /// - `ring.at(1)` - получить содержимое ячейки следом за первым элементом (ячейка может быть пустой)
96    /// - `ring.at(ring.used() - 1)` - получить последний элемент в очереди
97    /// - `ring.at(-1)` - также получить последний элемент в очереди
98    pub fn at(&self, naive_pos: isize) -> Option<&T> {
99        if self.cap == 0 || naive_pos >= self.cap as isize || naive_pos < -(self.cap as isize) {
100            return None;
101        }
102
103        let real_pos = if naive_pos >= 0 {
104            self.real_pos(naive_pos as usize)
105        } else {
106            self.neg_pos((-naive_pos) as usize)
107        };
108
109        if self.occupied[real_pos] {
110            Some(unsafe { self.buffer[real_pos].assume_init_ref() })
111        } else {
112            None
113        }
114    }
115
116    /// Получает элемент по очереди.
117    ///
118    /// Примеры:
119    ///
120    /// - `ring.get(0)` - получить первый элемент в очереди
121    /// - `ring.get(1)` - получить второй элемент в очереди
122    /// - `ring.get(ring.len() - 1)` - получить последний элемент в очереди
123    pub fn get(&self, pos: usize) -> Option<&T> {
124        if pos >= self.cap || self.cap == 0 {
125            return None;
126        }
127
128        let mut cntr = 0usize;
129        let mut real_pos = self.head;
130        let max_cntr = self.len();
131
132        while cntr < max_cntr {
133            if self.occupied[real_pos] {
134                if cntr == pos {
135                    return Some(unsafe { self.buffer[real_pos].assume_init_ref() });
136                } else {
137                    cntr += 1;
138                }
139            }
140            real_pos = (real_pos + 1) % N;
141        }
142
143        None
144    }
145
146    /// Создаёт итератор по очереди.
147    pub fn iter(&self) -> FrodoRingIterator<'_, T, N> {
148        FrodoRingIterator {
149            ring: self,
150            naive_pos: 0,
151        }
152    }
153
154    /// Получает наивную позицию (ячейку) элемента, отвечающего условию.
155    ///
156    /// Чтобы получить сам элемент, используйте `ring.at(naive_pos)`.
157    pub fn position<F: Fn(&T) -> bool>(&self, f: F) -> Option<isize> {
158        let mut real_pos = self.head;
159        let last_pos = self.neg_pos(1);
160
161        while real_pos <= last_pos {
162            if self.occupied[real_pos] && f(unsafe { self.buffer[real_pos].assume_init_ref() }) {
163                return Some(real_pos as isize);
164            }
165            real_pos = (real_pos + 1) % N;
166        }
167
168        None
169    }
170
171    /// Кладёт элемент в очередь.
172    ///
173    /// В случае, если число использованных очередью ячеек равно N, но при этом хотя бы одна из них не занята,
174    /// очередь проводит операцию сжатия (`O(n)`) с перемещением элементов в памяти.
175    pub fn push(&mut self, item: T) -> Result<(), T> {
176        let real_pos = if self.cap == N {
177            if self.occupied.iter().all(|o| *o) {
178                return Err(item);
179            } else if let Some(tail) = self.compact() {
180                tail
181            } else {
182                return Err(item);
183            }
184        } else {
185            self.real_pos(self.cap)
186        };
187
188        self.buffer[real_pos].write(item);
189        self.occupied[real_pos] = true;
190        self.cap += 1;
191        Ok(())
192    }
193
194    /// Отдаёт первый элемент, изымая его из очереди.
195    pub fn pick(&mut self) -> Option<T> {
196        self.remove_at(0)
197    }
198
199    /// Удаляет содержимое ячейки, находящейся по наивной позиции, и возвращает его.
200    pub fn remove_at(&mut self, naive_pos: isize) -> Option<T> {
201        if self.cap == 0 || naive_pos >= self.cap as isize || naive_pos < -(self.cap as isize) {
202            return None;
203        }
204
205        let real_pos = if naive_pos >= 0 {
206            self.real_pos(naive_pos as usize)
207        } else {
208            self.neg_pos((-naive_pos) as usize)
209        };
210
211        if self.occupied[real_pos] {
212            self.occupied[real_pos] = false;
213
214            if real_pos == self.head {
215                loop {
216                    self.head = (self.head + 1) % N;
217                    self.cap -= 1;
218                    if self.occupied[self.head] || self.cap == 0 {
219                        break;
220                    }
221                }
222            } else if real_pos == self.neg_pos(1) {
223                loop {
224                    if self.occupied[self.real_pos(self.cap - 1)] || self.cap == 1 {
225                        break;
226                    }
227                    self.cap -= 1;
228                }
229            }
230
231            Some(unsafe { self.buffer[real_pos].assume_init_read() })
232        } else {
233            None
234        }
235    }
236
237    /// Удаляет элемент из очереди.
238    pub fn remove(&mut self, pos: usize) -> Option<T> {
239        if pos >= self.cap || self.cap == 0 {
240            return None;
241        }
242
243        let mut cntr = 0usize;
244        let mut real_pos = self.head;
245        let max_cntr = self.len();
246
247        while cntr < max_cntr {
248            if self.occupied[real_pos] {
249                if cntr == pos {
250                    self.occupied[real_pos] = false;
251
252                    if real_pos == self.head {
253                        loop {
254                            self.head = (self.head + 1) % N;
255                            self.cap -= 1;
256                            if self.occupied[self.head] || self.cap == 0 {
257                                break;
258                            }
259                        }
260                    } else if real_pos == self.neg_pos(1) {
261                        loop {
262                            if self.occupied[self.real_pos(self.cap - 1)] || self.cap == 1 {
263                                break;
264                            }
265                            self.cap -= 1;
266                        }
267                    }
268
269                    return Some(unsafe { self.buffer[real_pos].assume_init_read() });
270                } else {
271                    cntr += 1;
272                }
273            }
274            real_pos = (real_pos + 1) % N;
275        }
276
277        None
278    }
279
280    /// Ужимает место в буфере, сохраняя порядок расположения элементов.
281    ///
282    /// Возвращает последнее пустое место (real_pos), куда можно вставить элемент.
283    ///
284    /// Важно: метод опирается на то, что первый элемент никогда не будет пустым (`self.real_pos(self.head)`).
285    fn compact(&mut self) -> Option<usize> {
286        assert_eq!(self.cap, N);
287
288        let mut read_pos = 0usize;
289        let mut read_real_pos = self.real_pos(read_pos);
290
291        let mut write_pos = 0usize;
292        let mut write_real_pos = self.real_pos(write_pos);
293        let mut moved = 0usize;
294
295        let last_pos = self.cap - 1;
296
297        while read_pos <= last_pos {
298            // Пока элементы совпадают, идём и ищем пропуски
299            if read_pos == write_pos && self.occupied[read_real_pos] {
300                read_pos += 1;
301                read_real_pos = self.real_pos(read_pos);
302                write_pos = read_pos;
303                write_real_pos = read_real_pos;
304                continue;
305            }
306
307            // Если находим пустую ячейку, - перемещаем туда указатель на запись
308            if !self.occupied[read_real_pos] {
309                read_pos += 1;
310                read_real_pos = self.real_pos(read_pos);
311                moved += 1;
312            } else {
313                self.occupied[read_real_pos] = false;
314                self.occupied[write_real_pos] = true;
315                let item = unsafe { self.buffer[read_real_pos].assume_init_read() };
316                self.buffer[write_real_pos].write(item);
317
318                read_pos += 1;
319                read_real_pos = self.real_pos(read_pos);
320                write_pos += 1;
321                write_real_pos = self.real_pos(write_pos);
322            }
323        }
324
325        if moved > 0 {
326            self.cap -= moved;
327            Some(self.real_pos(self.cap))
328        } else {
329            None
330        }
331    }
332}
333
334/// Итератор по элементам очереди.
335///
336/// При итерировании пропускает пустые ячейки, выдавая исключительно присутствующие элементы.
337pub struct FrodoRingIterator<'ring, T, const N: usize> {
338    ring: &'ring FrodoRing<T, N>,
339    naive_pos: usize,
340}
341
342impl<'ring, T: std::fmt::Debug, const N: usize> Iterator for FrodoRingIterator<'ring, T, N> {
343    type Item = &'ring T;
344
345    fn next(&mut self) -> Option<Self::Item> {
346        loop {
347            if self.naive_pos == self.ring.cap {
348                return None;
349            }
350            let res = self.ring.at(self.naive_pos as isize);
351            self.naive_pos += 1;
352            if res.is_some() {
353                return res;
354            }
355        }
356    }
357}
358
359#[cfg(test)]
360mod tests {
361    use super::*;
362
363    #[test]
364    fn test_1() {
365        let mut ring = FrodoRing::<u8, 4>::new();
366
367        assert!(ring.push(0x1).is_ok());
368        assert!(ring.push(0x2).is_ok());
369        assert!(ring.push(0x3).is_ok());
370        assert!(ring.push(0x4).is_ok());
371
372        assert!(ring.push(0x5).is_err());
373    }
374
375    #[test]
376    fn test_2() {
377        let mut ring = FrodoRing::<u8, 4>::new();
378
379        assert!(ring.push(0x1).is_ok());
380        assert!(ring.push(0x2).is_ok());
381        assert!(ring.push(0x3).is_ok());
382        assert!(ring.push(0x4).is_ok());
383
384        assert_eq!(ring.at(0), Some(&0x1));
385        assert_eq!(ring.at(1), Some(&0x2));
386        assert_eq!(ring.at(2), Some(&0x3));
387        assert_eq!(ring.at(3), Some(&0x4));
388        assert_eq!(ring.at(-1), Some(&0x4));
389        assert_eq!(ring.at(-2), Some(&0x3));
390        assert_eq!(ring.at(-3), Some(&0x2));
391        assert_eq!(ring.at(-4), Some(&0x1));
392
393        assert_eq!(ring.at(4), None);
394        assert_eq!(ring.at(-5), None);
395    }
396
397    #[test]
398    fn test_3() {
399        let mut ring = FrodoRing::<u8, 4>::new();
400
401        assert!(ring.push(0x1).is_ok());
402        assert!(ring.push(0x2).is_ok());
403        assert!(ring.push(0x3).is_ok());
404        assert!(ring.push(0x4).is_ok());
405
406        assert_eq!(ring.remove_at(1), Some(0x2));
407        assert_eq!(ring.at(0), Some(&0x1));
408        assert_eq!(ring.at(1), None);
409        assert_eq!(ring.at(2), Some(&0x3));
410        assert_eq!(ring.at(3), Some(&0x4));
411    }
412
413    #[test]
414    fn test_4() {
415        let mut ring = FrodoRing::<u8, 4>::new();
416
417        assert!(ring.push(0x1).is_ok());
418        assert!(ring.push(0x2).is_ok());
419        assert!(ring.push(0x3).is_ok());
420        assert!(ring.push(0x4).is_ok());
421
422        assert_eq!(ring.remove_at(1), Some(0x2));
423        assert_eq!(ring.at(0), Some(&0x1));
424        assert_eq!(ring.at(1), None);
425        assert_eq!(ring.at(2), Some(&0x3));
426        assert_eq!(ring.at(3), Some(&0x4));
427
428        assert!(ring.push(0x5).is_ok());
429        assert_eq!(ring.at(0), Some(&0x1));
430        assert_eq!(ring.at(1), Some(&0x3));
431        assert_eq!(ring.at(2), Some(&0x4));
432        assert_eq!(ring.at(3), Some(&0x5));
433    }
434
435    #[test]
436    fn massive() {
437        let mut ring = FrodoRing::<u8, 4>::new();
438
439        assert!(ring.push(0x1).is_ok());
440        assert!(ring.push(0x2).is_ok());
441        assert!(ring.push(0x3).is_ok());
442        assert!(ring.push(0x4).is_ok());
443
444        assert_eq!(ring.remove_at(1), Some(0x2));
445        assert_eq!(ring.used(), 4);
446        assert_eq!(ring.at(0), Some(&0x1));
447        assert_eq!(ring.at(1), None);
448        assert_eq!(ring.at(2), Some(&0x3));
449        assert_eq!(ring.at(3), Some(&0x4));
450
451        assert!(ring.push(0x5).is_ok());
452        assert_eq!(ring.used(), 4);
453        assert_eq!(ring.at(0), Some(&0x1));
454        assert_eq!(ring.at(1), Some(&0x3));
455        assert_eq!(ring.at(2), Some(&0x4));
456        assert_eq!(ring.at(3), Some(&0x5));
457
458        assert_eq!(ring.remove_at(0), Some(0x1));
459        assert_eq!(ring.used(), 3);
460        assert_eq!(ring.at(0), Some(&0x3));
461        assert_eq!(ring.at(1), Some(&0x4));
462        assert_eq!(ring.at(2), Some(&0x5));
463        assert_eq!(ring.at(3), None);
464
465        assert_eq!(ring.remove_at(1), Some(0x4));
466        assert_eq!(ring.used(), 3);
467        assert_eq!(ring.at(0), Some(&0x3));
468        assert_eq!(ring.at(1), None);
469        assert_eq!(ring.at(2), Some(&0x5));
470        assert_eq!(ring.at(3), None);
471
472        assert!(ring.push(0x6).is_ok());
473        assert_eq!(ring.used(), 4);
474        assert_eq!(ring.at(0), Some(&0x3));
475        assert_eq!(ring.at(1), None);
476        assert_eq!(ring.at(2), Some(&0x5));
477        assert_eq!(ring.at(3), Some(&0x6));
478
479        assert!(ring.push(0x7).is_ok());
480        assert_eq!(ring.used(), 4);
481        assert_eq!(ring.at(0), Some(&0x3));
482        assert_eq!(ring.at(1), Some(&0x5));
483        assert_eq!(ring.at(2), Some(&0x6));
484        assert_eq!(ring.at(3), Some(&0x7));
485
486        assert!(ring.push(0x8).is_err());
487    }
488
489    #[test]
490    fn iter() {
491        let mut ring = FrodoRing::<u8, 4>::new();
492
493        assert!(ring.push(0x1).is_ok());
494        assert!(ring.push(0x2).is_ok());
495        assert!(ring.push(0x3).is_ok());
496        assert!(ring.push(0x4).is_ok());
497
498        assert_eq!(ring.remove_at(1), Some(0x2));
499        let mut it = ring.iter();
500        assert_eq!(it.next(), Some(&0x1));
501        assert_eq!(it.next(), Some(&0x3));
502        assert_eq!(it.next(), Some(&0x4));
503        assert_eq!(it.next(), None);
504
505        assert!(ring.push(0x5).is_ok());
506        let mut it = ring.iter();
507        assert_eq!(it.next(), Some(&0x1));
508        assert_eq!(it.next(), Some(&0x3));
509        assert_eq!(it.next(), Some(&0x4));
510        assert_eq!(it.next(), Some(&0x5));
511        assert_eq!(it.next(), None);
512
513        assert_eq!(ring.remove_at(0), Some(0x1));
514        let mut it = ring.iter();
515        assert_eq!(it.next(), Some(&0x3));
516        assert_eq!(it.next(), Some(&0x4));
517        assert_eq!(it.next(), Some(&0x5));
518        assert_eq!(it.next(), None);
519
520        assert_eq!(ring.remove_at(1), Some(0x4));
521        let mut it = ring.iter();
522        assert_eq!(it.next(), Some(&0x3));
523        assert_eq!(it.next(), Some(&0x5));
524        assert_eq!(ring.at(3), None);
525
526        assert!(ring.push(0x6).is_ok());
527        let mut it = ring.iter();
528        assert_eq!(it.next(), Some(&0x3));
529        assert_eq!(it.next(), Some(&0x5));
530        assert_eq!(it.next(), Some(&0x6));
531        assert_eq!(it.next(), None);
532        assert_eq!(it.next(), None);
533        assert_eq!(it.next(), None);
534
535        assert!(ring.push(0x7).is_ok());
536        let mut it = ring.iter();
537        assert_eq!(it.next(), Some(&0x3));
538        assert_eq!(it.next(), Some(&0x5));
539        assert_eq!(it.next(), Some(&0x6));
540        assert_eq!(it.next(), Some(&0x7));
541        assert_eq!(it.next(), None);
542    }
543
544    #[test]
545    fn test_5() {
546        let mut ring = FrodoRing::<u8, 4>::new();
547
548        assert!(ring.push(0x1).is_ok());
549        assert!(ring.push(0x2).is_ok());
550        assert!(ring.push(0x3).is_ok());
551        assert!(ring.push(0x4).is_ok());
552
553        assert_eq!(ring.remove_at(1), Some(0x2));
554        assert_eq!(ring.used(), 4);
555        assert_eq!(ring.at(0), Some(&0x1));
556        assert_eq!(ring.at(1), None);
557        assert_eq!(ring.at(2), Some(&0x3));
558        assert_eq!(ring.at(3), Some(&0x4));
559
560        assert_eq!(ring.remove_at(2), Some(0x3));
561        assert_eq!(ring.used(), 4);
562        assert_eq!(ring.at(0), Some(&0x1));
563        assert_eq!(ring.at(1), None);
564        assert_eq!(ring.at(2), None);
565        assert_eq!(ring.at(3), Some(&0x4));
566
567        assert_eq!(ring.remove_at(0), Some(0x1));
568        assert_eq!(ring.used(), 1);
569        assert_eq!(ring.at(0), Some(&0x4));
570        assert_eq!(ring.at(1), None);
571        assert_eq!(ring.at(2), None);
572        assert_eq!(ring.at(3), None);
573    }
574
575    #[test]
576    fn test_6() {
577        let mut ring = FrodoRing::<u8, 4>::new();
578
579        assert!(ring.push(0x1).is_ok());
580        assert!(ring.push(0x2).is_ok());
581        assert!(ring.push(0x3).is_ok());
582        assert!(ring.push(0x4).is_ok());
583
584        assert_eq!(ring.remove_at(1), Some(0x2));
585        assert_eq!(ring.used(), 4);
586        assert_eq!(ring.at(0), Some(&0x1));
587        assert_eq!(ring.at(1), None);
588        assert_eq!(ring.at(2), Some(&0x3));
589        assert_eq!(ring.at(3), Some(&0x4));
590
591        assert_eq!(ring.remove_at(2), Some(0x3));
592        assert_eq!(ring.used(), 4);
593        assert_eq!(ring.at(0), Some(&0x1));
594        assert_eq!(ring.at(1), None);
595        assert_eq!(ring.at(2), None);
596        assert_eq!(ring.at(3), Some(&0x4));
597
598        assert_eq!(ring.remove_at(3), Some(0x4));
599        assert_eq!(ring.used(), 1);
600        assert_eq!(ring.at(0), Some(&0x1));
601        assert_eq!(ring.at(1), None);
602        assert_eq!(ring.at(2), None);
603        assert_eq!(ring.at(3), None);
604    }
605
606    #[test]
607    fn test_7() {
608        let mut ring = FrodoRing::<u8, 4>::new();
609
610        assert!(ring.push(0x1).is_ok());
611        assert!(ring.push(0x2).is_ok());
612        assert!(ring.push(0x3).is_ok());
613        assert!(ring.push(0x4).is_ok());
614
615        assert_eq!(ring.pick(), Some(0x1));
616        assert_eq!(ring.pick(), Some(0x2));
617        assert_eq!(ring.pick(), Some(0x3));
618        assert_eq!(ring.pick(), Some(0x4));
619        assert_eq!(ring.pick(), None);
620    }
621
622    #[test]
623    fn test_8() {
624        let mut ring = FrodoRing::<u8, 4>::new();
625
626        assert!(ring.push(0x1).is_ok());
627        assert!(ring.push(0x2).is_ok());
628        assert!(ring.push(0x3).is_ok());
629        assert!(ring.push(0x4).is_ok());
630
631        assert_eq!(ring.at(0), Some(&0x1));
632        assert_eq!(ring.at(1), Some(&0x2));
633        assert_eq!(ring.at(2), Some(&0x3));
634        assert_eq!(ring.at(3), Some(&0x4));
635        assert_eq!(ring.get(0), Some(&0x1));
636        assert_eq!(ring.get(1), Some(&0x2));
637        assert_eq!(ring.get(2), Some(&0x3));
638        assert_eq!(ring.get(3), Some(&0x4));
639
640        assert_eq!(ring.get(4), None);
641
642        assert_eq!(ring.remove_at(1), Some(0x2));
643        assert_eq!(ring.used(), 4);
644        assert_eq!(ring.at(0), Some(&0x1));
645        assert_eq!(ring.at(1), None);
646        assert_eq!(ring.at(2), Some(&0x3));
647        assert_eq!(ring.at(3), Some(&0x4));
648        assert_eq!(ring.get(0), Some(&0x1));
649        assert_eq!(ring.get(1), Some(&0x3));
650        assert_eq!(ring.get(2), Some(&0x4));
651        assert_eq!(ring.get(3), None);
652    }
653
654    #[test]
655    fn test_9() {
656        let mut ring = FrodoRing::<u8, 4>::new();
657
658        assert!(ring.push(0x1).is_ok());
659        assert!(ring.push(0x2).is_ok());
660        assert!(ring.push(0x3).is_ok());
661        assert!(ring.push(0x4).is_ok());
662
663        assert_eq!(ring.remove(1), Some(0x2));
664        assert_eq!(ring.used(), 4);
665        assert_eq!(ring.at(0), Some(&0x1));
666        assert_eq!(ring.at(1), None);
667        assert_eq!(ring.at(2), Some(&0x3));
668        assert_eq!(ring.at(3), Some(&0x4));
669
670        assert_eq!(ring.remove(1), Some(0x3));
671        assert_eq!(ring.used(), 4);
672        assert_eq!(ring.at(0), Some(&0x1));
673        assert_eq!(ring.at(1), None);
674        assert_eq!(ring.at(2), None);
675        assert_eq!(ring.at(3), Some(&0x4));
676
677        assert_eq!(ring.remove(1), Some(0x4));
678        assert_eq!(ring.used(), 1);
679        assert_eq!(ring.at(0), Some(&0x1));
680        assert_eq!(ring.at(1), None);
681        assert_eq!(ring.at(2), None);
682        assert_eq!(ring.at(3), None);
683    }
684}
frodo_ring/lib.rs

frodo_ring/
lib.rs
