/src/icu/source/common/uarrsort.cpp

Source (jump to first uncovered line)
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
*
*   Copyright (C) 2003-2013, International Business Machines
*   Corporation and others.  All Rights Reserved.
*
*******************************************************************************
*   file name:  uarrsort.c
*   encoding:   UTF-8
*   tab size:   8 (not used)
*   indentation:4
*
*   created on: 2003aug04
*   created by: Markus W. Scherer
*
*   Internal function for sorting arrays.
*/

#include <cstddef>

#include "unicode/utypes.h"
#include "cmemory.h"
#include "uarrsort.h"

enum {
    /**
     * "from Knuth"
     *
     * A binary search over 8 items performs 4 comparisons:
     * log2(8)=3 to subdivide, +1 to check for equality.
     * A linear search over 8 items on average also performs 4 comparisons.
     */
    MIN_QSORT=9,
    STACK_ITEM_SIZE=200
};

static constexpr int32_t sizeInMaxAlignTs(int32_t sizeInBytes) {
    return (sizeInBytes + sizeof(std::max_align_t) - 1) / sizeof(std::max_align_t);
}

/* UComparator convenience implementations ---------------------------------- */

U_CAPI int32_t U_EXPORT2
uprv_uint16Comparator(const void *context, const void *left, const void *right) {
    (void)context;
    return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
}

U_CAPI int32_t U_EXPORT2
uprv_int32Comparator(const void *context, const void *left, const void *right) {
    (void)context;
    return *(const int32_t *)left - *(const int32_t *)right;
}

U_CAPI int32_t U_EXPORT2
uprv_uint32Comparator(const void *context, const void *left, const void *right) {
    (void)context;
    uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;

    /* compare directly because (l-r) would overflow the int32_t result */
    if(l<r) {
        return -1;
    } else if(l==r) {
        return 0;
    } else /* l>r */ {
        return 1;
    }
}

/* Insertion sort using binary search --------------------------------------- */

U_CAPI int32_t U_EXPORT2
uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
                        UComparator *cmp, const void *context) {
    int32_t start=0;
    UBool found=FALSE;

    /* Binary search until we get down to a tiny sub-array. */
    while((limit-start)>=MIN_QSORT) {
        int32_t i=(start+limit)/2;
        int32_t diff=cmp(context, item, array+i*itemSize);
        if(diff==0) {
            /*
             * Found the item. We look for the *last* occurrence of such
             * an item, for stable sorting.
             * If we knew that there will be only few equal items,
             * we could break now and enter the linear search.
             * However, if there are many equal items, then it should be
             * faster to continue with the binary search.
             * It seems likely that we either have all unique items
             * (where found will never become TRUE in the insertion sort)
             * or potentially many duplicates.
             */
            found=TRUE;
            start=i+1;
        } else if(diff<0) {
            limit=i;
        } else {
            start=i;
        }
    }

    /* Linear search over the remaining tiny sub-array. */
    while(start<limit) {
        int32_t diff=cmp(context, item, array+start*itemSize);
        if(diff==0) {
            found=TRUE;
        } else if(diff<0) {
            break;
        }
        ++start;
    }
    return found ? (start-1) : ~start;
}

static void
doInsertionSort(char *array, int32_t length, int32_t itemSize,
                UComparator *cmp, const void *context, void *pv) {
    int32_t j;

    for(j=1; j<length; ++j) {
        char *item=array+j*itemSize;
        int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
        if(insertionPoint<0) {
            insertionPoint=~insertionPoint;
        } else {
            ++insertionPoint;  /* one past the last equal item */
        }
        if(insertionPoint<j) {
            char *dest=array+insertionPoint*itemSize;
            uprv_memcpy(pv, item, itemSize);  /* v=array[j] */
            uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize);
            uprv_memcpy(dest, pv, itemSize);  /* array[insertionPoint]=v */
        }
    }
}

static void
insertionSort(char *array, int32_t length, int32_t itemSize,
              UComparator *cmp, const void *context, UErrorCode *pErrorCode) {

    icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE)> v;
    if (sizeInMaxAlignTs(itemSize) > v.getCapacity() &&
            v.resize(sizeInMaxAlignTs(itemSize)) == nullptr) {
        *pErrorCode = U_MEMORY_ALLOCATION_ERROR;
        return;
    }

    doInsertionSort(array, length, itemSize, cmp, context, v.getAlias());
}

