1use std::cmp::Ordering;
2use std::ptr::NonNull;
3
4#[derive(Debug)]
5struct FixedSizeListNode<T> {
6 prev: usize,
7 next: usize,
8 data: T,
9}
10
11#[derive(Debug)]
12pub(crate) struct FixedSizeList<T> {
13 capacity: usize,
14 nodes: Vec<Option<FixedSizeListNode<T>>>,
15 // An un-ordered set of indices that are not in use in `nodes`.
16 // All `None` entries in `nodes` _must_ be listed in `free`.
17 // A `Vec<usize>` was choosen in order to have O(1) complexity
18 // for pop and avoid having to go through `nodes` in order to
19 // to find a free place.
20 free: Vec<usize>,
21 front: usize,
22 back: usize,
23}
24
25impl<T> FixedSizeList<T> {
26 #[inline]
27 pub(crate) fn new(capacity: usize) -> Self {
28 Self {
29 capacity,
30 nodes: Vec::new(),
31 free: Vec::new(),
32 front: usize::MAX,
33 back: usize::MAX,
34 }
35 }
36
37 #[inline]
38 pub(crate) fn with_memory(capacity: usize, mut reserve: usize) -> Self {
39 if reserve > capacity {
40 reserve = capacity;
41 }
42 Self {
43 capacity,
44 nodes: Vec::with_capacity(reserve),
45 free: Vec::new(),
46 front: usize::MAX,
47 back: usize::MAX,
48 }
49 }
50
51 #[inline]
52 pub(crate) fn capacity(&self) -> usize {
53 self.capacity
54 }
55
56 #[inline]
57 pub(crate) fn len(&self) -> usize {
58 self.nodes.len() - self.free.len()
59 }
60
61 #[inline]
62 pub(crate) fn is_empty(&self) -> bool {
63 self.len() == 0
64 }
65
66 #[inline]
67 pub(crate) fn is_full(&self) -> bool {
68 self.len() == self.capacity()
69 }
70
71 pub(crate) fn clear(&mut self) {
72 self.nodes.clear();
73 self.free.clear();
74 self.front = usize::MAX;
75 self.back = usize::MAX;
76 }
77
78 fn next(&mut self) -> Option<usize> {
79 if self.is_full() {
80 None
81 } else if self.free.is_empty() {
82 let len = self.len();
83 self.nodes.push(None);
84 Some(len)
85 } else {
86 self.free.pop()
87 }
88 }
89
90 #[inline]
91 fn node_ref(&self, idx: usize) -> Option<&FixedSizeListNode<T>> {
92 self.nodes.get(idx).and_then(|node| node.as_ref())
93 }
94
95 #[inline]
96 pub(crate) fn get(&self, idx: usize) -> Option<&T> {
97 self.node_ref(idx).map(|node| &node.data)
98 }
99
100 #[inline]
101 fn node_mut(&mut self, idx: usize) -> Option<&mut FixedSizeListNode<T>> {
102 self.nodes.get_mut(idx).and_then(|node| node.as_mut())
103 }
104
105 #[inline]
106 pub(crate) fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
107 self.node_mut(idx).map(|node| &mut node.data)
108 }
109
110 #[inline]
111 pub(crate) fn front(&self) -> Option<&T> {
112 self.node_ref(self.front).map(|node| &node.data)
113 }
114
115 #[inline]
116 pub(crate) fn front_mut(&mut self) -> Option<&mut T> {
117 self.node_mut(self.front).map(|node| &mut node.data)
118 }
119
120 #[inline]
121 pub(crate) fn back_idx(&self) -> usize {
122 self.back
123 }
124
125 #[inline]
126 pub(crate) fn back(&self) -> Option<&T> {
127 self.node_ref(self.back).map(|node| &node.data)
128 }
129
130 #[inline]
131 pub(crate) fn back_mut(&mut self) -> Option<&mut T> {
132 self.node_mut(self.back).map(|node| &mut node.data)
133 }
134
135 pub(crate) fn push_front(&mut self, data: T) -> Option<(usize, &mut T)> {
136 let idx = self.next()?;
137 if let Some(front) = self.node_mut(self.front) {
138 front.prev = idx;
139 }
140 if self.node_ref(self.back).is_none() {
141 self.back = idx;
142 }
143 let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode {
144 prev: usize::MAX,
145 next: self.front,
146 data,
147 });
148 self.front = idx;
149 Some((idx, &mut node.data))
150 }
151
152 #[cfg(test)]
153 fn push_back(&mut self, data: T) -> Option<(usize, &mut T)> {
154 let idx = self.next()?;
155 if let Some(back) = self.node_mut(self.back) {
156 back.next = idx;
157 }
158 if self.node_ref(self.front).is_none() {
159 self.front = idx;
160 }
161 let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode {
162 prev: self.back,
163 next: usize::MAX,
164 data,
165 });
166 self.back = idx;
167 Some((idx, &mut node.data))
168 }
169
170 #[inline]
171 pub(crate) fn pop_front(&mut self) -> Option<T> {
172 self.remove(self.front)
173 }
174
175 #[inline]
176 pub(crate) fn pop_back(&mut self) -> Option<T> {
177 self.remove(self.back)
178 }
179
180 pub(crate) fn remove(&mut self, idx: usize) -> Option<T> {
181 let node = self.nodes.get_mut(idx)?.take()?;
182 if let Some(prev) = self.node_mut(node.prev) {
183 prev.next = node.next;
184 } else {
185 self.front = node.next;
186 }
187 if let Some(next) = self.node_mut(node.next) {
188 next.prev = node.prev;
189 } else {
190 self.back = node.prev;
191 }
192 self.free.push(idx);
193 Some(node.data)
194 }
195
196 #[inline]
197 pub(crate) fn iter(&self) -> FixedSizeListIter<'_, T> {
198 FixedSizeListIter {
199 list: self,
200 front: self.front,
201 back: self.back,
202 len: self.len(),
203 }
204 }
205
206 #[inline]
207 pub(crate) fn iter_mut(&mut self) -> FixedSizeListIterMut<'_, T> {
208 let front = self.front;
209 let back = self.back;
210 let len = self.len();
211 FixedSizeListIterMut::new(&mut self.nodes, front, back, len)
212 }
213
214 fn reorder(&mut self) {
215 if self.is_empty() {
216 return;
217 }
218
219 let len = self.len();
220 let mut current = 0;
221 while current < len {
222 let front = self.front;
223 let front_data = self.pop_front().unwrap();
224 if front != current {
225 debug_assert!(current < front, "{} < {}", current, front);
226 // We need to free self.nodes[current] if its occupied
227 if let Some(current_node) = self.nodes[current].take() {
228 if let Some(node) = self.node_mut(current_node.prev) {
229 node.next = front;
230 } else {
231 self.front = front;
232 }
233 if let Some(node) = self.node_mut(current_node.next) {
234 node.prev = front;
235 } else {
236 self.back = front;
237 }
238 self.nodes[front] = Some(current_node);
239 }
240 }
241 // Assign new front node
242 self.nodes[current] = Some(FixedSizeListNode {
243 prev: current.wrapping_sub(1),
244 next: current + 1,
245 data: front_data,
246 });
247 current += 1;
248 }
249 self.front = 0;
250 self.nodes[len - 1].as_mut().unwrap().next = usize::MAX;
251 self.back = len - 1;
252 self.free.clear();
253 self.free.extend((len..self.nodes.len()).rev());
254 }
255
256 pub(crate) fn resize(&mut self, capacity: usize) {
257 let len = self.len();
258 let cap = self.capacity();
259 match capacity.cmp(&cap) {
260 Ordering::Less => {
261 self.reorder();
262 self.nodes.truncate(capacity);
263 self.free.clear();
264 self.free.extend(len..self.nodes.len());
265 self.capacity = capacity;
266 }
267 Ordering::Equal => {}
268 Ordering::Greater => {
269 self.capacity = capacity;
270 }
271 };
272 debug_assert_eq!(self.len(), len);
273 debug_assert_eq!(self.capacity(), capacity);
274 }
275
276 pub(crate) fn retain<F>(&mut self, mut f: F)
277 where
278 F: FnMut(&T) -> bool,
279 {
280 let mut front = self.front;
281 while front != usize::MAX {
282 let node = self.node_ref(front).unwrap();
283 let next = node.next;
284 if !f(&node.data) {
285 self.remove(front);
286 }
287 front = next;
288 }
289 }
290
291 pub(crate) fn retain_mut<F>(&mut self, mut f: F)
292 where
293 F: FnMut(&mut T) -> bool,
294 {
295 let mut front = self.front;
296 while front != usize::MAX {
297 let node = self.node_mut(front).unwrap();
298 let next = node.next;
299 if !f(&mut node.data) {
300 self.remove(front);
301 }
302 front = next;
303 }
304 }
305
306 #[inline]
307 pub(crate) fn move_front(&mut self, idx: usize) -> Option<&mut T> {
308 // TODO: try to optimize this funtion as it is a fairly hot path
309 let node = self.nodes.get_mut(idx)?.take()?;
310 if let Some(prev) = self.node_mut(node.prev) {
311 prev.next = node.next;
312 } else {
313 self.front = node.next;
314 }
315 if let Some(next) = self.node_mut(node.next) {
316 next.prev = node.prev;
317 } else {
318 self.back = node.prev;
319 }
320
321 if let Some(front) = self.node_mut(self.front) {
322 front.prev = idx;
323 }
324 if self.node_ref(self.back).is_none() {
325 self.back = idx;
326 }
327
328 let node = self.nodes.get_mut(idx).unwrap().insert(FixedSizeListNode {
329 prev: usize::MAX,
330 next: self.front,
331 data: node.data,
332 });
333 self.front = idx;
334 Some(&mut node.data)
335 }
336}
337
338#[derive(Debug)]
339pub(crate) struct FixedSizeListIter<'a, T> {
340 list: &'a FixedSizeList<T>,
341 front: usize,
342 back: usize,
343 len: usize,
344}
345
346impl<'a, T> Clone for FixedSizeListIter<'a, T> {
347 fn clone(&self) -> Self {
348 Self {
349 list: self.list,
350 front: self.front,
351 back: self.back,
352 len: self.len,
353 }
354 }
355}
356
357impl<'a, T> Iterator for FixedSizeListIter<'a, T> {
358 type Item = (usize, &'a T);
359
360 fn next(&mut self) -> Option<Self::Item> {
361 if self.len > 0 {
362 let front: usize = self.front;
363 let node: &FixedSizeListNode = self.list.node_ref(idx:front).unwrap();
364 self.front = node.next;
365 self.len -= 1;
366 Some((front, &node.data))
367 } else {
368 None
369 }
370 }
371
372 fn size_hint(&self) -> (usize, Option<usize>) {
373 (self.len, Some(self.len))
374 }
375}
376
377impl<'a, T> DoubleEndedIterator for FixedSizeListIter<'a, T> {
378 fn next_back(&mut self) -> Option<Self::Item> {
379 if self.len > 0 {
380 let back: usize = self.back;
381 let node: &FixedSizeListNode = self.list.node_ref(idx:back).unwrap();
382 self.back = node.prev;
383 self.len -= 1;
384 Some((back, &node.data))
385 } else {
386 None
387 }
388 }
389}
390
391impl<'a, T> ExactSizeIterator for FixedSizeListIter<'a, T> {
392 fn len(&self) -> usize {
393 self.size_hint().0
394 }
395}
396
397pub(crate) struct FixedSizeListIterMut<'a, T> {
398 ptr: NonNull<Option<FixedSizeListNode<T>>>,
399 front: usize,
400 back: usize,
401 len: usize,
402 _marker: std::marker::PhantomData<&'a mut T>,
403}
404
405impl<'a, T> FixedSizeListIterMut<'a, T> {
406 #[allow(unsafe_code)]
407 fn new(
408 slice: &'a mut [Option<FixedSizeListNode<T>>],
409 front: usize,
410 back: usize,
411 len: usize,
412 ) -> Self {
413 let ptr: *mut Option> = slice.as_mut_ptr();
414 Self {
415 ptr: unsafe { NonNull::new_unchecked(ptr) },
416 front,
417 back,
418 len,
419 _marker: std::marker::PhantomData,
420 }
421 }
422}
423
424impl<'a, T> Iterator for FixedSizeListIterMut<'a, T> {
425 type Item = (usize, &'a mut T);
426
427 #[allow(unsafe_code)]
428 fn next(&mut self) -> Option<Self::Item> {
429 if self.len > 0 {
430 let front = self.front;
431
432 // Safety:
433 // * `self.ptr` is a valid non null pointer since it can only be created through `FixedSizeListIterMut::new`.
434 // * `front` is guaranteed to be a valid index within the slice pointed to by `self.ptr`.
435 // Notes: implementation is inspired by the iterator over mutable slice from the standard rust library
436 // * https://doc.rust-lang.org/src/core/slice/iter.rs.html
437 // * https://doc.rust-lang.org/src/core/slice/iter/macros.rs.html
438 let node_ref = unsafe {
439 let ptr = NonNull::new_unchecked(self.ptr.as_ptr().add(front)).as_ptr();
440 &mut *ptr
441 };
442
443 let node = node_ref.as_mut().unwrap();
444 self.front = node.next;
445 self.len -= 1;
446 Some((front, &mut node.data))
447 } else {
448 None
449 }
450 }
451
452 fn size_hint(&self) -> (usize, Option<usize>) {
453 (self.len, Some(self.len))
454 }
455}
456
457impl<'a, T> DoubleEndedIterator for FixedSizeListIterMut<'a, T> {
458 #[allow(unsafe_code)]
459 fn next_back(&mut self) -> Option<Self::Item> {
460 if self.len > 0 {
461 let back = self.back;
462
463 // Safety:
464 // * `self.ptr` is a valid non null pointer since it can only be created through `FixedSizeListIterMut::new`.
465 // * `back` is guaranteed to be a valid index within the slice pointed to by `self.ptr`.
466 // Notes: implementation is inspired by the iterator over mutable slice from the standard rust library
467 // * https://doc.rust-lang.org/src/core/slice/iter.rs.html
468 // * https://doc.rust-lang.org/src/core/slice/iter/macros.rs.html
469 let node_ref = unsafe {
470 let ptr = NonNull::new_unchecked(self.ptr.as_ptr().add(back)).as_ptr();
471 &mut *ptr
472 };
473
474 let node = node_ref.as_mut().unwrap();
475 self.back = node.prev;
476 self.len -= 1;
477 Some((back, &mut node.data))
478 } else {
479 None
480 }
481 }
482}
483
484impl<'a, T> ExactSizeIterator for FixedSizeListIterMut<'a, T> {
485 fn len(&self) -> usize {
486 self.size_hint().0
487 }
488}
489
490#[cfg(test)]
491#[allow(clippy::bool_assert_comparison)]
492mod tests {
493 use super::*;
494
495 #[test]
496 fn test_fixed_size_list() {
497 let mut list = FixedSizeList::new(4);
498
499 assert!(list.is_empty());
500 assert_eq!(list.len(), 0);
501
502 assert_eq!(list.front(), None);
503 assert_eq!(list.front_mut(), None);
504
505 assert_eq!(list.back(), None);
506 assert_eq!(list.back_mut(), None);
507
508 assert_eq!(list.iter().count(), 0);
509 assert_eq!(list.iter().rev().count(), 0);
510
511 assert_eq!(list.push_front(7), Some((0, &mut 7)));
512
513 assert!(!list.is_empty());
514 assert_eq!(list.len(), 1);
515
516 assert_eq!(list.front(), Some(&7));
517 assert_eq!(list.front_mut(), Some(&mut 7));
518
519 assert_eq!(list.back(), Some(&7));
520 assert_eq!(list.back_mut(), Some(&mut 7));
521
522 assert_eq!(list.iter().collect::<Vec<_>>(), vec![(0, &7)]);
523 assert_eq!(list.iter().rev().collect::<Vec<_>>(), vec![(0, &7)]);
524
525 assert_eq!(list.push_front(5), Some((1, &mut 5)));
526
527 assert!(!list.is_empty());
528 assert_eq!(list.len(), 2);
529
530 assert_eq!(list.front(), Some(&5));
531 assert_eq!(list.front_mut(), Some(&mut 5));
532
533 assert_eq!(list.back(), Some(&7));
534 assert_eq!(list.back_mut(), Some(&mut 7));
535
536 assert_eq!(list.iter().collect::<Vec<_>>(), vec![(1, &5), (0, &7)]);
537 assert_eq!(
538 list.iter().rev().collect::<Vec<_>>(),
539 vec![(0, &7), (1, &5)]
540 );
541
542 assert_eq!(list.push_front(3), Some((2, &mut 3)));
543
544 assert!(!list.is_empty());
545 assert_eq!(list.len(), 3);
546
547 assert_eq!(list.front(), Some(&3));
548 assert_eq!(list.front_mut(), Some(&mut 3));
549
550 assert_eq!(list.back(), Some(&7));
551 assert_eq!(list.back_mut(), Some(&mut 7));
552
553 assert_eq!(
554 list.iter().collect::<Vec<_>>(),
555 vec![(2, &3), (1, &5), (0, &7)]
556 );
557 assert_eq!(
558 list.iter().rev().collect::<Vec<_>>(),
559 vec![(0, &7), (1, &5), (2, &3)]
560 );
561
562 list.remove(1);
563
564 assert!(!list.is_empty());
565 assert_eq!(list.len(), 2);
566
567 assert_eq!(list.front(), Some(&3));
568 assert_eq!(list.front_mut(), Some(&mut 3));
569
570 assert_eq!(list.back(), Some(&7));
571 assert_eq!(list.back_mut(), Some(&mut 7));
572
573 assert_eq!(list.iter().collect::<Vec<_>>(), vec![(2, &3), (0, &7)]);
574 assert_eq!(
575 list.iter().rev().collect::<Vec<_>>(),
576 vec![(0, &7), (2, &3)]
577 );
578
579 list.remove(0);
580
581 assert!(!list.is_empty());
582 assert_eq!(list.len(), 1);
583
584 assert_eq!(list.front(), Some(&3));
585 assert_eq!(list.front_mut(), Some(&mut 3));
586
587 assert_eq!(list.back(), Some(&3));
588 assert_eq!(list.back_mut(), Some(&mut 3));
589
590 assert_eq!(list.iter().collect::<Vec<_>>(), vec![(2, &3)]);
591 assert_eq!(list.iter().rev().collect::<Vec<_>>(), vec![(2, &3)]);
592
593 list.remove(2);
594
595 assert!(list.is_empty());
596 assert_eq!(list.len(), 0);
597
598 assert_eq!(list.front(), None);
599 assert_eq!(list.front_mut(), None);
600
601 assert_eq!(list.back(), None);
602 assert_eq!(list.back_mut(), None);
603
604 assert_eq!(list.iter().count(), 0);
605 assert_eq!(list.iter().rev().count(), 0);
606 }
607
608 #[test]
609 fn test_fixed_size_list_reorder() {
610 let mut list = FixedSizeList::new(4);
611
612 list.push_back('a');
613 list.push_front('b');
614 list.push_back('c');
615 list.push_front('d');
616
617 assert_eq!(
618 list.iter().collect::<Vec<_>>(),
619 vec![(3, &'d'), (1, &'b'), (0, &'a'), (2, &'c')]
620 );
621
622 list.reorder();
623
624 assert_eq!(
625 list.iter().collect::<Vec<_>>(),
626 vec![(0, &'d'), (1, &'b'), (2, &'a'), (3, &'c')]
627 );
628 }
629}
630