../deps/icu-small/source/common/umutablecptrie.cpp

Bug Summary

File:	out/../deps/icu-small/source/common/umutablecptrie.cpp
Warning:	line 849, column 38 The right operand of '+' is a garbage value
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name umutablecptrie.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D U_COMMON_IMPLEMENTATION=1 -D U_ATTRIBUTE_DEPRECATED= -D _CRT_SECURE_NO_DEPRECATE= -D U_STATIC_IMPLEMENTATION=1 -D UCONFIG_NO_SERVICE=1 -D U_ENABLE_DYLOAD=0 -D U_HAVE_STD_STRING=1 -D UCONFIG_NO_BREAK_ITERATION=0 -I ../deps/icu-small/source/common -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/x86_64-redhat-linux -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/backward -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -Wno-deprecated-declarations -Wno-strict-aliasing -std=gnu++17 -fdeprecated-macro -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c++ ../deps/icu-small/source/common/umutablecptrie.cpp
1// © 2017 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html

4// umutablecptrie.cpp (inspired by utrie2_builder.cpp)
5// created: 2017dec29 Markus W. Scherer

7// #define UCPTRIE_DEBUG
8#ifdef UCPTRIE_DEBUG
9#   include <stdio.h>
10#endif

12#include "unicode/utypes.h"
13#include "unicode/ucptrie.h"
14#include "unicode/umutablecptrie.h"
15#include "unicode/uobject.h"
16#include "unicode/utf16.h"
17#include "cmemory.h"
18#include "uassert.h"
19#include "ucptrie_impl.h"

21// ICU-20235 In case Microsoft math.h has defined this, undefine it.
22#ifdef OVERFLOW
23#undef OVERFLOW
24#endif

26U_NAMESPACE_BEGINnamespace icu_71 {

28namespace {

30constexpr int32_t MAX_UNICODE = 0x10ffff;

32constexpr int32_t UNICODE_LIMIT = 0x110000;
33constexpr int32_t BMP_LIMIT = 0x10000;
34constexpr int32_t ASCII_LIMIT = 0x80;

36constexpr int32_t I_LIMIT = UNICODE_LIMIT >> UCPTRIE_SHIFT_3;
37constexpr int32_t BMP_I_LIMIT = BMP_LIMIT >> UCPTRIE_SHIFT_3;
38constexpr int32_t ASCII_I_LIMIT = ASCII_LIMIT >> UCPTRIE_SHIFT_3;

40constexpr int32_t SMALL_DATA_BLOCKS_PER_BMP_BLOCK = (1 << (UCPTRIE_FAST_SHIFT - UCPTRIE_SHIFT_3));

42// Flag values for data blocks.
43constexpr uint8_t ALL_SAME = 0;
44constexpr uint8_t MIXED = 1;
45constexpr uint8_t SAME_AS = 2;

47/** Start with allocation of 16k data entries. */
48constexpr int32_t INITIAL_DATA_LENGTH = ((int32_t)1 << 14);

50/** Grow about 8x each time. */
51constexpr int32_t MEDIUM_DATA_LENGTH = ((int32_t)1 << 17);

53/**
* Maximum length of the build-time data array.
* One entry per 0x110000 code points.
*/
57constexpr int32_t MAX_DATA_LENGTH = UNICODE_LIMIT;

59// Flag values for index-3 blocks while compacting/building.
60constexpr uint8_t I3_NULL = 0;
61constexpr uint8_t I3_BMP = 1;
62constexpr uint8_t I3_16 = 2;
63constexpr uint8_t I3_18 = 3;

65constexpr int32_t INDEX_3_18BIT_BLOCK_LENGTH = UCPTRIE_INDEX_3_BLOCK_LENGTH + UCPTRIE_INDEX_3_BLOCK_LENGTH / 8;

67class AllSameBlocks;
68class MixedBlocks;

70class MutableCodePointTrie : public UMemory {
71public:
  MutableCodePointTrie(uint32_t initialValue, uint32_t errorValue, UErrorCode &errorCode);
  MutableCodePointTrie(const MutableCodePointTrie &other, UErrorCode &errorCode);
  MutableCodePointTrie(const MutableCodePointTrie &other) = delete;
  ~MutableCodePointTrie();

  MutableCodePointTrie &operator=(const MutableCodePointTrie &other) = delete;

  static MutableCodePointTrie *fromUCPMap(const UCPMap *map, UErrorCode &errorCode);
  static MutableCodePointTrie *fromUCPTrie(const UCPTrie *trie, UErrorCode &errorCode);

  uint32_t get(UChar32 c) const;
  int32_t getRange(UChar32 start, UCPMapValueFilter *filter, const void *context,
                   uint32_t *pValue) const;

  void set(UChar32 c, uint32_t value, UErrorCode &errorCode);
  void setRange(UChar32 start, UChar32 end, uint32_t value, UErrorCode &errorCode);

  UCPTrie *build(UCPTrieType type, UCPTrieValueWidth valueWidth, UErrorCode &errorCode);

91private:
  void clear();

  bool ensureHighStart(UChar32 c);
  int32_t allocDataBlock(int32_t blockLength);
  int32_t getDataBlock(int32_t i);

  void maskValues(uint32_t mask);
  UChar32 findHighStart() const;
  int32_t compactWholeDataBlocks(int32_t fastILimit, AllSameBlocks &allSameBlocks);
  int32_t compactData(
          int32_t fastILimit, uint32_t *newData, int32_t newDataCapacity,
          int32_t dataNullIndex, MixedBlocks &mixedBlocks, UErrorCode &errorCode);
  int32_t compactIndex(int32_t fastILimit, MixedBlocks &mixedBlocks, UErrorCode &errorCode);
  int32_t compactTrie(int32_t fastILimit, UErrorCode &errorCode);

  uint32_t *index = nullptr;
  int32_t indexCapacity = 0;
  int32_t index3NullOffset = -1;
  uint32_t *data = nullptr;
  int32_t dataCapacity = 0;
  int32_t dataLength = 0;
  int32_t dataNullOffset = -1;

  uint32_t origInitialValue;
  uint32_t initialValue;
  uint32_t errorValue;
  UChar32 highStart;
  uint32_t highValue;
120#ifdef UCPTRIE_DEBUG
121public:
  const char *name;
123#endif
124private:
  /** Temporary array while building the final data. */
  uint16_t *index16 = nullptr;
  uint8_t flags[UNICODE_LIMIT >> UCPTRIE_SHIFT_3];
128};

130MutableCodePointTrie::MutableCodePointTrie(uint32_t iniValue, uint32_t errValue, UErrorCode &errorCode) :
      origInitialValue(iniValue), initialValue(iniValue), errorValue(errValue),
      highStart(0), highValue(initialValue)
133#ifdef UCPTRIE_DEBUG
      , name("open")
135#endif
      {
  if (U_FAILURE(errorCode)) { return; }
  index = (uint32_t *)uprv_mallocuprv_malloc_71(BMP_I_LIMIT * 4);
  data = (uint32_t *)uprv_mallocuprv_malloc_71(INITIAL_DATA_LENGTH * 4);
  if (index == nullptr || data == nullptr) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return;
  }
  indexCapacity = BMP_I_LIMIT;
  dataCapacity = INITIAL_DATA_LENGTH;
146}

148MutableCodePointTrie::MutableCodePointTrie(const MutableCodePointTrie &other, UErrorCode &errorCode) :
      index3NullOffset(other.index3NullOffset),
      dataNullOffset(other.dataNullOffset),
      origInitialValue(other.origInitialValue), initialValue(other.initialValue),
      errorValue(other.errorValue),
      highStart(other.highStart), highValue(other.highValue)
154#ifdef UCPTRIE_DEBUG
      , name("mutable clone")
156#endif
      {
  if (U_FAILURE(errorCode)) { return; }
  int32_t iCapacity = highStart <= BMP_LIMIT ? BMP_I_LIMIT : I_LIMIT;
  index = (uint32_t *)uprv_mallocuprv_malloc_71(iCapacity * 4);
  data = (uint32_t *)uprv_mallocuprv_malloc_71(other.dataCapacity * 4);
  if (index == nullptr || data == nullptr) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return;
  }
  indexCapacity = iCapacity;
  dataCapacity = other.dataCapacity;

  int32_t iLimit = highStart >> UCPTRIE_SHIFT_3;
  uprv_memcpy(flags, other.flags, iLimit)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(flags, other
.flags, iLimit); } while (false);
  uprv_memcpy(index, other.index, iLimit * 4)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(index, other
.index, iLimit * 4); } while (false);
  uprv_memcpy(data, other.data, (size_t)other.dataLength * 4)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(data, other
.data, (size_t)other.dataLength * 4); } while (false);
  dataLength = other.dataLength;
  U_ASSERT(other.index16 == nullptr)(void)0;
175}

177MutableCodePointTrie::~MutableCodePointTrie() {
  uprv_freeuprv_free_71(index);
  uprv_freeuprv_free_71(data);
  uprv_freeuprv_free_71(index16);
181}

