netidx_value/
array.rs

1use crate::Value;
2use anyhow::{bail, Result};
3use bytes::{Buf, BufMut};
4use netidx_core::pack::{
5    decode_varint, encode_varint, varint_len, Pack, PackError, MAX_VEC,
6};
7use poolshark::{arc::TArc as PArc, Poolable, RawPool, RawPoolable, WeakPool};
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<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
145impl Poolable for ValArraySlice {
146    fn empty() -> Self {
147        Self { base: get_by_size(0), start: Bound::Unbounded, end: Bound::Unbounded }
148    }
149
150    fn capacity(&self) -> usize {
151        1
152    }
153
154    fn reset(&mut self) {
155        self.base = get_by_size(0);
156        self.start = Bound::Unbounded;
157        self.end = Bound::Unbounded
158    }
159}
160
161#[derive(Debug, Clone)]
162pub enum ValArray {
163    Base(ValArrayBase),
164    Slice(PArc<ValArraySlice>),
165}
166
167impl Deref for ValArray {
168    type Target = [Value];
169
170    fn deref(&self) -> &Self::Target {
171        match self {
172            Self::Base(a) => &*a,
173            Self::Slice(s) => &**s,
174        }
175    }
176}
177
178impl PartialEq for ValArray {
179    fn eq(&self, other: &Self) -> bool {
180        &self[..] == &other[..]
181    }
182}
183
184impl Eq for ValArray {}
185
186impl PartialOrd for ValArray {
187    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
188        self[..].partial_cmp(&other[..])
189    }
190}
191
192impl Ord for ValArray {
193    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
194        self[..].cmp(&other[..])
195    }
196}
197
198impl Hash for ValArray {
199    fn hash<H: Hasher>(&self, state: &mut H) {
200        self[..].hash(state)
201    }
202}
203
204impl Borrow<[Value]> for ValArray {
205    fn borrow(&self) -> &[Value] {
206        &*self
207    }
208}
209
210impl From<Vec<Value>> for ValArray {
211    fn from(v: Vec<Value>) -> Self {
212        Self::from_iter_exact(v.into_iter())
213    }
214}
215
216impl<const S: usize> From<SmallVec<[Value; S]>> for ValArray {
217    fn from(v: SmallVec<[Value; S]>) -> Self {
218        Self::from_iter_exact(v.into_iter())
219    }
220}
221
222impl<const S: usize> From<[Value; S]> for ValArray {
223    fn from(v: [Value; S]) -> Self {
224        Self::from_iter_exact(v.into_iter())
225    }
226}
227
228impl From<&[Value]> for ValArray {
229    fn from(v: &[Value]) -> Self {
230        Self::from_iter_exact(v.into_iter().map(|v| v.clone()))
231    }
232}
233
234impl FromIterator<Value> for ValArray {
235    fn from_iter<T: IntoIterator<Item = Value>>(iter: T) -> Self {
236        let mut tmp: SmallVec<[Value; 64]> = smallvec![];
237        for v in iter {
238            tmp.push(v);
239        }
240        Self::from_iter_exact(tmp.into_iter())
241    }
242}
243
244impl Into<Vec<Value>> for ValArray {
245    fn into(self) -> Vec<Value> {
246        let mut tmp = Vec::with_capacity(self.len());
247        for v in self.iter() {
248            tmp.push(v.clone());
249        }
250        tmp
251    }
252}
253
254impl<const S: usize> Into<SmallVec<[Value; S]>> for ValArray {
255    fn into(self) -> SmallVec<[Value; S]> {
256        let mut tmp = smallvec![];
257        for v in self.iter() {
258            tmp.push(v.clone())
259        }
260        tmp
261    }
262}
263
264pub struct OwnedValArrayIter {
265    pos: usize,
266    a: ValArray,
267}
268
269impl Iterator for OwnedValArrayIter {
270    type Item = Value;
271
272    fn next(&mut self) -> Option<Self::Item> {
273        let res = self.a.get(self.pos).map(|v| v.clone());
274        self.pos += 1;
275        res
276    }
277}
278
279impl IntoIterator for ValArray {
280    type IntoIter = OwnedValArrayIter;
281    type Item = Value;
282
283    fn into_iter(self) -> Self::IntoIter {
284        OwnedValArrayIter { pos: 0, a: self }
285    }
286}
287
288impl<'a> IntoIterator for &'a ValArray {
289    type IntoIter = Iter<'a, Value>;
290    type Item = &'a Value;
291
292    fn into_iter(self) -> Self::IntoIter {
293        self.iter()
294    }
295}
296
297impl ValArray {
298    pub fn from_iter_exact<I: Iterator<Item = Value> + ExactSizeIterator>(
299        iter: I,
300    ) -> Self {
301        let mut res = get_by_size(iter.len());
302        res.0.with_arc_mut(|res| {
303            let res = Arc::get_mut(res).unwrap();
304            for (i, v) in iter.enumerate() {
305                res.slice[i] = v;
306            }
307        });
308        Self::Base(res)
309    }
310
311    /// create a zero copy owned subslice of the array. Returns an
312    /// error if the subslice is out of bounds.
313    pub fn subslice<R: RangeBounds<usize>>(&self, r: R) -> Result<Self> {
314        fn check_bounds(
315            a: &ValArrayBase,
316            start: Bound<usize>,
317            end: Bound<usize>,
318        ) -> Result<()> {
319            let len = a.len();
320            match start {
321                Bound::Unbounded => (),
322                Bound::Excluded(i) => {
323                    if i > len - 1 {
324                        bail!("start index {i} out of bounds {len}")
325                    }
326                }
327                Bound::Included(i) => {
328                    if i > len {
329                        bail!("start index {i} out of bounds {len}")
330                    }
331                }
332            }
333            match end {
334                Bound::Unbounded => (),
335                Bound::Excluded(i) => {
336                    if i > len {
337                        bail!("end index {i} out of bounds {len}")
338                    }
339                }
340                Bound::Included(i) => {
341                    if i >= len {
342                        bail!("end index {i} out of bounds {len}")
343                    }
344                }
345            }
346            match (start, end) {
347                (
348                    Bound::Unbounded,
349                    Bound::Unbounded | Bound::Included(_) | Bound::Excluded(_),
350                )
351                | (Bound::Included(_) | Bound::Excluded(_), Bound::Unbounded) => (),
352                (Bound::Included(i), Bound::Included(j))
353                | (Bound::Excluded(i), Bound::Included(j))
354                | (Bound::Included(i), Bound::Excluded(j)) => {
355                    if j < i {
356                        bail!("array index starts at {i} but ends at {j}")
357                    }
358                }
359                (Bound::Excluded(i), Bound::Excluded(j)) => {
360                    if j <= i {
361                        bail!("array index starts at ex {i} but ends at ex {j}")
362                    }
363                }
364            }
365            Ok(())
366        }
367        match self {
368            Self::Base(a) => {
369                let (start, end) =
370                    (r.start_bound().map(|i| *i), r.end_bound().map(|i| *i));
371                let t = ValArraySlice { base: a.clone(), start, end };
372                check_bounds(&a, start, end)?;
373                Ok(Self::Slice(PArc::new(&SPOOL, t)))
374            }
375            Self::Slice(s) => {
376                let max_i = match s.end {
377                    Bound::Unbounded => s.base.len(),
378                    Bound::Excluded(i) => i,
379                    Bound::Included(i) => i,
380                };
381                let (start, end) =
382                    (r.start_bound().map(|i| *i), r.end_bound().map(|i| *i));
383                match (start, end) {
384                    (Bound::Excluded(i), Bound::Excluded(j)) if j <= i => {
385                        bail!("negative size slice ex {i}, ex {j}")
386                    }
387                    (Bound::Included(i), Bound::Included(j)) if j < i => {
388                        bail!("negative size slice {i}, {j}")
389                    }
390                    (_, _) => (),
391                }
392                let (start_i, start_off, start) = match (s.start, start) {
393                    (Bound::Unbounded, Bound::Unbounded) => (0, 0, Bound::Unbounded),
394                    (Bound::Unbounded, Bound::Excluded(i)) => {
395                        if i >= max_i {
396                            bail!("slice start {i} is out of bounds {max_i}")
397                        }
398                        (i, i, Bound::Excluded(i))
399                    }
400                    (Bound::Unbounded, Bound::Included(i)) => {
401                        if i > max_i {
402                            bail!("slice start {i} is out of bounds {max_i}")
403                        }
404                        (i, i, Bound::Included(i))
405                    }
406                    (Bound::Excluded(i), Bound::Unbounded) => (i, 0, Bound::Excluded(i)),
407                    (Bound::Excluded(i), Bound::Included(j)) => {
408                        let si = i + j;
409                        if si >= max_i {
410                            bail!("slice start {si} is out of bounds {max_i}")
411                        }
412                        (si, j, Bound::Excluded(si))
413                    }
414                    (Bound::Excluded(i), Bound::Excluded(j)) => {
415                        let si = i + j;
416                        if si >= max_i {
417                            bail!("slice start {si} is out of bounds {max_i}")
418                        }
419                        (si, j, Bound::Excluded(si))
420                    }
421                    (Bound::Included(i), Bound::Unbounded) => (i, 0, Bound::Included(i)),
422                    (Bound::Included(i), Bound::Included(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::Included(si))
428                    }
429                    (Bound::Included(i), Bound::Excluded(j)) => {
430                        let si = i + j;
431                        if si >= max_i {
432                            bail!("slice start {si} is out of bounds {max_i}")
433                        }
434                        (si, j, Bound::Excluded(si))
435                    }
436                };
437                let end = match (s.end, end) {
438                    (Bound::Unbounded, Bound::Unbounded) => Bound::Unbounded,
439                    (Bound::Unbounded, Bound::Excluded(j)) => {
440                        if j < start_off {
441                            bail!("array index starts at {start_off} but ends at {j}")
442                        }
443                        let r = start_i + (j - start_off);
444                        if r > max_i {
445                            bail!("slice end {r} is out of bounds {max_i}")
446                        }
447                        Bound::Excluded(r)
448                    }
449                    (Bound::Unbounded, Bound::Included(j)) => {
450                        if j < start_off {
451                            bail!("array index starts at {start_off} but ends at {j}")
452                        }
453                        let r = start_i + (j - start_off);
454                        if r > max_i {
455                            bail!("slice end {r} is out of bounds {max_i}")
456                        }
457                        Bound::Included(r)
458                    }
459                    (Bound::Excluded(i), Bound::Unbounded) => Bound::Excluded(i),
460                    (Bound::Excluded(i), Bound::Excluded(j)) => {
461                        if j < start_off {
462                            bail!("array index starts at {start_off} but ends at {j}")
463                        }
464                        let r = start_i + (j - start_off);
465                        if r > i {
466                            bail!("slice end {r} is out of bounds {i}")
467                        }
468                        Bound::Excluded(r)
469                    }
470                    (Bound::Excluded(i), Bound::Included(j)) => {
471                        if j < start_off {
472                            bail!("array index starts at {start_off} but ends at {j}")
473                        }
474                        let r = start_i + (j - start_off);
475                        if r >= i {
476                            bail!("slice end {r} is out of bounds {i}")
477                        }
478                        Bound::Included(r)
479                    }
480                    (Bound::Included(i), Bound::Unbounded) => Bound::Included(i),
481                    (Bound::Included(i), Bound::Excluded(j)) => {
482                        if j < start_off {
483                            bail!("array index starts at {start_off} but ends at {j}")
484                        }
485                        let r = start_i + (j - start_off);
486                        if r > i + 1 {
487                            bail!("slice end {r} is out of bounds {i}")
488                        }
489                        Bound::Excluded(r)
490                    }
491                    (Bound::Included(i), Bound::Included(j)) => {
492                        if j < start_off {
493                            bail!("array index starts at {start_off} but ends at {j}")
494                        }
495                        let r = start_i + (j - start_off);
496                        if r > i {
497                            bail!("slice end {r} is out of bound {i}")
498                        }
499                        Bound::Included(r)
500                    }
501                };
502                let t = ValArraySlice { base: s.base.clone(), start, end };
503                Ok(Self::Slice(PArc::new(&SPOOL, t)))
504            }
505        }
506    }
507}
508
509impl Serialize for ValArray {
510    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
511    where
512        S: serde::Serializer,
513    {
514        let mut seq = serializer.serialize_seq(Some(self.len()))?;
515        for v in &**self {
516            seq.serialize_element(v)?
517        }
518        seq.end()
519    }
520}
521
522struct ValArrayVisitor;
523
524impl<'de> Visitor<'de> for ValArrayVisitor {
525    type Value = ValArray;
526
527    fn expecting(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
528        write!(f, "expecting a sequence")
529    }
530
531    fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
532    where
533        A: serde::de::SeqAccess<'de>,
534    {
535        let mut tmp: SmallVec<[Value; 64]> = smallvec![];
536        while let Some(v) = seq.next_element()? {
537            tmp.push(v);
538        }
539        Ok(ValArray::from(tmp))
540    }
541}
542
543impl<'de> Deserialize<'de> for ValArray {
544    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
545    where
546        D: serde::Deserializer<'de>,
547    {
548        deserializer.deserialize_seq(ValArrayVisitor)
549    }
550}
551
552impl Pack for ValArray {
553    fn encoded_len(&self) -> usize {
554        self.iter()
555            .fold(varint_len(self.len() as u64), |len, t| len + Pack::encoded_len(t))
556    }
557
558    fn encode(&self, buf: &mut impl BufMut) -> Result<(), PackError> {
559        encode_varint(self.len() as u64, buf);
560        for t in &**self {
561            Pack::encode(t, buf)?
562        }
563        Ok(())
564    }
565
566    fn decode(buf: &mut impl Buf) -> Result<Self, PackError> {
567        let elts = decode_varint(buf)? as usize;
568        if elts > MAX_VEC {
569            return Err(PackError::TooBig);
570        }
571        let mut data = get_by_size(elts);
572        data.0.with_arc_mut(|data| {
573            let data = Arc::get_mut(data).unwrap();
574            for i in 0..elts {
575                data.slice[i] = Pack::decode(buf)?;
576            }
577            Ok(())
578        })?;
579        Ok(Self::Base(data))
580    }
581}
netidx_value/array.rs

netidx_value/
array.rs
