diff options
Diffstat (limited to 'WebKit/android/sort.cpp')
-rw-r--r-- | WebKit/android/sort.cpp | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/WebKit/android/sort.cpp b/WebKit/android/sort.cpp new file mode 100644 index 0000000..de7aa6c --- /dev/null +++ b/WebKit/android/sort.cpp @@ -0,0 +1,56 @@ +/* + * Copyright 2007, The Android Open Source Project + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +namespace std +{ + void sort(const void** start, const void** end, const void** temp, Comparator comp) + { + size_t endlen = end - start; + size_t midlen = endlen / 2; + const void** mid = start + midlen; + if (midlen > 1) + sort(start, mid, temp, comp); + if (end - mid > 1) + sort(mid, end, temp, comp); + memcpy(temp, start, midlen * sizeof(*start)); + size_t i = 0; + size_t j = midlen; + size_t off = 0; + while (i < midlen && j < endlen) + start[off++] = (*comp)(start[j], temp[i]) ? start[j++] : temp[i++]; + if (i < midlen) + memcpy(&start[off], &temp[i], (midlen - i) * sizeof(*start)); + } + + void sort(const void** start, const void** end, Comparator comp) { + if (end - start > 1) { + const void** temp = new sortType[(end - start) / 2]; + sort(start, end, temp, comp); + delete[] temp; + } + } +} |