183MutableCodePointTrie *MutableCodePointTrie::fromUCPMap(const UCPMap *map, UErrorCode &errorCode) {
  // Use the highValue as the initialValue to reduce the highStart.
  uint32_t errorValue = ucpmap_getucpmap_get_71(map, -1);
  uint32_t initialValue = ucpmap_getucpmap_get_71(map, 0x10ffff);
  LocalPointer<MutableCodePointTrie> mutableTrie(
      new MutableCodePointTrie(initialValue, errorValue, errorCode),
      errorCode);
  if (U_FAILURE(errorCode)) {
      return nullptr;
  }
  UChar32 start = 0, end;
  uint32_t value;
  while ((end = ucpmap_getRangeucpmap_getRange_71(map, start, UCPMAP_RANGE_NORMAL, 0,
                                nullptr, nullptr, &value)) >= 0) {
      if (value != initialValue) {
          if (start == end) {
              mutableTrie->set(start, value, errorCode);
          } else {
              mutableTrie->setRange(start, end, value, errorCode);
          }
      }
      start = end + 1;
  }
  if (U_SUCCESS(errorCode)) {
      return mutableTrie.orphan();
  } else {
      return nullptr;
  }
211}

213MutableCodePointTrie *MutableCodePointTrie::fromUCPTrie(const UCPTrie *trie, UErrorCode &errorCode) {
  // Use the highValue as the initialValue to reduce the highStart.
  uint32_t errorValue;
  uint32_t initialValue;
  switch (trie->valueWidth) {
  case UCPTRIE_VALUE_BITS_16:
      errorValue = trie->data.ptr16[trie->dataLength - UCPTRIE_ERROR_VALUE_NEG_DATA_OFFSET];
      initialValue = trie->data.ptr16[trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET];
      break;
  case UCPTRIE_VALUE_BITS_32:
      errorValue = trie->data.ptr32[trie->dataLength - UCPTRIE_ERROR_VALUE_NEG_DATA_OFFSET];
      initialValue = trie->data.ptr32[trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET];
      break;
  case UCPTRIE_VALUE_BITS_8:
      errorValue = trie->data.ptr8[trie->dataLength - UCPTRIE_ERROR_VALUE_NEG_DATA_OFFSET];
      initialValue = trie->data.ptr8[trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET];
      break;
  default:
      // Unreachable if the trie is properly initialized.
      errorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return nullptr;
  }
  LocalPointer<MutableCodePointTrie> mutableTrie(
      new MutableCodePointTrie(initialValue, errorValue, errorCode),
      errorCode);
  if (U_FAILURE(errorCode)) {
      return nullptr;
  }
  UChar32 start = 0, end;
  uint32_t value;
  while ((end = ucptrie_getRangeucptrie_getRange_71(trie, start, UCPMAP_RANGE_NORMAL, 0,
                                 nullptr, nullptr, &value)) >= 0) {
      if (value != initialValue) {
          if (start == end) {
              mutableTrie->set(start, value, errorCode);
          } else {
              mutableTrie->setRange(start, end, value, errorCode);
          }
      }
      start = end + 1;
  }
  if (U_SUCCESS(errorCode)) {
      return mutableTrie.orphan();
  } else {
      return nullptr;
  }
259}

261void MutableCodePointTrie::clear() {
  index3NullOffset = dataNullOffset = -1;
  dataLength = 0;
  highValue = initialValue = origInitialValue;
  highStart = 0;
  uprv_freeuprv_free_71(index16);
  index16 = nullptr;
268}

270uint32_t MutableCodePointTrie::get(UChar32 c) const {
  if ((uint32_t)c > MAX_UNICODE) {
      return errorValue;
  }
  if (c >= highStart) {
      return highValue;
  }
  int32_t i = c >> UCPTRIE_SHIFT_3;
  if (flags[i] == ALL_SAME) {
      return index[i];
  } else {
      return data[index[i] + (c & UCPTRIE_SMALL_DATA_MASK)];
  }
283}

285inline uint32_t maybeFilterValue(uint32_t value, uint32_t initialValue, uint32_t nullValue,
                               UCPMapValueFilter *filter, const void *context) {
  if (value == initialValue) {
      value = nullValue;
  } else if (filter != nullptr) {
      value = filter(context, value);
  }
  return value;
293}

295UChar32 MutableCodePointTrie::getRange(
      UChar32 start, UCPMapValueFilter *filter, const void *context,
      uint32_t *pValue) const {
  if ((uint32_t)start > MAX_UNICODE) {
      return U_SENTINEL(-1);
  }
  if (start >= highStart) {
      if (pValue != nullptr) {
          uint32_t value = highValue;
          if (filter != nullptr) { value = filter(context, value); }
          *pValue = value;
      }
      return MAX_UNICODE;
  }
  uint32_t nullValue = initialValue;
  if (filter != nullptr) { nullValue = filter(context, nullValue); }
  UChar32 c = start;
  uint32_t trieValue, value;
  bool haveValue = false;
  int32_t i = c >> UCPTRIE_SHIFT_3;
  do {
      if (flags[i] == ALL_SAME) {
          uint32_t trieValue2 = index[i];
          if (haveValue) {
              if (trieValue2 != trieValue) {
                  if (filter == nullptr ||
                          maybeFilterValue(trieValue2, initialValue, nullValue,
                                           filter, context) != value) {
                      return c - 1;
                  }
                  trieValue = trieValue2;  // may or may not help
              }
          } else {
              trieValue = trieValue2;
              value = maybeFilterValue(trieValue2, initialValue, nullValue, filter, context);
              if (pValue != nullptr) { *pValue = value; }
              haveValue = true;
          }
          c = (c + UCPTRIE_SMALL_DATA_BLOCK_LENGTH) & ~UCPTRIE_SMALL_DATA_MASK;
      } else /* MIXED */ {
          int32_t di = index[i] + (c & UCPTRIE_SMALL_DATA_MASK);
          uint32_t trieValue2 = data[di];
          if (haveValue) {
              if (trieValue2 != trieValue) {
                  if (filter == nullptr ||
                          maybeFilterValue(trieValue2, initialValue, nullValue,
                                           filter, context) != value) {
                      return c - 1;
                  }
                  trieValue = trieValue2;  // may or may not help
              }
          } else {
              trieValue = trieValue2;
              value = maybeFilterValue(trieValue2, initialValue, nullValue, filter, context);
              if (pValue != nullptr) { *pValue = value; }
              haveValue = true;
          }
          while ((++c & UCPTRIE_SMALL_DATA_MASK) != 0) {
              trieValue2 = data[++di];
              if (trieValue2 != trieValue) {
                  if (filter == nullptr ||
                          maybeFilterValue(trieValue2, initialValue, nullValue,
                                           filter, context) != value) {
                      return c - 1;
                  }
              }
              trieValue = trieValue2;  // may or may not help
          }
      }
      ++i;
  } while (c < highStart);
  U_ASSERT(haveValue)(void)0;
  if (maybeFilterValue(highValue, initialValue, nullValue,
                       filter, context) != value) {
      return c - 1;
  } else {
      return MAX_UNICODE;
  }
373}

375void
376writeBlock(uint32_t *block, uint32_t value) {
  uint32_t *limit = block + UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
  while (block < limit) {
      *block++ = value;
  }
381}

383bool MutableCodePointTrie::ensureHighStart(UChar32 c) {
  if (c >= highStart) {
      // Round up to a UCPTRIE_CP_PER_INDEX_2_ENTRY boundary to simplify compaction.
      c = (c + UCPTRIE_CP_PER_INDEX_2_ENTRY) & ~(UCPTRIE_CP_PER_INDEX_2_ENTRY - 1);
      int32_t i = highStart >> UCPTRIE_SHIFT_3;
      int32_t iLimit = c >> UCPTRIE_SHIFT_3;
      if (iLimit > indexCapacity) {
          uint32_t *newIndex = (uint32_t *)uprv_mallocuprv_malloc_71(I_LIMIT * 4);
          if (newIndex == nullptr) { return false; }
          uprv_memcpy(newIndex, index, i * 4)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(newIndex,
 index, i * 4); } while (false);
          uprv_freeuprv_free_71(index);
          index = newIndex;
          indexCapacity = I_LIMIT;
      }
      do {
          flags[i] = ALL_SAME;
          index[i] = initialValue;
      } while(++i < iLimit);
      highStart = c;
  }
  return true;
404}

406int32_t MutableCodePointTrie::allocDataBlock(int32_t blockLength) {
  int32_t newBlock = dataLength;
  int32_t newTop = newBlock + blockLength;
  if (newTop > dataCapacity) {
      int32_t capacity;
      if (dataCapacity < MEDIUM_DATA_LENGTH) {
          capacity = MEDIUM_DATA_LENGTH;
      } else if (dataCapacity < MAX_DATA_LENGTH) {
          capacity = MAX_DATA_LENGTH;
      } else {
          // Should never occur.
          // Either MAX_DATA_LENGTH is incorrect,
          // or the code writes more values than should be possible.
          return -1;
      }
      uint32_t *newData = (uint32_t *)uprv_mallocuprv_malloc_71(capacity * 4);
      if (newData == nullptr) {
          return -1;
      }
      uprv_memcpy(newData, data, (size_t)dataLength * 4)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(newData, data
, (size_t)dataLength * 4); } while (false);
      uprv_freeuprv_free_71(data);
      data = newData;
      dataCapacity = capacity;
  }
  dataLength = newTop;
  return newBlock;
