You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@marmotta.apache.org by ss...@apache.org on 2018/04/29 19:35:54 UTC
[25/51] [partial] marmotta git commit: * Replace gtest with upstream
version,
including LICENSE header. * Include absl library for faster and safer string
operations. * Update license headers where needed. * Removed custom code
replaced by absl.
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