Skip to main content

radixip/node/
compressed.rs

1//!  (Patricia) radix trie node implementations.
2//!
3//! Unlike un nodes which store a single `bit`, Patricia nodes
4//! store an `edge_bits: [u8;16]` and `edge_len: usize` representing a
5//! multi-bit path segment. This collapses non-branching chains of bits
6//! into a single node, giving O(k) lookups where k is the number of
7//! branching points rather than the full prefix length.
8//!
9//! Four concurrency variants are provided (mirroring un):
10//!
11//! - [`NormalRadixNode`]   — RwLock on all fields  
12//! - [`AtomicRadixNode`]   — AtomicU8 bit + RwLock for edge/children  
13//! - [`PaddedRadixNode`]   — Cache-line padded Patricia node  
14//! - [`LockFreeRadixNode`] — DashMap children for lock-free read throughput
15
16use 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//
27//  NORMAL NODE  (RwLock on every field)
28//
29
30#[derive(Default)]
31#[repr(C, align(64))]
32pub struct NormalRadixNode {
33    /// Bit-string for the edge leading *into* this node (MSB-first, packed).
34    edge_bits: RwLock<[u8; 16]>,
35    /// Number of valid bits in `edge_bits` (may be < edge_bits.len()*8).
36    edge_len: RwLock<usize>,
37    /// Terminal metadata stored when this node represents a real prefix.
38    metadata: RwLock<Option<Metadata>>,
39    /// The IP network prefix that produced this node.
40    prefix: RwLock<Option<IpNetwork>>,
41    /// Left child  (next routing bit == 0).
42    left: RwLock<Option<Arc<dyn Node>>>,
43    /// Right child (next routing bit == 1).
44    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    // Shared methods
55
56    /// Not meaningful for Patricia nodes; always returns `None`.
57    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    /// Not used by Patricia trees; no-op.
94    fn set_bit(&self, _bit: u8) {}
95
96    fn set_prefix(&self, prefix: IpNetwork) {
97        *self.prefix.write().unwrap() = Some(prefix);
98    }
99
100    // -node extensions
101
102    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//
117//  ATOMIC RADIX NODE
118// (AtomicU8 encodes edge_len up to 254; RwLock for the bit-vector and children)
119//
120
121#[repr(C, align(64))]
122pub struct AtomicRadixNode {
123    /// Encodes edge_len: 0 = "empty/root", 1..=254 = actual length, 255 = overflow sentinel.
124    /// For edge lengths ≥ 255 we fall back to the RwLock below.
125    atomic_edge_len: AtomicU8,
126    edge_bits: RwLock<[u8; 16]>,
127    edge_len_overflow: RwLock<usize>, // used only when edge_len >= 255
128    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            // Overflow case: read from the RwLock
207            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            // Mark overflow and store in RwLock
217            self.atomic_edge_len.store(255, Ordering::Release);
218            *self.edge_len_overflow.write().unwrap() = len;
219        }
220    }
221}
222
223//
224//  PADDED RADIX NODE  (Cache-line padded Patricia node)
225//
226
227#[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//
316//  LOCK-FREE RADIX NODE  (DashMap children + RwLock for edge data)
317//
318
319/// Key enum for the DashMap children store.
320#[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    /// Lock-free child store: at most 2 entries (Left, Right).
333    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}