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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
use crate::linkedlist::{HEAD_INDEX, Index, LinkedList, TAIL_INDEX};
use crate::{IsEqual, IsLessThan};
use std::fmt::Debug;
impl<K, V> LinkedList<K, V>
where
K: Debug + Clone + IsLessThan,
V: Debug + Clone,
{
/// Removes node at current index, updating the index to point to the next valid position
/// Returns the key-value pair if removal was successful.
/// Moves cursor current to the old prev value if existed. Else pick old next index.
pub fn remove_by_index(&mut self, cursor_index: &mut Option<Index>) -> Option<(K, V)> {
let lookup_index = (*cursor_index)?.0;
let prev = self._prev(lookup_index);
if prev == HEAD_INDEX {
*cursor_index = Some(Index(self._forward(lookup_index)))
} else {
*cursor_index = Some(Index(prev));
}
self.remove_at_(lookup_index)
}
#[inline(always)]
/// Remove a node by key
/// Returns the value of the removed node if found
pub fn remove(&mut self, key: &K) -> Option<(K, V)> {
if let Some(pos) = self.sequential_find_position_before_(key, HEAD_INDEX) {
let index = self._forward(pos);
if unsafe {
let node = &self.nodes[index];
dbg_assert!(node.kv.is_some());
node.kv.as_ref().unwrap_unchecked().0.is_equal(key)
} {
return self.remove_at_(index);
}
}
None
}
/// Remove a node by key
/// Returns the value of the removed node if found
fn remove_at_(&mut self, index: usize) -> Option<(K, V)> {
#[cfg(feature = "linkedlist_midpoint")]
let is_midpoint = self.mid_point == Some(index);
let prev_pos = self._prev(index);
let next_pos = self.nodes[index].forward;
if prev_pos == HEAD_INDEX {
self.head = next_pos;
} else {
self.nodes[prev_pos].forward = next_pos;
}
if next_pos == TAIL_INDEX {
self.tail = prev_pos;
} else {
self.nodes[next_pos].prev = prev_pos;
}
let rv = unsafe {
let kv = self.nodes[index].kv.take();
dbg_assert!(kv.is_some());
kv.unwrap_unchecked()
};
Self::release_index_(index, &mut self.nodes, &mut self.free_index_pool);
#[cfg(feature = "linkedlist_midpoint")]
// Update midpoint if needed
// Case 1: List is now empty
if self.is_empty() {
self.mid_point = None;
self.mid_point_delta = 0;
}
// Case 2: The removed node was the midpoint
else if is_midpoint {
// We need to select a new midpoint
if next_pos != TAIL_INDEX && prev_pos == HEAD_INDEX {
// If prev is the head, we can only move right
self.mid_point = Some(next_pos);
self.mid_point_delta -= 1;
#[cfg(feature = "console_debug")]
println!(
"mid node {:?} removed, new mid:{:?},#{}, ",
rv.0,
self.get_k_at_(next_pos).unwrap(),
next_pos
);
} else if prev_pos != HEAD_INDEX && next_pos == TAIL_INDEX {
// If next is the tail, we can only move left
self.mid_point = Some(prev_pos);
self.mid_point_delta += 1;
#[cfg(feature = "console_debug")]
println!(
"mid node {:?} removed, new mid:{:?},#{}, ",
rv.0,
self.get_k_at_(prev_pos).unwrap(),
prev_pos
);
} else if prev_pos != HEAD_INDEX && next_pos != TAIL_INDEX {
// Both directions are available, choose based on balancing the list
if self.mid_point_delta < 0 {
// List is right-heavy, prefer moving left to balance
self.mid_point = Some(prev_pos);
self.mid_point_delta += 1;
#[cfg(feature = "console_debug")]
println!(
"mid node {:?} removed, list was right-heavy, new mid:{:?},#{}, ",
rv.0,
self.get_k_at_(prev_pos).unwrap(),
prev_pos
);
} else {
// List is balanced or left-heavy, prefer moving right
self.mid_point = Some(next_pos);
self.mid_point_delta -= 1;
#[cfg(feature = "console_debug")]
println!(
"mid node {:?} removed, list was balanced/left-heavy, new mid:{:?},#{}, ",
rv.0,
self.get_k_at_(next_pos).unwrap(),
next_pos
);
}
} else {
// Fallback - this should rarely happen if the implementation is correct
self.mid_point = None;
self.mid_point_delta = 0;
}
}
// Case 3: The removed node affects the balance but wasn't the midpoint
else if let Some(mid_idx) = self.mid_point {
// Use key comparison to determine if the deleted node was before or after midpoint
let mid_key = unsafe {
let node = &self.nodes[mid_idx];
dbg_assert!(node.kv.is_some());
&node.kv.as_ref().unwrap_unchecked().0
};
if mid_key.is_less_than(&rv.0) {
// The deleted node was after the midpoint (right side contracted)
self.mid_point_delta -= 1;
// If delta is too negative, we need to move midpoint left
if self.mid_point_delta < -1 {
let prev_mid = self.nodes[mid_idx].prev;
if prev_mid != HEAD_INDEX {
self.mid_point = Some(prev_mid);
// Don't reset delta, just adjust it
// Moving left should increase delta by 1
self.mid_point_delta += 2;
#[cfg(feature = "console_debug")]
println!(
"node {:?} removed, old mid was less. moved mid to prev:{:?},#{}, ",
rv.0,
self.get_k_at_(prev_mid).unwrap(),
prev_mid
);
}
}
} else {
// The deleted node was before the midpoint (left side contracted)
self.mid_point_delta += 1;
// If delta is too positive, we need to move midpoint right
if self.mid_point_delta > 1 {
let next_mid = self.nodes[mid_idx].forward;
if next_mid != TAIL_INDEX {
self.mid_point = Some(next_mid);
// Don't reset delta, just adjust it
// Moving right should decrease delta by 1
self.mid_point_delta -= 2;
#[cfg(feature = "console_debug")]
println!(
"node {:?} removed, old mid was greater. moved mid to next:{:?},#{} ",
rv.0,
self.get_k_at_(next_mid).unwrap(),
next_mid
);
}
}
}
}
Some(rv)
}
/// Clear the LinkedList
pub fn clear(&mut self) {
// Start from the first element after head
let mut current = self.next_pos_(HEAD_INDEX);
// Traverse the list and free each node
while let Some(idx) = current {
if idx == TAIL_INDEX {
break;
}
// Get the next node before we clear the current one
let next = self.next_pos_(idx);
self.nodes[idx].kv = None;
// Free the node by setting it to None and adding its index to the free pool
Self::release_index_(idx, &mut self.nodes, &mut self.free_index_pool);
// Move to the next node
current = next;
}
// Reset head and tail nodes without recreating them
self.head = TAIL_INDEX;
// Reset prev pointer to point to head
self.tail = HEAD_INDEX;
#[cfg(feature = "linkedlist_midpoint")]
{
self.mid_point = None;
}
}
}