Index: src/base/hashmap.cc |
diff --git a/src/libsampler/hashmap.h b/src/base/hashmap.cc |
similarity index 58% |
copy from src/libsampler/hashmap.h |
copy to src/base/hashmap.cc |
index e4b3cc6009b977756f173d01fca426386358b499..bbfdd687c686eb8192f38d0c869a250e57d57b2d 100644 |
--- a/src/libsampler/hashmap.h |
+++ b/src/base/hashmap.cc |
@@ -2,138 +2,16 @@ |
// Use of this source code is governed by a BSD-style license that can be |
// found in the LICENSE file. |
-// This file is ported from src/hashmap.h |
- |
-#ifndef V8_LIBSAMPLER_HASHMAP_H_ |
-#define V8_LIBSAMPLER_HASHMAP_H_ |
- |
-#include "src/base/bits.h" |
-#include "src/base/logging.h" |
-#include "src/libsampler/utils.h" |
+#include "src/base/hashmap.h" |
namespace v8 { |
-namespace sampler { |
- |
-class HashMapImpl { |
- public: |
- typedef bool (*MatchFun) (void* key1, void* key2); |
- |
- // The default capacity. |
- static const uint32_t kDefaultHashMapCapacity = 8; |
- |
- // initial_capacity is the size of the initial hash map; |
- // it must be a power of 2 (and thus must not be 0). |
- HashMapImpl(MatchFun match, |
- uint32_t capacity = kDefaultHashMapCapacity); |
- |
- ~HashMapImpl(); |
- |
- // HashMap entries are (key, value, hash) triplets. |
- // Some clients may not need to use the value slot |
- // (e.g. implementers of sets, where the key is the value). |
- struct Entry { |
- void* key; |
- void* value; |
- uint32_t hash; // The full hash value for key |
- int order; // If you never remove entries this is the insertion order. |
- }; |
- |
- // If an entry with matching key is found, returns that entry. |
- // Otherwise, NULL is returned. |
- Entry* Lookup(void* key, uint32_t hash) const; |
- |
- // If an entry with matching key is found, returns that entry. |
- // If no matching entry is found, a new entry is inserted with |
- // corresponding key, key hash, and NULL value. |
- Entry* LookupOrInsert(void* key, uint32_t hash); |
- |
- // Removes the entry with matching key. |
- // It returns the value of the deleted entry |
- // or null if there is no value for such key. |
- void* Remove(void* key, uint32_t hash); |
- |
- // Empties the hash map (occupancy() == 0). |
- void Clear(); |
- |
- // The number of (non-empty) entries in the table. |
- uint32_t occupancy() const { return occupancy_; } |
- |
- // The capacity of the table. The implementation |
- // makes sure that occupancy is at most 80% of |
- // the table capacity. |
- uint32_t capacity() const { return capacity_; } |
- |
- // Iteration |
- // |
- // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { |
- // ... |
- // } |
- // |
- // If entries are inserted during iteration, the effect of |
- // calling Next() is undefined. |
- Entry* Start() const; |
- Entry* Next(Entry* p) const; |
- |
- // Some match functions defined for convenience. |
- static bool PointersMatch(void* key1, void* key2) { |
- return key1 == key2; |
- } |
- |
- private: |
- MatchFun match_; |
- Entry* map_; |
- uint32_t capacity_; |
- uint32_t occupancy_; |
- |
- Entry* map_end() const { return map_ + capacity_; } |
- Entry* Probe(void* key, uint32_t hash) const; |
- void Initialize(uint32_t capacity); |
- void Resize(); |
-}; |
- |
-typedef HashMapImpl HashMap; |
- |
-HashMapImpl::HashMapImpl(MatchFun match, uint32_t initial_capacity) { |
- match_ = match; |
- Initialize(initial_capacity); |
-} |
- |
- |
-HashMapImpl::~HashMapImpl() { |
- Malloced::Delete(map_); |
-} |
- |
+namespace base { |
HashMapImpl::Entry* HashMapImpl::Lookup(void* key, uint32_t hash) const { |
Entry* p = Probe(key, hash); |
return p->key != NULL ? p : NULL; |
} |
- |
-HashMapImpl::Entry* HashMapImpl::LookupOrInsert(void* key, uint32_t hash) { |
- // Find a matching entry. |
- Entry* p = Probe(key, hash); |
- if (p->key != NULL) { |
- return p; |
- } |
- |
- // No entry found; insert one. |
- p->key = key; |
- p->value = NULL; |
- p->hash = hash; |
- p->order = occupancy_; |
- occupancy_++; |
- |
- // Grow the map if we reached >= 80% occupancy. |
- if (occupancy_ + occupancy_ / 4 >= capacity_) { |
- Resize(); |
- p = Probe(key, hash); |
- } |
- |
- return p; |
-} |
- |
- |
void* HashMapImpl::Remove(void* key, uint32_t hash) { |
// Lookup the entry for the key to remove. |
Entry* p = Probe(key, hash); |
@@ -181,8 +59,7 @@ void* HashMapImpl::Remove(void* key, uint32_t hash) { |
// If the entry at position q has its initial position outside the range |
// between p and q it can be moved forward to position p and will still be |
// found. There is now a new candidate entry for clearing. |
- if ((q > p && (r <= p || r > q)) || |
- (q < p && (r <= p && r > q))) { |
+ if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { |
*p = *q; |
p = q; |
} |
@@ -194,7 +71,6 @@ void* HashMapImpl::Remove(void* key, uint32_t hash) { |
return value; |
} |
- |
void HashMapImpl::Clear() { |
// Mark all entries as empty. |
const Entry* end = map_end(); |
@@ -204,11 +80,7 @@ void HashMapImpl::Clear() { |
occupancy_ = 0; |
} |
- |
-HashMapImpl::Entry* HashMapImpl::Start() const { |
- return Next(map_ - 1); |
-} |
- |
+HashMapImpl::Entry* HashMapImpl::Start() const { return Next(map_ - 1); } |
HashMapImpl::Entry* HashMapImpl::Next(Entry* p) const { |
const Entry* end = map_end(); |
@@ -221,7 +93,6 @@ HashMapImpl::Entry* HashMapImpl::Next(Entry* p) const { |
return NULL; |
} |
- |
HashMapImpl::Entry* HashMapImpl::Probe(void* key, uint32_t hash) const { |
DCHECK(key != NULL); |
@@ -241,17 +112,37 @@ HashMapImpl::Entry* HashMapImpl::Probe(void* key, uint32_t hash) const { |
return p; |
} |
+HashMapImpl::Entry* HashMapImpl::LookupOrInsert(void* key, uint32_t hash) { |
Yang
2016/05/30 09:19:04
This is still very similar to TemplateHashMapImpl<
|
+ // Find a matching entry. |
+ Entry* p = Probe(key, hash); |
+ if (p->key != NULL) { |
+ return p; |
+ } |
-void HashMapImpl::Initialize(uint32_t capacity) { |
- DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
- map_ = reinterpret_cast<Entry*>(Malloced::New(capacity * sizeof(Entry))); |
- CHECK(map_ != NULL); |
- capacity_ = capacity; |
- Clear(); |
+ // No entry found; insert one. |
+ p->key = key; |
+ p->value = NULL; |
+ p->hash = hash; |
+ p->order = occupancy_; |
+ occupancy_++; |
+ |
+ // Grow the map if we reached >= 80% occupancy. |
+ if (occupancy_ + occupancy_ / 4 >= capacity_) { |
+ Resize(); |
+ p = Probe(key, hash); |
+ } |
+ |
+ return p; |
} |
+HashMap::HashMap(MatchFun match, uint32_t initial_capacity) : HashMapImpl() { |
+ match_ = match; |
+ Initialize(initial_capacity); |
+} |
-void HashMapImpl::Resize() { |
+HashMap::~HashMap() { free(map_); } |
+ |
+void HashMap::Resize() { |
Entry* map = map_; |
uint32_t n = occupancy_; |
@@ -269,10 +160,19 @@ void HashMapImpl::Resize() { |
} |
// Delete old map. |
- Malloced::Delete(map); |
+ free(map); |
} |
-} // namespace sampler |
-} // namespace v8 |
+void HashMap::Initialize(uint32_t capacity) { |
+ DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
+ map_ = reinterpret_cast<Entry*>(malloc(capacity * sizeof(Entry))); |
+ if (map_ == NULL) { |
+ FATAL("HashMapImpl::Initialize"); |
+ return; |
+ } |
+ capacity_ = capacity; |
+ Clear(); |
+} |
-#endif // V8_LIBSAMPLER_HASHMAP_H_ |
+} // namespace base |
+} // namespace v8 |