musli_zerocopy/phf/
generator.rs

1use core::cmp::Reverse;
2use core::hash::Hash;
3
4use alloc::vec;
5use alloc::vec::Vec;
6
7use crate::buf::{Buf, Visit};
8use crate::error::{Error, ErrorKind};
9use crate::phf::Entry;
10use crate::phf::hashing::{HashKey, Hashes, displace, hash};
11use crate::{ByteOrder, Ref, Size, ZeroCopy};
12
13use rand::rngs::SmallRng;
14use rand::{RngExt as _, SeedableRng};
15
16const DEFAULT_LAMBDA: usize = 5;
17const FIXED_SEED: u64 = 1234567890;
18
19pub(crate) struct HashState {
20    pub(crate) key: HashKey,
21}
22
23/// Calculate displacements length.
24#[inline]
25pub(crate) fn displacements_len(len: usize) -> usize {
26    len.div_ceil(DEFAULT_LAMBDA)
27}
28
29pub(crate) fn generate_hash<K, T, F, E, O>(
30    buf: &mut Buf,
31    entries: &Ref<[T], E, O>,
32    displacements: &Ref<[Entry<u32, u32>], E, O>,
33    map: &Ref<[usize], E, O>,
34    access: F,
35) -> Result<HashState, Error>
36where
37    K: Visit,
38    K::Target: Hash,
39    F: Fn(&T) -> &K,
40    T: ZeroCopy,
41    E: ByteOrder,
42    O: Size,
43{
44    for key in SmallRng::seed_from_u64(FIXED_SEED).random_iter() {
45        if let Some(hash) = try_generate_hash(buf, entries, displacements, map, key, &access)? {
46            return Ok(hash);
47        }
48
49        // Reset the state of displacements and maps since we're trying again.
50        for d in buf.load_mut(*displacements)? {
51            *d = Entry::new(0, 0);
52        }
53
54        for m in buf.load_mut(*map)? {
55            *m = usize::MAX;
56        }
57    }
58
59    Err(Error::new(ErrorKind::FailedPhf))
60}
61
62fn try_generate_hash<K, T, F, E, O>(
63    buf: &mut Buf,
64    entries: &Ref<[T], E, O>,
65    displacements: &Ref<[Entry<u32, u32>], E, O>,
66    map: &Ref<[usize], E, O>,
67    key: HashKey,
68    access: &F,
69) -> Result<Option<HashState>, Error>
70where
71    K: Visit,
72    K::Target: Hash,
73    F: ?Sized + Fn(&T) -> &K,
74    T: ZeroCopy,
75    E: ByteOrder,
76    O: Size,
77{
78    let mut hashes = Vec::new();
79
80    for entry in entries.iter() {
81        let entry = buf.load(entry)?;
82        let entry_key = access(entry);
83        let h = hash(buf, entry_key, &key)?;
84        hashes.push(h);
85    }
86
87    let mut buckets = (0..displacements.len())
88        .map(|index| (index, Vec::<usize>::new()))
89        .collect::<Vec<_>>();
90
91    for (index, hash) in hashes.iter().enumerate() {
92        let to = hash.g % buckets.len();
93        buckets[to].1.push(index);
94    }
95
96    // NB: the index of a bucket has to be kept around, since a lookup finds the
97    // displacement of a key through the index of the bucket it hashes into.
98    //
99    // Buckets are placed largest first, since the crowded buckets are the hard
100    // ones to find displacements for and the table is emptiest to begin with.
101    buckets.sort_by_key(|(_, keys)| Reverse(keys.len()));
102
103    let table_len = hashes.len();
104    // let mut map = vec![usize::MAX; table_len];
105
106    // store whether an element from the bucket being placed is
107    // located at a certain position, to allow for efficient overlap
108    // checks. It works by storing the generation in each cell and
109    // each new placement-attempt is a new generation, so you can tell
110    // if this is legitimately full by checking that the generations
111    // are equal. (A u64 is far too large to overflow in a reasonable
112    // time for current hardware.)
113    let mut try_map = vec![0u64; table_len];
114    let mut generation = 0u64;
115
116    // the actual values corresponding to the markers above, as
117    // (index, key) pairs, for adding to the main map once we've
118    // chosen the right displacements.
119    let mut values_to_add = vec![];
120
121    'outer: for (bucket_index, bucket) in buckets.iter() {
122        let d_ref = displacements.at(*bucket_index);
123
124        for d1 in 0..(table_len as u32) {
125            'inner: for d2 in 0..(table_len as u32) {
126                values_to_add.clear();
127                generation += 1;
128
129                for &key in bucket {
130                    let Hashes { f1, f2, .. } = hashes[key];
131                    let index = displace(f1, f2, d1, d2) as usize;
132                    let index = index % table_len;
133
134                    if *buf.load(map.at(index))? != usize::MAX || try_map[index] == generation {
135                        continue 'inner;
136                    }
137
138                    try_map[index] = generation;
139                    values_to_add.push((index, key));
140                }
141
142                // We've picked a good set of displacements
143                *buf.load_mut(d_ref)? = Entry::new(d1, d2);
144
145                for &(i, key) in &values_to_add {
146                    let m = buf.load_mut(map.at(i))?;
147                    *m = key;
148                }
149
150                continue 'outer;
151            }
152        }
153
154        // Unable to find displacements for a bucket
155        return Ok(None);
156    }
157
158    Ok(Some(HashState { key }))
159}
musli_zerocopy/phf/generator.rs

musli_zerocopy/phf/
generator.rs
