From a06f4849bc58cbe21b001f1f15fd0828bde9b79b Mon Sep 17 00:00:00 2001 From: Jesse Crocker Date: Fri, 8 Sep 2017 13:56:11 -0700 Subject: [core] Move *TileID hashing to separate impl --- cmake/core-files.cmake | 3 +- include/mbgl/tile/tile_id.hpp | 263 +++++++++++++++++++++++++++++++++++++++ src/mbgl/tile/tile_id.hpp | 276 ----------------------------------------- src/mbgl/tile/tile_id_hash.cpp | 29 +++++ 4 files changed, 294 insertions(+), 277 deletions(-) create mode 100644 include/mbgl/tile/tile_id.hpp delete mode 100644 src/mbgl/tile/tile_id.hpp create mode 100644 src/mbgl/tile/tile_id_hash.cpp diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake index 49697a5c29..c34a0724f4 100644 --- a/cmake/core-files.cmake +++ b/cmake/core-files.cmake @@ -490,6 +490,7 @@ set(MBGL_CORE_FILES src/mbgl/text/shaping.hpp # tile + include/mbgl/tile/tile_id.hpp src/mbgl/tile/geojson_tile.cpp src/mbgl/tile/geojson_tile.hpp src/mbgl/tile/geometry_tile.cpp @@ -506,7 +507,7 @@ set(MBGL_CORE_FILES src/mbgl/tile/tile.hpp src/mbgl/tile/tile_cache.cpp src/mbgl/tile/tile_cache.hpp - src/mbgl/tile/tile_id.hpp + src/mbgl/tile/tile_id_hash.cpp src/mbgl/tile/tile_id_io.cpp src/mbgl/tile/tile_loader.hpp src/mbgl/tile/tile_loader_impl.hpp diff --git a/include/mbgl/tile/tile_id.hpp b/include/mbgl/tile/tile_id.hpp new file mode 100644 index 0000000000..0457dd3a07 --- /dev/null +++ b/include/mbgl/tile/tile_id.hpp @@ -0,0 +1,263 @@ +#pragma once + +#include + +#include +#include +#include +#include +#include +#include +#include + +namespace mbgl { + +class OverscaledTileID; +class CanonicalTileID; +class UnwrappedTileID; + +// Has integer z/x/y coordinates +// All tiles must be derived from 0/0/0 (=no tiles outside of the main tile pyramid) +// Used for requesting data; represents data tiles that exist out there. +// z is never larger than the source's maxzoom +class CanonicalTileID { +public: + CanonicalTileID(uint8_t z, uint32_t x, uint32_t y); + bool operator==(const CanonicalTileID&) const; + bool operator!=(const CanonicalTileID&) const; + bool operator<(const CanonicalTileID&) const; + bool isChildOf(const CanonicalTileID&) const; + CanonicalTileID scaledTo(uint8_t z) const; + std::array children() const; + + const uint8_t z; + const uint32_t x; + const uint32_t y; +}; + +::std::ostream& operator<<(::std::ostream& os, const CanonicalTileID& rhs); +namespace util { +std::string toString(const CanonicalTileID&); +} // namespace util + +// Has integer z/x/y coordinates +// overscaledZ describes the zoom level this tile is intented to represent, e.g. when parsing data +// z is never larger than the source's maxzoom +// z/x/y describe the +class OverscaledTileID { +public: + OverscaledTileID(uint8_t overscaledZ, int16_t wrap, CanonicalTileID); + OverscaledTileID(uint8_t overscaledZ, int16_t wrap, uint8_t z, uint32_t x, uint32_t y); + OverscaledTileID(uint8_t z, uint32_t x, uint32_t y); + explicit OverscaledTileID(const CanonicalTileID&); + explicit OverscaledTileID(CanonicalTileID&&); + bool operator==(const OverscaledTileID&) const; + bool operator!=(const OverscaledTileID&) const; + bool operator<(const OverscaledTileID&) const; + bool isChildOf(const OverscaledTileID&) const; + uint32_t overscaleFactor() const; + OverscaledTileID scaledTo(uint8_t z) const; + UnwrappedTileID toUnwrapped() const; + + const uint8_t overscaledZ; + const int16_t wrap; + const CanonicalTileID canonical; +}; + +::std::ostream& operator<<(::std::ostream& os, const OverscaledTileID& rhs); +namespace util { +std::string toString(const OverscaledTileID&); +} // namespace util + +// Has integer z/x/y coordinates +// wrap describes tiles that are left/right of the main tile pyramid, e.g. when wrapping the world +// Used for describing what position tiles are getting rendered at (= calc the matrix) +// z is never larger than the source's maxzoom +class UnwrappedTileID { +public: + UnwrappedTileID(uint8_t z, int64_t x, int64_t y); + UnwrappedTileID(int16_t wrap, CanonicalTileID); + bool operator==(const UnwrappedTileID&) const; + bool operator!=(const UnwrappedTileID&) const; + bool operator<(const UnwrappedTileID&) const; + bool isChildOf(const UnwrappedTileID&) const; + std::array children() const; + OverscaledTileID overscaleTo(uint8_t z) const; + float pixelsToTileUnits(float pixelValue, float zoom) const; + + const int16_t wrap; + const CanonicalTileID canonical; +}; + +::std::ostream& operator<<(::std::ostream& os, const UnwrappedTileID& rhs); +namespace util { +std::string toString(const UnwrappedTileID&); +} // namespace util + +inline CanonicalTileID::CanonicalTileID(uint8_t z_, uint32_t x_, uint32_t y_) : z(z_), x(x_), y(y_) { + assert(z <= 32); + assert(x < (1ull << z)); + assert(y < (1ull << z)); +} + +inline bool CanonicalTileID::operator==(const CanonicalTileID& rhs) const { + return z == rhs.z && x == rhs.x && y == rhs.y; +} + +inline bool CanonicalTileID::operator!=(const CanonicalTileID& rhs) const { + return z != rhs.z || x != rhs.x || y != rhs.y; +} + +inline bool CanonicalTileID::operator<(const CanonicalTileID& rhs) const { + return std::tie(z, x, y) < std::tie(rhs.z, rhs.x, rhs.y); +} + +inline bool CanonicalTileID::isChildOf(const CanonicalTileID& parent) const { + // We're first testing for z == 0, to avoid a 32 bit shift, which is undefined. + return parent.z == 0 || + (parent.z < z && parent.x == (x >> (z - parent.z)) && parent.y == (y >> (z - parent.z))); +} + +inline CanonicalTileID CanonicalTileID::scaledTo(uint8_t targetZ) const { + if (targetZ <= z) { + return { targetZ, x >> (z - targetZ), y >> (z - targetZ) }; // parent or same + } else { + return { targetZ, x << (targetZ - z), y << (targetZ - z) }; // child + } +} + +inline std::array CanonicalTileID::children() const { + const uint8_t childZ = z + 1; + const uint32_t childX = x * 2; + const uint32_t childY = y * 2; + return { { + { childZ, childX, childY }, + { childZ, childX, childY + 1 }, + { childZ, childX + 1, childY }, + { childZ, childX + 1, childY + 1 }, + } }; +} + +inline OverscaledTileID::OverscaledTileID(uint8_t overscaledZ_, int16_t wrap_, CanonicalTileID canonical_) + : overscaledZ(overscaledZ_), wrap(wrap_), canonical(std::move(canonical_)) { + assert(overscaledZ >= canonical.z); +} + +inline OverscaledTileID::OverscaledTileID(uint8_t overscaledZ_, int16_t wrap_, uint8_t z, uint32_t x, uint32_t y) + : overscaledZ(overscaledZ_), wrap(wrap_), canonical(z, x, y) { + assert(overscaledZ >= canonical.z); +} + +inline OverscaledTileID::OverscaledTileID(uint8_t z, uint32_t x, uint32_t y) + : overscaledZ(z), wrap(0), canonical(z, x, y) { +} + +inline OverscaledTileID::OverscaledTileID(const CanonicalTileID& canonical_) + : overscaledZ(canonical_.z), wrap(0), canonical(canonical_) { + assert(overscaledZ >= canonical.z); +} + +inline OverscaledTileID::OverscaledTileID(CanonicalTileID&& canonical_) + : overscaledZ(canonical_.z), wrap(0), canonical(std::forward(canonical_)) { + assert(overscaledZ >= canonical.z); +} + +inline bool OverscaledTileID::operator==(const OverscaledTileID& rhs) const { + return overscaledZ == rhs.overscaledZ && wrap == rhs.wrap &&canonical == rhs.canonical; +} + +inline bool OverscaledTileID::operator!=(const OverscaledTileID& rhs) const { + return overscaledZ != rhs.overscaledZ || wrap != rhs.wrap || canonical != rhs.canonical; +} + +inline bool OverscaledTileID::operator<(const OverscaledTileID& rhs) const { + return std::tie(overscaledZ, wrap, canonical) < std::tie(rhs.overscaledZ, rhs.wrap, rhs.canonical); +} + +inline uint32_t OverscaledTileID::overscaleFactor() const { + return 1u << (overscaledZ - canonical.z); +} + +inline bool OverscaledTileID::isChildOf(const OverscaledTileID& rhs) const { + return overscaledZ > rhs.overscaledZ && + (canonical == rhs.canonical || canonical.isChildOf(rhs.canonical)); +} + +inline OverscaledTileID OverscaledTileID::scaledTo(uint8_t z) const { + return { z, wrap, z >= canonical.z ? canonical : canonical.scaledTo(z) }; +} + +inline UnwrappedTileID OverscaledTileID::toUnwrapped() const { + return { wrap, canonical }; +} + +inline UnwrappedTileID::UnwrappedTileID(uint8_t z_, int64_t x_, int64_t y_) + : wrap((x_ < 0 ? x_ - (1ll << z_) + 1 : x_) / (1ll << z_)), + canonical( + z_, + static_cast(x_ - wrap * (1ll << z_)), + y_ < 0 ? 0 : std::min(static_cast(y_), static_cast(1ull << z_) - 1)) { +} + +inline UnwrappedTileID::UnwrappedTileID(int16_t wrap_, CanonicalTileID canonical_) + : wrap(wrap_), canonical(std::move(canonical_)) { +} + +inline bool UnwrappedTileID::operator==(const UnwrappedTileID& rhs) const { + return wrap == rhs.wrap && canonical == rhs.canonical; +} + +inline bool UnwrappedTileID::operator!=(const UnwrappedTileID& rhs) const { + return wrap != rhs.wrap || canonical != rhs.canonical; +} + +inline bool UnwrappedTileID::operator<(const UnwrappedTileID& rhs) const { + return std::tie(wrap, canonical) < std::tie(rhs.wrap, rhs.canonical); +} + +inline bool UnwrappedTileID::isChildOf(const UnwrappedTileID& parent) const { + return wrap == parent.wrap && canonical.isChildOf(parent.canonical); +} + +inline std::array UnwrappedTileID::children() const { + const uint8_t childZ = canonical.z + 1; + const uint32_t childX = canonical.x * 2; + const uint32_t childY = canonical.y * 2; + return { { + { wrap, { childZ, childX, childY } }, + { wrap, { childZ, childX, childY + 1 } }, + { wrap, { childZ, childX + 1, childY } }, + { wrap, { childZ, childX + 1, childY + 1 } }, + } }; +} + +inline OverscaledTileID UnwrappedTileID::overscaleTo(const uint8_t overscaledZ) const { + assert(overscaledZ >= canonical.z); + return { overscaledZ, wrap, canonical }; +} + +inline float UnwrappedTileID::pixelsToTileUnits(const float pixelValue, const float zoom) const { + return pixelValue * (util::EXTENT / (util::tileSize * std::pow(2, zoom - canonical.z))); +} + +} // namespace mbgl + +namespace std { + +template <> +struct hash { + size_t operator()(const mbgl::CanonicalTileID& id) const; +}; + +template <> +struct hash { + size_t operator()(const mbgl::UnwrappedTileID& id) const; +}; + +template <> +struct hash { + size_t operator()(const mbgl::OverscaledTileID& id) const; +}; + +} // namespace std + diff --git a/src/mbgl/tile/tile_id.hpp b/src/mbgl/tile/tile_id.hpp deleted file mode 100644 index 811158e9b9..0000000000 --- a/src/mbgl/tile/tile_id.hpp +++ /dev/null @@ -1,276 +0,0 @@ -#pragma once - -#include - -#include -#include -#include -#include -#include -#include -#include - -namespace mbgl { - -class OverscaledTileID; -class CanonicalTileID; -class UnwrappedTileID; - -// Has integer z/x/y coordinates -// All tiles must be derived from 0/0/0 (=no tiles outside of the main tile pyramid) -// Used for requesting data; represents data tiles that exist out there. -// z is never larger than the source's maxzoom -class CanonicalTileID { -public: - CanonicalTileID(uint8_t z, uint32_t x, uint32_t y); - bool operator==(const CanonicalTileID&) const; - bool operator!=(const CanonicalTileID&) const; - bool operator<(const CanonicalTileID&) const; - bool isChildOf(const CanonicalTileID&) const; - CanonicalTileID scaledTo(uint8_t z) const; - std::array children() const; - - const uint8_t z; - const uint32_t x; - const uint32_t y; -}; - -::std::ostream& operator<<(::std::ostream& os, const CanonicalTileID& rhs); -namespace util { -std::string toString(const CanonicalTileID&); -} // namespace util - -// Has integer z/x/y coordinates -// overscaledZ describes the zoom level this tile is intented to represent, e.g. when parsing data -// z is never larger than the source's maxzoom -// z/x/y describe the -class OverscaledTileID { -public: - OverscaledTileID(uint8_t overscaledZ, int16_t wrap, CanonicalTileID); - OverscaledTileID(uint8_t overscaledZ, int16_t wrap, uint8_t z, uint32_t x, uint32_t y); - OverscaledTileID(uint8_t z, uint32_t x, uint32_t y); - explicit OverscaledTileID(const CanonicalTileID&); - explicit OverscaledTileID(CanonicalTileID&&); - bool operator==(const OverscaledTileID&) const; - bool operator!=(const OverscaledTileID&) const; - bool operator<(const OverscaledTileID&) const; - bool isChildOf(const OverscaledTileID&) const; - uint32_t overscaleFactor() const; - OverscaledTileID scaledTo(uint8_t z) const; - UnwrappedTileID toUnwrapped() const; - - const uint8_t overscaledZ; - const int16_t wrap; - const CanonicalTileID canonical; -}; - -::std::ostream& operator<<(::std::ostream& os, const OverscaledTileID& rhs); -namespace util { -std::string toString(const OverscaledTileID&); -} // namespace util - -// Has integer z/x/y coordinates -// wrap describes tiles that are left/right of the main tile pyramid, e.g. when wrapping the world -// Used for describing what position tiles are getting rendered at (= calc the matrix) -// z is never larger than the source's maxzoom -class UnwrappedTileID { -public: - UnwrappedTileID(uint8_t z, int64_t x, int64_t y); - UnwrappedTileID(int16_t wrap, CanonicalTileID); - bool operator==(const UnwrappedTileID&) const; - bool operator!=(const UnwrappedTileID&) const; - bool operator<(const UnwrappedTileID&) const; - bool isChildOf(const UnwrappedTileID&) const; - std::array children() const; - OverscaledTileID overscaleTo(uint8_t z) const; - float pixelsToTileUnits(float pixelValue, float zoom) const; - - const int16_t wrap; - const CanonicalTileID canonical; -}; - -::std::ostream& operator<<(::std::ostream& os, const UnwrappedTileID& rhs); -namespace util { -std::string toString(const UnwrappedTileID&); -} // namespace util - -inline CanonicalTileID::CanonicalTileID(uint8_t z_, uint32_t x_, uint32_t y_) : z(z_), x(x_), y(y_) { - assert(z <= 32); - assert(x < (1ull << z)); - assert(y < (1ull << z)); -} - -inline bool CanonicalTileID::operator==(const CanonicalTileID& rhs) const { - return z == rhs.z && x == rhs.x && y == rhs.y; -} - -inline bool CanonicalTileID::operator!=(const CanonicalTileID& rhs) const { - return z != rhs.z || x != rhs.x || y != rhs.y; -} - -inline bool CanonicalTileID::operator<(const CanonicalTileID& rhs) const { - return std::tie(z, x, y) < std::tie(rhs.z, rhs.x, rhs.y); -} - -inline bool CanonicalTileID::isChildOf(const CanonicalTileID& parent) const { - // We're first testing for z == 0, to avoid a 32 bit shift, which is undefined. - return parent.z == 0 || - (parent.z < z && parent.x == (x >> (z - parent.z)) && parent.y == (y >> (z - parent.z))); -} - -inline CanonicalTileID CanonicalTileID::scaledTo(uint8_t targetZ) const { - if (targetZ <= z) { - return { targetZ, x >> (z - targetZ), y >> (z - targetZ) }; // parent or same - } else { - return { targetZ, x << (targetZ - z), y << (targetZ - z) }; // child - } -} - -inline std::array CanonicalTileID::children() const { - const uint8_t childZ = z + 1; - const uint32_t childX = x * 2; - const uint32_t childY = y * 2; - return { { - { childZ, childX, childY }, - { childZ, childX, childY + 1 }, - { childZ, childX + 1, childY }, - { childZ, childX + 1, childY + 1 }, - } }; -} - -inline OverscaledTileID::OverscaledTileID(uint8_t overscaledZ_, int16_t wrap_, CanonicalTileID canonical_) - : overscaledZ(overscaledZ_), wrap(wrap_), canonical(std::move(canonical_)) { - assert(overscaledZ >= canonical.z); -} - -inline OverscaledTileID::OverscaledTileID(uint8_t overscaledZ_, int16_t wrap_, uint8_t z, uint32_t x, uint32_t y) - : overscaledZ(overscaledZ_), wrap(wrap_), canonical(z, x, y) { - assert(overscaledZ >= canonical.z); -} - -inline OverscaledTileID::OverscaledTileID(uint8_t z, uint32_t x, uint32_t y) - : overscaledZ(z), wrap(0), canonical(z, x, y) { -} - -inline OverscaledTileID::OverscaledTileID(const CanonicalTileID& canonical_) - : overscaledZ(canonical_.z), wrap(0), canonical(canonical_) { - assert(overscaledZ >= canonical.z); -} - -inline OverscaledTileID::OverscaledTileID(CanonicalTileID&& canonical_) - : overscaledZ(canonical_.z), wrap(0), canonical(std::forward(canonical_)) { - assert(overscaledZ >= canonical.z); -} - -inline bool OverscaledTileID::operator==(const OverscaledTileID& rhs) const { - return overscaledZ == rhs.overscaledZ && wrap == rhs.wrap &&canonical == rhs.canonical; -} - -inline bool OverscaledTileID::operator!=(const OverscaledTileID& rhs) const { - return overscaledZ != rhs.overscaledZ || wrap != rhs.wrap || canonical != rhs.canonical; -} - -inline bool OverscaledTileID::operator<(const OverscaledTileID& rhs) const { - return std::tie(overscaledZ, wrap, canonical) < std::tie(rhs.overscaledZ, rhs.wrap, rhs.canonical); -} - -inline uint32_t OverscaledTileID::overscaleFactor() const { - return 1u << (overscaledZ - canonical.z); -} - -inline bool OverscaledTileID::isChildOf(const OverscaledTileID& rhs) const { - return overscaledZ > rhs.overscaledZ && - (canonical == rhs.canonical || canonical.isChildOf(rhs.canonical)); -} - -inline OverscaledTileID OverscaledTileID::scaledTo(uint8_t z) const { - return { z, wrap, z >= canonical.z ? canonical : canonical.scaledTo(z) }; -} - -inline UnwrappedTileID OverscaledTileID::toUnwrapped() const { - return { wrap, canonical }; -} - -inline UnwrappedTileID::UnwrappedTileID(uint8_t z_, int64_t x_, int64_t y_) - : wrap((x_ < 0 ? x_ - (1ll << z_) + 1 : x_) / (1ll << z_)), - canonical( - z_, - static_cast(x_ - wrap * (1ll << z_)), - y_ < 0 ? 0 : std::min(static_cast(y_), static_cast(1ull << z_) - 1)) { -} - -inline UnwrappedTileID::UnwrappedTileID(int16_t wrap_, CanonicalTileID canonical_) - : wrap(wrap_), canonical(std::move(canonical_)) { -} - -inline bool UnwrappedTileID::operator==(const UnwrappedTileID& rhs) const { - return wrap == rhs.wrap && canonical == rhs.canonical; -} - -inline bool UnwrappedTileID::operator!=(const UnwrappedTileID& rhs) const { - return wrap != rhs.wrap || canonical != rhs.canonical; -} - -inline bool UnwrappedTileID::operator<(const UnwrappedTileID& rhs) const { - return std::tie(wrap, canonical) < std::tie(rhs.wrap, rhs.canonical); -} - -inline bool UnwrappedTileID::isChildOf(const UnwrappedTileID& parent) const { - return wrap == parent.wrap && canonical.isChildOf(parent.canonical); -} - -inline std::array UnwrappedTileID::children() const { - const uint8_t childZ = canonical.z + 1; - const uint32_t childX = canonical.x * 2; - const uint32_t childY = canonical.y * 2; - return { { - { wrap, { childZ, childX, childY } }, - { wrap, { childZ, childX, childY + 1 } }, - { wrap, { childZ, childX + 1, childY } }, - { wrap, { childZ, childX + 1, childY + 1 } }, - } }; -} - -inline OverscaledTileID UnwrappedTileID::overscaleTo(const uint8_t overscaledZ) const { - assert(overscaledZ >= canonical.z); - return { overscaledZ, wrap, canonical }; -} - -inline float UnwrappedTileID::pixelsToTileUnits(const float pixelValue, const float zoom) const { - return pixelValue * (util::EXTENT / (util::tileSize * std::pow(2, zoom - canonical.z))); -} - -} // namespace mbgl - -namespace std { - -template <> struct hash { - size_t operator()(const mbgl::CanonicalTileID &id) const { - std::size_t seed = 0; - boost::hash_combine(seed, id.x); - boost::hash_combine(seed, id.y); - boost::hash_combine(seed, id.z); - return seed; - } -}; - -template <> struct hash { - size_t operator()(const mbgl::UnwrappedTileID &id) const { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash{}(id.canonical)); - boost::hash_combine(seed, id.wrap); - return seed; - } -}; - -template <> struct hash { - size_t operator()(const mbgl::OverscaledTileID &id) const { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash{}(id.canonical)); - boost::hash_combine(seed, id.overscaledZ); - return seed; - } -}; - -} // namespace std - diff --git a/src/mbgl/tile/tile_id_hash.cpp b/src/mbgl/tile/tile_id_hash.cpp new file mode 100644 index 0000000000..4a1f185817 --- /dev/null +++ b/src/mbgl/tile/tile_id_hash.cpp @@ -0,0 +1,29 @@ +#include + +#include + +namespace std { + +size_t hash::operator()(const mbgl::CanonicalTileID& id) const { + std::size_t seed = 0; + boost::hash_combine(seed, id.x); + boost::hash_combine(seed, id.y); + boost::hash_combine(seed, id.z); + return seed; +} + +size_t hash::operator()(const mbgl::UnwrappedTileID& id) const { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash{}(id.canonical)); + boost::hash_combine(seed, id.wrap); + return seed; +} + +size_t hash::operator()(const mbgl::OverscaledTileID& id) const { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash{}(id.canonical)); + boost::hash_combine(seed, id.overscaledZ); + return seed; +} + +} // namespace std -- cgit v1.2.1