Function qsort_cells

renderers/agg/include/agg_rasterizer_cells_aa.h:513–618

    //------------------------------------------------------------------------
    template<class Cell>
    void qsort_cells(Cell** start, unsigned num)
    {
        Cell**  stack[80];
        Cell*** top; 
        Cell**  limit;
        Cell**  base;

        limit = start + num;
        base  = start;
        top   = stack;

        for (;;)
        {
            int len = int(limit - base);

            Cell** i;
            Cell** j;
            Cell** pivot;

            if(len > qsort_threshold)
            {
                // we use base + len/2 as the pivot
                pivot = base + len / 2;
                swap_cells(base, pivot);

                i = base + 1;
                j = limit - 1;

                // now ensure that *i <= *base <= *j 
                if((*j)->x < (*i)->x)
                {
                    swap_cells(i, j);
                }

                if((*base)->x < (*i)->x)
                {
                    swap_cells(base, i);
                }

                if((*j)->x < (*base)->x)
                {
                    swap_cells(base, j);
                }

                for(;;)
                {
                    int x = (*base)->x;
                    do i++; while( (*i)->x < x );
                    do j--; while( x < (*j)->x );

                    if(i > j)
                    {
                        break;
                    }

                    swap_cells(i, j);
                }