leapfrog 0.3.3

A fast, lock-free concurrent hash map
Documentation 
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

//! This module provides utility functionality used throughout the crate.

use core::{
    alloc::Layout,
    mem::{align_of, size_of},
    ops::{Add, BitOr, Shr, Sub, SubAssign},
};

#[cfg(feature = "stable_alloc")]
use allocator_api2::alloc::Allocator;
#[cfg(not(feature = "stable_alloc"))]
use core::alloc::Allocator;

/// Loads the buffer `buf` as a u64.
#[inline(always)]
pub fn load_u64_le(buf: &[u8], len: usize) -> u64 {
    debug_assert!(len <= buf.len());
    let mut data = 0u64;
    let ptr: *mut _ = &mut data;
    unsafe {
        std::ptr::copy_nonoverlapping(buf.as_ptr(), ptr as *mut u8, len);
    }
    data.to_le()
}

/// Rounds the `value` up to the nearest power of two.
#[inline]
pub fn round_to_pow2<T>(value: T) -> T
where
    T: SubAssign
        + Add<Output = T>
        + Sub<Output = T>
        + Shr<Output = T>
        + BitOr<Output = T>
        + Copy
        + From<usize>,
{
    let v = value - T::from(1);
    let res = match size_of::<T>() {
        1 => {
            let v = v | (v >> T::from(1));
            let v = v | (v >> T::from(2));
            v | (v >> T::from(4))
        }
        2 => {
            let v = v | (v >> T::from(1));
            let v = v | (v >> T::from(2));
            let v = v | (v >> T::from(4));
            v | (v >> T::from(8))
        }
        4 => {
            let v = v | (v >> T::from(1));
            let v = v | (v >> T::from(2));
            let v = v | (v >> T::from(4));
            let v = v | (v >> T::from(8));
            v | (v >> T::from(16))
        }
        8 => {
            let v = v | (v >> T::from(1));
            let v = v | (v >> T::from(2));
            let v = v | (v >> T::from(4));
            let v = v | (v >> T::from(8));
            let v = v | (v >> T::from(16));
            v | (v >> T::from(32))
        }
        _ => v,
    };
    res + T::from(1)
}

/// Kinds of allocation initialization.
pub enum AllocationKind {
    /// Allocation should be zeroed.
    Zeroed,
    /// Allocation can be uninitialized.
    Uninitialized,
}

/// Allocates `count` number of elements of type T, using the `allocator`.
pub(crate) fn allocate<T, A: Allocator>(
    allocator: &A,
    count: usize,
    kind: AllocationKind,
) -> *mut T {
    let size = size_of::<T>();
    let align = align_of::<T>();

    // We unwrap here because we want to panic if we fail to get a valid layout
    let layout = Layout::from_size_align(size * count, align).unwrap();

    // Again, unwrap the allocation result. It should never fail to allocate.
    match kind {
        AllocationKind::Zeroed => allocator.allocate_zeroed(layout).unwrap().as_ptr() as *mut T,
        AllocationKind::Uninitialized => allocator.allocate(layout).unwrap().as_ptr() as *mut T,
    }
}

/// Deallocates `count` number of elements of type T, using the `allocator`.
pub(crate) fn deallocate<T, A: Allocator>(allocator: &A, ptr: *mut T, count: usize) {
    let size = size_of::<T>();
    let align = align_of::<T>();

    // We unwrap here because we want to panic if we fail to get a valid layout
    let layout = Layout::from_size_align(size * count, align).unwrap();

    // Again, unwrap the allocation result. It should never fail to allocate.
    let raw_ptr = ptr as *mut u8;
    let nonnull_ptr = std::ptr::NonNull::new(raw_ptr).unwrap();
    unsafe {
        allocator.deallocate(nonnull_ptr, layout);
    }
}