diff options
| author | thegeorg <thegeorg@yandex-team.ru> | 2022-02-10 16:45:12 +0300 |
|---|---|---|
| committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:12 +0300 |
| commit | 49116032d905455a7b1c994e4a696afc885c1e71 (patch) | |
| tree | be835aa92c6248212e705f25388ebafcf84bc7a1 /contrib/libs/hyperscan/src/util | |
| parent | 4e839db24a3bbc9f1c610c43d6faaaa99824dcca (diff) | |
| download | ydb-49116032d905455a7b1c994e4a696afc885c1e71.tar.gz | |
Restoring authorship annotation for <thegeorg@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/hyperscan/src/util')
23 files changed, 1131 insertions, 1131 deletions
diff --git a/contrib/libs/hyperscan/src/util/arch.h b/contrib/libs/hyperscan/src/util/arch.h index 5bcca08c94..6220f12bc1 100644 --- a/contrib/libs/hyperscan/src/util/arch.h +++ b/contrib/libs/hyperscan/src/util/arch.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2020, Intel Corporation + * Copyright (c) 2017-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -34,7 +34,7 @@ #define UTIL_ARCH_H_ #define HAVE_SSE2 - + /* * MSVC uses a different form of inline asm */ diff --git a/contrib/libs/hyperscan/src/util/bitfield.h b/contrib/libs/hyperscan/src/util/bitfield.h index 181c1100b6..a580da7b60 100644 --- a/contrib/libs/hyperscan/src/util/bitfield.h +++ b/contrib/libs/hyperscan/src/util/bitfield.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2018, Intel Corporation + * Copyright (c) 2015-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -305,10 +305,10 @@ public: } /// Bitwise OR. - bitfield operator|(const bitfield &a) const { - bitfield b = a; - b |= *this; - return b; + bitfield operator|(const bitfield &a) const { + bitfield b = a; + b |= *this; + return b; } /// Bitwise OR-equals. @@ -326,10 +326,10 @@ public: } /// Bitwise AND. - bitfield operator&(const bitfield &a) const { - bitfield b = a; - b &= *this; - return b; + bitfield operator&(const bitfield &a) const { + bitfield b = a; + b &= *this; + return b; } /// Bitwise AND-equals. diff --git a/contrib/libs/hyperscan/src/util/copybytes.h b/contrib/libs/hyperscan/src/util/copybytes.h index cb703c30f9..7f37d96bc5 100644 --- a/contrib/libs/hyperscan/src/util/copybytes.h +++ b/contrib/libs/hyperscan/src/util/copybytes.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2016-2020, Intel Corporation + * Copyright (c) 2016-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -33,7 +33,7 @@ #include "simd_utils.h" static really_inline -void copy_upto_64_bytes(u8 *dst, const u8 *src, unsigned int len) { +void copy_upto_64_bytes(u8 *dst, const u8 *src, unsigned int len) { switch (len) { case 0: break; @@ -72,41 +72,41 @@ void copy_upto_64_bytes(u8 *dst, const u8 *src, unsigned int len) { case 16: storeu128(dst, loadu128(src)); break; - case 17: - case 18: - case 19: - case 20: - case 21: - case 22: - case 23: - case 24: - case 25: - case 26: - case 27: - case 28: - case 29: - case 30: - case 31: - storeu128(dst + len - 16, loadu128(src + len - 16)); - storeu128(dst, loadu128(src)); - break; + case 17: + case 18: + case 19: + case 20: + case 21: + case 22: + case 23: + case 24: + case 25: + case 26: + case 27: + case 28: + case 29: + case 30: + case 31: + storeu128(dst + len - 16, loadu128(src + len - 16)); + storeu128(dst, loadu128(src)); + break; case 32: storeu256(dst, loadu256(src)); break; -#ifdef HAVE_AVX512 - case 64: - storebytes512(dst, loadu512(src), 64); - break; +#ifdef HAVE_AVX512 + case 64: + storebytes512(dst, loadu512(src), 64); + break; default: - assert(len < 64); - u64a k = (1ULL << len) - 1; - storeu_mask_m512(dst, k, loadu_maskz_m512(k, src)); + assert(len < 64); + u64a k = (1ULL << len) - 1; + storeu_mask_m512(dst, k, loadu_maskz_m512(k, src)); break; -#else - default: - assert(0); - break; -#endif +#else + default: + assert(0); + break; +#endif } } diff --git a/contrib/libs/hyperscan/src/util/cpuid_flags.c b/contrib/libs/hyperscan/src/util/cpuid_flags.c index 42d920da29..c00ce58e2d 100644 --- a/contrib/libs/hyperscan/src/util/cpuid_flags.c +++ b/contrib/libs/hyperscan/src/util/cpuid_flags.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2020, Intel Corporation + * Copyright (c) 2015-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -50,11 +50,11 @@ u64a cpuid_flags(void) { cap |= HS_CPU_FEATURES_AVX512; } - if (check_avx512vbmi()) { - DEBUG_PRINTF("AVX512VBMI enabled\n"); - cap |= HS_CPU_FEATURES_AVX512VBMI; - } - + if (check_avx512vbmi()) { + DEBUG_PRINTF("AVX512VBMI enabled\n"); + cap |= HS_CPU_FEATURES_AVX512VBMI; + } + #if !defined(FAT_RUNTIME) && !defined(HAVE_AVX2) cap &= ~HS_CPU_FEATURES_AVX2; #endif @@ -64,11 +64,11 @@ u64a cpuid_flags(void) { cap &= ~HS_CPU_FEATURES_AVX512; #endif -#if (!defined(FAT_RUNTIME) && !defined(HAVE_AVX512VBMI)) || \ - (defined(FAT_RUNTIME) && !defined(BUILD_AVX512VBMI)) - cap &= ~HS_CPU_FEATURES_AVX512VBMI; -#endif - +#if (!defined(FAT_RUNTIME) && !defined(HAVE_AVX512VBMI)) || \ + (defined(FAT_RUNTIME) && !defined(BUILD_AVX512VBMI)) + cap &= ~HS_CPU_FEATURES_AVX512VBMI; +#endif + return cap; } @@ -115,11 +115,11 @@ static const struct family_id known_microarch[] = { { 0x6, 0x8E, HS_TUNE_FAMILY_SKL }, /* Kabylake Mobile */ { 0x6, 0x9E, HS_TUNE_FAMILY_SKL }, /* Kabylake desktop */ - { 0x6, 0x7D, HS_TUNE_FAMILY_ICL }, /* Icelake */ - { 0x6, 0x7E, HS_TUNE_FAMILY_ICL }, /* Icelake */ - { 0x6, 0x6A, HS_TUNE_FAMILY_ICX }, /* Icelake Xeon-D */ - { 0x6, 0x6C, HS_TUNE_FAMILY_ICX }, /* Icelake Xeon */ - + { 0x6, 0x7D, HS_TUNE_FAMILY_ICL }, /* Icelake */ + { 0x6, 0x7E, HS_TUNE_FAMILY_ICL }, /* Icelake */ + { 0x6, 0x6A, HS_TUNE_FAMILY_ICX }, /* Icelake Xeon-D */ + { 0x6, 0x6C, HS_TUNE_FAMILY_ICX }, /* Icelake Xeon */ + }; #ifdef DUMP_SUPPORT @@ -135,8 +135,8 @@ const char *dumpTune(u32 tune) { T_CASE(HS_TUNE_FAMILY_BDW); T_CASE(HS_TUNE_FAMILY_SKL); T_CASE(HS_TUNE_FAMILY_SKX); - T_CASE(HS_TUNE_FAMILY_ICL); - T_CASE(HS_TUNE_FAMILY_ICX); + T_CASE(HS_TUNE_FAMILY_ICL); + T_CASE(HS_TUNE_FAMILY_ICX); } #undef T_CASE return "unknown"; diff --git a/contrib/libs/hyperscan/src/util/cpuid_inline.h b/contrib/libs/hyperscan/src/util/cpuid_inline.h index 4e4e7f6d6d..b7b4245289 100644 --- a/contrib/libs/hyperscan/src/util/cpuid_inline.h +++ b/contrib/libs/hyperscan/src/util/cpuid_inline.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2020, Intel Corporation + * Copyright (c) 2017-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -74,9 +74,9 @@ void cpuid(unsigned int op, unsigned int leaf, unsigned int *eax, #define CPUID_HTT (1 << 28) // Structured Extended Feature Flags Enumeration Leaf ECX values -#define CPUID_AVX512VBMI (1 << 1) - -// Structured Extended Feature Flags Enumeration Leaf EBX values +#define CPUID_AVX512VBMI (1 << 1) + +// Structured Extended Feature Flags Enumeration Leaf EBX values #define CPUID_BMI (1 << 3) #define CPUID_AVX2 (1 << 5) #define CPUID_BMI2 (1 << 8) @@ -188,51 +188,51 @@ int check_avx512(void) { } static inline -int check_avx512vbmi(void) { -#if defined(__INTEL_COMPILER) - return _may_i_use_cpu_feature(_FEATURE_AVX512VBMI); -#else - unsigned int eax, ebx, ecx, edx; - - cpuid(1, 0, &eax, &ebx, &ecx, &edx); - - /* check XSAVE is enabled by OS */ - if (!(ecx & CPUID_XSAVE)) { - DEBUG_PRINTF("AVX and XSAVE not supported\n"); - return 0; - } - - /* check that AVX 512 registers are enabled by OS */ - u64a xcr0 = xgetbv(0); - if ((xcr0 & CPUID_XCR0_AVX512) != CPUID_XCR0_AVX512) { - DEBUG_PRINTF("AVX512 registers not enabled\n"); - return 0; - } - - /* ECX and EDX contain capability flags */ - ecx = 0; - cpuid(7, 0, &eax, &ebx, &ecx, &edx); - - if (!(ebx & CPUID_AVX512F)) { - DEBUG_PRINTF("AVX512F (AVX512 Foundation) instructions not enabled\n"); - return 0; - } - - if (!(ebx & CPUID_AVX512BW)) { - DEBUG_PRINTF("AVX512BW instructions not enabled\n"); - return 0; - } - - if (ecx & CPUID_AVX512VBMI) { - DEBUG_PRINTF("AVX512VBMI instructions enabled\n"); - return 1; - } - - return 0; -#endif -} - -static inline +int check_avx512vbmi(void) { +#if defined(__INTEL_COMPILER) + return _may_i_use_cpu_feature(_FEATURE_AVX512VBMI); +#else + unsigned int eax, ebx, ecx, edx; + + cpuid(1, 0, &eax, &ebx, &ecx, &edx); + + /* check XSAVE is enabled by OS */ + if (!(ecx & CPUID_XSAVE)) { + DEBUG_PRINTF("AVX and XSAVE not supported\n"); + return 0; + } + + /* check that AVX 512 registers are enabled by OS */ + u64a xcr0 = xgetbv(0); + if ((xcr0 & CPUID_XCR0_AVX512) != CPUID_XCR0_AVX512) { + DEBUG_PRINTF("AVX512 registers not enabled\n"); + return 0; + } + + /* ECX and EDX contain capability flags */ + ecx = 0; + cpuid(7, 0, &eax, &ebx, &ecx, &edx); + + if (!(ebx & CPUID_AVX512F)) { + DEBUG_PRINTF("AVX512F (AVX512 Foundation) instructions not enabled\n"); + return 0; + } + + if (!(ebx & CPUID_AVX512BW)) { + DEBUG_PRINTF("AVX512BW instructions not enabled\n"); + return 0; + } + + if (ecx & CPUID_AVX512VBMI) { + DEBUG_PRINTF("AVX512VBMI instructions enabled\n"); + return 1; + } + + return 0; +#endif +} + +static inline int check_ssse3(void) { unsigned int eax, ebx, ecx, edx; cpuid(1, 0, &eax, &ebx, &ecx, &edx); diff --git a/contrib/libs/hyperscan/src/util/dump_util.h b/contrib/libs/hyperscan/src/util/dump_util.h index 48f0821810..dc352c28ee 100644 --- a/contrib/libs/hyperscan/src/util/dump_util.h +++ b/contrib/libs/hyperscan/src/util/dump_util.h @@ -1,63 +1,63 @@ -/* - * Copyright (c) 2016-2017, Intel Corporation - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * * Neither the name of Intel Corporation nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef DUMP_UTIL -#define DUMP_UTIL - -#include "noncopyable.h" - -#include <cstdio> -#include <memory> -#include <string> - -namespace ue2 { - -/** - * Same as fopen(), but on error throws an exception rather than returning NULL. - */ -FILE *fopen_or_throw(const char *path, const char *mode); - -/** - * \brief Helper class: wraps C stdio FILE* handle and takes care of closing - * the file on destruction. - */ -class StdioFile : noncopyable { -public: - StdioFile(const std::string &filename, const char *mode) - : handle(fopen_or_throw(filename.c_str(), mode), &fclose) {} - - // Implicit conversion to FILE* for use by stdio calls. - operator FILE *() { return handle.get(); } - -private: - std::unique_ptr<FILE, decltype(&fclose)> handle; -}; - -} // namespace ue2 - -#endif +/* + * Copyright (c) 2016-2017, Intel Corporation + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Intel Corporation nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef DUMP_UTIL +#define DUMP_UTIL + +#include "noncopyable.h" + +#include <cstdio> +#include <memory> +#include <string> + +namespace ue2 { + +/** + * Same as fopen(), but on error throws an exception rather than returning NULL. + */ +FILE *fopen_or_throw(const char *path, const char *mode); + +/** + * \brief Helper class: wraps C stdio FILE* handle and takes care of closing + * the file on destruction. + */ +class StdioFile : noncopyable { +public: + StdioFile(const std::string &filename, const char *mode) + : handle(fopen_or_throw(filename.c_str(), mode), &fclose) {} + + // Implicit conversion to FILE* for use by stdio calls. + operator FILE *() { return handle.get(); } + +private: + std::unique_ptr<FILE, decltype(&fclose)> handle; +}; + +} // namespace ue2 + +#endif diff --git a/contrib/libs/hyperscan/src/util/graph.h b/contrib/libs/hyperscan/src/util/graph.h index 9fd55304fd..3e18dae552 100644 --- a/contrib/libs/hyperscan/src/util/graph.h +++ b/contrib/libs/hyperscan/src/util/graph.h @@ -170,7 +170,7 @@ find_vertices_in_cycles(const Graph &g) { assert(!comp.empty()); if (comp.size() > 1) { insert(&rv, comp); - continue; + continue; } vertex_descriptor v = *comp.begin(); if (hasSelfLoop(v, g)) { diff --git a/contrib/libs/hyperscan/src/util/graph_small_color_map.h b/contrib/libs/hyperscan/src/util/graph_small_color_map.h index 9918bc771f..249b71531c 100644 --- a/contrib/libs/hyperscan/src/util/graph_small_color_map.h +++ b/contrib/libs/hyperscan/src/util/graph_small_color_map.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017-2018, Intel Corporation + * Copyright (c) 2017-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -114,21 +114,21 @@ public: std::memset(data->data(), val, data->size()); } - size_t count(small_color color) const { - assert(static_cast<u8>(color) < sizeof(fill_lut)); - size_t num = 0; - for (size_t i = 0; i < n; i++) { - size_t byte = i / entries_per_byte; - assert(byte < data->size()); - size_t bit = (i % entries_per_byte) * bit_size; - u8 val = ((*data)[byte] >> bit) & bit_mask; - if (static_cast<small_color>(val) == color) { - num++; - } - } - return num; - } - + size_t count(small_color color) const { + assert(static_cast<u8>(color) < sizeof(fill_lut)); + size_t num = 0; + for (size_t i = 0; i < n; i++) { + size_t byte = i / entries_per_byte; + assert(byte < data->size()); + size_t bit = (i % entries_per_byte) * bit_size; + u8 val = ((*data)[byte] >> bit) & bit_mask; + if (static_cast<small_color>(val) == color) { + num++; + } + } + return num; + } + small_color get_impl(key_type key) const { auto i = get(index_map, key); assert(i < n); diff --git a/contrib/libs/hyperscan/src/util/graph_undirected.h b/contrib/libs/hyperscan/src/util/graph_undirected.h index 75b6084c4d..049964ab07 100644 --- a/contrib/libs/hyperscan/src/util/graph_undirected.h +++ b/contrib/libs/hyperscan/src/util/graph_undirected.h @@ -1,501 +1,501 @@ -/* - * Copyright (c) 2018, Intel Corporation - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * * Neither the name of Intel Corporation nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -/** - * \file - * \brief Adaptor that presents an undirected view of a bidirectional BGL graph. - * - * Analogous to the reverse_graph adapter. You can construct one of these for - * bidirectional graph g with: - * - * auto ug = make_undirected_graph(g); - * - * The vertex descriptor type is the same as that of the underlying graph, but - * the edge descriptor is different. - */ - -#ifndef GRAPH_UNDIRECTED_H -#define GRAPH_UNDIRECTED_H - -#include "util/operators.h" - -#include <boost/graph/adjacency_iterator.hpp> -#include <boost/graph/graph_traits.hpp> -#include <boost/graph/properties.hpp> -#include <boost/iterator/iterator_facade.hpp> - -#include <type_traits> -#include <utility> - -namespace ue2 { - -struct undirected_graph_tag {}; - -template <class BidirectionalGraph, class GraphRef> -class undirected_graph; - -namespace undirected_detail { - -template <typename BidirectionalGraph> -class undirected_graph_edge_descriptor - : totally_ordered<undirected_graph_edge_descriptor<BidirectionalGraph>> { - using base_graph_type = BidirectionalGraph; - using base_graph_traits = typename boost::graph_traits<base_graph_type>; - using base_edge_type = typename base_graph_traits::edge_descriptor; - using base_vertex_type = typename base_graph_traits::vertex_descriptor; - - base_edge_type underlying_edge; - const base_graph_type *g; - bool reverse; // if true, reverse vertices in source() and target() - - inline std::pair<base_vertex_type, base_vertex_type> - canonical_edge() const { - auto u = std::min(source(underlying_edge, *g), - target(underlying_edge, *g)); - auto v = std::max(source(underlying_edge, *g), - target(underlying_edge, *g)); - return std::make_pair(u, v); - } - - template <class BidiGraph, class GraphRef> - friend class ::ue2::undirected_graph; - -public: - undirected_graph_edge_descriptor() = default; - - undirected_graph_edge_descriptor(base_edge_type edge, - const base_graph_type &g_in, - bool reverse_in) - : underlying_edge(std::move(edge)), g(&g_in), reverse(reverse_in) {} - - bool operator==(const undirected_graph_edge_descriptor &other) const { - return canonical_edge() == other.canonical_edge(); - } - - bool operator<(const undirected_graph_edge_descriptor &other) const { - return canonical_edge() < other.canonical_edge(); - } - - base_vertex_type get_source() const { - return reverse ? target(underlying_edge, *g) - : source(underlying_edge, *g); - } - - base_vertex_type get_target() const { - return reverse ? source(underlying_edge, *g) - : target(underlying_edge, *g); - } -}; - -} // namespace undirected_detail - -template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph &> -class undirected_graph { -private: - using Self = undirected_graph<BidirectionalGraph, GraphRef>; - using Traits = boost::graph_traits<BidirectionalGraph>; - -public: - using base_type = BidirectionalGraph; - using base_ref_type = GraphRef; - - explicit undirected_graph(GraphRef g_in) : g(g_in) {} - - // Graph requirements - using vertex_descriptor = typename Traits::vertex_descriptor; - using edge_descriptor = - undirected_detail::undirected_graph_edge_descriptor<base_type>; - using directed_category = boost::undirected_tag; - using edge_parallel_category = boost::disallow_parallel_edge_tag; - using traversal_category = typename Traits::traversal_category; - - // IncidenceGraph requirements - - /** - * \brief Templated iterator used for out_edge_iterator and - * in_edge_iterator, depending on the value of Reverse. - */ - template <bool Reverse> - class adj_edge_iterator - : public boost::iterator_facade< - adj_edge_iterator<Reverse>, edge_descriptor, - boost::forward_traversal_tag, edge_descriptor> { - vertex_descriptor u; - const base_type *g; - typename Traits::in_edge_iterator in_it; - typename Traits::out_edge_iterator out_it; - bool done_in = false; - public: - adj_edge_iterator() = default; - - adj_edge_iterator(vertex_descriptor u_in, const base_type &g_in, - bool end_iter) - : u(std::move(u_in)), g(&g_in) { - auto pi = in_edges(u, *g); - auto po = out_edges(u, *g); - if (end_iter) { - in_it = pi.second; - out_it = po.second; - done_in = true; - } else { - in_it = pi.first; - out_it = po.first; - if (in_it == pi.second) { - done_in = true; - find_first_valid_out(); - } - } - } - - private: - friend class boost::iterator_core_access; - - void find_first_valid_out() { - auto out_end = out_edges(u, *g).second; - for (; out_it != out_end; ++out_it) { - auto v = target(*out_it, *g); - if (!edge(v, u, *g).second) { - break; - } - } - } - - void increment() { - if (!done_in) { - auto in_end = in_edges(u, *g).second; - assert(in_it != in_end); - ++in_it; - if (in_it == in_end) { - done_in = true; - find_first_valid_out(); - } - } else { - ++out_it; - find_first_valid_out(); - } - } - bool equal(const adj_edge_iterator &other) const { - return in_it == other.in_it && out_it == other.out_it; - } - edge_descriptor dereference() const { - if (done_in) { - return edge_descriptor(*out_it, *g, Reverse); - } else { - return edge_descriptor(*in_it, *g, !Reverse); - } - } - }; - - using out_edge_iterator = adj_edge_iterator<false>; - using in_edge_iterator = adj_edge_iterator<true>; - - using degree_size_type = typename Traits::degree_size_type; - - // AdjacencyGraph requirements - using adjacency_iterator = - typename boost::adjacency_iterator_generator<Self, vertex_descriptor, - out_edge_iterator>::type; - using inv_adjacency_iterator = - typename boost::inv_adjacency_iterator_generator< - Self, vertex_descriptor, in_edge_iterator>::type; - - // VertexListGraph requirements - using vertex_iterator = typename Traits::vertex_iterator; - - // EdgeListGraph requirements - enum { - is_edge_list = std::is_convertible<traversal_category, - boost::edge_list_graph_tag>::value - }; - - /** \brief Iterator used for edges(). */ - class edge_iterator - : public boost::iterator_facade<edge_iterator, edge_descriptor, - boost::forward_traversal_tag, - edge_descriptor> { - const base_type *g; - typename Traits::edge_iterator it; - public: - edge_iterator() = default; - - edge_iterator(typename Traits::edge_iterator it_in, - const base_type &g_in) - : g(&g_in), it(std::move(it_in)) { - find_first_valid_edge(); - } - - private: - friend class boost::iterator_core_access; - - void find_first_valid_edge() { - const auto end = edges(*g).second; - for (; it != end; ++it) { - const auto &u = source(*it, *g); - const auto &v = target(*it, *g); - if (!edge(v, u, *g).second) { - break; // No reverse edge, we must visit this one - } - if (u <= v) { - // We have a reverse edge, but we'll return this one (and - // skip the other). Note that (u, u) shouldn't be skipped. - break; - } - } - } - - void increment() { - assert(it != edges(*g).second); - ++it; - find_first_valid_edge(); - } - bool equal(const edge_iterator &other) const { - return it == other.it; - } - edge_descriptor dereference() const { - return edge_descriptor(*it, *g, false); - } - }; - - using vertices_size_type = typename Traits::vertices_size_type; - using edges_size_type = typename Traits::edges_size_type; - - using graph_tag = undirected_graph_tag; - - using vertex_bundle_type = - typename boost::vertex_bundle_type<base_type>::type; - using edge_bundle_type = typename boost::edge_bundle_type<base_type>::type; - - vertex_bundle_type &operator[](const vertex_descriptor &d) { - return const_cast<base_type &>(g)[d]; - } - const vertex_bundle_type &operator[](const vertex_descriptor &d) const { - return g[d]; - } - - edge_bundle_type &operator[](const edge_descriptor &d) { - return const_cast<base_type &>(g)[d.underlying_edge]; - } - const edge_bundle_type &operator[](const edge_descriptor &d) const { - return g[d.underlying_edge]; - } - - static vertex_descriptor null_vertex() { return Traits::null_vertex(); } - - // Accessor free functions follow - - friend std::pair<vertex_iterator, vertex_iterator> - vertices(const undirected_graph &ug) { - return vertices(ug.g); - } - - friend std::pair<edge_iterator, edge_iterator> - edges(const undirected_graph &ug) { - auto e = edges(ug.g); - return std::make_pair(edge_iterator(e.first, ug.g), - edge_iterator(e.second, ug.g)); - } - - friend std::pair<out_edge_iterator, out_edge_iterator> - out_edges(const vertex_descriptor &u, const undirected_graph &ug) { - return std::make_pair(out_edge_iterator(u, ug.g, false), - out_edge_iterator(u, ug.g, true)); - } - - friend vertices_size_type num_vertices(const undirected_graph &ug) { - return num_vertices(ug.g); - } - - friend edges_size_type num_edges(const undirected_graph &ug) { - auto p = edges(ug); - return std::distance(p.first, p.second); - } - - friend degree_size_type out_degree(const vertex_descriptor &u, - const undirected_graph &ug) { - return degree(u, ug); - } - - friend vertex_descriptor vertex(vertices_size_type n, - const undirected_graph &ug) { - return vertex(n, ug.g); - } - - friend std::pair<edge_descriptor, bool> edge(const vertex_descriptor &u, - const vertex_descriptor &v, - const undirected_graph &ug) { - auto e = edge(u, v, ug.g); - if (e.second) { - return std::make_pair(edge_descriptor(e.first, ug.g, false), true); - } - auto e_rev = edge(v, u, ug.g); - if (e_rev.second) { - return std::make_pair(edge_descriptor(e_rev.first, ug.g, true), - true); - } - return std::make_pair(edge_descriptor(), false); - } - - friend std::pair<in_edge_iterator, in_edge_iterator> - in_edges(const vertex_descriptor &v, const undirected_graph &ug) { - return std::make_pair(in_edge_iterator(v, ug.g, false), - in_edge_iterator(v, ug.g, true)); - } - - friend std::pair<adjacency_iterator, adjacency_iterator> - adjacent_vertices(const vertex_descriptor &u, const undirected_graph &ug) { - out_edge_iterator oi, oe; - std::tie(oi, oe) = out_edges(u, ug); - return std::make_pair(adjacency_iterator(oi, &ug), - adjacency_iterator(oe, &ug)); - } - - friend std::pair<inv_adjacency_iterator, inv_adjacency_iterator> - inv_adjacent_vertices(const vertex_descriptor &v, - const undirected_graph &ug) { - in_edge_iterator ei, ee; - std::tie(ei, ee) = in_edges(v, ug); - return std::make_pair(inv_adjacency_iterator(ei, &ug), - inv_adjacency_iterator(ee, &ug)); - } - - friend degree_size_type in_degree(const vertex_descriptor &v, - const undirected_graph &ug) { - return degree(v, ug); - } - - friend vertex_descriptor source(const edge_descriptor &e, - const undirected_graph &) { - return e.get_source(); - } - - friend vertex_descriptor target(const edge_descriptor &e, - const undirected_graph &) { - return e.get_target(); - } - - friend degree_size_type degree(const vertex_descriptor &u, - const undirected_graph &ug) { - auto p = out_edges(u, ug); - return std::distance(p.first, p.second); - } - - // Property accessors. - - template <typename Property> - using prop_map = typename boost::property_map<undirected_graph, Property>; - - template <typename Property> - friend typename prop_map<Property>::type - get(Property p, undirected_graph &ug) { - return get(p, ug.g); - } - - template <typename Property> - friend typename prop_map<Property>::const_type - get(Property p, const undirected_graph &ug) { - return get(p, ug.g); - } - - template <typename Property, typename Key> - friend typename boost::property_traits< - typename prop_map<Property>::const_type>::value_type - get(Property p, const undirected_graph &ug, const Key &k) { - return get(p, ug.g, get_underlying_descriptor(k)); - } - - template <typename Property, typename Value, typename Key> - friend void put(Property p, const undirected_graph &ug, - const Key &k, const Value &val) { - put(p, const_cast<BidirectionalGraph &>(ug.g), - get_underlying_descriptor(k), val); - } - -private: - // Accessors are here because our free friend functions (above) cannot see - // edge_descriptor's private members. - static typename base_type::vertex_descriptor - get_underlying_descriptor(const vertex_descriptor &v) { - return v; - } - static typename base_type::edge_descriptor - get_underlying_descriptor(const edge_descriptor &e) { - return e.underlying_edge; - } - - // Reference to underlying bidirectional graph - GraphRef g; -}; - -template <class BidirectionalGraph> -undirected_graph<BidirectionalGraph> -make_undirected_graph(const BidirectionalGraph &g) { - return undirected_graph<BidirectionalGraph>(g); -} - -} // namespace ue2 - -namespace boost { - -/* Derive all the property map specializations from the underlying - * bidirectional graph. */ - -template <typename BidirectionalGraph, typename GraphRef, typename Property> -struct property_map<ue2::undirected_graph<BidirectionalGraph, GraphRef>, - Property> { - using base_map_type = property_map<BidirectionalGraph, Property>; - using type = typename base_map_type::type; - using const_type = typename base_map_type::const_type; -}; - -template <class BidirectionalGraph, class GraphRef> -struct vertex_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : vertex_property_type<BidirectionalGraph> {}; - -template <class BidirectionalGraph, class GraphRef> -struct edge_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : edge_property_type<BidirectionalGraph> {}; - -template <class BidirectionalGraph, class GraphRef> -struct graph_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : graph_property_type<BidirectionalGraph> {}; - -template <typename BidirectionalGraph, typename GraphRef> -struct vertex_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : vertex_bundle_type<BidirectionalGraph> {}; - -template <typename BidirectionalGraph, typename GraphRef> -struct edge_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : edge_bundle_type<BidirectionalGraph> {}; - -template <typename BidirectionalGraph, typename GraphRef> -struct graph_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> - : graph_bundle_type<BidirectionalGraph> {}; - -} // namespace boost - -#endif // GRAPH_UNDIRECTED_H +/* + * Copyright (c) 2018, Intel Corporation + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Intel Corporation nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * \brief Adaptor that presents an undirected view of a bidirectional BGL graph. + * + * Analogous to the reverse_graph adapter. You can construct one of these for + * bidirectional graph g with: + * + * auto ug = make_undirected_graph(g); + * + * The vertex descriptor type is the same as that of the underlying graph, but + * the edge descriptor is different. + */ + +#ifndef GRAPH_UNDIRECTED_H +#define GRAPH_UNDIRECTED_H + +#include "util/operators.h" + +#include <boost/graph/adjacency_iterator.hpp> +#include <boost/graph/graph_traits.hpp> +#include <boost/graph/properties.hpp> +#include <boost/iterator/iterator_facade.hpp> + +#include <type_traits> +#include <utility> + +namespace ue2 { + +struct undirected_graph_tag {}; + +template <class BidirectionalGraph, class GraphRef> +class undirected_graph; + +namespace undirected_detail { + +template <typename BidirectionalGraph> +class undirected_graph_edge_descriptor + : totally_ordered<undirected_graph_edge_descriptor<BidirectionalGraph>> { + using base_graph_type = BidirectionalGraph; + using base_graph_traits = typename boost::graph_traits<base_graph_type>; + using base_edge_type = typename base_graph_traits::edge_descriptor; + using base_vertex_type = typename base_graph_traits::vertex_descriptor; + + base_edge_type underlying_edge; + const base_graph_type *g; + bool reverse; // if true, reverse vertices in source() and target() + + inline std::pair<base_vertex_type, base_vertex_type> + canonical_edge() const { + auto u = std::min(source(underlying_edge, *g), + target(underlying_edge, *g)); + auto v = std::max(source(underlying_edge, *g), + target(underlying_edge, *g)); + return std::make_pair(u, v); + } + + template <class BidiGraph, class GraphRef> + friend class ::ue2::undirected_graph; + +public: + undirected_graph_edge_descriptor() = default; + + undirected_graph_edge_descriptor(base_edge_type edge, + const base_graph_type &g_in, + bool reverse_in) + : underlying_edge(std::move(edge)), g(&g_in), reverse(reverse_in) {} + + bool operator==(const undirected_graph_edge_descriptor &other) const { + return canonical_edge() == other.canonical_edge(); + } + + bool operator<(const undirected_graph_edge_descriptor &other) const { + return canonical_edge() < other.canonical_edge(); + } + + base_vertex_type get_source() const { + return reverse ? target(underlying_edge, *g) + : source(underlying_edge, *g); + } + + base_vertex_type get_target() const { + return reverse ? source(underlying_edge, *g) + : target(underlying_edge, *g); + } +}; + +} // namespace undirected_detail + +template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph &> +class undirected_graph { +private: + using Self = undirected_graph<BidirectionalGraph, GraphRef>; + using Traits = boost::graph_traits<BidirectionalGraph>; + +public: + using base_type = BidirectionalGraph; + using base_ref_type = GraphRef; + + explicit undirected_graph(GraphRef g_in) : g(g_in) {} + + // Graph requirements + using vertex_descriptor = typename Traits::vertex_descriptor; + using edge_descriptor = + undirected_detail::undirected_graph_edge_descriptor<base_type>; + using directed_category = boost::undirected_tag; + using edge_parallel_category = boost::disallow_parallel_edge_tag; + using traversal_category = typename Traits::traversal_category; + + // IncidenceGraph requirements + + /** + * \brief Templated iterator used for out_edge_iterator and + * in_edge_iterator, depending on the value of Reverse. + */ + template <bool Reverse> + class adj_edge_iterator + : public boost::iterator_facade< + adj_edge_iterator<Reverse>, edge_descriptor, + boost::forward_traversal_tag, edge_descriptor> { + vertex_descriptor u; + const base_type *g; + typename Traits::in_edge_iterator in_it; + typename Traits::out_edge_iterator out_it; + bool done_in = false; + public: + adj_edge_iterator() = default; + + adj_edge_iterator(vertex_descriptor u_in, const base_type &g_in, + bool end_iter) + : u(std::move(u_in)), g(&g_in) { + auto pi = in_edges(u, *g); + auto po = out_edges(u, *g); + if (end_iter) { + in_it = pi.second; + out_it = po.second; + done_in = true; + } else { + in_it = pi.first; + out_it = po.first; + if (in_it == pi.second) { + done_in = true; + find_first_valid_out(); + } + } + } + + private: + friend class boost::iterator_core_access; + + void find_first_valid_out() { + auto out_end = out_edges(u, *g).second; + for (; out_it != out_end; ++out_it) { + auto v = target(*out_it, *g); + if (!edge(v, u, *g).second) { + break; + } + } + } + + void increment() { + if (!done_in) { + auto in_end = in_edges(u, *g).second; + assert(in_it != in_end); + ++in_it; + if (in_it == in_end) { + done_in = true; + find_first_valid_out(); + } + } else { + ++out_it; + find_first_valid_out(); + } + } + bool equal(const adj_edge_iterator &other) const { + return in_it == other.in_it && out_it == other.out_it; + } + edge_descriptor dereference() const { + if (done_in) { + return edge_descriptor(*out_it, *g, Reverse); + } else { + return edge_descriptor(*in_it, *g, !Reverse); + } + } + }; + + using out_edge_iterator = adj_edge_iterator<false>; + using in_edge_iterator = adj_edge_iterator<true>; + + using degree_size_type = typename Traits::degree_size_type; + + // AdjacencyGraph requirements + using adjacency_iterator = + typename boost::adjacency_iterator_generator<Self, vertex_descriptor, + out_edge_iterator>::type; + using inv_adjacency_iterator = + typename boost::inv_adjacency_iterator_generator< + Self, vertex_descriptor, in_edge_iterator>::type; + + // VertexListGraph requirements + using vertex_iterator = typename Traits::vertex_iterator; + + // EdgeListGraph requirements + enum { + is_edge_list = std::is_convertible<traversal_category, + boost::edge_list_graph_tag>::value + }; + + /** \brief Iterator used for edges(). */ + class edge_iterator + : public boost::iterator_facade<edge_iterator, edge_descriptor, + boost::forward_traversal_tag, + edge_descriptor> { + const base_type *g; + typename Traits::edge_iterator it; + public: + edge_iterator() = default; + + edge_iterator(typename Traits::edge_iterator it_in, + const base_type &g_in) + : g(&g_in), it(std::move(it_in)) { + find_first_valid_edge(); + } + + private: + friend class boost::iterator_core_access; + + void find_first_valid_edge() { + const auto end = edges(*g).second; + for (; it != end; ++it) { + const auto &u = source(*it, *g); + const auto &v = target(*it, *g); + if (!edge(v, u, *g).second) { + break; // No reverse edge, we must visit this one + } + if (u <= v) { + // We have a reverse edge, but we'll return this one (and + // skip the other). Note that (u, u) shouldn't be skipped. + break; + } + } + } + + void increment() { + assert(it != edges(*g).second); + ++it; + find_first_valid_edge(); + } + bool equal(const edge_iterator &other) const { + return it == other.it; + } + edge_descriptor dereference() const { + return edge_descriptor(*it, *g, false); + } + }; + + using vertices_size_type = typename Traits::vertices_size_type; + using edges_size_type = typename Traits::edges_size_type; + + using graph_tag = undirected_graph_tag; + + using vertex_bundle_type = + typename boost::vertex_bundle_type<base_type>::type; + using edge_bundle_type = typename boost::edge_bundle_type<base_type>::type; + + vertex_bundle_type &operator[](const vertex_descriptor &d) { + return const_cast<base_type &>(g)[d]; + } + const vertex_bundle_type &operator[](const vertex_descriptor &d) const { + return g[d]; + } + + edge_bundle_type &operator[](const edge_descriptor &d) { + return const_cast<base_type &>(g)[d.underlying_edge]; + } + const edge_bundle_type &operator[](const edge_descriptor &d) const { + return g[d.underlying_edge]; + } + + static vertex_descriptor null_vertex() { return Traits::null_vertex(); } + + // Accessor free functions follow + + friend std::pair<vertex_iterator, vertex_iterator> + vertices(const undirected_graph &ug) { + return vertices(ug.g); + } + + friend std::pair<edge_iterator, edge_iterator> + edges(const undirected_graph &ug) { + auto e = edges(ug.g); + return std::make_pair(edge_iterator(e.first, ug.g), + edge_iterator(e.second, ug.g)); + } + + friend std::pair<out_edge_iterator, out_edge_iterator> + out_edges(const vertex_descriptor &u, const undirected_graph &ug) { + return std::make_pair(out_edge_iterator(u, ug.g, false), + out_edge_iterator(u, ug.g, true)); + } + + friend vertices_size_type num_vertices(const undirected_graph &ug) { + return num_vertices(ug.g); + } + + friend edges_size_type num_edges(const undirected_graph &ug) { + auto p = edges(ug); + return std::distance(p.first, p.second); + } + + friend degree_size_type out_degree(const vertex_descriptor &u, + const undirected_graph &ug) { + return degree(u, ug); + } + + friend vertex_descriptor vertex(vertices_size_type n, + const undirected_graph &ug) { + return vertex(n, ug.g); + } + + friend std::pair<edge_descriptor, bool> edge(const vertex_descriptor &u, + const vertex_descriptor &v, + const undirected_graph &ug) { + auto e = edge(u, v, ug.g); + if (e.second) { + return std::make_pair(edge_descriptor(e.first, ug.g, false), true); + } + auto e_rev = edge(v, u, ug.g); + if (e_rev.second) { + return std::make_pair(edge_descriptor(e_rev.first, ug.g, true), + true); + } + return std::make_pair(edge_descriptor(), false); + } + + friend std::pair<in_edge_iterator, in_edge_iterator> + in_edges(const vertex_descriptor &v, const undirected_graph &ug) { + return std::make_pair(in_edge_iterator(v, ug.g, false), + in_edge_iterator(v, ug.g, true)); + } + + friend std::pair<adjacency_iterator, adjacency_iterator> + adjacent_vertices(const vertex_descriptor &u, const undirected_graph &ug) { + out_edge_iterator oi, oe; + std::tie(oi, oe) = out_edges(u, ug); + return std::make_pair(adjacency_iterator(oi, &ug), + adjacency_iterator(oe, &ug)); + } + + friend std::pair<inv_adjacency_iterator, inv_adjacency_iterator> + inv_adjacent_vertices(const vertex_descriptor &v, + const undirected_graph &ug) { + in_edge_iterator ei, ee; + std::tie(ei, ee) = in_edges(v, ug); + return std::make_pair(inv_adjacency_iterator(ei, &ug), + inv_adjacency_iterator(ee, &ug)); + } + + friend degree_size_type in_degree(const vertex_descriptor &v, + const undirected_graph &ug) { + return degree(v, ug); + } + + friend vertex_descriptor source(const edge_descriptor &e, + const undirected_graph &) { + return e.get_source(); + } + + friend vertex_descriptor target(const edge_descriptor &e, + const undirected_graph &) { + return e.get_target(); + } + + friend degree_size_type degree(const vertex_descriptor &u, + const undirected_graph &ug) { + auto p = out_edges(u, ug); + return std::distance(p.first, p.second); + } + + // Property accessors. + + template <typename Property> + using prop_map = typename boost::property_map<undirected_graph, Property>; + + template <typename Property> + friend typename prop_map<Property>::type + get(Property p, undirected_graph &ug) { + return get(p, ug.g); + } + + template <typename Property> + friend typename prop_map<Property>::const_type + get(Property p, const undirected_graph &ug) { + return get(p, ug.g); + } + + template <typename Property, typename Key> + friend typename boost::property_traits< + typename prop_map<Property>::const_type>::value_type + get(Property p, const undirected_graph &ug, const Key &k) { + return get(p, ug.g, get_underlying_descriptor(k)); + } + + template <typename Property, typename Value, typename Key> + friend void put(Property p, const undirected_graph &ug, + const Key &k, const Value &val) { + put(p, const_cast<BidirectionalGraph &>(ug.g), + get_underlying_descriptor(k), val); + } + +private: + // Accessors are here because our free friend functions (above) cannot see + // edge_descriptor's private members. + static typename base_type::vertex_descriptor + get_underlying_descriptor(const vertex_descriptor &v) { + return v; + } + static typename base_type::edge_descriptor + get_underlying_descriptor(const edge_descriptor &e) { + return e.underlying_edge; + } + + // Reference to underlying bidirectional graph + GraphRef g; +}; + +template <class BidirectionalGraph> +undirected_graph<BidirectionalGraph> +make_undirected_graph(const BidirectionalGraph &g) { + return undirected_graph<BidirectionalGraph>(g); +} + +} // namespace ue2 + +namespace boost { + +/* Derive all the property map specializations from the underlying + * bidirectional graph. */ + +template <typename BidirectionalGraph, typename GraphRef, typename Property> +struct property_map<ue2::undirected_graph<BidirectionalGraph, GraphRef>, + Property> { + using base_map_type = property_map<BidirectionalGraph, Property>; + using type = typename base_map_type::type; + using const_type = typename base_map_type::const_type; +}; + +template <class BidirectionalGraph, class GraphRef> +struct vertex_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : vertex_property_type<BidirectionalGraph> {}; + +template <class BidirectionalGraph, class GraphRef> +struct edge_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : edge_property_type<BidirectionalGraph> {}; + +template <class BidirectionalGraph, class GraphRef> +struct graph_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : graph_property_type<BidirectionalGraph> {}; + +template <typename BidirectionalGraph, typename GraphRef> +struct vertex_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : vertex_bundle_type<BidirectionalGraph> {}; + +template <typename BidirectionalGraph, typename GraphRef> +struct edge_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : edge_bundle_type<BidirectionalGraph> {}; + +template <typename BidirectionalGraph, typename GraphRef> +struct graph_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>> + : graph_bundle_type<BidirectionalGraph> {}; + +} // namespace boost + +#endif // GRAPH_UNDIRECTED_H diff --git a/contrib/libs/hyperscan/src/util/logical.h b/contrib/libs/hyperscan/src/util/logical.h index 134c786ccd..0c8b6469aa 100644 --- a/contrib/libs/hyperscan/src/util/logical.h +++ b/contrib/libs/hyperscan/src/util/logical.h @@ -1,77 +1,77 @@ -/* - * Copyright (c) 2018, Intel Corporation - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * * Neither the name of Intel Corporation nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - */ - -/** \file - * \brief Inline functions for manipulating logical combinations. - */ - -#ifndef LOGICAL_H -#define LOGICAL_H - -#include "ue2common.h" - -/** Index meaning a given logical key is invalid. */ -#define INVALID_LKEY (~(u32)0) -#define INVALID_CKEY INVALID_LKEY - -/** Logical operation type, the priority is from high to low. */ -enum LogicalOpType { - LOGICAL_OP_NOT, - LOGICAL_OP_AND, - LOGICAL_OP_OR, - LAST_LOGICAL_OP = LOGICAL_OP_OR //!< Sentinel. -}; - -#define UNKNOWN_OP (~(u32)0) - -/** Logical Operation is consist of 4 parts. */ -struct LogicalOp { - u32 id; //!< logical operator/operation id - u32 op; //!< LogicalOpType - u32 lo; //!< left operand - u32 ro; //!< right operand -}; - -/** Each logical combination has its info: - * It occupies a region in LogicalOp vector. - * It has an exhaustion key for single-match mode. */ -struct CombInfo { - u32 id; - u32 ekey; //!< exhaustion key - u32 start; //!< ckey of logical operation to start calculating - u32 result; //!< ckey of logical operation to give final result - u64a min_offset; - u64a max_offset; -}; - -/** Temporarily use to seperate operations' id from reports' lkey - * when building logicalTree in shunting yard algorithm, - * operations' id will be finally renumbered following reports' lkey. */ -#define LOGICAL_OP_BIT 0x80000000UL - -#endif +/* + * Copyright (c) 2018, Intel Corporation + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Intel Corporation nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** \file + * \brief Inline functions for manipulating logical combinations. + */ + +#ifndef LOGICAL_H +#define LOGICAL_H + +#include "ue2common.h" + +/** Index meaning a given logical key is invalid. */ +#define INVALID_LKEY (~(u32)0) +#define INVALID_CKEY INVALID_LKEY + +/** Logical operation type, the priority is from high to low. */ +enum LogicalOpType { + LOGICAL_OP_NOT, + LOGICAL_OP_AND, + LOGICAL_OP_OR, + LAST_LOGICAL_OP = LOGICAL_OP_OR //!< Sentinel. +}; + +#define UNKNOWN_OP (~(u32)0) + +/** Logical Operation is consist of 4 parts. */ +struct LogicalOp { + u32 id; //!< logical operator/operation id + u32 op; //!< LogicalOpType + u32 lo; //!< left operand + u32 ro; //!< right operand +}; + +/** Each logical combination has its info: + * It occupies a region in LogicalOp vector. + * It has an exhaustion key for single-match mode. */ +struct CombInfo { + u32 id; + u32 ekey; //!< exhaustion key + u32 start; //!< ckey of logical operation to start calculating + u32 result; //!< ckey of logical operation to give final result + u64a min_offset; + u64a max_offset; +}; + +/** Temporarily use to seperate operations' id from reports' lkey + * when building logicalTree in shunting yard algorithm, + * operations' id will be finally renumbered following reports' lkey. */ +#define LOGICAL_OP_BIT 0x80000000UL + +#endif diff --git a/contrib/libs/hyperscan/src/util/multibit.h b/contrib/libs/hyperscan/src/util/multibit.h index caa7bd7b20..c3a4ba461a 100644 --- a/contrib/libs/hyperscan/src/util/multibit.h +++ b/contrib/libs/hyperscan/src/util/multibit.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2018, Intel Corporation + * Copyright (c) 2015-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -1197,11 +1197,11 @@ u32 mmbit_sparse_iter_begin(const u8 *bits, u32 total_bits, u32 *idx, assert(ISALIGNED_N(it_root, alignof(struct mmbit_sparse_iter))); // Our state _may_ be on the stack -#ifndef _WIN32 +#ifndef _WIN32 assert(ISALIGNED_N(s, alignof(struct mmbit_sparse_state))); -#else - assert(ISALIGNED_N(s, 4)); -#endif +#else + assert(ISALIGNED_N(s, 4)); +#endif MDEBUG_PRINTF("%p total_bits %u\n", bits, total_bits); // iterator should have _something_ at the root level @@ -1309,11 +1309,11 @@ u32 mmbit_sparse_iter_next(const u8 *bits, u32 total_bits, u32 last_key, assert(ISALIGNED_N(it_root, alignof(struct mmbit_sparse_iter))); // Our state _may_ be on the stack -#ifndef _WIN32 +#ifndef _WIN32 assert(ISALIGNED_N(s, alignof(struct mmbit_sparse_state))); -#else - assert(ISALIGNED_N(s, 4)); -#endif +#else + assert(ISALIGNED_N(s, 4)); +#endif MDEBUG_PRINTF("%p total_bits %u\n", bits, total_bits); MDEBUG_PRINTF("NEXT (total_bits=%u, last_key=%u)\n", total_bits, last_key); @@ -1466,11 +1466,11 @@ void mmbit_sparse_iter_unset(u8 *bits, u32 total_bits, assert(ISALIGNED_N(it, alignof(struct mmbit_sparse_iter))); // Our state _may_ be on the stack -#ifndef _WIN32 +#ifndef _WIN32 assert(ISALIGNED_N(s, alignof(struct mmbit_sparse_state))); -#else - assert(ISALIGNED_N(s, 4)); -#endif +#else + assert(ISALIGNED_N(s, 4)); +#endif MDEBUG_PRINTF("%p total_bits %u\n", bits, total_bits); diff --git a/contrib/libs/hyperscan/src/util/multibit_build.cpp b/contrib/libs/hyperscan/src/util/multibit_build.cpp index 9cf5799424..67bb9ec702 100644 --- a/contrib/libs/hyperscan/src/util/multibit_build.cpp +++ b/contrib/libs/hyperscan/src/util/multibit_build.cpp @@ -192,8 +192,8 @@ vector<mmbit_sparse_iter> mmbBuildSparseIterator(const vector<u32> &bits, template<typename T> static void add_scatter(vector<T> *out, u32 offset, u64a mask) { - out->emplace_back(); - T &su = out->back(); + out->emplace_back(); + T &su = out->back(); memset(&su, 0, sizeof(su)); su.offset = offset; su.val = mask; diff --git a/contrib/libs/hyperscan/src/util/multibit_build.h b/contrib/libs/hyperscan/src/util/multibit_build.h index 52bac41f6a..24f1bb55b0 100644 --- a/contrib/libs/hyperscan/src/util/multibit_build.h +++ b/contrib/libs/hyperscan/src/util/multibit_build.h @@ -33,7 +33,7 @@ #ifndef MULTIBIT_BUILD_H #define MULTIBIT_BUILD_H -#include "hs_common.h" +#include "hs_common.h" #include "multibit_internal.h" #include "hash.h" diff --git a/contrib/libs/hyperscan/src/util/report.h b/contrib/libs/hyperscan/src/util/report.h index 35922bcedb..ee830d0f10 100644 --- a/contrib/libs/hyperscan/src/util/report.h +++ b/contrib/libs/hyperscan/src/util/report.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2018, Intel Corporation + * Copyright (c) 2015-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -36,7 +36,7 @@ #include "ue2common.h" #include "util/exhaust.h" // for INVALID_EKEY -#include "util/logical.h" // for INVALID_LKEY +#include "util/logical.h" // for INVALID_LKEY #include "util/hash.h" #include "util/order_check.h" @@ -108,16 +108,16 @@ struct Report { * exhaustible, this will be INVALID_EKEY. */ u32 ekey = INVALID_EKEY; - /** \brief Logical Combination key in each combination. - * - * If in Logical Combination, the lkey to check before reporting a match. - * Additionally before checking the lkey will be set. If not - * in Logical Combination, this will be INVALID_LKEY. */ - u32 lkey = INVALID_LKEY; - - /** \brief Quiet flag for expressions in any logical combination. */ - bool quiet = false; - + /** \brief Logical Combination key in each combination. + * + * If in Logical Combination, the lkey to check before reporting a match. + * Additionally before checking the lkey will be set. If not + * in Logical Combination, this will be INVALID_LKEY. */ + u32 lkey = INVALID_LKEY; + + /** \brief Quiet flag for expressions in any logical combination. */ + bool quiet = false; + /** \brief Adjustment to add to the match offset when we report a match. * * This is usually used for reports attached to states that form part of a @@ -218,17 +218,17 @@ bool operator==(const Report &a, const Report &b) { } static inline -Report makeECallback(u32 report, s32 offsetAdjust, u32 ekey, bool quiet) { +Report makeECallback(u32 report, s32 offsetAdjust, u32 ekey, bool quiet) { Report ir(EXTERNAL_CALLBACK, report); ir.offsetAdjust = offsetAdjust; ir.ekey = ekey; - ir.quiet = (u8)quiet; + ir.quiet = (u8)quiet; return ir; } static inline Report makeCallback(u32 report, s32 offsetAdjust) { - return makeECallback(report, offsetAdjust, INVALID_EKEY, false); + return makeECallback(report, offsetAdjust, INVALID_EKEY, false); } static inline diff --git a/contrib/libs/hyperscan/src/util/report_manager.cpp b/contrib/libs/hyperscan/src/util/report_manager.cpp index bf6208849d..78b9b73dfc 100644 --- a/contrib/libs/hyperscan/src/util/report_manager.cpp +++ b/contrib/libs/hyperscan/src/util/report_manager.cpp @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2018, Intel Corporation + * Copyright (c) 2015-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -95,31 +95,31 @@ u32 ReportManager::getExhaustibleKey(u32 a) { return it->second; } -const set<u32> &ReportManager::getRelateCKeys(u32 lkey) { - auto it = pl.lkey2ckeys.find(lkey); - assert(it != pl.lkey2ckeys.end()); - return it->second; -} - -void ReportManager::logicalKeyRenumber() { - pl.logicalKeyRenumber(); - // assign to corresponding report - for (u32 i = 0; i < reportIds.size(); i++) { - Report &ir = reportIds[i]; - if (contains(pl.toLogicalKeyMap, ir.onmatch)) { - ir.lkey = pl.toLogicalKeyMap.at(ir.onmatch); - } - } -} - -const vector<LogicalOp> &ReportManager::getLogicalTree() const { - return pl.logicalTree; -} - -const vector<CombInfo> &ReportManager::getCombInfoMap() const { - return pl.combInfoMap; -} - +const set<u32> &ReportManager::getRelateCKeys(u32 lkey) { + auto it = pl.lkey2ckeys.find(lkey); + assert(it != pl.lkey2ckeys.end()); + return it->second; +} + +void ReportManager::logicalKeyRenumber() { + pl.logicalKeyRenumber(); + // assign to corresponding report + for (u32 i = 0; i < reportIds.size(); i++) { + Report &ir = reportIds[i]; + if (contains(pl.toLogicalKeyMap, ir.onmatch)) { + ir.lkey = pl.toLogicalKeyMap.at(ir.onmatch); + } + } +} + +const vector<LogicalOp> &ReportManager::getLogicalTree() const { + return pl.logicalTree; +} + +const vector<CombInfo> &ReportManager::getCombInfoMap() const { + return pl.combInfoMap; +} + u32 ReportManager::getUnassociatedExhaustibleKey(void) { u32 rv = toExhaustibleKeyMap.size(); bool inserted; @@ -140,18 +140,18 @@ u32 ReportManager::numEkeys() const { return (u32) toExhaustibleKeyMap.size(); } -u32 ReportManager::numLogicalKeys() const { - return (u32) pl.toLogicalKeyMap.size(); -} - -u32 ReportManager::numLogicalOps() const { - return (u32) pl.logicalTree.size(); -} - -u32 ReportManager::numCkeys() const { - return (u32) pl.toCombKeyMap.size(); -} - +u32 ReportManager::numLogicalKeys() const { + return (u32) pl.toLogicalKeyMap.size(); +} + +u32 ReportManager::numLogicalOps() const { + return (u32) pl.logicalTree.size(); +} + +u32 ReportManager::numCkeys() const { + return (u32) pl.toCombKeyMap.size(); +} + bool ReportManager::patternSetCanExhaust() const { return global_exhaust && !toExhaustibleKeyMap.empty(); } @@ -256,7 +256,7 @@ Report ReportManager::getBasicInternalReport(const ExpressionInfo &expr, ekey = getExhaustibleKey(expr.report); } - return makeECallback(expr.report, adj, ekey, expr.quiet); + return makeECallback(expr.report, adj, ekey, expr.quiet); } void ReportManager::setProgramOffset(ReportID id, u32 programOffset) { diff --git a/contrib/libs/hyperscan/src/util/report_manager.h b/contrib/libs/hyperscan/src/util/report_manager.h index 017545a5d1..015dc9c855 100644 --- a/contrib/libs/hyperscan/src/util/report_manager.h +++ b/contrib/libs/hyperscan/src/util/report_manager.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2018, Intel Corporation + * Copyright (c) 2015-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -38,7 +38,7 @@ #include "util/compile_error.h" #include "util/noncopyable.h" #include "util/report.h" -#include "parser/logical_combination.h" +#include "parser/logical_combination.h" #include <map> #include <set> @@ -81,15 +81,15 @@ public: /** \brief Total number of exhaustion keys. */ u32 numEkeys() const; - /** \brief Total number of logical keys. */ - u32 numLogicalKeys() const; - - /** \brief Total number of logical operators. */ - u32 numLogicalOps() const; - - /** \brief Total number of combination keys. */ - u32 numCkeys() const; - + /** \brief Total number of logical keys. */ + u32 numLogicalKeys() const; + + /** \brief Total number of logical operators. */ + u32 numLogicalOps() const; + + /** \brief Total number of combination keys. */ + u32 numCkeys() const; + /** \brief True if the pattern set can exhaust (i.e. all patterns are * highlander). */ bool patternSetCanExhaust() const; @@ -120,19 +120,19 @@ public: * assigning one if necessary. */ u32 getExhaustibleKey(u32 expressionIndex); - /** \brief Get lkey's corresponding ckeys. */ - const std::set<u32> &getRelateCKeys(u32 lkey); - - /** \brief Renumber lkey for logical operations, after parsed - * all logical expressions. */ - void logicalKeyRenumber(); - - /** \brief Used in Rose for writing bytecode. */ - const std::vector<LogicalOp> &getLogicalTree() const; - - /** \brief Used in Rose for writing bytecode. */ - const std::vector<CombInfo> &getCombInfoMap() const; - + /** \brief Get lkey's corresponding ckeys. */ + const std::set<u32> &getRelateCKeys(u32 lkey); + + /** \brief Renumber lkey for logical operations, after parsed + * all logical expressions. */ + void logicalKeyRenumber(); + + /** \brief Used in Rose for writing bytecode. */ + const std::vector<LogicalOp> &getLogicalTree() const; + + /** \brief Used in Rose for writing bytecode. */ + const std::vector<CombInfo> &getCombInfoMap() const; + /** \brief Fetch the dedupe key associated with the given report. Returns * ~0U if no dkey is needed. */ u32 getDkey(const Report &r) const; @@ -145,9 +145,9 @@ public: * set. */ u32 getProgramOffset(ReportID id) const; - /** \brief Parsed logical combination structure. */ - ParsedLogical pl; - + /** \brief Parsed logical combination structure. */ + ParsedLogical pl; + private: /** \brief Grey box ref, for checking resource limits. */ const Grey &grey; diff --git a/contrib/libs/hyperscan/src/util/simd_utils.h b/contrib/libs/hyperscan/src/util/simd_utils.h index 03b90e2c7a..d1f060b070 100644 --- a/contrib/libs/hyperscan/src/util/simd_utils.h +++ b/contrib/libs/hyperscan/src/util/simd_utils.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2020, Intel Corporation + * Copyright (c) 2015-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -138,12 +138,12 @@ m128 lshift64_m128(m128 a, unsigned b) { #define eq128(a, b) _mm_cmpeq_epi8((a), (b)) #define movemask128(a) ((u32)_mm_movemask_epi8((a))) -#if defined(HAVE_AVX512) -static really_inline m128 cast512to128(const m512 in) { - return _mm512_castsi512_si128(in); -} -#endif - +#if defined(HAVE_AVX512) +static really_inline m128 cast512to128(const m512 in) { + return _mm512_castsi512_si128(in); +} +#endif + static really_inline m128 set16x8(u8 c) { return _mm_set1_epi8(c); } @@ -156,20 +156,20 @@ static really_inline u32 movd(const m128 in) { return _mm_cvtsi128_si32(in); } -#if defined(HAVE_AVX512) -static really_inline u32 movd512(const m512 in) { - // NOTE: seems gcc doesn't support _mm512_cvtsi512_si32(in), - // so we use 2-step convertions to work around. - return _mm_cvtsi128_si32(_mm512_castsi512_si128(in)); -} - -static really_inline u64a movq512(const m512 in) { - // NOTE: seems AVX512 doesn't support _mm512_cvtsi512_si64(in), - // so we use 2-step convertions to work around. - return _mm_cvtsi128_si64(_mm512_castsi512_si128(in)); -} -#endif - +#if defined(HAVE_AVX512) +static really_inline u32 movd512(const m512 in) { + // NOTE: seems gcc doesn't support _mm512_cvtsi512_si32(in), + // so we use 2-step convertions to work around. + return _mm_cvtsi128_si32(_mm512_castsi512_si128(in)); +} + +static really_inline u64a movq512(const m512 in) { + // NOTE: seems AVX512 doesn't support _mm512_cvtsi512_si64(in), + // so we use 2-step convertions to work around. + return _mm_cvtsi128_si64(_mm512_castsi512_si128(in)); +} +#endif + static really_inline u64a movq(const m128 in) { #if defined(ARCH_X86_64) return _mm_cvtsi128_si64(in); @@ -223,24 +223,24 @@ static really_inline m128 or128(m128 a, m128 b) { return _mm_or_si128(a,b); } -#if defined(HAVE_AVX512VBMI) -static really_inline m512 expand128(m128 a) { - return _mm512_broadcast_i32x4(a); -} - -static really_inline m512 expand256(m256 a) { - return _mm512_broadcast_i64x4(a); -} - -static really_inline m512 expand384(m384 a) { - u64a *lo = (u64a*)&a.lo; - u64a *mid = (u64a*)&a.mid; - u64a *hi = (u64a*)&a.hi; - return _mm512_set_epi64(0ULL, 0ULL, hi[1], hi[0], mid[1], mid[0], - lo[1], lo[0]); -} -#endif - +#if defined(HAVE_AVX512VBMI) +static really_inline m512 expand128(m128 a) { + return _mm512_broadcast_i32x4(a); +} + +static really_inline m512 expand256(m256 a) { + return _mm512_broadcast_i64x4(a); +} + +static really_inline m512 expand384(m384 a) { + u64a *lo = (u64a*)&a.lo; + u64a *mid = (u64a*)&a.mid; + u64a *hi = (u64a*)&a.hi; + return _mm512_set_epi64(0ULL, 0ULL, hi[1], hi[0], mid[1], mid[0], + lo[1], lo[0]); +} +#endif + static really_inline m128 andnot128(m128 a, m128 b) { return _mm_andnot_si128(a, b); } @@ -356,14 +356,14 @@ static really_inline m512 maskz_pshufb_m512(__mmask64 k, m512 a, m512 b) { return _mm512_maskz_shuffle_epi8(k, a, b); } - -#if defined(HAVE_AVX512VBMI) -#define vpermb512(idx, a) _mm512_permutexvar_epi8(idx, a) -#define maskz_vpermb512(k, idx, a) _mm512_maskz_permutexvar_epi8(k, idx, a) + +#if defined(HAVE_AVX512VBMI) +#define vpermb512(idx, a) _mm512_permutexvar_epi8(idx, a) +#define maskz_vpermb512(k, idx, a) _mm512_maskz_permutexvar_epi8(k, idx, a) +#endif + #endif -#endif - static really_inline m128 variable_byte_shift_m128(m128 in, s32 amount) { assert(amount >= -16 && amount <= 16); @@ -1031,11 +1031,11 @@ m512 set8x64(u64a a) { } static really_inline -m512 set16x32(u32 a) { - return _mm512_set1_epi32(a); -} - -static really_inline +m512 set16x32(u32 a) { + return _mm512_set1_epi32(a); +} + +static really_inline m512 set512_64(u64a hi_3, u64a hi_2, u64a hi_1, u64a hi_0, u64a lo_3, u64a lo_2, u64a lo_1, u64a lo_0) { return _mm512_set_epi64(hi_3, hi_2, hi_1, hi_0, @@ -1052,26 +1052,26 @@ static really_inline m512 set4x128(m128 a) { return _mm512_broadcast_i32x4(a); } - -static really_inline -m512 sadd_u8_m512(m512 a, m512 b) { - return _mm512_adds_epu8(a, b); -} - -static really_inline -m512 max_u8_m512(m512 a, m512 b) { - return _mm512_max_epu8(a, b); -} - -static really_inline -m512 min_u8_m512(m512 a, m512 b) { - return _mm512_min_epu8(a, b); -} - -static really_inline -m512 sub_u8_m512(m512 a, m512 b) { - return _mm512_sub_epi8(a, b); -} + +static really_inline +m512 sadd_u8_m512(m512 a, m512 b) { + return _mm512_adds_epu8(a, b); +} + +static really_inline +m512 max_u8_m512(m512 a, m512 b) { + return _mm512_max_epu8(a, b); +} + +static really_inline +m512 min_u8_m512(m512 a, m512 b) { + return _mm512_min_epu8(a, b); +} + +static really_inline +m512 sub_u8_m512(m512 a, m512 b) { + return _mm512_sub_epi8(a, b); +} #endif static really_inline @@ -1259,23 +1259,23 @@ m512 loadu512(const void *ptr) { #endif } -// unaligned store -static really_inline -void storeu512(void *ptr, m512 a) { +// unaligned store +static really_inline +void storeu512(void *ptr, m512 a) { +#if defined(HAVE_AVX512) + _mm512_storeu_si512((m512 *)ptr, a); +#elif defined(HAVE_AVX2) + storeu256(ptr, a.lo); + storeu256((char *)ptr + 32, a.hi); +#else + storeu128(ptr, a.lo.lo); + storeu128((char *)ptr + 16, a.lo.hi); + storeu128((char *)ptr + 32, a.hi.lo); + storeu128((char *)ptr + 48, a.hi.hi); +#endif +} + #if defined(HAVE_AVX512) - _mm512_storeu_si512((m512 *)ptr, a); -#elif defined(HAVE_AVX2) - storeu256(ptr, a.lo); - storeu256((char *)ptr + 32, a.hi); -#else - storeu128(ptr, a.lo.lo); - storeu128((char *)ptr + 16, a.lo.hi); - storeu128((char *)ptr + 32, a.hi.lo); - storeu128((char *)ptr + 48, a.hi.hi); -#endif -} - -#if defined(HAVE_AVX512) static really_inline m512 loadu_maskz_m512(__mmask64 k, const void *ptr) { return _mm512_maskz_loadu_epi8(k, ptr); @@ -1287,19 +1287,19 @@ m512 loadu_mask_m512(m512 src, __mmask64 k, const void *ptr) { } static really_inline -void storeu_mask_m512(void *ptr, __mmask64 k, m512 a) { - _mm512_mask_storeu_epi8(ptr, k, a); -} - -static really_inline +void storeu_mask_m512(void *ptr, __mmask64 k, m512 a) { + _mm512_mask_storeu_epi8(ptr, k, a); +} + +static really_inline m512 set_mask_m512(__mmask64 k) { return _mm512_movm_epi8(k); } - -static really_inline -m256 loadu_maskz_m256(__mmask32 k, const void *ptr) { - return _mm256_maskz_loadu_epi8(k, ptr); -} + +static really_inline +m256 loadu_maskz_m256(__mmask32 k, const void *ptr) { + return _mm256_maskz_loadu_epi8(k, ptr); +} #endif // packed unaligned store of first N bytes diff --git a/contrib/libs/hyperscan/src/util/target_info.cpp b/contrib/libs/hyperscan/src/util/target_info.cpp index 21fbb6d39b..66ba5f5acc 100644 --- a/contrib/libs/hyperscan/src/util/target_info.cpp +++ b/contrib/libs/hyperscan/src/util/target_info.cpp @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2020, Intel Corporation + * Copyright (c) 2015-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -50,10 +50,10 @@ bool target_t::can_run_on_code_built_for(const target_t &code_target) const { return false; } - if (!has_avx512vbmi() && code_target.has_avx512vbmi()) { - return false; - } - + if (!has_avx512vbmi() && code_target.has_avx512vbmi()) { + return false; + } + return true; } @@ -68,10 +68,10 @@ bool target_t::has_avx512(void) const { return cpu_features & HS_CPU_FEATURES_AVX512; } -bool target_t::has_avx512vbmi(void) const { - return cpu_features & HS_CPU_FEATURES_AVX512VBMI; -} - +bool target_t::has_avx512vbmi(void) const { + return cpu_features & HS_CPU_FEATURES_AVX512VBMI; +} + bool target_t::is_atom_class(void) const { return tune == HS_TUNE_FAMILY_SLM || tune == HS_TUNE_FAMILY_GLM; } diff --git a/contrib/libs/hyperscan/src/util/target_info.h b/contrib/libs/hyperscan/src/util/target_info.h index 803c002a48..f64573aeda 100644 --- a/contrib/libs/hyperscan/src/util/target_info.h +++ b/contrib/libs/hyperscan/src/util/target_info.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2020, Intel Corporation + * Copyright (c) 2015-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -42,8 +42,8 @@ struct target_t { bool has_avx512(void) const; - bool has_avx512vbmi(void) const; - + bool has_avx512vbmi(void) const; + bool is_atom_class(void) const; // This asks: can this target (the object) run on code that was built for diff --git a/contrib/libs/hyperscan/src/util/ue2_graph.h b/contrib/libs/hyperscan/src/util/ue2_graph.h index f99f28f5cd..aa9718d73a 100644 --- a/contrib/libs/hyperscan/src/util/ue2_graph.h +++ b/contrib/libs/hyperscan/src/util/ue2_graph.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2016-2018, Intel Corporation + * Copyright (c) 2016-2018, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -89,7 +89,7 @@ * (1) Deterministic ordering for vertices and edges * boost::adjacency_list<> uses pointer ordering for vertex_descriptors. As * a result, ordering of vertices and edges between runs is - * non-deterministic unless containers, etc use custom comparators. + * non-deterministic unless containers, etc use custom comparators. * * (2) Proper types for descriptors, etc. * No more void * for vertex_descriptors and trying to use it for the wrong @@ -288,7 +288,7 @@ private: vertex_edge_list<in_edge_hook> in_edge_list; /* The out going edges are considered owned by the vertex and - * need to be freed when the graph is being destroyed */ + * need to be freed when the graph is being destroyed */ vertex_edge_list<out_edge_hook> out_edge_list; /* The destructor only frees memory owned by the vertex and will leave @@ -1025,208 +1025,208 @@ public: } }; -/** \brief Type trait to enable on whether the Graph is an ue2_graph. */ +/** \brief Type trait to enable on whether the Graph is an ue2_graph. */ template<typename Graph> -struct is_ue2_graph - : public ::std::integral_constant< - bool, std::is_base_of<graph_detail::graph_base, Graph>::value> {}; - -template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertex_descriptor>::type +struct is_ue2_graph + : public ::std::integral_constant< + bool, std::is_base_of<graph_detail::graph_base, Graph>::value> {}; + +template<typename Graph> +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertex_descriptor>::type add_vertex(Graph &g) { return g.add_vertex_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_vertex(typename Graph::vertex_descriptor v, Graph &g) { g.remove_vertex_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type clear_in_edges(typename Graph::vertex_descriptor v, Graph &g) { g.clear_in_edges_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type clear_out_edges(typename Graph::vertex_descriptor v, Graph &g) { g.clear_out_edges_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type clear_vertex(typename Graph::vertex_descriptor v, Graph &g) { g.clear_in_edges_impl(v); g.clear_out_edges_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertex_descriptor>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertex_descriptor>::type source(typename Graph::edge_descriptor e, const Graph &) { return Graph::source_impl(e); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertex_descriptor>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertex_descriptor>::type target(typename Graph::edge_descriptor e, const Graph &) { return Graph::target_impl(e); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::degree_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::degree_size_type>::type out_degree(typename Graph::vertex_descriptor v, const Graph &) { return Graph::out_degree_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::out_edge_iterator, - typename Graph::out_edge_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::out_edge_iterator, + typename Graph::out_edge_iterator>>::type out_edges(typename Graph::vertex_descriptor v, const Graph &) { return Graph::out_edges_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::degree_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::degree_size_type>::type in_degree(typename Graph::vertex_descriptor v, const Graph &) { return Graph::in_degree_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::in_edge_iterator, - typename Graph::in_edge_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::in_edge_iterator, + typename Graph::in_edge_iterator>>::type in_edges(typename Graph::vertex_descriptor v, const Graph &) { return Graph::in_edges_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::degree_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::degree_size_type>::type degree(typename Graph::vertex_descriptor v, const Graph &) { return Graph::degree_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::adjacency_iterator, - typename Graph::adjacency_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::adjacency_iterator, + typename Graph::adjacency_iterator>>::type adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) { return Graph::adjacent_vertices_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::edge_descriptor, bool>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::edge_descriptor, bool>>::type edge(typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v, const Graph &g) { return g.edge_impl(u, v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::inv_adjacency_iterator, - typename Graph::inv_adjacency_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::inv_adjacency_iterator, + typename Graph::inv_adjacency_iterator>>::type inv_adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) { return Graph::inv_adjacent_vertices_impl(v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::edge_descriptor, bool>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::edge_descriptor, bool>>::type add_edge(typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v, Graph &g) { return g.add_edge_impl(u, v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_edge(typename Graph::edge_descriptor e, Graph &g) { g.remove_edge_impl(e); } template<typename Graph, typename Iter> typename std::enable_if< - !std::is_convertible<Iter, typename Graph::edge_descriptor>::value && - is_ue2_graph<Graph>::value>::type + !std::is_convertible<Iter, typename Graph::edge_descriptor>::value && + is_ue2_graph<Graph>::value>::type remove_edge(Iter it, Graph &g) { g.remove_edge_impl(*it); } template<typename Graph, typename Predicate> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_out_edge_if(typename Graph::vertex_descriptor v, Predicate pred, Graph &g) { g.remove_out_edge_if_impl(v, pred); } template<typename Graph, typename Predicate> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_in_edge_if(typename Graph::vertex_descriptor v, Predicate pred, Graph &g) { g.remove_in_edge_if_impl(v, pred); } template<typename Graph, typename Predicate> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_edge_if(Predicate pred, Graph &g) { g.remove_edge_if_impl(pred); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type remove_edge(const typename Graph::vertex_descriptor &u, const typename Graph::vertex_descriptor &v, Graph &g) { g.remove_edge_impl(u, v); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertices_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertices_size_type>::type num_vertices(const Graph &g) { return g.num_vertices_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::vertex_iterator, - typename Graph::vertex_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::vertex_iterator, + typename Graph::vertex_iterator>>::type vertices(const Graph &g) { return g.vertices_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::edges_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::edges_size_type>::type num_edges(const Graph &g) { return g.num_edges_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::edge_iterator, - typename Graph::edge_iterator>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::edge_iterator, + typename Graph::edge_iterator>>::type edges(const Graph &g) { return g.edges_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertex_descriptor>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertex_descriptor>::type add_vertex(const typename Graph::vertex_property_type &vp, Graph &g) { return g.add_vertex_impl(vp); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - std::pair<typename Graph::edge_descriptor, bool>>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + std::pair<typename Graph::edge_descriptor, bool>>::type add_edge(typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v, const typename Graph::edge_property_type &ep, Graph &g) { @@ -1234,59 +1234,59 @@ add_edge(typename Graph::vertex_descriptor u, } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type renumber_edges(Graph &g) { g.renumber_edges_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value>::type +typename std::enable_if<is_ue2_graph<Graph>::value>::type renumber_vertices(Graph &g) { g.renumber_vertices_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::vertices_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::vertices_size_type>::type vertex_index_upper_bound(const Graph &g) { return g.vertex_index_upper_bound_impl(); } template<typename Graph> -typename std::enable_if<is_ue2_graph<Graph>::value, - typename Graph::edges_size_type>::type +typename std::enable_if<is_ue2_graph<Graph>::value, + typename Graph::edges_size_type>::type edge_index_upper_bound(const Graph &g) { return g.edge_index_upper_bound_impl(); } -template<typename T> struct pointer_to_member_traits {}; - -template<typename Return, typename Class> -struct pointer_to_member_traits<Return(Class::*)> { - using member_type = Return; - using class_type = Class; -}; - -template<typename Graph, typename Property, typename Enable = void> -struct is_ue2_vertex_or_edge_property { - static constexpr bool value = false; -}; - -template<typename Graph, typename Property> -struct is_ue2_vertex_or_edge_property< - Graph, Property, typename std::enable_if<is_ue2_graph<Graph>::value && - std::is_member_object_pointer< - Property>::value>::type> { -private: - using class_type = typename pointer_to_member_traits<Property>::class_type; - using vertex_type = typename Graph::vertex_property_type; - using edge_type = typename Graph::edge_property_type; -public: - static constexpr bool value = - std::is_same<class_type, vertex_type>::value || - std::is_same<class_type, edge_type>::value; -}; - +template<typename T> struct pointer_to_member_traits {}; + +template<typename Return, typename Class> +struct pointer_to_member_traits<Return(Class::*)> { + using member_type = Return; + using class_type = Class; +}; + +template<typename Graph, typename Property, typename Enable = void> +struct is_ue2_vertex_or_edge_property { + static constexpr bool value = false; +}; + +template<typename Graph, typename Property> +struct is_ue2_vertex_or_edge_property< + Graph, Property, typename std::enable_if<is_ue2_graph<Graph>::value && + std::is_member_object_pointer< + Property>::value>::type> { +private: + using class_type = typename pointer_to_member_traits<Property>::class_type; + using vertex_type = typename Graph::vertex_property_type; + using edge_type = typename Graph::edge_property_type; +public: + static constexpr bool value = + std::is_same<class_type, vertex_type>::value || + std::is_same<class_type, edge_type>::value; +}; + using boost::vertex_index; using boost::edge_index; @@ -1298,55 +1298,55 @@ namespace boost { * adaptors (like filtered_graph) to know the type of the property maps */ template<typename Graph, typename Prop> struct property_map<Graph, Prop, - typename std::enable_if<ue2::is_ue2_graph<Graph>::value && - ue2::is_ue2_vertex_or_edge_property< - Graph, Prop>::value>::type> { -private: - using prop_traits = ue2::pointer_to_member_traits<Prop>; - using member_type = typename prop_traits::member_type; - using class_type = typename prop_traits::class_type; -public: - using type = typename Graph::template prop_map<member_type &, class_type>; - using const_type = typename Graph::template prop_map<const member_type &, - class_type>; + typename std::enable_if<ue2::is_ue2_graph<Graph>::value && + ue2::is_ue2_vertex_or_edge_property< + Graph, Prop>::value>::type> { +private: + using prop_traits = ue2::pointer_to_member_traits<Prop>; + using member_type = typename prop_traits::member_type; + using class_type = typename prop_traits::class_type; +public: + using type = typename Graph::template prop_map<member_type &, class_type>; + using const_type = typename Graph::template prop_map<const member_type &, + class_type>; +}; + +template<typename Graph> +struct property_map<Graph, vertex_index_t, + typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { + using v_prop_type = typename Graph::vertex_property_type; + using type = typename Graph::template prop_map<size_t &, v_prop_type>; + using const_type = + typename Graph::template prop_map<const size_t &, v_prop_type>; +}; + +template<typename Graph> +struct property_map<Graph, edge_index_t, + typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { + using e_prop_type = typename Graph::edge_property_type; + using type = typename Graph::template prop_map<size_t &, e_prop_type>; + using const_type = + typename Graph::template prop_map<const size_t &, e_prop_type>; +}; + +template<typename Graph> +struct property_map<Graph, vertex_all_t, + typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { + using v_prop_type = typename Graph::vertex_property_type; + using type = typename Graph::template prop_map_all<v_prop_type &>; + using const_type = + typename Graph::template prop_map_all<const v_prop_type &>; +}; + +template<typename Graph> +struct property_map<Graph, edge_all_t, + typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { + using e_prop_type = typename Graph::edge_property_type; + using type = typename Graph::template prop_map_all<e_prop_type &>; + using const_type = + typename Graph::template prop_map_all<const e_prop_type &>; }; -template<typename Graph> -struct property_map<Graph, vertex_index_t, - typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { - using v_prop_type = typename Graph::vertex_property_type; - using type = typename Graph::template prop_map<size_t &, v_prop_type>; - using const_type = - typename Graph::template prop_map<const size_t &, v_prop_type>; -}; - -template<typename Graph> -struct property_map<Graph, edge_index_t, - typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { - using e_prop_type = typename Graph::edge_property_type; - using type = typename Graph::template prop_map<size_t &, e_prop_type>; - using const_type = - typename Graph::template prop_map<const size_t &, e_prop_type>; -}; - -template<typename Graph> -struct property_map<Graph, vertex_all_t, - typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { - using v_prop_type = typename Graph::vertex_property_type; - using type = typename Graph::template prop_map_all<v_prop_type &>; - using const_type = - typename Graph::template prop_map_all<const v_prop_type &>; -}; - -template<typename Graph> -struct property_map<Graph, edge_all_t, - typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> { - using e_prop_type = typename Graph::edge_property_type; - using type = typename Graph::template prop_map_all<e_prop_type &>; - using const_type = - typename Graph::template prop_map_all<const e_prop_type &>; -}; - } // namespace boost namespace std { diff --git a/contrib/libs/hyperscan/src/util/ue2string.cpp b/contrib/libs/hyperscan/src/util/ue2string.cpp index 0d0590024a..50b2bbcc89 100644 --- a/contrib/libs/hyperscan/src/util/ue2string.cpp +++ b/contrib/libs/hyperscan/src/util/ue2string.cpp @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2019, Intel Corporation + * Copyright (c) 2015-2019, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: diff --git a/contrib/libs/hyperscan/src/util/ue2string.h b/contrib/libs/hyperscan/src/util/ue2string.h index e9d4632a38..0aa846896e 100644 --- a/contrib/libs/hyperscan/src/util/ue2string.h +++ b/contrib/libs/hyperscan/src/util/ue2string.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2019, Intel Corporation + * Copyright (c) 2015-2019, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: diff --git a/contrib/libs/hyperscan/src/util/uniform_ops.h b/contrib/libs/hyperscan/src/util/uniform_ops.h index 074cc40dce..262104aca2 100644 --- a/contrib/libs/hyperscan/src/util/uniform_ops.h +++ b/contrib/libs/hyperscan/src/util/uniform_ops.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2020, Intel Corporation + * Copyright (c) 2015-2020, Intel Corporation * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -101,18 +101,18 @@ #define or_m384(a, b) (or384(a, b)) #define or_m512(a, b) (or512(a, b)) -#if defined(HAVE_AVX512VBMI) -#define expand_m128(a) (expand128(a)) -#define expand_m256(a) (expand256(a)) -#define expand_m384(a) (expand384(a)) -#define expand_m512(a) (a) - -#define shuffle_byte_m128(a, b) (pshufb_m512(b, a)) -#define shuffle_byte_m256(a, b) (vpermb512(a, b)) -#define shuffle_byte_m384(a, b) (vpermb512(a, b)) -#define shuffle_byte_m512(a, b) (vpermb512(a, b)) -#endif - +#if defined(HAVE_AVX512VBMI) +#define expand_m128(a) (expand128(a)) +#define expand_m256(a) (expand256(a)) +#define expand_m384(a) (expand384(a)) +#define expand_m512(a) (a) + +#define shuffle_byte_m128(a, b) (pshufb_m512(b, a)) +#define shuffle_byte_m256(a, b) (vpermb512(a, b)) +#define shuffle_byte_m384(a, b) (vpermb512(a, b)) +#define shuffle_byte_m512(a, b) (vpermb512(a, b)) +#endif + #define and_u8(a, b) ((a) & (b)) #define and_u32(a, b) ((a) & (b)) #define and_u64a(a, b) ((a) & (b)) |