/* QuickSort ---------------------------------------------------------------- */

/*
 * This implementation is semi-recursive:
 * It recurses for the smaller sub-array to shorten the recursion depth,
 * and loops for the larger sub-array.
 *
 * Loosely after QuickSort algorithms in
 * Niklaus Wirth
 * Algorithmen und Datenstrukturen mit Modula-2
 * B.G. Teubner Stuttgart
 * 4. Auflage 1986
 * ISBN 3-519-02260-5
 */
static void
subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
             UComparator *cmp, const void *context,
             void *px, void *pw) {
    int32_t left, right;

    /* start and left are inclusive, limit and right are exclusive */
    do {
        if((start+MIN_QSORT)>=limit) {
            doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
            break;
        }

        left=start;
        right=limit;

        /* x=array[middle] */
        uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize);

        do {
            while(/* array[left]<x */
                  cmp(context, array+left*itemSize, px)<0
            ) {
                ++left;
            }
            while(/* x<array[right-1] */
                  cmp(context, px, array+(right-1)*itemSize)<0
            ) {
                --right;
            }

            /* swap array[left] and array[right-1] via w; ++left; --right */
            if(left<right) {
                --right;

                if(left<right) {
                    uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize);
                    uprv_memcpy(array+(size_t)left*itemSize, array+(size_t)right*itemSize, itemSize);
                    uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize);
                }

                ++left;
            }
        } while(left<right);

        /* sort sub-arrays */
        if((right-start)<(limit-left)) {
            /* sort [start..right[ */
            if(start<(right-1)) {
                subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
            }

            /* sort [left..limit[ */
            start=left;
        } else {
            /* sort [left..limit[ */
            if(left<(limit-1)) {
                subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
            }

            /* sort [start..right[ */
            limit=right;
        }
    } while(start<(limit-1));
}

static void
quickSort(char *array, int32_t length, int32_t itemSize,
            UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
    /* allocate two intermediate item variables (x and w) */
    icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE) * 2> xw;
    if(sizeInMaxAlignTs(itemSize)*2 > xw.getCapacity() &&
            xw.resize(sizeInMaxAlignTs(itemSize) * 2) == nullptr) {
        *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
        return;
    }

    subQuickSort(array, 0, length, itemSize, cmp, context,
                 xw.getAlias(), xw.getAlias() + sizeInMaxAlignTs(itemSize));
}

/* uprv_sortArray() API ----------------------------------------------------- */

/*
 * Check arguments, select an appropriate implementation,
 * cast the array to char * so that array+i*itemSize works.
 */
U_CAPI void U_EXPORT2
uprv_sortArray(void *array, int32_t length, int32_t itemSize,
               UComparator *cmp, const void *context,
               UBool sortStable, UErrorCode *pErrorCode) {
    if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
        return;
    }
    if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
        *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
        return;
    }

    if(length<=1) {
        return;
    } else if(length<MIN_QSORT || sortStable) {
        insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
    } else {
        quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
    }
}

Coverage Report

Created: 2025-01-28 06:38

