| 314 | |
| 315 | template <typename Tag, typename type> |
| 316 | static int |
| 317 | string_quicksort_(type *start, npy_intp num, void *varr) |
| 318 | { |
| 319 | PyArrayObject *arr = (PyArrayObject *)varr; |
| 320 | const size_t len = PyArray_ITEMSIZE(arr) / sizeof(type); |
| 321 | type *vp; |
| 322 | type *pl = start; |
| 323 | type *pr = pl + (num - 1) * len; |
| 324 | type *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk; |
| 325 | int depth[PYA_QS_STACK]; |
| 326 | int *psdepth = depth; |
| 327 | int cdepth = npy_get_msb(num) * 2; |
| 328 | |
| 329 | /* Items that have zero size don't make sense to sort */ |
| 330 | if (len == 0) { |
| 331 | return 0; |
| 332 | } |
| 333 | |
| 334 | vp = (type *)malloc(PyArray_ITEMSIZE(arr)); |
| 335 | if (vp == NULL) { |
| 336 | return -NPY_ENOMEM; |
| 337 | } |
| 338 | |
| 339 | for (;;) { |
| 340 | if (NPY_UNLIKELY(cdepth < 0)) { |
| 341 | string_heapsort_<Tag>(pl, (pr - pl) / len + 1, varr); |
| 342 | goto stack_pop; |
| 343 | } |
| 344 | while ((size_t)(pr - pl) > SMALL_QUICKSORT * len) { |
| 345 | /* quicksort partition */ |
| 346 | pm = pl + (((pr - pl) / len) >> 1) * len; |
| 347 | if (Tag::less(pm, pl, len)) { |
| 348 | Tag::swap(pm, pl, len); |
| 349 | } |
| 350 | if (Tag::less(pr, pm, len)) { |
| 351 | Tag::swap(pr, pm, len); |
| 352 | } |
| 353 | if (Tag::less(pm, pl, len)) { |
| 354 | Tag::swap(pm, pl, len); |
| 355 | } |
| 356 | Tag::copy(vp, pm, len); |
| 357 | pi = pl; |
| 358 | pj = pr - len; |
| 359 | Tag::swap(pm, pj, len); |
| 360 | for (;;) { |
| 361 | do { |
| 362 | pi += len; |
| 363 | } while (Tag::less(pi, vp, len)); |
| 364 | do { |
| 365 | pj -= len; |
| 366 | } while (Tag::less(vp, pj, len)); |
| 367 | if (pi >= pj) { |
| 368 | break; |
| 369 | } |
| 370 | Tag::swap(pi, pj, len); |
| 371 | } |
| 372 | pk = pr - len; |
| 373 | Tag::swap(pi, pk, len); |
nothing calls this directly
no test coverage detected