qanglang_core/frontend/
node_array_arena.rs

1use crate::{
2    arena::{Arena, Index},
3    frontend::ast_node_arena::NodeId,
4};
5
6#[derive(Debug, Default, Clone, Copy, Eq, PartialEq, Hash)]
7pub struct NodeArrayId(Index);
8
9#[derive(Debug, Default, Clone, Copy, PartialEq)]
10struct NodeArrayChunk {
11    ids: [NodeId; 8],
12    size: usize,
13    next_chunk: Option<NodeArrayId>,
14}
15
16#[derive(Default, Clone, Debug)]
17pub struct NodeArrayArena {
18    node_ids: Arena<NodeArrayChunk>,
19}
20
21impl NodeArrayArena {
22    pub fn new() -> Self {
23        Self {
24            node_ids: Arena::new(),
25        }
26    }
27
28    pub fn create(&mut self) -> NodeArrayId {
29        let index = self.node_ids.insert(NodeArrayChunk {
30            ids: std::array::from_fn(|_| NodeId::default()),
31            size: 0,
32            next_chunk: None,
33        });
34
35        NodeArrayId(index)
36    }
37
38    pub fn push(&mut self, array_id: NodeArrayId, node_id: NodeId) {
39        let mut current_id = array_id;
40
41        loop {
42            let needs_new_chunk = {
43                let chunk = &mut self.node_ids[current_id.0];
44
45                if chunk.size < 8 {
46                    chunk.ids[chunk.size] = node_id;
47                    chunk.size += 1;
48                    return;
49                }
50
51                if let Some(next_id) = chunk.next_chunk {
52                    current_id = next_id;
53                    false
54                } else {
55                    true
56                }
57            };
58
59            if needs_new_chunk {
60                let new_chunk_id = self.create();
61                self.node_ids[current_id.0].next_chunk = Some(new_chunk_id);
62                current_id = new_chunk_id;
63            }
64        }
65    }
66
67    pub fn size(&self, array_id: NodeArrayId) -> usize {
68        let mut total_size = 0;
69        let mut current_id = Some(array_id);
70
71        while let Some(chunk_id) = current_id {
72            let chunk = &self.node_ids[chunk_id.0];
73            total_size += chunk.size;
74            current_id = chunk.next_chunk;
75        }
76
77        total_size
78    }
79
80    pub fn get_node_id_at(&self, array_id: NodeArrayId, index: usize) -> Option<NodeId> {
81        let mut current_id = Some(array_id);
82        let mut current_offset = 0;
83
84        while let Some(chunk_id) = current_id {
85            let chunk = &self.node_ids[chunk_id.0];
86
87            if index < current_offset + chunk.size {
88                let local_index = index - current_offset;
89                return Some(chunk.ids[local_index]);
90            }
91
92            current_offset += chunk.size;
93            current_id = chunk.next_chunk;
94        }
95
96        None
97    }
98}
qanglang_core/frontend/node_array_arena.rs

qanglang_core/frontend/
node_array_arena.rs
