Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(254)

Side by Side Diff: runtime/platform/hashmap.h

Issue 2231123002: Retry: Fixes memory leaks in the eventhandler (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Remove include of <map> Created 4 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « runtime/bin/socket.cc ('k') | runtime/platform/hashmap.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 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 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. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 #ifndef PLATFORM_HASHMAP_H_ 5 #ifndef PLATFORM_HASHMAP_H_
6 #define PLATFORM_HASHMAP_H_ 6 #define PLATFORM_HASHMAP_H_
7 7
8 #include "platform/globals.h" 8 #include "platform/globals.h"
9 9
10 namespace dart { 10 namespace dart {
11 11
12 class HashMap { 12 class HashMap {
13 public: 13 public:
14 typedef bool (*MatchFun) (void* key1, void* key2); 14 typedef bool (*MatchFun) (void* key1, void* key2);
15 15
16 typedef void (*ClearFun) (void* value);
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
16 static bool SamePointerValue(void* key1, void* key2) { 24 static bool SamePointerValue(void* key1, void* key2) {
17 return key1 == key2; 25 return key1 == key2;
18 } 26 }
19 27
20 static uint32_t StringHash(char* key) { 28 static uint32_t StringHash(char* key) {
21 uint32_t hash_ = 0; 29 uint32_t hash_ = 0;
22 if (key == NULL) return hash_; 30 if (key == NULL) return hash_;
23 int len = strlen(key); 31 int len = strlen(key);
24 for (int i = 0; i < len; i++) { 32 for (int i = 0; i < len; i++) {
25 hash_ += key[i]; 33 hash_ += key[i];
26 hash_ += hash_ << 10; 34 hash_ += hash_ << 10;
27 hash_ ^= hash_ >> 6; 35 hash_ ^= hash_ >> 6;
28 } 36 }
29 hash_ += hash_ << 3; 37 hash_ += hash_ << 3;
30 hash_ ^= hash_ >> 11; 38 hash_ ^= hash_ >> 11;
31 hash_ += hash_ << 15; 39 hash_ += hash_ << 15;
32 return hash_ == 0 ? 1 : hash_; 40 return hash_ == 0 ? 1 : hash_;
33 } 41 }
34 42
35 static bool SameStringValue(void* key1, void* key2) { 43 static bool SameStringValue(void* key1, void* key2) {
36 return strcmp(reinterpret_cast<char*>(key1), 44 return strcmp(reinterpret_cast<char*>(key1),
37 reinterpret_cast<char*>(key2)) == 0; 45 reinterpret_cast<char*>(key2)) == 0;
38 } 46 }
39 47
40
41 // initial_capacity is the size of the initial hash map;
42 // it must be a power of 2 (and thus must not be 0).
43 HashMap(MatchFun match, uint32_t initial_capacity);
44
45 ~HashMap();
46
47 // HashMap entries are (key, value, hash) triplets. 48 // HashMap entries are (key, value, hash) triplets.
48 // Some clients may not need to use the value slot 49 // Some clients may not need to use the value slot
49 // (e.g. implementers of sets, where the key is the value). 50 // (e.g. implementers of sets, where the key is the value).
50 struct Entry { 51 struct Entry {
52 Entry() : key(NULL), value(NULL), hash(0) {}
51 void* key; 53 void* key;
52 void* value; 54 void* value;
53 uint32_t hash; // The full hash value for key. 55 uint32_t hash; // The full hash value for key.
54 }; 56 };
55 57
56 // If an entry with matching key is found, Lookup() 58 // If an entry with matching key is found, Lookup()
57 // returns that entry. If no matching entry is found, 59 // returns that entry. If no matching entry is found,
58 // but insert is set, a new entry is inserted with 60 // but insert is set, a new entry is inserted with
59 // corresponding key, key hash, and NULL value. 61 // corresponding key, key hash, and NULL value.
60 // Otherwise, NULL is returned. 62 // Otherwise, NULL is returned.
61 Entry* Lookup(void* key, uint32_t hash, bool insert); 63 Entry* Lookup(void* key, uint32_t hash, bool insert);
62 64
63 // Removes the entry with matching key. 65 // Removes the entry with matching key.
64 void Remove(void* key, uint32_t hash); 66 void Remove(void* key, uint32_t hash);
65 67
66 // Empties the hash map (occupancy() == 0). 68 // Empties the hash map (occupancy() == 0), and calls the function 'clear' on
67 void Clear(); 69 // each of the values if given.
70 void Clear(ClearFun clear = NULL);
71
72 // The number of entries stored in the table.
73 intptr_t size() const { return occupancy_; }
68 74
69 // The capacity of the table. The implementation 75 // The capacity of the table. The implementation
70 // makes sure that occupancy is at most 80% of 76 // makes sure that occupancy is at most 80% of
71 // the table capacity. 77 // the table capacity.
72 intptr_t capacity() const { return capacity_; } 78 intptr_t capacity() const { return capacity_; }
73 79
74 // Iteration 80 // Iteration
75 // 81 //
76 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 82 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
77 // ... 83 // ...
78 // } 84 // }
79 // 85 //
80 // If entries are inserted during iteration, the effect of 86 // If entries are inserted during iteration, the effect of
81 // calling Next() is undefined. 87 // calling Next() is undefined.
82 Entry* Start() const; 88 Entry* Start() const;
83 Entry* Next(Entry* p) const; 89 Entry* Next(Entry* p) const;
84 90
85 private: 91 private:
86 MatchFun match_; 92 MatchFun match_;
87 Entry* map_; 93 Entry* map_;
88 uint32_t capacity_; 94 uint32_t capacity_;
89 uint32_t occupancy_; 95 uint32_t occupancy_;
90 96
91 Entry* map_end() const { return map_ + capacity_; } 97 Entry* map_end() const { return map_ + capacity_; }
92 Entry* Probe(void* key, uint32_t hash); 98 Entry* Probe(void* key, uint32_t hash);
93 void Initialize(uint32_t capacity); 99 void Initialize(uint32_t capacity);
94 void Resize(); 100 void Resize();
95 101
96 friend class IntSet; // From hashmap_test.cc 102 friend class IntSet; // From hashmap_test.cc
103 DISALLOW_COPY_AND_ASSIGN(HashMap);
97 }; 104 };
98 105
99 } // namespace dart 106 } // namespace dart
100 107
101 #endif // PLATFORM_HASHMAP_H_ 108 #endif // PLATFORM_HASHMAP_H_
OLDNEW
« no previous file with comments | « runtime/bin/socket.cc ('k') | runtime/platform/hashmap.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698