folly/Foreach.h

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FOLLY_BASE_FOREACH_H_
  18 #define FOLLY_BASE_FOREACH_H_
  19
  20 /*
  21  * Iterim macros (until we have C++0x range-based for) that simplify
  22  * writing loops of the form
  23  *
  24  * for (Container<data>::iterator i = c.begin(); i != c.end(); ++i) statement
  25  *
  26  * Just replace the above with:
  27  *
  28  * FOR_EACH (i, c) statement
  29  *
  30  * and everything is taken care of.
  31  *
  32  * The implementation is a bit convoluted to make sure the container is
  33  * only evaluated once (however, keep in mind that c.end() is evaluated
  34  * at every pass through the loop). To ensure the container is not
  35  * evaluated multiple times, the macro defines one do-nothing if
  36  * statement to inject the Boolean variable FOR_EACH_state1, and then a
  37  * for statement that is executed only once, which defines the variable
  38  * FOR_EACH_state2 holding a reference to the container being
  39  * iterated. The workhorse is the last loop, which uses the just defined
  40  * reference FOR_EACH_state2.
  41  *
  42  * The state variables are nested so they don't interfere; you can use
  43  * FOR_EACH multiple times in the same scope, either at the same level or
  44  * nested.
  45  *
  46  * In optimized builds g++ eliminates the extra gymnastics entirely and
  47  * generates code 100% identical to the handwritten loop.
  48  *
  49  * This will not work with temporary containers.  Consider BOOST_FOREACH
  50  * if you need that.
  51  */
  52
  53 #include <boost/type_traits/remove_cv.hpp>
  54
  55 namespace folly { namespace detail {
  56
  57 /*
  58  * Simple template for obtaining the unqualified type given a generic
  59  * type T. For example, if T is const int,
  60  * typeof(remove_cv_from_expression(T())) yields int. Due to a bug in
  61  * g++, you need to actually use
  62  * typeof(remove_cv_from_expression(T())) instead of typename
  63  * boost::remove_cv<T>::type. Note that the function
  64  * remove_cv_from_expression is never defined - use it only inside
  65  * typeof.
  66  */
  67 template <class T> typename boost::remove_cv<T>::type
  68 remove_cv_from_expression(T value);
  69
  70 }}
  71
  72 /*
  73  * Use a "reference reference" (auto&&) to take advantage of reference
  74  * collapsing rules, if available.  In this case, FOR_EACH* will work with
  75  * temporary containers.
  76  */
  77 #define FB_AUTO_RR(x, y) auto&& x = y
  78
  79 /*
  80  * The first AUTO should be replaced by decltype((c)) &
  81  * FOR_EACH_state2, but bugs in gcc prevent that from functioning
  82  * properly. The second pair of parens in decltype is actually
  83  * required, see
  84  * cpp-next.com/archive/2011/04/appearing-and-disappearing-consts-in-c/
  85  */
  86 #define FOR_EACH(i, c)                              \
  87   if (bool FOR_EACH_state1 = false) {} else         \
  88     for (auto & FOR_EACH_state2 = (c);              \
  89          !FOR_EACH_state1; FOR_EACH_state1 = true)  \
  90       for (auto i = FOR_EACH_state2.begin();        \
  91            i != FOR_EACH_state2.end(); ++i)
  92
  93 /*
  94  * Similar to FOR_EACH, but iterates the container backwards by
  95  * using rbegin() and rend().
  96  */
  97 #define FOR_EACH_R(i, c)                                \
  98   if (bool FOR_EACH_R_state1 = false) {} else           \
  99     for (auto & FOR_EACH_R_state2 = (c);                \
 100          !FOR_EACH_R_state1; FOR_EACH_R_state1 = true)  \
 101       for (auto i = FOR_EACH_R_state2.rbegin();         \
 102            i != FOR_EACH_R_state2.rend(); ++i)
 103
 104 /*
 105  * Similar to FOR_EACH but also allows client to specify a 'count' variable
 106  * to track the current iteration in the loop (starting at zero).
 107  * Similar to python's enumerate() function.  For example:
 108  * string commaSeparatedValues = "VALUES: ";
 109  * FOR_EACH_ENUMERATE(ii, value, columns) {   // don't want comma at the end!
 110  *   commaSeparatedValues += (ii == 0) ? *value : string(",") + *value;
 111  * }
 112  */
 113 #define FOR_EACH_ENUMERATE(count, i, c)                                \
 114   if (bool FOR_EACH_state1 = false) {} else                            \
 115     for (auto & FOR_EACH_state2 = (c);                                 \
 116          !FOR_EACH_state1; FOR_EACH_state1 = true)                     \
 117       if (size_t FOR_EACH_privateCount = 0) {} else                    \
 118         if (const size_t& count = FOR_EACH_privateCount) {} else       \
 119           for (auto i = FOR_EACH_state2.begin();                       \
 120                i != FOR_EACH_state2.end(); ++FOR_EACH_privateCount, ++i)
 121
 122 /**
 123  * Similar to FOR_EACH, but gives the user the key and value for each entry in
 124  * the container, instead of just the iterator to the entry. For example:
 125  *   map<string, string> testMap;
 126  *   FOR_EACH_KV(key, value, testMap) {
 127  *      cout << key << " " << value;
 128  *   }
 129  */
 130 #define FOR_EACH_KV(k, v, c)                                    \
 131   if (unsigned int FOR_EACH_state1 = 0) {} else                 \
 132     for (FB_AUTO_RR(FOR_EACH_state2, (c));                      \
 133          !FOR_EACH_state1; FOR_EACH_state1 = 1)                 \
 134       for (auto FOR_EACH_state3 = FOR_EACH_state2.begin();      \
 135            FOR_EACH_state3 != FOR_EACH_state2.end();            \
 136            FOR_EACH_state1 == 2                                 \
 137              ? ((FOR_EACH_state1 = 0), ++FOR_EACH_state3)       \
 138              : (FOR_EACH_state3 = FOR_EACH_state2.end()))       \
 139         for (auto &k = FOR_EACH_state3->first;                  \
 140              !FOR_EACH_state1; ++FOR_EACH_state1)               \
 141           for (auto &v = FOR_EACH_state3->second;               \
 142                !FOR_EACH_state1; ++FOR_EACH_state1)
 143
 144 namespace folly { namespace detail {
 145
 146 // Boost 1.48 lacks has_less, we emulate a subset of it here.
 147 template <typename T, typename U>
 148 class HasLess {
 149   struct BiggerThanChar { char unused[2]; };
 150   template <typename C, typename D> static char test(decltype(C() < D())*);
 151   template <typename, typename> static BiggerThanChar test(...);
 152 public:
 153   enum { value = sizeof(test<T, U>(0)) == 1 };
 154 };
 155
 156 /**
 157  * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
 158  * using "<" instead of "!=" whenever available when checking for loop
 159  * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
 160  * 10, 5) execute zero iterations instead of looping virtually
 161  * forever. At the same time, some iterator types define "!=" but not
 162  * "<". The notThereYet function will dispatch differently for those.
 163  *
 164  * Below is the correct implementation of notThereYet. It is disabled
 165  * because of a bug in Boost 1.46: The filesystem::path::iterator
 166  * defines operator< (via boost::iterator_facade), but that in turn
 167  * uses distance_to which is undefined for that particular
 168  * iterator. So HasLess (defined above) identifies
 169  * boost::filesystem::path as properly comparable with <, but in fact
 170  * attempting to do so will yield a compile-time error.
 171  *
 172  * The else branch (active) contains a conservative
 173  * implementation.
 174  */
 175
 176 #if 0
 177
 178 template <class T, class U>
 179 typename std::enable_if<HasLess<T, U>::value, bool>::type
 180 notThereYet(T& iter, const U& end) {
 181   return iter < end;
 182 }
 183
 184 template <class T, class U>
 185 typename std::enable_if<!HasLess<T, U>::value, bool>::type
 186 notThereYet(T& iter, const U& end) {
 187   return iter != end;
 188 }
 189
 190 #else
 191
 192 template <class T, class U>
 193 typename std::enable_if<
 194   (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 195   (std::is_pointer<T>::value && std::is_pointer<U>::value),
 196   bool>::type
 197 notThereYet(T& iter, const U& end) {
 198   return iter < end;
 199 }
 200
 201 template <class T, class U>
 202 typename std::enable_if<
 203   !(
 204     (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
 205     (std::is_pointer<T>::value && std::is_pointer<U>::value)
 206   ),
 207   bool>::type
 208 notThereYet(T& iter, const U& end) {
 209   return iter != end;
 210 }
 211
 212 #endif
 213
 214
 215 /**
 216  * downTo is similar to notThereYet, but in reverse - it helps the
 217  * FOR_EACH_RANGE_R macro.
 218  */
 219 template <class T, class U>
 220 typename std::enable_if<HasLess<U, T>::value, bool>::type
 221 downTo(T& iter, const U& begin) {
 222   return begin < iter--;
 223 }
 224
 225 template <class T, class U>
 226 typename std::enable_if<!HasLess<U, T>::value, bool>::type
 227 downTo(T& iter, const U& begin) {
 228   if (iter == begin) return false;
 229   --iter;
 230   return true;
 231 }
 232
 233 } }
 234
 235 /*
 236  * Iteration with given limits. end is assumed to be reachable from
 237  * begin. end is evaluated every pass through the loop.
 238  *
 239  * NOTE: The type of the loop variable should be the common type of "begin"
 240  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 241  *       to be "long". This is done by getting the type of (true ? begin : end)
 242  */
 243 #define FOR_EACH_RANGE(i, begin, end)           \
 244   for (auto i = (true ? (begin) : (end));       \
 245        ::folly::detail::notThereYet(i, (end));  \
 246        ++i)
 247
 248 /*
 249  * Iteration with given limits. begin is assumed to be reachable from
 250  * end by successive decrements. begin is evaluated every pass through
 251  * the loop.
 252  *
 253  * NOTE: The type of the loop variable should be the common type of "begin"
 254  *       and "end". e.g. If "begin" is "int" but "end" is "long", we want "i"
 255  *       to be "long". This is done by getting the type of (false ? begin : end)
 256  */
 257 #define FOR_EACH_RANGE_R(i, begin, end) \
 258   for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
 259
 260 #endif