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