alt_std/
hashmap.rs

1//
2// Based on SkTHash.h from Skia
3// Copyright 2019 Wael El Oraiby
4// Copyright 2015 Google Inc.
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9//    * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11//    * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15//    * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30//
31use core::*;
32use crate::mem::*;
33use crate::hash::*;
34
35
36struct KeyValue<K : Hash + PartialEq, V> {
37    hash    : usize,
38    key     : K,
39    value   : V,
40}
41
42impl<K: Hash + PartialEq, V> KeyValue<K, V> {
43    pub fn isEmpty(&self) -> bool { self.hash == 0 }
44}
45
46pub struct HashMap<K: Hash + PartialEq, V> {
47    table   : Unique<KeyValue<K, V>>,
48    capacity: usize,
49    count   : usize,
50}
51
52impl<K: Hash + PartialEq, V> HashMap<K, V> {
53    pub fn new() -> Self {
54        Self {
55            table   : Unique::new(ptr::null_mut()),
56            count   : 0,
57            capacity: 0,
58        }
59    }
60
61    pub fn count(&self) -> usize { self.count }
62
63    #[inline]
64    fn hash(k: &K) -> usize {
65        match k.hash() {
66            0 => 1,
67            h => h,
68        }
69    }
70
71    #[inline]
72    fn next(&self, index: isize) -> isize {
73        let mut ret = index - 1;
74        if ret < 0 { ret += self.capacity as isize }
75        ret
76    }
77
78    fn uncheckedSet(&mut self, k: K, v: V) {
79        let hash    = Self::hash(&k);
80        let mut index   = (hash & (self.capacity - 1)) as isize;
81        let entries = unsafe { core::slice::from_raw_parts_mut(self.table.getMutPtr(), self.capacity) };
82
83        for _ in 0..self.capacity {
84            let mut e = &mut entries[index as usize];
85            if e.isEmpty() {
86                e.key   = k;
87                e.value = v;
88                e.hash  = hash;
89                self.count += 1;
90                return;
91            }
92
93            if hash == e.hash && k == e.key {
94                e.value = v;
95                return;
96            }
97
98            index = self.next(index);
99        }
100        panic!("uncheckedSet shouldn't reach this point");
101    }
102
103    fn newWithCap(cap: usize) -> Self {
104        Self {
105            table   : Unique::new(unsafe { allocRaw(cap * ::core::mem::size_of::<KeyValue<K, V>>()) as *mut KeyValue<K, V> }),
106            count   : 0,
107            capacity: cap,
108        }
109    }
110
111    fn grow(&mut self, newCap: usize) {
112        let oldEntries  = unsafe { core::slice::from_raw_parts(self.table.getPtr(), self.capacity) };
113        let mut newHM   = HashMap::<K, V>::newWithCap(newCap);
114        for o in oldEntries {
115            if !o.isEmpty() {
116                unsafe {
117                newHM.uncheckedSet(::core::ptr::read_unaligned(&o.key),
118                                   ::core::ptr::read_unaligned(&o.value));
119                }
120            }
121        }
122
123        self.count  = 0;
124        self.capacity = 0;
125        unsafe { free(self.table.getMutPtr()) };
126        *self = newHM;
127    }
128
129    pub fn set(&mut self, k: K, v: V) {
130        if 4 * self.count >= 3 * self.capacity {
131            self.grow(if self.capacity == 0 { 4 } else { self.capacity * 2 });
132        }
133        self.uncheckedSet(k, v)
134    }
135
136    pub fn exist(&self, k: K) -> bool {
137        let hash = Self::hash(&k);
138        let mut index   = (hash & (self.capacity - 1)) as isize;
139        let entries = unsafe { core::slice::from_raw_parts(self.table.getPtr(), self.capacity) };
140
141        for _ in 0..self.capacity {
142            let e = &entries[index as usize];
143            if e.isEmpty() {
144                return false;
145            }
146
147            if hash == e.hash && k == e.key {
148                return true;
149            }
150
151            index = self.next(index);
152        }
153        false
154    }
155
156    pub fn get(&self, k: K) -> Option<&V> {
157        let hash = Self::hash(&k);
158        let mut index   = (hash & (self.capacity - 1)) as isize;
159        let entries = unsafe { core::slice::from_raw_parts(self.table.getPtr(), self.capacity) };
160
161        for _ in 0..self.capacity {
162            let e = &entries[index as usize];
163            if e.isEmpty() {
164                return None;
165            }
166
167            if hash == e.hash && k == e.key {
168                return Some(&e.value);
169            }
170
171            index = self.next(index);
172        }
173        None
174    }
175
176    pub fn remove(&mut self, k: K) {
177        let hash = Self::hash(&k);
178        let mut index   = (hash & (self.capacity - 1)) as isize;
179        let entries = unsafe { core::slice::from_raw_parts_mut(self.table.getMutPtr(), self.capacity) };
180
181        for _ in 0..self.capacity {
182            let e = &entries[index as usize];
183            if e.isEmpty() {
184                return;
185            }
186
187            if hash == e.hash && k == e.key {
188                self.count -= 1;
189                break;
190            }
191
192            index = self.next(index);
193        }
194
195        loop {
196            let emptyIndex = index;
197            let mut originalIndex;
198            loop {
199                index = self.next(index);
200                let s = &entries[index as usize];
201                if s.isEmpty() {
202                    entries[emptyIndex as usize].hash = 0;
203                    unsafe { ::core::ptr::read_unaligned(&entries[emptyIndex as usize]) };  // drop it!
204                    return;
205                }
206
207                originalIndex   = (s.hash & (self.capacity - 1)) as isize;
208
209                if ! ((index <= originalIndex && originalIndex < emptyIndex)
210                    || (originalIndex < emptyIndex && emptyIndex < index)
211                    || (emptyIndex < index && index <= originalIndex)) {
212                    break;
213                }
214            }
215
216            entries[emptyIndex as usize] = unsafe { ::core::ptr::read_unaligned(&entries[index as usize]) };
217            entries[index as usize].hash = 0;
218        }
219    }
220}
221
222impl<K : Hash + PartialEq, V> Drop for HashMap<K, V> {
223    fn drop(&mut self) {
224            if self.capacity > 0 {
225            let arr      = unsafe { core::slice::from_raw_parts_mut(self.table.getMutPtr(), self.capacity) };
226            for kv in arr {
227                if !kv.isEmpty() {
228                    unsafe { ptr::drop_in_place(&kv.key as *const K as *mut K) };
229                    unsafe { ptr::drop_in_place(&kv.value as *const V as *mut V) };
230                }
231            }
232            unsafe { free(self.table.getMutPtr()) }
233        }
234    }
235}
236
237impl Hash for i32 {
238    fn hash(&self) -> usize { *self as usize }
239}
240
241#[cfg(test)]
242mod test {
243    use super::*;
244    use crate::vec::*;
245
246    #[test]
247    fn testInsert() {
248        let mut hm = HashMap::<i32, i32>::new();
249        for i in 0..100 {
250            hm.set(i, i * 2);
251        }
252
253        for i in 0..100 {
254            let ret = hm.get(i);
255            assert!(ret.is_some());
256            match ret {
257                Some(o) => assert!(*o == i * 2),
258                None => assert!(false)
259            }
260        }
261    }
262
263    #[test]
264    fn testRemove() {
265        let mut hm = HashMap::<i32, i32>::new();
266        for i in 0..100 {
267            hm.set(i, i * 2);
268        }
269
270        for i in 45..55 {
271            hm.remove(i);
272            assert!(hm.exist(i) == false);
273        }
274
275        for i in 0..45 {
276            let ret = hm.get(i);
277            assert!(ret.is_some());
278            match ret {
279                Some(o) => assert!(*o == i * 2),
280                None => assert!(false)
281            }
282        }
283
284        for i in 55..100 {
285            let ret = hm.get(i);
286            assert!(ret.is_some());
287            match ret {
288                Some(o) => assert!(*o == i * 2),
289                None => assert!(false)
290            }
291        }
292
293        for i in 45..55 {
294            assert!(hm.exist(i) == false);
295        }
296
297        assert!(hm.count() == 90);
298    }
299
300    #[test]
301    fn testVecInsert() {
302        let mut hm = HashMap::<i32, Vec<i32>>::new();
303        for i in 0..100 {
304            let mut v = Vec::new();
305            for j in 0..i * 2 {
306                v.pushBack(j);
307            }
308            hm.set(i, v);
309        }
310
311        for i in 0..100 {
312            let ret = hm.get(i);
313            assert!(ret.is_some());
314            match ret {
315                Some(o) => {
316                    for j in 0..i*2 {
317                        assert!((*o)[j as usize] == j)
318                    }
319                }
320                None => assert!(false)
321            }
322        }
323    }
324
325    #[test]
326    fn testVecRemove() {
327        let mut hm = HashMap::<i32, Vec<i32>>::new();
328        for i in 0..100 {
329            let mut v = Vec::new();
330            for j in 0..i * 2 {
331                v.pushBack(j);
332            }
333            hm.set(i, v);
334        }
335
336        for i in 45..55 {
337            hm.remove(i);
338            assert!(hm.exist(i) == false);
339        }
340
341        for i in 0..45 {
342            let ret = hm.get(i);
343            assert!(ret.is_some());
344            match ret {
345                Some(o) => {
346                    for j in 0..i*2 {
347                        assert!((*o)[j as usize] == j)
348                    }
349                },
350                None => assert!(false)
351            }
352        }
353
354        for i in 55..100 {
355            let ret = hm.get(i);
356            assert!(ret.is_some());
357            match ret {
358                Some(o) => {
359                    for j in 0..i*2 {
360                        assert!((*o)[j as usize] == j)
361                    }
362                },
363                None => assert!(false)
364            }
365        }
366
367        for i in 45..55 {
368            assert!(hm.exist(i) == false);
369        }
370
371        assert!(hm.count() == 90);
372    }
373}
alt_std/hashmap.rs

alt_std/
hashmap.rs
