| 2042 | |
| 2043 | |
| 2044 | void Sort::sortBuffer(thread_db* tdbb) |
| 2045 | { |
| 2046 | /************************************** |
| 2047 | * |
| 2048 | * Set up for and call quick sort. Quicksort, by design, doesn't |
| 2049 | * order partitions of length 2, so make a pass thru the data to |
| 2050 | * straighten out pairs. While we at it, if duplicate handling has |
| 2051 | * been requested, detect and handle them. |
| 2052 | * |
| 2053 | **************************************/ |
| 2054 | EngineCheckout cout(tdbb, FB_FUNCTION); |
| 2055 | |
| 2056 | // First, insert a pointer to the high key |
| 2057 | |
| 2058 | *m_next_pointer = reinterpret_cast<sort_record*>(high_key); |
| 2059 | |
| 2060 | // Next, call QuickSort. Keep in mind that the first pointer is the |
| 2061 | // low key and not a record. |
| 2062 | |
| 2063 | SORTP** j = (SORTP**) (m_first_pointer) + 1; |
| 2064 | const ULONG n = (SORTP**) (m_next_pointer) - j; // calculate # of records |
| 2065 | |
| 2066 | quick(n, j, m_longs); |
| 2067 | |
| 2068 | // Scream through and correct any out of order pairs |
| 2069 | // hvlad: don't compare user keys against high_key |
| 2070 | while (j < (SORTP**) m_next_pointer - 1) |
| 2071 | { |
| 2072 | SORTP** i = j; |
| 2073 | j++; |
| 2074 | if (**i >= **j) |
| 2075 | { |
| 2076 | const SORTP* p = *i; |
| 2077 | const SORTP* q = *j; |
| 2078 | ULONG tl = m_longs - 1; |
| 2079 | while (tl && *p == *q) |
| 2080 | { |
| 2081 | p++; |
| 2082 | q++; |
| 2083 | tl--; |
| 2084 | } |
| 2085 | if (tl && *p > *q) { |
| 2086 | swap(i, j); |
| 2087 | } |
| 2088 | } |
| 2089 | } |
| 2090 | |
| 2091 | // If duplicate handling hasn't been requested, we're done |
| 2092 | |
| 2093 | if (!m_dup_callback) |
| 2094 | return; |
| 2095 | |
| 2096 | // Make another pass and eliminate duplicates. It's possible to do this |
| 2097 | // in the same pass the final ordering, but the logic is complicated enough |
| 2098 | // to screw up register optimizations. Better two fast passes than one |
| 2099 | // slow pass, I suppose. Prove me wrong and win a trip for two to |
| 2100 | // Cleveland, Ohio. |
| 2101 | |