1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
//! An implementation of the individual memory blocks that make up a [`Hive`].
use core::{
mem::{self, ManuallyDrop},
ptr::NonNull,
};
use crate::hive::skipfield;
/// A type that may be either part of the free list or an element.
pub union Slot<T, Sk>
where
Sk: skipfield::SkipfieldType,
{
/// An element of the [`Group`].
element: ManuallyDrop<T>,
/// A free list index.
free_list: FreeList<Sk>,
}
/// The contents of a free list index.
///
/// This uses the `packed` C representation to avoid any excess space. This is
/// not a problem in the general case as our type will only ever be `u16` or
/// `u8` unless an end-user overrides the skipfield type with a custom
/// implementation.
#[repr(C, packed)]
#[derive(Copy, Clone)]
pub struct FreeList<Sk>
where
Sk: skipfield::SkipfieldType,
{
/// Index of the previous element in the free list.
pub previous: Sk,
/// Index of the next element in the free list.
pub next: Sk,
}
/// A doubly-linked `Group` of `T` with a skipfield type of `Sk`.
pub struct Group<T, Sk>
where
Sk: skipfield::SkipfieldType,
{
/// Pointer to the start of the skipfield.
pub skipfield: Option<NonNull<Sk>>,
/// Pointer to the next [`Group`].
pub next: Option<NonNull<Group<T, Sk>>>,
/// Pointer to element storage.
pub elements: Option<NonNull<Slot<T, Sk>>>,
/// Pointer to the previous [`Group`].
pub previous: Option<NonNull<Group<T, Sk>>>,
/// Index of the last erased element in the group.
///
/// The last erased element contains the index of the next, and so on. If
/// this is equal to the maximum value of the underlying integer type,
/// then the free list is considered to be empty.
pub free_list_head: Sk,
/// Total number of elements this [`Group`] can hold.
pub capacity: Sk,
/// Number of elements stored in this [`Group`].
pub size: Sk,
/// Pointer to the next [`Group`] with erased elements.
pub next_with_erasures: Option<NonNull<Group<T, Sk>>>,
/// Pointer to the previous [`Group`] with erased elements.
pub previous_with_erasures: Option<NonNull<Group<T, Sk>>>,
/// Number assigned to this group in the [`Hive`].
pub number: usize,
}
impl<T, Sk> Group<T, Sk>
where
Sk: skipfield::SkipfieldType,
{
/// Size of each individual element within a [`Group`]
pub const ELEMENT_ALLOCATION_SIZE: usize =
compute_element_allocation_size::<T, Sk>();
}
/// Helper function which computes the allocation size of elements
const fn compute_element_allocation_size<T, Sk>() -> usize {
let t_align = mem::align_of::<T>();
let t_size = mem::size_of::<T>();
let sk2_size = mem::size_of::<Sk>() * 2;
if t_align > t_size {
if sk2_size > t_align {
sk2_size
} else {
t_align
}
} else {
if sk2_size > t_size { sk2_size } else { t_size }
}
}
|
