| 511 | */ |
| 512 | |
| 513 | NPY_NO_EXPORT int |
| 514 | npy_quicksort(void *start, npy_intp num, void *varr) |
| 515 | { |
| 516 | PyArrayObject *arr = (PyArrayObject *)varr; |
| 517 | npy_intp elsize = PyArray_ITEMSIZE(arr); |
| 518 | PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare; |
| 519 | char *vp; |
| 520 | char *pl = (char *)start; |
| 521 | char *pr = pl + (num - 1) * elsize; |
| 522 | char *stack[PYA_QS_STACK]; |
| 523 | char **sptr = stack; |
| 524 | char *pm, *pi, *pj, *pk; |
| 525 | int depth[PYA_QS_STACK]; |
| 526 | int *psdepth = depth; |
| 527 | int cdepth = npy_get_msb(num) * 2; |
| 528 | |
| 529 | /* Items that have zero size don't make sense to sort */ |
| 530 | if (elsize == 0) { |
| 531 | return 0; |
| 532 | } |
| 533 | |
| 534 | vp = (char *)malloc(elsize); |
| 535 | if (vp == NULL) { |
| 536 | return -NPY_ENOMEM; |
| 537 | } |
| 538 | |
| 539 | for (;;) { |
| 540 | if (NPY_UNLIKELY(cdepth < 0)) { |
| 541 | npy_heapsort(pl, (pr - pl) / elsize + 1, varr); |
| 542 | goto stack_pop; |
| 543 | } |
| 544 | while (pr - pl > SMALL_QUICKSORT * elsize) { |
| 545 | /* quicksort partition */ |
| 546 | pm = pl + (((pr - pl) / elsize) >> 1) * elsize; |
| 547 | if (cmp(pm, pl, arr) < 0) { |
| 548 | GENERIC_SWAP(pm, pl, elsize); |
| 549 | } |
| 550 | if (cmp(pr, pm, arr) < 0) { |
| 551 | GENERIC_SWAP(pr, pm, elsize); |
| 552 | } |
| 553 | if (cmp(pm, pl, arr) < 0) { |
| 554 | GENERIC_SWAP(pm, pl, elsize); |
| 555 | } |
| 556 | GENERIC_COPY(vp, pm, elsize); |
| 557 | pi = pl; |
| 558 | pj = pr - elsize; |
| 559 | GENERIC_SWAP(pm, pj, elsize); |
| 560 | /* |
| 561 | * Generic comparisons may be buggy, so don't rely on the sentinels |
| 562 | * to keep the pointers from going out of bounds. |
| 563 | */ |
| 564 | for (;;) { |
| 565 | do { |
| 566 | pi += elsize; |
| 567 | } while (cmp(pi, vp, arr) < 0 && pi < pj); |
| 568 | do { |
| 569 | pj -= elsize; |
| 570 | } while (cmp(vp, pj, arr) < 0 && pi < pj); |
nothing calls this directly
no test coverage detected