Line	Count	Source (jump to first uncovered line)
1		// © 2016 and later: Unicode, Inc. and others.
2		// License & terms of use: http://www.unicode.org/copyright.html
3		/*
4		*******************************************************************************
5		*
6		* Copyright (C) 2003-2013, International Business Machines
7		* Corporation and others. All Rights Reserved.
8		*
9		*******************************************************************************
10		* file name: uarrsort.c
11		* encoding: UTF-8
12		* tab size: 8 (not used)
13		* indentation:4
14		*
15		* created on: 2003aug04
16		* created by: Markus W. Scherer
17		*
18		* Internal function for sorting arrays.
19		*/
20
21		#include <cstddef>
22
23		#include "unicode/utypes.h"
24		#include "cmemory.h"
25		#include "uarrsort.h"
26
27		enum {
28		/**
29		* "from Knuth"
30		*
31		* A binary search over 8 items performs 4 comparisons:
32		* log2(8)=3 to subdivide, +1 to check for equality.
33		* A linear search over 8 items on average also performs 4 comparisons.
34		*/
35		MIN_QSORT=9,
36		STACK_ITEM_SIZE=200
37		};
38
39	0	static constexpr int32_t sizeInMaxAlignTs(int32_t sizeInBytes) {
40	0	return (sizeInBytes + sizeof(std::max_align_t) - 1) / sizeof(std::max_align_t);
41	0	}
42
43		/* UComparator convenience implementations ---------------------------------- */
44
45		U_CAPI int32_t U_EXPORT2
46	0	uprv_uint16Comparator(const void context, const void left, const void *right) {
47	0	(void)context;
48	0	return (int32_t)(const uint16_t )left - (int32_t)(const uint16_t )right;
49	0	}
50
51		U_CAPI int32_t U_EXPORT2
52	0	uprv_int32Comparator(const void context, const void left, const void *right) {
53	0	(void)context;
54	0	return (const int32_t )left - (const int32_t )right;
55	0	}
56
57		U_CAPI int32_t U_EXPORT2
58	0	uprv_uint32Comparator(const void context, const void left, const void *right) {
59	0	(void)context;
60	0	uint32_t l=(const uint32_t )left, r=(const uint32_t )right;
61
62		/* compare directly because (l-r) would overflow the int32_t result */
63	0	if(l<r) {
64	0	return -1;
65	0	} else if(l==r) {
66	0	return 0;
67	0	} else /* l>r */ {
68	0	return 1;
69	0	}
70	0	}
71
72		/* Insertion sort using binary search --------------------------------------- */
73
74		U_CAPI int32_t U_EXPORT2
75		uprv_stableBinarySearch(char array, int32_t limit, void item, int32_t itemSize,
76	0	UComparator cmp, const void context) {
77	0	int32_t start=0;
78	0	UBool found=FALSE;
79
80		/* Binary search until we get down to a tiny sub-array. */
81	0	while((limit-start)>=MIN_QSORT) {
82	0	int32_t i=(start+limit)/2;
83	0	int32_t diff=cmp(context, item, array+i*itemSize);
84	0	if(diff==0) {
85		/*
86		* Found the item. We look for the last occurrence of such
87		* an item, for stable sorting.
88		* If we knew that there will be only few equal items,
89		* we could break now and enter the linear search.
90		* However, if there are many equal items, then it should be
91		* faster to continue with the binary search.
92		* It seems likely that we either have all unique items
93		* (where found will never become TRUE in the insertion sort)
94		* or potentially many duplicates.
95		*/
96	0	found=TRUE;
97	0	start=i+1;
98	0	} else if(diff<0) {
99	0	limit=i;
100	0	} else {
101	0	start=i;
102	0	}
103	0	}
104
105		/* Linear search over the remaining tiny sub-array. */
106	0	while(start<limit) {
107	0	int32_t diff=cmp(context, item, array+start*itemSize);
108	0	if(diff==0) {
109	0	found=TRUE;
110	0	} else if(diff<0) {
111	0	break;
112	0	}
113	0	++start;
114	0	}
115	0	return found ? (start-1) : ~start;
116	0	}
117
118		static void
119		doInsertionSort(char *array, int32_t length, int32_t itemSize,
120	0	UComparator cmp, const void context, void *pv) {
121	0	int32_t j;
122
123	0	for(j=1; j<length; ++j) {
124	0	char item=array+jitemSize;
125	0	int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
126	0	if(insertionPoint<0) {
127	0	insertionPoint=~insertionPoint;
128	0	} else {
129	0	++insertionPoint; /* one past the last equal item */
130	0	}
131	0	if(insertionPoint<j) {
132	0	char dest=array+insertionPointitemSize;
133	0	uprv_memcpy(pv, item, itemSize); /* v=array[j] */
134	0	uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize);
135	0	uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */
136	0	}
137	0	}
138	0	}
139
140		static void
141		insertionSort(char *array, int32_t length, int32_t itemSize,
142	0	UComparator cmp, const void context, UErrorCode *pErrorCode) {
143
144	0	icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE)> v;
145	0	if (sizeInMaxAlignTs(itemSize) > v.getCapacity() &&
146	0	v.resize(sizeInMaxAlignTs(itemSize)) == nullptr) {
147	0	*pErrorCode = U_MEMORY_ALLOCATION_ERROR;
148	0	return;
149	0	}
150
151	0	doInsertionSort(array, length, itemSize, cmp, context, v.getAlias());
152	0	}
153
154		/* QuickSort ---------------------------------------------------------------- */
155
156		/*
157		* This implementation is semi-recursive:
158		* It recurses for the smaller sub-array to shorten the recursion depth,
159		* and loops for the larger sub-array.
160		*
161		* Loosely after QuickSort algorithms in
162		* Niklaus Wirth
163		* Algorithmen und Datenstrukturen mit Modula-2
164		* B.G. Teubner Stuttgart
165		* 4. Auflage 1986
166		* ISBN 3-519-02260-5
167		*/
168		static void
169		subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
170		UComparator cmp, const void context,
171	0	void px, void pw) {
172	0	int32_t left, right;
173
174		/* start and left are inclusive, limit and right are exclusive */
175	0	do {
176	0	if((start+MIN_QSORT)>=limit) {
177	0	doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
178	0	break;
179	0	}
180
181	0	left=start;
182	0	right=limit;
183
184		/* x=array[middle] */
185	0	uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize);
186
187	0	do {
188	0	while(/* array[left]<x */
189	0	cmp(context, array+left*itemSize, px)<0
190	0	) {
191	0	++left;
192	0	}
193	0	while(/* x<array[right-1] */
194	0	cmp(context, px, array+(right-1)*itemSize)<0
195	0	) {
196	0	--right;
197	0	}
198
199		/* swap array[left] and array[right-1] via w; ++left; --right */
200	0	if(left<right) {
201	0	--right;
202
203	0	if(left<right) {
204	0	uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize);
205	0	uprv_memcpy(array+(size_t)leftitemSize, array+(size_t)rightitemSize, itemSize);
206	0	uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize);
207	0	}
208
209	0	++left;
210	0	}
211	0	} while(left<right);
212
213		/* sort sub-arrays */
214	0	if((right-start)<(limit-left)) {
215		/* sort [start..right[ */
216	0	if(start<(right-1)) {
217	0	subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
218	0	}
219
220		/* sort [left..limit[ */
221	0	start=left;
222	0	} else {
223		/* sort [left..limit[ */
224	0	if(left<(limit-1)) {
225	0	subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
226	0	}
227
228		/* sort [start..right[ */
229	0	limit=right;
230	0	}
231	0	} while(start<(limit-1));
232	0	}
233
234		static void
235		quickSort(char *array, int32_t length, int32_t itemSize,
236	0	UComparator cmp, const void context, UErrorCode *pErrorCode) {
237		/* allocate two intermediate item variables (x and w) */
238	0	icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE) * 2> xw;
239	0	if(sizeInMaxAlignTs(itemSize)*2 > xw.getCapacity() &&
240	0	xw.resize(sizeInMaxAlignTs(itemSize) * 2) == nullptr) {
241	0	*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
242	0	return;
243	0	}
244
245	0	subQuickSort(array, 0, length, itemSize, cmp, context,
246	0	xw.getAlias(), xw.getAlias() + sizeInMaxAlignTs(itemSize));
247	0	}
248
249		/* uprv_sortArray() API ----------------------------------------------------- */
250
251		/*
252		* Check arguments, select an appropriate implementation,
253		* cast the array to char * so that array+i*itemSize works.
254		*/
255		U_CAPI void U_EXPORT2
256		uprv_sortArray(void *array, int32_t length, int32_t itemSize,
257		UComparator cmp, const void context,
258	0	UBool sortStable, UErrorCode *pErrorCode) {
259	0	if(pErrorCode==NULL \|\| U_FAILURE(*pErrorCode)) {
260	0	return;
261	0	}
262	0	if((length>0 && array==NULL) \|\| length<0 \|\| itemSize<=0 \|\| cmp==NULL) {
263	0	*pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
264	0	return;
265	0	}
266
267	0	if(length<=1) {
268	0	return;
269	0	} else if(length<MIN_QSORT \|\| sortStable) {
270	0	insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
271	0	} else {
272	0	quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
273	0	}
274	0	}