hopper_core/collections/
sorted_vec.rs

1//! Sorted bounded dynamic array with O(log n) binary search.
2//!
3//! Wire layout (identical to FixedVec):
4//! ```text
5//! [count: u32 LE][element 0][element 1]...[element capacity-1]
6//! ```
7//!
8//! Elements are maintained in sorted order. Requires `T: Ord + Pod + FixedLayout`.
9//! Binary search costs ~3-15 CU per lookup vs ~50-500 CU linear scan (depending on N).
10
11use crate::account::{FixedLayout, Pod};
12use hopper_runtime::error::ProgramError;
13
14const HEADER_SIZE: usize = 4;
15
16/// Sorted bounded dynamic array -- zero-copy with O(log n) binary search.
17///
18/// Elements are kept in ascending order. Insert is O(n) (shift right),
19/// remove is O(n) (shift left), search is O(log n).
20pub struct SortedVec<'a, T: Pod + FixedLayout + Ord> {
21    data: &'a mut [u8],
22    _phantom: core::marker::PhantomData<T>,
23}
24
25impl<'a, T: Pod + FixedLayout + Ord> SortedVec<'a, T> {
26    /// Overlay a SortedVec on a mutable byte slice.
27    #[inline]
28    pub fn from_bytes(data: &'a mut [u8]) -> Result<Self, ProgramError> {
29        if data.len() < HEADER_SIZE {
30            return Err(ProgramError::AccountDataTooSmall);
31        }
32        Ok(Self {
33            data,
34            _phantom: core::marker::PhantomData,
35        })
36    }
37
38    /// Current number of elements.
39    #[inline(always)]
40    pub fn len(&self) -> usize {
41        u32::from_le_bytes([self.data[0], self.data[1], self.data[2], self.data[3]]) as usize
42    }
43
44    /// Maximum capacity.
45    #[inline(always)]
46    pub fn capacity(&self) -> usize {
47        (self.data.len() - HEADER_SIZE) / T::SIZE
48    }
49
50    /// Is the vec empty?
51    #[inline(always)]
52    pub fn is_empty(&self) -> bool {
53        self.len() == 0
54    }
55
56    /// Is the vec at capacity?
57    #[inline(always)]
58    pub fn is_full(&self) -> bool {
59        self.len() >= self.capacity()
60    }
61
62    #[inline(always)]
63    fn set_len(&mut self, len: usize) {
64        let bytes = (len as u32).to_le_bytes();
65        self.data[0] = bytes[0];
66        self.data[1] = bytes[1];
67        self.data[2] = bytes[2];
68        self.data[3] = bytes[3];
69    }
70
71    #[inline(always)]
72    fn element_offset(index: usize) -> usize {
73        HEADER_SIZE + index * T::SIZE
74    }
75
76    /// Read element at index by copy.
77    #[inline]
78    fn read_at(&self, index: usize) -> T {
79        let offset = Self::element_offset(index);
80        // SAFETY: Caller ensures index < len. T: Pod, alignment-1.
81        unsafe { core::ptr::read_unaligned(self.data.as_ptr().add(offset) as *const T) }
82    }
83
84    /// Write element at index.
85    #[inline]
86    fn write_at(&mut self, index: usize, value: T) {
87        let offset = Self::element_offset(index);
88        // SAFETY: Caller ensures index < capacity. T: Pod.
89        unsafe { core::ptr::write_unaligned(self.data.as_mut_ptr().add(offset) as *mut T, value) }
90    }
91
92    /// Binary search for a value. Returns `Ok(index)` if found, or
93    /// `Err(insert_index)` where `insert_index` is where the value would go.
94    #[inline]
95    pub fn binary_search(&self, target: &T) -> Result<usize, usize> {
96        let len = self.len();
97        if len == 0 {
98            return Err(0);
99        }
100        let mut lo: usize = 0;
101        let mut hi: usize = len;
102        while lo < hi {
103            let mid = lo + (hi - lo) / 2;
104            let elem = self.read_at(mid);
105            match elem.cmp(target) {
106                core::cmp::Ordering::Less => lo = mid + 1,
107                core::cmp::Ordering::Equal => return Ok(mid),
108                core::cmp::Ordering::Greater => hi = mid,
109            }
110        }
111        Err(lo)
112    }
113
114    /// Check if the value exists in the vec. O(log n).
115    #[inline]
116    pub fn contains(&self, target: &T) -> bool {
117        self.binary_search(target).is_ok()
118    }
119
120    /// Get element at index (bounds-checked).
121    #[inline]
122    pub fn get(&self, index: usize) -> Result<T, ProgramError> {
123        if index >= self.len() {
124            return Err(ProgramError::InvalidArgument);
125        }
126        Ok(self.read_at(index))
127    }
128
129    /// Insert a value in sorted position. O(n) due to shift.
130    /// Returns the index where it was inserted.
131    #[inline]
132    pub fn insert(&mut self, value: T) -> Result<usize, ProgramError> {
133        let len = self.len();
134        if len >= self.capacity() {
135            return Err(ProgramError::AccountDataTooSmall);
136        }
137        let insert_idx = match self.binary_search(&value) {
138            Ok(idx) => idx, // Duplicate -- insert at same position (stable)
139            Err(idx) => idx,
140        };
141        // Shift elements right from insert_idx to len-1
142        if insert_idx < len {
143            let src_offset = Self::element_offset(insert_idx);
144            let dst_offset = Self::element_offset(insert_idx + 1);
145            let byte_count = (len - insert_idx) * T::SIZE;
146            // SAFETY: Non-overlapping copy within bounds.
147            unsafe {
148                core::ptr::copy(
149                    self.data.as_ptr().add(src_offset),
150                    self.data.as_mut_ptr().add(dst_offset),
151                    byte_count,
152                );
153            }
154        }
155        self.write_at(insert_idx, value);
156        self.set_len(len + 1);
157        Ok(insert_idx)
158    }
159
160    /// Insert a value only if it doesn't already exist.
161    /// Returns `Ok(index)` on successful insert, or `Err(existing_index)` if duplicate.
162    #[inline]
163    pub fn insert_unique(&mut self, value: T) -> Result<usize, usize> {
164        match self.binary_search(&value) {
165            Ok(existing) => Err(existing),
166            Err(insert_idx) => {
167                let len = self.len();
168                if len >= self.capacity() {
169                    return Err(usize::MAX); // Signal capacity full
170                }
171                if insert_idx < len {
172                    let src_offset = Self::element_offset(insert_idx);
173                    let dst_offset = Self::element_offset(insert_idx + 1);
174                    let byte_count = (len - insert_idx) * T::SIZE;
175                    // SAFETY: This block is part of Hopper's audited zero-copy/backend boundary; surrounding checks and caller contracts uphold the required raw-pointer, layout, and aliasing invariants.
176                    unsafe {
177                        core::ptr::copy(
178                            self.data.as_ptr().add(src_offset),
179                            self.data.as_mut_ptr().add(dst_offset),
180                            byte_count,
181                        );
182                    }
183                }
184                self.write_at(insert_idx, value);
185                self.set_len(len + 1);
186                Ok(insert_idx)
187            }
188        }
189    }
190
191    /// Remove value at index (shift left). O(n).
192    #[inline]
193    pub fn remove(&mut self, index: usize) -> Result<T, ProgramError> {
194        let len = self.len();
195        if index >= len {
196            return Err(ProgramError::InvalidArgument);
197        }
198        let removed = self.read_at(index);
199        // Shift elements left
200        if index + 1 < len {
201            let src_offset = Self::element_offset(index + 1);
202            let dst_offset = Self::element_offset(index);
203            let byte_count = (len - index - 1) * T::SIZE;
204            // SAFETY: This block is part of Hopper's audited zero-copy/backend boundary; surrounding checks and caller contracts uphold the required raw-pointer, layout, and aliasing invariants.
205            unsafe {
206                core::ptr::copy(
207                    self.data.as_ptr().add(src_offset),
208                    self.data.as_mut_ptr().add(dst_offset),
209                    byte_count,
210                );
211            }
212        }
213        // Zero the vacated last slot
214        let last_offset = Self::element_offset(len - 1);
215        for b in &mut self.data[last_offset..last_offset + T::SIZE] {
216            *b = 0;
217        }
218        self.set_len(len - 1);
219        Ok(removed)
220    }
221
222    /// Remove a specific value by searching for it first. O(n).
223    #[inline]
224    pub fn remove_value(&mut self, value: &T) -> Result<T, ProgramError> {
225        match self.binary_search(value) {
226            Ok(idx) => self.remove(idx),
227            Err(_) => Err(ProgramError::InvalidArgument),
228        }
229    }
230
231    /// Returns the minimum element (first). O(1).
232    #[inline]
233    pub fn min(&self) -> Result<T, ProgramError> {
234        if self.is_empty() {
235            return Err(ProgramError::InvalidArgument);
236        }
237        Ok(self.read_at(0))
238    }
239
240    /// Returns the maximum element (last). O(1).
241    #[inline]
242    pub fn max(&self) -> Result<T, ProgramError> {
243        let len = self.len();
244        if len == 0 {
245            return Err(ProgramError::InvalidArgument);
246        }
247        Ok(self.read_at(len - 1))
248    }
249}
250
251#[cfg(test)]
252mod tests {
253    use super::*;
254    use crate::abi::WireU64;
255
256    #[test]
257    fn sorted_vec_insert_and_search() {
258        let mut buf = [0u8; 4 + 8 * 8]; // capacity 8
259        let mut sv = SortedVec::<WireU64>::from_bytes(&mut buf).unwrap();
260
261        // Insert out of order
262        sv.insert(WireU64::new(50)).unwrap();
263        sv.insert(WireU64::new(10)).unwrap();
264        sv.insert(WireU64::new(30)).unwrap();
265        sv.insert(WireU64::new(20)).unwrap();
266        sv.insert(WireU64::new(40)).unwrap();
267
268        assert_eq!(sv.len(), 5);
269
270        // Should be sorted
271        assert_eq!(sv.get(0).unwrap().get(), 10);
272        assert_eq!(sv.get(1).unwrap().get(), 20);
273        assert_eq!(sv.get(2).unwrap().get(), 30);
274        assert_eq!(sv.get(3).unwrap().get(), 40);
275        assert_eq!(sv.get(4).unwrap().get(), 50);
276
277        // Binary search
278        assert!(sv.contains(&WireU64::new(30)));
279        assert!(!sv.contains(&WireU64::new(25)));
280        assert_eq!(sv.binary_search(&WireU64::new(30)), Ok(2));
281        assert_eq!(sv.binary_search(&WireU64::new(25)), Err(2));
282    }
283
284    #[test]
285    fn sorted_vec_min_max() {
286        let mut buf = [0u8; 4 + 8 * 4];
287        let mut sv = SortedVec::<WireU64>::from_bytes(&mut buf).unwrap();
288        sv.insert(WireU64::new(100)).unwrap();
289        sv.insert(WireU64::new(5)).unwrap();
290        sv.insert(WireU64::new(42)).unwrap();
291
292        assert_eq!(sv.min().unwrap().get(), 5);
293        assert_eq!(sv.max().unwrap().get(), 100);
294    }
295
296    #[test]
297    fn sorted_vec_remove() {
298        let mut buf = [0u8; 4 + 8 * 4];
299        let mut sv = SortedVec::<WireU64>::from_bytes(&mut buf).unwrap();
300        sv.insert(WireU64::new(10)).unwrap();
301        sv.insert(WireU64::new(20)).unwrap();
302        sv.insert(WireU64::new(30)).unwrap();
303
304        sv.remove_value(&WireU64::new(20)).unwrap();
305        assert_eq!(sv.len(), 2);
306        assert_eq!(sv.get(0).unwrap().get(), 10);
307        assert_eq!(sv.get(1).unwrap().get(), 30);
308    }
309
310    #[test]
311    fn sorted_vec_insert_unique() {
312        let mut buf = [0u8; 4 + 8 * 4];
313        let mut sv = SortedVec::<WireU64>::from_bytes(&mut buf).unwrap();
314        assert!(sv.insert_unique(WireU64::new(10)).is_ok());
315        assert!(sv.insert_unique(WireU64::new(20)).is_ok());
316        // Duplicate should fail
317        assert!(sv.insert_unique(WireU64::new(10)).is_err());
318        assert_eq!(sv.len(), 2);
319    }
320}
hopper_core/collections/sorted_vec.rs

hopper_core/collections/
sorted_vec.rs
