docchi_diff/imp/write/
store_ids.rs

1
2use std::collections::BTreeMap;
3use docchi_core::structs::{RustParam, Qv};
4
5#[derive(Debug)]
6pub(crate) enum StoredIDs{
7    Zero,
8    U64(u64),
9    Bits(Vec<u64>),
10    Numbers(Vec<usize>),
11}
12
13enum StoredIDsType{
14    U64, Bits, Numbers, Zero
15}
16
17pub(crate) fn store_ids<'a, T>(params : &'a BTreeMap<usize, &'a RustParam>, lists : &'a BTreeMap<usize, T>) -> StoredIDs{
18    let mut max : usize = 0;
19    let mut len_sum : usize = 0;
20    update_max_and_len(params, &mut max, &mut len_sum);
21    update_max_and_len(lists, &mut max, &mut len_sum);
22
23
24    match calc_type(max, len_sum){
25        StoredIDsType::Zero => StoredIDs::Zero,
26        StoredIDsType::U64 => StoredIDs::U64(get_u64(params, lists)),
27        StoredIDsType::Bits => StoredIDs::Bits(get_bits(params, lists, max)),
28        StoredIDsType::Numbers => StoredIDs::Numbers(get_numbers(params, lists, len_sum)),
29    }
30}
31
32pub(crate) fn store_ids_ref(refs : &BTreeMap<usize, &Qv<String>>) -> StoredIDs{
33    let mut max : usize = 0;
34    let mut len_sum : usize = 0;
35    update_max_and_len(refs, &mut max, &mut len_sum);
36
37    match calc_type(max, len_sum){
38        StoredIDsType::Zero => StoredIDs::Zero,
39        StoredIDsType::U64 =>{
40            let mut u = 0;
41            update_u64(refs, &mut u);
42            StoredIDs::U64(u)
43        }
44        StoredIDsType::Bits =>{
45            StoredIDs::Bits(get_bits_ref(refs, max))
46        },
47        StoredIDsType::Numbers => StoredIDs::Numbers(get_numbers_ref(refs, len_sum)),
48    }
49}
50
51
52fn get_u64<'a,T>(params : &'a BTreeMap<usize, &'a RustParam>, lists : &'a BTreeMap<usize,T>) -> u64{
53    let mut r : u64 = 0;
54    update_u64(params, &mut r);
55    update_u64(lists, &mut r);
56    r
57}
58
59fn update_u64<T>(map : &BTreeMap<usize, T>, r : &mut u64){
60    for &i in map.keys(){
61        *r |= 1 << i;
62    }
63}
64
65fn get_bits<'a, T>(params : &'a BTreeMap<usize, &'a RustParam>, lists : &'a BTreeMap<usize, T>, max : usize) -> Vec<u64> {
66    let len = max / 64 + 1;
67    let mut r : Vec<u64> = Vec::with_capacity(len);
68    for _ in 0..len{
69        r.push(0);
70    }
71
72    update_bits(params, &mut r);
73    update_bits(lists, &mut r);
74    return r;
75}
76
77fn get_bits_ref(refs : &BTreeMap<usize, &Qv<String>>, max : usize) -> Vec<u64> {
78    let len = max / 64 + 1;
79    let mut r : Vec<u64> = Vec::with_capacity(len);
80    for _ in 0..len{
81        r.push(0);
82    }
83
84    update_bits(refs, &mut r);
85    return r;
86}
87
88fn update_bits<T>(map : &BTreeMap<usize, T>, r : &mut Vec<u64>){
89    for &i in map.keys(){
90        let ind = i / 64;
91        let bit = i % 64;
92
93        unsafe {
94            *r.get_unchecked_mut(ind) |= 1 << bit;
95        }
96    }
97}
98
99fn get_numbers<'a, T>(params : &'a BTreeMap<usize, &'a RustParam>, lists : &'a BTreeMap<usize, T>, len : usize) -> Vec<usize> {
100    let mut r : Vec<usize> = Vec::with_capacity(len);
101    update_numbers(params, &mut r);
102    update_numbers(lists, &mut r);
103    r
104}
105
106fn get_numbers_ref(refs : &BTreeMap<usize, &Qv<String>>, len : usize) -> Vec<usize> {
107    let mut r : Vec<usize> = Vec::with_capacity(len);
108    update_numbers(refs, &mut r);
109    r
110}
111
112fn update_numbers<T>(map : &BTreeMap<usize, T>, r : &mut Vec<usize>){
113    for &i in map.keys(){
114        r.push(i);
115    }
116}
117
118fn calc_type(max : usize, len : usize)->StoredIDsType {
119    if len == 0 { return StoredIDsType::Zero; }
120
121    //numberは表すのにひとつあたり11bitぐらいかかるのに対し、u64なら1bitである。
122    // u64の場合あるものもないものも割り当てる必要があるが、Numbersはあるものにだけ割り当てる
123    //あるものが1/11なら節約になる場合がある
124    //
125    //別に必要のない機能に思うが、膨大なメンバ数やリストのアイテム数になったときに、1つ2つだけ変化がある、
126    // という場合にはこの細かい指定が意味を持ってくるはずだ。一般的にはあまり意味を持たない気もするが、
127    // ありうる範囲ならばワーストケースに備えたい
128    //
129    //ないものだけを指定する、という方式で節約できる可能性もあるのだが、そんなのあるかなあ？
130    //あったとしても変化データが膨大になるのでこのフラグ部分を節約することにたいした意味を感じない
131    //面倒臭さがまさる
132    if max < 64 {
133        if len > max / 11 {
134            StoredIDsType::U64
135        } else {
136            StoredIDsType::Numbers
137        }
138    } else if max < 32768{
139        if len > max / 24 {
140            StoredIDsType::Bits
141        } else {
142            StoredIDsType::Numbers
143        }
144    } else if max < 8388608{
145        if len > max / 32 {
146            StoredIDsType::Bits
147        } else {
148            StoredIDsType::Numbers
149        }
150    } else if max < 2147483648{
151        if len > max / 40 {
152            StoredIDsType::Bits
153        } else {
154            StoredIDsType::Numbers
155        }
156    } else{
157        //このサイズまで処理できると考えるべきではないだろう。未来のコンピュータならわからないが・・・
158        if len > max / 48 {
159            StoredIDsType::Bits
160        } else {
161            StoredIDsType::Numbers
162        }
163    }
164}
165
166fn update_max_and_len<T>(map : &BTreeMap<usize,T>, max : &mut usize, len : &mut usize){
167    let (max_t, len_t) = max_and_len(map);
168    *len += len_t;
169    *max = (*max).max(max_t);
170}
171
172fn max_and_len<T>(map : &BTreeMap<usize,T>) -> (usize, usize){
173    if map.len() == 0{ (0,0) }
174    else{
175        let (id,_) = map.iter().next_back().unwrap();
176        (*id, map.len())
177    }
178}
docchi_diff/imp/write/store_ids.rs

docchi_diff/imp/write/
store_ids.rs
