bitrush_index/bitmap_index/
mod.rs

1// This code is released under the
2// General Public License (GPL), version 3
3// http://www.gnu.org/licenses/gpl-3.0.en.html
4// (c) Lorenzo Vannucci
5
6//! # BitmapIndex
7//!
8//! A serializable bitmap-index for each value that implement BitValue trait
9//! and for each bitmap that implement Bitmap trait.
10//! On default `BitValue` is implemented for:
11//! `u8, u16`, `u32`, `u64`, `u128`, `i8`, `i16`, `i32`, `i64`, `i128`.
12
13/// [`Bitmap`]: ./bitmap.rs
14
15use std::ops::{BitAnd, BitOr, Shr};
16use std::marker::Copy;
17use std::fmt::{Display};
18use std::convert::From;
19use std::mem;
20use std::io::{Write, Error as IoError, SeekFrom, Seek, Read};
21use std::fs;
22use std::path::{Path, PathBuf};
23
24mod bitmap;
25pub use self::bitmap::Bitmap;
26
27/// A trait that allow to convert `BitValue` to `usize`.
28pub trait TransmuteToUsize {
29
30    /// Return the right most bits of self as `usize` type.
31    fn transmute_to_usize(self) -> usize;
32}
33
34macro_rules! impl_transmute_to_usize_for_number {
35    ($ty:ident) => {
36        impl TransmuteToUsize for $ty {
37            fn transmute_to_usize(self) -> usize { self as usize }
38        }
39    };
40}
41
42/// `BitValue` trait.
43/// On default `BitValue` is implemented for:
44/// `u8, u16`, `u32`, `u64`, `u128`, `i8`, `i16`, `i32`, `i64`, `i128`.
45pub trait BitValue: Copy + Display + BitAnd + BitOr + Shr<usize> + TransmuteToUsize {}
46
47macro_rules! impl_bit_value_for_number {
48    ($ty:ident) => {
49        impl_transmute_to_usize_for_number!($ty);
50        impl BitValue for $ty {}
51    };
52    ($ty1:ident, $($ty2:ident),+) => {
53        impl_transmute_to_usize_for_number!($ty1);
54        impl BitValue for $ty1 {}
55        impl_bit_value_for_number!($($ty2),+);
56    }    
57}
58
59impl_bit_value_for_number!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128);
60
61/// `BitmapIndex` errors types.
62#[derive(Debug)]
63pub enum Error {
64    ParametersError,
65    FileError(IoError),
66    BitmapError,
67}
68
69/// `BitmapIndex` works in chunks, each chunk represent `ChunkSize` values,
70/// possibily values for `ChunkSize` are: 1 Mega, 2 Mega, 4 Mega, 8 Mega, 16 Mega, 32 Mega.
71/// If `BitmapIndex` is created in storage mode, bitmaps are serialized every time a chunk
72/// is full.
73#[derive(Clone)]
74pub enum ChunkSize {
75    M1 = (1 << 20),
76    M2 = (1 << 21),
77    M4 = (1 << 22),
78    M8 = (1 << 23),
79    M16 = (1 << 24),
80    M32 = (1 << 25),
81}
82
83/// `BitmapIndex` struct that requires a bitmap that implement [`Bitmap`] trait and
84/// a type that implement `BitValue` trait.
85pub struct BitmapIndex<T: Bitmap, U: BitValue>
86where <U as Shr<usize>>::Output: TransmuteToUsize,
87for <'a> &'a T: BitAnd<&'a T, Output=T> {
88    num_values: u64,
89    chunk_size: u64,
90    chunk_size_mask: u64,
91    
92    bitmaps: Vec<T>,
93    block_info: BlockInfo,
94    
95    storage_idx: Option<StorageIdx>,
96    chunk_offset: u64,
97    chunks: Option<Vec<Vec<T>>>,
98    last_checkpoint: Option<MetaData>,
99    
100    _marker: std::marker::PhantomData<U>
101}
102
103struct BlockInfo {
104    bit_block_size: usize,
105    bit_block_mask: usize,
106    num_blocks: usize,
107    num_bitmaps_in_block: usize,
108}
109
110/// `BuildOptions` defines how many bitmap compose a `BitmapIndex` and how many values must
111/// represent every chunk in `BitmapIndex`.
112/// On a `BitmapIndex` of a `BitValue` 'U' with `size_in_bit(U) = L`, `bit_block_size` represent
113/// the size in bit of each sub-index.
114/// For example a `BitmapIndex` of a `BitValue` 'U=`u16`' with 'size_in_bit(u16) = 16'
115/// and `bit_block_size = 8` is composed from '16 / 8 = 2' blocks of '2^8 = 256' bitmaps each,
116/// so is composed from '2 * 256 = 512' bitmaps.
117#[derive(Clone)]
118#[repr(C)]
119pub struct BuildOptions {
120    bit_block_size: usize,
121    chunk_size: ChunkSize
122}
123
124impl BuildOptions {
125    /// Create a new `BuildOptions`.
126    pub fn new(bit_block_size: usize, chunk_size: ChunkSize) -> Self {
127        BuildOptions {
128            bit_block_size,
129            chunk_size
130        }
131    }
132}
133
134/// `StorageIdx` defines a `BitmapIndex` opened in read-only storage mode.
135pub struct StorageIdx {
136    meta_data_file: fs::File,
137    offset_file: fs::File,
138    data_file: fs::File
139}
140
141/// `MetaData` defines the meta data of a `BitmapIndex`.
142#[repr(C)]
143pub struct MetaData {
144    num_values: u64,
145    build_options: BuildOptions
146}
147
148impl<T: Bitmap, U: BitValue> BitmapIndex<T, U>
149where <U as std::ops::Shr<usize>>::Output: TransmuteToUsize,
150for <'a> &'a T: BitAnd<&'a T, Output=T> {
151
152    /// Return a `BitmapIndex` in storage mode and create a folder with `bitmap_index_path` path.
153    /// The created folder contain 3 files that represent a `BitmapIndex`:
154    /// 1) A file with 'mbidx' extension that represent `BitmapIndex` meta data.
155    /// 2) A file with 'obidx' extension that represent all offsets of all bitmaps chunks.
156    /// 3) A file with 'dbix' extension that represent all bitmaps chunks content.
157    pub fn create(bitmap_index_path: &Path, build_options: BuildOptions) -> Result<Self, Error> {
158        if Self::check_if_path_exixsts(bitmap_index_path) {
159            return Err(Error::ParametersError);
160        }
161        let storage_idx = Self::get_storage_idx(bitmap_index_path, Some(build_options.clone()))?;
162
163        let mut bitmap_index: Self = Self::new_index(build_options, true)?;
164        bitmap_index.storage_idx = Some(storage_idx);
165        bitmap_index.last_checkpoint = Some(bitmap_index.get_meta_data());
166        
167        Ok(bitmap_index)
168    }
169
170    /// Open a `BitmapIndex` in storage mode previusly created.
171    pub fn open(dir_path: &Path) -> Result<Self, Error> {
172        let mut storage_idx = Self::get_storage_idx(dir_path, None)?;
173        let m = Self::map_io_result(Self::read_meta_data(&mut storage_idx))?;
174        let mut bitmap_index = Self::new_index(m.0.build_options, true)?;
175        bitmap_index.num_values = m.0.num_values;
176
177        let offsets_r = Self::read_chunk_offset(&mut storage_idx, bitmap_index.num_values, bitmap_index.chunk_size);
178        let offsets = Self::map_io_result(offsets_r)?;
179        bitmap_index.chunk_offset = offsets.0;
180        if bitmap_index.num_values & bitmap_index.chunk_size_mask != 0 {
181            let r_buf_chunk = Self::read_chunk(&mut storage_idx, offsets);
182            let buf_chunk = Self::map_io_result(r_buf_chunk)?;
183            Self::read_bitmaps(&buf_chunk, &mut bitmap_index.bitmaps)?;
184        }
185        bitmap_index.storage_idx = Some(storage_idx);
186        bitmap_index.last_checkpoint = Some(m.1);
187
188        Ok(bitmap_index)
189    }
190
191    fn read_bitmaps(buf: &[u8], bitmaps: &mut [T]) -> Result<(), Error> {
192        let num_offsets = bitmaps.len() + 1;
193        let buf_offsets_size = num_offsets * mem::size_of::<u32>();
194        let v_offsets: &[u32] = Self::convert_slice(&buf[0..buf_offsets_size]);
195        let v_bitmap: &[u8] = &buf[buf_offsets_size..];
196
197        let mut i = 0;
198        let mut start_offset = 0;
199        
200        for b in bitmaps.iter_mut() {
201            let b_size: usize = (v_offsets[i + 1] - v_offsets[i]) as usize;
202            let end_offset = start_offset + b_size;
203            Self::read_bitmap(&v_bitmap[start_offset..end_offset], true, b)?;
204            start_offset = end_offset;
205            i += 1;
206        }
207        Ok(())
208    }
209    
210    fn read_bitmap(buf: &[u8], check_bitmap: bool, bitmap: &mut T) -> Result<(), Error> {
211        let r = bitmap.read_from_buffer(buf, check_bitmap);
212        Self::map_bitmap_result(r)
213    }
214
215    fn map_bitmap_result(result: Result<(), ()>) -> Result<(), Error> {
216        let r = match result {
217            Err(_) => Err(Error::BitmapError),
218            Ok(_) => Ok(())
219        };
220        r
221    }
222
223    fn read_chunk(storage_idx: &mut StorageIdx, offsets: (u64, u64)) -> Result<Vec<u8>, IoError> {
224        let buf_chunk_size: usize = (offsets.1 - offsets.0) as usize;
225        let mut buf_chunk: Vec<u8> = vec![0; buf_chunk_size];
226        storage_idx.data_file.seek(SeekFrom::Start(offsets.0))?;
227        storage_idx.data_file.read_exact(&mut buf_chunk)?;
228
229        Ok(buf_chunk)
230    }
231
232    fn read_bitmap_offset(storage_idx: &mut StorageIdx, chunk_offset: u64, i_bitmap: usize) -> Result<(u64, u64), Error> {
233        let i_bitmap_offset = chunk_offset + (i_bitmap * mem::size_of::<u32>()) as u64;
234        let r_seek = storage_idx.data_file.seek(SeekFrom::Start(i_bitmap_offset));
235        Self::map_io_result(r_seek)?;
236        const BUF_SIZE: usize = mem::size_of::<u32>() * 2;
237        let mut buf: [u8; BUF_SIZE] = [0; BUF_SIZE];
238
239        Self::map_io_result(storage_idx.data_file.read_exact(&mut buf))?;
240        let start_offset: u32 = Self::copy_from_slice_u8(&buf[0..mem::size_of::<u32>()]);
241        let end_offset: u32 = Self::copy_from_slice_u8(&buf[mem::size_of::<u32>()..]);
242        
243        Ok((chunk_offset + start_offset as u64, chunk_offset + end_offset as u64)) 
244    }
245
246    fn read_query_bitmaps(storage_idx: &mut StorageIdx, chunk_offset: u64, query_i_bitmaps: &[usize]) -> Result<Vec<T>, Error> {
247        let vec_len = query_i_bitmaps.len();
248        let mut bitmaps_offset: Vec<(u64, u64)> = Vec::with_capacity(vec_len);
249        for i_bitmap in query_i_bitmaps {
250            let bitmap_offset = Self::read_bitmap_offset(storage_idx, chunk_offset, *i_bitmap)?;
251            bitmaps_offset.push(bitmap_offset);
252        }
253
254        let mut query_bitmaps: Vec<T> = Vec::with_capacity(vec_len);
255        let mut buf: Vec<u8> = Vec::new();
256        for offset in bitmaps_offset {
257            let buf_len = (offset.1 - offset.0) as usize;
258            let mut bitmap = T::new();
259            if buf.len() < buf_len {
260                buf = vec![0; buf_len];
261            }
262            Self::map_io_result(storage_idx.data_file.seek(SeekFrom::Start(offset.0)))?;
263            let r_read = storage_idx.data_file.read_exact(&mut buf[0..buf_len]);
264            Self::map_io_result(r_read)?;
265            Self::read_bitmap(&buf[0..buf_len], true, &mut bitmap)?;
266            query_bitmaps.push(bitmap);
267        }
268        
269        Ok(query_bitmaps)
270    }
271    
272    fn read_chunk_offset(storage_idx: &mut StorageIdx, num_values: u64, chunk_size: u64) -> Result<(u64, u64), IoError> {
273        let chunk_size_mask = chunk_size - 1;
274        let offsets = if num_values == 0 {
275            (0, 0)
276        } else {
277            let start_index = num_values - (num_values & chunk_size_mask);
278            let end_index = num_values;
279            let offsets = Self::read_chunks_offsets(storage_idx, start_index, end_index, chunk_size, 2, 1)?;
280            if offsets.len() == 1 {
281                (offsets[0], offsets[0])
282            } else {
283                (offsets[0], offsets[1])
284            }
285        };
286                
287        Ok((offsets.0, offsets.1))
288    }
289
290    fn read_chunks_offsets(storage_idx: &mut StorageIdx, start_index: u64, end_index: u64, chunk_size: u64, max_num_offsets: usize, plus_chunk: usize) -> Result<Vec<u64>, IoError> {
291        let start_offset = Self::get_chunk_id(start_index, chunk_size);
292        let mut num_offsets = (Self::get_chunk_id(end_index, chunk_size) - start_offset) as usize + plus_chunk;
293        if num_offsets > max_num_offsets
294        {
295            num_offsets = max_num_offsets;
296        }
297        let offsets: Vec<u64> = vec![0; num_offsets];
298        
299        let block_offset: u64 = Self::get_block_offset(start_offset);
300        let buf: &mut [u8] = Self::convert_slice(&offsets);
301
302        storage_idx.offset_file.seek(SeekFrom::Start(block_offset))?;
303        storage_idx.offset_file.read_exact(buf)?;
304        
305        Ok(offsets)
306    }
307
308
309    fn read_meta_data(storage_idx: &mut StorageIdx) -> Result<(MetaData, MetaData), IoError> {
310        const META_DATA_SIZE: usize = mem::size_of::<MetaData>();
311        let mut meta_data_buf: [u8; META_DATA_SIZE] = [0; META_DATA_SIZE];
312        storage_idx.meta_data_file.seek(SeekFrom::Start(0))?;
313        storage_idx.meta_data_file.read_exact(&mut meta_data_buf)?;
314        let meta_data: MetaData = Self::copy_from_slice_u8(&meta_data_buf);
315        storage_idx.meta_data_file.read_exact(&mut meta_data_buf)?; 
316        let last_check_point: MetaData = Self::copy_from_slice_u8(&meta_data_buf);
317        Ok((meta_data, last_check_point))
318    }
319
320    fn check_if_path_exixsts(dir_path: &Path) -> bool {
321        match fs::metadata(dir_path) {
322            Ok(_) => true,
323            Err(_) => false
324        }
325    }
326
327    fn map_io_result<M>(result: Result<M, IoError>) -> Result<M, Error> {
328        match result {
329            Ok(r) => Ok(r),
330            Err(err) => Err(Error::FileError(err))
331        }
332    }
333
334    pub fn new_storage_idx(dir_path: &Path) -> Result<StorageIdx, Error> {
335        Self::get_storage_idx(dir_path, None)
336    }
337
338    fn get_storage_idx(dir_path: &Path, build_options: Option<BuildOptions>) -> Result<StorageIdx, Error> {
339        let storage_idx = match Self::open_storage_idx(dir_path, build_options.clone()) {
340            Ok(s_idx) => s_idx,
341            Err(err) => {
342                if build_options.is_some() {
343                    Self::map_io_result(fs::remove_dir(dir_path))?;
344                }
345                return Err(Error::FileError(err));
346            }
347        };
348
349        Ok(storage_idx)
350    }
351    
352    fn open_storage_idx(dir_path: &Path, build_options: Option<BuildOptions>) -> Result<StorageIdx, IoError> {
353        if build_options.is_some() {
354            fs::create_dir(dir_path)?;
355        }
356        let name = dir_path.file_name().unwrap();
357        
358        let mut meta_data_path = PathBuf::from(dir_path);
359        meta_data_path.push(name);
360        meta_data_path.set_extension("mbidx");
361
362        let mut offset_path = PathBuf::from(dir_path);
363        offset_path.push(name);
364        offset_path.set_extension("obidx");
365        
366        let mut data_path = PathBuf::from(dir_path);
367        data_path.push(name);
368        data_path.set_extension("dbidx");
369
370        let data_file = Self::open_file(data_path.as_path(), true)?;
371        let offset_file = Self::open_file(offset_path.as_path(), true)?;
372        let meta_data_file = Self::open_file(meta_data_path.as_path(), true)?;
373        let mut storage_idx = StorageIdx {
374            meta_data_file,
375            offset_file,
376            data_file
377        };
378        if build_options.is_some() {
379            let meta_data = MetaData {
380                num_values: 0,
381                build_options: build_options.unwrap()
382            };
383            Self::write_empty_storage_idx(&mut storage_idx, &meta_data)?;
384        }
385
386        Ok(storage_idx)
387    }
388
389    fn write_empty_storage_idx(storage_idx: &mut StorageIdx, meta_data: &MetaData) -> Result<(), IoError> {
390        storage_idx.meta_data_file.write_all(Self::to_slice_u8(meta_data))?;
391        Ok(())
392    }
393
394    
395    fn get_meta_data(&self) -> MetaData {
396        MetaData {
397            num_values: self.num_values,
398            build_options: BuildOptions {
399                bit_block_size: self.block_info.bit_block_size,
400                chunk_size: unsafe { mem::transmute::<u32, ChunkSize>(self.chunk_size as u32) }
401            }
402        }
403    }
404
405    fn to_slice_u8<M>(m: &M) -> &[u8] {
406        let m: *const u8 = Self::convert_pointer(m as *const M);
407        unsafe {
408            std::slice::from_raw_parts(m, mem::size_of::<M>())
409        }
410    }
411
412    fn copy_from_slice_u8<M>(slice: &[u8]) -> M {
413        let m: *const M = Self::convert_pointer(slice.as_ptr());
414        unsafe { mem::transmute_copy::<M, M>(&*m) }
415    }
416
417    fn convert_slice<M,N>(slice: &[M]) -> &mut [N] {
418        let n: *mut N = Self::convert_pointer::<M,N>(slice.as_ptr()) as *mut N;
419        let len = slice.len() * mem::size_of::<M>() / mem::size_of::<N>();
420        unsafe {
421            std::slice::from_raw_parts_mut(n, len)
422        }
423    }
424
425    fn convert_pointer<M, N>(m: *const M) -> *const N {
426        m as *const N
427    }
428
429    fn open_file(path: &Path, create: bool) -> Result<fs::File, IoError> {
430        fs::OpenOptions::new()
431            .read(true)
432            .write(true)
433            .create(create)
434            .open(path)
435    }
436
437
438    fn new_block_info(bit_block_size: usize) -> Result<BlockInfo, Error> {
439        let bit_value_size = mem::size_of::<U>() << 3;
440        if bit_value_size % bit_block_size != 0 || bit_block_size > 16 || bit_block_size == 1 {
441            return Err(Error::ParametersError);
442        }
443
444        let num_blocks = bit_value_size / bit_block_size;
445        let num_bitmaps_in_block = 1 << bit_block_size;
446        Ok(BlockInfo {
447            bit_block_size,
448            bit_block_mask: num_bitmaps_in_block - 1,
449            num_blocks,
450            num_bitmaps_in_block            
451        })
452    }
453
454    /// Return a new `BitmapIndex` in memory mode. A `BitmapIndex` created with this
455    /// function works in memory and can't be serialized.
456    pub fn new(build_options: BuildOptions) -> Result<Self, Error> {
457        Self::new_index(build_options, false)
458    }
459
460    fn new_index(build_options: BuildOptions, is_storage_idx: bool) -> Result<Self, Error> {
461        let block_info = Self::new_block_info(build_options.bit_block_size)?;
462        let num_bitmaps = block_info.num_blocks * block_info.num_bitmaps_in_block;
463        let chunk_size: u64 = build_options.chunk_size as u64;
464
465        let mut b_index = BitmapIndex {
466            num_values: 0,
467            chunk_size,
468            chunk_size_mask: chunk_size - 1,
469            
470            bitmaps: vec![T::new(); num_bitmaps],
471            block_info,
472
473            storage_idx: None,
474            chunk_offset: 0,
475            chunks: None,
476            last_checkpoint: None,
477            
478            _marker: std::marker::PhantomData,
479        };
480        if is_storage_idx == false {
481            b_index.chunks = Some(Vec::new());
482        }
483        Ok(b_index)
484    }
485
486    fn run_f_on_i_bitmaps(block_info: &BlockInfo, value: U, mut f: impl FnMut(usize)) {
487        let mut i_block: usize = 0;
488        let mut i_bitmap = value.transmute_to_usize() & block_info.bit_block_mask;
489        let mut shift_value: usize = 0;
490        f(i_bitmap);
491
492        for _i in 1..block_info.num_blocks {
493            shift_value += block_info.bit_block_size;
494            i_block += block_info.num_bitmaps_in_block;
495            i_bitmap = i_block + ((value >> shift_value).transmute_to_usize() & block_info.bit_block_mask);
496            f(i_bitmap);
497        }
498    }
499
500    /// Insert (in append) a `value` into the index. If `BitmapIndex` is opened in
501    /// storage mode and the chunk is full, automatically the chunk is flushed on
502    /// persistent memory.
503    pub fn push_value(&mut self, value: U) -> Result<(), Error> {
504        let num_values_in_chunk = self.num_values & self.chunk_size_mask;
505        let bitmaps = &mut self.bitmaps;
506        let f = |i_bitmap: usize| {
507            bitmaps[i_bitmap].set(num_values_in_chunk as u32);
508        };
509        Self::run_f_on_i_bitmaps(&self.block_info, value, f);
510        self.num_values += 1;
511
512        if self.num_values & self.chunk_size_mask != 0 {
513            return Ok(());
514        }
515        if self.storage_idx.is_some() {
516            self.write_chunk()?;
517            self.bitmaps = vec![T::new(); self.bitmaps.len()];
518        } else if self.chunks.is_some() {
519            let chunks = self.chunks.as_mut().unwrap();
520            let mut bitmaps = vec![T::new(); self.bitmaps.len()];
521            mem::swap(&mut bitmaps, &mut self.bitmaps);
522            chunks.push(bitmaps);
523        }
524        Ok(())
525    }
526
527    fn get_chunk_id(num_values: u64, chunk_size: u64) -> u64 {
528        num_values / chunk_size
529    }
530
531    fn get_block_offset(chunk_id: u64) -> u64 {
532        chunk_id * mem::size_of::<u64>() as u64
533    }
534
535    /// Serialize current bitmaps chunk. Error occur if `BitmapIndex` is opened in memory mode.
536    pub fn flush_chunk(&mut self) -> Result<(), Error> {
537        if self.storage_idx.is_none() {
538            return Err(Error::ParametersError);
539        }
540        self.write_chunk()
541    }
542    
543    fn write_chunk(&mut self) -> Result<(), Error> {
544        let num_bitmaps: usize = self.bitmaps.len();
545        let mut bitmaps_size: usize = 0;
546        let mut bitmaps_offset: Vec<u32> = vec![0; num_bitmaps + 1];
547        let bitmap_start_offset: u32 = (bitmaps_offset.len() * mem::size_of::<u32>()) as u32;
548        let mut i: usize = 1;
549        bitmaps_offset[0] = bitmap_start_offset;
550        for b in &self.bitmaps {
551            bitmaps_size += b.size();
552            bitmaps_offset[i] = bitmap_start_offset + bitmaps_size as u32;
553            i += 1;
554        }
555        
556        let mut bitmaps_content: Vec<u8> = vec![0; bitmaps_size];
557        if let Err(_) = self.write_bitmaps_into_buffer(&mut bitmaps_content) {
558            return Err(Error::BitmapError);
559        };
560        let chunk_id = Self::get_chunk_id(self.num_values, self.chunk_size);
561        let block_offset: u64 = Self::get_block_offset(chunk_id);
562        let b_offsets = Self::convert_slice(&bitmaps_offset);
563        
564        let storage_idx: &mut StorageIdx = self.storage_idx.as_mut().unwrap();
565        let storage_idx2: &'static mut StorageIdx = unsafe { &mut*(storage_idx as *mut StorageIdx)};
566        self.chunk_offset = Self::map_io_result(
567            self.write_bitmaps_sync(storage_idx2, &b_offsets, &bitmaps_content, block_offset)
568        )?;
569        self.last_checkpoint = Some(self.get_meta_data());
570
571        Ok(())
572    }
573
574    fn write_bitmaps_sync(&mut self, storage_idx: &mut StorageIdx, bitmaps_offsets: &[u8], bitmaps_content: &[u8], block_offset: u64) -> Result<u64, IoError> {
575        storage_idx.data_file.seek(SeekFrom::Start(self.chunk_offset))?;
576        storage_idx.data_file.write_all(bitmaps_offsets)?;
577        storage_idx.data_file.write_all(bitmaps_content)?;
578
579        let chunk_data_size: u64 = (bitmaps_offsets.len() + bitmaps_content.len()) as u64;
580        let chunk_next_offset: u64 = self.chunk_offset + chunk_data_size;
581        storage_idx.offset_file.seek(SeekFrom::Start(block_offset))?;        
582        storage_idx.offset_file.write_all(&chunk_next_offset.to_ne_bytes())?;
583
584        let meta_data: MetaData = self.get_meta_data();
585        storage_idx.meta_data_file.seek(SeekFrom::Start(0))?;
586        storage_idx.meta_data_file.write_all(Self::to_slice_u8(&meta_data))?;
587        storage_idx.meta_data_file.write_all(Self::to_slice_u8(&self.last_checkpoint))?;
588        
589        Ok(chunk_next_offset)
590    }
591
592
593    fn write_bitmaps_into_buffer(&mut self, buf: &mut [u8]) -> Result<(), ()> {
594        let mut start_offest: usize = 0;
595        for b in &self.bitmaps {
596            let b_size = b.write_to_buffer(&mut buf[start_offest..])?;
597            start_offest += b_size;
598        }
599        Ok(())
600    }
601
602    /// Insert (in append) values into the index.
603    pub fn push_values(&mut self, values: &[U]) -> Result<(), Error> {
604        for v in values {
605            self.push_value(*v)?;
606        }
607        Ok(())
608    }
609
610    /// Return a `Vec<u64>` that contains all indexes of values pushed
611    /// in `BitmapIndex` equal to `value`. The parameters `start_index` and `end_index`
612    /// are optional and if specified define the range where query is runned.
613    pub fn run_query(&mut self, value: U, start_index: Option<u64>, end_index: Option<u64>) -> Result<Vec<u64>, Error> {
614        let query_i_bitmaps: Vec<usize> = Self::get_query_i_bitmaps(&self.block_info, value);
615
616        let start_index: u64 = start_index.unwrap_or(0);
617        let end_index: u64 = end_index.unwrap_or(self.num_values);
618        let mut chunk_id = 0;
619        let mut indexes: Vec<u64> = Vec::new();
620        
621        if self.chunks.is_some() {
622            let chunks: &Vec<Vec<T>> = self.chunks.as_ref().unwrap();
623            for bitmaps in chunks {
624                let query_bitmaps: Vec<&T> = query_i_bitmaps.iter()
625                    .map(|i_bitmap| &bitmaps[*i_bitmap]).collect();
626                Self::push_indexes(&query_bitmaps, chunk_id, self.chunk_size, start_index, end_index, &mut indexes);
627                chunk_id += 1;
628            }
629        } else if self.storage_idx.is_some() {
630            let meta_data = self.get_meta_data(); 
631            let storage_idx = self.storage_idx.as_mut().unwrap();
632            chunk_id = self.num_values / self.chunk_size;
633            let end_index = end_index - (end_index & self.chunk_size_mask);
634            let s_indexes = Self::run_query_from_storage_idx(storage_idx, value, Some(start_index), Some(end_index), Some(meta_data))?;
635            indexes = s_indexes;
636        }
637        let query_bitmaps: Vec<&T> = query_i_bitmaps.iter()
638            .map(|i_bitmap| &self.bitmaps[*i_bitmap]).collect();
639        Self::push_indexes(&query_bitmaps, chunk_id, self.chunk_size, start_index, end_index, &mut indexes);
640
641        Ok(indexes)
642    }
643
644    /// Return a `Vec<u64>` that contains all indexes of values pushed in a storage `BitmapIndex`
645    /// equal to `value`. Differently from `run_query` method allow to run a query only on
646    /// the chunks already flushed of a `BitmapIndex`.
647    pub fn run_query_from_storage_idx(storage_idx: &mut StorageIdx, value: U, start_index: Option<u64>, end_index: Option<u64>, meta_data: Option<MetaData>) -> Result<Vec<u64>, Error> {
648        let m_data = if meta_data.is_some() {
649            meta_data.unwrap()
650        } else {
651            let meta_data_r = Self::read_meta_data(storage_idx);
652            let meta_data = Self::map_io_result(meta_data_r)?;
653            meta_data.0
654        };
655        let block_info = Self::new_block_info(m_data.build_options.bit_block_size)?;
656        let mut start_index = start_index.unwrap_or(0);
657        if start_index > m_data.num_values {
658            return Ok(Vec::new())
659        }
660        let mut end_index = end_index.unwrap_or(m_data.num_values);
661        if end_index > m_data.num_values {
662            end_index = m_data.num_values;
663        }
664        let query_i_bitmaps: Vec<usize> = Self::get_query_i_bitmaps(&block_info, value);
665
666        let mut indexes: Vec<u64> = Vec::new();
667        const MAX_NUM_OFFSETS: usize = 1 << 13;
668        let chunk_size = m_data.build_options.chunk_size as u64;
669        let mut chunk_id = 0;
670        while start_index < end_index {
671            let chunks_offsets_r = Self::read_chunks_offsets(storage_idx, start_index, end_index, chunk_size, MAX_NUM_OFFSETS, 0);
672            let chunks_offsets: Vec<u64> = Self::map_io_result(chunks_offsets_r)?;
673            for chunk_offset in chunks_offsets.iter() {
674                let query_bitmaps = Self::read_query_bitmaps(storage_idx, *chunk_offset, &query_i_bitmaps)?;
675                let query_bitmaps_ref: Vec<&T> = query_bitmaps.iter().map(|q| q).collect();
676                Self::push_indexes(&query_bitmaps_ref, chunk_id, chunk_size, start_index, end_index, &mut indexes);
677                chunk_id += 1;
678            }
679
680            start_index += (chunks_offsets.len() as u64) * chunk_size;
681        }
682
683        Ok(indexes)
684    }
685
686    fn push_indexes(query_bitmaps: &[&T], chunk_id: u64, chunk_size: u64, start_index: u64, end_index: u64, indexes: &mut Vec<u64>)
687    {
688        let offset_index: u64 = chunk_id * chunk_size;
689        if offset_index + chunk_size < start_index || offset_index > end_index {
690            return;
691        }
692        let mut b_result: T = query_bitmaps[0].clone();
693        for i in 1..query_bitmaps.len() {
694            b_result = (&b_result) & query_bitmaps[i];
695        }
696        // let new_indexes: Vec<u64> = b_result.unroll_bitmap().iter()
697        //                .map(|idx| offset_index + *idx as u64)
698        //                .filter(|idx| *idx >= start_index && *idx <= end_index).collect();
699        indexes.extend(b_result.unroll_bitmap().iter()
700                       .map(|idx| offset_index + *idx as u64)
701                       .filter(|idx| *idx >= start_index && *idx <= end_index)
702        );
703    }
704
705    fn get_query_i_bitmaps(block_info: &BlockInfo, value: U) -> Vec<usize> {
706        let mut query_i_bitmaps: Vec<usize> = Vec::new();
707        
708        let f = |i_bitmap| {
709            query_i_bitmaps.push(i_bitmap);
710        };
711        Self::run_f_on_i_bitmaps(block_info, value, f);
712        query_i_bitmaps
713    }
714
715}
bitrush_index/bitmap_index/mod.rs

bitrush_index/bitmap_index/
mod.rs
