fixed_free_list/lib.rs
1//! A fixed-size free-list with optional key lifetime safety and macroless unique typing.
2#![doc(html_root_url = "https://docs.rs/fixed_free_list")]
3#![crate_name = "fixed_free_list"]
4#![warn(
5 missing_debug_implementations,
6 trivial_casts,
7 trivial_numeric_casts,
8 unused_lifetimes,
9 unused_import_braces,
10 clippy::shadow_unrelated
11)]
12#![deny(missing_docs, unaligned_references, unsafe_op_in_unsafe_fn)]
13#![cfg_attr(all(nightly, feature = "unstable"), feature(maybe_uninit_uninit_array))]
14
15use std::{
16 fmt::{Debug, Formatter, Result},
17 marker::PhantomData,
18 mem::{self, ManuallyDrop, MaybeUninit},
19};
20
21union Block<T> {
22 value: ManuallyDrop<T>,
23 next: usize,
24}
25
26/// A fixed-size free-list.
27///
28/// # Time Complexity
29///
30/// All operations are worst case O(1) unless noted otherwise
31///
32/// # Examples
33///
34/// ```
35/// # use fixed_free_list::*;
36/// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
37/// let key1 = list.alloc(8).unwrap();
38/// let key2 = list.alloc(5).unwrap();
39/// assert_eq!(unsafe { *list.get_unchecked(key1) }, 8);
40/// assert_eq!(unsafe { *list.get_unchecked(key2) }, 5);
41/// let value = unsafe { list.get_mut_unchecked(key1) };
42/// *value = 2;
43/// assert_eq!(unsafe { list.free_unchecked(key1) }, 2);
44/// assert!(list.is_free(key1));
45/// assert_eq!(list.size_hint(), 2);
46/// let key3 = list.alloc(7).unwrap();
47/// assert_eq!(list.size_hint(), 2);
48/// list.clear();
49/// assert!(list.is_free(key3));
50/// ```
51pub struct FixedFreeList<T, const N: usize> {
52 next: usize,
53 high: usize,
54 data: [MaybeUninit<Block<T>>; N],
55}
56
57impl<T, const N: usize> FixedFreeList<T, N> {
58 /// Creates a new empty `FixedFreeList`.
59 ///
60 /// # Examples
61 ///
62 /// ```
63 /// # use fixed_free_list::*;
64 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
65 /// ```
66 #[inline(always)]
67 pub fn new() -> Self {
68 Self {
69 next: N,
70 high: 0,
71 #[cfg(all(nightly, feature = "unstable"))]
72 data: MaybeUninit::uninit_array(),
73 #[cfg(not(all(nightly, feature = "unstable")))]
74 data: unsafe { MaybeUninit::uninit().assume_init() },
75 }
76 }
77
78 /// If there is space, adds `value` to the free list and returns its key.
79 /// If there is no space, Drops `value` and returns `None`.
80 ///
81 /// # Returns
82 ///
83 /// `None` if the list was already full.
84 /// Note: `value` is dropped in this case. Check [`is_full`] beforehand to avoid this if desired.
85 ///
86 /// `Some(key)` if there was spare capacity to accommodate `value`.
87 /// `key` can now be used to access `value` via [`get_unchecked`].
88 ///
89 /// # Examples
90 ///
91 /// ```
92 /// # use fixed_free_list::*;
93 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
94 /// list.alloc(1);
95 /// ```
96 pub fn alloc(&mut self, value: T) -> Option<usize> {
97 let key;
98 if self.next < N {
99 // Use a previously used but now free space
100 key = self.next;
101 // Update `next` to point at the next free space now that the current one will be used
102 // # Safety
103 // This space is guaranteed to be free, because otherwise `next` wouldn't point at it.
104 self.next = unsafe { self.data.get_unchecked(key).assume_init_ref().next };
105 } else {
106 if self.high >= N {
107 // Drops `value`
108 return None;
109 }
110 // Use a fresh uninitialized space
111 key = self.high;
112 // Bump high-water mark
113 self.high += 1;
114 };
115 // Dropping is unneccessary here because `data[key]` is either `usize` or `MaybeUninit<T>::uninit()`
116 unsafe {
117 *self.data.get_unchecked_mut(key) = MaybeUninit::new(Block {
118 value: ManuallyDrop::new(value),
119 });
120 }
121 Some(key)
122 }
123
124 /// Solely intended for verification purposes.
125 /// If your algorithm needs this you're probably doing something wrong.
126 ///
127 /// # Time Complexity
128 ///
129 /// Worst case O(N)
130 ///
131 /// # Examples
132 ///
133 /// ```
134 /// # use fixed_free_list::*;
135 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
136 /// assert_eq!(list.is_free(0), true);
137 /// let key = list.alloc(1).unwrap();
138 /// assert_eq!(list.is_free(0), false);
139 /// unsafe { list.free_unchecked(key); }
140 /// assert_eq!(list.is_free(0), true);
141 /// ```
142 pub fn is_free(&self, key: usize) -> bool {
143 if key >= self.high {
144 return true;
145 }
146 let mut next = self.next;
147 while next < N {
148 if next == key {
149 return true;
150 }
151 next = unsafe { self.data.get_unchecked(next).assume_init_ref().next };
152 }
153 false
154 }
155
156 /// Frees the space occupied by the value at `key` and returns the value.
157 ///
158 /// # Returns
159 ///
160 /// The value at `key`.
161 ///
162 /// # Safety
163 ///
164 /// `key` must have originated from calling [`alloc`] on the same instance
165 /// and the space must not already been freed since the [`alloc`] call.
166 ///
167 /// # Examples
168 ///
169 /// ```
170 /// # use fixed_free_list::*;
171 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
172 /// let key = list.alloc(1).unwrap();
173 /// let value = unsafe { list.free_unchecked(key) };
174 /// assert_eq!(value, 1);
175 /// ```
176 #[inline(always)]
177 pub unsafe fn free_unchecked(&mut self, key: usize) -> T {
178 #[cfg(all(feature = "strict"))]
179 assert!(!self.is_free(key));
180
181 let value = mem::replace(
182 unsafe { self.data.get_unchecked_mut(key) },
183 MaybeUninit::new(Block { next: self.next }),
184 );
185
186 self.next = key;
187
188 // # Safety
189 // Function invariants imply the space is occupied by an initialized value
190 ManuallyDrop::into_inner(unsafe { value.assume_init().value })
191 }
192
193 /// Provides immutable access to the value at `key`.
194 ///
195 /// # Returns
196 ///
197 /// An immutable borrow of the value at `key`.
198 ///
199 /// # Safety
200 ///
201 /// `key` must have originated from calling [`alloc`] on the same instance
202 /// and the space must not already been freed since the [`alloc`] call.
203 ///
204 /// There must be no existing mutable borrow of the value at `key` via [`get_mut_unchecked`].
205 /// Multiple immutable borrows are permitted.
206 ///
207 /// # Examples
208 ///
209 /// ```
210 /// # use fixed_free_list::*;
211 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
212 /// let key = list.alloc(1).unwrap();
213 /// let value = unsafe { list.get_unchecked(key) };
214 /// assert_eq!(*value, 1);
215 /// ```
216 #[inline(always)]
217 pub unsafe fn get_unchecked(&self, key: usize) -> &T {
218 #[cfg(all(feature = "strict"))]
219 assert!(!self.is_free(key));
220
221 // # Safety
222 // Function invariants imply the space is occupied by an initialized value
223 unsafe { &self.data.get_unchecked(key).assume_init_ref().value }
224 }
225
226 /// Provides mutable access to the value at `key`.
227 ///
228 /// # Returns
229 ///
230 /// An immutable borrow of the value at `key`.
231 ///
232 /// # Safety
233 ///
234 /// `key` must have originated from calling [`alloc`] on the same instance
235 /// and the space must not already been freed since the [`alloc`] call.
236 ///
237 /// There must be no existing borrows of the value at `key` via [`get_unchecked`] or [`get_mut_unchecked`].
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// # use fixed_free_list::*;
243 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
244 /// let key = list.alloc(8).unwrap();
245 /// let value = unsafe { list.get_mut_unchecked(key) };
246 /// *value = 2;
247 /// assert_eq!(unsafe { list.free_unchecked(key) }, 2);
248 /// ```
249 #[inline(always)]
250 pub unsafe fn get_mut_unchecked(&mut self, key: usize) -> &mut T {
251 #[cfg(all(feature = "strict"))]
252 assert!(!self.is_free(key));
253
254 // # Safety
255 // Function invariants imply the space is occupied by an initialized value
256 unsafe { &mut self.data.get_unchecked_mut(key).assume_init_mut().value }
257 }
258
259 /// Returns an upper bound on the number of elements contained.
260 /// The actual number of elements is guaranteed to be less than or equal to this.
261 ///
262 /// # Examples
263 ///
264 /// ```
265 /// # use fixed_free_list::*;
266 /// let mut list: FixedFreeList<i32, 16> = FixedFreeList::new();
267 /// list.alloc(5);
268 /// assert_eq!(list.size_hint(), 1);
269 /// ```
270 #[inline(always)]
271 pub fn size_hint(&self) -> usize {
272 self.high
273 }
274
275 /// Returns `true` if there is no free space left.
276 ///
277 /// # Examples
278 ///
279 /// ```
280 /// # use fixed_free_list::*;
281 /// let mut list: FixedFreeList<i32, 1> = FixedFreeList::new();
282 /// assert!(!list.is_full());
283 /// list.alloc(7);
284 /// assert!(list.is_full());
285 /// ```
286 #[inline(always)]
287 pub fn is_full(&self) -> bool {
288 self.high == N && self.next == N
289 }
290
291 /// Removes and drops all contained values.
292 ///
293 /// # Time Complexity
294 ///
295 /// O(1) if `T: Copy`, otherwise O(N).
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// # use fixed_free_list::*;
301 /// let mut list: FixedFreeList<i32, 1> = FixedFreeList::new();
302 /// list.alloc(3);
303 /// assert!(list.is_full());
304 /// list.clear();
305 /// assert!(!list.is_full());
306 /// ```
307 pub fn clear(&mut self) {
308 if mem::needs_drop::<T>() {
309 let mut free = [false; N];
310 let mut next = self.next;
311 while next < N {
312 free[next] = true;
313 next = unsafe { self.data.get_unchecked(next).assume_init_ref().next };
314 }
315 for (i, &is_free) in free.iter().enumerate().take(self.high) {
316 if !is_free {
317 unsafe {
318 ManuallyDrop::drop(
319 &mut self.data.get_unchecked_mut(i).assume_init_mut().value,
320 );
321 }
322 }
323 }
324 }
325
326 self.high = 0;
327 self.next = N;
328 }
329}
330
331unsafe impl<T: Sync, const N: usize> Sync for FixedFreeList<T, N> {}
332unsafe impl<T: Send, const N: usize> Send for FixedFreeList<T, N> {}
333
334impl<T, const N: usize> Drop for FixedFreeList<T, N> {
335 #[inline(always)]
336 fn drop(&mut self) {
337 if mem::needs_drop::<T>() {
338 self.clear();
339 }
340 }
341}
342
343#[derive(Debug)]
344enum Space<T: Sized> {
345 Value(T),
346 Free(usize),
347 Uninit,
348}
349
350trait UninitProvider: Sized {
351 const UNINIT: Space<Self>;
352}
353
354impl<T> UninitProvider for T {
355 const UNINIT: Space<Self> = Space::Uninit;
356}
357
358impl<T, const N: usize> Debug for FixedFreeList<T, N>
359where
360 T: Debug,
361{
362 fn fmt(&self, f: &mut Formatter) -> Result {
363 // Alternative array initializer for rustc <1.63
364 // let mut spaces = [<&T>::UNINIT; N];
365 let mut spaces = std::array::from_fn::<Space<&T>, N, _>(|_| Space::Uninit);
366 let mut next = self.next;
367 while next < N {
368 let free = unsafe { self.data.get_unchecked(next).assume_init_ref().next };
369 spaces[next] = Space::Free(free);
370 next = free;
371 }
372 for (i, space) in spaces.iter_mut().enumerate().take(self.high) {
373 if let Space::Uninit = space {
374 *space = Space::Value(unsafe { &self.data[i].assume_init_ref().value });
375 }
376 }
377
378 f.debug_struct("FixedFreeList")
379 .field("next", &self.next)
380 .field("high", &self.high)
381 .field("data", &spaces)
382 .finish()
383 }
384}
385
386impl<T, const N: usize> Default for FixedFreeList<T, N> {
387 fn default() -> Self {
388 Self::new()
389 }
390}
391
392/// A lifetimed key into a `SafeFixedFreeList`
393#[derive(Debug)]
394pub struct ArenaKey<'a, T> {
395 index: usize,
396 _marker: PhantomData<&'a T>,
397}
398
399/// A fixed-size free-list with key lifetime safety and macroless unique typing.
400/// This is a somewhat experimental use of the borrowchecker,
401/// and as such [`new`] is `unsafe`.
402pub struct SafeFixedFreeList<'a, T, const N: usize, U> {
403 _marker: PhantomData<&'a U>,
404 inner: FixedFreeList<T, N>,
405}
406
407impl<'a, T, const N: usize, U: Fn()> SafeFixedFreeList<'a, T, N, U> {
408 /// Creates a new empty [`SafeFixedFreeList`]
409 ///
410 /// # Safety
411 /// You MUST provide a unique inline closure to ensure keys are not
412 /// shared with another instance.
413 ///
414 /// # Examples
415 ///
416 /// ```
417 /// # use fixed_free_list::*;
418 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
419 /// ```
420 #[inline(always)]
421 pub unsafe fn new(_: U) -> Self {
422 Self {
423 _marker: PhantomData,
424 inner: FixedFreeList::new(),
425 }
426 }
427
428 /// If there is space, adds `value` to the free list and returns its key.
429 /// If there is no space, Drops `value` and returns `None`.
430 ///
431 /// # Returns
432 ///
433 /// `None` if the list was already full.
434 /// Note: `value` is dropped in this case. Check [`is_full`] beforehand to avoid this if desired.
435 ///
436 /// `Some(key)` if there was spare capacity to accommodate `value`.
437 /// `key` can now be used to access `value` via [`get`].
438 ///
439 /// # Examples
440 ///
441 /// ```
442 /// # use fixed_free_list::*;
443 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
444 /// list.alloc(1);
445 /// ```
446 #[inline(always)]
447 pub fn alloc<'k>(&mut self, value: T) -> Option<ArenaKey<'k, U>>
448 where
449 'a: 'k,
450 {
451 self.inner.alloc(value).map(|index| ArenaKey {
452 index,
453 _marker: PhantomData,
454 })
455 }
456
457 /// Frees the space occupied by the value at `key` and returns the value.
458 ///
459 /// # Returns
460 ///
461 /// The value at `key`.
462 ///
463 /// # Examples
464 ///
465 /// ```
466 /// # use fixed_free_list::*;
467 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
468 /// let key = list.alloc(1).unwrap();
469 /// let value = list.free(key);
470 /// assert_eq!(value, 1);
471 /// ```
472 #[inline(always)]
473 pub fn free(&mut self, key: ArenaKey<U>) -> T {
474 unsafe { self.inner.free_unchecked(key.index) }
475 }
476
477 /// Provides immutable access to the value at `key`.
478 ///
479 /// # Returns
480 ///
481 /// An immutable borrow of the value at `key`.
482 ///
483 /// # Examples
484 ///
485 /// ```
486 /// # use fixed_free_list::*;
487 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
488 /// let key = list.alloc(1).unwrap();
489 /// let value = list.get(&key);
490 /// assert_eq!(*value, 1);
491 /// ```
492 #[inline(always)]
493 pub fn get<'k: 'v, 'v>(&self, key: &'k ArenaKey<U>) -> &'v T
494 where
495 'a: 'k,
496 {
497 unsafe { mem::transmute::<&T, &T>(self.inner.get_unchecked(key.index)) }
498 }
499
500 /// Provides mutable access to the value at `key`.
501 ///
502 /// # Returns
503 ///
504 /// An immutable borrow of the value at `key`.
505 ///
506 /// # Examples
507 ///
508 /// ```
509 /// # use fixed_free_list::*;
510 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
511 /// let mut key = list.alloc(8).unwrap();
512 /// let value = list.get_mut(&mut key);
513 /// *value = 2;
514 /// assert_eq!(list.free(key), 2);
515 /// ```
516 #[inline(always)]
517 pub fn get_mut<'k: 'v, 'v>(&mut self, key: &'k mut ArenaKey<U>) -> &'v mut T
518 where
519 'a: 'k,
520 {
521 unsafe { mem::transmute::<&mut T, &mut T>(self.inner.get_mut_unchecked(key.index)) }
522 }
523
524 /// Returns an upper bound on the number of elements contained.
525 /// The actual number of elements is guaranteed to be less than or equal to this.
526 ///
527 /// # Examples
528 ///
529 /// ```
530 /// # use fixed_free_list::*;
531 /// let mut list = unsafe { SafeFixedFreeList::<i32, 16, _>::new(||()) };
532 /// list.alloc(5);
533 /// assert_eq!(list.size_hint(), 1);
534 /// ```
535 #[inline(always)]
536 pub fn size_hint(&self) -> usize {
537 self.inner.size_hint()
538 }
539
540 /// Returns `true` if there is no free space left.
541 ///
542 /// # Examples
543 ///
544 /// ```
545 /// # use fixed_free_list::*;
546 /// let mut list = unsafe { SafeFixedFreeList::<i32, 1, _>::new(||()) };
547 /// assert!(!list.is_full());
548 /// list.alloc(7);
549 /// assert!(list.is_full());
550 /// ```
551 #[inline(always)]
552 pub fn is_full(&self) -> bool {
553 self.inner.is_full()
554 }
555
556 /// Removes and drops all contained values.
557 ///
558 /// # Time Complexity
559 ///
560 /// O(1) if `T: Copy`, otherwise O(N).
561 ///
562 /// # Examples
563 ///
564 /// ```
565 /// # use fixed_free_list::*;
566 /// let mut list = unsafe { SafeFixedFreeList::<i32, 1, _>::new(||()) };
567 /// list.alloc(3);
568 /// assert!(list.is_full());
569 /// list.clear();
570 /// assert!(!list.is_full());
571 /// ```
572 #[inline(always)]
573 pub fn clear(&mut self) {
574 self.inner.clear();
575 }
576}
577
578impl<'a, T, const N: usize, U: Fn()> Debug for SafeFixedFreeList<'a, T, N, U>
579where
580 T: Debug,
581{
582 fn fmt(&self, f: &mut Formatter) -> Result {
583 f.debug_struct("SafeFixedFreeList")
584 .field("inner", &self.inner)
585 .finish()
586 }
587}
588
589#[cfg(test)]
590mod test {
591 use crate::*;
592 use rand::Rng;
593 use std::cell::RefCell;
594
595 #[test]
596 fn test_safe() {
597 fn consume<T>(_: T) {}
598 let mut list = unsafe { SafeFixedFreeList::<u32, 16, _>::new(|| ()) };
599 let mut key1 = list.alloc(5).unwrap();
600 let mut key2 = list.alloc(6).unwrap();
601 let value1 = list.get_mut(&mut key1);
602 let value2 = list.get_mut(&mut key2);
603 // miri hates this, I think its a valid abuse of borrowck though
604 *value1 = 2;
605 consume(value1);
606 consume(value2);
607 list.free(key1);
608 list.free(key2);
609 consume(list);
610 }
611
612 #[test]
613 fn test_remove_all() {
614 let mut list = FixedFreeList::<u32, 16>::new();
615 for i in 0..16 {
616 assert_eq!(list.alloc(i), Some(i as usize));
617 }
618 for i in 0..16 {
619 unsafe {
620 assert_eq!(list.free_unchecked(i as usize), i);
621 }
622 }
623 for i in 0..16 {
624 assert!(list.is_free(i));
625 }
626 for i in 0..16 {
627 list.alloc(i);
628 }
629 assert!(list.is_full());
630 }
631
632 #[test]
633 fn test_reuse_half() {
634 let mut list = FixedFreeList::<u32, 16>::new();
635 for i in 0..16 {
636 assert_eq!(list.alloc(i), Some(i as usize));
637 }
638 for i in 0..8 {
639 unsafe {
640 list.free_unchecked(i * 2usize);
641 }
642 }
643 for i in 0..8 {
644 list.alloc(i);
645 }
646 assert!(list.is_full());
647 }
648
649 #[test]
650 fn test_reuse_preferred() {
651 let mut list = FixedFreeList::<u32, 16>::new();
652 for i in 0..8 {
653 assert_eq!(list.alloc(i), Some(i as usize));
654 }
655 for i in 0..4 {
656 unsafe {
657 list.free_unchecked(i * 2usize);
658 }
659 }
660 for i in 0..4 {
661 list.alloc(i);
662 }
663 assert_eq!(list.size_hint(), 8);
664 for i in 8..16 {
665 assert_eq!(list.alloc(i), Some(i as usize));
666 }
667 assert!(list.is_full());
668 }
669
670 #[test]
671 fn test_debug() {
672 let mut list = FixedFreeList::<u32, 8>::new();
673 list.alloc(3);
674 let key1 = list.alloc(5).unwrap();
675 list.alloc(7);
676 list.alloc(4);
677 let key2 = list.alloc(2).unwrap();
678 unsafe {
679 list.free_unchecked(key1);
680 list.free_unchecked(key2);
681 }
682 assert_eq!(format!("{:?}", list), "FixedFreeList { next: 4, high: 5, data: [Value(3), Free(8), Value(7), Value(4), Free(1), Uninit, Uninit, Uninit] }");
683 }
684
685 #[test]
686 fn test_full() {
687 let mut list = FixedFreeList::<u32, 4>::new();
688 assert_eq!(list.alloc(3), Some(0));
689 assert_eq!(list.alloc(5), Some(1));
690 assert_eq!(list.alloc(7), Some(2));
691 assert_eq!(list.alloc(4), Some(3));
692 assert_eq!(list.alloc(2), None);
693 }
694
695 #[test]
696 fn test_drop() {
697 let drops = RefCell::new(0usize);
698 {
699 let mut list: FixedFreeList<DropCounted, 16> = FixedFreeList::new();
700 for _ in 0..11 {
701 list.alloc(DropCounted(&drops));
702 }
703 assert_eq!(*drops.borrow(), 0);
704
705 // Drop a few
706 for i in 0..4 {
707 unsafe {
708 list.free_unchecked(i);
709 }
710 }
711 assert_eq!(*drops.borrow(), 4);
712
713 // Let the rest drop
714 }
715 assert_eq!(*drops.borrow(), 11);
716 {
717 let mut list: FixedFreeList<DropCounted, 1> = FixedFreeList::new();
718 list.alloc(DropCounted(&drops));
719
720 // Inserting into a full list should drop the value
721 list.alloc(DropCounted(&drops));
722 assert_eq!(*drops.borrow(), 12);
723
724 // Let the rest drop
725 }
726 assert_eq!(*drops.borrow(), 13);
727 }
728
729 #[derive(Clone)]
730 struct DropCounted<'a>(&'a RefCell<usize>);
731
732 impl<'a> Drop for DropCounted<'a> {
733 fn drop(&mut self) {
734 *self.0.borrow_mut() += 1;
735 }
736 }
737
738 #[test]
739 fn test_fuzz() {
740 fuzz::<0, 4>(10);
741 fuzz::<1, 8>(10);
742 fuzz::<2, 8>(10);
743 fuzz::<3, 8>(10);
744 fuzz::<5, 8>(10);
745 fuzz::<7, 16>(10);
746 fuzz::<16, 16>(10);
747 fuzz::<16, 64>(10);
748 }
749
750 fn fuzz<const N: usize, const M: usize>(iters: usize) {
751 for _ in 0..iters {
752 let mut list: FixedFreeList<usize, N> = FixedFreeList::new();
753 let mut keys = Vec::new();
754 let mut count = 0;
755 let mut high = 0;
756 for i in 0..M {
757 if rand::thread_rng().gen() {
758 if let Some(key) = list.alloc(i) {
759 keys.push(key);
760 count += 1;
761 if high < count {
762 high = count;
763 }
764 } else {
765 assert_eq!(count, N);
766 }
767 } else if count > 0 {
768 let key = keys.swap_remove(rand::thread_rng().gen_range(0..keys.len()));
769 unsafe {
770 assert!(!list.is_free(key));
771 list.free_unchecked(key);
772 assert!(list.is_free(key));
773 count -= 1;
774 }
775 }
776 assert_eq!(list.size_hint(), high);
777 }
778 }
779 }
780}