Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code

Unified Diff: compiled/Map.h

Issue 29572731: Issue 5141 - Generalize Map class to allow non-strings as keys (Closed) Base URL: https://hg.adblockplus.org/adblockpluscore
Patch Set: Introduced key_type_cref Created Dec. 4, 2017, 1:43 p.m.
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: compiled/Map.h
===================================================================
copy from compiled/StringMap.h
copy to compiled/Map.h
--- a/compiled/StringMap.h
+++ b/compiled/Map.h
@@ -12,42 +12,41 @@
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
-#include <cstddef>
#include <cmath>
#include <initializer_list>
#include <memory>
+#include "debug.h"
#include "String.h"
-#include "debug.h"
-template<typename T>
-class StringMap;
+template<typename Entry>
+class Map;
-namespace StringMap_internal
+namespace Map_internal
{
template<typename Entry>
struct HashContainerIterator
{
typedef Entry entry_type;
typedef HashContainerIterator<Entry> iterator;
const entry_type* mPos;
const entry_type* mEnd;
explicit HashContainerIterator(const entry_type* start, const entry_type* end)
: mPos(start), mEnd(end)
{
- if (mPos != mEnd && mPos->first.is_invalid())
+ if (mPos != mEnd && mPos->is_invalid())
++(*this);
}
const entry_type& operator*() const
{
return *mPos;
}
@@ -55,17 +54,17 @@ namespace StringMap_internal
{
return mPos;
}
iterator& operator++()
{
do {
++mPos;
- } while(mPos != mEnd && mPos->first.is_invalid());
+ } while(mPos != mEnd && mPos->is_invalid());
return *this;
}
bool operator==(const iterator& it) const
{
return mPos == it.mPos;
}
@@ -89,26 +88,27 @@ namespace StringMap_internal
const entry_type* operator->() const
{
return mEntry;
}
operator bool() const
{
- return !mEntry->first.is_invalid();
+ return !mEntry->is_invalid();
}
};
template<typename Entry>
class HashContainer
{
public:
typedef Entry entry_type;
- typedef size_t size_type;
+ typedef typename Entry::key_type_cref key_type_cref;
+ typedef typename entry_type::size_type size_type;
typedef HashContainerIterator<Entry> const_iterator;
typedef HashContainerReference<const Entry> const_reference;
private:
explicit HashContainer(const HashContainer& other);
void operator=(const HashContainer& other);
protected:
@@ -117,50 +117,28 @@ namespace StringMap_internal
std::unique_ptr<entry_type[]> mBuckets;
size_type mBucketCount;
size_type mEntryCount;
#if defined(DEBUG)
size_type mInsertCounter;
#endif
- explicit HashContainer(size_type expectedEntries = 0)
- : mEntryCount(0)
+ entry_type* find_bucket(key_type_cref key) const
{
- expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
- mBucketCount = MIN_BUCKETS;
- while (mBucketCount < expectedEntries)
- mBucketCount <<= 1;
-
- mBuckets.reset(new entry_type[mBucketCount]);
- // Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
- annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash table buffer");
- }
-
- static size_type hash(const String& str)
- {
- // FNV-1a hash function
- size_type result = 2166136261;
- for (String::size_type i = 0; i < str.length(); i++)
- result = (result ^ str[i]) * 16777619;
- return result;
- }
-
- entry_type* find_bucket(const String& key) const
- {
- size_type h = hash(key);
+ size_type h = entry_type::hash(key);
// This does quadratic probing, effectively the following formula is used:
// pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
for (size_type i = 0; ; ++i)
{
// mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
// h % mBucketCount but significantly faster.
entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
- if (entry->first.is_invalid() || entry->first.equals(key))
+ if (entry->is_invalid() || entry->equals(key))
return entry;
h += i;
}
}
void resize(size_type bucketCount)
{
std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
@@ -171,59 +149,72 @@ namespace StringMap_internal
mBuckets.reset(new entry_type[mBucketCount]);
// Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash table buffer");
// Copy old entries into the new buffer
for (size_type i = 0; i < oldCount; i++)
{
entry_type& entry = oldBuckets[i];
- if (!entry.first.is_invalid() && !entry.first.is_deleted())
+ if (!entry.is_invalid() && !entry.is_deleted())
{
*find_bucket(entry.first) = entry;
mEntryCount++;
}
}
}
entry_type* assign(entry_type* existing, const entry_type& entry)
{
- if (existing->first.is_invalid())
+ if (existing->is_invalid())
{
if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
{
resize(mBucketCount << 1);
existing = find_bucket(entry.first);
}
mEntryCount++;
#if defined(DEBUG)
mInsertCounter++;
#endif
}
*existing = entry;
return existing;
}
public:
+ explicit HashContainer(size_type expectedEntries = 0)
+ : mEntryCount(0)
+ {
+ expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
+ mBucketCount = MIN_BUCKETS;
+ while (mBucketCount < expectedEntries)
+ mBucketCount <<= 1;
+
+ mBuckets.reset(new entry_type[mBucketCount]);
+ // Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
+ annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash table buffer");
+ }
+
void insert(const entry_type& entry)
{
assign(find_bucket(entry.first), entry);
}
- bool erase(const String& key)
+ bool erase(key_type_cref key)
{
entry_type* entry = find_bucket(key);
- if (entry->first.is_invalid())
+ if (entry->is_invalid())
return false;
- entry->first.erase();
+ entry->erase();
return true;
}
- const_reference find(const String& key) const
+ const_reference find(key_type_cref key) const
{
return const_reference(find_bucket(key));
}
const_iterator begin() const
{
return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
}
@@ -234,124 +225,90 @@ namespace StringMap_internal
}
size_type size() const
{
return mEntryCount;
}
};
- struct StringSetEntry
- {
- StringSetEntry() {}
- StringSetEntry(const String& key)
- : first(key)
- {
- }
-
- DependentString first;
- };
-
- template<typename T>
- struct StringMapEntry
+ template<typename Entry>
+ struct MapReference : public HashContainerReference<Entry>
{
- StringMapEntry() {}
- StringMapEntry(const String& key)
- : first(key), second()
- {
- }
- StringMapEntry(const String& key, T value)
- : first(key), second(value)
- {
- }
-
- DependentString first;
- T second;
- };
-
- template<typename T>
- struct StringMapEntryReference : public HashContainerReference<StringMapEntry<T>>
- {
- typedef HashContainerReference<StringMapEntry<T>> super;
+ typedef HashContainerReference<Entry> super;
typedef typename super::entry_type entry_type;
- typedef StringMap<T> map_type;
+ typedef typename entry_type::key_type_cref key_type_cref;
+ typedef typename entry_type::value_type value_type;
+ typedef Map<entry_type> map_type;
map_type* mMap;
#if defined(DEBUG)
typename map_type::size_type mInsertCounter;
typename map_type::size_type mHash;
#endif
- StringMapEntryReference(map_type* map, const String& key, entry_type* entry)
+ MapReference(map_type* map, key_type_cref key, entry_type* entry)
: super(entry), mMap(map)
{
#if defined(DEBUG)
mInsertCounter = mMap->mInsertCounter;
- mHash = mMap->hash(key);
+ mHash = entry_type::hash(key);
#endif
}
- void assign(const String& key, const T& value)
+ void assign(key_type_cref key, const value_type& value)
{
#if defined(DEBUG)
assert2(mInsertCounter == mMap->mInsertCounter,
u"There should be no insert operations performed between map.find() and assign()"_str);
- assert2(mHash == mMap->hash(key),
+ assert2(mHash == entry_type::hash(key),
u"The keys used in map.find() and assign() should be identical"_str);
#endif
mMap->assign(this->mEntry, entry_type(key, value));
}
};
}
-class StringSet
- : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
-{
-};
+template<typename Entry>
+using Set = Map_internal::HashContainer<Entry>;
-template<typename T>
-class StringMap
- : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T>>
+template<typename Entry>
+class Map : public Map_internal::HashContainer<Entry>
{
public:
- typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T>> super;
+ typedef Map_internal::HashContainer<Entry> super;
typedef typename super::size_type size_type;
typedef typename super::entry_type entry_type;
+ typedef typename super::key_type_cref key_type_cref;
+ typedef typename entry_type::value_type value_type;
typedef typename super::const_reference const_reference;
- typedef StringMap_internal::StringMapEntryReference<T> reference;
- friend struct StringMap_internal::StringMapEntryReference<T>;
+ typedef Map_internal::MapReference<entry_type> reference;
+ friend struct Map_internal::MapReference<entry_type>;
- explicit StringMap(size_type expectedEntries = 0)
- : super(expectedEntries)
- {
- }
+ using super::super;
- StringMap(std::initializer_list<entry_type> list)
+ Map(std::initializer_list<entry_type> list)
: super(list.size())
{
for (const auto& item : list)
super::insert(item);
}
- ~StringMap()
- {
- }
-
- T& operator[](const String& key)
+ value_type& operator[](key_type_cref key)
{
entry_type* entry = super::find_bucket(key);
- if (entry->first.is_invalid())
+ if (entry->is_invalid())
entry = super::assign(entry, key);
return entry->second;
}
- const_reference find(const String& key) const
+ const_reference find(key_type_cref key) const
{
return super::find(key);
}
- reference find(const String& key)
+ reference find(key_type_cref key)
{
return reference(this, key, super::find_bucket(key));
}
};

Powered by Google App Engine
This is Rietveld