OLD | NEW |
| (Empty) |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | |
2 // for details. All rights reserved. Use of this source code is governed by a | |
3 // BSD-style license that can be found in the LICENSE file. | |
4 | |
5 #ifndef BIN_HASHMAP_H_ | |
6 #define BIN_HASHMAP_H_ | |
7 | |
8 #include "platform/globals.h" | |
9 | |
10 class HashMap { | |
11 public: | |
12 typedef bool (*MatchFun) (void* key1, void* key2); | |
13 | |
14 static bool SamePointerValue(void* key1, void* key2) { | |
15 return key1 == key2; | |
16 } | |
17 | |
18 // initial_capacity is the size of the initial hash map; | |
19 // it must be a power of 2 (and thus must not be 0). | |
20 HashMap(MatchFun match, uint32_t initial_capacity); | |
21 | |
22 ~HashMap(); | |
23 | |
24 // HashMap entries are (key, value, hash) triplets. | |
25 // Some clients may not need to use the value slot | |
26 // (e.g. implementers of sets, where the key is the value). | |
27 struct Entry { | |
28 void* key; | |
29 void* value; | |
30 uint32_t hash; // The full hash value for key. | |
31 }; | |
32 | |
33 // If an entry with matching key is found, Lookup() | |
34 // returns that entry. If no matching entry is found, | |
35 // but insert is set, a new entry is inserted with | |
36 // corresponding key, key hash, and NULL value. | |
37 // Otherwise, NULL is returned. | |
38 Entry* Lookup(void* key, uint32_t hash, bool insert); | |
39 | |
40 // Removes the entry with matching key. | |
41 void Remove(void* key, uint32_t hash); | |
42 | |
43 // Empties the hash map (occupancy() == 0). | |
44 void Clear(); | |
45 | |
46 // The capacity of the table. The implementation | |
47 // makes sure that occupancy is at most 80% of | |
48 // the table capacity. | |
49 intptr_t capacity() const { return capacity_; } | |
50 | |
51 // Iteration | |
52 // | |
53 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | |
54 // ... | |
55 // } | |
56 // | |
57 // If entries are inserted during iteration, the effect of | |
58 // calling Next() is undefined. | |
59 Entry* Start() const; | |
60 Entry* Next(Entry* p) const; | |
61 | |
62 private: | |
63 MatchFun match_; | |
64 Entry* map_; | |
65 uint32_t capacity_; | |
66 uint32_t occupancy_; | |
67 | |
68 Entry* map_end() const { return map_ + capacity_; } | |
69 Entry* Probe(void* key, uint32_t hash); | |
70 void Initialize(uint32_t capacity); | |
71 void Resize(); | |
72 | |
73 friend class IntSet; // From hashmap_test.cc | |
74 }; | |
75 | |
76 #endif // BIN_HASHMAP_H_ | |
OLD | NEW |