432}

434/**
* No error checking for illegal arguments.
*
* @return -1 if no new data block available (out of memory in data array)
* @internal
*/
440int32_t MutableCodePointTrie::getDataBlock(int32_t i) {
  if (flags[i] == MIXED) {
      return index[i];
  }
  if (i < BMP_I_LIMIT) {
      int32_t newBlock = allocDataBlock(UCPTRIE_FAST_DATA_BLOCK_LENGTH);
      if (newBlock < 0) { return newBlock; }
      int32_t iStart = i & ~(SMALL_DATA_BLOCKS_PER_BMP_BLOCK -1);
      int32_t iLimit = iStart + SMALL_DATA_BLOCKS_PER_BMP_BLOCK;
      do {
          U_ASSERT(flags[iStart] == ALL_SAME)(void)0;
          writeBlock(data + newBlock, index[iStart]);
          flags[iStart] = MIXED;
          index[iStart++] = newBlock;
          newBlock += UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
      } while (iStart < iLimit);
      return index[i];
  } else {
      int32_t newBlock = allocDataBlock(UCPTRIE_SMALL_DATA_BLOCK_LENGTH);
      if (newBlock < 0) { return newBlock; }
      writeBlock(data + newBlock, index[i]);
      flags[i] = MIXED;
      index[i] = newBlock;
      return newBlock;
  }
465}

467void MutableCodePointTrie::set(UChar32 c, uint32_t value, UErrorCode &errorCode) {
  if (U_FAILURE(errorCode)) {
      return;
  }
  if ((uint32_t)c > MAX_UNICODE) {
      errorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return;
  }

  int32_t block;
  if (!ensureHighStart(c) || (block = getDataBlock(c >> UCPTRIE_SHIFT_3)) < 0) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return;
  }

  data[block + (c & UCPTRIE_SMALL_DATA_MASK)] = value;
483}

485void
486fillBlock(uint32_t *block, UChar32 start, UChar32 limit, uint32_t value) {
  uint32_t *pLimit = block + limit;
  block += start;
  while (block < pLimit) {
      *block++ = value;
  }
492}

494void MutableCodePointTrie::setRange(UChar32 start, UChar32 end, uint32_t value, UErrorCode &errorCode) {
  if (U_FAILURE(errorCode)) {
      return;
  }
  if ((uint32_t)start > MAX_UNICODE || (uint32_t)end > MAX_UNICODE || start > end) {
      errorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return;
  }
  if (!ensureHighStart(end)) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return;
  }

  UChar32 limit = end + 1;
  if (start & UCPTRIE_SMALL_DATA_MASK) {
      // Set partial block at [start..following block boundary[.
      int32_t block = getDataBlock(start >> UCPTRIE_SHIFT_3);
      if (block < 0) {
          errorCode = U_MEMORY_ALLOCATION_ERROR;
          return;
      }

      UChar32 nextStart = (start + UCPTRIE_SMALL_DATA_MASK) & ~UCPTRIE_SMALL_DATA_MASK;
      if (nextStart <= limit) {
          fillBlock(data + block, start & UCPTRIE_SMALL_DATA_MASK, UCPTRIE_SMALL_DATA_BLOCK_LENGTH,
                    value);
          start = nextStart;
      } else {
          fillBlock(data + block, start & UCPTRIE_SMALL_DATA_MASK, limit & UCPTRIE_SMALL_DATA_MASK,
                    value);
          return;
      }
  }

  // Number of positions in the last, partial block.
  int32_t rest = limit & UCPTRIE_SMALL_DATA_MASK;

  // Round down limit to a block boundary.
  limit &= ~UCPTRIE_SMALL_DATA_MASK;

  // Iterate over all-value blocks.
  while (start < limit) {
      int32_t i = start >> UCPTRIE_SHIFT_3;
      if (flags[i] == ALL_SAME) {
          index[i] = value;
      } else /* MIXED */ {
          fillBlock(data + index[i], 0, UCPTRIE_SMALL_DATA_BLOCK_LENGTH, value);
      }
      start += UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
  }

  if (rest > 0) {
      // Set partial block at [last block boundary..limit[.
      int32_t block = getDataBlock(start >> UCPTRIE_SHIFT_3);
      if (block < 0) {
          errorCode = U_MEMORY_ALLOCATION_ERROR;
          return;
      }

      fillBlock(data + block, 0, rest, value);
  }
555}

557/* compaction --------------------------------------------------------------- */

559void MutableCodePointTrie::maskValues(uint32_t mask) {
  initialValue &= mask;
  errorValue &= mask;
  highValue &= mask;
  int32_t iLimit = highStart >> UCPTRIE_SHIFT_3;
  for (int32_t i = 0; i < iLimit; ++i) {
      if (flags[i] == ALL_SAME) {
          index[i] &= mask;
      }
  }
  for (int32_t i = 0; i < dataLength; ++i) {
      data[i] &= mask;
  }
572}

574template<typename UIntA, typename UIntB>
575bool equalBlocks(const UIntA *s, const UIntB *t, int32_t length) {
  while (length > 0 && *s == *t) {
      ++s;
      ++t;
      --length;
  }
  return length == 0;
582}

584bool allValuesSameAs(const uint32_t *p, int32_t length, uint32_t value) {
  const uint32_t *pLimit = p + length;
  while (p < pLimit && *p == value) { ++p; }
  return p == pLimit;
588}

590/** Search for an identical block. */
591int32_t findSameBlock(const uint16_t *p, int32_t pStart, int32_t length,
                    const uint16_t *q, int32_t qStart, int32_t blockLength) {
  // Ensure that we do not even partially get past length.
  length -= blockLength;

  q += qStart;
  while (pStart <= length) {
      if (equalBlocks(p + pStart, q, blockLength)) {
          return pStart;
      }
      ++pStart;
  }
  return -1;
604}

606int32_t findAllSameBlock(const uint32_t *p, int32_t start, int32_t limit,
                       uint32_t value, int32_t blockLength) {
  // Ensure that we do not even partially get past limit.
  limit -= blockLength;

  for (int32_t block = start; block <= limit; ++block) {
      if (p[block] == value) {
          for (int32_t i = 1;; ++i) {
              if (i == blockLength) {
                  return block;
              }
              if (p[block + i] != value) {
                  block += i;
                  break;
              }
          }
      }
  }
  return -1;
625}

627/**
* Look for maximum overlap of the beginning of the other block
* with the previous, adjacent block.
*/
631template<typename UIntA, typename UIntB>
632int32_t getOverlap(const UIntA *p, int32_t length,
                 const UIntB *q, int32_t qStart, int32_t blockLength) {
  int32_t overlap = blockLength - 1;
  U_ASSERT(overlap <= length)(void)0;
  q += qStart;
  while (overlap > 0 && !equalBlocks(p + (length - overlap), q, overlap)) {
      --overlap;
  }
  return overlap;
641}

643int32_t getAllSameOverlap(const uint32_t *p, int32_t length, uint32_t value,
                        int32_t blockLength) {
  int32_t min = length - (blockLength - 1);
  int32_t i = length;
  while (min < i && p[i - 1] == value) { --i; }
  return length - i;
649}

651bool isStartOfSomeFastBlock(uint32_t dataOffset, const uint32_t index[], int32_t fastILimit) {
  for (int32_t i = 0; i < fastILimit; i += SMALL_DATA_BLOCKS_PER_BMP_BLOCK) {
      if (index[i] == dataOffset) {
          return true;
      }
  }
  return false;
658}

660/**
* Finds the start of the last range in the trie by enumerating backward.
* Indexes for code points higher than this will be omitted.
*/
664UChar32 MutableCodePointTrie::findHighStart() const {
  int32_t i = highStart >> UCPTRIE_SHIFT_3;
  while (i > 0) {
      bool match;
      if (flags[--i] == ALL_SAME) {
          match = index[i] == highValue;
      } else /* MIXED */ {
          const uint32_t *p = data + index[i];
          for (int32_t j = 0;; ++j) {
              if (j == UCPTRIE_SMALL_DATA_BLOCK_LENGTH) {
                  match = true;
                  break;
              }
              if (p[j] != highValue) {
                  match = false;
                  break;
              }
          }
      }
      if (!match) {
          return (i + 1) << UCPTRIE_SHIFT_3;
      }
  }
  return 0;
688}

