twizzler/collections/hachage/raw/
mod.rs

1use std::{
2    alloc::{AllocError, Layout},
3    marker::PhantomData,
4    ptr::NonNull,
5};
6
7use twizzler_abi::object::{MAX_SIZE, NULLPAGE_SIZE};
8
9use super::DefaultHashBuilder;
10use crate::{
11    alloc::Allocator,
12    collections::hachage::control::{Tag, TagSliceExt},
13    marker::{BaseType, Invariant},
14    ptr::{GlobalPtr, InvPtr, Ref, RefMut, RefSliceMut},
15    Result,
16};
17
18// todo figure out a better way to parameterize size
19// generic feels too clunky, so does a const usize
20#[derive(Default, Clone, Copy)]
21pub struct HashTableAlloc {}
22
23const MAX_ALIGNMENT: usize = 4096;
24// We need some leeway for aligning the data
25const MAX_SPACE: usize = MAX_SIZE - NULLPAGE_SIZE * 4 - MAX_ALIGNMENT;
26
27// We need to have a set group width since invariant pointers mean that computers that use SSE2 or
28// AVX512 can interpret the same hash table. 64 bytes is a good middle ground.
29const INVARIANT_GROUP_WIDTH: usize = 64;
30
31// This is a bit of a hack, but this assumes that the hash table is on a single object with no other
32// allocations on the object. So we know the size of the tag, and the layout provides information
33// on the data. However we do need to store the size, since Layout shows the total space of the
34// allocation and not just the size of data. Also we can't just feed the Layout for the data array
35// because we also want the hashtable to use other traditional allocators. Though this means this
36// yields a pointer that overlaps with a previous allocation.
37
38impl Allocator for HashTableAlloc {
39    fn alloc(
40        &self,
41        _layout: Layout,
42    ) -> std::result::Result<crate::ptr::GlobalPtr<u8>, std::alloc::AllocError> {
43        panic!("unsupported")
44    }
45
46    unsafe fn dealloc(&self, _ptr: crate::ptr::GlobalPtr<u8>, _layout: Layout) {}
47
48    unsafe fn realloc(
49        &self,
50        _ptr: GlobalPtr<u8>,
51        _layout: Layout,
52        _newsize: usize,
53    ) -> std::result::Result<GlobalPtr<u8>, AllocError> {
54        panic!("unsupported")
55    }
56}
57
58impl HashTableAlloc {
59    // This will return a pointer to the middle of the allocation, specifically the ptr right after
60    // the data portion or the first Tag
61    fn allocate(
62        &self,
63        table_layout: &TableLayout,
64        buckets: usize,
65    ) -> std::result::Result<crate::ptr::GlobalPtr<u8>, std::alloc::AllocError> {
66        assert!(buckets.is_power_of_two());
67        let (layout, _) = table_layout
68            .calculate_layout_for(buckets)
69            .ok_or(std::alloc::AllocError)?;
70        if layout.align() > MAX_ALIGNMENT {
71            return Err(std::alloc::AllocError);
72        }
73        // 1 for null page, 2 for metadata pages, 1 for base
74        if layout.size() > MAX_SPACE {
75            return Err(std::alloc::AllocError);
76        }
77        let offset = (MAX_SPACE / (table_layout.size + 1)) * table_layout.size;
78        let corrected_offset = offset + (MAX_ALIGNMENT - offset % MAX_ALIGNMENT);
79        let obj = twizzler_rt_abi::object::twz_rt_get_object_handle((self as *const Self).cast())
80            .unwrap();
81
82        Ok(GlobalPtr::new(
83            obj.id(),
84            (NULLPAGE_SIZE * 2 + corrected_offset) as u64,
85        ))
86    }
87}
88
89#[inline]
90#[allow(clippy::cast_possible_truncation)]
91fn h1(hash: u64) -> usize {
92    // On 32-bit platforms we simply ignore the higher hash bits.
93    hash as usize
94}
95
96#[derive(Copy, Clone)]
97struct TableLayout {
98    pub size: usize,
99    pub ctrl_align: usize,
100}
101
102impl TableLayout {
103    #[inline]
104    const fn new<T: Invariant>() -> Self {
105        let layout = Layout::new::<T>();
106        Self {
107            size: layout.size(),
108            ctrl_align: if layout.align() > INVARIANT_GROUP_WIDTH {
109                layout.align()
110            } else {
111                INVARIANT_GROUP_WIDTH
112            },
113        }
114    }
115
116    fn calculate_ctrl_offset(&self, buckets: usize) -> usize {
117        self.size * buckets + (self.ctrl_align - 1) & !(self.ctrl_align - 1)
118    }
119
120    #[inline]
121    fn calculate_layout_for(&self, buckets: usize) -> Option<(Layout, usize)> {
122        debug_assert!(buckets.is_power_of_two());
123
124        // TODO: fix this for regular allocators and do bounds checking
125        // maybe enforce a minimum element count?
126        // Well I guess we can just check it twice maybe.
127        // This calculates the nearest alignment value for buckets * self.size
128        let ctrl_offset = self.calculate_ctrl_offset(buckets);
129        let len = ctrl_offset + buckets + INVARIANT_GROUP_WIDTH;
130
131        Some((
132            unsafe { Layout::from_size_align_unchecked(len, self.ctrl_align) },
133            ctrl_offset,
134        ))
135    }
136}
137
138struct ProbeSeq {
139    pos: usize,
140}
141
142impl ProbeSeq {
143    fn move_next(&mut self, bucket_mask: usize) {
144        self.pos += 1;
145        self.pos &= bucket_mask
146    }
147}
148
149/// Returns the maximum effective capacity for the given bucket mask, taking
150/// the maximum load factor into account.
151#[inline]
152fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
153    if bucket_mask < 8 {
154        // For tables with 1/2/4/8 buckets, we always reserve one empty slot.
155        // Keep in mind that the bucket mask is one less than the bucket count.
156        bucket_mask
157    } else {
158        // For larger tables we reserve 12.5% of the slots as empty.
159        ((bucket_mask + 1) / 8) * 7
160    }
161}
162
163// To reduce the number of Ref.resolves() to ideally one per call of RawTable
164pub struct CarryCtx<'a> {
165    backing: Ref<'a, u8>,
166}
167
168pub struct CarryCtxMut<'a> {
169    backing: RefMut<'a, u8>,
170}
171
172pub trait Ctx {
173    fn base(&self) -> *const u8;
174
175    #[inline]
176    fn ctrl<'a>(&self, buckets: usize) -> &'a [Tag] {
177        unsafe { std::slice::from_raw_parts(self.base().cast::<Tag>(), buckets) }
178    }
179
180    #[inline]
181    fn bucket<'a, T>(&self, index: usize) -> &'a T {
182        unsafe { self.base().cast::<T>().sub(index + 1).as_ref_unchecked() }
183    }
184}
185
186pub trait CtxMut: Ctx {
187    fn base_mut(&self) -> *mut u8;
188
189    #[inline]
190    fn ctrl_mut(&self, buckets: usize) -> &mut [Tag] {
191        unsafe { std::slice::from_raw_parts_mut(self.base_mut().cast(), buckets) }
192    }
193
194    #[inline]
195    fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8 {
196        unsafe { self.base_mut().sub(size_of * (index + 1)) }
197    }
198
199    fn bucket_ref_mut<T>(&self, index: usize) -> &mut T {
200        unsafe {
201            self.base_mut()
202                .cast::<T>()
203                .sub(index + 1)
204                .as_mut_unchecked()
205        }
206    }
207}
208
209impl CarryCtx<'_> {
210    #[inline]
211    pub fn new(base: Ref<u8>) -> CarryCtx<'_> {
212        CarryCtx { backing: base }
213    }
214}
215
216impl CarryCtxMut<'_> {
217    #[inline]
218    pub fn new(base: RefMut<u8>) -> CarryCtxMut<'_> {
219        CarryCtxMut { backing: base }
220    }
221}
222
223impl Ctx for CarryCtx<'_> {
224    #[inline]
225    fn base(&self) -> *const u8 {
226        self.backing.raw()
227    }
228}
229
230impl Ctx for CarryCtxMut<'_> {
231    #[inline]
232    fn base(&self) -> *const u8 {
233        self.backing.raw().cast_const()
234    }
235}
236
237impl CtxMut for CarryCtxMut<'_> {
238    #[inline]
239    fn base_mut(&self) -> *mut u8 {
240        self.backing.raw()
241    }
242}
243
244pub struct RawTable<T: Invariant, S = DefaultHashBuilder, A: Allocator = HashTableAlloc> {
245    table: RawTableInner,
246    // I have to keep the hasher state otherwise the hashes won't be the same upon reload
247    hasher: S,
248    alloc: A,
249    _phantom: PhantomData<T>,
250}
251
252impl<T: Invariant, S, A: Allocator> BaseType for RawTable<T, S, A> {}
253
254impl<T: Invariant> RawTable<T, DefaultHashBuilder, HashTableAlloc> {
255    pub fn new() -> Self {
256        Self {
257            table: RawTableInner::new(),
258            hasher: DefaultHashBuilder::default(),
259            alloc: HashTableAlloc::default(),
260            _phantom: PhantomData,
261        }
262    }
263}
264
265impl<T: Invariant, S, A: Allocator> RawTable<T, S, A> {
266    const TABLE_LAYOUT: TableLayout = TableLayout::new::<T>();
267
268    pub fn hasher(&self) -> &S {
269        &self.hasher
270    }
271
272    pub fn allocator(&self) -> &A {
273        &self.alloc
274    }
275
276    pub fn len(&self) -> usize {
277        self.table.items
278    }
279
280    pub fn capacity(&self) -> usize {
281        self.table.growth_left
282    }
283
284    pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
285        Self {
286            table: RawTableInner::new(),
287            hasher,
288            alloc,
289            _phantom: PhantomData,
290        }
291    }
292
293    pub fn remove(
294        &mut self,
295        hash: u64,
296        mut eq: impl FnMut(&T) -> bool,
297        ctx: &impl CtxMut,
298    ) -> Option<T> {
299        match unsafe {
300            self.table
301                .find_inner(hash, &mut |index| eq(&self.bucket(index)), ctx)
302        } {
303            Some(bucket) => Some(unsafe {
304                let item = self.bucket(bucket).raw().read();
305                self.table.erase(bucket);
306                item
307            }),
308            None => None,
309        }
310    }
311
312    pub fn get(&self, hash: u64, mut eq: impl FnMut(&T) -> bool, ctx: &impl Ctx) -> Option<&T> {
313        unsafe {
314            let result = self
315                .table
316                .find_inner(hash, &mut |index| eq(ctx.bucket::<T>(index)), ctx);
317
318            match result {
319                Some(index) => Some(ctx.bucket(index)),
320                None => None,
321            }
322        }
323    }
324
325    pub fn get_mut<'a>(
326        &mut self,
327        hash: u64,
328        mut eq: impl FnMut(&T) -> bool,
329        ctx: &'a impl CtxMut,
330    ) -> Option<&'a mut T> {
331        unsafe {
332            let result = self
333                .table
334                .find_inner(hash, &mut |index| eq(ctx.bucket::<T>(index)), ctx);
335
336            match result {
337                Some(index) => Some(ctx.bucket_ref_mut(index)),
338                None => None,
339            }
340        }
341    }
342
343    pub fn clear(&mut self) {
344        if self.table.is_empty_singleton() {
345            return;
346        }
347        let mut ctrl = unsafe { self.table.ctrl_slice_mut() };
348
349        ctrl.fill_tag(Tag::EMPTY);
350        self.table.items = 0;
351    }
352
353    fn bucket(&self, index: usize) -> Ref<T> {
354        unsafe { self.table.bucket::<T>(index) }
355    }
356
357    pub fn carry_ctx(&self) -> CarryCtx {
358        CarryCtx::new(unsafe { self.table.ctrl.resolve() })
359    }
360
361    pub fn carry_ctx_mut<'a>(&self, base: &RefMut<'a, RawTable<T, S, A>>) -> CarryCtxMut<'a> {
362        CarryCtxMut::new(unsafe { base.table.ctrl.resolve_mut().owned() })
363    }
364
365    pub unsafe fn iter(&self) -> RawIter<T> {
366        self.table.iter()
367    }
368
369    pub unsafe fn backing(&self) -> Ref<u8> {
370        self.table.ctrl.resolve()
371    }
372
373    pub unsafe fn backing_mut(&mut self) -> RefMut<u8> {
374        self.table.ctrl.resolve_mut()
375    }
376}
377
378impl<T: Invariant, S> RawTable<T, S, HashTableAlloc> {
379    pub fn bootstrap(&mut self, capacity: usize) -> Result<()> {
380        unsafe {
381            self.table
382                .bootstrap(&self.alloc, capacity, &Self::TABLE_LAYOUT)
383        }
384    }
385
386    pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64, ctx: &impl CtxMut) {
387        if core::intrinsics::unlikely(additional > self.table.growth_left) {
388            self.reserve_rehash(additional, hasher, ctx).unwrap();
389        }
390    }
391
392    pub fn reserve_rehash(
393        &mut self,
394        additional: usize,
395        hasher: impl Fn(&T) -> u64,
396        ctx: &impl CtxMut,
397    ) -> Result<()> {
398        unsafe {
399            self.table.reserve_rehash_inner(
400                &self.alloc,
401                additional,
402                &|_table, index| hasher(&ctx.bucket(index)),
403                &Self::TABLE_LAYOUT,
404                None,
405                ctx,
406            )
407        }
408    }
409
410    pub unsafe fn resize(
411        &mut self,
412        capacity: usize,
413        hasher: impl Fn(&T) -> u64,
414        ctx: &impl CtxMut,
415    ) -> Result<()> {
416        self.table.resize_inner(
417            &self.alloc,
418            capacity,
419            &|_table, index| hasher(ctx.bucket(index)),
420            &Self::TABLE_LAYOUT,
421            ctx,
422        )
423    }
424
425    // Returns a reference to a slot or a candidate to insert
426    pub fn find_or_find_insert_slot(
427        &mut self,
428        hash: u64,
429        mut eq: impl FnMut(&T) -> bool,
430        hasher: impl Fn(&T) -> u64,
431        ctx: &impl CtxMut,
432    ) -> std::result::Result<Ref<T>, usize> {
433        // self.reserve() can change the invariant pointer (only when the hashtable is empty)
434        self.reserve(1, hasher, ctx);
435
436        unsafe {
437            match self.table.find_or_find_insert_slot_inner(
438                hash,
439                &mut |index| eq(ctx.bucket(index)),
440                ctx,
441            ) {
442                Ok(index) => Ok(self.bucket(index)),
443                Err(slot) => Err(slot),
444            }
445        }
446    }
447
448    #[inline]
449    pub unsafe fn insert_in_slot(&mut self, hash: u64, slot: usize, value: T, ctx: &impl CtxMut) {
450        {
451            let ctrl = ctx.ctrl_mut(self.table.buckets());
452            let old_ctrl = ctrl[slot];
453            self.table.growth_left -= usize::from(old_ctrl.special_is_empty());
454            ctrl[slot] = Tag::full(hash);
455            self.table.items += 1;
456        }
457
458        let bucket = ctx.bucket_ptr(slot, size_of::<T>()).cast::<T>();
459
460        *bucket = value;
461    }
462}
463
464#[derive(Debug)]
465pub struct RawTableInner {
466    ctrl: InvPtr<u8>,
467    bucket_mask: usize,
468    growth_left: usize,
469    items: usize,
470}
471
472impl RawTableInner {
473    pub fn new() -> Self {
474        Self {
475            ctrl: InvPtr::null(),
476            bucket_mask: 0,
477            growth_left: 0,
478            items: 0,
479        }
480    }
481
482    pub fn len(&self) -> usize {
483        self.items
484    }
485
486    pub fn buckets(&self) -> usize {
487        self.bucket_mask + 1
488    }
489
490    pub fn is_empty(&self) -> bool {
491        self.len() == 0
492    }
493
494    fn is_empty_singleton(&self) -> bool {
495        self.bucket_mask == 0
496    }
497}
498
499impl RawTableInner {
500    fn probe_seq(&self, hash: u64) -> ProbeSeq {
501        ProbeSeq {
502            pos: h1(hash) & self.bucket_mask,
503        }
504    }
505
506    unsafe fn find_or_find_insert_slot_inner(
507        &self,
508        hash: u64,
509        eq: &mut dyn FnMut(usize) -> bool,
510        ctx: &impl Ctx,
511    ) -> std::result::Result<usize, usize> {
512        let tag_hash = Tag::full(hash);
513        let mut probe_seq = self.probe_seq(hash);
514
515        let ctrl = ctx.ctrl(self.buckets());
516        loop {
517            let tag = ctrl[probe_seq.pos];
518
519            if tag.eq(&tag_hash) && eq(probe_seq.pos) {
520                return Ok(probe_seq.pos);
521            }
522
523            // If the tag is empty that means that the index couldn't be in subsequent elements
524            // since if the tag was deleted there's a still a change the element could be
525            // further down the line
526            if tag.is_special() && tag.special_is_empty() {
527                return Err(probe_seq.pos);
528            }
529
530            probe_seq.move_next(self.bucket_mask);
531        }
532    }
533
534    unsafe fn find_insert_slot(&self, hash: u64, ctx: &impl Ctx) -> usize {
535        let mut probe_seq = self.probe_seq(hash);
536        let ctrl_slice = ctx.ctrl(self.buckets());
537        loop {
538            let tag = ctrl_slice[probe_seq.pos];
539            if tag.is_special() {
540                return probe_seq.pos;
541            }
542            probe_seq.move_next(self.bucket_mask);
543        }
544    }
545
546    unsafe fn find_inner(
547        &self,
548        hash: u64,
549        eq: &mut dyn FnMut(usize) -> bool,
550        ctx: &impl Ctx,
551    ) -> Option<usize> {
552        debug_assert!(!self.is_empty());
553
554        let tag_hash = Tag::full(hash);
555        let mut probe_seq = self.probe_seq(hash);
556        let ctrl_slice = ctx.ctrl(self.buckets());
557
558        loop {
559            let tag = ctrl_slice[probe_seq.pos];
560
561            if tag.eq(&tag_hash) && eq(probe_seq.pos) {
562                return Some(probe_seq.pos);
563            }
564
565            if tag.is_special() && tag.special_is_empty() {
566                return None;
567            }
568
569            probe_seq.move_next(self.bucket_mask);
570        }
571    }
572
573    unsafe fn reserve_rehash_inner(
574        &mut self,
575        alloc: &HashTableAlloc,
576        additional: usize,
577        hasher: &dyn Fn(&mut Self, usize) -> u64,
578        table_layout: &TableLayout,
579        drop: Option<unsafe fn(*mut u8)>,
580        ctx: &impl CtxMut,
581    ) -> Result<()> {
582        let new_items = self.items + additional;
583        let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
584        if new_items <= full_capacity / 2 {
585            self.rehash_in_place(hasher, table_layout.size, drop, ctx);
586        } else {
587            self.resize_inner(
588                alloc,
589                usize::max(new_items, full_capacity + 1),
590                hasher,
591                table_layout,
592                ctx,
593            )?
594        }
595
596        Ok(())
597    }
598
599    // to avoid unnecessary work between rehash_in_place and resize_inner
600    unsafe fn rehash_in_place(
601        &mut self,
602        hasher: &dyn Fn(&mut Self, usize) -> u64,
603        size_of: usize,
604        drop: Option<unsafe fn(*mut u8)>,
605        ctx: &impl CtxMut,
606    ) {
607        self.prepare_rehash_in_place(ctx);
608
609        self.rehash_in_place_inner(hasher, size_of, self.buckets(), drop, ctx);
610    }
611
612    unsafe fn rehash_in_place_inner(
613        &mut self,
614        hasher: &dyn Fn(&mut Self, usize) -> u64,
615        size_of: usize,
616        workable_buckets: usize,
617        _drop: Option<unsafe fn(*mut u8)>,
618        ctx: &impl CtxMut,
619    ) {
620        // since this is also called by resize inner, in that case we don't need to work on all the
621        // buckets just the area that may contain deleted entries.
622        let ctrl = ctx.ctrl_mut(self.buckets());
623
624        'outer: for i in 0..workable_buckets {
625            if ctrl[i] != Tag::DELETED {
626                continue;
627            }
628
629            let i_p = ctx.bucket_ptr(i, size_of);
630            'inner: loop {
631                let hash = hasher(self, i);
632
633                let new_i = self.find_insert_slot(hash, ctx);
634
635                if i == new_i {
636                    self.replace_ctrl_hash(new_i, hash, ctx);
637                    continue 'outer;
638                }
639
640                let new_i_p = ctx.bucket_ptr(new_i, size_of);
641
642                let prev_ctrl = self.replace_ctrl_hash(new_i, hash, ctx);
643                if prev_ctrl == Tag::EMPTY {
644                    ctrl[i] = Tag::EMPTY;
645                    std::ptr::copy_nonoverlapping(i_p, new_i_p, size_of);
646                    continue 'outer;
647                } else {
648                    debug_assert_eq!(prev_ctrl, Tag::DELETED);
649                    std::ptr::swap_nonoverlapping(i_p, new_i_p, size_of);
650                    continue 'inner;
651                }
652            }
653        }
654
655        self.growth_left = bucket_mask_to_capacity(self.bucket_mask) - self.items;
656    }
657
658    unsafe fn prepare_rehash_in_place(&mut self, ctx: &impl CtxMut) {
659        if self.is_empty() {
660            return;
661        }
662
663        let slice = ctx.ctrl_mut(self.buckets());
664        for i in 0..self.buckets() {
665            if slice[i].is_full() {
666                slice[i] = Tag::DELETED;
667            } else {
668                slice[i] = Tag::EMPTY;
669            }
670        }
671    }
672
673    unsafe fn bootstrap(
674        &mut self,
675        alloc: &HashTableAlloc,
676        capacity: usize,
677        table_layout: &TableLayout,
678    ) -> Result<()> {
679        let buckets = std::cmp::max((capacity * 8 / 7).next_power_of_two(), 8);
680
681        let global = alloc.allocate(table_layout, buckets)?;
682        self.ctrl = InvPtr::new(Ref::from_ptr(self), global)?;
683        self.bucket_mask = buckets - 1;
684        self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
685        self.items = 0;
686
687        self.ctrl_slice_mut().fill_empty();
688
689        Ok(())
690    }
691
692    // I'm using alloc instead of realloc here, making an assumption about how the allocator works
693    // but this gets me half the potential capacity of an object I need to do a rehash in place
694    // instead but with two different sizes on the same array?
695    // But once I create a sharding wrapper the amount a single object holds matters less.
696    // TODO: Redo this once a real allocation function is made
697    unsafe fn resize_inner(
698        &mut self,
699        alloc: &HashTableAlloc,
700        capacity: usize,
701        hasher: &dyn Fn(&mut Self, usize) -> u64,
702        table_layout: &TableLayout,
703        ctx: &impl CtxMut,
704    ) -> Result<()> {
705        debug_assert!(self.items <= capacity);
706
707        let old_buckets = self.buckets();
708
709        // To not waste work, we are preparing resize before we empty the tags to not operate on
710        // tags we know are empty Allocate the tags in place, and empty them out
711        let buckets = std::cmp::max((capacity * 8 / 7).next_power_of_two(), 8);
712        let global = alloc.allocate(table_layout, buckets)?;
713        if !self.is_empty_singleton() {
714            self.prepare_rehash_in_place(ctx);
715            let p = ctx.base_mut().add(self.buckets()).cast::<Tag>();
716            let slice = std::slice::from_raw_parts_mut(p, buckets - self.buckets());
717            slice.fill_empty();
718
719            self.bucket_mask = buckets - 1;
720            self.growth_left = bucket_mask_to_capacity(self.bucket_mask) - self.items;
721            self.rehash_in_place_inner(hasher, table_layout.size, old_buckets, None, ctx);
722        } else {
723            self.ctrl = InvPtr::new(Ref::from_ptr(self), global)?;
724            self.bucket_mask = buckets - 1;
725            self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
726            self.items = 0;
727
728            self.ctrl_slice_mut().fill_empty();
729        }
730
731        Ok(())
732    }
733
734    unsafe fn erase(&mut self, index: usize) {
735        self.set_ctrl(index, Tag::DELETED);
736        self.items -= 1;
737    }
738
739    unsafe fn bucket<T: Invariant>(&self, index: usize) -> Ref<T> {
740        unsafe { self.ctrl.resolve().cast::<T>().sub(index + 1) }
741    }
742
743    #[inline]
744    unsafe fn replace_ctrl_hash(&mut self, index: usize, hash: u64, ctx: &impl CtxMut) -> Tag {
745        let ctrl = ctx.ctrl_mut(self.buckets());
746        let prev_ctrl = ctrl[index];
747        ctrl[index] = Tag::full(hash);
748        prev_ctrl.to_owned()
749    }
750
751    #[inline]
752    unsafe fn set_ctrl(&mut self, index: usize, ctrl: Tag) {
753        self.ctrl_slice_mut()[index] = ctrl;
754    }
755
756    #[inline]
757    unsafe fn ctrl_slice_mut(&mut self) -> RefSliceMut<'_, Tag> {
758        let r = self.ctrl.resolve().cast::<Tag>().into_mut();
759        let slice = RefSliceMut::from_ref(r, self.buckets());
760        slice
761    }
762
763    // This function isn't responsible for guaranteeing mutability
764    unsafe fn iter<T: Invariant>(&self) -> RawIter<T> {
765        let data = self.ctrl.resolve().raw().cast::<T>().sub(1).cast_mut();
766        RawIter::new(
767            self.ctrl.resolve().raw().cast(),
768            NonNull::new(data).unwrap(),
769            self.buckets(),
770        )
771    }
772}
773
774// Assumes there exists a valid hashtable and object handle to it.
775// also that the underlying hashtable doesn't change size
776pub struct RawIter<T: Invariant> {
777    data: NonNull<T>,
778    ctrl: *const Tag,
779    top: *const Tag,
780}
781
782impl<T: Invariant> RawIter<T> {
783    pub(crate) unsafe fn new(ctrl: *const Tag, data: NonNull<T>, len: usize) -> RawIter<T> {
784        let end = ctrl.add(len);
785
786        Self {
787            data,
788            ctrl,
789            top: end,
790        }
791    }
792
793    pub(crate) unsafe fn next_impl(&mut self) -> Option<NonNull<T>> {
794        loop {
795            if self.ctrl >= self.top {
796                return None;
797            }
798
799            if (*self.ctrl).is_full() {
800                self.data = self.data.sub(1);
801                self.ctrl = self.ctrl.add(1);
802                return Some(self.data.add(1));
803            }
804            self.data = self.data.sub(1);
805            self.ctrl = self.ctrl.add(1);
806        }
807    }
808}
809
810impl<T: Invariant> Iterator for RawIter<T> {
811    type Item = NonNull<T>;
812
813    fn next(&mut self) -> Option<Self::Item> {
814        unsafe { self.next_impl() }
815    }
816}
twizzler/collections/hachage/raw/mod.rs

twizzler/collections/hachage/raw/
mod.rs
