1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//! HNSW Layer implementation.
//!
//! A single layer in the HNSW hierarchy containing node adjacency lists.
use parking_lot::RwLock;
/// Unique identifier for a node in the graph.
pub type NodeId = usize;
/// A single layer in the HNSW hierarchy.
#[derive(Debug)]
pub struct Layer {
/// Adjacency list: node_id -> list of neighbor node_ids
pub(crate) neighbors: Vec<RwLock<Vec<NodeId>>>,
}
impl Layer {
/// Creates a new layer with the given capacity.
pub(crate) fn new(capacity: usize) -> Self {
Self {
neighbors: (0..capacity).map(|_| RwLock::new(Vec::new())).collect(),
}
}
/// Ensures the layer has capacity for the given node_id.
pub(crate) fn ensure_capacity(&mut self, node_id: NodeId) {
while self.neighbors.len() <= node_id {
self.neighbors.push(RwLock::new(Vec::new()));
}
}
/// Gets the neighbors of a node.
#[allow(dead_code)] // Reason: Used in tests (layer_tests, graph_tests) for adjacency verification
#[inline]
pub(crate) fn get_neighbors(&self, node_id: NodeId) -> Vec<NodeId> {
if node_id < self.neighbors.len() {
self.neighbors[node_id].read().clone()
} else {
Vec::new()
}
}
/// Runs a closure with immutable access to a node's adjacency list under a read lock.
#[inline]
pub(crate) fn with_neighbors<R>(
&self,
node_id: NodeId,
f: impl FnOnce(&[NodeId]) -> R,
) -> Option<R> {
if node_id < self.neighbors.len() {
let guard = self.neighbors[node_id].read();
Some(f(&guard))
} else {
None
}
}
/// Sets the neighbors for a node.
#[inline]
pub(crate) fn set_neighbors(&self, node_id: NodeId, neighbors: Vec<NodeId>) {
if node_id < self.neighbors.len() {
*self.neighbors[node_id].write() = neighbors;
}
}
/// Mutates the neighbors for a node in-place under a single write lock.
#[inline]
pub(crate) fn with_neighbors_mut<R>(
&self,
node_id: NodeId,
f: impl FnOnce(&mut Vec<NodeId>) -> R,
) -> Option<R> {
if node_id < self.neighbors.len() {
let mut guard = self.neighbors[node_id].write();
Some(f(&mut guard))
} else {
None
}
}
/// Adds a neighbor to a node's adjacency list.
#[allow(dead_code)] // Reason: Used in tests for graph construction verification
pub(super) fn add_neighbor(&self, node_id: NodeId, neighbor: NodeId) {
if node_id < self.neighbors.len() {
self.neighbors[node_id].write().push(neighbor);
}
}
/// Remaps all neighbor IDs using the provided old-to-new mapping.
///
/// After graph reordering, node IDs change. This method updates every
/// neighbor reference in the layer to use the new IDs, and reorders the
/// adjacency lists themselves so that slot `new_id` contains the neighbors
/// of the node that was formerly at `old_id`.
pub(crate) fn remap_ids(&mut self, old_to_new: &[usize]) {
let count = old_to_new.len();
// Phase 1: Remap neighbor IDs within each adjacency list.
for lock in &self.neighbors {
let mut neighbors = lock.write();
for id in neighbors.iter_mut() {
if *id < count {
*id = old_to_new[*id];
}
}
}
// Phase 2: Reorder the adjacency lists themselves.
// Extract all lists (releases write locks), then apply the old→new
// permutation in-place via cycle decomposition so that slot new_id
// ends up with the list that was at old_id — without allocating a
// second full-size Vec<Vec<NodeId>>.
let mut extracted: Vec<Vec<NodeId>> = self
.neighbors
.iter()
.map(|lock| std::mem::take(&mut *lock.write()))
.collect();
// Build inverse mapping: new_to_old[new_id] = old_id, so the
// cycle-decomposition below can be driven forward ("output slot i
// receives element from slot new_to_old[i]").
let n = count.min(extracted.len());
let mut new_to_old: Vec<usize> = (0..n).collect();
for (old, &new) in old_to_new.iter().enumerate() {
if old < extracted.len() && new < n {
new_to_old[new] = old;
}
}
// Apply permutation to the first `n` slots in-place.
for i in 0..n {
let mut j = i;
while new_to_old[j] != i {
let k = new_to_old[j];
extracted.swap(j, k);
new_to_old[j] = j;
j = k;
}
new_to_old[j] = j;
}
// Write back all slots (slots >= n were already cleared by mem::take).
for (i, lock) in self.neighbors.iter().enumerate() {
*lock.write() = std::mem::take(&mut extracted[i]);
}
}
}