690class AllSameBlocks {
691public:
  static constexpr int32_t NEW_UNIQUE = -1;
  static constexpr int32_t OVERFLOW = -2;

  AllSameBlocks() : length(0), mostRecent(-1) {}

  int32_t findOrAdd(int32_t index, int32_t count, uint32_t value) {
      if (mostRecent >= 0 && values[mostRecent] == value) {
          refCounts[mostRecent] += count;
          return indexes[mostRecent];
      }
      for (int32_t i = 0; i < length; ++i) {
          if (values[i] == value) {
              mostRecent = i;
              refCounts[i] += count;
              return indexes[i];
          }
      }
      if (length == CAPACITY) {
          return OVERFLOW;
      }
      mostRecent = length;
      indexes[length] = index;
      values[length] = value;
      refCounts[length++] = count;
      return NEW_UNIQUE;
  }

  /** Replaces the block which has the lowest reference count. */
  void add(int32_t index, int32_t count, uint32_t value) {
      U_ASSERT(length == CAPACITY)(void)0;
      int32_t least = -1;
      int32_t leastCount = I_LIMIT;
      for (int32_t i = 0; i < length; ++i) {
          U_ASSERT(values[i] != value)(void)0;
          if (refCounts[i] < leastCount) {
              least = i;
              leastCount = refCounts[i];
          }
      }
      U_ASSERT(least >= 0)(void)0;
      mostRecent = least;
      indexes[least] = index;
      values[least] = value;
      refCounts[least] = count;
  }

  int32_t findMostUsed() const {
      if (length == 0) { return -1; }
      int32_t max = -1;
      int32_t maxCount = 0;
      for (int32_t i = 0; i < length; ++i) {
          if (refCounts[i] > maxCount) {
              max = i;
              maxCount = refCounts[i];
          }
      }
      return indexes[max];
  }

751private:
  static constexpr int32_t CAPACITY = 32;

  int32_t length;
  int32_t mostRecent;

  int32_t indexes[CAPACITY];
  uint32_t values[CAPACITY];
  int32_t refCounts[CAPACITY];
760};

762// Custom hash table for mixed-value blocks to be found anywhere in the
763// compacted data or index so far.
764class MixedBlocks {
765public:
  MixedBlocks() {}
  ~MixedBlocks() {
      uprv_freeuprv_free_71(table);
  }

  bool init(int32_t maxLength, int32_t newBlockLength) {
      // We store actual data indexes + 1 to reserve 0 for empty entries.
      int32_t maxDataIndex = maxLength - newBlockLength + 1;
      int32_t newLength;
      if (maxDataIndex <= 0xfff) {  // 4k
          newLength = 6007;
          shift = 12;
          mask = 0xfff;
      } else if (maxDataIndex <= 0x7fff) {  // 32k
          newLength = 50021;
          shift = 15;
          mask = 0x7fff;
      } else if (maxDataIndex <= 0x1ffff) {  // 128k
          newLength = 200003;
          shift = 17;
          mask = 0x1ffff;
      } else {
          // maxDataIndex up to around MAX_DATA_LENGTH, ca. 1.1M
          newLength = 1500007;
          shift = 21;
          mask = 0x1fffff;
      }
      if (newLength > capacity) {
          uprv_freeuprv_free_71(table);
          table = (uint32_t *)uprv_mallocuprv_malloc_71(newLength * 4);
          if (table == nullptr) {
              return false;
          }
          capacity = newLength;
      }
      length = newLength;
      uprv_memset(table, 0, length * 4):: memset(table, 0, length * 4);

      blockLength = newBlockLength;
      return true;
  }

  template<typename UInt>
  void extend(const UInt *data, int32_t minStart, int32_t prevDataLength, int32_t newDataLength) {
      int32_t start = prevDataLength - blockLength;
      if (start14.1
'start' is < 'minStart'
 >= minStart) {
15
←
Taking false branch→
          ++start;  // Skip the last block that we added last time.
      } else {
          start = minStart;  // Begin with the first full block.
      }
      for (int32_t end = newDataLength - blockLength; start <= end; ++start) {
16
←
Assuming 'start' is <= 'end'→
17
←
Loop condition is true.  Entering loop body→
          uint32_t hashCode = makeHashCode(data, start);
18
←
Calling 'MixedBlocks::makeHashCode'→
          addEntry(data, start, hashCode, start);
      }
  }

  template<typename UIntA, typename UIntB>
  int32_t findBlock(const UIntA *data, const UIntB *blockData, int32_t blockStart) const {
      uint32_t hashCode = makeHashCode(blockData, blockStart);
      int32_t entryIndex = findEntry(data, blockData, blockStart, hashCode);
      if (entryIndex >= 0) {
          return (table[entryIndex] & mask) - 1;
      } else {
          return -1;
      }
  }

  int32_t findAllSameBlock(const uint32_t *data, uint32_t blockValue) const {
      uint32_t hashCode = makeHashCode(blockValue);
      int32_t entryIndex = findEntry(data, blockValue, hashCode);
      if (entryIndex >= 0) {
          return (table[entryIndex] & mask) - 1;
      } else {
          return -1;
      }
  }

843private:
  template<typename UInt>
  uint32_t makeHashCode(const UInt *blockData, int32_t blockStart) const {
      int32_t blockLimit = blockStart + blockLength;
      uint32_t hashCode = blockData[blockStart++];
      do {
          hashCode = 37 * hashCode + blockData[blockStart++];
19
←
The right operand of '+' is a garbage value
      } while (blockStart < blockLimit);
      return hashCode;
  }

  uint32_t makeHashCode(uint32_t blockValue) const {
      uint32_t hashCode = blockValue;
      for (int32_t i = 1; i < blockLength; ++i) {
          hashCode = 37 * hashCode + blockValue;
      }
      return hashCode;
  }

  template<typename UInt>
  void addEntry(const UInt *data, int32_t blockStart, uint32_t hashCode, int32_t dataIndex) {
      U_ASSERT(0 <= dataIndex && dataIndex < (int32_t)mask)(void)0;
      int32_t entryIndex = findEntry(data, data, blockStart, hashCode);
      if (entryIndex < 0) {
          table[~entryIndex] = (hashCode << shift) | (dataIndex + 1);
      }
  }

  template<typename UIntA, typename UIntB>
  int32_t findEntry(const UIntA *data, const UIntB *blockData, int32_t blockStart,
                    uint32_t hashCode) const {
      uint32_t shiftedHashCode = hashCode << shift;
      int32_t initialEntryIndex = (hashCode % (length - 1)) + 1;  // 1..length-1
      for (int32_t entryIndex = initialEntryIndex;;) {
          uint32_t entry = table[entryIndex];
          if (entry == 0) {
              return ~entryIndex;
          }
          if ((entry & ~mask) == shiftedHashCode) {
              int32_t dataIndex = (entry & mask) - 1;
              if (equalBlocks(data + dataIndex, blockData + blockStart, blockLength)) {
                  return entryIndex;
              }
          }
          entryIndex = nextIndex(initialEntryIndex, entryIndex);
      }
  }

  int32_t findEntry(const uint32_t *data, uint32_t blockValue, uint32_t hashCode) const {
      uint32_t shiftedHashCode = hashCode << shift;
      int32_t initialEntryIndex = (hashCode % (length - 1)) + 1;  // 1..length-1
      for (int32_t entryIndex = initialEntryIndex;;) {
          uint32_t entry = table[entryIndex];
          if (entry == 0) {
              return ~entryIndex;
          }
          if ((entry & ~mask) == shiftedHashCode) {
              int32_t dataIndex = (entry & mask) - 1;
              if (allValuesSameAs(data + dataIndex, blockLength, blockValue)) {
                  return entryIndex;
              }
          }
          entryIndex = nextIndex(initialEntryIndex, entryIndex);
      }
  }

  inline int32_t nextIndex(int32_t initialEntryIndex, int32_t entryIndex) const {
      // U_ASSERT(0 < initialEntryIndex && initialEntryIndex < length);
      return (entryIndex + initialEntryIndex) % length;
  }

  // Hash table.
  // The length is a prime number, larger than the maximum data length.
  // The "shift" lower bits store a data index + 1.
  // The remaining upper bits store a partial hashCode of the block data values.
  uint32_t *table = nullptr;
  int32_t capacity = 0;
  int32_t length = 0;
  int32_t shift = 0;
  uint32_t mask = 0;

  int32_t blockLength = 0;
925};

