Repository: mesos Updated Branches: refs/heads/master c72bd196d -> f9f474c26
stout: Make the counting of netmask set bits more efficient. see summary Review: https://reviews.apache.org/r/31677 Project: http://git-wip-us.apache.org/repos/asf/mesos/repo Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/1730af32 Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/1730af32 Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/1730af32 Branch: refs/heads/master Commit: 1730af32755b360cd341573a2d02b9a1946c02a7 Parents: c72bd19 Author: Evelina Dumitrescu <[email protected]> Authored: Wed Mar 11 09:50:53 2015 -0700 Committer: Dominic Hamon <[email protected]> Committed: Wed Mar 11 09:54:23 2015 -0700 ---------------------------------------------------------------------- 3rdparty/libprocess/3rdparty/stout/Makefile.am | 1 + .../3rdparty/stout/include/Makefile.am | 1 + .../3rdparty/stout/include/stout/bits.hpp | 37 ++++++++++++++++++++ .../3rdparty/stout/include/stout/ip.hpp | 11 ++---- .../3rdparty/stout/tests/bits_tests.cpp | 13 +++++++ 5 files changed, 54 insertions(+), 9 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/mesos/blob/1730af32/3rdparty/libprocess/3rdparty/stout/Makefile.am ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/Makefile.am b/3rdparty/libprocess/3rdparty/stout/Makefile.am index a522455..cde5106 100644 --- a/3rdparty/libprocess/3rdparty/stout/Makefile.am +++ b/3rdparty/libprocess/3rdparty/stout/Makefile.am @@ -12,6 +12,7 @@ SUBDIRS = . include # Tests. EXTRA_DIST = \ tests/base64_tests.cpp \ + tests/bits_tests.cpp \ tests/bytes_tests.cpp \ tests/cache_tests.cpp \ tests/duration_tests.cpp \ http://git-wip-us.apache.org/repos/asf/mesos/blob/1730af32/3rdparty/libprocess/3rdparty/stout/include/Makefile.am ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/include/Makefile.am b/3rdparty/libprocess/3rdparty/stout/include/Makefile.am index e2e0971..8effd89 100644 --- a/3rdparty/libprocess/3rdparty/stout/include/Makefile.am +++ b/3rdparty/libprocess/3rdparty/stout/include/Makefile.am @@ -2,6 +2,7 @@ nobase_include_HEADERS = \ stout/abort.hpp \ stout/base64.hpp \ + stout/bits.hpp \ stout/bytes.hpp \ stout/cache.hpp \ stout/check.hpp \ http://git-wip-us.apache.org/repos/asf/mesos/blob/1730af32/3rdparty/libprocess/3rdparty/stout/include/stout/bits.hpp ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/include/stout/bits.hpp b/3rdparty/libprocess/3rdparty/stout/include/stout/bits.hpp new file mode 100644 index 0000000..b9a9c20 --- /dev/null +++ b/3rdparty/libprocess/3rdparty/stout/include/stout/bits.hpp @@ -0,0 +1,37 @@ +/** + * 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 __STOUT_BITS_HPP__ +#define __STOUT_BITS_HPP__ + +#include <stdint.h> + +// Provides efficient bit operations. +// More details can be found at: +// http://graphics.stanford.edu/~seander/bithacks.html +namespace bits { + +// Counts set bits from a 32 bit unsigned integer using Hamming weight. +inline int countSetBits(uint32_t value) +{ + int count = 0; + value = value - ((value >> 1) & 0x55555555); + value = (value & 0x33333333) + ((value >> 2) & 0x33333333); + count = (((value + (value >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; + + return count; +} + +} // namespace bits { + +#endif // __STOUT_BITS_HPP__ http://git-wip-us.apache.org/repos/asf/mesos/blob/1730af32/3rdparty/libprocess/3rdparty/stout/include/stout/ip.hpp ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/include/stout/ip.hpp b/3rdparty/libprocess/3rdparty/stout/include/stout/ip.hpp index e4e86de..69cd81e 100644 --- a/3rdparty/libprocess/3rdparty/stout/include/stout/ip.hpp +++ b/3rdparty/libprocess/3rdparty/stout/include/stout/ip.hpp @@ -38,6 +38,7 @@ #include <string> #include "abort.hpp" +#include "bits.hpp" #include "error.hpp" #include "none.hpp" #include "numify.hpp" @@ -295,15 +296,7 @@ public: { switch (netmask_.family()) { case AF_INET: { - uint32_t mask = ntohl(netmask_.in().get().s_addr); - int value = 0; - - while (mask != 0) { - value += mask & 1; - mask >>= 1; - } - - return value; + return bits::countSetBits(ntohl(netmask_.in().get().s_addr)); } default: { UNREACHABLE(); http://git-wip-us.apache.org/repos/asf/mesos/blob/1730af32/3rdparty/libprocess/3rdparty/stout/tests/bits_tests.cpp ---------------------------------------------------------------------- diff --git a/3rdparty/libprocess/3rdparty/stout/tests/bits_tests.cpp b/3rdparty/libprocess/3rdparty/stout/tests/bits_tests.cpp new file mode 100644 index 0000000..c47bd13 --- /dev/null +++ b/3rdparty/libprocess/3rdparty/stout/tests/bits_tests.cpp @@ -0,0 +1,13 @@ +#include <gtest/gtest.h> + +#include <stout/bits.hpp> + +TEST(BitsTest, CountSetBits) +{ + EXPECT_EQ(0, bits::countSetBits(0)); + EXPECT_EQ(6, bits::countSetBits(0xf3)); + EXPECT_EQ(15, bits::countSetBits(0xffbf)); + EXPECT_EQ(22, bits::countSetBits(0xfffffc)); + EXPECT_EQ(26, bits::countSetBits(0xfffffcf)); + EXPECT_EQ(32, bits::countSetBits(0xffffffff)); +}
