netidx_value/
array.rs

1use crate::Value;
2use anyhow::{bail, Result};
3use bytes::{Buf, BufMut};
4use netidx_core::{
5    pack::{decode_varint, encode_varint, varint_len, Pack, PackError, MAX_VEC},
6    pool::{pooled::PArc, RawPool, RawPoolable, WeakPool},
7};
8use seq_macro::seq;
9use serde::{de::Visitor, ser::SerializeSeq, Deserialize, Serialize};
10use smallvec::{smallvec, SmallVec};
11use std::{
12    borrow::Borrow,
13    fmt::Debug,
14    hash::{Hash, Hasher},
15    mem::ManuallyDrop,
16    ops::{Bound, Deref, RangeBounds},
17    ptr,
18    slice::Iter,
19    sync::LazyLock,
20};
21use triomphe::{Arc, ThinArc};
22
23const MAX_LEN: usize = 128;
24
25const POOLS: [LazyLock<RawPool<ValArrayBase>>; 129] = seq!(N in 0..=128 {
26    [
27        #(LazyLock::new(|| RawPool::new(32 * (MAX_LEN + 1 - N), 1)),)*
28    ]
29});
30
31const SPOOL: LazyLock<RawPool<PArc<Option<ValArraySlice>>>> =
32    LazyLock::new(|| RawPool::new(1024, 64));
33
34fn get_by_size(len: usize) -> ValArrayBase {
35    if len <= MAX_LEN {
36        let pool = &POOLS[len];
37        match pool.try_take() {
38            Some(t) => t,
39            None => ValArrayBase::new_with_len(pool.downgrade(), len),
40        }
41    } else {
42        ValArrayBase::new_with_len(WeakPool::new(), len)
43    }
44}
45
46#[derive(Debug, Clone)]
47pub struct ValArrayBase(ManuallyDrop<ThinArc<WeakPool<Self>, Value>>);
48
49impl Drop for ValArrayBase {
50    fn drop(&mut self) {
51        if ThinArc::strong_count(&self.0) > 1 {
52            unsafe { ManuallyDrop::drop(&mut self.0) }
53        } else {
54            match self.0.header.header.upgrade() {
55                Some(pool) => pool.insert(unsafe { ptr::read(self) }),
56                None => unsafe { ManuallyDrop::drop(&mut self.0) },
57            }
58        }
59    }
60}
61
62impl Deref for ValArrayBase {
63    type Target = [Value];
64
65    fn deref(&self) -> &Self::Target {
66        &self.0.slice
67    }
68}
69
70unsafe impl RawPoolable for ValArrayBase {
71    fn capacity(&self) -> usize {
72        1
73    }
74
75    fn empty(pool: WeakPool<Self>) -> Self {
76        let t = ThinArc::from_header_and_iter(pool, [].into_iter());
77        ValArrayBase(ManuallyDrop::new(t))
78    }
79
80    fn reset(&mut self) {
81        self.0.with_arc_mut(|t| {
82            // reset can only be called if the arc is unique
83            for v in Arc::get_mut(t).unwrap().slice.iter_mut() {
84                // ensure we drop any allocated values
85                *v = Value::Bool(false);
86            }
87        })
88    }
89
90    fn really_drop(self) {
91        let mut t = ManuallyDrop::new(self);
92        unsafe { ManuallyDrop::drop(&mut t.0) }
93    }
94}
95
96impl ValArrayBase {
97    fn new_with_len(pool: WeakPool<Self>, len: usize) -> Self {
98        let iter = (0..len).map(|_| Value::Bool(false));
99        let t = ThinArc::from_header_and_iter(pool, iter);
100        Self(ManuallyDrop::new(t))
101    }
102}
103
104impl PartialEq for ValArrayBase {
105    fn eq(&self, other: &Self) -> bool {
106        self.0.slice == other.0.slice
107    }
108}
109
110impl Eq for ValArrayBase {}
111
112impl PartialOrd for ValArrayBase {
113    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
114        self.0.slice.partial_cmp(&other.0.slice)
115    }
116}
117
118impl Ord for ValArrayBase {
119    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
120        self.0.slice.cmp(&other.0.slice)
121    }
122}
123
124impl Hash for ValArrayBase {
125    fn hash<H: Hasher>(&self, state: &mut H) {
126        self.0.slice.hash(state)
127    }
128}
129
130#[derive(Debug, Clone)]
131pub struct ValArraySlice {
132    base: ValArrayBase,
133    start: Bound<usize>,
134    end: Bound<usize>,
135}
136
137impl Deref for ValArraySlice {
138    type Target = [Value];
139
140    fn deref(&self) -> &Self::Target {
141        &self.base[(self.start, self.end)]
142    }
143}
144
145#[derive(Debug, Clone)]
146pub enum ValArray {
147    Base(ValArrayBase),
148    Slice(PArc<Option<ValArraySlice>>),
149}
150
151impl Deref for ValArray {
152    type Target = [Value];
153
154    fn deref(&self) -> &Self::Target {
155        match self {
156            Self::Base(a) => &*a,
157            Self::Slice(s) => match &**s {
158                Some(s) => &*s,
159                None => &[],
160            },
161        }
162    }
163}
164
165impl PartialEq for ValArray {
166    fn eq(&self, other: &Self) -> bool {
167        &self[..] == &other[..]
168    }
169}
170
171impl Eq for ValArray {}
172
173impl PartialOrd for ValArray {
174    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
175        self[..].partial_cmp(&other[..])
176    }
177}
178
179impl Ord for ValArray {
180    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
181        self[..].cmp(&other[..])
182    }
183}
184
185impl Hash for ValArray {
186    fn hash<H: Hasher>(&self, state: &mut H) {
187        self[..].hash(state)
188    }
189}
190
191impl Borrow<[Value]> for ValArray {
192    fn borrow(&self) -> &[Value] {
193        &*self
194    }
195}
196
197impl From<Vec<Value>> for ValArray {
198    fn from(v: Vec<Value>) -> Self {
199        Self::from_iter_exact(v.into_iter())
200    }
201}
202
203impl<const S: usize> From<SmallVec<[Value; S]>> for ValArray {
204    fn from(v: SmallVec<[Value; S]>) -> Self {
205        Self::from_iter_exact(v.into_iter())
206    }
207}
208
209impl<const S: usize> From<[Value; S]> for ValArray {
210    fn from(v: [Value; S]) -> Self {
211        Self::from_iter_exact(v.into_iter())
212    }
213}
214
215impl From<&[Value]> for ValArray {
216    fn from(v: &[Value]) -> Self {
217        Self::from_iter_exact(v.into_iter().map(|v| v.clone()))
218    }
219}
220
221impl FromIterator<Value> for ValArray {
222    fn from_iter<T: IntoIterator<Item = Value>>(iter: T) -> Self {
223        let mut tmp: SmallVec<[Value; 64]> = smallvec![];
224        for v in iter {
225            tmp.push(v);
226        }
227        Self::from_iter_exact(tmp.into_iter())
228    }
229}
230
231impl Into<Vec<Value>> for ValArray {
232    fn into(self) -> Vec<Value> {
233        let mut tmp = Vec::with_capacity(self.len());
234        for v in self.iter() {
235            tmp.push(v.clone());
236        }
237        tmp
238    }
239}
240
241impl<const S: usize> Into<SmallVec<[Value; S]>> for ValArray {
242    fn into(self) -> SmallVec<[Value; S]> {
243        let mut tmp = smallvec![];
244        for v in self.iter() {
245            tmp.push(v.clone())
246        }
247        tmp
248    }
249}
250
251pub struct OwnedValArrayIter {
252    pos: usize,
253    a: ValArray,
254}
255
256impl Iterator for OwnedValArrayIter {
257    type Item = Value;
258
259    fn next(&mut self) -> Option<Self::Item> {
260        let res = self.a.get(self.pos).map(|v| v.clone());
261        self.pos += 1;
262        res
263    }
264}
265
266impl IntoIterator for ValArray {
267    type IntoIter = OwnedValArrayIter;
268    type Item = Value;
269
270    fn into_iter(self) -> Self::IntoIter {
271        OwnedValArrayIter { pos: 0, a: self }
272    }
273}
274
275impl<'a> IntoIterator for &'a ValArray {
276    type IntoIter = Iter<'a, Value>;
277    type Item = &'a Value;
278
279    fn into_iter(self) -> Self::IntoIter {
280        self.iter()
281    }
282}
283
284impl ValArray {
285    pub fn from_iter_exact<I: Iterator<Item = Value> + ExactSizeIterator>(
286        iter: I,
287    ) -> Self {
288        let mut res = get_by_size(iter.len());
289        res.0.with_arc_mut(|res| {
290            let res = Arc::get_mut(res).unwrap();
291            for (i, v) in iter.enumerate() {
292                res.slice[i] = v;
293            }
294        });
295        Self::Base(res)
296    }
297
298    /// create a zero copy owned subslice of the array. Returns an
299    /// error if the subslice is out of bounds.
300    pub fn subslice<R: RangeBounds<usize>>(&self, r: R) -> Result<Self> {
301        fn check_bounds(
302            a: &ValArrayBase,
303            start: Bound<usize>,
304            end: Bound<usize>,
305        ) -> Result<()> {
306            let len = a.len();
307            match start {
308                Bound::Unbounded => (),
309                Bound::Excluded(i) => {
310                    if i > len - 1 {
311                        bail!("start index {i} out of bounds {len}")
312                    }
313                }
314                Bound::Included(i) => {
315                    if i > len {
316                        bail!("start index {i} out of bounds {len}")
317                    }
318                }
319            }
320            match end {
321                Bound::Unbounded => (),
322                Bound::Excluded(i) => {
323                    if i > len {
324                        bail!("end index {i} out of bounds {len}")
325                    }
326                }
327                Bound::Included(i) => {
328                    if i >= len {
329                        bail!("end index {i} out of bounds {len}")
330                    }
331                }
332            }
333            match (start, end) {
334                (
335                    Bound::Unbounded,
336                    Bound::Unbounded | Bound::Included(_) | Bound::Excluded(_),
337                )
338                | (Bound::Included(_) | Bound::Excluded(_), Bound::Unbounded) => (),
339                (Bound::Included(i), Bound::Included(j))
340                | (Bound::Excluded(i), Bound::Included(j))
341                | (Bound::Included(i), Bound::Excluded(j)) => {
342                    if j < i {
343                        bail!("array index starts at {i} but ends at {j}")
344                    }
345                }
346                (Bound::Excluded(i), Bound::Excluded(j)) => {
347                    if j <= i {
348                        bail!("array index starts at ex {i} but ends at ex {j}")
349                    }
350                }
351            }
352            Ok(())
353        }
354        match self {
355            Self::Base(a) => {
356                let (start, end) =
357                    (r.start_bound().map(|i| *i), r.end_bound().map(|i| *i));
358                let t = Some(ValArraySlice { base: a.clone(), start, end });
359                check_bounds(&a, start, end)?;
360                Ok(Self::Slice(PArc::new(&SPOOL, t)))
361            }
362            Self::Slice(s) => match &**s {
363                None => bail!("can't subslice an empty subslice"),
364                Some(s) => {
365                    let max_i = match s.end {
366                        Bound::Unbounded => s.base.len(),
367                        Bound::Excluded(i) => i,
368                        Bound::Included(i) => i,
369                    };
370                    let (start, end) =
371                        (r.start_bound().map(|i| *i), r.end_bound().map(|i| *i));
372                    match (start, end) {
373                        (Bound::Excluded(i), Bound::Excluded(j)) if j <= i => {
374                            bail!("negative size slice ex {i}, ex {j}")
375                        }
376                        (Bound::Included(i), Bound::Included(j)) if j < i => {
377                            bail!("negative size slice {i}, {j}")
378                        }
379                        (_, _) => (),
380                    }
381                    let (start_i, start_off, start) = match (s.start, start) {
382                        (Bound::Unbounded, Bound::Unbounded) => (0, 0, Bound::Unbounded),
383                        (Bound::Unbounded, Bound::Excluded(i)) => {
384                            if i >= max_i {
385                                bail!("slice start {i} is out of bounds {max_i}")
386                            }
387                            (i, i, Bound::Excluded(i))
388                        }
389                        (Bound::Unbounded, Bound::Included(i)) => {
390                            if i > max_i {
391                                bail!("slice start {i} is out of bounds {max_i}")
392                            }
393                            (i, i, Bound::Included(i))
394                        }
395                        (Bound::Excluded(i), Bound::Unbounded) => {
396                            (i, 0, Bound::Excluded(i))
397                        }
398                        (Bound::Excluded(i), Bound::Included(j)) => {
399                            let si = i + j;
400                            if si >= max_i {
401                                bail!("slice start {si} is out of bounds {max_i}")
402                            }
403                            (si, j, Bound::Excluded(si))
404                        }
405                        (Bound::Excluded(i), Bound::Excluded(j)) => {
406                            let si = i + j;
407                            if si >= max_i {
408                                bail!("slice start {si} is out of bounds {max_i}")
409                            }
410                            (si, j, Bound::Excluded(si))
411                        }
412                        (Bound::Included(i), Bound::Unbounded) => {
413                            (i, 0, Bound::Included(i))
414                        }
415                        (Bound::Included(i), Bound::Included(j)) => {
416                            let si = i + j;
417                            if si > max_i {
418                                bail!("slice start {si} is out of bounds {max_i}")
419                            }
420                            (si, j, Bound::Included(si))
421                        }
422                        (Bound::Included(i), Bound::Excluded(j)) => {
423                            let si = i + j;
424                            if si >= max_i {
425                                bail!("slice start {si} is out of bounds {max_i}")
426                            }
427                            (si, j, Bound::Excluded(si))
428                        }
429                    };
430                    let end = match (s.end, end) {
431                        (Bound::Unbounded, Bound::Unbounded) => Bound::Unbounded,
432                        (Bound::Unbounded, Bound::Excluded(j)) => {
433                            if j < start_off {
434                                bail!("array index starts at {start_off} but ends at {j}")
435                            }
436                            let r = start_i + (j - start_off);
437                            if r > max_i {
438                                bail!("slice end {r} is out of bounds {max_i}")
439                            }
440                            Bound::Excluded(r)
441                        }
442                        (Bound::Unbounded, Bound::Included(j)) => {
443                            if j < start_off {
444                                bail!("array index starts at {start_off} but ends at {j}")
445                            }
446                            let r = start_i + (j - start_off);
447                            if r > max_i {
448                                bail!("slice end {r} is out of bounds {max_i}")
449                            }
450                            Bound::Included(r)
451                        }
452                        (Bound::Excluded(i), Bound::Unbounded) => Bound::Excluded(i),
453                        (Bound::Excluded(i), Bound::Excluded(j)) => {
454                            if j < start_off {
455                                bail!("array index starts at {start_off} but ends at {j}")
456                            }
457                            let r = start_i + (j - start_off);
458                            if r > i {
459                                bail!("slice end {r} is out of bounds {i}")
460                            }
461                            Bound::Excluded(r)
462                        }
463                        (Bound::Excluded(i), Bound::Included(j)) => {
464                            if j < start_off {
465                                bail!("array index starts at {start_off} but ends at {j}")
466                            }
467                            let r = start_i + (j - start_off);
468                            if r >= i {
469                                bail!("slice end {r} is out of bounds {i}")
470                            }
471                            Bound::Included(r)
472                        }
473                        (Bound::Included(i), Bound::Unbounded) => Bound::Included(i),
474                        (Bound::Included(i), Bound::Excluded(j)) => {
475                            if j < start_off {
476                                bail!("array index starts at {start_off} but ends at {j}")
477                            }
478                            let r = start_i + (j - start_off);
479                            if r > i + 1 {
480                                bail!("slice end {r} is out of bounds {i}")
481                            }
482                            Bound::Excluded(r)
483                        }
484                        (Bound::Included(i), Bound::Included(j)) => {
485                            if j < start_off {
486                                bail!("array index starts at {start_off} but ends at {j}")
487                            }
488                            let r = start_i + (j - start_off);
489                            if r > i {
490                                bail!("slice end {r} is out of bound {i}")
491                            }
492                            Bound::Included(r)
493                        }
494                    };
495                    let t = Some(ValArraySlice { base: s.base.clone(), start, end });
496                    Ok(Self::Slice(PArc::new(&SPOOL, t)))
497                }
498            },
499        }
500    }
501}
502
503impl Serialize for ValArray {
504    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
505    where
506        S: serde::Serializer,
507    {
508        let mut seq = serializer.serialize_seq(Some(self.len()))?;
509        for v in &**self {
510            seq.serialize_element(v)?
511        }
512        seq.end()
513    }
514}
515
516struct ValArrayVisitor;
517
518impl<'de> Visitor<'de> for ValArrayVisitor {
519    type Value = ValArray;
520
521    fn expecting(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
522        write!(f, "expecting a sequence")
523    }
524
525    fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
526    where
527        A: serde::de::SeqAccess<'de>,
528    {
529        let mut tmp: SmallVec<[Value; 64]> = smallvec![];
530        while let Some(v) = seq.next_element()? {
531            tmp.push(v);
532        }
533        Ok(ValArray::from(tmp))
534    }
535}
536
537impl<'de> Deserialize<'de> for ValArray {
538    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
539    where
540        D: serde::Deserializer<'de>,
541    {
542        deserializer.deserialize_seq(ValArrayVisitor)
543    }
544}
545
546impl Pack for ValArray {
547    fn encoded_len(&self) -> usize {
548        self.iter()
549            .fold(varint_len(self.len() as u64), |len, t| len + Pack::encoded_len(t))
550    }
551
552    fn encode(&self, buf: &mut impl BufMut) -> Result<(), PackError> {
553        encode_varint(self.len() as u64, buf);
554        for t in &**self {
555            Pack::encode(t, buf)?
556        }
557        Ok(())
558    }
559
560    fn decode(buf: &mut impl Buf) -> Result<Self, PackError> {
561        let elts = decode_varint(buf)? as usize;
562        if elts > MAX_VEC {
563            return Err(PackError::TooBig);
564        }
565        let mut data = get_by_size(elts);
566        data.0.with_arc_mut(|data| {
567            let data = Arc::get_mut(data).unwrap();
568            for i in 0..elts {
569                data.slice[i] = Pack::decode(buf)?;
570            }
571            Ok(())
572        })?;
573        Ok(Self::Base(data))
574    }
575}
netidx_value/array.rs

netidx_value/
array.rs
