rangetree 0.1.2

Range-tree for storing non-overlapping scalar ranges.
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
113
114
115
116
117

// Apache License, Version 2.0
// (c) Campbell Barton, 2016

/// This module handles many small allocations of the same type
/// using memory chunks and a single linked list for a free-chain of elements.
///
/// Users of this API need to define get/set methods
/// so they can be members of the free-chain.

use std::ptr;

pub trait MemElemUtils {
    fn free_ptr_get(&self) -> *mut Self;
    fn free_ptr_set(&mut self, ptr: *mut Self);
}

pub trait MemElem:
    MemElemUtils +
    Default +
    {}

impl<TElem> MemElem for TElem where TElem:
    MemElemUtils +
    Default +
    {}

struct MemChunk<TElem: MemElem> {
    data: Vec<TElem>,
}

pub struct MemPool<TElem: MemElem> {
    /// Data storage.
    chunks: Vec<MemChunk<TElem>>,
    /// Number of elements per chunk.
    chunk_size: usize,
    /// Single linked list of freed elements to be reused.
    /// `free_ptr_get` is used to store the *chain* terminating at `null`.
    free: *mut TElem,
}

impl <TElem: MemElem> MemPool<TElem> {
    pub fn new(
        chunk_size: usize,
    ) -> MemPool<TElem> {
        MemPool {
            chunks: vec![
                MemChunk {
                    data: Vec::with_capacity(chunk_size),
                },
            ],
            chunk_size: chunk_size,
            free: ptr::null_mut(),
        }
    }

    pub fn clear(
        &mut self,
    ) {
        self.chunks.truncate(1);
        self.chunks[0].data.clear();
        debug_assert!(self.chunks[0].data.capacity() == self.chunk_size);
        self.free = ptr::null_mut();
    }

    #[allow(dead_code)]
    pub fn alloc_elem(
        &mut self,
    ) -> *mut TElem {
        if self.free.is_null() {
            if self.chunks.last().unwrap().data.len() == self.chunk_size {
                self.chunks.push(MemChunk {
                    data: Vec::with_capacity(self.chunk_size),
                });
            }
            let chunk = self.chunks.last_mut().unwrap();
            chunk.data.push(TElem::default());
            return chunk.data.last_mut().unwrap();
        } else {
            let elem = self.free;
            self.free = unsafe { (*elem).free_ptr_get() };
            return unsafe { &mut *elem };
        }
    }

    pub fn alloc_elem_from(
        &mut self,
        from: TElem,
    ) -> *mut TElem {
        if self.free.is_null() {
            if self.chunks.last().unwrap().data.len() == self.chunk_size {
                self.chunks.push(MemChunk {
                    data: Vec::with_capacity(self.chunk_size),
                });
            }
            let chunk = self.chunks.last_mut().unwrap();
            chunk.data.push(from);
            return chunk.data.last_mut().unwrap();
        } else {
            let elem = self.free;
            unsafe {
                self.free = (*elem).free_ptr_get();
                ptr::write(elem, from);
            }
            return unsafe { &mut *elem };
        }
    }

    pub fn free_elem(
        &mut self,
        elem: *mut TElem,
    ) {
        unsafe {
            (*elem).free_ptr_set(self.free);
        }
        self.free = elem;
    }
}