DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (d8847129d134)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210

/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */


#ifndef SkTSort_DEFINED
#define SkTSort_DEFINED

#include "SkTypes.h"
#include "SkMath.h"

/* A comparison functor which performs the comparison 'a < b'. */
template <typename T> struct SkTCompareLT {
    bool operator()(const T a, const T b) const { return a < b; }
};

/* A comparison functor which performs the comparison '*a < *b'. */
template <typename T> struct SkTPointerCompareLT {
    bool operator()(const T* a, const T* b) const { return *a < *b; }
};

///////////////////////////////////////////////////////////////////////////////

/*  Sifts a broken heap. The input array is a heap from root to bottom
 *  except that the root entry may be out of place.
 *
 *  Sinks a hole from array[root] to leaf and then sifts the original array[root] element
 *  from the leaf level up.
 *
 *  This version does extra work, in that it copies child to parent on the way down,
 *  then copies parent to child on the way back up. When copies are inexpensive,
 *  this is an optimization as this sift variant should only be used when
 *  the potentially out of place root entry value is expected to be small.
 *
 *  @param root the one based index into array of the out-of-place root of the heap.
 *  @param bottom the one based index in the array of the last entry in the heap.
 */
template <typename T, typename C>
void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) {
    T x = array[root-1];
    size_t start = root;
    size_t j = root << 1;
    while (j <= bottom) {
        if (j < bottom && lessThan(array[j-1], array[j])) {
            ++j;
        }
        array[root-1] = array[j-1];
        root = j;
        j = root << 1;
    }
    j = root >> 1;
    while (j >= start) {
        if (lessThan(array[j-1], x)) {
            array[root-1] = array[j-1];
            root = j;
            j = root >> 1;
        } else {
            break;
        }
    }
    array[root-1] = x;
}

/*  Sifts a broken heap. The input array is a heap from root to bottom
 *  except that the root entry may be out of place.
 *
 *  Sifts the array[root] element from the root down.
 *
 *  @param root the one based index into array of the out-of-place root of the heap.
 *  @param bottom the one based index in the array of the last entry in the heap.
 */
template <typename T, typename C>
void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) {
    T x = array[root-1];
    size_t child = root << 1;
    while (child <= bottom) {
        if (child < bottom && lessThan(array[child-1], array[child])) {
            ++child;
        }
        if (lessThan(x, array[child-1])) {
            array[root-1] = array[child-1];
            root = child;
            child = root << 1;
        } else {
            break;
        }
    }
    array[root-1] = x;
}

/** Sorts the array of size count using comparator lessThan using a Heap Sort algorithm. Be sure to
 *  specialize SkTSwap if T has an efficient swap operation.
 *
 *  @param array the array to be sorted.
 *  @param count the number of elements in the array.
 *  @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
 */
template <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) {
    for (size_t i = count >> 1; i > 0; --i) {
        SkTHeapSort_SiftDown(array, i, count, lessThan);
    }

    for (size_t i = count - 1; i > 0; --i) {
        SkTSwap<T>(array[0], array[i]);
        SkTHeapSort_SiftUp(array, 1, i, lessThan);
    }
}

/** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */
template <typename T> void SkTHeapSort(T array[], size_t count) {
    SkTHeapSort(array, count, SkTCompareLT<T>());
}

///////////////////////////////////////////////////////////////////////////////

/** Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm. */
template <typename T, typename C> static void SkTInsertionSort(T* left, T* right, C lessThan) {
    for (T* next = left + 1; next <= right; ++next) {
        T insert = *next;
        T* hole = next;
        while (left < hole && lessThan(insert, *(hole - 1))) {
            *hole = *(hole - 1);
            --hole;
        }
        *hole = insert;
    }
}

///////////////////////////////////////////////////////////////////////////////

template <typename T, typename C>
static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) {
    T pivotValue = *pivot;
    SkTSwap(*pivot, *right);
    T* newPivot = left;
    while (left < right) {
        if (lessThan(*left, pivotValue)) {
            SkTSwap(*left, *newPivot);
            newPivot += 1;
        }
        left += 1;
    }
    SkTSwap(*newPivot, *right);
    return newPivot;
}

/*  Intro Sort is a modified Quick Sort.
 *  When the region to be sorted is a small constant size it uses Insertion Sort.
 *  When depth becomes zero, it switches over to Heap Sort.
 *  This implementation recurses on the left region after pivoting and loops on the right,
 *    we already limit the stack depth by switching to heap sort,
 *    and cache locality on the data appears more important than saving a few stack frames.
 *
 *  @param depth at this recursion depth, switch to Heap Sort.
 *  @param left the beginning of the region to be sorted.
 *  @param right the end of the region to be sorted (inclusive).
 *  @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
 */
template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) {
    while (true) {
        if (right - left < 32) {
            SkTInsertionSort(left, right, lessThan);
            return;
        }

        if (depth == 0) {
            SkTHeapSort<T>(left, right - left + 1, lessThan);
            return;
        }
        --depth;

        T* pivot = left + ((right - left) >> 1);
        pivot = SkTQSort_Partition(left, right, pivot, lessThan);

        SkTIntroSort(depth, left, pivot - 1, lessThan);
        left = pivot + 1;
    }
}

/** Sorts the region from left to right using comparator lessThan using a Quick Sort algorithm. Be
 *  sure to specialize SkTSwap if T has an efficient swap operation.
 *
 *  @param left the beginning of the region to be sorted.
 *  @param right the end of the region to be sorted (inclusive).
 *  @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
 */
template <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) {
    if (left >= right) {
        return;
    }
    // Limit Intro Sort recursion depth to no more than 2 * ceil(log2(n)).
    int depth = 2 * SkNextLog2(SkToU32(right - left));
    SkTIntroSort(depth, left, right, lessThan);
}

/** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */
template <typename T> void SkTQSort(T* left, T* right) {
    SkTQSort(left, right, SkTCompareLT<T>());
}

/** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */
template <typename T> void SkTQSort(T** left, T** right) {
    SkTQSort(left, right, SkTPointerCompareLT<T>());
}

#endif