thin_boxed_slice/
lib.rs

1//! `ThinBoxedSlice` stores the size of the slice before the content of the slice, so that `size_of::<ThinBoxedSlice>` is only the size of a pointer:
2//!
3//! ```
4//! use core::mem::size_of;
5//! use thin_boxed_slice::ThinBoxedSlice;
6//! assert_eq!(size_of::<ThinBoxedSlice<u8>>(), size_of::<*mut u8>());
7//! ```
8//!
9//! # Examples
10//!
11//! ```
12//! use thin_boxed_slice::ThinBoxedSlice;
13//! use core::ops::Deref;
14//!
15//! let data = &[1, 2, 3];
16//! let result = ThinBoxedSlice::<i32>::from(data);
17//! assert_eq!(result.len(), 3);
18//! assert_eq!(result.deref(), data);
19//! ```
20//!
21//! `ThinBoxedSlice` is extremely useful to be the key of hash tables, because
22//! hash tables usually allocates more slots than elements to reduce hash
23//! collisions, and reduce the size of key with `ThinBoxedSlice` can reduce
24//! the memory consumption of extra slots allocated. Example:
25//!
26//! ```
27//! use thin_boxed_slice::ThinBoxedSlice;
28//! use std::collections::HashSet;
29//! use std::ops::Deref;
30//!
31//! let mut s: HashSet<ThinBoxedSlice<u8>> = HashSet::new();
32//! s.insert(ThinBoxedSlice::from("123".as_bytes()));
33//! s.insert(ThinBoxedSlice::from("456".as_bytes()));
34//! assert_eq!(s.get("123".as_bytes()).unwrap().deref(), "123".as_bytes());
35//! ```
36
37#![cfg_attr(not(test), no_std)]
38
39use core::borrow::Borrow;
40use core::cmp::max;
41use core::hash::{Hash, Hasher};
42use core::marker::PhantomData;
43use core::mem::{align_of, size_of};
44use core::ops::{Deref, DerefMut};
45use core::ptr::NonNull;
46use core::slice;
47
48use allocator_api2::alloc::{self, Allocator, Global};
49
50mod tests;
51
52#[derive(Debug)]
53pub struct ThinBoxedSlice<T, A: Allocator = Global> {
54    p: NonNull<u8>,
55    allocator: A,
56    phantom: PhantomData<T>,
57}
58
59impl<T, A: Allocator> ThinBoxedSlice<T, A> {
60    const fn array_offset() -> usize {
61        let align = align_of::<T>();
62        let misalign = size_of::<usize>() % align;
63        let padding = if misalign == 0 { 0 } else { align - misalign };
64        size_of::<usize>() + padding
65    }
66    fn layout(n: usize) -> alloc::Layout {
67        let alloc_len = Self::array_offset() + n * size_of::<T>();
68        let align = max(align_of::<usize>(), align_of::<T>());
69        alloc::Layout::from_size_align(alloc_len, align).unwrap()
70    }
71    fn array_ptr(&self) -> *mut T {
72        unsafe { self.p.clone().as_ptr().add(Self::array_offset()) as *mut T }
73    }
74    fn len(&self) -> usize {
75        // Useful unstable: non_null_convenience
76        unsafe { self.p.cast::<usize>().clone().as_ptr().read() }
77    }
78}
79
80impl<T: Clone, A: Allocator> ThinBoxedSlice<T, A> {
81    pub fn new_in(s: &[T], allocator: A) -> Self {
82        let layout = Self::layout(s.len());
83        unsafe {
84            let p = allocator.allocate(layout).unwrap().cast::<u8>();
85            let ret = Self {
86                p: p.clone(),
87                allocator,
88                phantom: PhantomData::default(),
89            };
90            // Useful unstable: non_null_convenience
91            p.cast::<usize>().as_ptr().write(s.len());
92            let mut v = ret.array_ptr();
93            // Useful unstable: maybe_uninit_write_slice
94            for i in 0..s.len() {
95                v.write(s[i].clone());
96                v = v.add(1);
97            }
98            ret
99        }
100    }
101}
102
103impl<T, A: Allocator> Drop for ThinBoxedSlice<T, A> {
104    fn drop(&mut self) {
105        unsafe {
106            self.allocator.deallocate(self.p, Self::layout(self.len()));
107        }
108    }
109}
110
111impl<T: Clone, A: Allocator + Default> From<&[T]> for ThinBoxedSlice<T, A> {
112    fn from(value: &[T]) -> Self {
113        Self::new_in(value, A::default())
114    }
115}
116
117impl<T: Clone, A: Allocator + Default, const N: usize> From<&[T; N]>
118    for ThinBoxedSlice<T, A>
119{
120    fn from(value: &[T; N]) -> Self {
121        Self::from(value.as_slice())
122    }
123}
124
125impl<T, A: Allocator> Deref for ThinBoxedSlice<T, A> {
126    type Target = [T];
127    fn deref(&self) -> &Self::Target {
128        unsafe { slice::from_raw_parts(self.array_ptr(), self.len()) }
129    }
130}
131
132impl<T, A: Allocator> DerefMut for ThinBoxedSlice<T, A> {
133    fn deref_mut(&mut self) -> &mut Self::Target {
134        unsafe { slice::from_raw_parts_mut(self.array_ptr(), self.len()) }
135    }
136}
137
138impl<T, A: Allocator> Borrow<[T]> for ThinBoxedSlice<T, A> {
139    fn borrow(&self) -> &[T] {
140        self.deref()
141    }
142}
143
144impl<T: PartialEq, A: Allocator> PartialEq for ThinBoxedSlice<T, A> {
145    fn eq(&self, other: &Self) -> bool {
146        self.deref() == other.deref()
147    }
148}
149
150impl<T: PartialEq, A: Allocator> Eq for ThinBoxedSlice<T, A> {
151    fn assert_receiver_is_total_eq(&self) {}
152}
153
154impl<T: Hash, A: Allocator> Hash for ThinBoxedSlice<T, A> {
155    fn hash<H: Hasher>(&self, state: &mut H) {
156        self.deref().hash(state);
157    }
158}
thin_boxed_slice/lib.rs

thin_boxed_slice/
lib.rs
