|
| 1 | +// Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +// or more contributor license agreements. See the NOTICE file |
| 3 | +// distributed with this work for additional information |
| 4 | +// regarding copyright ownership. The ASF licenses this file |
| 5 | +// to you under the Apache License, Version 2.0 (the |
| 6 | +// "License"); you may not use this file except in compliance |
| 7 | +// with the License. You may obtain a copy of the License at |
| 8 | +// |
| 9 | +// http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +// |
| 11 | +// Unless required by applicable law or agreed to in writing, |
| 12 | +// software distributed under the License is distributed on an |
| 13 | +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +// KIND, either express or implied. See the License for the |
| 15 | +// specific language governing permissions and limitations |
| 16 | +// under the License. |
| 17 | + |
| 18 | +//! [`BatchedVec`] — a Vec-like structure that stores elements in |
| 19 | +//! fixed-size batches for efficient batch-at-a-time emission. |
| 20 | +
|
| 21 | +use std::fmt::Debug; |
| 22 | +use std::mem::size_of; |
| 23 | + |
| 24 | +/// A Vec-like container that stores elements in fixed-size batches. |
| 25 | +/// |
| 26 | +/// Indexed by a flat `usize` which is decomposed into |
| 27 | +/// `(batch_index, offset)` via simple division/modulo on `batch_size`. |
| 28 | +/// |
| 29 | +/// Each inner batch is always exactly `batch_size` elements (except |
| 30 | +/// possibly the last one during growth). Emission of a single batch |
| 31 | +/// is O(1) via [`Self::take_batch`]. |
| 32 | +#[derive(Debug)] |
| 33 | +pub struct BatchedVec<T> { |
| 34 | + batches: Vec<Vec<T>>, |
| 35 | + /// log2(batch_size) — used for bit-shift decomposition |
| 36 | + batch_shift: u32, |
| 37 | + /// batch_size - 1 — used as bitmask for offset extraction |
| 38 | + batch_mask: usize, |
| 39 | + len: usize, |
| 40 | +} |
| 41 | + |
| 42 | +impl<T: Clone> BatchedVec<T> { |
| 43 | + pub fn new(batch_size: usize) -> Self { |
| 44 | + assert!(batch_size > 0 && batch_size.is_power_of_two(), |
| 45 | + "batch_size must be a power of two, got {batch_size}"); |
| 46 | + Self { |
| 47 | + batches: Vec::new(), |
| 48 | + batch_shift: batch_size.trailing_zeros(), |
| 49 | + batch_mask: batch_size - 1, |
| 50 | + len: 0, |
| 51 | + } |
| 52 | + } |
| 53 | + |
| 54 | + #[inline] |
| 55 | + fn batch_size(&self) -> usize { |
| 56 | + 1 << self.batch_shift |
| 57 | + } |
| 58 | + |
| 59 | + #[inline] |
| 60 | + fn decompose(&self, index: usize) -> (usize, usize) { |
| 61 | + (index >> self.batch_shift, index & self.batch_mask) |
| 62 | + } |
| 63 | + |
| 64 | + pub fn len(&self) -> usize { |
| 65 | + self.len |
| 66 | + } |
| 67 | + |
| 68 | + pub fn is_empty(&self) -> bool { |
| 69 | + self.len == 0 |
| 70 | + } |
| 71 | + |
| 72 | + /// Ensure capacity for at least `total` elements, filling new |
| 73 | + /// slots with `default_value`. |
| 74 | + pub fn ensure_capacity(&mut self, total: usize, default_value: T) { |
| 75 | + if total <= self.len { |
| 76 | + return; |
| 77 | + } |
| 78 | + |
| 79 | + let batch_size = self.batch_size(); |
| 80 | + |
| 81 | + // Fill current last batch up to batch_size before adding new ones |
| 82 | + if let Some(last) = self.batches.last_mut() { |
| 83 | + let can_add = batch_size - last.len(); |
| 84 | + let need = total - self.len; |
| 85 | + let add = can_add.min(need); |
| 86 | + if add > 0 { |
| 87 | + last.resize(last.len() + add, default_value.clone()); |
| 88 | + self.len += add; |
| 89 | + } |
| 90 | + } |
| 91 | + |
| 92 | + // Add new batches as needed |
| 93 | + while self.len < total { |
| 94 | + let batch_len = (total - self.len).min(batch_size); |
| 95 | + let mut batch = Vec::with_capacity(batch_len); |
| 96 | + batch.resize(batch_len, default_value.clone()); |
| 97 | + self.batches.push(batch); |
| 98 | + self.len += batch_len; |
| 99 | + } |
| 100 | + } |
| 101 | + |
| 102 | + /// # Safety |
| 103 | + /// |
| 104 | + /// `index` must be in bounds (< self.len). |
| 105 | + #[inline] |
| 106 | + pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T { |
| 107 | + let (batch, offset) = self.decompose(index); |
| 108 | + self.batches |
| 109 | + .get_unchecked_mut(batch) |
| 110 | + .get_unchecked_mut(offset) |
| 111 | + } |
| 112 | + |
| 113 | + /// Number of batches (including a possible partial last batch). |
| 114 | + pub fn num_batches(&self) -> usize { |
| 115 | + self.batches.len() |
| 116 | + } |
| 117 | + |
| 118 | + /// Take one batch by index, leaving an empty Vec in its place. |
| 119 | + /// This is O(1). |
| 120 | + pub fn take_batch(&mut self, batch_idx: usize) -> Option<Vec<T>> { |
| 121 | + self.batches.get_mut(batch_idx).map(|batch| { |
| 122 | + self.len = self.len.saturating_sub(batch.len()); |
| 123 | + std::mem::take(batch) |
| 124 | + }) |
| 125 | + } |
| 126 | + |
| 127 | + /// Take all elements as a flat Vec (for `EmitTo::All`). |
| 128 | + pub fn take_all(&mut self) -> Vec<T> { |
| 129 | + self.len = 0; |
| 130 | + std::mem::take(&mut self.batches) |
| 131 | + .into_iter() |
| 132 | + .flatten() |
| 133 | + .collect() |
| 134 | + } |
| 135 | + |
| 136 | + /// Take the first `n` elements (for `EmitTo::First(n)`). |
| 137 | + /// |
| 138 | + /// When `n` equals `batch_size`, this is zero-copy (just `mem::take` |
| 139 | + /// on the first batch). Otherwise, full batches are drained via |
| 140 | + /// `mem::take` (O(1) each) and only the split-point batch is copied. |
| 141 | + pub fn take_first(&mut self, n: usize) -> Vec<T> { |
| 142 | + assert!(n <= self.len); |
| 143 | + let full_batches = n >> self.batch_shift; |
| 144 | + let remainder = n & self.batch_mask; |
| 145 | + |
| 146 | + // Fast path: exactly one full batch, no remainder — zero copy |
| 147 | + if full_batches == 1 && remainder == 0 { |
| 148 | + self.len -= n; |
| 149 | + return self.batches.drain(..1).next().unwrap(); |
| 150 | + } |
| 151 | + |
| 152 | + let mut result = Vec::with_capacity(n); |
| 153 | + |
| 154 | + // Take full batches — O(1) each |
| 155 | + for batch in self.batches.drain(..full_batches) { |
| 156 | + result.extend(batch); |
| 157 | + } |
| 158 | + |
| 159 | + // Split the next batch if there's a remainder |
| 160 | + if remainder > 0 && !self.batches.is_empty() { |
| 161 | + let batch = &mut self.batches[0]; |
| 162 | + let mut tail = batch.split_off(remainder); |
| 163 | + std::mem::swap(batch, &mut tail); |
| 164 | + result.extend(tail); // tail has [0..remainder] |
| 165 | + } |
| 166 | + |
| 167 | + self.len -= n; |
| 168 | + result |
| 169 | + } |
| 170 | + |
| 171 | + /// Total heap memory used by this structure. |
| 172 | + pub fn size(&self) -> usize { |
| 173 | + self.batches |
| 174 | + .iter() |
| 175 | + .map(|b| b.capacity() * size_of::<T>()) |
| 176 | + .sum::<usize>() |
| 177 | + + self.batches.capacity() * size_of::<Vec<T>>() |
| 178 | + } |
| 179 | +} |
| 180 | + |
| 181 | +#[cfg(test)] |
| 182 | +mod tests { |
| 183 | + use super::*; |
| 184 | + |
| 185 | + #[test] |
| 186 | + fn test_basic_operations() { |
| 187 | + let mut v = BatchedVec::new(4); |
| 188 | + assert_eq!(v.len(), 0); |
| 189 | + |
| 190 | + v.ensure_capacity(10, 0i32); |
| 191 | + assert_eq!(v.len(), 10); |
| 192 | + assert_eq!(v.num_batches(), 3); // 4 + 4 + 2 |
| 193 | + |
| 194 | + // Write via composite index |
| 195 | + for i in 0..10 { |
| 196 | + unsafe { |
| 197 | + *v.get_unchecked_mut(i) = i as i32; |
| 198 | + } |
| 199 | + } |
| 200 | + |
| 201 | + // take_all flattens |
| 202 | + let all = v.take_all(); |
| 203 | + assert_eq!(&all[..10], &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); |
| 204 | + assert_eq!(v.len(), 0); |
| 205 | + } |
| 206 | + |
| 207 | + #[test] |
| 208 | + fn test_take_batch() { |
| 209 | + let mut v = BatchedVec::new(4); |
| 210 | + v.ensure_capacity(10, 0i32); |
| 211 | + for i in 0..10 { |
| 212 | + unsafe { |
| 213 | + *v.get_unchecked_mut(i) = i as i32; |
| 214 | + } |
| 215 | + } |
| 216 | + |
| 217 | + let b0 = v.take_batch(0).unwrap(); |
| 218 | + assert_eq!(b0, vec![0, 1, 2, 3]); |
| 219 | + |
| 220 | + let b1 = v.take_batch(1).unwrap(); |
| 221 | + assert_eq!(b1, vec![4, 5, 6, 7]); |
| 222 | + |
| 223 | + // Last batch has only the 2 remaining elements |
| 224 | + let b2 = v.take_batch(2).unwrap(); |
| 225 | + assert_eq!(b2, vec![8, 9]); |
| 226 | + } |
| 227 | + |
| 228 | + #[test] |
| 229 | + fn test_take_first() { |
| 230 | + let mut v = BatchedVec::new(4); |
| 231 | + v.ensure_capacity(10, 0i32); |
| 232 | + for i in 0..10 { |
| 233 | + unsafe { |
| 234 | + *v.get_unchecked_mut(i) = i as i32; |
| 235 | + } |
| 236 | + } |
| 237 | + |
| 238 | + let first = v.take_first(6); |
| 239 | + assert_eq!(first, vec![0, 1, 2, 3, 4, 5]); |
| 240 | + |
| 241 | + let rest = v.take_all(); |
| 242 | + assert_eq!(&rest[..4], &[6, 7, 8, 9]); |
| 243 | + } |
| 244 | + |
| 245 | + #[test] |
| 246 | + fn test_ensure_capacity_grows() { |
| 247 | + let mut v = BatchedVec::new(4); |
| 248 | + v.ensure_capacity(3, 42i32); |
| 249 | + assert_eq!(v.len(), 3); |
| 250 | + assert_eq!(v.num_batches(), 1); |
| 251 | + // Batch has exactly the elements needed |
| 252 | + assert_eq!(v.take_batch(0).unwrap().len(), 3); |
| 253 | + } |
| 254 | +} |
0 commit comments