hphp/util/safesort.h

   1 /**
   2  * ===========================================================================
   3  * libc++ License
   4  * ===========================================================================
   5  *
   6  * The libc++ library is dual licensed under both the University of Illinois
   7  * "BSD-Like" license and the MIT license. As a user of this code you may
   8  * choose to use it under either license. As a contributor, you agree to allow
   9  * your code to be used under both.
  10  *
  11  * Full text of the relevant licenses is included below.
  12  *
  13  * ===========================================================================
  14  *
  15  * University of Illinois/NCSA
  16  * Open Source License
  17  *
  18  * Copyright (c) 2009-2012 by the contributors listed at
  19  * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
  20  *
  21  * All rights reserved.
  22  *
  23  * Developed by:
  24  *
  25  *     LLVM Team
  26  *
  27  *     University of Illinois at Urbana-Champaign
  28  *
  29  *     http://llvm.org
  30  *
  31  * Permission is hereby granted, free of charge, to any person obtaining a copy
  32  * of this software and associated documentation files (the "Software"), to
  33  * deal with the Software without restriction, including without limitation the
  34  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  35  * sell copies of the Software, and to permit persons to whom the Software is
  36  * furnished to do so, subject to the following conditions:
  37  *
  38  *     * Redistributions of source code must retain the above copyright notice,
  39  *       this list of conditions and the following disclaimers.
  40  *
  41  *     * Redistributions in binary form must reproduce the above copyright
  42  *       notice, this list of conditions and the following disclaimers in the
  43  *       documentation and/or other materials provided with the distribution.
  44  *
  45  *     * Neither the names of the LLVM Team, University of Illinois at
  46  *       Urbana-Champaign, nor the names of its contributors may be used to
  47  *       endorse or promote products derived from this Software without
  48  *       specific prior written permission.
  49  *
  50  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  51  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  52  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  53  * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  54  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  55  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  56  * WITH THE SOFTWARE.
  57  *
  58  * ===========================================================================
  59  *
  60  * Copyright (c) 2009-2012 by the contributors listed at
  61  * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
  62  *
  63  * Permission is hereby granted, free of charge, to any person obtaining a copy
  64  * of this software and associated documentation files (the "Software"), to
  65  * deal in the Software without restriction, including without limitation the
  66  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  67  * sell copies of the Software, and to permit persons to whom the Software is
  68  * furnished to do so, subject to the following conditions:
  69  *
  70  * The above copyright notice and this permission notice shall be included in
  71  * all copies or substantial portions of the Software.
  72  *
  73  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  74  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  75  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  76  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  77  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  78  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  79  * IN THE SOFTWARE.
  80  */
  81
  82 /**
  83  * == Safesort ==
  84  *
  85  * The safesort algorithm below is based on LLVM's libc++ implementation
  86  * of std::sort.
  87  *
  88  * The key difference is that safesort is safe to use with a comparator
  89  * that does not impose a strict weak ordering on the elements (whereas
  90  * std::sort may crash or go into infinite loops for such comparators).
  91  * Safesoft is also "exception safe", leaving the array in a consistent
  92  * state in the event that the comparator throws. This is important for
  93  * HipHop for several reasons. Some of the builtin comparators in PHP do
  94  * not impose a strict weak ordereding (ex. SORT_REGULAR over strings).
  95  * Also, user code can supply comparators that behave inconsistently or
  96  * throw exceptions.
  97  *
  98  * In cases where the comparator does not impose a strict weak ordering
  99  * or the comparator throws, no guarantees are made about the order of
 100  * the elements produced the sort algorithm, though the algorithm still
 101  * upholds a weaker guarantee that the result will be some permutation
 102  * of the input.
 103  */
 104
 105 #ifndef incl_HPHP_SAFESORT_H_
 106 #define incl_HPHP_SAFESORT_H_
 107
 108 #include <algorithm>
 109
 110 namespace HPHP {
 111 namespace Sort {
 112
 113 template <class CompT, class IterT>
 114 void sort3(IterT x, IterT y, IterT z, CompT c) {
 115   using std::swap;
 116   if (!c(*y, *x)) {
 117     if (!c(*z, *y))
 118       return;
 119     swap(*y, *z);
 120     if (c(*y, *x)) {
 121       swap(*x, *y);
 122     }
 123     return;
 124   }
 125   if (c(*z, *y)) {
 126     swap(*x, *z);
 127     return;
 128   }
 129   swap(*x, *y);
 130   if (c(*z, *y)) {
 131     swap(*y, *z);
 132   }
 133 }
 134
 135 template <class CompT, class IterT>
 136 void sort4(IterT x1, IterT x2, IterT x3, IterT x4, CompT c) {
 137   using std::swap;
 138   sort3<CompT>(x1, x2, x3, c);
 139   if (c(*x4, *x3)) {
 140     swap(*x3, *x4);
 141     if (c(*x3, *x2)) {
 142       swap(*x2, *x3);
 143       if (c(*x2, *x1)) {
 144         swap(*x1, *x2);
 145       }
 146     }
 147   }
 148 }
 149
 150 template <class CompT, class IterT>
 151 void sort5(IterT x1, IterT x2, IterT x3, IterT x4, IterT x5, CompT c) {
 152   using std::swap;
 153   sort4<CompT>(x1, x2, x3, x4, c);
 154   if (c(*x5, *x4)) {
 155     swap(*x4, *x5);
 156     if (c(*x4, *x3)) {
 157       swap(*x3, *x4);
 158       if (c(*x3, *x2)) {
 159         swap(*x2, *x3);
 160         if (c(*x2, *x1)) {
 161           swap(*x1, *x2);
 162         }
 163       }
 164     }
 165   }
 166 }
 167
 168 template <class CompT, class IterT>
 169 void insertion_sort(IterT first, IterT last, CompT comp) {
 170   typedef typename std::iterator_traits<IterT>::value_type value_type;
 171   typedef typename std::iterator_traits<IterT>::difference_type
 172     difference_type;
 173   difference_type len = last - first;
 174   if (len < 2) {
 175     // If there aren't at least 2 elements, we're done
 176     return;
 177   }
 178   // Loop over the first six elements
 179   IterT i = first;
 180   ++i;
 181   IterT l = (len < 6) ? last : first+6;
 182   for (; i != l; ++i) {
 183     IterT j = i;
 184     --j;
 185     // If this element is not less than the element
 186     // immediately before it, then we can leave this
 187     // element where it is for now
 188     if (!comp(*i, *j))
 189       continue;
 190     // Scan backward one element at a time looking
 191     // for the earliest element that *i is less than
 192     for (;;) {
 193       if (j == first) {
 194         break;
 195       }
 196       IterT k = j;
 197       --k;
 198       if (!comp(*i, *k)) {
 199         break;
 200       }
 201       j = k;
 202     }
 203     value_type t(*i);
 204     for (IterT k = i; k != j; --k) {
 205       *k = *(k-1);
 206     }
 207     *j = t;
 208   }
 209   // Loop over the remaining elements
 210   IterT second = first;
 211   ++second;
 212   for (; i != last; ++i) {
 213     IterT j = i;
 214     --j;
 215     // If this element is not less than the element
 216     // immediately before it, then we can leave this
 217     // element where it is for now
 218     if (!comp(*i, *j))
 219       continue;
 220     // Scan backward two elements at a time looking
 221     // for the earliest element that *i is less than
 222     for (;;) {
 223       // Invariant: j >= first && *i < *j
 224       if (j <= second) {
 225         // j points to first or second, so we have
 226         // reached the end of the loop
 227         if (j == second) {
 228           // If j points to second, we need to test
 229           // if *i is less than *first
 230           IterT m = j;
 231           --m;
 232           if (comp(*i, *m)) {
 233             j = m;
 234           }
 235         }
 236         break;
 237       }
 238       // Move backward by two
 239       IterT k = j-2;
 240       if (!comp(*i, *k)) {
 241         // If (*i < *k) is false, we know that *(k+1) or
 242         // *(k+2) is the element we are looking for.
 243         IterT m = k;
 244         ++m;
 245         if (comp(*i, *m)) {
 246           j = m;
 247         }
 248         break;
 249       }
 250       j = k;
 251     }
 252     // Move *i to temporary t, move the elements in the
 253     // range [j,i) over to the right one position, and
 254     // then move t to *j
 255     value_type t(*i);
 256     for (IterT m = i; m != j; --m) {
 257       *m = *(m-1);
 258     }
 259     *j = t;
 260   }
 261 }
 262
 263 template <class CompT, class IterT>
 264 void sort(IterT first, IterT last, CompT comp) {
 265   typedef typename std::iterator_traits<IterT>::difference_type
 266     difference_type;
 267   using std::swap;
 268   while (true) {
 269     difference_type len = last - first;
 270     // For small numbers of elements, use insertion sort
 271     if (len <= 16) {
 272       insertion_sort<CompT>(first, last, comp);
 273       return;
 274     }
 275     // Find a pivot
 276     IterT pivot;
 277     {
 278       IterT lm1 = last-1;
 279       difference_type delta = len/2;
 280       pivot = first + delta;
 281       if (len >= 1000) {
 282         // Compute the median of 5
 283         delta /= 2;
 284         sort5<CompT>(first, first + delta, pivot, pivot+delta, lm1, comp);
 285       } else {
 286         // Compute the median of 3
 287         sort3<CompT>(first, pivot, lm1, comp);
 288       }
 289       // Temporarily move the pivot to the second position
 290       swap(*(first+1), *pivot);
 291       pivot = first+1;
 292     }
 293     // Split the elements into two partitions (excluding the pivot);
 294     // we don't have to inspect the first element and last element
 295     // because they've already been put in the right place by the
 296     // call to sort3/sort5 above
 297     IterT i = first+2;
 298     IterT j = last-1;
 299     for (;;) {
 300       while (comp(*i, *pivot)) {
 301         ++i;
 302         if (UNLIKELY(i == j)) {
 303           goto done;
 304         }
 305       }
 306       --j;
 307       if (UNLIKELY(i == j)) {
 308         goto done;
 309       }
 310       while (comp(*pivot, *j)) {
 311         --j;
 312         if (UNLIKELY(i == j)) {
 313           goto done;
 314         }
 315       }
 316       swap(*i, *j);
 317       ++i;
 318       if (UNLIKELY(i == j)) {
 319         goto done;
 320       }
 321     }
 322     done:
 323     // Put the pivot in between the left partition and right partition
 324     swap(*pivot, *(i-1));
 325     // We now have the left partition in [first,i-1) and we have the
 326     // right parition in [i,last). Sort smaller partition with recursive
 327     // call and sort the larger partition with tail recursion elimination
 328     if ((i-1) - first < last - i) {
 329       sort<CompT>(first, i-1, comp);
 330       first = i;
 331     } else {
 332       sort<CompT>(i, last, comp);
 333       last = i-1;
 334     }
 335   }
 336 }
 337
 338 }
 339 }
 340
 341 #endif // incl_HPHP_SAFESORT_H_
 342