hphp/runtime/base/array-sort.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/base/array-init.h"
  18 #include "hphp/runtime/base/array-iterator.h"
  19 #include "hphp/runtime/base/execution-context.h"
  20 #include "hphp/runtime/base/vanilla-sort.h"
  21 #include "hphp/runtime/base/sort-helpers.h"
  22 #include "hphp/runtime/base/tv-mutate.h"
  23 #include "hphp/runtime/base/tv-variant.h"
  24 #include "hphp/runtime/base/vanilla-dict-defs.h"
  25 #include "hphp/runtime/base/vanilla-keyset.h"
  26 #include "hphp/runtime/base/vanilla-vec.h"
  27 #include "hphp/runtime/base/vanilla-vec-defs.h"
  28 #include "hphp/runtime/vm/jit/translator-inline.h"
  29 #include "hphp/runtime/vm/coeffects.h"
  30
  31 #include <folly/ScopeGuard.h>
  32
  33 namespace HPHP {
  34 ///////////////////////////////////////////////////////////////////////////////
  35
  36 /**
  37  * preSort() does an initial pass over the array to do some preparatory work
  38  * before the sort algorithm runs. For sorts that use builtin comparators, the
  39  * types of values are also observed during this first pass. By observing the
  40  * types during this initial pass, we can often use a specialized comparator
  41  * and avoid performing type checks during the actual sort.
  42  */
  43 template <typename AccessorT, class ArrayT>
  44 SortFlavor genericPreSort(ArrayT& arr,
  45                           const AccessorT& acc,
  46                           bool checkTypes) {
  47   assertx(arr.m_size > 0);
  48   if (!checkTypes && arr.m_size == arr.m_used) {
  49     // No need to loop over the elements, we're done
  50     return GenericSort;
  51   }
  52   typename ArrayT::Elm* start = arr.data();
  53   typename ArrayT::Elm* end = arr.data() + arr.m_used;
  54   bool allInts UNUSED = true;
  55   bool allStrs UNUSED = true;
  56   for (;;) {
  57     if (checkTypes) {
  58       while (!start->isTombstone()) {
  59         allInts = (allInts && acc.isInt(*start));
  60         allStrs = (allStrs && acc.isStr(*start));
  61         ++start;
  62         if (start == end) {
  63           goto done;
  64         }
  65       }
  66     } else {
  67       while (!start->isTombstone()) {
  68         ++start;
  69         if (start == end) {
  70           goto done;
  71         }
  72       }
  73     }
  74     --end;
  75     if (start == end) {
  76       goto done;
  77     }
  78     while (end->isTombstone()) {
  79       --end;
  80       if (start == end) {
  81         goto done;
  82       }
  83     }
  84     memcpy(start, end, sizeof(typename ArrayT::Elm));
  85   }
  86 done:
  87   arr.m_used = start - arr.data();
  88   assertx(arr.m_size == arr.m_used);
  89   if (checkTypes) {
  90     return allStrs ? StringSort : allInts ? IntegerSort : GenericSort;
  91   }
  92   return GenericSort;
  93 }
  94
  95 template <typename AccessorT>
  96 SortFlavor VanillaDict::preSort(const AccessorT& acc, bool checkTypes) {
  97   return genericPreSort(*this, acc, checkTypes);
  98 }
  99
 100 template <typename AccessorT>
 101 SortFlavor VanillaKeyset::preSort(const AccessorT& acc, bool checkTypes) {
 102   auto const oldUsed UNUSED = m_used;
 103   auto flav = genericPreSort(*this, acc, checkTypes);
 104   assertx(ClearElms(data() + m_used, oldUsed - m_used));
 105   return flav;
 106 }
 107
 108 /**
 109  * postSort() runs after the sort has been performed. For VanillaDict, postSort()
 110  * handles rebuilding the hash. Also, if resetKeys is true, postSort() will
 111  * renumber the keys 0 thru n-1.
 112  */
 113 void VanillaDict::postSort(bool resetKeys) {   // nothrow guarantee
 114   assertx(m_size > 0);
 115   assertx(m_size == m_used);
 116   auto const ht = initHash(m_scale);
 117   auto const mask = this->mask();
 118   if (resetKeys) {
 119     mutableKeyTypes()->renumberKeys();
 120     for (uint32_t pos = 0; pos < m_used; ++pos) {
 121       auto& e = data()[pos];
 122       if (e.hasStrKey()) decRefStr(e.skey);
 123       auto h = hash_int64(pos);
 124       e.setIntKey(pos, h);
 125       *findForNewInsert(ht, mask, h) = pos;
 126     }
 127     m_nextKI = m_size;
 128   } else {
 129     mutableKeyTypes()->makeCompact();
 130     auto data = this->data();
 131     for (uint32_t pos = 0; pos < m_used; ++pos) {
 132       auto& e = data[pos];
 133       *findForNewInsert(ht, mask, e.probe()) = pos;
 134     }
 135   }
 136   assertx(checkInvariants());
 137 }
 138
 139 /**
 140  * postSort() runs after the sort has been performed. For VanillaKeyset,
 141  * postSort() handles rebuilding the hash.
 142  */
 143 void VanillaKeyset::postSort(bool) {   // nothrow guarantee
 144   assertx(m_size > 0);
 145   auto const ht = initHash(m_scale);
 146   auto const mask = this->mask();
 147   auto elms = data();
 148   assertx(m_used == m_size);
 149   for (uint32_t i = 0; i < m_used; ++i) {
 150     auto& elm = elms[i];
 151     assertx(!elm.isInvalid());
 152     *findForNewInsert(ht, mask, elm.hash()) = i;
 153   }
 154 }
 155
 156 ArrayData* VanillaDict::EscalateForSort(ArrayData* ad, SortFunction sf) {
 157   auto const a = as(ad);
 158   return a->cowCheck() ? a->copyMixed() : a;
 159 }
 160
 161 ArrayData* VanillaKeyset::EscalateForSort(ArrayData* ad, SortFunction sf) {
 162   auto const a = asSet(ad);
 163   return a->cowCheck() ? a->copySet() : a;
 164 }
 165
 166 ArrayData* VanillaVec::EscalateForSort(ArrayData* ad, SortFunction sf) {
 167   assertx(checkInvariants(ad));
 168   assertx(sf != SORTFUNC_KSORT);
 169   if (isSortFamily(sf)) { // sort/rsort/usort
 170     return ad->cowCheck() ? VanillaVec::Copy(ad) : ad;
 171   }
 172   return ToMixedCopy(ad);
 173 }
 174
 175 #define SORT_CASE(flag, cmp_type, acc_type) \
 176   case flag: { \
 177     if (ascending) { \
 178       cmp_type##Compare<acc_type, flag, true> comp; \
 179       HPHP::Sort::sort(data_begin, data_end, comp); \
 180     } else { \
 181       cmp_type##Compare<acc_type, flag, false> comp; \
 182       HPHP::Sort::sort(data_begin, data_end, comp); \
 183     } \
 184     break; \
 185   }
 186 #define SORT_CASE_BLOCK(cmp_type, acc_type) \
 187   switch (sort_flags) { \
 188     default: /* fall through to SORT_REGULAR case */ \
 189     SORT_CASE(SORT_REGULAR, cmp_type, acc_type) \
 190     SORT_CASE(SORT_NUMERIC, cmp_type, acc_type) \
 191     SORT_CASE(SORT_STRING, cmp_type, acc_type) \
 192     SORT_CASE(SORT_STRING_CASE, cmp_type, acc_type) \
 193     SORT_CASE(SORT_LOCALE_STRING, cmp_type, acc_type) \
 194     SORT_CASE(SORT_NATURAL, cmp_type, acc_type) \
 195     SORT_CASE(SORT_NATURAL_CASE, cmp_type, acc_type) \
 196   }
 197
 198 #define CALL_SORT(acc_type)                     \
 199   if (flav == StringSort) {                     \
 200     SORT_CASE_BLOCK(StrElm, acc_type)           \
 201   } else if (flav == IntegerSort) {             \
 202     SORT_CASE_BLOCK(IntElm, acc_type)           \
 203   } else {                                      \
 204     SORT_CASE_BLOCK(Elm, acc_type)              \
 205   }
 206
 207 #define SORT_BODY(acc_type, resetKeys)                          \
 208   do {                                                          \
 209     if (!a->m_size) return;                                     \
 210     SortFlavor flav = a->preSort<acc_type>(acc_type(), true);   \
 211     try {                                                       \
 212       CALL_SORT(acc_type);                                      \
 213     } catch (...) {                                             \
 214       /* Make sure we leave the array in a consistent state */  \
 215       a->postSort(resetKeys);                                   \
 216       throw;                                                    \
 217     }                                                           \
 218     a->postSort(resetKeys);                                     \
 219   } while (0)
 220
 221 void VanillaDict::Ksort(ArrayData* ad, int sort_flags, bool ascending) {
 222   auto a = as(ad);
 223   auto data_begin = a->data();
 224   auto data_end = data_begin + a->m_size;
 225   SORT_BODY(AssocKeyAccessor<VanillaDict::Elm>, false);
 226 }
 227
 228 void VanillaDict::Sort(ArrayData* ad, int sort_flags, bool ascending) {
 229   auto a = as(ad);
 230   auto data_begin = a->data();
 231   auto data_end = data_begin + a->m_size;
 232   a->m_nextKI = 0;
 233   SORT_BODY(AssocValAccessor<VanillaDict::Elm>, true);
 234 }
 235
 236 void VanillaDict::Asort(ArrayData* ad, int sort_flags, bool ascending) {
 237   auto a = as(ad);
 238   auto data_begin = a->data();
 239   auto data_end = data_begin + a->m_size;
 240   SORT_BODY(AssocValAccessor<VanillaDict::Elm>, false);
 241 }
 242
 243 void VanillaKeyset::Ksort(ArrayData* ad, int sort_flags, bool ascending) {
 244   auto a = asSet(ad);
 245   auto data_begin = a->data();
 246   auto data_end = data_begin + a->m_size;
 247   SORT_BODY(AssocKeyAccessor<VanillaKeyset::Elm>, false);
 248 }
 249
 250 #undef SORT_BODY
 251
 252 void VanillaVec::Sort(ArrayData* ad, int sort_flags, bool ascending) {
 253   assertx(checkInvariants(ad));
 254   if (ad->m_size <= 1) {
 255     return;
 256   }
 257   assertx(!ad->hasMultipleRefs());
 258   auto a = ad;
 259   SortFlavor flav = preSort(ad);
 260   auto data_begin = VanillaLvalIterator { ad, 0 };
 261   auto data_end = data_begin + a->m_size;
 262   CALL_SORT(VanillaLvalAccessor);
 263 }
 264
 265 #undef SORT_CASE
 266 #undef SORT_CASE_BLOCK
 267 #undef CALL_SORT
 268
 269 #define USER_SORT_BODY(acc_type, resetKeys)                     \
 270   do {                                                          \
 271     CoeffectsAutoGuard _;                                       \
 272     if (!a->m_size) return true;                                \
 273     CallCtx ctx;                                                \
 274     vm_decode_function(cmp_function, ctx);                      \
 275     if (!ctx.func) {                                            \
 276       return false;                                             \
 277     }                                                           \
 278     a->preSort<acc_type>(acc_type(), false);                    \
 279     SCOPE_EXIT {                                                \
 280       /* Make sure we leave the array in a consistent state */  \
 281       a->postSort(resetKeys);                                   \
 282     };                                                          \
 283     ElmUCompare<acc_type> comp;                                 \
 284     comp.ctx = &ctx;                                            \
 285     HPHP::Sort::sort(a->data(), a->data() + a->m_size, comp);   \
 286     return true;                                                \
 287   } while (0)
 288
 289 bool VanillaDict::Uksort(ArrayData* ad, const Variant& cmp_function) {
 290   auto a = as(ad);
 291   USER_SORT_BODY(AssocKeyAccessor<VanillaDict::Elm>, false);
 292 }
 293
 294 bool VanillaDict::Usort(ArrayData* ad, const Variant& cmp_function) {
 295   auto a = as(ad);
 296   a->m_nextKI = 0;
 297   USER_SORT_BODY(AssocValAccessor<VanillaDict::Elm>, true);
 298 }
 299
 300 bool VanillaDict::Uasort(ArrayData* ad, const Variant& cmp_function) {
 301   auto a = as(ad);
 302   USER_SORT_BODY(AssocValAccessor<VanillaDict::Elm>, false);
 303 }
 304
 305 bool VanillaKeyset::Uksort(ArrayData* ad, const Variant& cmp_function) {
 306   auto a = asSet(ad);
 307   USER_SORT_BODY(AssocKeyAccessor<VanillaKeyset::Elm>, false);
 308 }
 309
 310 #undef USER_SORT_BODY
 311
 312 SortFlavor VanillaVec::preSort(ArrayData* ad) {
 313   assertx(checkInvariants(ad));
 314   assertx(ad->m_size > 0);
 315   bool allInts = true;
 316   bool allStrs = true;
 317   uint32_t i = 0;
 318   uint32_t size = ad->m_size;
 319   do {
 320     const auto type = VanillaVec::LvalUncheckedInt(ad, i).type();
 321     if (type == KindOfInt64) {
 322       if (!allInts) return GenericSort;
 323       allStrs = false;
 324     } else if (isStringType(type)) {
 325       if (!allStrs) return GenericSort;
 326       allInts = false;
 327     } else {
 328       return GenericSort;
 329     }
 330   } while (++i < size);
 331   if (allInts) return IntegerSort;
 332   assertx(allStrs);
 333   return StringSort;
 334 }
 335
 336 bool VanillaVec::Usort(ArrayData* ad, const Variant& cmp_function) {
 337   assertx(checkInvariants(ad));
 338   if (ad->m_size <= 1) {
 339     return true;
 340   }
 341   assertx(!ad->hasMultipleRefs());
 342   CoeffectsAutoGuard _;
 343   CallCtx ctx;
 344   vm_decode_function(cmp_function, ctx);
 345   if (!ctx.func) {
 346     return false;
 347   }
 348   ElmUCompare<VanillaLvalAccessor> comp;
 349   comp.ctx = &ctx;
 350   auto data = VanillaLvalIterator { ad, 0 };
 351   Sort::sort(data, data + ad->m_size, comp);
 352   return true;
 353 }
 354
 355 ///////////////////////////////////////////////////////////////////////////////
 356 }