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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/base/hashmap.h

Issue 2354593002: [base] Template MatchFun in TemplateHashMapImpl (Closed)
Patch Set: Rebase after forgetting to rebase Created 4 years, 3 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/address-map.cc ('k') | src/gdb-jit.cc » ('j') | src/gdb-jit.cc » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/base/hashmap.h
diff --git a/src/base/hashmap.h b/src/base/hashmap.h
index 6bef83ed4d8c7cbb2d25c55625fd65ade6b58b00..37ee4498675ce39efd720bacc503045a2fb2713e 100644
--- a/src/base/hashmap.h
+++ b/src/base/hashmap.h
@@ -24,15 +24,9 @@ class DefaultAllocationPolicy {
V8_INLINE static void Delete(void* p) { free(p); }
};
-// Metaprogramming helper to allow pointer keys to be passed by value and
-// non-pointer keys by const reference.
-template <typename Key>
-struct MatchFunHelper;
-
-template <typename Key, typename Value, class AllocationPolicy>
+template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
class TemplateHashMapImpl {
public:
- typedef typename MatchFunHelper<Key>::Fun MatchFun;
typedef TemplateHashMapEntry<Key, Value> Entry;
// The default capacity. This is used by the call sites which want
@@ -42,7 +36,7 @@ class TemplateHashMapImpl {
// initial_capacity is the size of the initial hash map;
// it must be a power of 2 (and thus must not be 0).
- TemplateHashMapImpl(MatchFun match,
+ TemplateHashMapImpl(MatchFun match = MatchFun(),
uint32_t capacity = kDefaultHashMapCapacity,
AllocationPolicy allocator = AllocationPolicy());
@@ -86,20 +80,11 @@ class TemplateHashMapImpl {
Entry* Start() const;
Entry* Next(Entry* entry) const;
- // Some match functions defined for convenience.
- // TODO(leszeks): This isn't really matching pointers, so the name doesn't
- // really make sense, but we should remove this entirely and template the map
- // on the matching function.
- static bool PointersMatch(typename MatchFunHelper<Key>::KeyRef key1,
- typename MatchFunHelper<Key>::KeyRef key2) {
- return key1 == key2;
- }
-
private:
- MatchFun match_;
Entry* map_;
uint32_t capacity_;
uint32_t occupancy_;
+ MatchFun match_;
AllocationPolicy allocator_;
Entry* map_end() const { return map_ + capacity_; }
@@ -110,44 +95,35 @@ class TemplateHashMapImpl {
void Resize();
};
-template <typename Key>
-struct MatchFunHelper {
- typedef const Key& KeyRef;
- typedef bool (*Fun)(KeyRef key1, KeyRef key2);
-};
-
-template <typename Key>
-struct MatchFunHelper<Key*> {
- typedef Key* KeyRef;
- typedef bool (*Fun)(KeyRef key1, KeyRef key2);
-};
-
-typedef TemplateHashMapImpl<void*, void*, DefaultAllocationPolicy> HashMap;
-
-template <typename Key, typename Value, class AllocationPolicy>
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::TemplateHashMapImpl(
- MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator)
- : allocator_(allocator) {
- match_ = match;
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
+ TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity,
+ AllocationPolicy allocator)
+ : match_(match), allocator_(allocator) {
Initialize(initial_capacity);
}
-template <typename Key, typename Value, class AllocationPolicy>
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+TemplateHashMapImpl<Key, Value, MatchFun,
+ AllocationPolicy>::~TemplateHashMapImpl() {
allocator_.Delete(map_);
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key,
- uint32_t hash) const {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
+ const Key& key, uint32_t hash) const {
Entry* entry = Probe(key, hash);
return entry->exists() ? entry : nullptr;
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
const Key& key, uint32_t hash) {
// Find a matching entry.
Entry* entry = Probe(key, hash);
@@ -158,17 +134,19 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
return FillEmptyEntry(entry, key, Value(), hash);
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew(const Key& key,
- uint32_t hash) {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
+ const Key& key, uint32_t hash) {
Entry* entry = Probe(key, hash);
return FillEmptyEntry(entry, key, Value(), hash);
}
-template <typename Key, typename Value, class AllocationPolicy>
-Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
- uint32_t hash) {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
+ const Key& key, uint32_t hash) {
// Lookup the entry for the key to remove.
Entry* p = Probe(key, hash);
if (!p->exists()) {
@@ -227,8 +205,9 @@ Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
return value;
}
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() {
// Mark all entries as empty.
const Entry* end = map_end();
for (Entry* entry = map_; entry < end; entry++) {
@@ -237,15 +216,18 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
occupancy_ = 0;
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const {
return Next(map_ - 1);
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next(
+ Entry* entry) const {
const Entry* end = map_end();
DCHECK(map_ - 1 <= entry && entry < end);
for (entry++; entry < end; entry++) {
@@ -256,10 +238,11 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const {
return nullptr;
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
- uint32_t hash) const {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
+ const Key& key, uint32_t hash) const {
DCHECK(base::bits::IsPowerOfTwo32(capacity_));
Entry* entry = map_ + (hash & (capacity_ - 1));
const Entry* end = map_end();
@@ -276,9 +259,10 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
return entry;
}
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry(
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
Entry* entry, const Key& key, const Value& value, uint32_t hash) {
DCHECK(!entry->exists());
@@ -294,8 +278,9 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry(
return entry;
}
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
uint32_t capacity) {
DCHECK(base::bits::IsPowerOfTwo32(capacity));
map_ = reinterpret_cast<Entry*>(allocator_.New(capacity * sizeof(Entry)));
@@ -307,8 +292,9 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
Clear();
}
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
+template <typename Key, typename Value, typename MatchFun,
+ class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize() {
Entry* map = map_;
uint32_t n = occupancy_;
@@ -329,11 +315,35 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
allocator_.Delete(map);
}
+template <typename AllocationPolicy>
+class PointerTemplateHashMapImpl
+ : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+ AllocationPolicy> {
+ typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+ AllocationPolicy>
+ Base;
rmcilroy 2016/09/20 16:06:03 weird formating here - I guess this was git cl for
Leszek Swirski 2016/09/26 16:54:52 Not really, I could define the MatchFun typedef hi
+
+ public:
+ typedef bool (*MatchFun)(void*, void*);
+
+ PointerTemplateHashMapImpl(MatchFun match = PointersMatch,
+ uint32_t capacity = Base::kDefaultHashMapCapacity,
+ AllocationPolicy allocator = AllocationPolicy())
+ : Base(match, capacity, allocator) {}
+
+ static bool PointersMatch(void* key1, void* key2) { return key1 == key2; }
+};
+
+typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap;
+
// A hash map for pointer keys and values with an STL-like interface.
template <class Key, class Value, class AllocationPolicy>
-class TemplateHashMap
- : private TemplateHashMapImpl<void*, void*, AllocationPolicy> {
+class TemplateHashMap : private PointerTemplateHashMapImpl<AllocationPolicy> {
+ typedef PointerTemplateHashMapImpl<AllocationPolicy> Base;
+
public:
+ typedef bool (*MatchFun)(void*, void*);
+
STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT
STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT
struct value_type {
@@ -352,25 +362,18 @@ class TemplateHashMap
bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
private:
- Iterator(const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map,
- typename TemplateHashMapImpl<void*, void*,
- AllocationPolicy>::Entry* entry)
+ Iterator(const Base* map, typename Base::Entry* entry)
: map_(map), entry_(entry) {}
- const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map_;
- typename TemplateHashMapImpl<void*, void*, AllocationPolicy>::Entry* entry_;
+ const Base* map_;
+ typename Base::Entry* entry_;
friend class TemplateHashMap;
};
- TemplateHashMap(typename TemplateHashMapImpl<
- void*, void*, AllocationPolicy>::MatchFun match,
+ TemplateHashMap(MatchFun match,
AllocationPolicy allocator = AllocationPolicy())
- : TemplateHashMapImpl<void*, void*, AllocationPolicy>(
- match,
- TemplateHashMapImpl<void*, void*,
- AllocationPolicy>::kDefaultHashMapCapacity,
- allocator) {}
+ : Base(match, Base::kDefaultHashMapCapacity, allocator) {}
Iterator begin() const { return Iterator(this, this->Start()); }
Iterator end() const { return Iterator(this, nullptr); }
« no previous file with comments | « src/address-map.cc ('k') | src/gdb-jit.cc » ('j') | src/gdb-jit.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698