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

netidx_value/
array.rs