927int32_t MutableCodePointTrie::compactWholeDataBlocks(int32_t fastILimit, AllSameBlocks &allSameBlocks) {
928#ifdef UCPTRIE_DEBUG
  bool overflow = false;
930#endif

  // ASCII data will be stored as a linear table, even if the following code
  // does not yet count it that way.
  int32_t newDataCapacity = ASCII_LIMIT;
  // Add room for a small data null block in case it would match the start of
  // a fast data block where dataNullOffset must not be set in that case.
  newDataCapacity += UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
  // Add room for special values (errorValue, highValue) and padding.
  newDataCapacity += 4;
  int32_t iLimit = highStart >> UCPTRIE_SHIFT_3;
  int32_t blockLength = UCPTRIE_FAST_DATA_BLOCK_LENGTH;
  int32_t inc = SMALL_DATA_BLOCKS_PER_BMP_BLOCK;
  for (int32_t i = 0; i < iLimit; i += inc) {
      if (i == fastILimit) {
          blockLength = UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
          inc = 1;
      }
      uint32_t value = index[i];
      if (flags[i] == MIXED) {
          // Really mixed?
          const uint32_t *p = data + value;
          value = *p;
          if (allValuesSameAs(p + 1, blockLength - 1, value)) {
              flags[i] = ALL_SAME;
              index[i] = value;
              // Fall through to ALL_SAME handling.
          } else {
              newDataCapacity += blockLength;
              continue;
          }
      } else {
          U_ASSERT(flags[i] == ALL_SAME)(void)0;
          if (inc > 1) {
              // Do all of the fast-range data block's ALL_SAME parts have the same value?
              bool allSame = true;
              int32_t next_i = i + inc;
              for (int32_t j = i + 1; j < next_i; ++j) {
                  U_ASSERT(flags[j] == ALL_SAME)(void)0;
                  if (index[j] != value) {
                      allSame = false;
                      break;
                  }
              }
              if (!allSame) {
                  // Turn it into a MIXED block.
                  if (getDataBlock(i) < 0) {
                      return -1;
                  }
                  newDataCapacity += blockLength;
                  continue;
              }
          }
      }
      // Is there another ALL_SAME block with the same value?
      int32_t other = allSameBlocks.findOrAdd(i, inc, value);
      if (other == AllSameBlocks::OVERFLOW) {
          // The fixed-size array overflowed. Slow check for a duplicate block.
988#ifdef UCPTRIE_DEBUG
          if (!overflow) {
              puts("UCPTrie AllSameBlocks overflow");
              overflow = true;
          }
993#endif
          int32_t jInc = SMALL_DATA_BLOCKS_PER_BMP_BLOCK;
          for (int32_t j = 0;; j += jInc) {
              if (j == i) {
                  allSameBlocks.add(i, inc, value);
                  break;
              }
              if (j == fastILimit) {
                  jInc = 1;
              }
              if (flags[j] == ALL_SAME && index[j] == value) {
                  allSameBlocks.add(j, jInc + inc, value);
                  other = j;
                  break;
                  // We could keep counting blocks with the same value
                  // before we add the first one, which may improve compaction in rare cases,
                  // but it would make it slower.
              }
          }
      }
      if (other >= 0) {
          flags[i] = SAME_AS;
          index[i] = other;
      } else {
          // New unique same-value block.
          newDataCapacity += blockLength;
      }
  }
  return newDataCapacity;
1022}

1024#ifdef UCPTRIE_DEBUG
1025#   define DEBUG_DO(expr) expr
1026#else
1027#   define DEBUG_DO(expr)
1028#endif

1030#ifdef UCPTRIE_DEBUG
1031// Braille symbols: U+28xx = UTF-8 E2 A0 80..E2 A3 BF
1032int32_t appendValue(char s[], int32_t length, uint32_t value) {
  value ^= value >> 16;
  value ^= value >> 8;
  s[length] = 0xE2;
  s[length + 1] = (char)(0xA0 + ((value >> 6) & 3));
  s[length + 2] = (char)(0x80 + (value & 0x3F));
  return length + 3;
1039}

1041void printBlock(const uint32_t *block, int32_t blockLength, uint32_t value,
              UChar32 start, int32_t overlap, uint32_t initialValue) {
  char s[UCPTRIE_FAST_DATA_BLOCK_LENGTH * 3 + 3];
  int32_t length = 0;
  int32_t i;
  for (i = 0; i < overlap; ++i) {
      length = appendValue(s, length, 0);  // Braille blank
  }
  s[length++] = '|';
  for (; i < blockLength; ++i) {
      if (block != nullptr) {
          value = block[i];
      }
      if (value == initialValue) {
          value = 0x40;  // Braille lower left dot
      }
      length = appendValue(s, length, value);
  }
  s[length] = 0;
  start += overlap;
  if (start <= 0xffff) {
      printf("    %04lX  %s|\n", (long)start, s);
  } else if (start <= 0xfffff) {
      printf("   %5lX  %s|\n", (long)start, s);
  } else {
      printf("  %6lX  %s|\n", (long)start, s);
  }
1068}
1069#endif

1071/**
* Compacts a build-time trie.
*
* The compaction
* - removes blocks that are identical with earlier ones
* - overlaps each new non-duplicate block as much as possible with the previously-written one
* - works with fast-range data blocks whose length is a multiple of that of
*   higher-code-point data blocks
*
* It does not try to find an optimal order of writing, deduplicating, and overlapping blocks.
*/
1082int32_t MutableCodePointTrie::compactData(
      int32_t fastILimit, uint32_t *newData, int32_t newDataCapacity,
      int32_t dataNullIndex, MixedBlocks &mixedBlocks, UErrorCode &errorCode) {
1085#ifdef UCPTRIE_DEBUG
  int32_t countSame=0, sumOverlaps=0;
  bool printData = dataLength == 29088 /* line.brk */ ||
      // dataLength == 30048 /* CanonIterData */ ||
      dataLength == 50400 /* zh.txt~stroke */;
1090#endif

  // The linear ASCII data has been copied into newData already.
  int32_t newDataLength = 0;
  for (int32_t i = 0; newDataLength < ASCII_LIMIT;
          newDataLength += UCPTRIE_FAST_DATA_BLOCK_LENGTH, i += SMALL_DATA_BLOCKS_PER_BMP_BLOCK) {
      index[i] = newDataLength;
1097#ifdef UCPTRIE_DEBUG
      if (printData) {
          printBlock(newData + newDataLength, UCPTRIE_FAST_DATA_BLOCK_LENGTH, 0, newDataLength, 0, initialValue);
      }
1101#endif
  }

  int32_t blockLength = UCPTRIE_FAST_DATA_BLOCK_LENGTH;
  if (!mixedBlocks.init(newDataCapacity, blockLength)) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  mixedBlocks.extend(newData, 0, 0, newDataLength);

  int32_t iLimit = highStart >> UCPTRIE_SHIFT_3;
  int32_t inc = SMALL_DATA_BLOCKS_PER_BMP_BLOCK;
  int32_t fastLength = 0;
  for (int32_t i = ASCII_I_LIMIT; i < iLimit; i += inc) {
      if (i == fastILimit) {
          blockLength = UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
          inc = 1;
          fastLength = newDataLength;
          if (!mixedBlocks.init(newDataCapacity, blockLength)) {
              errorCode = U_MEMORY_ALLOCATION_ERROR;
              return 0;
          }
          mixedBlocks.extend(newData, 0, 0, newDataLength);
      }
      if (flags[i] == ALL_SAME) {
          uint32_t value = index[i];
          // Find an earlier part of the data array of length blockLength
          // that is filled with this value.
          int32_t n = mixedBlocks.findAllSameBlock(newData, value);
          // If we find a match, and the current block is the data null block,
          // and it is not a fast block but matches the start of a fast block,
          // then we need to continue looking.
          // This is because this small block is shorter than the fast block,
          // and not all of the rest of the fast block is filled with this value.
          // Otherwise trie.getRange() would detect that the fast block starts at
          // dataNullOffset and assume incorrectly that it is filled with the null value.
          while (n >= 0 && i == dataNullIndex && i >= fastILimit && n < fastLength &&
                  isStartOfSomeFastBlock(n, index, fastILimit)) {
              n = findAllSameBlock(newData, n + 1, newDataLength, value, blockLength);
          }
          if (n >= 0) {
              DEBUG_DO(++countSame);
              index[i] = n;
          } else {
              n = getAllSameOverlap(newData, newDataLength, value, blockLength);
              DEBUG_DO(sumOverlaps += n);
1147#ifdef UCPTRIE_DEBUG
              if (printData) {
                  printBlock(nullptr, blockLength, value, i << UCPTRIE_SHIFT_3, n, initialValue);
              }
1151#endif
              index[i] = newDataLength - n;
              int32_t prevDataLength = newDataLength;
              while (n < blockLength) {
                  newData[newDataLength++] = value;
                  ++n;
              }
              mixedBlocks.extend(newData, 0, prevDataLength, newDataLength);
          }
      } else if (flags[i] == MIXED) {
          const uint32_t *block = data + index[i];
          int32_t n = mixedBlocks.findBlock(newData, block, 0);
          if (n >= 0) {
              DEBUG_DO(++countSame);
              index[i] = n;
          } else {
              n = getOverlap(newData, newDataLength, block, 0, blockLength);
              DEBUG_DO(sumOverlaps += n);
1169#ifdef UCPTRIE_DEBUG
              if (printData) {
                  printBlock(block, blockLength, 0, i << UCPTRIE_SHIFT_3, n, initialValue);
              }
1173#endif
              index[i] = newDataLength - n;
              int32_t prevDataLength = newDataLength;
              while (n < blockLength) {
                  newData[newDataLength++] = block[n++];
              }
              mixedBlocks.extend(newData, 0, prevDataLength, newDataLength);
          }
      } else /* SAME_AS */ {
          uint32_t j = index[i];
          index[i] = index[j];
      }
  }

1187#ifdef UCPTRIE_DEBUG
  /* we saved some space */
  printf("compacting UCPTrie: count of 32-bit data words %lu->%lu  countSame=%ld  sumOverlaps=%ld\n",
          (long)dataLength, (long)newDataLength, (long)countSame, (long)sumOverlaps);
1191#endif
  return newDataLength;
1193}

