summaryrefslogtreecommitdiff
path: root/deps/node/deps/icu-small/source/common/uarrsort.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'deps/node/deps/icu-small/source/common/uarrsort.cpp')
-rw-r--r--deps/node/deps/icu-small/source/common/uarrsort.cpp288
1 files changed, 0 insertions, 288 deletions
diff --git a/deps/node/deps/icu-small/source/common/uarrsort.cpp b/deps/node/deps/icu-small/source/common/uarrsort.cpp
deleted file mode 100644
index 03c4d4e7..00000000
--- a/deps/node/deps/icu-small/source/common/uarrsort.cpp
+++ /dev/null
@@ -1,288 +0,0 @@
-// © 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 "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
-};
-
-/* 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) {
- UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
- void *pv;
-
- /* allocate an intermediate item variable (v) */
- if(itemSize<=STACK_ITEM_SIZE) {
- pv=v;
- } else {
- pv=uprv_malloc(itemSize);
- if(pv==NULL) {
- *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
- return;
- }
- }
-
- doInsertionSort(array, length, itemSize, cmp, context, pv);
-
- if(pv!=v) {
- uprv_free(pv);
- }
-}
-
-/* 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) {
- UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
- void *p;
-
- /* allocate two intermediate item variables (x and w) */
- if(itemSize<=STACK_ITEM_SIZE) {
- p=xw;
- } else {
- p=uprv_malloc(2*itemSize);
- if(p==NULL) {
- *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
- return;
- }
- }
-
- subQuickSort(array, 0, length, itemSize,
- cmp, context, p, (char *)p+itemSize);
-
- if(p!=xw) {
- uprv_free(p);
- }
-}
-
-/* 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);
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-23 11:45:38 +0000