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