1use dashmap::DashMap;
17use ipnetwork::IpNetwork;
18use std::sync::{
19 Arc, RwLock,
20 atomic::{AtomicU8, Ordering},
21};
22
23use crate::traits::Node;
24use crate::types::Metadata;
25
26#[derive(Default)]
31#[repr(C, align(64))]
32pub struct NormalRadixNode {
33 edge_bits: RwLock<[u8; 16]>,
35 edge_len: RwLock<usize>,
37 metadata: RwLock<Option<Metadata>>,
39 prefix: RwLock<Option<IpNetwork>>,
41 left: RwLock<Option<Arc<dyn Node>>>,
43 right: RwLock<Option<Arc<dyn Node>>>,
45}
46
47impl NormalRadixNode {
48 pub fn new() -> Self {
49 Self::default()
50 }
51}
52
53impl Node for NormalRadixNode {
54 fn bit(&self) -> Option<u8> {
58 None
59 }
60
61 fn left(&self) -> Option<Arc<dyn Node>> {
62 self.left.read().unwrap().clone()
63 }
64
65 fn right(&self) -> Option<Arc<dyn Node>> {
66 self.right.read().unwrap().clone()
67 }
68
69 fn metadata(&self) -> Option<Metadata> {
70 self.metadata.read().unwrap().clone()
71 }
72
73 fn prefix(&self) -> Option<IpNetwork> {
74 *self.prefix.read().unwrap()
75 }
76
77 fn set_left(&self, node: Option<Arc<dyn Node>>) {
78 *self.left.write().unwrap() = node;
79 }
80
81 fn set_right(&self, node: Option<Arc<dyn Node>>) {
82 *self.right.write().unwrap() = node;
83 }
84
85 fn set_metadata(&self, metadata: Metadata) {
86 *self.metadata.write().unwrap() = Some(metadata);
87 }
88
89 fn clear_metadata(&self) {
90 *self.metadata.write().unwrap() = None;
91 }
92
93 fn set_bit(&self, _bit: u8) {}
95
96 fn set_prefix(&self, prefix: IpNetwork) {
97 *self.prefix.write().unwrap() = Some(prefix);
98 }
99
100 fn edge_bits(&self) -> Option<[u8; 16]> {
103 Some(self.edge_bits.read().unwrap().clone())
104 }
105
106 fn edge_len(&self) -> Option<usize> {
107 Some(*self.edge_len.read().unwrap())
108 }
109
110 fn set_edge(&self, bits: [u8; 16], len: usize) {
111 *self.edge_bits.write().unwrap() = bits;
112 *self.edge_len.write().unwrap() = len;
113 }
114}
115
116#[repr(C, align(64))]
122pub struct AtomicRadixNode {
123 atomic_edge_len: AtomicU8,
126 edge_bits: RwLock<[u8; 16]>,
127 edge_len_overflow: RwLock<usize>, metadata: RwLock<Option<Metadata>>,
129 prefix: RwLock<Option<IpNetwork>>,
130 left: RwLock<Option<Arc<dyn Node>>>,
131 right: RwLock<Option<Arc<dyn Node>>>,
132}
133
134impl AtomicRadixNode {
135 pub fn new() -> Self {
136 Self {
137 atomic_edge_len: AtomicU8::new(0),
138 edge_bits: RwLock::new([0u8; 16]),
139 edge_len_overflow: RwLock::new(0),
140 metadata: RwLock::new(None),
141 prefix: RwLock::new(None),
142 left: RwLock::new(None),
143 right: RwLock::new(None),
144 }
145 }
146}
147
148impl Default for AtomicRadixNode {
149 fn default() -> Self {
150 Self::new()
151 }
152}
153
154impl Node for AtomicRadixNode {
155 fn bit(&self) -> Option<u8> {
156 None
157 }
158
159 fn left(&self) -> Option<Arc<dyn Node>> {
160 self.left.read().unwrap().clone()
161 }
162
163 fn right(&self) -> Option<Arc<dyn Node>> {
164 self.right.read().unwrap().clone()
165 }
166
167 fn metadata(&self) -> Option<Metadata> {
168 self.metadata.read().unwrap().clone()
169 }
170
171 fn prefix(&self) -> Option<IpNetwork> {
172 *self.prefix.read().unwrap()
173 }
174
175 fn set_left(&self, node: Option<Arc<dyn Node>>) {
176 *self.left.write().unwrap() = node;
177 }
178
179 fn set_right(&self, node: Option<Arc<dyn Node>>) {
180 *self.right.write().unwrap() = node;
181 }
182
183 fn set_metadata(&self, metadata: Metadata) {
184 *self.metadata.write().unwrap() = Some(metadata);
185 }
186
187 fn clear_metadata(&self) {
188 *self.metadata.write().unwrap() = None;
189 }
190
191 fn set_bit(&self, _bit: u8) {}
192
193 fn set_prefix(&self, prefix: IpNetwork) {
194 *self.prefix.write().unwrap() = Some(prefix);
195 }
196
197 fn edge_bits(&self) -> Option<[u8; 16]> {
198 Some(self.edge_bits.read().unwrap().clone())
199 }
200
201 fn edge_len(&self) -> Option<usize> {
202 let atomic_val = self.atomic_edge_len.load(Ordering::Acquire) as usize;
203 if atomic_val < 255 {
204 Some(atomic_val)
205 } else {
206 Some(*self.edge_len_overflow.read().unwrap())
208 }
209 }
210
211 fn set_edge(&self, bits: [u8; 16], len: usize) {
212 *self.edge_bits.write().unwrap() = bits;
213 if len < 255 {
214 self.atomic_edge_len.store(len as u8, Ordering::Release);
215 } else {
216 self.atomic_edge_len.store(255, Ordering::Release);
218 *self.edge_len_overflow.write().unwrap() = len;
219 }
220 }
221}
222
223#[repr(C, align(64))]
228pub struct PaddedRadixNode {
229 edge_bits: RwLock<[u8; 16]>,
230 _pad1: [u8; 63],
231 edge_len: RwLock<usize>,
232 metadata: RwLock<Option<Metadata>>,
233 prefix: RwLock<Option<IpNetwork>>,
234 left: RwLock<Option<Arc<dyn Node>>>,
235 right: RwLock<Option<Arc<dyn Node>>>,
236}
237
238impl PaddedRadixNode {
239 pub fn new() -> Self {
240 Self {
241 edge_bits: RwLock::new([0u8; 16]),
242 _pad1: [0; 63],
243 edge_len: RwLock::new(0),
244 metadata: RwLock::new(None),
245 prefix: RwLock::new(None),
246 left: RwLock::new(None),
247 right: RwLock::new(None),
248 }
249 }
250}
251
252impl Default for PaddedRadixNode {
253 fn default() -> Self {
254 Self::new()
255 }
256}
257
258impl Node for PaddedRadixNode {
259 fn bit(&self) -> Option<u8> {
260 None
261 }
262
263 fn left(&self) -> Option<Arc<dyn Node>> {
264 self.left.read().unwrap().clone()
265 }
266
267 fn right(&self) -> Option<Arc<dyn Node>> {
268 self.right.read().unwrap().clone()
269 }
270
271 fn metadata(&self) -> Option<Metadata> {
272 self.metadata.read().unwrap().clone()
273 }
274
275 fn prefix(&self) -> Option<IpNetwork> {
276 *self.prefix.read().unwrap()
277 }
278
279 fn set_left(&self, node: Option<Arc<dyn Node>>) {
280 *self.left.write().unwrap() = node;
281 }
282
283 fn set_right(&self, node: Option<Arc<dyn Node>>) {
284 *self.right.write().unwrap() = node;
285 }
286
287 fn set_metadata(&self, metadata: Metadata) {
288 *self.metadata.write().unwrap() = Some(metadata);
289 }
290
291 fn clear_metadata(&self) {
292 *self.metadata.write().unwrap() = None;
293 }
294
295 fn set_bit(&self, _bit: u8) {}
296
297 fn set_prefix(&self, prefix: IpNetwork) {
298 *self.prefix.write().unwrap() = Some(prefix);
299 }
300
301 fn edge_bits(&self) -> Option<[u8; 16]> {
302 Some(self.edge_bits.read().unwrap().clone())
303 }
304
305 fn edge_len(&self) -> Option<usize> {
306 Some(*self.edge_len.read().unwrap())
307 }
308
309 fn set_edge(&self, bits: [u8; 16], len: usize) {
310 *self.edge_bits.write().unwrap() = bits;
311 *self.edge_len.write().unwrap() = len;
312 }
313}
314
315#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
321enum ChildKey {
322 Left,
323 Right,
324}
325
326#[repr(C, align(64))]
327pub struct LockFreeRadixNode {
328 edge_bits: RwLock<[u8; 16]>,
329 edge_len: RwLock<usize>,
330 metadata: RwLock<Option<Metadata>>,
331 prefix: RwLock<Option<IpNetwork>>,
332 children: DashMap<ChildKey, Arc<dyn Node>>,
334}
335
336impl LockFreeRadixNode {
337 pub fn new() -> Self {
338 Self {
339 edge_bits: RwLock::new([0u8; 16]),
340 edge_len: RwLock::new(0),
341 metadata: RwLock::new(None),
342 prefix: RwLock::new(None),
343 children: DashMap::new(),
344 }
345 }
346}
347
348impl Default for LockFreeRadixNode {
349 fn default() -> Self {
350 Self::new()
351 }
352}
353
354impl Node for LockFreeRadixNode {
355 fn bit(&self) -> Option<u8> {
356 None
357 }
358
359 fn left(&self) -> Option<Arc<dyn Node>> {
360 self.children
361 .get(&ChildKey::Left)
362 .map(|r| r.value().clone())
363 }
364
365 fn right(&self) -> Option<Arc<dyn Node>> {
366 self.children
367 .get(&ChildKey::Right)
368 .map(|r| r.value().clone())
369 }
370
371 fn metadata(&self) -> Option<Metadata> {
372 self.metadata.read().unwrap().clone()
373 }
374
375 fn prefix(&self) -> Option<IpNetwork> {
376 *self.prefix.read().unwrap()
377 }
378
379 fn set_left(&self, node: Option<Arc<dyn Node>>) {
380 match node {
381 Some(n) => {
382 self.children.insert(ChildKey::Left, n);
383 }
384 None => {
385 self.children.remove(&ChildKey::Left);
386 }
387 }
388 }
389
390 fn set_right(&self, node: Option<Arc<dyn Node>>) {
391 match node {
392 Some(n) => {
393 self.children.insert(ChildKey::Right, n);
394 }
395 None => {
396 self.children.remove(&ChildKey::Right);
397 }
398 }
399 }
400
401 fn set_metadata(&self, metadata: Metadata) {
402 *self.metadata.write().unwrap() = Some(metadata);
403 }
404
405 fn clear_metadata(&self) {
406 *self.metadata.write().unwrap() = None;
407 }
408
409 fn set_bit(&self, _bit: u8) {}
410
411 fn set_prefix(&self, prefix: IpNetwork) {
412 *self.prefix.write().unwrap() = Some(prefix);
413 }
414
415 fn edge_bits(&self) -> Option<[u8; 16]> {
416 Some(self.edge_bits.read().unwrap().clone())
417 }
418
419 fn edge_len(&self) -> Option<usize> {
420 Some(*self.edge_len.read().unwrap())
421 }
422
423 fn set_edge(&self, bits: [u8; 16], len: usize) {
424 *self.edge_bits.write().unwrap() = bits;
425 *self.edge_len.write().unwrap() = len;
426 }
427}