1 #![no_std] 2 #![feature(core_intrinsics)] 3 #![allow(internal_features)] 4 #![allow(clippy::needless_return)] 5 6 #[cfg(test)] 7 #[macro_use] 8 extern crate std; 9 10 use core::cmp::min; 11 use core::intrinsics::unlikely; 12 use core::marker::PhantomData; 13 use core::ops::Deref; 14 15 struct EmptyIdaItemRef<'a> { 16 _marker: PhantomData<&'a EmptyIdaItem>, 17 } 18 19 impl Deref for EmptyIdaItemRef<'_> { 20 type Target = EmptyIdaItem; 21 deref(&self) -> &Self::Target22 fn deref(&self) -> &Self::Target { 23 &EmptyIdaItem 24 } 25 } 26 27 struct EmptyIdaItem; 28 29 unsafe impl kdepends::xarray::ItemEntry for EmptyIdaItem { 30 type Ref<'a> 31 = EmptyIdaItemRef<'a> 32 where 33 Self: 'a; 34 into_raw(self) -> *const ()35 fn into_raw(self) -> *const () { 36 core::ptr::null() 37 } 38 from_raw(_raw: *const ()) -> Self39 unsafe fn from_raw(_raw: *const ()) -> Self { 40 EmptyIdaItem 41 } 42 raw_as_ref<'a>(_raw: *const ()) -> Self::Ref<'a>43 unsafe fn raw_as_ref<'a>(_raw: *const ()) -> Self::Ref<'a> { 44 EmptyIdaItemRef { 45 _marker: PhantomData, 46 } 47 } 48 } 49 /// id分配器 50 pub struct IdAllocator { 51 current_id: usize, 52 min_id: usize, 53 max_id: usize, 54 used: usize, 55 xarray: kdepends::xarray::XArray<EmptyIdaItem>, 56 } 57 58 impl IdAllocator { 59 /// 创建一个新的id分配器 new(initial_id: usize, max_id: usize) -> Option<Self>60 pub const fn new(initial_id: usize, max_id: usize) -> Option<Self> { 61 if initial_id >= max_id { 62 return None; 63 } 64 Some(Self { 65 current_id: initial_id, 66 min_id: initial_id, 67 max_id, 68 used: 0, 69 xarray: kdepends::xarray::XArray::new(), 70 }) 71 } 72 73 /// 可用的id数量 74 #[inline] available(&self) -> usize75 pub fn available(&self) -> usize { 76 self.max_id - self.min_id - self.used 77 } 78 79 /// 分配一个新的id 80 /// 81 /// ## 返回 82 /// 83 /// 如果分配成功，返回Some(id)，否则返回None alloc(&mut self) -> Option<usize>84 pub fn alloc(&mut self) -> Option<usize> { 85 if unlikely(self.available() == 0) { 86 return None; 87 } 88 89 if let Some(try1) = self.do_find_first_free_index(self.current_id, self.max_id) { 90 self.current_id = try1; 91 self.xarray.store(try1 as u64, EmptyIdaItem); 92 self.used += 1; 93 return Some(try1); 94 } 95 96 // 从头开始找 97 if let Some(try2) = 98 self.do_find_first_free_index(self.min_id, min(self.current_id, self.max_id)) 99 { 100 self.current_id = try2; 101 self.xarray.store(try2 as u64, EmptyIdaItem); 102 self.used += 1; 103 return Some(try2); 104 } 105 return None; 106 } 107 108 /// 检查id是否存在 109 /// 110 /// ## 参数 111 /// 112 /// - `id`：要检查的id 113 /// 114 /// ## 返回 115 /// 116 /// 如果id存在，返回true，否则返回false exists(&self, id: usize) -> bool117 pub fn exists(&self, id: usize) -> bool { 118 if id < self.min_id || id >= self.max_id { 119 return false; 120 } 121 self.xarray.load(id as u64).is_some() 122 } 123 do_find_first_free_index(&self, start_id: usize, end: usize) -> Option<usize>124 fn do_find_first_free_index(&self, start_id: usize, end: usize) -> Option<usize> { 125 (start_id..end).find(|&i| !self.exists(i)) 126 } 127 128 /// 释放一个id 129 /// 130 /// ## 参数 131 /// 132 /// - `id`：要释放的id free(&mut self, id: usize)133 pub fn free(&mut self, id: usize) { 134 if id < self.min_id || id >= self.max_id { 135 return; 136 } 137 if self.xarray.remove(id as u64).is_some() { 138 self.used -= 1; 139 } 140 } 141 142 /// 返回已经使用的id数量 used(&self) -> usize143 pub fn used(&self) -> usize { 144 self.used 145 } 146 147 /// 返回最大id数 get_max_id(&self) -> usize148 pub fn get_max_id(&self) -> usize { 149 self.max_id 150 } 151 } 152 153 impl core::fmt::Debug for IdAllocator { fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result154 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { 155 f.debug_struct("IdAllocator") 156 .field("current_id", &self.current_id) 157 .field("min_id", &self.min_id) 158 .field("max_id", &self.max_id) 159 .field("used", &self.used) 160 .field("xarray", &"xarray<()>") 161 .finish() 162 } 163 } 164 165 #[cfg(test)] 166 mod tests { 167 use super::*; 168 #[test] test_new_fail()169 fn test_new_fail() { 170 assert_eq!(IdAllocator::new(10, 10).is_none(), true); 171 assert_eq!(IdAllocator::new(11, 10).is_none(), true); 172 } 173 #[test] test_new_success()174 fn test_new_success() { 175 assert_eq!(IdAllocator::new(9, 10).is_some(), true); 176 assert_eq!(IdAllocator::new(0, 10).is_some(), true); 177 } 178 179 #[test] test_id_allocator()180 fn test_id_allocator() { 181 let mut ida = IdAllocator::new(0, 10).unwrap(); 182 assert_eq!(ida.alloc(), Some(0)); 183 assert_eq!(ida.alloc(), Some(1)); 184 assert_eq!(ida.alloc(), Some(2)); 185 assert_eq!(ida.alloc(), Some(3)); 186 assert_eq!(ida.alloc(), Some(4)); 187 assert_eq!(ida.alloc(), Some(5)); 188 assert_eq!(ida.alloc(), Some(6)); 189 assert_eq!(ida.alloc(), Some(7)); 190 assert_eq!(ida.alloc(), Some(8)); 191 assert_eq!(ida.alloc(), Some(9)); 192 assert_eq!(ida.alloc(), None); 193 194 for i in 0..10 { 195 assert_eq!(ida.exists(i), true); 196 } 197 198 ida.free(5); 199 200 for i in 0..10 { 201 if i == 5 { 202 assert_eq!(ida.exists(i), false); 203 } else { 204 assert_eq!(ida.exists(i), true); 205 } 206 } 207 assert_eq!(ida.used(), 9); 208 assert_eq!(ida.alloc(), Some(5)); 209 assert_eq!(ida.alloc(), None); 210 211 assert_eq!(ida.used(), 10); 212 for i in 0..10 { 213 ida.free(i); 214 } 215 216 assert_eq!(ida.used(), 0); 217 } 218 } 219