http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/strings/substitute_test.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/strings/substitute_test.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/substitute_test.cc new file mode 100644 index 0000000..144df01 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/substitute_test.cc @@ -0,0 +1,192 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/substitute.h" + +#include <cstdint> + +#include "gtest/gtest.h" +#include "absl/strings/str_cat.h" + +namespace { + +TEST(SubstituteTest, Substitute) { + // Basic. + EXPECT_EQ("Hello, world!", absl::Substitute("$0, $1!", "Hello", "world")); + + // Non-char* types. + EXPECT_EQ("123 0.2 0.1 foo true false x", + absl::Substitute("$0 $1 $2 $3 $4 $5 $6", 123, 0.2, 0.1f, + std::string("foo"), true, false, 'x')); + + // All int types. + EXPECT_EQ( + "-32767 65535 " + "-1234567890 3234567890 " + "-1234567890 3234567890 " + "-1234567890123456789 9234567890123456789", + absl::Substitute( + "$0 $1 $2 $3 $4 $5 $6 $7", + static_cast<short>(-32767), // NOLINT(runtime/int) + static_cast<unsigned short>(65535), // NOLINT(runtime/int) + -1234567890, 3234567890U, -1234567890L, 3234567890UL, + -int64_t{1234567890123456789}, uint64_t{9234567890123456789u})); + + // Hex format + EXPECT_EQ("0 1 f ffff0ffff 0123456789abcdef", + absl::Substitute("$0$1$2$3$4 $5", // + absl::Hex(0), absl::Hex(1, absl::kSpacePad2), + absl::Hex(0xf, absl::kSpacePad2), + absl::Hex(int16_t{-1}, absl::kSpacePad5), + absl::Hex(int16_t{-1}, absl::kZeroPad5), + absl::Hex(0x123456789abcdef, absl::kZeroPad16))); + + // Dec format + EXPECT_EQ("0 115 -1-0001 81985529216486895", + absl::Substitute("$0$1$2$3$4 $5", // + absl::Dec(0), absl::Dec(1, absl::kSpacePad2), + absl::Dec(0xf, absl::kSpacePad2), + absl::Dec(int16_t{-1}, absl::kSpacePad5), + absl::Dec(int16_t{-1}, absl::kZeroPad5), + absl::Dec(0x123456789abcdef, absl::kZeroPad16))); + + // Pointer. + const int* int_p = reinterpret_cast<const int*>(0x12345); + std::string str = absl::Substitute("$0", int_p); + EXPECT_EQ(absl::StrCat("0x", absl::Hex(int_p)), str); + + // Volatile Pointer. + // Like C++ streamed I/O, such pointers implicitly become bool + volatile int vol = 237; + volatile int *volatile volptr = &vol; + str = absl::Substitute("$0", volptr); + EXPECT_EQ("true", str); + + // null is special. StrCat prints 0x0. Substitute prints NULL. + const uint64_t* null_p = nullptr; + str = absl::Substitute("$0", null_p); + EXPECT_EQ("NULL", str); + + // char* is also special. + const char* char_p = "print me"; + str = absl::Substitute("$0", char_p); + EXPECT_EQ("print me", str); + + char char_buf[16]; + strncpy(char_buf, "print me too", sizeof(char_buf)); + str = absl::Substitute("$0", char_buf); + EXPECT_EQ("print me too", str); + + // null char* is "doubly" special. Represented as the empty std::string. + char_p = nullptr; + str = absl::Substitute("$0", char_p); + EXPECT_EQ("", str); + + // Out-of-order. + EXPECT_EQ("b, a, c, b", absl::Substitute("$1, $0, $2, $1", "a", "b", "c")); + + // Literal $ + EXPECT_EQ("$", absl::Substitute("$$")); + + EXPECT_EQ("$1", absl::Substitute("$$1")); + + // Test all overloads. + EXPECT_EQ("a", absl::Substitute("$0", "a")); + EXPECT_EQ("a b", absl::Substitute("$0 $1", "a", "b")); + EXPECT_EQ("a b c", absl::Substitute("$0 $1 $2", "a", "b", "c")); + EXPECT_EQ("a b c d", absl::Substitute("$0 $1 $2 $3", "a", "b", "c", "d")); + EXPECT_EQ("a b c d e", + absl::Substitute("$0 $1 $2 $3 $4", "a", "b", "c", "d", "e")); + EXPECT_EQ("a b c d e f", absl::Substitute("$0 $1 $2 $3 $4 $5", "a", "b", "c", + "d", "e", "f")); + EXPECT_EQ("a b c d e f g", absl::Substitute("$0 $1 $2 $3 $4 $5 $6", "a", "b", + "c", "d", "e", "f", "g")); + EXPECT_EQ("a b c d e f g h", + absl::Substitute("$0 $1 $2 $3 $4 $5 $6 $7", "a", "b", "c", "d", "e", + "f", "g", "h")); + EXPECT_EQ("a b c d e f g h i", + absl::Substitute("$0 $1 $2 $3 $4 $5 $6 $7 $8", "a", "b", "c", "d", + "e", "f", "g", "h", "i")); + EXPECT_EQ("a b c d e f g h i j", + absl::Substitute("$0 $1 $2 $3 $4 $5 $6 $7 $8 $9", "a", "b", "c", + "d", "e", "f", "g", "h", "i", "j")); + EXPECT_EQ("a b c d e f g h i j b0", + absl::Substitute("$0 $1 $2 $3 $4 $5 $6 $7 $8 $9 $10", "a", "b", "c", + "d", "e", "f", "g", "h", "i", "j")); + + const char* null_cstring = nullptr; + EXPECT_EQ("Text: ''", absl::Substitute("Text: '$0'", null_cstring)); +} + +TEST(SubstituteTest, SubstituteAndAppend) { + std::string str = "Hello"; + absl::SubstituteAndAppend(&str, ", $0!", "world"); + EXPECT_EQ("Hello, world!", str); + + // Test all overloads. + str.clear(); + absl::SubstituteAndAppend(&str, "$0", "a"); + EXPECT_EQ("a", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1", "a", "b"); + EXPECT_EQ("a b", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2", "a", "b", "c"); + EXPECT_EQ("a b c", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3", "a", "b", "c", "d"); + EXPECT_EQ("a b c d", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4", "a", "b", "c", "d", "e"); + EXPECT_EQ("a b c d e", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4 $5", "a", "b", "c", "d", "e", + "f"); + EXPECT_EQ("a b c d e f", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4 $5 $6", "a", "b", "c", "d", + "e", "f", "g"); + EXPECT_EQ("a b c d e f g", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4 $5 $6 $7", "a", "b", "c", "d", + "e", "f", "g", "h"); + EXPECT_EQ("a b c d e f g h", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4 $5 $6 $7 $8", "a", "b", "c", + "d", "e", "f", "g", "h", "i"); + EXPECT_EQ("a b c d e f g h i", str); + str.clear(); + absl::SubstituteAndAppend(&str, "$0 $1 $2 $3 $4 $5 $6 $7 $8 $9", "a", "b", + "c", "d", "e", "f", "g", "h", "i", "j"); + EXPECT_EQ("a b c d e f g h i j", str); +} + +#ifdef GTEST_HAS_DEATH_TEST + +TEST(SubstituteDeathTest, SubstituteDeath) { + EXPECT_DEBUG_DEATH( + static_cast<void>(absl::Substitute(absl::string_view("-$2"), "a", "b")), + "Invalid strings::Substitute\\(\\) format std::string: asked for \"\\$2\", " + "but only 2 args were given."); + EXPECT_DEBUG_DEATH( + static_cast<void>(absl::Substitute("-$z-")), + "Invalid strings::Substitute\\(\\) format std::string: \"-\\$z-\""); + EXPECT_DEBUG_DEATH( + static_cast<void>(absl::Substitute("-$")), + "Invalid strings::Substitute\\(\\) format std::string: \"-\\$\""); +} + +#endif // GTEST_HAS_DEATH_TEST + +} // namespace
http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-1.txt ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-1.txt b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-1.txt new file mode 100644 index 0000000..19b9097 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-1.txt @@ -0,0 +1,3 @@ +alpha + +beta gamma http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-2.txt ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-2.txt b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-2.txt new file mode 100644 index 0000000..d6842d8 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/strings/testdata/getline-2.txt @@ -0,0 +1 @@ +one.two.three http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/BUILD.bazel ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/BUILD.bazel b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/BUILD.bazel new file mode 100644 index 0000000..69f9c81 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/BUILD.bazel @@ -0,0 +1,206 @@ +# +# Copyright 2017 The Abseil Authors. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# + +load( + "//absl:copts.bzl", + "ABSL_DEFAULT_COPTS", + "ABSL_TEST_COPTS", +) + +package(default_visibility = ["//visibility:public"]) + +licenses(["notice"]) # Apache 2.0 + +# Internal data structure for efficiently detecting mutex dependency cycles +cc_library( + name = "graphcycles_internal", + srcs = [ + "internal/graphcycles.cc", + ], + hdrs = [ + "internal/graphcycles.h", + ], + copts = ABSL_DEFAULT_COPTS, + visibility = [ + "//absl:__subpackages__", + ], + deps = [ + "//absl/base", + "//absl/base:core_headers", + "//absl/base:malloc_internal", + ], +) + +cc_library( + name = "synchronization", + srcs = [ + "barrier.cc", + "blocking_counter.cc", + "internal/create_thread_identity.cc", + "internal/per_thread_sem.cc", + "internal/waiter.cc", + "notification.cc", + ] + select({ + "//conditions:default": ["mutex.cc"], + }), + hdrs = [ + "barrier.h", + "blocking_counter.h", + "internal/create_thread_identity.h", + "internal/kernel_timeout.h", + "internal/mutex_nonprod.inc", + "internal/per_thread_sem.h", + "internal/waiter.h", + "mutex.h", + "notification.h", + ], + copts = ABSL_DEFAULT_COPTS, + deps = [ + ":graphcycles_internal", + "//absl/base", + "//absl/base:base_internal", + "//absl/base:config", + "//absl/base:core_headers", + "//absl/base:dynamic_annotations", + "//absl/base:malloc_internal", + "//absl/debugging:stacktrace", + "//absl/time", + ], +) + +cc_test( + name = "barrier_test", + size = "small", + srcs = ["barrier_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":synchronization", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "blocking_counter_test", + size = "small", + srcs = ["blocking_counter_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":synchronization", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "graphcycles_test", + size = "medium", + srcs = ["internal/graphcycles_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":graphcycles_internal", + "//absl/base", + "//absl/base:core_headers", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( + name = "thread_pool", + testonly = 1, + hdrs = ["internal/thread_pool.h"], + deps = [ + ":synchronization", + "//absl/base:core_headers", + ], +) + +cc_test( + name = "mutex_test", + size = "large", + srcs = ["mutex_test.cc"], + copts = ABSL_TEST_COPTS, + tags = [ + "no_test_loonix", # Too slow. + ], + deps = [ + ":synchronization", + ":thread_pool", + "//absl/base", + "//absl/base:core_headers", + "//absl/memory", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "notification_test", + size = "small", + srcs = ["notification_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":synchronization", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_library( + name = "per_thread_sem_test_common", + testonly = 1, + srcs = ["internal/per_thread_sem_test.cc"], + copts = ABSL_TEST_COPTS, + deps = [ + ":synchronization", + "//absl/base", + "//absl/strings", + "//absl/time", + "@com_google_googletest//:gtest", + ], + alwayslink = 1, +) + +cc_test( + name = "per_thread_sem_test", + size = "medium", + copts = ABSL_TEST_COPTS, + deps = [ + ":per_thread_sem_test_common", + ":synchronization", + "//absl/base", + "//absl/strings", + "//absl/time", + "@com_google_googletest//:gtest_main", + ], +) + +cc_test( + name = "lifetime_test", + srcs = [ + "lifetime_test.cc", + ], + copts = ABSL_TEST_COPTS, + linkopts = select({ + "//absl:windows": [], + "//conditions:default": ["-pthread"], + }), + deps = [ + ":synchronization", + "//absl/base", + "//absl/base:core_headers", + ], +) http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/CMakeLists.txt ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/CMakeLists.txt b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/CMakeLists.txt new file mode 100644 index 0000000..c8f84fa --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/CMakeLists.txt @@ -0,0 +1,154 @@ +# +# Copyright 2017 The Abseil Authors. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# + +list(APPEND SYNCHRONIZATION_PUBLIC_HEADERS + "barrier.h" + "blocking_counter.h" + "mutex.h" + "notification.h" +) + + +list(APPEND SYNCHRONIZATION_INTERNAL_HEADERS + "internal/create_thread_identity.h" + "internal/graphcycles.h" + "internal/kernel_timeout.h" + "internal/per_thread_sem.h" + "internal/thread_pool.h" + "internal/waiter.h" +) + + + +# syncrhonisation library +list(APPEND SYNCHRONIZATION_SRC + "barrier.cc" + "blocking_counter.cc" + "internal/create_thread_identity.cc" + "internal/per_thread_sem.cc" + "internal/waiter.cc" + "internal/graphcycles.cc" + "notification.cc" + "mutex.cc" +) +set(SYNCHRONIZATION_PUBLIC_LIBRARIES absl::base absl::time) + +absl_library( + TARGET + absl_synchronization + SOURCES + ${SYNCHRONIZATION_SRC} + PUBLIC_LIBRARIES + ${SYNCHRONIZATION_PUBLIC_LIBRARIES} + EXPORT_NAME + synchronization +) + + +# +## TESTS +# + + +# test barrier_test +set(BARRIER_TEST_SRC "barrier_test.cc") +set(BARRIER_TEST_PUBLIC_LIBRARIES absl::synchronization) + +absl_test( + TARGET + barrier_test + SOURCES + ${BARRIER_TEST_SRC} + PUBLIC_LIBRARIES + ${BARRIER_TEST_PUBLIC_LIBRARIES} +) + + +# test blocking_counter_test +set(BLOCKING_COUNTER_TEST_SRC "blocking_counter_test.cc") +set(BLOCKING_COUNTER_TEST_PUBLIC_LIBRARIES absl::synchronization) + +absl_test( + TARGET + blocking_counter_test + SOURCES + ${BLOCKING_COUNTER_TEST_SRC} + PUBLIC_LIBRARIES + ${BLOCKING_COUNTER_TEST_PUBLIC_LIBRARIES} +) + + +# test graphcycles_test +set(GRAPHCYCLES_TEST_SRC "internal/graphcycles_test.cc") +set(GRAPHCYCLES_TEST_PUBLIC_LIBRARIES absl::synchronization) + +absl_test( + TARGET + graphcycles_test + SOURCES + ${GRAPHCYCLES_TEST_SRC} + PUBLIC_LIBRARIES + ${GRAPHCYCLES_TEST_PUBLIC_LIBRARIES} +) + + +# test mutex_test +set(MUTEX_TEST_SRC "mutex_test.cc") +set(MUTEX_TEST_PUBLIC_LIBRARIES absl::synchronization) + +absl_test( + TARGET + mutex_test + SOURCES + ${MUTEX_TEST_SRC} + PUBLIC_LIBRARIES + ${MUTEX_TEST_PUBLIC_LIBRARIES} +) + + +# test notification_test +set(NOTIFICATION_TEST_SRC "notification_test.cc") +set(NOTIFICATION_TEST_PUBLIC_LIBRARIES absl::synchronization) + +absl_test( + TARGET + notification_test + SOURCES + ${NOTIFICATION_TEST_SRC} + PUBLIC_LIBRARIES + ${NOTIFICATION_TEST_PUBLIC_LIBRARIES} +) + + +# test per_thread_sem_test_common +set(PER_THREAD_SEM_TEST_COMMON_SRC "internal/per_thread_sem_test.cc") +set(PER_THREAD_SEM_TEST_COMMON_PUBLIC_LIBRARIES absl::synchronization absl::strings) + +absl_test( + TARGET + per_thread_sem_test_common + SOURCES + ${PER_THREAD_SEM_TEST_COMMON_SRC} + PUBLIC_LIBRARIES + ${PER_THREAD_SEM_TEST_COMMON_PUBLIC_LIBRARIES} +) + + + + + + + http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.cc new file mode 100644 index 0000000..a1b3ad5 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.cc @@ -0,0 +1,50 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/barrier.h" + +#include "absl/base/internal/raw_logging.h" +#include "absl/synchronization/mutex.h" + +namespace absl { + +// Return whether int *arg is zero. +static bool IsZero(void *arg) { + return 0 == *reinterpret_cast<int *>(arg); +} + +bool Barrier::Block() { + MutexLock l(&this->lock_); + + this->num_to_block_--; + if (this->num_to_block_ < 0) { + ABSL_RAW_LOG( + FATAL, + "Block() called too many times. num_to_block_=%d out of total=%d", + this->num_to_block_, this->num_to_exit_); + } + + this->lock_.Await(Condition(IsZero, &this->num_to_block_)); + + // Determine which thread can safely delete this Barrier object + this->num_to_exit_--; + ABSL_RAW_CHECK(this->num_to_exit_ >= 0, "barrier underflow"); + + // If num_to_exit_ == 0 then all other threads in the barrier have + // exited the Wait() and have released the Mutex so this thread is + // free to delete the barrier. + return this->num_to_exit_ == 0; +} + +} // namespace absl http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.h ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.h b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.h new file mode 100644 index 0000000..f834fee --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier.h @@ -0,0 +1,77 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// barrier.h +// ----------------------------------------------------------------------------- + +#ifndef ABSL_SYNCHRONIZATION_BARRIER_H_ +#define ABSL_SYNCHRONIZATION_BARRIER_H_ + +#include "absl/base/thread_annotations.h" +#include "absl/synchronization/mutex.h" + +namespace absl { + +// Barrier +// +// This class creates a barrier which blocks threads until a prespecified +// threshold of threads (`num_threads`) utilizes the barrier. A thread utilizes +// the `Barrier` by calling `Block()` on the barrier, which will block that +// thread; no call to `Block()` will return until `num_threads` threads have +// called it. +// +// Exactly one call to `Block()` will return `true`, which is then responsible +// for destroying the barrier; because stack allocation will cause the barrier +// to be deleted when it is out of scope, barriers should not be stack +// allocated. +// +// Example: +// +// // Main thread creates a `Barrier`: +// barrier = new Barrier(num_threads); +// +// // Each participating thread could then call: +// if (barrier->Block()) delete barrier; // Exactly one call to `Block()` +// // returns `true`; that call +// // deletes the barrier. +class Barrier { + public: + // `num_threads` is the number of threads that will participate in the barrier + explicit Barrier(int num_threads) + : num_to_block_(num_threads), num_to_exit_(num_threads) {} + + Barrier(const Barrier&) = delete; + Barrier& operator=(const Barrier&) = delete; + + // Barrier::Block() + // + // Blocks the current thread, and returns only when the `num_threads` + // threshold of threads utilizing this barrier has been reached. `Block()` + // returns `true` for precisely one caller, which may then destroy the + // barrier. + // + // Memory ordering: For any threads X and Y, any action taken by X + // before X calls `Block()` will be visible to Y after Y returns from + // `Block()`. + bool Block(); + + private: + Mutex lock_; + int num_to_block_ GUARDED_BY(lock_); + int num_to_exit_ GUARDED_BY(lock_); +}; + +} // namespace absl +#endif // ABSL_SYNCHRONIZATION_BARRIER_H_ http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier_test.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier_test.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier_test.cc new file mode 100644 index 0000000..d6cabab --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/barrier_test.cc @@ -0,0 +1,75 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/barrier.h" + +#include <thread> // NOLINT(build/c++11) +#include <vector> + +#include "gtest/gtest.h" +#include "absl/synchronization/mutex.h" +#include "absl/time/clock.h" + + +TEST(Barrier, SanityTest) { + constexpr int kNumThreads = 10; + absl::Barrier* barrier = new absl::Barrier(kNumThreads); + + absl::Mutex mutex; + int counter = 0; // Guarded by mutex. + + auto thread_func = [&] { + if (barrier->Block()) { + // This thread is the last thread to reach the barrier so it is + // responsible for deleting it. + delete barrier; + } + + // Increment the counter. + absl::MutexLock lock(&mutex); + ++counter; + }; + + // Start (kNumThreads - 1) threads running thread_func. + std::vector<std::thread> threads; + for (int i = 0; i < kNumThreads - 1; ++i) { + threads.push_back(std::thread(thread_func)); + } + + // Give (kNumThreads - 1) threads a chance to reach the barrier. + // This test assumes at least one thread will have run after the + // sleep has elapsed. Sleeping in a test is usually bad form, but we + // need to make sure that we are testing the barrier instead of some + // other synchronization method. + absl::SleepFor(absl::Seconds(1)); + + // The counter should still be zero since no thread should have + // been able to pass the barrier yet. + { + absl::MutexLock lock(&mutex); + EXPECT_EQ(counter, 0); + } + + // Start 1 more thread. This should make all threads pass the barrier. + threads.push_back(std::thread(thread_func)); + + // All threads should now be able to proceed and finish. + for (auto& thread : threads) { + thread.join(); + } + + // All threads should now have incremented the counter. + absl::MutexLock lock(&mutex); + EXPECT_EQ(counter, kNumThreads); +} http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.cc new file mode 100644 index 0000000..7e68e96 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.cc @@ -0,0 +1,55 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/blocking_counter.h" + +#include "absl/base/internal/raw_logging.h" + +namespace absl { + +// Return whether int *arg is zero. +static bool IsZero(void *arg) { + return 0 == *reinterpret_cast<int *>(arg); +} + +bool BlockingCounter::DecrementCount() { + MutexLock l(&lock_); + count_--; + if (count_ < 0) { + ABSL_RAW_LOG( + FATAL, + "BlockingCounter::DecrementCount() called too many times. count=%d", + count_); + } + return count_ == 0; +} + +void BlockingCounter::Wait() { + MutexLock l(&this->lock_); + ABSL_RAW_CHECK(count_ >= 0, "BlockingCounter underflow"); + + // only one thread may call Wait(). To support more than one thread, + // implement a counter num_to_exit, like in the Barrier class. + ABSL_RAW_CHECK(num_waiting_ == 0, "multiple threads called Wait()"); + num_waiting_++; + + this->lock_.Await(Condition(IsZero, &this->count_)); + + // At this point, We know that all threads executing DecrementCount have + // released the lock, and so will not touch this object again. + // Therefore, the thread calling this method is free to delete the object + // after we return from this method. +} + +} // namespace absl http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.h ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.h b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.h new file mode 100644 index 0000000..557ed02 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter.h @@ -0,0 +1,97 @@ +// +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// blocking_counter.h +// ----------------------------------------------------------------------------- + +#ifndef ABSL_SYNCHRONIZATION_BLOCKING_COUNTER_H_ +#define ABSL_SYNCHRONIZATION_BLOCKING_COUNTER_H_ + +#include "absl/base/thread_annotations.h" +#include "absl/synchronization/mutex.h" + +namespace absl { + +// BlockingCounter +// +// This class allows a thread to block for a pre-specified number of actions. +// `BlockingCounter` maintains a single non-negative abstract integer "count" +// with an initial value `initial_count`. A thread can then call `Wait()` on +// this blocking counter to block until the specified number of events occur; +// worker threads then call 'DecrementCount()` on the counter upon completion of +// their work. Once the counter's internal "count" reaches zero, the blocked +// thread unblocks. +// +// A `BlockingCounter` requires the following: +// - its `initial_count` is non-negative. +// - the number of calls to `DecrementCount()` on it is at most +// `initial_count`. +// - `Wait()` is called at most once on it. +// +// Given the above requirements, a `BlockingCounter` provides the following +// guarantees: +// - Once its internal "count" reaches zero, no legal action on the object +// can further change the value of "count". +// - When `Wait()` returns, it is legal to destroy the `BlockingCounter`. +// - When `Wait()` returns, the number of calls to `DecrementCount()` on +// this blocking counter exactly equals `initial_count`. +// +// Example: +// BlockingCounter bcount(N); // there are N items of work +// ... Allow worker threads to start. +// ... On completing each work item, workers do: +// ... bcount.DecrementCount(); // an item of work has been completed +// +// bcount.Wait(); // wait for all work to be complete +// +class BlockingCounter { + public: + explicit BlockingCounter(int initial_count) + : count_(initial_count), num_waiting_(0) {} + + BlockingCounter(const BlockingCounter&) = delete; + BlockingCounter& operator=(const BlockingCounter&) = delete; + + // BlockingCounter::DecrementCount() + // + // Decrements the counter's "count" by one, and return "count == 0". This + // function requires that "count != 0" when it is called. + // + // Memory ordering: For any threads X and Y, any action taken by X + // before it calls `DecrementCount()` is visible to thread Y after + // Y's call to `DecrementCount()`, provided Y's call returns `true`. + bool DecrementCount(); + + // BlockingCounter::Wait() + // + // Blocks until the counter reaches zero. This function may be called at most + // once. On return, `DecrementCount()` will have been called "initial_count" + // times and the blocking counter may be destroyed. + // + // Memory ordering: For any threads X and Y, any action taken by X + // before X calls `DecrementCount()` is visible to Y after Y returns + // from `Wait()`. + void Wait(); + + private: + Mutex lock_; + int count_ GUARDED_BY(lock_); + int num_waiting_ GUARDED_BY(lock_); +}; + +} // namespace absl + +#endif // ABSL_SYNCHRONIZATION_BLOCKING_COUNTER_H_ http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter_test.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter_test.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter_test.cc new file mode 100644 index 0000000..e8223f8 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/blocking_counter_test.cc @@ -0,0 +1,66 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/blocking_counter.h" + +#include <thread> // NOLINT(build/c++11) +#include <vector> + +#include "gtest/gtest.h" +#include "absl/time/clock.h" +#include "absl/time/time.h" + +namespace absl { +namespace { + +void PauseAndDecreaseCounter(BlockingCounter* counter, int* done) { + absl::SleepFor(absl::Seconds(1)); + *done = 1; + counter->DecrementCount(); +} + +TEST(BlockingCounterTest, BasicFunctionality) { + // This test verifies that BlockingCounter functions correctly. Starts a + // number of threads that just sleep for a second and decrement a counter. + + // Initialize the counter. + const int num_workers = 10; + BlockingCounter counter(num_workers); + + std::vector<std::thread> workers; + std::vector<int> done(num_workers, 0); + + // Start a number of parallel tasks that will just wait for a seconds and + // then decrement the count. + workers.reserve(num_workers); + for (int k = 0; k < num_workers; k++) { + workers.emplace_back( + [&counter, &done, k] { PauseAndDecreaseCounter(&counter, &done[k]); }); + } + + // Wait for the threads to have all finished. + counter.Wait(); + + // Check that all the workers have completed. + for (int k = 0; k < num_workers; k++) { + EXPECT_EQ(1, done[k]); + } + + for (std::thread& w : workers) { + w.join(); + } +} + +} // namespace +} // namespace absl http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.cc new file mode 100644 index 0000000..e7a65cd --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.cc @@ -0,0 +1,112 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <stdint.h> +#include <new> + +// This file is a no-op if the required LowLevelAlloc support is missing. +#include "absl/base/internal/low_level_alloc.h" +#ifndef ABSL_LOW_LEVEL_ALLOC_MISSING + +#include <string.h> + +#include "absl/base/attributes.h" +#include "absl/base/internal/spinlock.h" +#include "absl/base/internal/thread_identity.h" +#include "absl/synchronization/internal/per_thread_sem.h" + +namespace absl { +namespace synchronization_internal { + +// ThreadIdentity storage is persistent, we maintain a free-list of previously +// released ThreadIdentity objects. +static base_internal::SpinLock freelist_lock(base_internal::kLinkerInitialized); +static base_internal::ThreadIdentity* thread_identity_freelist; + +// A per-thread destructor for reclaiming associated ThreadIdentity objects. +// Since we must preserve their storage we cache them for re-use. +static void ReclaimThreadIdentity(void* v) { + base_internal::ThreadIdentity* identity = + static_cast<base_internal::ThreadIdentity*>(v); + + // all_locks might have been allocated by the Mutex implementation. + // We free it here when we are notified that our thread is dying. + if (identity->per_thread_synch.all_locks != nullptr) { + base_internal::LowLevelAlloc::Free(identity->per_thread_synch.all_locks); + } + + // We must explicitly clear the current thread's identity: + // (a) Subsequent (unrelated) per-thread destructors may require an identity. + // We must guarantee a new identity is used in this case (this instructor + // will be reinvoked up to PTHREAD_DESTRUCTOR_ITERATIONS in this case). + // (b) ThreadIdentity implementations may depend on memory that is not + // reinitialized before reuse. We must allow explicit clearing of the + // association state in this case. + base_internal::ClearCurrentThreadIdentity(); + { + base_internal::SpinLockHolder l(&freelist_lock); + identity->next = thread_identity_freelist; + thread_identity_freelist = identity; + } +} + +// Return value rounded up to next multiple of align. +// Align must be a power of two. +static intptr_t RoundUp(intptr_t addr, intptr_t align) { + return (addr + align - 1) & ~(align - 1); +} + +static base_internal::ThreadIdentity* NewThreadIdentity() { + base_internal::ThreadIdentity* identity = nullptr; + + { + // Re-use a previously released object if possible. + base_internal::SpinLockHolder l(&freelist_lock); + if (thread_identity_freelist) { + identity = thread_identity_freelist; // Take list-head. + thread_identity_freelist = thread_identity_freelist->next; + } + } + + if (identity == nullptr) { + // Allocate enough space to align ThreadIdentity to a multiple of + // PerThreadSynch::kAlignment. This space is never released (it is + // added to a freelist by ReclaimThreadIdentity instead). + void* allocation = base_internal::LowLevelAlloc::Alloc( + sizeof(*identity) + base_internal::PerThreadSynch::kAlignment - 1); + // Round up the address to the required alignment. + identity = reinterpret_cast<base_internal::ThreadIdentity*>( + RoundUp(reinterpret_cast<intptr_t>(allocation), + base_internal::PerThreadSynch::kAlignment)); + } + memset(identity, 0, sizeof(*identity)); + + return identity; +} + +// Allocates and attaches ThreadIdentity object for the calling thread. Returns +// the new identity. +// REQUIRES: CurrentThreadIdentity(false) == nullptr +base_internal::ThreadIdentity* CreateThreadIdentity() { + base_internal::ThreadIdentity* identity = NewThreadIdentity(); + PerThreadSem::Init(identity); + // Associate the value with the current thread, and attach our destructor. + base_internal::SetCurrentThreadIdentity(identity, ReclaimThreadIdentity); + return identity; +} + +} // namespace synchronization_internal +} // namespace absl + +#endif // ABSL_LOW_LEVEL_ALLOC_MISSING http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.h ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.h b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.h new file mode 100644 index 0000000..1bb87de --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/create_thread_identity.h @@ -0,0 +1,53 @@ +/* + * Copyright 2017 The Abseil Authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// Interface for getting the current ThreadIdentity, creating one if necessary. +// See thread_identity.h. +// +// This file is separate from thread_identity.h because creating a new +// ThreadIdentity requires slightly higher level libraries (per_thread_sem +// and low_level_alloc) than accessing an existing one. This separation allows +// us to have a smaller //absl/base:base. + +#ifndef ABSL_SYNCHRONIZATION_INTERNAL_CREATE_THREAD_IDENTITY_H_ +#define ABSL_SYNCHRONIZATION_INTERNAL_CREATE_THREAD_IDENTITY_H_ + +#include "absl/base/internal/thread_identity.h" +#include "absl/base/port.h" + +namespace absl { +namespace synchronization_internal { + +// Allocates and attaches a ThreadIdentity object for the calling thread. +// For private use only. +base_internal::ThreadIdentity* CreateThreadIdentity(); + +// Returns the ThreadIdentity object representing the calling thread; guaranteed +// to be unique for its lifetime. The returned object will remain valid for the +// program's lifetime; although it may be re-assigned to a subsequent thread. +// If one does not exist for the calling thread, allocate it now. +inline base_internal::ThreadIdentity* GetOrCreateCurrentThreadIdentity() { + base_internal::ThreadIdentity* identity = + base_internal::CurrentThreadIdentityIfPresent(); + if (ABSL_PREDICT_FALSE(identity == nullptr)) { + return CreateThreadIdentity(); + } + return identity; +} + +} // namespace synchronization_internal +} // namespace absl +#endif // ABSL_SYNCHRONIZATION_INTERNAL_CREATE_THREAD_IDENTITY_H_ http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.cc new file mode 100644 index 0000000..28ad172 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.cc @@ -0,0 +1,709 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// GraphCycles provides incremental cycle detection on a dynamic +// graph using the following algorithm: +// +// A dynamic topological sort algorithm for directed acyclic graphs +// David J. Pearce, Paul H. J. Kelly +// Journal of Experimental Algorithmics (JEA) JEA Homepage archive +// Volume 11, 2006, Article No. 1.7 +// +// Brief summary of the algorithm: +// +// (1) Maintain a rank for each node that is consistent +// with the topological sort of the graph. I.e., path from x to y +// implies rank[x] < rank[y]. +// (2) When a new edge (x->y) is inserted, do nothing if rank[x] < rank[y]. +// (3) Otherwise: adjust ranks in the neighborhood of x and y. + +#include "absl/base/attributes.h" +// This file is a no-op if the required LowLevelAlloc support is missing. +#include "absl/base/internal/low_level_alloc.h" +#ifndef ABSL_LOW_LEVEL_ALLOC_MISSING + +#include "absl/synchronization/internal/graphcycles.h" + +#include <algorithm> +#include <array> +#include "absl/base/internal/raw_logging.h" +#include "absl/base/internal/spinlock.h" + +// Do not use STL. This module does not use standard memory allocation. + +namespace absl { +namespace synchronization_internal { + +namespace { + +// Avoid LowLevelAlloc's default arena since it calls malloc hooks in +// which people are doing things like acquiring Mutexes. +static absl::base_internal::SpinLock arena_mu( + absl::base_internal::kLinkerInitialized); +static base_internal::LowLevelAlloc::Arena* arena; + +static void InitArenaIfNecessary() { + arena_mu.Lock(); + if (arena == nullptr) { + arena = base_internal::LowLevelAlloc::NewArena(0); + } + arena_mu.Unlock(); +} + +// Number of inlined elements in Vec. Hash table implementation +// relies on this being a power of two. +static const uint32_t kInline = 8; + +// A simple LowLevelAlloc based resizable vector with inlined storage +// for a few elements. T must be a plain type since constructor +// and destructor are not run on elements of type T managed by Vec. +template <typename T> +class Vec { + public: + Vec() { Init(); } + ~Vec() { Discard(); } + + void clear() { + Discard(); + Init(); + } + + bool empty() const { return size_ == 0; } + uint32_t size() const { return size_; } + T* begin() { return ptr_; } + T* end() { return ptr_ + size_; } + const T& operator[](uint32_t i) const { return ptr_[i]; } + T& operator[](uint32_t i) { return ptr_[i]; } + const T& back() const { return ptr_[size_-1]; } + void pop_back() { size_--; } + + void push_back(const T& v) { + if (size_ == capacity_) Grow(size_ + 1); + ptr_[size_] = v; + size_++; + } + + void resize(uint32_t n) { + if (n > capacity_) Grow(n); + size_ = n; + } + + void fill(const T& val) { + for (uint32_t i = 0; i < size(); i++) { + ptr_[i] = val; + } + } + + // Guarantees src is empty at end. + // Provided for the hash table resizing code below. + void MoveFrom(Vec<T>* src) { + if (src->ptr_ == src->space_) { + // Need to actually copy + resize(src->size_); + std::copy(src->ptr_, src->ptr_ + src->size_, ptr_); + src->size_ = 0; + } else { + Discard(); + ptr_ = src->ptr_; + size_ = src->size_; + capacity_ = src->capacity_; + src->Init(); + } + } + + private: + T* ptr_; + T space_[kInline]; + uint32_t size_; + uint32_t capacity_; + + void Init() { + ptr_ = space_; + size_ = 0; + capacity_ = kInline; + } + + void Discard() { + if (ptr_ != space_) base_internal::LowLevelAlloc::Free(ptr_); + } + + void Grow(uint32_t n) { + while (capacity_ < n) { + capacity_ *= 2; + } + size_t request = static_cast<size_t>(capacity_) * sizeof(T); + T* copy = static_cast<T*>( + base_internal::LowLevelAlloc::AllocWithArena(request, arena)); + std::copy(ptr_, ptr_ + size_, copy); + Discard(); + ptr_ = copy; + } + + Vec(const Vec&) = delete; + Vec& operator=(const Vec&) = delete; +}; + +// A hash set of non-negative int32_t that uses Vec for its underlying storage. +class NodeSet { + public: + NodeSet() { Init(); } + + void clear() { Init(); } + bool contains(int32_t v) const { return table_[FindIndex(v)] == v; } + + bool insert(int32_t v) { + uint32_t i = FindIndex(v); + if (table_[i] == v) { + return false; + } + if (table_[i] == kEmpty) { + // Only inserting over an empty cell increases the number of occupied + // slots. + occupied_++; + } + table_[i] = v; + // Double when 75% full. + if (occupied_ >= table_.size() - table_.size()/4) Grow(); + return true; + } + + void erase(uint32_t v) { + uint32_t i = FindIndex(v); + if (static_cast<uint32_t>(table_[i]) == v) { + table_[i] = kDel; + } + } + + // Iteration: is done via HASH_FOR_EACH + // Example: + // HASH_FOR_EACH(elem, node->out) { ... } +#define HASH_FOR_EACH(elem, eset) \ + for (int32_t elem, _cursor = 0; (eset).Next(&_cursor, &elem); ) + bool Next(int32_t* cursor, int32_t* elem) { + while (static_cast<uint32_t>(*cursor) < table_.size()) { + int32_t v = table_[*cursor]; + (*cursor)++; + if (v >= 0) { + *elem = v; + return true; + } + } + return false; + } + + private: + static const int32_t kEmpty; + static const int32_t kDel; + Vec<int32_t> table_; + uint32_t occupied_; // Count of non-empty slots (includes deleted slots) + + static uint32_t Hash(uint32_t a) { return a * 41; } + + // Return index for storing v. May return an empty index or deleted index + int FindIndex(int32_t v) const { + // Search starting at hash index. + const uint32_t mask = table_.size() - 1; + uint32_t i = Hash(v) & mask; + int deleted_index = -1; // If >= 0, index of first deleted element we see + while (true) { + int32_t e = table_[i]; + if (v == e) { + return i; + } else if (e == kEmpty) { + // Return any previously encountered deleted slot. + return (deleted_index >= 0) ? deleted_index : i; + } else if (e == kDel && deleted_index < 0) { + // Keep searching since v might be present later. + deleted_index = i; + } + i = (i + 1) & mask; // Linear probing; quadratic is slightly slower. + } + } + + void Init() { + table_.clear(); + table_.resize(kInline); + table_.fill(kEmpty); + occupied_ = 0; + } + + void Grow() { + Vec<int32_t> copy; + copy.MoveFrom(&table_); + occupied_ = 0; + table_.resize(copy.size() * 2); + table_.fill(kEmpty); + + for (const auto& e : copy) { + if (e >= 0) insert(e); + } + } + + NodeSet(const NodeSet&) = delete; + NodeSet& operator=(const NodeSet&) = delete; +}; + +const int32_t NodeSet::kEmpty = -1; +const int32_t NodeSet::kDel = -2; + +// We encode a node index and a node version in GraphId. The version +// number is incremented when the GraphId is freed which automatically +// invalidates all copies of the GraphId. + +inline GraphId MakeId(int32_t index, uint32_t version) { + GraphId g; + g.handle = + (static_cast<uint64_t>(version) << 32) | static_cast<uint32_t>(index); + return g; +} + +inline int32_t NodeIndex(GraphId id) { + return static_cast<uint32_t>(id.handle & 0xfffffffful); +} + +inline uint32_t NodeVersion(GraphId id) { + return static_cast<uint32_t>(id.handle >> 32); +} + +// We need to hide Mutexes (or other deadlock detection's pointers) +// from the leak detector. Xor with an arbitrary number with high bits set. +static const uintptr_t kHideMask = static_cast<uintptr_t>(0xF03A5F7BF03A5F7Bll); + +static inline uintptr_t MaskPtr(void *ptr) { + return reinterpret_cast<uintptr_t>(ptr) ^ kHideMask; +} + +static inline void* UnmaskPtr(uintptr_t word) { + return reinterpret_cast<void*>(word ^ kHideMask); +} + +struct Node { + int32_t rank; // rank number assigned by Pearce-Kelly algorithm + uint32_t version; // Current version number + int32_t next_hash; // Next entry in hash table + bool visited; // Temporary marker used by depth-first-search + uintptr_t masked_ptr; // User-supplied pointer + NodeSet in; // List of immediate predecessor nodes in graph + NodeSet out; // List of immediate successor nodes in graph + int priority; // Priority of recorded stack trace. + int nstack; // Depth of recorded stack trace. + void* stack[40]; // stack[0,nstack-1] holds stack trace for node. +}; + +// Hash table for pointer to node index lookups. +class PointerMap { + public: + explicit PointerMap(const Vec<Node*>* nodes) : nodes_(nodes) { + table_.fill(-1); + } + + int32_t Find(void* ptr) { + auto masked = MaskPtr(ptr); + for (int32_t i = table_[Hash(ptr)]; i != -1;) { + Node* n = (*nodes_)[i]; + if (n->masked_ptr == masked) return i; + i = n->next_hash; + } + return -1; + } + + void Add(void* ptr, int32_t i) { + int32_t* head = &table_[Hash(ptr)]; + (*nodes_)[i]->next_hash = *head; + *head = i; + } + + int32_t Remove(void* ptr) { + // Advance through linked list while keeping track of the + // predecessor slot that points to the current entry. + auto masked = MaskPtr(ptr); + for (int32_t* slot = &table_[Hash(ptr)]; *slot != -1; ) { + int32_t index = *slot; + Node* n = (*nodes_)[index]; + if (n->masked_ptr == masked) { + *slot = n->next_hash; // Remove n from linked list + n->next_hash = -1; + return index; + } + slot = &n->next_hash; + } + return -1; + } + + private: + // Number of buckets in hash table for pointer lookups. + static constexpr uint32_t kHashTableSize = 8171; // should be prime + + const Vec<Node*>* nodes_; + std::array<int32_t, kHashTableSize> table_; + + static uint32_t Hash(void* ptr) { + return reinterpret_cast<uintptr_t>(ptr) % kHashTableSize; + } +}; + +} // namespace + +struct GraphCycles::Rep { + Vec<Node*> nodes_; + Vec<int32_t> free_nodes_; // Indices for unused entries in nodes_ + PointerMap ptrmap_; + + // Temporary state. + Vec<int32_t> deltaf_; // Results of forward DFS + Vec<int32_t> deltab_; // Results of backward DFS + Vec<int32_t> list_; // All nodes to reprocess + Vec<int32_t> merged_; // Rank values to assign to list_ entries + Vec<int32_t> stack_; // Emulates recursion stack for depth-first searches + + Rep() : ptrmap_(&nodes_) {} +}; + +static Node* FindNode(GraphCycles::Rep* rep, GraphId id) { + Node* n = rep->nodes_[NodeIndex(id)]; + return (n->version == NodeVersion(id)) ? n : nullptr; +} + +GraphCycles::GraphCycles() { + InitArenaIfNecessary(); + rep_ = new (base_internal::LowLevelAlloc::AllocWithArena(sizeof(Rep), arena)) + Rep; +} + +GraphCycles::~GraphCycles() { + for (auto* node : rep_->nodes_) { + node->Node::~Node(); + base_internal::LowLevelAlloc::Free(node); + } + rep_->Rep::~Rep(); + base_internal::LowLevelAlloc::Free(rep_); +} + +bool GraphCycles::CheckInvariants() const { + Rep* r = rep_; + NodeSet ranks; // Set of ranks seen so far. + for (uint32_t x = 0; x < r->nodes_.size(); x++) { + Node* nx = r->nodes_[x]; + void* ptr = UnmaskPtr(nx->masked_ptr); + if (ptr != nullptr && static_cast<uint32_t>(r->ptrmap_.Find(ptr)) != x) { + ABSL_RAW_LOG(FATAL, "Did not find live node in hash table %u %p", x, ptr); + } + if (nx->visited) { + ABSL_RAW_LOG(FATAL, "Did not clear visited marker on node %u", x); + } + if (!ranks.insert(nx->rank)) { + ABSL_RAW_LOG(FATAL, "Duplicate occurrence of rank %d", nx->rank); + } + HASH_FOR_EACH(y, nx->out) { + Node* ny = r->nodes_[y]; + if (nx->rank >= ny->rank) { + ABSL_RAW_LOG(FATAL, "Edge %u->%d has bad rank assignment %d->%d", x, y, + nx->rank, ny->rank); + } + } + } + return true; +} + +GraphId GraphCycles::GetId(void* ptr) { + int32_t i = rep_->ptrmap_.Find(ptr); + if (i != -1) { + return MakeId(i, rep_->nodes_[i]->version); + } else if (rep_->free_nodes_.empty()) { + Node* n = + new (base_internal::LowLevelAlloc::AllocWithArena(sizeof(Node), arena)) + Node; + n->version = 1; // Avoid 0 since it is used by InvalidGraphId() + n->visited = false; + n->rank = rep_->nodes_.size(); + n->masked_ptr = MaskPtr(ptr); + n->nstack = 0; + n->priority = 0; + rep_->nodes_.push_back(n); + rep_->ptrmap_.Add(ptr, n->rank); + return MakeId(n->rank, n->version); + } else { + // Preserve preceding rank since the set of ranks in use must be + // a permutation of [0,rep_->nodes_.size()-1]. + int32_t r = rep_->free_nodes_.back(); + rep_->free_nodes_.pop_back(); + Node* n = rep_->nodes_[r]; + n->masked_ptr = MaskPtr(ptr); + n->nstack = 0; + n->priority = 0; + rep_->ptrmap_.Add(ptr, r); + return MakeId(r, n->version); + } +} + +void GraphCycles::RemoveNode(void* ptr) { + int32_t i = rep_->ptrmap_.Remove(ptr); + if (i == -1) { + return; + } + Node* x = rep_->nodes_[i]; + HASH_FOR_EACH(y, x->out) { + rep_->nodes_[y]->in.erase(i); + } + HASH_FOR_EACH(y, x->in) { + rep_->nodes_[y]->out.erase(i); + } + x->in.clear(); + x->out.clear(); + x->masked_ptr = MaskPtr(nullptr); + if (x->version == std::numeric_limits<uint32_t>::max()) { + // Cannot use x any more + } else { + x->version++; // Invalidates all copies of node. + rep_->free_nodes_.push_back(i); + } +} + +void* GraphCycles::Ptr(GraphId id) { + Node* n = FindNode(rep_, id); + return n == nullptr ? nullptr : UnmaskPtr(n->masked_ptr); +} + +bool GraphCycles::HasNode(GraphId node) { + return FindNode(rep_, node) != nullptr; +} + +bool GraphCycles::HasEdge(GraphId x, GraphId y) const { + Node* xn = FindNode(rep_, x); + return xn && FindNode(rep_, y) && xn->out.contains(NodeIndex(y)); +} + +void GraphCycles::RemoveEdge(GraphId x, GraphId y) { + Node* xn = FindNode(rep_, x); + Node* yn = FindNode(rep_, y); + if (xn && yn) { + xn->out.erase(NodeIndex(y)); + yn->in.erase(NodeIndex(x)); + // No need to update the rank assignment since a previous valid + // rank assignment remains valid after an edge deletion. + } +} + +static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound); +static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound); +static void Reorder(GraphCycles::Rep* r); +static void Sort(const Vec<Node*>&, Vec<int32_t>* delta); +static void MoveToList( + GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst); + +bool GraphCycles::InsertEdge(GraphId idx, GraphId idy) { + Rep* r = rep_; + const int32_t x = NodeIndex(idx); + const int32_t y = NodeIndex(idy); + Node* nx = FindNode(r, idx); + Node* ny = FindNode(r, idy); + if (nx == nullptr || ny == nullptr) return true; // Expired ids + + if (nx == ny) return false; // Self edge + if (!nx->out.insert(y)) { + // Edge already exists. + return true; + } + + ny->in.insert(x); + + if (nx->rank <= ny->rank) { + // New edge is consistent with existing rank assignment. + return true; + } + + // Current rank assignments are incompatible with the new edge. Recompute. + // We only need to consider nodes that fall in the range [ny->rank,nx->rank]. + if (!ForwardDFS(r, y, nx->rank)) { + // Found a cycle. Undo the insertion and tell caller. + nx->out.erase(y); + ny->in.erase(x); + // Since we do not call Reorder() on this path, clear any visited + // markers left by ForwardDFS. + for (const auto& d : r->deltaf_) { + r->nodes_[d]->visited = false; + } + return false; + } + BackwardDFS(r, x, ny->rank); + Reorder(r); + return true; +} + +static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound) { + // Avoid recursion since stack space might be limited. + // We instead keep a stack of nodes to visit. + r->deltaf_.clear(); + r->stack_.clear(); + r->stack_.push_back(n); + while (!r->stack_.empty()) { + n = r->stack_.back(); + r->stack_.pop_back(); + Node* nn = r->nodes_[n]; + if (nn->visited) continue; + + nn->visited = true; + r->deltaf_.push_back(n); + + HASH_FOR_EACH(w, nn->out) { + Node* nw = r->nodes_[w]; + if (nw->rank == upper_bound) { + return false; // Cycle + } + if (!nw->visited && nw->rank < upper_bound) { + r->stack_.push_back(w); + } + } + } + return true; +} + +static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound) { + r->deltab_.clear(); + r->stack_.clear(); + r->stack_.push_back(n); + while (!r->stack_.empty()) { + n = r->stack_.back(); + r->stack_.pop_back(); + Node* nn = r->nodes_[n]; + if (nn->visited) continue; + + nn->visited = true; + r->deltab_.push_back(n); + + HASH_FOR_EACH(w, nn->in) { + Node* nw = r->nodes_[w]; + if (!nw->visited && lower_bound < nw->rank) { + r->stack_.push_back(w); + } + } + } +} + +static void Reorder(GraphCycles::Rep* r) { + Sort(r->nodes_, &r->deltab_); + Sort(r->nodes_, &r->deltaf_); + + // Adds contents of delta lists to list_ (backwards deltas first). + r->list_.clear(); + MoveToList(r, &r->deltab_, &r->list_); + MoveToList(r, &r->deltaf_, &r->list_); + + // Produce sorted list of all ranks that will be reassigned. + r->merged_.resize(r->deltab_.size() + r->deltaf_.size()); + std::merge(r->deltab_.begin(), r->deltab_.end(), + r->deltaf_.begin(), r->deltaf_.end(), + r->merged_.begin()); + + // Assign the ranks in order to the collected list. + for (uint32_t i = 0; i < r->list_.size(); i++) { + r->nodes_[r->list_[i]]->rank = r->merged_[i]; + } +} + +static void Sort(const Vec<Node*>& nodes, Vec<int32_t>* delta) { + struct ByRank { + const Vec<Node*>* nodes; + bool operator()(int32_t a, int32_t b) const { + return (*nodes)[a]->rank < (*nodes)[b]->rank; + } + }; + ByRank cmp; + cmp.nodes = &nodes; + std::sort(delta->begin(), delta->end(), cmp); +} + +static void MoveToList( + GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst) { + for (auto& v : *src) { + int32_t w = v; + v = r->nodes_[w]->rank; // Replace v entry with its rank + r->nodes_[w]->visited = false; // Prepare for future DFS calls + dst->push_back(w); + } +} + +int GraphCycles::FindPath(GraphId idx, GraphId idy, int max_path_len, + GraphId path[]) const { + Rep* r = rep_; + if (FindNode(r, idx) == nullptr || FindNode(r, idy) == nullptr) return 0; + const int32_t x = NodeIndex(idx); + const int32_t y = NodeIndex(idy); + + // Forward depth first search starting at x until we hit y. + // As we descend into a node, we push it onto the path. + // As we leave a node, we remove it from the path. + int path_len = 0; + + NodeSet seen; + r->stack_.clear(); + r->stack_.push_back(x); + while (!r->stack_.empty()) { + int32_t n = r->stack_.back(); + r->stack_.pop_back(); + if (n < 0) { + // Marker to indicate that we are leaving a node + path_len--; + continue; + } + + if (path_len < max_path_len) { + path[path_len] = MakeId(n, rep_->nodes_[n]->version); + } + path_len++; + r->stack_.push_back(-1); // Will remove tentative path entry + + if (n == y) { + return path_len; + } + + HASH_FOR_EACH(w, r->nodes_[n]->out) { + if (seen.insert(w)) { + r->stack_.push_back(w); + } + } + } + + return 0; +} + +bool GraphCycles::IsReachable(GraphId x, GraphId y) const { + return FindPath(x, y, 0, nullptr) > 0; +} + +void GraphCycles::UpdateStackTrace(GraphId id, int priority, + int (*get_stack_trace)(void** stack, int)) { + Node* n = FindNode(rep_, id); + if (n == nullptr || n->priority >= priority) { + return; + } + n->nstack = (*get_stack_trace)(n->stack, ABSL_ARRAYSIZE(n->stack)); + n->priority = priority; +} + +int GraphCycles::GetStackTrace(GraphId id, void*** ptr) { + Node* n = FindNode(rep_, id); + if (n == nullptr) { + *ptr = nullptr; + return 0; + } else { + *ptr = n->stack; + return n->nstack; + } +} + +} // namespace synchronization_internal +} // namespace absl + +#endif // ABSL_LOW_LEVEL_ALLOC_MISSING http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.h ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.h b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.h new file mode 100644 index 0000000..53474b7 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles.h @@ -0,0 +1,136 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +#ifndef ABSL_SYNCHRONIZATION_INTERNAL_GRAPHCYCLES_H_ +#define ABSL_SYNCHRONIZATION_INTERNAL_GRAPHCYCLES_H_ + +// GraphCycles detects the introduction of a cycle into a directed +// graph that is being built up incrementally. +// +// Nodes are identified by small integers. It is not possible to +// record multiple edges with the same (source, destination) pair; +// requests to add an edge where one already exists are silently +// ignored. +// +// It is also not possible to introduce a cycle; an attempt to insert +// an edge that would introduce a cycle fails and returns false. +// +// GraphCycles uses no internal locking; calls into it should be +// serialized externally. + +// Performance considerations: +// Works well on sparse graphs, poorly on dense graphs. +// Extra information is maintained incrementally to detect cycles quickly. +// InsertEdge() is very fast when the edge already exists, and reasonably fast +// otherwise. +// FindPath() is linear in the size of the graph. +// The current implemenation uses O(|V|+|E|) space. + +#include <cstdint> + +namespace absl { +namespace synchronization_internal { + +// Opaque identifier for a graph node. +struct GraphId { + uint64_t handle; + + bool operator==(const GraphId& x) const { return handle == x.handle; } + bool operator!=(const GraphId& x) const { return handle != x.handle; } +}; + +// Return an invalid graph id that will never be assigned by GraphCycles. +inline GraphId InvalidGraphId() { + return GraphId{0}; +} + +class GraphCycles { + public: + GraphCycles(); + ~GraphCycles(); + + // Return the id to use for ptr, assigning one if necessary. + // Subsequent calls with the same ptr value will return the same id + // until Remove(). + GraphId GetId(void* ptr); + + // Remove "ptr" from the graph. Its corresponding node and all + // edges to and from it are removed. + void RemoveNode(void* ptr); + + // Return the pointer associated with id, or nullptr if id is not + // currently in the graph. + void* Ptr(GraphId id); + + // Attempt to insert an edge from source_node to dest_node. If the + // edge would introduce a cycle, return false without making any + // changes. Otherwise add the edge and return true. + bool InsertEdge(GraphId source_node, GraphId dest_node); + + // Remove any edge that exists from source_node to dest_node. + void RemoveEdge(GraphId source_node, GraphId dest_node); + + // Return whether node exists in the graph. + bool HasNode(GraphId node); + + // Return whether there is an edge directly from source_node to dest_node. + bool HasEdge(GraphId source_node, GraphId dest_node) const; + + // Return whether dest_node is reachable from source_node + // by following edges. + bool IsReachable(GraphId source_node, GraphId dest_node) const; + + // Find a path from "source" to "dest". If such a path exists, + // place the nodes on the path in the array path[], and return + // the number of nodes on the path. If the path is longer than + // max_path_len nodes, only the first max_path_len nodes are placed + // in path[]. The client should compare the return value with + // max_path_len" to see when this occurs. If no path exists, return + // 0. Any valid path stored in path[] will start with "source" and + // end with "dest". There is no guarantee that the path is the + // shortest, but no node will appear twice in the path, except the + // source and destination node if they are identical; therefore, the + // return value is at most one greater than the number of nodes in + // the graph. + int FindPath(GraphId source, GraphId dest, int max_path_len, + GraphId path[]) const; + + // Update the stack trace recorded for id with the current stack + // trace if the last time it was updated had a smaller priority + // than the priority passed on this call. + // + // *get_stack_trace is called to get the stack trace. + void UpdateStackTrace(GraphId id, int priority, + int (*get_stack_trace)(void**, int)); + + // Set *ptr to the beginning of the array that holds the recorded + // stack trace for id and return the depth of the stack trace. + int GetStackTrace(GraphId id, void*** ptr); + + // Check internal invariants. Crashes on failure, returns true on success. + // Expensive: should only be called from graphcycles_test.cc. + bool CheckInvariants() const; + + // ---------------------------------------------------- + struct Rep; + private: + Rep *rep_; // opaque representation + GraphCycles(const GraphCycles&) = delete; + GraphCycles& operator=(const GraphCycles&) = delete; +}; + +} // namespace synchronization_internal +} // namespace absl +#endif http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles_test.cc ---------------------------------------------------------------------- diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles_test.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles_test.cc new file mode 100644 index 0000000..9a85b39 --- /dev/null +++ b/libraries/ostrich/backend/3rdparty/abseil/absl/synchronization/internal/graphcycles_test.cc @@ -0,0 +1,462 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/synchronization/internal/graphcycles.h" + +#include <map> +#include <random> +#include <unordered_set> +#include <utility> +#include <vector> + +#include "gtest/gtest.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" + +namespace absl { +namespace synchronization_internal { + +// We emulate a GraphCycles object with a node vector and an edge vector. +// We then compare the two implementations. + +using Nodes = std::vector<int>; +struct Edge { + int from; + int to; +}; +using Edges = std::vector<Edge>; +using RandomEngine = std::mt19937_64; + +// Mapping from integer index to GraphId. +typedef std::map<int, GraphId> IdMap; +static GraphId Get(const IdMap& id, int num) { + auto iter = id.find(num); + return (iter == id.end()) ? InvalidGraphId() : iter->second; +} + +// Return whether "to" is reachable from "from". +static bool IsReachable(Edges *edges, int from, int to, + std::unordered_set<int> *seen) { + seen->insert(from); // we are investigating "from"; don't do it again + if (from == to) return true; + for (const auto &edge : *edges) { + if (edge.from == from) { + if (edge.to == to) { // success via edge directly + return true; + } else if (seen->find(edge.to) == seen->end() && // success via edge + IsReachable(edges, edge.to, to, seen)) { + return true; + } + } + } + return false; +} + +static void PrintEdges(Edges *edges) { + ABSL_RAW_LOG(INFO, "EDGES (%zu)", edges->size()); + for (const auto &edge : *edges) { + int a = edge.from; + int b = edge.to; + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc) { + ABSL_RAW_LOG(INFO, "GC EDGES"); + for (int a : *nodes) { + for (int b : *nodes) { + if (gc->HasEdge(Get(id, a), Get(id, b))) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintTransitiveClosure(Nodes *nodes, Edges *edges) { + ABSL_RAW_LOG(INFO, "Transitive closure"); + for (int a : *nodes) { + for (int b : *nodes) { + std::unordered_set<int> seen; + if (IsReachable(edges, a, b, &seen)) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id, + GraphCycles *gc) { + ABSL_RAW_LOG(INFO, "GC Transitive closure"); + for (int a : *nodes) { + for (int b : *nodes) { + if (gc->IsReachable(Get(id, a), Get(id, b))) { + ABSL_RAW_LOG(INFO, "%d %d", a, b); + } + } + } + ABSL_RAW_LOG(INFO, "---"); +} + +static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id, + GraphCycles *gc) { + std::unordered_set<int> seen; + for (const auto &a : *nodes) { + for (const auto &b : *nodes) { + seen.clear(); + bool gc_reachable = gc->IsReachable(Get(id, a), Get(id, b)); + bool reachable = IsReachable(edges, a, b, &seen); + if (gc_reachable != reachable) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + PrintTransitiveClosure(nodes, edges); + PrintGCTransitiveClosure(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "gc_reachable %s reachable %s a %d b %d", + gc_reachable ? "true" : "false", + reachable ? "true" : "false", a, b); + } + } + } +} + +static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id, + GraphCycles *gc) { + int count = 0; + for (const auto &edge : *edges) { + int a = edge.from; + int b = edge.to; + if (!gc->HasEdge(Get(id, a), Get(id, b))) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "!gc->HasEdge(%d, %d)", a, b); + } + } + for (const auto &a : *nodes) { + for (const auto &b : *nodes) { + if (gc->HasEdge(Get(id, a), Get(id, b))) { + count++; + } + } + } + if (count != edges->size()) { + PrintEdges(edges); + PrintGCEdges(nodes, id, gc); + ABSL_RAW_LOG(FATAL, "edges->size() %zu count %d", edges->size(), count); + } +} + +static void CheckInvariants(const GraphCycles &gc) { + if (ABSL_PREDICT_FALSE(!gc.CheckInvariants())) + ABSL_RAW_LOG(FATAL, "CheckInvariants"); +} + +// Returns the index of a randomly chosen node in *nodes. +// Requires *nodes be non-empty. +static int RandomNode(RandomEngine* rng, Nodes *nodes) { + std::uniform_int_distribution<int> uniform(0, nodes->size()-1); + return uniform(*rng); +} + +// Returns the index of a randomly chosen edge in *edges. +// Requires *edges be non-empty. +static int RandomEdge(RandomEngine* rng, Edges *edges) { + std::uniform_int_distribution<int> uniform(0, edges->size()-1); + return uniform(*rng); +} + +// Returns the index of edge (from, to) in *edges or -1 if it is not in *edges. +static int EdgeIndex(Edges *edges, int from, int to) { + int i = 0; + while (i != edges->size() && + ((*edges)[i].from != from || (*edges)[i].to != to)) { + i++; + } + return i == edges->size()? -1 : i; +} + +TEST(GraphCycles, RandomizedTest) { + int next_node = 0; + Nodes nodes; + Edges edges; // from, to + IdMap id; + GraphCycles graph_cycles; + static const int kMaxNodes = 7; // use <= 7 nodes to keep test short + static const int kDataOffset = 17; // an offset to the node-specific data + int n = 100000; + int op = 0; + RandomEngine rng(testing::UnitTest::GetInstance()->random_seed()); + std::uniform_int_distribution<int> uniform(0, 5); + + auto ptr = [](intptr_t i) { + return reinterpret_cast<void*>(i + kDataOffset); + }; + + for (int iter = 0; iter != n; iter++) { + for (const auto &node : nodes) { + ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), ptr(node)) << " node " << node; + } + CheckEdges(&nodes, &edges, id, &graph_cycles); + CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles); + op = uniform(rng); + switch (op) { + case 0: // Add a node + if (nodes.size() < kMaxNodes) { + int new_node = next_node++; + GraphId new_gnode = graph_cycles.GetId(ptr(new_node)); + ASSERT_NE(new_gnode, InvalidGraphId()); + id[new_node] = new_gnode; + ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode)); + nodes.push_back(new_node); + } + break; + + case 1: // Remove a node + if (nodes.size() > 0) { + int node_index = RandomNode(&rng, &nodes); + int node = nodes[node_index]; + nodes[node_index] = nodes.back(); + nodes.pop_back(); + graph_cycles.RemoveNode(ptr(node)); + ASSERT_EQ(graph_cycles.Ptr(Get(id, node)), nullptr); + id.erase(node); + int i = 0; + while (i != edges.size()) { + if (edges[i].from == node || edges[i].to == node) { + edges[i] = edges.back(); + edges.pop_back(); + } else { + i++; + } + } + } + break; + + case 2: // Add an edge + if (nodes.size() > 0) { + int from = RandomNode(&rng, &nodes); + int to = RandomNode(&rng, &nodes); + if (EdgeIndex(&edges, nodes[from], nodes[to]) == -1) { + if (graph_cycles.InsertEdge(id[nodes[from]], id[nodes[to]])) { + Edge new_edge; + new_edge.from = nodes[from]; + new_edge.to = nodes[to]; + edges.push_back(new_edge); + } else { + std::unordered_set<int> seen; + ASSERT_TRUE(IsReachable(&edges, nodes[to], nodes[from], &seen)) + << "Edge " << nodes[to] << "->" << nodes[from]; + } + } + } + break; + + case 3: // Remove an edge + if (edges.size() > 0) { + int i = RandomEdge(&rng, &edges); + int from = edges[i].from; + int to = edges[i].to; + ASSERT_EQ(i, EdgeIndex(&edges, from, to)); + edges[i] = edges.back(); + edges.pop_back(); + ASSERT_EQ(-1, EdgeIndex(&edges, from, to)); + graph_cycles.RemoveEdge(id[from], id[to]); + } + break; + + case 4: // Check a path + if (nodes.size() > 0) { + int from = RandomNode(&rng, &nodes); + int to = RandomNode(&rng, &nodes); + GraphId path[2*kMaxNodes]; + int path_len = graph_cycles.FindPath(id[nodes[from]], id[nodes[to]], + ABSL_ARRAYSIZE(path), path); + std::unordered_set<int> seen; + bool reachable = IsReachable(&edges, nodes[from], nodes[to], &seen); + bool gc_reachable = + graph_cycles.IsReachable(Get(id, nodes[from]), Get(id, nodes[to])); + ASSERT_EQ(path_len != 0, reachable); + ASSERT_EQ(path_len != 0, gc_reachable); + // In the following line, we add one because a node can appear + // twice, if the path is from that node to itself, perhaps via + // every other node. + ASSERT_LE(path_len, kMaxNodes + 1); + if (path_len != 0) { + ASSERT_EQ(id[nodes[from]], path[0]); + ASSERT_EQ(id[nodes[to]], path[path_len-1]); + for (int i = 1; i < path_len; i++) { + ASSERT_TRUE(graph_cycles.HasEdge(path[i-1], path[i])); + } + } + } + break; + + case 5: // Check invariants + CheckInvariants(graph_cycles); + break; + + default: + ABSL_RAW_LOG(FATAL, "op %d", op); + } + + // Very rarely, test graph expansion by adding then removing many nodes. + std::bernoulli_distribution one_in_1024(1.0 / 1024); + if (one_in_1024(rng)) { + CheckEdges(&nodes, &edges, id, &graph_cycles); + CheckTransitiveClosure(&nodes, &edges, id, &graph_cycles); + for (int i = 0; i != 256; i++) { + int new_node = next_node++; + GraphId new_gnode = graph_cycles.GetId(ptr(new_node)); + ASSERT_NE(InvalidGraphId(), new_gnode); + id[new_node] = new_gnode; + ASSERT_EQ(ptr(new_node), graph_cycles.Ptr(new_gnode)); + for (const auto &node : nodes) { + ASSERT_NE(node, new_node); + } + nodes.push_back(new_node); + } + for (int i = 0; i != 256; i++) { + ASSERT_GT(nodes.size(), 0); + int node_index = RandomNode(&rng, &nodes); + int node = nodes[node_index]; + nodes[node_index] = nodes.back(); + nodes.pop_back(); + graph_cycles.RemoveNode(ptr(node)); + id.erase(node); + int j = 0; + while (j != edges.size()) { + if (edges[j].from == node || edges[j].to == node) { + edges[j] = edges.back(); + edges.pop_back(); + } else { + j++; + } + } + } + CheckInvariants(graph_cycles); + } + } +} + +class GraphCyclesTest : public ::testing::Test { + public: + IdMap id_; + GraphCycles g_; + + static void* Ptr(int i) { + return reinterpret_cast<void*>(static_cast<uintptr_t>(i)); + } + + static int Num(void* ptr) { + return static_cast<int>(reinterpret_cast<uintptr_t>(ptr)); + } + + // Test relies on ith NewNode() call returning Node numbered i + GraphCyclesTest() { + for (int i = 0; i < 100; i++) { + id_[i] = g_.GetId(Ptr(i)); + } + CheckInvariants(g_); + } + + bool AddEdge(int x, int y) { + return g_.InsertEdge(Get(id_, x), Get(id_, y)); + } + + void AddMultiples() { + // For every node x > 0: add edge to 2*x, 3*x + for (int x = 1; x < 25; x++) { + EXPECT_TRUE(AddEdge(x, 2*x)) << x; + EXPECT_TRUE(AddEdge(x, 3*x)) << x; + } + CheckInvariants(g_); + } + + std::string Path(int x, int y) { + GraphId path[5]; + int np = g_.FindPath(Get(id_, x), Get(id_, y), ABSL_ARRAYSIZE(path), path); + std::string result; + for (int i = 0; i < np; i++) { + if (i >= ABSL_ARRAYSIZE(path)) { + result += " ..."; + break; + } + if (!result.empty()) result.push_back(' '); + char buf[20]; + snprintf(buf, sizeof(buf), "%d", Num(g_.Ptr(path[i]))); + result += buf; + } + return result; + } +}; + +TEST_F(GraphCyclesTest, NoCycle) { + AddMultiples(); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, SimpleCycle) { + AddMultiples(); + EXPECT_FALSE(AddEdge(8, 4)); + EXPECT_EQ("4 8", Path(4, 8)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, IndirectCycle) { + AddMultiples(); + EXPECT_TRUE(AddEdge(16, 9)); + CheckInvariants(g_); + EXPECT_FALSE(AddEdge(9, 2)); + EXPECT_EQ("2 4 8 16 9", Path(2, 9)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, LongPath) { + ASSERT_TRUE(AddEdge(2, 4)); + ASSERT_TRUE(AddEdge(4, 6)); + ASSERT_TRUE(AddEdge(6, 8)); + ASSERT_TRUE(AddEdge(8, 10)); + ASSERT_TRUE(AddEdge(10, 12)); + ASSERT_FALSE(AddEdge(12, 2)); + EXPECT_EQ("2 4 6 8 10 ...", Path(2, 12)); + CheckInvariants(g_); +} + +TEST_F(GraphCyclesTest, RemoveNode) { + ASSERT_TRUE(AddEdge(1, 2)); + ASSERT_TRUE(AddEdge(2, 3)); + ASSERT_TRUE(AddEdge(3, 4)); + ASSERT_TRUE(AddEdge(4, 5)); + g_.RemoveNode(g_.Ptr(id_[3])); + id_.erase(3); + ASSERT_TRUE(AddEdge(5, 1)); +} + +TEST_F(GraphCyclesTest, ManyEdges) { + const int N = 50; + for (int i = 0; i < N; i++) { + for (int j = 1; j < N; j++) { + ASSERT_TRUE(AddEdge(i, i+j)); + } + } + CheckInvariants(g_); + ASSERT_TRUE(AddEdge(2*N-1, 0)); + CheckInvariants(g_); + ASSERT_FALSE(AddEdge(10, 9)); + CheckInvariants(g_); +} + +} // namespace synchronization_internal +} // namespace absl
