simple_slab/
lib.rs

1// Copyright 2016 Nathan Sizemore <nathanrsizemore@gmail.com>
2//
3// This Source Code Form is subject to the terms of the Mozilla Public
4// License, v. 2.0. If a copy of the MPL was not distributed with this file,
5// You can obtain one at http://mozilla.org/MPL/2.0/.
6
7//! Fast and lightweight Slab Allocator.
8
9extern crate libc;
10
11use std::iter::{IntoIterator, Iterator};
12use std::ops::{Drop, Index};
13use std::{mem, ptr};
14
15pub struct Slab<T> {
16    capacity: usize,
17    len: usize,
18    mem: *mut T,
19}
20
21pub struct SlabIter<'a, T: 'a> {
22    slab: &'a Slab<T>,
23    current_offset: usize,
24}
25
26pub struct SlabMutIter<'a, T: 'a> {
27    iter: SlabIter<'a, T>,
28}
29
30impl<T> Slab<T> {
31    /// Creates a new Slab
32    pub fn new() -> Slab<T> {
33        Slab::with_capacity(1)
34    }
35
36    /// Creates a new, empty Slab with room for `capacity` elems
37    ///
38    /// # Panics
39    ///
40    /// * If the host system is out of memory
41    pub fn with_capacity(capacity: usize) -> Slab<T> {
42        let maybe_ptr =
43            unsafe { libc::malloc(mem::size_of::<T>() * capacity) as *mut T };
44
45        // malloc will return NULL if called with zero
46        if maybe_ptr.is_null() && capacity != 0 {
47            panic!("Unable to allocate requested capacity")
48        }
49
50        return Slab {
51            capacity: capacity,
52            len: 0,
53            mem: maybe_ptr,
54        };
55    }
56
57    /// Inserts a new element into the slab, re-allocating if neccessary.
58    ///
59    /// # Panics
60    ///
61    /// * If the host system is out of memory.
62    #[inline]
63    pub fn insert(&mut self, elem: T) {
64        if self.len == self.capacity {
65            self.reallocate();
66        }
67
68        unsafe {
69            let ptr = self.mem.offset(self.len as isize);
70            ptr::write(ptr, elem);
71        }
72
73        self.len += 1;
74    }
75
76    /// Removes the element at `offset`.
77    ///
78    /// # Panics
79    ///
80    /// * If `offset` is out of bounds.
81    #[inline]
82    pub fn remove(&mut self, offset: usize) -> T {
83        assert!(offset < self.len, "Offset out of bounds");
84
85        let elem: T;
86        let last_elem: T;
87        let elem_ptr: *mut T;
88        let last_elem_ptr: *mut T;
89
90        unsafe {
91            elem_ptr = self.mem.offset(offset as isize);
92            last_elem_ptr = self.mem.offset((self.len - 1) as isize);
93
94            elem = ptr::read(elem_ptr);
95            last_elem = ptr::read(last_elem_ptr);
96
97            ptr::write(elem_ptr, last_elem);
98        }
99
100        self.len -= 1;
101        return elem;
102    }
103
104    /// Returns the number of elements in the slab
105    #[inline]
106    pub fn len(&self) -> usize {
107        self.len
108    }
109
110    /// Returns an iterator over the slab
111    #[inline]
112    pub fn iter(&self) -> SlabIter<T> {
113        SlabIter {
114            slab: self,
115            current_offset: 0,
116        }
117    }
118
119    /// Returns a mutable iterator over the slab
120    #[inline]
121    pub fn iter_mut(&mut self) -> SlabMutIter<T> {
122        SlabMutIter { iter: self.iter() }
123    }
124
125    /// Reserves capacity * 2 extra space in this slab
126    ///
127    /// # Panics
128    ///
129    /// Panics if the host system is out of memory
130    #[inline]
131    fn reallocate(&mut self) {
132        let new_capacity = if self.capacity != 0 {
133            self.capacity * 2
134        } else {
135            1
136        };
137
138        let maybe_ptr = unsafe {
139            libc::realloc(
140                self.mem as *mut libc::c_void,
141                mem::size_of::<T>() * new_capacity,
142            ) as *mut T
143        };
144
145        assert!(!maybe_ptr.is_null(), "Out of Memory");
146
147        self.capacity = new_capacity;
148        self.mem = maybe_ptr;
149    }
150}
151
152impl<T> Drop for Slab<T> {
153    fn drop(&mut self) {
154        for x in 0..self.len() {
155            unsafe {
156                let elem_ptr = self.mem.offset(x as isize);
157                ptr::drop_in_place(elem_ptr);
158            }
159        }
160
161        unsafe { libc::free(self.mem as *mut _ as *mut libc::c_void) };
162    }
163}
164
165impl<T> Index<usize> for Slab<T> {
166    type Output = T;
167    fn index(&self, index: usize) -> &Self::Output {
168        assert!(index < self.len, "Index out of bounds");
169        unsafe { &(*(self.mem.offset(index as isize))) }
170    }
171}
172
173impl<'a, T> Iterator for SlabIter<'a, T> {
174    type Item = &'a T;
175    fn next(&mut self) -> Option<&'a T> {
176        while self.current_offset < self.slab.len() {
177            let offset = self.current_offset;
178            self.current_offset += 1;
179            unsafe {
180                return Some(&(*self.slab.mem.offset(offset as isize)));
181            }
182        }
183
184        None
185    }
186}
187
188impl<'a, T> Iterator for SlabMutIter<'a, T> {
189    type Item = &'a mut T;
190    fn next(&mut self) -> Option<&'a mut T> {
191        unsafe { mem::transmute(self.iter.next()) }
192    }
193}
194
195impl<'a, T> IntoIterator for &'a Slab<T> {
196    type Item = &'a T;
197    type IntoIter = SlabIter<'a, T>;
198    fn into_iter(self) -> SlabIter<'a, T> {
199        self.iter()
200    }
201}
202
203impl<'a, T> IntoIterator for &'a mut Slab<T> {
204    type Item = &'a mut T;
205    type IntoIter = SlabMutIter<'a, T>;
206    fn into_iter(self) -> SlabMutIter<'a, T> {
207        self.iter_mut()
208    }
209}
simple_slab/lib.rs

simple_slab/
lib.rs
