<commit_before>const POINTERS_IN_NODE: u64 = disk::SECTOR_SIZE / page::POINTER_SIZE;

struct Array<T> {
    root: page::Pointer,
    len: u64,
    _phantom: PhantomData<T>,
}

impl Array<T> {
    fn depth(&self) -> u64 {
        64 - self.len.leading_zeros() as u64
    }

    fn capacity(&self) -> u64 {
        1 << self.depth()
    }

    fn is_leaf(&self) -> bool {
        self.len <= POINTERS_IN_NODE
    }

    fn full_child() -> u64 {
        self.capacity() / POINTERS_IN_NODE
    }

    fn is_full() -> bool {
        self.len == self.capacity()
    }

    fn get_ptr(&self, fs: &fs::State, n: u8) -> Result<page::Pointer, alloc::Error> {
        let buf = fs.read(root)?;
        Ok(little_endian::read(&buf[n * page::POINTER_SIZE..]))
    }

    fn get_child(&self, fs: &fs::State, n: u8) -> Result<Array<T>, alloc::Error> {
        let depth = self.depth();

        Array {
            root: self.get_ptr(fs, n),
            len: if n == POINTERS_IN_NODE - 1 {
                self.len - self.full_child() * POINTERS_IN_NODE
            } else {
                self.full_child()
            },
            _phatom: PhantomData,
        }
    }

    fn get_leaf(&self, fs: &fs::State, mut idx: u64) -> Result<Array<T>, alloc::Error> {
        let mut node = self;
        while !node.is_leaf() {
            idx = idx / node.full_child();
            node = node.get(fs, idx)?;
        }

        Ok(node)
    }

    fn get(&self, fs: &fs::State, idx: u64) -> Result<Option<page::Pointer>, alloc::Error> {
        if idx < self.len {
            if self.len == 1 {
                Ok(Some(self.ptr))
            } else {
                Ok(Some(self.get_leaf(fs, idx)?.get_ptr(idx % POINTERS_IN_NODE)?))
            }
        } else {
            Ok(None)
        }
    }

    fn write<I>(&self, fs: &fs::State, idx: u64, arr: I) -> Result<(), alloc::Error>
        where I: ExactSizeIterator + Iterator<Item = page::Pointer> {
        unimplemented!();
    }

    fn push(&mut self, fs: &fs::State, ptr: page::Pointer) -> Result<(), alloc::Error> {
        if self.len == 0 {
            self.root = ptr;
        } else if self.is_full() {
            let mut buf = disk::SectorBuf::default();
            little_endian::write(self.ptr, &mut buf);
            little_endian::write(&mut buf[page::POINTER_SIZE..], ptr);

            self.ptr = fs.alloc(buf, "array node")?;
        } else {
            let leaf = self.get_leaf(fs, idx)?;
            let buf = fs.read(leaf.ptr)?;

            little_endian::write(&mut buf[page::POINTER_SIZE * (idx % POINTERS_IN_NODE)..], ptr);
        }

        self.len += 1;
    }

    fn pop(&mut self)
}

impl<T: Object + From<page::Pointer>> Object {
    fn gc_visit(&self, fs: &fs::State) -> Result<(), alloc::Error> {
        // TODO: This recursion can be very deep and potentially lead to stack overflow.
        // TODO: This should run in parallel.

        // We make sure that the tree isn't empty. If it is, we have nothing to traverse.
        if self.len != 0 {
            if self.len == 1 {
                // This node is a leaf, so we cast the pointer into an object and traverse it.
                fs.visit(T::from(self.root))?;
            } else {
                // Set the root as reachable.
                fs.set_reachable(self.root)?;
                // Go over the pointers in the root and visit the children.
                for i in 0..self.len / self.full_child() {
                    fs.visit(self.get_child(i)?);
                }
            }
        }<commit_msg>Use suffix trees to store arrays on-disk (WIP).<commit_after>const POINTERS_IN_NODE: u64 = disk::SECTOR_SIZE / page::POINTER_SIZE;

struct Array<T> {
    root: page::Pointer,
    len: u64,
    _phantom: PhantomData<T>,
}

impl Array<T> {
    fn is_leaf(&self) -> bool {
        self.len <= POINTERS_IN_NODE
    }

    fn for_each<F>(&self, fs: &fs::State, range: Range, f: F) -> Result<(), alloc::Error>
        where F: Fn(usize, page::Pointer) -> Result<(), alloc::Error> {
        self.for_each_idx(fs, range.start, range, f)
    }

    fn for_each_idx<F>(&self, fs: &fs::State, idx: usize, range: Range, f: F) -> Result<(), alloc::Error>
        where F: Fn(usize, page::Pointer) -> Result<(), alloc::Error> {
        if self.is_leaf() {
            let buf = fs.read(self.root)?;
            for i in range {
                f(idx + i, little_endian::read(&buf[i * page::POINTER_SIZE..]))?;
            }
        } else {
            let max_child = (self.len + POINTERS_IN_NODE / 2) / POINTERS_IN_NODE;

            self.for_each_idx(idx, range.start..cmp::min(range.end, range.start + POINTERS_IN_NODE), f)?;

            for i in (POINTERS_IN_NODE..range.end).step_by(max_child) {
                self.for_each_idx()
            }
        }
    }
}

impl<T: Object + From<page::Pointer>> Object {
    fn gc_visit(&self, fs: &fs::State) -> Result<(), alloc::Error> {
{'fraction_non_alphanumeric': 0.15428339423467316, 'fraction_numerical': 0.007105156313438896, 'mean_word_length': 1.9102185469580626, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4078506', 'n_tokens_mistral': 1688, 'n_tokens_neox': 1631, 'n_words': 387}