1195int32_t MutableCodePointTrie::compactIndex(int32_t fastILimit, MixedBlocks &mixedBlocks,
                                         UErrorCode &errorCode) {
  int32_t fastIndexLength = fastILimit >> (UCPTRIE_FAST_SHIFT - UCPTRIE_SHIFT_3);
  if ((highStart >> UCPTRIE_FAST_SHIFT) <= fastIndexLength) {
1
Assuming the condition is false→
2
←
Taking false branch→
      // Only the linear fast index, no multi-stage index tables.
      index3NullOffset = UCPTRIE_NO_INDEX3_NULL_OFFSET;
      return fastIndexLength;
  }

  // Condense the fast index table.
  // Also, does it contain an index-3 block with all dataNullOffset?
  uint16_t fastIndex[UCPTRIE_BMP_INDEX_LENGTH];  // fastIndexLength
  int32_t i3FirstNull = -1;
  for (int32_t i = 0, j = 0; i < fastILimit; ++j) {
3
←
Assuming 'i' is < 'fastILimit'→
4
←
Loop condition is true.  Entering loop body→
11
←
Assuming 'i' is >= 'fastILimit'→
12
←
Loop condition is false. Execution continues on line 1230→
      uint32_t i3 = index[i];
      fastIndex[j] = (uint16_t)i3;
      if (i3 == (uint32_t)dataNullOffset) {
5
←
Assuming 'i3' is not equal to field 'dataNullOffset'→
6
←
Taking false branch→
          if (i3FirstNull < 0) {
              i3FirstNull = j;
          } else if (index3NullOffset < 0 &&
                  (j - i3FirstNull + 1) == UCPTRIE_INDEX_3_BLOCK_LENGTH) {
              index3NullOffset = i3FirstNull;
          }
      } else {
          i3FirstNull = -1;
      }
      // Set the index entries that compactData() skipped.
      // Needed when the multi-stage index covers the fast index range as well.
      int32_t iNext = i + SMALL_DATA_BLOCKS_PER_BMP_BLOCK;
      while (++i < iNext) {
7
←
Loop condition is true.  Entering loop body→
8
←
Loop condition is true.  Entering loop body→
9
←
Loop condition is true.  Entering loop body→
10
←
Loop condition is false. Execution continues on line 1208→
          i3 += UCPTRIE_SMALL_DATA_BLOCK_LENGTH;
          index[i] = i3;
      }
  }

  if (!mixedBlocks.init(fastIndexLength, UCPTRIE_INDEX_3_BLOCK_LENGTH)) {
13
←
Taking false branch→
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  mixedBlocks.extend(fastIndex, 0, 0, fastIndexLength);
14
←
Calling 'MixedBlocks::extend'→

  // Examine index-3 blocks. For each determine one of:
  // - same as the index-3 null block
  // - same as a fast-index block
  // - 16-bit indexes
  // - 18-bit indexes
  // We store this in the first flags entry for the index-3 block.
  //
  // Also determine an upper limit for the index-3 table length.
  int32_t index3Capacity = 0;
  i3FirstNull = index3NullOffset;
  bool hasLongI3Blocks = false;
  // If the fast index covers the whole BMP, then
  // the multi-stage index is only for supplementary code points.
  // Otherwise, the multi-stage index covers all of Unicode.
  int32_t iStart = fastILimit < BMP_I_LIMIT ? 0 : BMP_I_LIMIT;
  int32_t iLimit = highStart >> UCPTRIE_SHIFT_3;
  for (int32_t i = iStart; i < iLimit;) {
      int32_t j = i;
      int32_t jLimit = i + UCPTRIE_INDEX_3_BLOCK_LENGTH;
      uint32_t oredI3 = 0;
      bool isNull = true;
      do {
          uint32_t i3 = index[j];
          oredI3 |= i3;
          if (i3 != (uint32_t)dataNullOffset) {
              isNull = false;
          }
      } while (++j < jLimit);
      if (isNull) {
          flags[i] = I3_NULL;
          if (i3FirstNull < 0) {
              if (oredI3 <= 0xffff) {
                  index3Capacity += UCPTRIE_INDEX_3_BLOCK_LENGTH;
              } else {
                  index3Capacity += INDEX_3_18BIT_BLOCK_LENGTH;
                  hasLongI3Blocks = true;
              }
              i3FirstNull = 0;
          }
      } else {
          if (oredI3 <= 0xffff) {
              int32_t n = mixedBlocks.findBlock(fastIndex, index, i);
              if (n >= 0) {
                  flags[i] = I3_BMP;
                  index[i] = n;
              } else {
                  flags[i] = I3_16;
                  index3Capacity += UCPTRIE_INDEX_3_BLOCK_LENGTH;
              }
          } else {
              flags[i] = I3_18;
              index3Capacity += INDEX_3_18BIT_BLOCK_LENGTH;
              hasLongI3Blocks = true;
          }
      }
      i = j;
  }

  int32_t index2Capacity = (iLimit - iStart) >> UCPTRIE_SHIFT_2_3;

  // Length of the index-1 table, rounded up.
  int32_t index1Length = (index2Capacity + UCPTRIE_INDEX_2_MASK) >> UCPTRIE_SHIFT_1_2;

  // Index table: Fast index, index-1, index-3, index-2.
  // +1 for possible index table padding.
  int32_t index16Capacity = fastIndexLength + index1Length + index3Capacity + index2Capacity + 1;
  index16 = (uint16_t *)uprv_mallocuprv_malloc_71(index16Capacity * 2);
  if (index16 == nullptr) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  uprv_memcpy(index16, fastIndex, fastIndexLength * 2)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(index16, fastIndex
, fastIndexLength * 2); } while (false);

  if (!mixedBlocks.init(index16Capacity, UCPTRIE_INDEX_3_BLOCK_LENGTH)) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  MixedBlocks longI3Blocks;
  if (hasLongI3Blocks) {
      if (!longI3Blocks.init(index16Capacity, INDEX_3_18BIT_BLOCK_LENGTH)) {
          errorCode = U_MEMORY_ALLOCATION_ERROR;
          return 0;
      }
  }

  // Compact the index-3 table and write an uncompacted version of the index-2 table.
  uint16_t index2[UNICODE_LIMIT >> UCPTRIE_SHIFT_2];  // index2Capacity
  int32_t i2Length = 0;
  i3FirstNull = index3NullOffset;
  int32_t index3Start = fastIndexLength + index1Length;
  int32_t indexLength = index3Start;
  for (int32_t i = iStart; i < iLimit; i += UCPTRIE_INDEX_3_BLOCK_LENGTH) {
      int32_t i3;
      uint8_t f = flags[i];
      if (f == I3_NULL && i3FirstNull < 0) {
          // First index-3 null block. Write & overlap it like a normal block, then remember it.
          f = dataNullOffset <= 0xffff ? I3_16 : I3_18;
          i3FirstNull = 0;
      }
      if (f == I3_NULL) {
          i3 = index3NullOffset;
      } else if (f == I3_BMP) {
          i3 = index[i];
      } else if (f == I3_16) {
          int32_t n = mixedBlocks.findBlock(index16, index, i);
          if (n >= 0) {
              i3 = n;
          } else {
              if (indexLength == index3Start) {
                  // No overlap at the boundary between the index-1 and index-3 tables.
                  n = 0;
              } else {
                  n = getOverlap(index16, indexLength,
                                 index, i, UCPTRIE_INDEX_3_BLOCK_LENGTH);
              }
              i3 = indexLength - n;
              int32_t prevIndexLength = indexLength;
              while (n < UCPTRIE_INDEX_3_BLOCK_LENGTH) {
                  index16[indexLength++] = index[i + n++];
              }
              mixedBlocks.extend(index16, index3Start, prevIndexLength, indexLength);
              if (hasLongI3Blocks) {
                  longI3Blocks.extend(index16, index3Start, prevIndexLength, indexLength);
              }
          }
      } else {
          U_ASSERT(f == I3_18)(void)0;
          U_ASSERT(hasLongI3Blocks)(void)0;
          // Encode an index-3 block that contains one or more data indexes exceeding 16 bits.
          int32_t j = i;
          int32_t jLimit = i + UCPTRIE_INDEX_3_BLOCK_LENGTH;
          int32_t k = indexLength;
          do {
              ++k;
              uint32_t v = index[j++];
              uint32_t upperBits = (v & 0x30000) >> 2;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 4;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 6;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 8;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 10;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 12;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 14;
              index16[k++] = v;
              v = index[j++];
              upperBits |= (v & 0x30000) >> 16;
              index16[k++] = v;
              index16[k - 9] = upperBits;
          } while (j < jLimit);
          int32_t n = longI3Blocks.findBlock(index16, index16, indexLength);
          if (n >= 0) {
              i3 = n | 0x8000;
          } else {
              if (indexLength == index3Start) {
                  // No overlap at the boundary between the index-1 and index-3 tables.
                  n = 0;
              } else {
                  n = getOverlap(index16, indexLength,
                                 index16, indexLength, INDEX_3_18BIT_BLOCK_LENGTH);
              }
              i3 = (indexLength - n) | 0x8000;
              int32_t prevIndexLength = indexLength;
              if (n > 0) {
                  int32_t start = indexLength;
                  while (n < INDEX_3_18BIT_BLOCK_LENGTH) {
                      index16[indexLength++] = index16[start + n++];
                  }
              } else {
                  indexLength += INDEX_3_18BIT_BLOCK_LENGTH;
              }
              mixedBlocks.extend(index16, index3Start, prevIndexLength, indexLength);
              if (hasLongI3Blocks) {
                  longI3Blocks.extend(index16, index3Start, prevIndexLength, indexLength);
              }
          }
      }
      if (index3NullOffset < 0 && i3FirstNull >= 0) {
          index3NullOffset = i3;
      }
      // Set the index-2 table entry.
      index2[i2Length++] = i3;
  }
  U_ASSERT(i2Length == index2Capacity)(void)0;
  U_ASSERT(indexLength <= index3Start + index3Capacity)(void)0;

  if (index3NullOffset < 0) {
      index3NullOffset = UCPTRIE_NO_INDEX3_NULL_OFFSET;
  }
  if (indexLength >= (UCPTRIE_NO_INDEX3_NULL_OFFSET + UCPTRIE_INDEX_3_BLOCK_LENGTH)) {
      // The index-3 offsets exceed 15 bits, or
      // the last one cannot be distinguished from the no-null-block value.
      errorCode = U_INDEX_OUTOFBOUNDS_ERROR;
      return 0;
  }

  // Compact the index-2 table and write the index-1 table.
  static_assert(UCPTRIE_INDEX_2_BLOCK_LENGTH == UCPTRIE_INDEX_3_BLOCK_LENGTH,
                "must re-init mixedBlocks");
  int32_t blockLength = UCPTRIE_INDEX_2_BLOCK_LENGTH;
  int32_t i1 = fastIndexLength;
  for (int32_t i = 0; i < i2Length; i += blockLength) {
      int32_t n;
      if ((i2Length - i) >= blockLength) {
          // normal block
          U_ASSERT(blockLength == UCPTRIE_INDEX_2_BLOCK_LENGTH)(void)0;
          n = mixedBlocks.findBlock(index16, index2, i);
      } else {
          // highStart is inside the last index-2 block. Shorten it.
          blockLength = i2Length - i;
          n = findSameBlock(index16, index3Start, indexLength,
                            index2, i, blockLength);
      }
      int32_t i2;
      if (n >= 0) {
          i2 = n;
      } else {
          if (indexLength == index3Start) {
              // No overlap at the boundary between the index-1 and index-3/2 tables.
              n = 0;
          } else {
              n = getOverlap(index16, indexLength, index2, i, blockLength);
          }
          i2 = indexLength - n;
          int32_t prevIndexLength = indexLength;
          while (n < blockLength) {
              index16[indexLength++] = index2[i + n++];
          }
          mixedBlocks.extend(index16, index3Start, prevIndexLength, indexLength);
      }
      // Set the index-1 table entry.
      index16[i1++] = i2;
  }
  U_ASSERT(i1 == index3Start)(void)0;
  U_ASSERT(indexLength <= index16Capacity)(void)0;

1482#ifdef UCPTRIE_DEBUG
  /* we saved some space */
  printf("compacting UCPTrie: count of 16-bit index words %lu->%lu\n",
          (long)iLimit, (long)indexLength);
1486#endif

  return indexLength;
1489}

