Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(456)

Unified Diff: source/i18n/ucol_wgt.cpp

Issue 845603002: Update ICU to 54.1 step 1 (Closed) Base URL: https://chromium.googlesource.com/chromium/deps/icu.git@master
Patch Set: remove unusued directories Created 5 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « source/i18n/ucol_wgt.h ('k') | source/i18n/ucoleitr.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: source/i18n/ucol_wgt.cpp
diff --git a/source/i18n/ucol_wgt.cpp b/source/i18n/ucol_wgt.cpp
deleted file mode 100644
index 57d49fca7987f8897fd1035a01102ec4758e4b7c..0000000000000000000000000000000000000000
--- a/source/i18n/ucol_wgt.cpp
+++ /dev/null
@@ -1,577 +0,0 @@
-/*
-*******************************************************************************
-*
-* Copyright (C) 1999-2011, International Business Machines
-* Corporation and others. All Rights Reserved.
-*
-*******************************************************************************
-* file name: ucol_wgt.cpp
-* encoding: US-ASCII
-* tab size: 8 (not used)
-* indentation:4
-*
-* created on: 2001mar08
-* created by: Markus W. Scherer
-*
-* This file contains code for allocating n collation element weights
-* between two exclusive limits.
-* It is used only internally by ucol_bld.
-*/
-
-#include "unicode/utypes.h"
-
-#if !UCONFIG_NO_COLLATION
-
-#include "ucol_imp.h"
-#include "ucol_wgt.h"
-#include "cmemory.h"
-#include "uarrsort.h"
-
-#ifdef UCOL_DEBUG
-# include <stdio.h>
-#endif
-
-/* collation element weight allocation -------------------------------------- */
-
-/* helper functions for CE weights */
-
-static inline int32_t
-lengthOfWeight(uint32_t weight) {
- if((weight&0xffffff)==0) {
- return 1;
- } else if((weight&0xffff)==0) {
- return 2;
- } else if((weight&0xff)==0) {
- return 3;
- } else {
- return 4;
- }
-}
-
-static inline uint32_t
-getWeightTrail(uint32_t weight, int32_t length) {
- return (uint32_t)(weight>>(8*(4-length)))&0xff;
-}
-
-static inline uint32_t
-setWeightTrail(uint32_t weight, int32_t length, uint32_t trail) {
- length=8*(4-length);
- return (uint32_t)((weight&(0xffffff00<<length))|(trail<<length));
-}
-
-static inline uint32_t
-getWeightByte(uint32_t weight, int32_t idx) {
- return getWeightTrail(weight, idx); /* same calculation */
-}
-
-static inline uint32_t
-setWeightByte(uint32_t weight, int32_t idx, uint32_t byte) {
- uint32_t mask; /* 0xffffffff except a 00 "hole" for the index-th byte */
-
- idx*=8;
- if(idx<32) {
- mask=((uint32_t)0xffffffff)>>idx;
- } else {
- // Do not use uint32_t>>32 because on some platforms that does not shift at all
- // while we need it to become 0.
- // PowerPC: 0xffffffff>>32 = 0 (wanted)
- // x86: 0xffffffff>>32 = 0xffffffff (not wanted)
- //
- // ANSI C99 6.5.7 Bitwise shift operators:
- // "If the value of the right operand is negative
- // or is greater than or equal to the width of the promoted left operand,
- // the behavior is undefined."
- mask=0;
- }
- idx=32-idx;
- mask|=0xffffff00<<idx;
- return (uint32_t)((weight&mask)|(byte<<idx));
-}
-
-static inline uint32_t
-truncateWeight(uint32_t weight, int32_t length) {
- return (uint32_t)(weight&(0xffffffff<<(8*(4-length))));
-}
-
-static inline uint32_t
-incWeightTrail(uint32_t weight, int32_t length) {
- return (uint32_t)(weight+(1UL<<(8*(4-length))));
-}
-
-static inline uint32_t
-decWeightTrail(uint32_t weight, int32_t length) {
- return (uint32_t)(weight-(1UL<<(8*(4-length))));
-}
-
-static inline uint32_t
-incWeight(uint32_t weight, int32_t length, uint32_t maxByte) {
- uint32_t byte;
-
- for(;;) {
- byte=getWeightByte(weight, length);
- if(byte<maxByte) {
- return setWeightByte(weight, length, byte+1);
- } else {
- /* roll over, set this byte to UCOL_BYTE_FIRST_TAILORED and increment the previous one */
- weight=setWeightByte(weight, length, UCOL_BYTE_FIRST_TAILORED);
- --length;
- }
- }
-}
-
-static inline int32_t
-lengthenRange(WeightRange *range, uint32_t maxByte, uint32_t countBytes) {
- int32_t length;
-
- length=range->length2+1;
- range->start=setWeightTrail(range->start, length, UCOL_BYTE_FIRST_TAILORED);
- range->end=setWeightTrail(range->end, length, maxByte);
- range->count2*=countBytes;
- range->length2=length;
- return length;
-}
-
-/* for uprv_sortArray: sort ranges in weight order */
-static int32_t U_CALLCONV
-compareRanges(const void * /*context*/, const void *left, const void *right) {
- uint32_t l, r;
-
- l=((const WeightRange *)left)->start;
- r=((const WeightRange *)right)->start;
- if(l<r) {
- return -1;
- } else if(l>r) {
- return 1;
- } else {
- return 0;
- }
-}
-
-/*
- * take two CE weights and calculate the
- * possible ranges of weights between the two limits, excluding them
- * for weights with up to 4 bytes there are up to 2*4-1=7 ranges
- */
-static inline int32_t
-getWeightRanges(uint32_t lowerLimit, uint32_t upperLimit,
- uint32_t maxByte, uint32_t countBytes,
- WeightRange ranges[7]) {
- WeightRange lower[5], middle, upper[5]; /* [0] and [1] are not used - this simplifies indexing */
- uint32_t weight, trail;
- int32_t length, lowerLength, upperLength, rangeCount;
-
- /* assume that both lowerLimit & upperLimit are not 0 */
-
- /* get the lengths of the limits */
- lowerLength=lengthOfWeight(lowerLimit);
- upperLength=lengthOfWeight(upperLimit);
-
-#ifdef UCOL_DEBUG
- printf("length of lower limit 0x%08lx is %ld\n", lowerLimit, lowerLength);
- printf("length of upper limit 0x%08lx is %ld\n", upperLimit, upperLength);
-#endif
-
- if(lowerLimit>=upperLimit) {
-#ifdef UCOL_DEBUG
- printf("error: no space between lower & upper limits\n");
-#endif
- return 0;
- }
-
- /* check that neither is a prefix of the other */
- if(lowerLength<upperLength) {
- if(lowerLimit==truncateWeight(upperLimit, lowerLength)) {
-#ifdef UCOL_DEBUG
- printf("error: lower limit 0x%08lx is a prefix of upper limit 0x%08lx\n", lowerLimit, upperLimit);
-#endif
- return 0;
- }
- }
- /* if the upper limit is a prefix of the lower limit then the earlier test lowerLimit>=upperLimit has caught it */
-
- /* reset local variables */
- uprv_memset(lower, 0, sizeof(lower));
- uprv_memset(&middle, 0, sizeof(middle));
- uprv_memset(upper, 0, sizeof(upper));
-
- /*
- * With the limit lengths of 1..4, there are up to 7 ranges for allocation:
- * range minimum length
- * lower[4] 4
- * lower[3] 3
- * lower[2] 2
- * middle 1
- * upper[2] 2
- * upper[3] 3
- * upper[4] 4
- *
- * We are now going to calculate up to 7 ranges.
- * Some of them will typically overlap, so we will then have to merge and eliminate ranges.
- */
- weight=lowerLimit;
- for(length=lowerLength; length>=2; --length) {
- trail=getWeightTrail(weight, length);
- if(trail<maxByte) {
- lower[length].start=incWeightTrail(weight, length);
- lower[length].end=setWeightTrail(weight, length, maxByte);
- lower[length].length=length;
- lower[length].count=maxByte-trail;
- }
- weight=truncateWeight(weight, length-1);
- }
- middle.start=incWeightTrail(weight, 1);
-
- weight=upperLimit;
- for(length=upperLength; length>=2; --length) {
- trail=getWeightTrail(weight, length);
- if(trail>UCOL_BYTE_FIRST_TAILORED) {
- upper[length].start=setWeightTrail(weight, length, UCOL_BYTE_FIRST_TAILORED);
- upper[length].end=decWeightTrail(weight, length);
- upper[length].length=length;
- upper[length].count=trail-UCOL_BYTE_FIRST_TAILORED;
- }
- weight=truncateWeight(weight, length-1);
- }
- middle.end=decWeightTrail(weight, 1);
-
- /* set the middle range */
- middle.length=1;
- if(middle.end>=middle.start) {
- middle.count=(int32_t)((middle.end-middle.start)>>24)+1;
- } else {
- /* eliminate overlaps */
- uint32_t start, end;
-
- /* remove the middle range */
- middle.count=0;
-
- /* reduce or remove the lower ranges that go beyond upperLimit */
- for(length=4; length>=2; --length) {
- if(lower[length].count>0 && upper[length].count>0) {
- start=upper[length].start;
- end=lower[length].end;
-
- if(end>=start || incWeight(end, length, maxByte)==start) {
- /* lower and upper ranges collide or are directly adjacent: merge these two and remove all shorter ranges */
- start=lower[length].start;
- end=lower[length].end=upper[length].end;
- /*
- * merging directly adjacent ranges needs to subtract the 0/1 gaps in between;
- * it may result in a range with count>countBytes
- */
- lower[length].count=
- (int32_t)(getWeightTrail(end, length)-getWeightTrail(start, length)+1+
- countBytes*(getWeightByte(end, length-1)-getWeightByte(start, length-1)));
- upper[length].count=0;
- while(--length>=2) {
- lower[length].count=upper[length].count=0;
- }
- break;
- }
- }
- }
- }
-
-#ifdef UCOL_DEBUG
- /* print ranges */
- for(length=4; length>=2; --length) {
- if(lower[length].count>0) {
- printf("lower[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, lower[length].start, lower[length].end, lower[length].count);
- }
- }
- if(middle.count>0) {
- printf("middle .start=0x%08lx .end=0x%08lx .count=%ld\n", middle.start, middle.end, middle.count);
- }
- for(length=2; length<=4; ++length) {
- if(upper[length].count>0) {
- printf("upper[%ld] .start=0x%08lx .end=0x%08lx .count=%ld\n", length, upper[length].start, upper[length].end, upper[length].count);
- }
- }
-#endif
-
- /* copy the ranges, shortest first, into the result array */
- rangeCount=0;
- if(middle.count>0) {
- uprv_memcpy(ranges, &middle, sizeof(WeightRange));
- rangeCount=1;
- }
- for(length=2; length<=4; ++length) {
- /* copy upper first so that later the middle range is more likely the first one to use */
- if(upper[length].count>0) {
- uprv_memcpy(ranges+rangeCount, upper+length, sizeof(WeightRange));
- ++rangeCount;
- }
- if(lower[length].count>0) {
- uprv_memcpy(ranges+rangeCount, lower+length, sizeof(WeightRange));
- ++rangeCount;
- }
- }
- return rangeCount;
-}
-
-/*
- * call getWeightRanges and then determine heuristically
- * which ranges to use for a given number of weights between (excluding)
- * two limits
- */
-U_CFUNC int32_t
-ucol_allocWeights(uint32_t lowerLimit, uint32_t upperLimit,
- uint32_t n,
- uint32_t maxByte,
- WeightRange ranges[7]) {
- /* number of usable byte values 3..maxByte */
- uint32_t countBytes=maxByte-UCOL_BYTE_FIRST_TAILORED+1;
-
- uint32_t lengthCounts[6]; /* [0] unused, [5] to make index checks unnecessary */
- uint32_t maxCount;
- int32_t i, rangeCount, minLength/*, maxLength*/;
-
- /* countBytes to the power of index */
- uint32_t powers[5];
- /* gcc requires explicit initialization */
- powers[0] = 1;
- powers[1] = countBytes;
- powers[2] = countBytes*countBytes;
- powers[3] = countBytes*countBytes*countBytes;
- powers[4] = countBytes*countBytes*countBytes*countBytes;
-
-#ifdef UCOL_DEBUG
- puts("");
-#endif
-
- rangeCount=getWeightRanges(lowerLimit, upperLimit, maxByte, countBytes, ranges);
- if(rangeCount<=0) {
-#ifdef UCOL_DEBUG
- printf("error: unable to get Weight ranges\n");
-#endif
- return 0;
- }
-
- /* what is the maximum number of weights with these ranges? */
- maxCount=0;
- for(i=0; i<rangeCount; ++i) {
- maxCount+=(uint32_t)ranges[i].count*powers[4-ranges[i].length];
- }
- if(maxCount>=n) {
-#ifdef UCOL_DEBUG
- printf("the maximum number of %lu weights is sufficient for n=%lu\n", maxCount, n);
-#endif
- } else {
-#ifdef UCOL_DEBUG
- printf("error: the maximum number of %lu weights is insufficient for n=%lu\n", maxCount, n);
-#endif
- return 0;
- }
-
- /* set the length2 and count2 fields */
- for(i=0; i<rangeCount; ++i) {
- ranges[i].length2=ranges[i].length;
- ranges[i].count2=(uint32_t)ranges[i].count;
- }
-
- /* try until we find suitably large ranges */
- for(;;) {
- /* get the smallest number of bytes in a range */
- minLength=ranges[0].length2;
-
- /* sum up the number of elements that fit into ranges of each byte length */
- uprv_memset(lengthCounts, 0, sizeof(lengthCounts));
- for(i=0; i<rangeCount; ++i) {
- lengthCounts[ranges[i].length2]+=ranges[i].count2;
- }
-
- /* now try to allocate n elements in the available short ranges */
- if(n<=(lengthCounts[minLength]+lengthCounts[minLength+1])) {
- /* trivial cases, use the first few ranges */
- maxCount=0;
- rangeCount=0;
- do {
- maxCount+=ranges[rangeCount].count2;
- ++rangeCount;
- } while(n>maxCount);
-#ifdef UCOL_DEBUG
- printf("take first %ld ranges\n", rangeCount);
-#endif
- break;
- } else if(n<=ranges[0].count2*countBytes) {
- /* easy case, just make this one range large enough by lengthening it once more, possibly split it */
- uint32_t count1, count2, power_1, power;
-
- /*maxLength=minLength+1;*/
-
- /* calculate how to split the range between maxLength-1 (count1) and maxLength (count2) */
- power_1=powers[minLength-ranges[0].length];
- power=power_1*countBytes;
- count2=(n+power-1)/power;
- count1=ranges[0].count-count2;
-
- /* split the range */
-#ifdef UCOL_DEBUG
- printf("split the first range %ld:%ld\n", count1, count2);
-#endif
- if(count1<1) {
- rangeCount=1;
-
- /* lengthen the entire range to maxLength */
- lengthenRange(ranges, maxByte, countBytes);
- } else {
- /* really split the range */
- uint32_t byte;
-
- /* create a new range with the end and initial and current length of the old one */
- rangeCount=2;
- ranges[1].end=ranges[0].end;
- ranges[1].length=ranges[0].length;
- ranges[1].length2=minLength;
-
- /* set the end of the first range according to count1 */
- i=ranges[0].length;
- byte=getWeightByte(ranges[0].start, i)+count1-1;
-
- /*
- * ranges[0].count and count1 may be >countBytes
- * from merging adjacent ranges;
- * byte>maxByte is possible
- */
- if(byte<=maxByte) {
- ranges[0].end=setWeightByte(ranges[0].start, i, byte);
- } else /* byte>maxByte */ {
- ranges[0].end=setWeightByte(incWeight(ranges[0].start, i-1, maxByte), i, byte-countBytes);
- }
-
- /* set the bytes in the end weight at length+1..length2 to maxByte */
- byte=(maxByte<<24)|(maxByte<<16)|(maxByte<<8)|maxByte; /* this used to be 0xffffffff */
- ranges[0].end=truncateWeight(ranges[0].end, i)|
- ((byte>>(8*i))&(byte<<(8*(4-minLength))));
-
- /* set the start of the second range to immediately follow the end of the first one */
- ranges[1].start=incWeight(ranges[0].end, minLength, maxByte);
-
- /* set the count values (informational) */
- ranges[0].count=count1;
- ranges[1].count=count2;
-
- ranges[0].count2=count1*power_1;
- ranges[1].count2=count2*power_1; /* will be *countBytes when lengthened */
-
- /* lengthen the second range to maxLength */
- lengthenRange(ranges+1, maxByte, countBytes);
- }
- break;
- }
-
- /* no good match, lengthen all minLength ranges and iterate */
-#ifdef UCOL_DEBUG
- printf("lengthen the short ranges from %ld bytes to %ld and iterate\n", minLength, minLength+1);
-#endif
- for(i=0; ranges[i].length2==minLength; ++i) {
- lengthenRange(ranges+i, maxByte, countBytes);
- }
- }
-
- if(rangeCount>1) {
- /* sort the ranges by weight values */
- UErrorCode errorCode=U_ZERO_ERROR;
- uprv_sortArray(ranges, rangeCount, sizeof(WeightRange), compareRanges, NULL, FALSE, &errorCode);
- /* ignore error code: we know that the internal sort function will not fail here */
- }
-
-#ifdef UCOL_DEBUG
- puts("final ranges:");
- for(i=0; i<rangeCount; ++i) {
- printf("ranges[%ld] .start=0x%08lx .end=0x%08lx .length=%ld .length2=%ld .count=%ld .count2=%lu\n",
- i, ranges[i].start, ranges[i].end, ranges[i].length, ranges[i].length2, ranges[i].count, ranges[i].count2);
- }
-#endif
-
- /* set maxByte in ranges[0] for ucol_nextWeight() */
- ranges[0].count=maxByte;
-
- return rangeCount;
-}
-
-/*
- * given a set of ranges calculated by ucol_allocWeights(),
- * iterate through the weights
- */
-U_CFUNC uint32_t
-ucol_nextWeight(WeightRange ranges[], int32_t *pRangeCount) {
- if(*pRangeCount<=0) {
- return 0xffffffff;
- } else {
- uint32_t weight, maxByte;
-
- /* get maxByte from the .count field */
- maxByte=ranges[0].count;
-
- /* get the next weight */
- weight=ranges[0].start;
- if(weight==ranges[0].end) {
- /* this range is finished, remove it and move the following ones up */
- if(--*pRangeCount>0) {
- uprv_memmove(ranges, ranges+1, *pRangeCount*sizeof(WeightRange));
- ranges[0].count=maxByte; /* keep maxByte in ranges[0] */
- }
- } else {
- /* increment the weight for the next value */
- ranges[0].start=incWeight(weight, ranges[0].length2, maxByte);
- }
-
- return weight;
- }
-}
-
-#if 0 // #ifdef UCOL_DEBUG
-
-static void
-testAlloc(uint32_t lowerLimit, uint32_t upperLimit, uint32_t n, UBool enumerate) {
- WeightRange ranges[8];
- int32_t rangeCount;
-
- rangeCount=ucol_allocWeights(lowerLimit, upperLimit, n, ranges);
- if(enumerate) {
- uint32_t weight;
-
- while(n>0) {
- weight=ucol_nextWeight(ranges, &rangeCount);
- if(weight==0xffffffff) {
- printf("error: 0xffffffff with %lu more weights to go\n", n);
- break;
- }
- printf(" 0x%08lx\n", weight);
- --n;
- }
- }
-}
-
-extern int
-main(int argc, const char *argv[]) {
-#if 0
-#endif
- testAlloc(0x364214fc, 0x44b87d23, 5, FALSE);
- testAlloc(0x36421500, 0x44b87d23, 5, FALSE);
- testAlloc(0x36421500, 0x44b87d23, 20, FALSE);
- testAlloc(0x36421500, 0x44b87d23, 13700, FALSE);
- testAlloc(0x36421500, 0x38b87d23, 1, FALSE);
- testAlloc(0x36421500, 0x38b87d23, 20, FALSE);
- testAlloc(0x36421500, 0x38b87d23, 200, TRUE);
- testAlloc(0x36421500, 0x38b87d23, 13700, FALSE);
- testAlloc(0x36421500, 0x37b87d23, 13700, FALSE);
- testAlloc(0x36ef1500, 0x37b87d23, 13700, FALSE);
- testAlloc(0x36421500, 0x36b87d23, 13700, FALSE);
- testAlloc(0x36b87122, 0x36b87d23, 13700, FALSE);
- testAlloc(0x49000000, 0x4a600000, 13700, FALSE);
- testAlloc(0x9fffffff, 0xd0000000, 13700, FALSE);
- testAlloc(0x9fffffff, 0xd0000000, 67400, FALSE);
- testAlloc(0x9fffffff, 0xa0030000, 67400, FALSE);
- testAlloc(0x9fffffff, 0xa0030000, 40000, FALSE);
- testAlloc(0xa0000000, 0xa0030000, 40000, FALSE);
- testAlloc(0xa0031100, 0xa0030000, 40000, FALSE);
-#if 0
-#endif
- return 0;
-}
-
-#endif
-
-#endif /* #if !UCONFIG_NO_COLLATION */
« no previous file with comments | « source/i18n/ucol_wgt.h ('k') | source/i18n/ucoleitr.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698