aboutsummaryrefslogtreecommitdiffhomepage
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/core/SkChecksum.h198
-rw-r--r--src/core/SkTHash.h292
-rw-r--r--src/utils/SkTLogic.h111
3 files changed, 0 insertions, 601 deletions
diff --git a/src/core/SkChecksum.h b/src/core/SkChecksum.h
deleted file mode 100644
index 8eb1766ec0..0000000000
--- a/src/core/SkChecksum.h
+++ /dev/null
@@ -1,198 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef SkChecksum_DEFINED
-#define SkChecksum_DEFINED
-
-#include "SkString.h"
-#include "SkTLogic.h"
-#include "SkTypes.h"
-
-/**
- * Computes a 32bit checksum from a blob of 32bit aligned data. This is meant
- * to be very very fast, as it is used internally by the font cache, in
- * conjuction with the entire raw key. This algorithm does not generate
- * unique values as well as others (e.g. MD5) but it performs much faster.
- * Skia's use cases can survive non-unique values (since the entire key is
- * always available). Clients should only be used in circumstances where speed
- * over uniqueness is at a premium.
- */
-class SkChecksum : SkNoncopyable {
-private:
- /*
- * Our Rotate and Mash helpers are meant to automatically do the right
- * thing depending if sizeof(uintptr_t) is 4 or 8.
- */
- enum {
- ROTR = 17,
- ROTL = sizeof(uintptr_t) * 8 - ROTR,
- HALFBITS = sizeof(uintptr_t) * 4
- };
-
- static inline uintptr_t Mash(uintptr_t total, uintptr_t value) {
- return ((total >> ROTR) | (total << ROTL)) ^ value;
- }
-
-public:
- /**
- * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you
- * suspect its low bits aren't well mixed.
- *
- * This is the Murmur3 finalizer.
- */
- static uint32_t Mix(uint32_t hash) {
- hash ^= hash >> 16;
- hash *= 0x85ebca6b;
- hash ^= hash >> 13;
- hash *= 0xc2b2ae35;
- hash ^= hash >> 16;
- return hash;
- }
-
- /**
- * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you
- * suspect its low bits aren't well mixed.
- *
- * This version is 2-lines cheaper than Mix, but seems to be sufficient for the font cache.
- */
- static uint32_t CheapMix(uint32_t hash) {
- hash ^= hash >> 16;
- hash *= 0x85ebca6b;
- hash ^= hash >> 16;
- return hash;
- }
-
- /**
- * Calculate 32-bit Murmur hash (murmur3).
- * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash.
- * See en.wikipedia.org/wiki/MurmurHash.
- *
- * @param data Memory address of the data block to be processed.
- * @param size Size of the data block in bytes.
- * @param seed Initial hash seed. (optional)
- * @return hash result
- */
- static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0) {
- // Use may_alias to remind the compiler we're intentionally violating strict aliasing,
- // and so not to apply strict-aliasing-based optimizations.
- typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t;
- typedef uint8_t SK_ATTRIBUTE(may_alias) aliased_uint8_t;
-
- // Handle 4 bytes at a time while possible.
- const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data;
- const size_t words = bytes/4;
- uint32_t hash = seed;
- for (size_t i = 0; i < words; i++) {
- uint32_t k = safe_data[i];
- k *= 0xcc9e2d51;
- k = (k << 15) | (k >> 17);
- k *= 0x1b873593;
-
- hash ^= k;
- hash = (hash << 13) | (hash >> 19);
- hash *= 5;
- hash += 0xe6546b64;
- }
-
- // Handle last 0-3 bytes.
- const aliased_uint8_t* safe_tail = (const uint8_t*)(safe_data + words);
- uint32_t k = 0;
- switch (bytes & 3) {
- case 3: k ^= safe_tail[2] << 16;
- case 2: k ^= safe_tail[1] << 8;
- case 1: k ^= safe_tail[0] << 0;
- k *= 0xcc9e2d51;
- k = (k << 15) | (k >> 17);
- k *= 0x1b873593;
- hash ^= k;
- }
-
- hash ^= bytes;
- return Mix(hash);
- }
-
- /**
- * Compute a 32-bit checksum for a given data block
- *
- * WARNING: this algorithm is tuned for efficiency, not backward/forward
- * compatibility. It may change at any time, so a checksum generated with
- * one version of the Skia code may not match a checksum generated with
- * a different version of the Skia code.
- *
- * @param data Memory address of the data block to be processed. Must be
- * 32-bit aligned.
- * @param size Size of the data block in bytes. Must be a multiple of 4.
- * @return checksum result
- */
- static uint32_t Compute(const uint32_t* data, size_t size) {
- // Use may_alias to remind the compiler we're intentionally violating strict aliasing,
- // and so not to apply strict-aliasing-based optimizations.
- typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t;
- const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data;
-
- SkASSERT(SkIsAlign4(size));
-
- /*
- * We want to let the compiler use 32bit or 64bit addressing and math
- * so we use uintptr_t as our magic type. This makes the code a little
- * more obscure (we can't hard-code 32 or 64 anywhere, but have to use
- * sizeof()).
- */
- uintptr_t result = 0;
- const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(safe_data);
-
- /*
- * count the number of quad element chunks. This takes into account
- * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t)
- * to compute how much to shift-down the size.
- */
- size_t n4 = size / (sizeof(uintptr_t) << 2);
- for (size_t i = 0; i < n4; ++i) {
- result = Mash(result, *ptr++);
- result = Mash(result, *ptr++);
- result = Mash(result, *ptr++);
- result = Mash(result, *ptr++);
- }
- size &= ((sizeof(uintptr_t) << 2) - 1);
-
- safe_data = reinterpret_cast<const aliased_uint32_t*>(ptr);
- const aliased_uint32_t* stop = safe_data + (size >> 2);
- while (safe_data < stop) {
- result = Mash(result, *safe_data++);
- }
-
- /*
- * smash us down to 32bits if we were 64. Note that when uintptr_t is
- * 32bits, this code-path should go away, but I still got a warning
- * when I wrote
- * result ^= result >> 32;
- * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS
- * define.
- */
- if (8 == sizeof(result)) {
- result ^= result >> HALFBITS;
- }
- return static_cast<uint32_t>(result);
- }
-};
-
-// SkGoodHash should usually be your first choice in hashing data.
-// It should be both reasonably fast and high quality.
-
-template <typename K>
-uint32_t SkGoodHash(const K& k) {
- if (sizeof(K) == 4) {
- return SkChecksum::Mix(*(const uint32_t*)&k);
- }
- return SkChecksum::Murmur3(&k, sizeof(K));
-}
-
-inline uint32_t SkGoodHash(const SkString& k) {
- return SkChecksum::Murmur3(k.c_str(), k.size());
-}
-
-#endif
diff --git a/src/core/SkTHash.h b/src/core/SkTHash.h
deleted file mode 100644
index ffcdea5329..0000000000
--- a/src/core/SkTHash.h
+++ /dev/null
@@ -1,292 +0,0 @@
-/*
- * Copyright 2015 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef SkTHash_DEFINED
-#define SkTHash_DEFINED
-
-#include "SkChecksum.h"
-#include "SkTypes.h"
-#include "SkTemplates.h"
-
-// Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you.
-// They're easier to use, usually perform the same, and have fewer sharp edges.
-
-// T and K are treated as ordinary copyable C++ types.
-// Traits must have:
-// - static K GetKey(T)
-// - static uint32_t Hash(K)
-// If the key is large and stored inside T, you may want to make K a const&.
-// Similarly, if T is large you might want it to be a pointer.
-template <typename T, typename K, typename Traits = T>
-class SkTHashTable : SkNoncopyable {
-public:
- SkTHashTable() : fCount(0), fRemoved(0), fCapacity(0) {}
-
- // Clear the table.
- void reset() {
- this->~SkTHashTable();
- SkNEW_PLACEMENT(this, SkTHashTable);
- }
-
- // How many entries are in the table?
- int count() const { return fCount; }
-
- // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!!
- // set(), find() and foreach() all allow mutable access to table entries.
- // If you change an entry so that it no longer has the same key, all hell
- // will break loose. Do not do that!
- //
- // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger.
-
- // The pointers returned by set() and find() are valid only until the next call to set().
- // The pointers you receive in foreach() are only valid for its duration.
-
- // Copy val into the hash table, returning a pointer to the copy now in the table.
- // If there already is an entry in the table with the same key, we overwrite it.
- T* set(const T& val) {
- if (4 * (fCount+fRemoved) >= 3 * fCapacity) {
- this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
- }
- return this->uncheckedSet(val);
- }
-
- // If there is an entry in the table with this key, return a pointer to it. If not, NULL.
- T* find(const K& key) const {
- uint32_t hash = Hash(key);
- int index = hash & (fCapacity-1);
- for (int n = 0; n < fCapacity; n++) {
- Slot& s = fSlots[index];
- if (s.empty()) {
- return NULL;
- }
- if (!s.removed() && hash == s.hash && key == Traits::GetKey(s.val)) {
- return &s.val;
- }
- index = this->next(index, n);
- }
- SkASSERT(fCapacity == 0);
- return NULL;
- }
-
- // Remove the value with this key from the hash table.
- void remove(const K& key) {
- SkASSERT(this->find(key));
-
- uint32_t hash = Hash(key);
- int index = hash & (fCapacity-1);
- for (int n = 0; n < fCapacity; n++) {
- Slot& s = fSlots[index];
- SkASSERT(!s.empty());
- if (!s.removed() && hash == s.hash && key == Traits::GetKey(s.val)) {
- fRemoved++;
- fCount--;
- s.markRemoved();
- return;
- }
- index = this->next(index, n);
- }
- SkASSERT(fCapacity == 0);
- }
-
- // Call fn on every entry in the table. You may mutate the entries, but be very careful.
- template <typename Fn> // f(T*)
- void foreach(Fn&& fn) {
- for (int i = 0; i < fCapacity; i++) {
- if (!fSlots[i].empty() && !fSlots[i].removed()) {
- fn(&fSlots[i].val);
- }
- }
- }
-
- // Call fn on every entry in the table. You may not mutate anything.
- template <typename Fn> // f(T) or f(const T&)
- void foreach(Fn&& fn) const {
- for (int i = 0; i < fCapacity; i++) {
- if (!fSlots[i].empty() && !fSlots[i].removed()) {
- fn(fSlots[i].val);
- }
- }
- }
-
-private:
- T* uncheckedSet(const T& val) {
- const K& key = Traits::GetKey(val);
- uint32_t hash = Hash(key);
- int index = hash & (fCapacity-1);
- for (int n = 0; n < fCapacity; n++) {
- Slot& s = fSlots[index];
- if (s.empty() || s.removed()) {
- // New entry.
- if (s.removed()) {
- fRemoved--;
- }
- s.val = val;
- s.hash = hash;
- fCount++;
- return &s.val;
- }
- if (hash == s.hash && key == Traits::GetKey(s.val)) {
- // Overwrite previous entry.
- // Note: this triggers extra copies when adding the same value repeatedly.
- s.val = val;
- return &s.val;
- }
- index = this->next(index, n);
- }
- SkASSERT(false);
- return NULL;
- }
-
- void resize(int capacity) {
- int oldCapacity = fCapacity;
- SkDEBUGCODE(int oldCount = fCount);
-
- fCount = fRemoved = 0;
- fCapacity = capacity;
- SkAutoTArray<Slot> oldSlots(capacity);
- oldSlots.swap(fSlots);
-
- for (int i = 0; i < oldCapacity; i++) {
- const Slot& s = oldSlots[i];
- if (!s.empty() && !s.removed()) {
- this->uncheckedSet(s.val);
- }
- }
- SkASSERT(fCount == oldCount);
- }
-
- int next(int index, int n) const {
- // A valid strategy explores all slots in [0, fCapacity) as n walks from 0 to fCapacity-1.
- // Both of these strategies are valid:
- //return (index + 0 + 1) & (fCapacity-1); // Linear probing.
- return (index + n + 1) & (fCapacity-1); // Quadratic probing.
- }
-
- static uint32_t Hash(const K& key) {
- uint32_t hash = Traits::Hash(key);
- return hash < 2 ? hash+2 : hash; // We reserve hash 0 and 1 to mark empty or removed slots.
- }
-
- struct Slot {
- Slot() : hash(0) {}
- bool empty() const { return this->hash == 0; }
- bool removed() const { return this->hash == 1; }
-
- void markRemoved() { this->hash = 1; }
-
- T val;
- uint32_t hash;
- };
-
- int fCount, fRemoved, fCapacity;
- SkAutoTArray<Slot> fSlots;
-};
-
-// Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases.
-// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two.
-template <typename K, typename V, uint32_t(*HashK)(const K&) = &SkGoodHash>
-class SkTHashMap : SkNoncopyable {
-public:
- SkTHashMap() {}
-
- // Clear the map.
- void reset() { fTable.reset(); }
-
- // How many key/value pairs are in the table?
- int count() const { return fTable.count(); }
-
- // N.B. The pointers returned by set() and find() are valid only until the next call to set().
-
- // Set key to val in the table, replacing any previous value with the same key.
- // We copy both key and val, and return a pointer to the value copy now in the table.
- V* set(const K& key, const V& val) {
- Pair in = { key, val };
- Pair* out = fTable.set(in);
- return &out->val;
- }
-
- // If there is key/value entry in the table with this key, return a pointer to the value.
- // If not, return NULL.
- V* find(const K& key) const {
- if (Pair* p = fTable.find(key)) {
- return &p->val;
- }
- return NULL;
- }
-
- // Remove the key/value entry in the table with this key.
- void remove(const K& key) {
- SkASSERT(this->find(key));
- fTable.remove(key);
- }
-
- // Call fn on every key/value pair in the table. You may mutate the value but not the key.
- template <typename Fn> // f(K, V*) or f(const K&, V*)
- void foreach(Fn&& fn) {
- fTable.foreach([&fn](Pair* p){ fn(p->key, &p->val); });
- }
-
- // Call fn on every key/value pair in the table. You may not mutate anything.
- template <typename Fn> // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&).
- void foreach(Fn&& fn) const {
- fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); });
- }
-
-private:
- struct Pair {
- K key;
- V val;
- static const K& GetKey(const Pair& p) { return p.key; }
- static uint32_t Hash(const K& key) { return HashK(key); }
- };
-
- SkTHashTable<Pair, K> fTable;
-};
-
-// A set of T. T is treated as an ordiary copyable C++ type.
-template <typename T, uint32_t(*HashT)(const T&) = &SkGoodHash>
-class SkTHashSet : SkNoncopyable {
-public:
- SkTHashSet() {}
-
- // Clear the set.
- void reset() { fTable.reset(); }
-
- // How many items are in the set?
- int count() const { return fTable.count(); }
-
- // Copy an item into the set.
- void add(const T& item) { fTable.set(item); }
-
- // Is this item in the set?
- bool contains(const T& item) const { return SkToBool(this->find(item)); }
-
- // If an item equal to this is in the set, return a pointer to it, otherwise null.
- // This pointer remains valid until the next call to add().
- const T* find(const T& item) const { return fTable.find(item); }
-
- // Remove the item in the set equal to this.
- void remove(const T& item) {
- SkASSERT(this->contains(item));
- fTable.remove(item);
- }
-
- // Call fn on every item in the set. You may not mutate anything.
- template <typename Fn> // f(T), f(const T&)
- void foreach (Fn&& fn) const {
- fTable.foreach(fn);
- }
-
-private:
- struct Traits {
- static const T& GetKey(const T& item) { return item; }
- static uint32_t Hash(const T& item) { return HashT(item); }
- };
- SkTHashTable<T, T, Traits> fTable;
-};
-
-#endif//SkTHash_DEFINED
diff --git a/src/utils/SkTLogic.h b/src/utils/SkTLogic.h
deleted file mode 100644
index d188242446..0000000000
--- a/src/utils/SkTLogic.h
+++ /dev/null
@@ -1,111 +0,0 @@
-/*
- * Copyright 2013 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- *
- *
- * This header provides some of the helpers (std::integral_constant) and
- * type transformations (std::conditional) which will become available with
- * C++11 in the type_traits header.
- *
- * Because we lack constexpr, we cannot mimic
- * std::integral_constant::'constexpr operator T()'.
- * As a result we introduce SkTBool and SkTIf similar to Boost in order to
- * minimize the visual noise of many uses of '::value'.
- */
-
-#ifndef SkTLogic_DEFINED
-#define SkTLogic_DEFINED
-
-/** Represents a templated integer constant.
- * Pre-C++11 version of std::integral_constant.
- */
-template <typename T, T v> struct SkTIntegralConstant {
- static const T value = v;
- typedef T value_type;
- typedef SkTIntegralConstant<T, v> type;
-};
-
-/** Convenience specialization of SkTIntegralConstant. */
-template <bool b> struct SkTBool : SkTIntegralConstant<bool, b> { };
-
-/** Pre-C++11 version of std::is_empty<T>. */
-template <typename T>
-class SkTIsEmpty {
- struct Derived : public T { char unused; };
-public:
- static const bool value = sizeof(Derived) == sizeof(char);
-};
-
-/** Pre-C++11 version of std::true_type. */
-typedef SkTBool<true> SkTrue;
-
-/** Pre-C++11 version of std::false_type. */
-typedef SkTBool<false> SkFalse;
-
-/** SkTIf_c::type = (condition) ? T : F;
- * Pre-C++11 version of std::conditional.
- */
-template <bool condition, typename T, typename F> struct SkTIf_c {
- typedef F type;
-};
-template <typename T, typename F> struct SkTIf_c<true, T, F> {
- typedef T type;
-};
-
-/** SkTIf::type = (Condition::value) ? T : F; */
-template <typename Condition, typename T, typename F> struct SkTIf {
- typedef typename SkTIf_c<static_cast<bool>(Condition::value), T, F>::type type;
-};
-
-/** SkTMux::type = (a && b) ? Both : (a) ? A : (b) ? B : Neither; */
-template <typename a, typename b, typename Both, typename A, typename B, typename Neither>
-struct SkTMux {
- typedef typename SkTIf<a, typename SkTIf<b, Both, A>::type,
- typename SkTIf<b, B, Neither>::type>::type type;
-};
-
-/** SkTEnableIf_c::type = (condition) ? T : [does not exist]; */
-template <bool condition, class T = void> struct SkTEnableIf_c { };
-template <class T> struct SkTEnableIf_c<true, T> {
- typedef T type;
-};
-
-/** SkTEnableIf::type = (Condition::value) ? T : [does not exist]; */
-template <class Condition, class T = void> struct SkTEnableIf
- : public SkTEnableIf_c<static_cast<bool>(Condition::value), T> { };
-
-/** Use as a return type to enable a function only when cond_type::value is true,
- * like C++14's std::enable_if_t. E.g. (N.B. this is a dumb example.)
- * SK_WHEN(SkTrue, int) f(void* ptr) { return 1; }
- * SK_WHEN(!SkTrue, int) f(void* ptr) { return 2; }
- */
-#define SK_WHEN(cond_prefix, T) typename SkTEnableIf_c<cond_prefix::value, T>::type
-#define SK_WHEN_C(cond, T) typename SkTEnableIf_c<cond, T>::type
-
-// See http://en.wikibooks.org/wiki/More_C++_Idioms/Member_Detector
-#define SK_CREATE_MEMBER_DETECTOR(member) \
-template <typename T> \
-class HasMember_##member { \
- struct Fallback { int member; }; \
- struct Derived : T, Fallback {}; \
- template <typename U, U> struct Check; \
- template <typename U> static uint8_t func(Check<int Fallback::*, &U::member>*); \
- template <typename U> static uint16_t func(...); \
-public: \
- typedef HasMember_##member type; \
- static const bool value = sizeof(func<Derived>(NULL)) == sizeof(uint16_t); \
-}
-
-// Same sort of thing as SK_CREATE_MEMBER_DETECTOR, but checks for the existence of a nested type.
-#define SK_CREATE_TYPE_DETECTOR(type) \
-template <typename T> \
-class HasType_##type { \
- template <typename U> static uint8_t func(typename U::type*); \
- template <typename U> static uint16_t func(...); \
-public: \
- static const bool value = sizeof(func<T>(NULL)) == sizeof(uint8_t); \
-}
-
-#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-03 21:28:43 +0000