1491int32_t MutableCodePointTrie::compactTrie(int32_t fastILimit, UErrorCode &errorCode) {
  // Find the real highStart and round it up.
  U_ASSERT((highStart & (UCPTRIE_CP_PER_INDEX_2_ENTRY - 1)) == 0)(void)0;
  highValue = get(MAX_UNICODE);
  int32_t realHighStart = findHighStart();
  realHighStart = (realHighStart + (UCPTRIE_CP_PER_INDEX_2_ENTRY - 1)) &
      ~(UCPTRIE_CP_PER_INDEX_2_ENTRY - 1);
  if (realHighStart == UNICODE_LIMIT) {
      highValue = initialValue;
  }

1502#ifdef UCPTRIE_DEBUG
  printf("UCPTrie: highStart U+%06lx  highValue 0x%lx  initialValue 0x%lx\n",
          (long)realHighStart, (long)highValue, (long)initialValue);
1505#endif

  // We always store indexes and data values for the fast range.
  // Pin highStart to the top of that range while building.
  UChar32 fastLimit = fastILimit << UCPTRIE_SHIFT_3;
  if (realHighStart < fastLimit) {
      for (int32_t i = (realHighStart >> UCPTRIE_SHIFT_3); i < fastILimit; ++i) {
          flags[i] = ALL_SAME;
          index[i] = highValue;
      }
      highStart = fastLimit;
  } else {
      highStart = realHighStart;
  }

  uint32_t asciiData[ASCII_LIMIT];
  for (int32_t i = 0; i < ASCII_LIMIT; ++i) {
      asciiData[i] = get(i);
  }

  // First we look for which data blocks have the same value repeated over the whole block,
  // deduplicate such blocks, find a good null data block (for faster enumeration),
  // and get an upper bound for the necessary data array length.
  AllSameBlocks allSameBlocks;
  int32_t newDataCapacity = compactWholeDataBlocks(fastILimit, allSameBlocks);
  if (newDataCapacity < 0) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  uint32_t *newData = (uint32_t *)uprv_mallocuprv_malloc_71(newDataCapacity * 4);
  if (newData == nullptr) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return 0;
  }
  uprv_memcpy(newData, asciiData, sizeof(asciiData))do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(newData, asciiData
, sizeof(asciiData)); } while (false);

  int32_t dataNullIndex = allSameBlocks.findMostUsed();

  MixedBlocks mixedBlocks;
  int32_t newDataLength = compactData(fastILimit, newData, newDataCapacity,
                                      dataNullIndex, mixedBlocks, errorCode);
  if (U_FAILURE(errorCode)) { return 0; }
  U_ASSERT(newDataLength <= newDataCapacity)(void)0;
  uprv_freeuprv_free_71(data);
  data = newData;
  dataCapacity = newDataCapacity;
  dataLength = newDataLength;
  if (dataLength > (0x3ffff + UCPTRIE_SMALL_DATA_BLOCK_LENGTH)) {
      // The offset of the last data block is too high to be stored in the index table.
      errorCode = U_INDEX_OUTOFBOUNDS_ERROR;
      return 0;
  }

  if (dataNullIndex >= 0) {
      dataNullOffset = index[dataNullIndex];
1560#ifdef UCPTRIE_DEBUG
      if (data[dataNullOffset] != initialValue) {
          printf("UCPTrie initialValue %lx -> more common nullValue %lx\n",
                 (long)initialValue, (long)data[dataNullOffset]);
      }
1565#endif
      initialValue = data[dataNullOffset];
  } else {
      dataNullOffset = UCPTRIE_NO_DATA_NULL_OFFSET;
  }

  int32_t indexLength = compactIndex(fastILimit, mixedBlocks, errorCode);
  highStart = realHighStart;
  return indexLength;
1574}

1576UCPTrie *MutableCodePointTrie::build(UCPTrieType type, UCPTrieValueWidth valueWidth, UErrorCode &errorCode) {
  if (U_FAILURE(errorCode)) {
      return nullptr;
  }
  if (type < UCPTRIE_TYPE_FAST || UCPTRIE_TYPE_SMALL < type ||
          valueWidth < UCPTRIE_VALUE_BITS_16 || UCPTRIE_VALUE_BITS_8 < valueWidth) {
      errorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return nullptr;
  }

  // The mutable trie always stores 32-bit values.
  // When we build a UCPTrie for a smaller value width, we first mask off unused bits
  // before compacting the data.
  switch (valueWidth) {
  case UCPTRIE_VALUE_BITS_32:
      break;
  case UCPTRIE_VALUE_BITS_16:
      maskValues(0xffff);
      break;
  case UCPTRIE_VALUE_BITS_8:
      maskValues(0xff);
      break;
  default:
      break;
  }

  UChar32 fastLimit = type == UCPTRIE_TYPE_FAST ? BMP_LIMIT : UCPTRIE_SMALL_LIMIT;
  int32_t indexLength = compactTrie(fastLimit >> UCPTRIE_SHIFT_3, errorCode);
  if (U_FAILURE(errorCode)) {
      clear();
      return nullptr;
  }

  // Ensure data table alignment: The index length must be even for uint32_t data.
  if (valueWidth == UCPTRIE_VALUE_BITS_32 && (indexLength & 1) != 0) {
      index16[indexLength++] = 0xffee;  // arbitrary value
  }

  // Make the total trie structure length a multiple of 4 bytes by padding the data table,
  // and store special values as the last two data values.
  int32_t length = indexLength * 2;
  if (valueWidth == UCPTRIE_VALUE_BITS_16) {
      if (((indexLength ^ dataLength) & 1) != 0) {
          // padding
          data[dataLength++] = errorValue;
      }
      if (data[dataLength - 1] != errorValue || data[dataLength - 2] != highValue) {
          data[dataLength++] = highValue;
          data[dataLength++] = errorValue;
      }
      length += dataLength * 2;
  } else if (valueWidth == UCPTRIE_VALUE_BITS_32) {
      // 32-bit data words never need padding to a multiple of 4 bytes.
      if (data[dataLength - 1] != errorValue || data[dataLength - 2] != highValue) {
          if (data[dataLength - 1] != highValue) {
              data[dataLength++] = highValue;
          }
          data[dataLength++] = errorValue;
      }
      length += dataLength * 4;
  } else {
      int32_t and3 = (length + dataLength) & 3;
      if (and3 == 0 && data[dataLength - 1] == errorValue && data[dataLength - 2] == highValue) {
          // all set
      } else if(and3 == 3 && data[dataLength - 1] == highValue) {
          data[dataLength++] = errorValue;
      } else {
          while (and3 != 2) {
              data[dataLength++] = highValue;
              and3 = (and3 + 1) & 3;
          }
          data[dataLength++] = highValue;
          data[dataLength++] = errorValue;
      }
      length += dataLength;
  }

  // Calculate the total length of the UCPTrie as a single memory block.
  length += sizeof(UCPTrie);
  U_ASSERT((length & 3) == 0)(void)0;

  uint8_t *bytes = (uint8_t *)uprv_mallocuprv_malloc_71(length);
  if (bytes == nullptr) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      clear();
      return nullptr;
  }
  UCPTrie *trie = reinterpret_cast<UCPTrie *>(bytes);
  uprv_memset(trie, 0, sizeof(UCPTrie)):: memset(trie, 0, sizeof(UCPTrie));
  trie->indexLength = indexLength;
  trie->dataLength = dataLength;

  trie->highStart = highStart;
  // Round up shifted12HighStart to a multiple of 0x1000 for easy testing from UTF-8 lead bytes.
  // Runtime code needs to then test for the real highStart as well.
  trie->shifted12HighStart = (highStart + 0xfff) >> 12;
  trie->type = type;
  trie->valueWidth = valueWidth;

  trie->index3NullOffset = index3NullOffset;
  trie->dataNullOffset = dataNullOffset;
  trie->nullValue = initialValue;

  bytes += sizeof(UCPTrie);

  // Fill the index and data arrays.
  uint16_t *dest16 = (uint16_t *)bytes;
  trie->index = dest16;

  if (highStart <= fastLimit) {
      // Condense only the fast index from the mutable-trie index.
      for (int32_t i = 0, j = 0; j < indexLength; i += SMALL_DATA_BLOCKS_PER_BMP_BLOCK, ++j) {
          *dest16++ = (uint16_t)index[i];  // dest16[j]
      }
  } else {
      uprv_memcpy(dest16, index16, indexLength * 2)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(dest16, index16
, indexLength * 2); } while (false);
      dest16 += indexLength;
  }
  bytes += indexLength * 2;

  // Write the data array.
  const uint32_t *p = data;
  switch (valueWidth) {
  case UCPTRIE_VALUE_BITS_16:
      // Write 16-bit data values.
      trie->data.ptr16 = dest16;
      for (int32_t i = dataLength; i > 0; --i) {
          *dest16++ = (uint16_t)*p++;
      }
      break;
  case UCPTRIE_VALUE_BITS_32:
      // Write 32-bit data values.
      trie->data.ptr32 = (uint32_t *)bytes;
      uprv_memcpy(bytes, p, (size_t)dataLength * 4)do { clang diagnostic push
 clang diagnostic ignored "-Waddress"

 (void)0; (void)0; clang diagnostic pop
 :: memcpy(bytes, p,
 (size_t)dataLength * 4); } while (false);
      break;
  case UCPTRIE_VALUE_BITS_8:
      // Write 8-bit data values.
      trie->data.ptr8 = bytes;
      for (int32_t i = dataLength; i > 0; --i) {
          *bytes++ = (uint8_t)*p++;
      }
      break;
  default:
      // Will not occur, valueWidth checked at the beginning.
      break;
  }

1723#ifdef UCPTRIE_DEBUG
  trie->name = name;

  ucptrie_printLengths(trie, "");
1727#endif

  clear();
  return trie;
1731}

1733}  // namespace

1735U_NAMESPACE_END}

1737U_NAMESPACE_USEusing namespace icu_71;

1739U_CAPIextern "C" UMutableCPTrie * U_EXPORT2
1740umutablecptrie_openumutablecptrie_open_71(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  LocalPointer<MutableCodePointTrie> trie(
      new MutableCodePointTrie(initialValue, errorValue, *pErrorCode), *pErrorCode);
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  return reinterpret_cast<UMutableCPTrie *>(trie.orphan());
1750}

1752U_CAPIextern "C" UMutableCPTrie * U_EXPORT2
1753umutablecptrie_cloneumutablecptrie_clone_71(const UMutableCPTrie *other, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  if (other == nullptr) {
      return nullptr;
  }
  LocalPointer<MutableCodePointTrie> clone(
      new MutableCodePointTrie(*reinterpret_cast<const MutableCodePointTrie *>(other), *pErrorCode), *pErrorCode);
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  return reinterpret_cast<UMutableCPTrie *>(clone.orphan());
1766}

1768U_CAPIextern "C" void U_EXPORT2
1769umutablecptrie_closeumutablecptrie_close_71(UMutableCPTrie *trie) {
  delete reinterpret_cast<MutableCodePointTrie *>(trie);
1771}

1773U_CAPIextern "C" UMutableCPTrie * U_EXPORT2
1774umutablecptrie_fromUCPMapumutablecptrie_fromUCPMap_71(const UCPMap *map, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  if (map == nullptr) {
      *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return nullptr;
  }
  return reinterpret_cast<UMutableCPTrie *>(MutableCodePointTrie::fromUCPMap(map, *pErrorCode));
1783}

1785U_CAPIextern "C" UMutableCPTrie * U_EXPORT2
1786umutablecptrie_fromUCPTrieumutablecptrie_fromUCPTrie_71(const UCPTrie *trie, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  if (trie == nullptr) {
      *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return nullptr;
  }
  return reinterpret_cast<UMutableCPTrie *>(MutableCodePointTrie::fromUCPTrie(trie, *pErrorCode));
1795}

1797U_CAPIextern "C" uint32_t U_EXPORT2
1798umutablecptrie_getumutablecptrie_get_71(const UMutableCPTrie *trie, UChar32 c) {
  return reinterpret_cast<const MutableCodePointTrie *>(trie)->get(c);
1800}

1802namespace {

1804UChar32 getRange(const void *trie, UChar32 start,
               UCPMapValueFilter *filter, const void *context, uint32_t *pValue) {
  return reinterpret_cast<const MutableCodePointTrie *>(trie)->
      getRange(start, filter, context, pValue);
1808}

1810}  // namespace

1812U_CAPIextern "C" UChar32 U_EXPORT2
1813umutablecptrie_getRangeumutablecptrie_getRange_71(const UMutableCPTrie *trie, UChar32 start,
                      UCPMapRangeOption option, uint32_t surrogateValue,
                      UCPMapValueFilter *filter, const void *context, uint32_t *pValue) {
  return ucptrie_internalGetRangeucptrie_internalGetRange_71(getRange, trie, start,
                                  option, surrogateValue,
                                  filter, context, pValue);
1819}

1821U_CAPIextern "C" void U_EXPORT2
1822umutablecptrie_setumutablecptrie_set_71(UMutableCPTrie *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return;
  }
  reinterpret_cast<MutableCodePointTrie *>(trie)->set(c, value, *pErrorCode);
1827}

1829U_CAPIextern "C" void U_EXPORT2
1830umutablecptrie_setRangeumutablecptrie_setRange_71(UMutableCPTrie *trie, UChar32 start, UChar32 end,
                 uint32_t value, UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return;
  }
  reinterpret_cast<MutableCodePointTrie *>(trie)->setRange(start, end, value, *pErrorCode);
1836}

1838/* Compact and internally serialize the trie. */
1839U_CAPIextern "C" UCPTrie * U_EXPORT2
1840umutablecptrie_buildImmutableumutablecptrie_buildImmutable_71(UMutableCPTrie *trie, UCPTrieType type, UCPTrieValueWidth valueWidth,
                            UErrorCode *pErrorCode) {
  if (U_FAILURE(*pErrorCode)) {
      return nullptr;
  }
  return reinterpret_cast<MutableCodePointTrie *>(trie)->build(type, valueWidth, *pErrorCode);
1846}

1848#ifdef UCPTRIE_DEBUG
1849U_CFUNCextern "C" void umutablecptrie_setName(UMutableCPTrie *trie, const char *name) {
  reinterpret_cast<MutableCodePointTrie *>(trie)->name = name;
1851}
1852#endif