icuSources/i18n/tznames_impl.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 *******************************************************************************
   5 * Copyright (C) 2011-2016, International Business Machines Corporation and
   6 * others. All Rights Reserved.
   7 *******************************************************************************
   8 *
   9 * File TZNAMES_IMPL.CPP
  10 *
  11 *******************************************************************************
  12 */
  13
  14 #include "unicode/utypes.h"
  15
  16 #if !UCONFIG_NO_FORMATTING
  17
  18 #include "unicode/strenum.h"
  19 #include "unicode/ustring.h"
  20 #include "unicode/timezone.h"
  21 #include "unicode/utf16.h"
  22
  23 #include "tznames_impl.h"
  24 #include "cmemory.h"
  25 #include "cstring.h"
  26 #include "uassert.h"
  27 #include "mutex.h"
  28 #include "resource.h"
  29 #include "uresimp.h"
  30 #include "ureslocs.h"
  31 #include "zonemeta.h"
  32 #include "ucln_in.h"
  33 #include "uvector.h"
  34 #include "olsontz.h"
  35
  36 U_NAMESPACE_BEGIN
  37
  38 #define ZID_KEY_MAX  128
  39 #define MZ_PREFIX_LEN 5
  40
  41 static const char gZoneStrings[]        = "zoneStrings";
  42 static const char gMZPrefix[]           = "meta:";
  43
  44 static const char EMPTY[]               = "<empty>";   // place holder for empty ZNames
  45 static const char DUMMY_LOADER[]        = "<dummy>";   // place holder for dummy ZNamesLoader
  46 static const UChar NO_NAME[]            = { 0 };   // for empty no-fallback time zone names
  47
  48 // stuff for TZDBTimeZoneNames
  49 static const char* TZDBNAMES_KEYS[]               = {"ss", "sd"};
  50 static const int32_t TZDBNAMES_KEYS_SIZE = UPRV_LENGTHOF(TZDBNAMES_KEYS);
  51
  52 static UMutex gTZDBNamesMapLock = U_MUTEX_INITIALIZER;
  53 static UMutex gDataMutex = U_MUTEX_INITIALIZER;
  54
  55 static UHashtable* gTZDBNamesMap = NULL;
  56 static icu::UInitOnce gTZDBNamesMapInitOnce = U_INITONCE_INITIALIZER;
  57
  58 static TextTrieMap* gTZDBNamesTrie = NULL;
  59 static icu::UInitOnce gTZDBNamesTrieInitOnce = U_INITONCE_INITIALIZER;
  60
  61 // The order in which strings are stored may be different than the order in the public enum.
  62 enum UTimeZoneNameTypeIndex {
  63     UTZNM_INDEX_UNKNOWN = -1,
  64     UTZNM_INDEX_EXEMPLAR_LOCATION,
  65     UTZNM_INDEX_LONG_GENERIC,
  66     UTZNM_INDEX_LONG_STANDARD,
  67     UTZNM_INDEX_LONG_DAYLIGHT,
  68     UTZNM_INDEX_SHORT_GENERIC,
  69     UTZNM_INDEX_SHORT_STANDARD,
  70     UTZNM_INDEX_SHORT_DAYLIGHT,
  71     UTZNM_INDEX_COUNT
  72 };
  73 static const UChar* const EMPTY_NAMES[UTZNM_INDEX_COUNT] = {0,0,0,0,0,0,0};
  74
  75 U_CDECL_BEGIN
  76 static UBool U_CALLCONV tzdbTimeZoneNames_cleanup(void) {
  77     if (gTZDBNamesMap != NULL) {
  78         uhash_close(gTZDBNamesMap);
  79         gTZDBNamesMap = NULL;
  80     }
  81     gTZDBNamesMapInitOnce.reset();
  82
  83     if (gTZDBNamesTrie != NULL) {
  84         delete gTZDBNamesTrie;
  85         gTZDBNamesTrie = NULL;
  86     }
  87     gTZDBNamesTrieInitOnce.reset();
  88
  89     return TRUE;
  90 }
  91 U_CDECL_END
  92
  93 /**
  94  * ZNameInfo stores zone name information in the trie
  95  */
  96 struct ZNameInfo {
  97     UTimeZoneNameType   type;
  98     const UChar*        tzID;
  99     const UChar*        mzID;
 100 };
 101
 102 /**
 103  * ZMatchInfo stores zone name match information used by find method
 104  */
 105 struct ZMatchInfo {
 106     const ZNameInfo*    znameInfo;
 107     int32_t             matchLength;
 108 };
 109
 110 // Helper functions
 111 static void mergeTimeZoneKey(const UnicodeString& mzID, char* result);
 112
 113 #define DEFAULT_CHARACTERNODE_CAPACITY 1
 114
 115 // ---------------------------------------------------
 116 // CharacterNode class implementation
 117 // ---------------------------------------------------
 118 void CharacterNode::clear() {
 119     uprv_memset(this, 0, sizeof(*this));
 120 }
 121
 122 void CharacterNode::deleteValues(UObjectDeleter *valueDeleter) {
 123     if (fValues == NULL) {
 124         // Do nothing.
 125     } else if (!fHasValuesVector) {
 126         if (valueDeleter) {
 127             valueDeleter(fValues);
 128         }
 129     } else {
 130         delete (UVector *)fValues;
 131     }
 132 }
 133
 134 void
 135 CharacterNode::addValue(void *value, UObjectDeleter *valueDeleter, UErrorCode &status) {
 136     if (U_FAILURE(status)) {
 137         if (valueDeleter) {
 138             valueDeleter(value);
 139         }
 140         return;
 141     }
 142     if (fValues == NULL) {
 143         fValues = value;
 144     } else {
 145         // At least one value already.
 146         if (!fHasValuesVector) {
 147             // There is only one value so far, and not in a vector yet.
 148             // Create a vector and add the old value.
 149             UVector *values = new UVector(valueDeleter, NULL, DEFAULT_CHARACTERNODE_CAPACITY, status);
 150             if (U_FAILURE(status)) {
 151                 if (valueDeleter) {
 152                     valueDeleter(value);
 153                 }
 154                 return;
 155             }
 156             values->addElement(fValues, status);
 157             fValues = values;
 158             fHasValuesVector = TRUE;
 159         }
 160         // Add the new value.
 161         ((UVector *)fValues)->addElement(value, status);
 162     }
 163 }
 164
 165 // ---------------------------------------------------
 166 // TextTrieMapSearchResultHandler class implementation
 167 // ---------------------------------------------------
 168 TextTrieMapSearchResultHandler::~TextTrieMapSearchResultHandler(){
 169 }
 170
 171 // ---------------------------------------------------
 172 // TextTrieMap class implementation
 173 // ---------------------------------------------------
 174 TextTrieMap::TextTrieMap(UBool ignoreCase, UObjectDeleter *valueDeleter)
 175 : fIgnoreCase(ignoreCase), fNodes(NULL), fNodesCapacity(0), fNodesCount(0),
 176   fLazyContents(NULL), fIsEmpty(TRUE), fValueDeleter(valueDeleter) {
 177 }
 178
 179 TextTrieMap::~TextTrieMap() {
 180     int32_t index;
 181     for (index = 0; index < fNodesCount; ++index) {
 182         fNodes[index].deleteValues(fValueDeleter);
 183     }
 184     uprv_free(fNodes);
 185     if (fLazyContents != NULL) {
 186         for (int32_t i=0; i<fLazyContents->size(); i+=2) {
 187             if (fValueDeleter) {
 188                 fValueDeleter(fLazyContents->elementAt(i+1));
 189             }
 190         }
 191         delete fLazyContents;
 192     }
 193 }
 194
 195 int32_t TextTrieMap::isEmpty() const {
 196     // Use a separate field for fIsEmpty because it will remain unchanged once the
 197     //   Trie is built, while fNodes and fLazyContents change with the lazy init
 198     //   of the nodes structure.  Trying to test the changing fields has
 199     //   thread safety complications.
 200     return fIsEmpty;
 201 }
 202
 203
 204 //  We defer actually building the TextTrieMap node structure until the first time a
 205 //     search is performed.  put() simply saves the parameters in case we do
 206 //     eventually need to build it.
 207 //
 208 void
 209 TextTrieMap::put(const UnicodeString &key, void *value, ZNStringPool &sp, UErrorCode &status) {
 210     const UChar *s = sp.get(key, status);
 211     put(s, value, status);
 212 }
 213
 214 // This method is designed for a persistent key, such as string key stored in
 215 // resource bundle.
 216 void
 217 TextTrieMap::put(const UChar *key, void *value, UErrorCode &status) {
 218     fIsEmpty = FALSE;
 219     if (fLazyContents == NULL) {
 220         fLazyContents = new UVector(status);
 221         if (fLazyContents == NULL) {
 222             status = U_MEMORY_ALLOCATION_ERROR;
 223         }
 224     }
 225     if (U_FAILURE(status)) {
 226         if (fValueDeleter) {
 227             fValueDeleter((void*) key);
 228         }
 229         return;
 230     }
 231     U_ASSERT(fLazyContents != NULL);
 232
 233     UChar *s = const_cast<UChar *>(key);
 234     fLazyContents->addElement(s, status);
 235     if (U_FAILURE(status)) {
 236         if (fValueDeleter) {
 237             fValueDeleter((void*) key);
 238         }
 239         return;
 240     }
 241
 242     fLazyContents->addElement(value, status);
 243 }
 244
 245 void
 246 TextTrieMap::putImpl(const UnicodeString &key, void *value, UErrorCode &status) {
 247     if (fNodes == NULL) {
 248         fNodesCapacity = 512;
 249         fNodes = (CharacterNode *)uprv_malloc(fNodesCapacity * sizeof(CharacterNode));
 250         if (fNodes == NULL) {
 251             status = U_MEMORY_ALLOCATION_ERROR;
 252             return;
 253         }
 254         fNodes[0].clear();  // Init root node.
 255         fNodesCount = 1;
 256     }
 257
 258     UnicodeString foldedKey;
 259     const UChar *keyBuffer;
 260     int32_t keyLength;
 261     if (fIgnoreCase) {
 262         // Ok to use fastCopyFrom() because we discard the copy when we return.
 263         foldedKey.fastCopyFrom(key).foldCase();
 264         keyBuffer = foldedKey.getBuffer();
 265         keyLength = foldedKey.length();
 266     } else {
 267         keyBuffer = key.getBuffer();
 268         keyLength = key.length();
 269     }
 270
 271     CharacterNode *node = fNodes;
 272     int32_t index;
 273     for (index = 0; index < keyLength; ++index) {
 274         node = addChildNode(node, keyBuffer[index], status);
 275     }
 276     node->addValue(value, fValueDeleter, status);
 277 }
 278
 279 UBool
 280 TextTrieMap::growNodes() {
 281     if (fNodesCapacity == 0xffff) {
 282         return FALSE;  // We use 16-bit node indexes.
 283     }
 284     int32_t newCapacity = fNodesCapacity + 1000;
 285     if (newCapacity > 0xffff) {
 286         newCapacity = 0xffff;
 287     }
 288     CharacterNode *newNodes = (CharacterNode *)uprv_malloc(newCapacity * sizeof(CharacterNode));
 289     if (newNodes == NULL) {
 290         return FALSE;
 291     }
 292     uprv_memcpy(newNodes, fNodes, fNodesCount * sizeof(CharacterNode));
 293     uprv_free(fNodes);
 294     fNodes = newNodes;
 295     fNodesCapacity = newCapacity;
 296     return TRUE;
 297 }
 298
 299 CharacterNode*
 300 TextTrieMap::addChildNode(CharacterNode *parent, UChar c, UErrorCode &status) {
 301     if (U_FAILURE(status)) {
 302         return NULL;
 303     }
 304     // Linear search of the sorted list of children.
 305     uint16_t prevIndex = 0;
 306     uint16_t nodeIndex = parent->fFirstChild;
 307     while (nodeIndex > 0) {
 308         CharacterNode *current = fNodes + nodeIndex;
 309         UChar childCharacter = current->fCharacter;
 310         if (childCharacter == c) {
 311             return current;
 312         } else if (childCharacter > c) {
 313             break;
 314         }
 315         prevIndex = nodeIndex;
 316         nodeIndex = current->fNextSibling;
 317     }
 318
 319     // Ensure capacity. Grow fNodes[] if needed.
 320     if (fNodesCount == fNodesCapacity) {
 321         int32_t parentIndex = (int32_t)(parent - fNodes);
 322         if (!growNodes()) {
 323             status = U_MEMORY_ALLOCATION_ERROR;
 324             return NULL;
 325         }
 326         parent = fNodes + parentIndex;
 327     }
 328
 329     // Insert a new child node with c in sorted order.
 330     CharacterNode *node = fNodes + fNodesCount;
 331     node->clear();
 332     node->fCharacter = c;
 333     node->fNextSibling = nodeIndex;
 334     if (prevIndex == 0) {
 335         parent->fFirstChild = (uint16_t)fNodesCount;
 336     } else {
 337         fNodes[prevIndex].fNextSibling = (uint16_t)fNodesCount;
 338     }
 339     ++fNodesCount;
 340     return node;
 341 }
 342
 343 CharacterNode*
 344 TextTrieMap::getChildNode(CharacterNode *parent, UChar c) const {
 345     // Linear search of the sorted list of children.
 346     uint16_t nodeIndex = parent->fFirstChild;
 347     while (nodeIndex > 0) {
 348         CharacterNode *current = fNodes + nodeIndex;
 349         UChar childCharacter = current->fCharacter;
 350         if (childCharacter == c) {
 351             return current;
 352         } else if (childCharacter > c) {
 353             break;
 354         }
 355         nodeIndex = current->fNextSibling;
 356     }
 357     return NULL;
 358 }
 359
 360 // Mutex for protecting the lazy creation of the Trie node structure on the first call to search().
 361 static UMutex TextTrieMutex = U_MUTEX_INITIALIZER;
 362
 363 // buildTrie() - The Trie node structure is needed.  Create it from the data that was
 364 //               saved at the time the ZoneStringFormatter was created.  The Trie is only
 365 //               needed for parsing operations, which are less common than formatting,
 366 //               and the Trie is big, which is why its creation is deferred until first use.
 367 void TextTrieMap::buildTrie(UErrorCode &status) {
 368     if (fLazyContents != NULL) {
 369         for (int32_t i=0; i<fLazyContents->size(); i+=2) {
 370             const UChar *key = (UChar *)fLazyContents->elementAt(i);
 371             void  *val = fLazyContents->elementAt(i+1);
 372             UnicodeString keyString(TRUE, key, -1);  // Aliasing UnicodeString constructor.
 373             putImpl(keyString, val, status);
 374         }
 375         delete fLazyContents;
 376         fLazyContents = NULL;
 377     }
 378 }
 379
 380 void
 381 TextTrieMap::search(const UnicodeString &text, int32_t start,
 382                   TextTrieMapSearchResultHandler *handler, UErrorCode &status) const {
 383     {
 384         // TODO: if locking the mutex for each check proves to be a performance problem,
 385         //       add a flag of type atomic_int32_t to class TextTrieMap, and use only
 386         //       the ICU atomic safe functions for assigning and testing.
 387         //       Don't test the pointer fLazyContents.
 388         //       Don't do unless it's really required.
 389         Mutex lock(&TextTrieMutex);
 390         if (fLazyContents != NULL) {
 391             TextTrieMap *nonConstThis = const_cast<TextTrieMap *>(this);
 392             nonConstThis->buildTrie(status);
 393         }
 394     }
 395     if (fNodes == NULL) {
 396         return;
 397     }
 398     search(fNodes, text, start, start, handler, status);
 399 }
 400
 401 void
 402 TextTrieMap::search(CharacterNode *node, const UnicodeString &text, int32_t start,
 403                   int32_t index, TextTrieMapSearchResultHandler *handler, UErrorCode &status) const {
 404     if (U_FAILURE(status)) {
 405         return;
 406     }
 407     if (node->hasValues()) {
 408         if (!handler->handleMatch(index - start, node, status)) {
 409             return;
 410         }
 411         if (U_FAILURE(status)) {
 412             return;
 413         }
 414     }
 415     if (fIgnoreCase) {
 416         // for folding we need to get a complete code point.
 417         // size of character may grow after fold operation;
 418         // then we need to get result as UTF16 code units.
 419         UChar32 c32 = text.char32At(index);
 420         index += U16_LENGTH(c32);
 421         UnicodeString tmp(c32);
 422         tmp.foldCase();
 423         int32_t tmpidx = 0;
 424         while (tmpidx < tmp.length()) {
 425             UChar c = tmp.charAt(tmpidx++);
 426             node = getChildNode(node, c);
 427             if (node == NULL) {
 428                 break;
 429             }
 430         }
 431     } else {
 432         // here we just get the next UTF16 code unit
 433         UChar c = text.charAt(index++);
 434         node = getChildNode(node, c);
 435     }
 436     if (node != NULL) {
 437         search(node, text, start, index, handler, status);
 438     }
 439 }
 440
 441 // ---------------------------------------------------
 442 // ZNStringPool class implementation
 443 // ---------------------------------------------------
 444 static const int32_t POOL_CHUNK_SIZE = 2000;
 445 struct ZNStringPoolChunk: public UMemory {
 446     ZNStringPoolChunk    *fNext;                       // Ptr to next pool chunk
 447     int32_t               fLimit;                       // Index to start of unused area at end of fStrings
 448     UChar                 fStrings[POOL_CHUNK_SIZE];    //  Strings array
 449     ZNStringPoolChunk();
 450 };
 451
 452 ZNStringPoolChunk::ZNStringPoolChunk() {
 453     fNext = NULL;
 454     fLimit = 0;
 455 }
 456
 457 ZNStringPool::ZNStringPool(UErrorCode &status) {
 458     fChunks = NULL;
 459     fHash   = NULL;
 460     if (U_FAILURE(status)) {
 461         return;
 462     }
 463     fChunks = new ZNStringPoolChunk;
 464     if (fChunks == NULL) {
 465         status = U_MEMORY_ALLOCATION_ERROR;
 466         return;
 467     }
 468
 469     fHash   = uhash_open(uhash_hashUChars      /* keyHash */,
 470                          uhash_compareUChars   /* keyComp */,
 471                          uhash_compareUChars   /* valueComp */,
 472                          &status);
 473     if (U_FAILURE(status)) {
 474         return;
 475     }
 476 }
 477
 478 ZNStringPool::~ZNStringPool() {
 479     if (fHash != NULL) {
 480         uhash_close(fHash);
 481         fHash = NULL;
 482     }
 483
 484     while (fChunks != NULL) {
 485         ZNStringPoolChunk *nextChunk = fChunks->fNext;
 486         delete fChunks;
 487         fChunks = nextChunk;
 488     }
 489 }
 490
 491 static const UChar EmptyString = 0;
 492
 493 const UChar *ZNStringPool::get(const UChar *s, UErrorCode &status) {
 494     const UChar *pooledString;
 495     if (U_FAILURE(status)) {
 496         return &EmptyString;
 497     }
 498
 499     pooledString = static_cast<UChar *>(uhash_get(fHash, s));
 500     if (pooledString != NULL) {
 501         return pooledString;
 502     }
 503
 504     int32_t length = u_strlen(s);
 505     int32_t remainingLength = POOL_CHUNK_SIZE - fChunks->fLimit;
 506     if (remainingLength <= length) {
 507         U_ASSERT(length < POOL_CHUNK_SIZE);
 508         if (length >= POOL_CHUNK_SIZE) {
 509             status = U_INTERNAL_PROGRAM_ERROR;
 510             return &EmptyString;
 511         }
 512         ZNStringPoolChunk *oldChunk = fChunks;
 513         fChunks = new ZNStringPoolChunk;
 514         if (fChunks == NULL) {
 515             status = U_MEMORY_ALLOCATION_ERROR;
 516             return &EmptyString;
 517         }
 518         fChunks->fNext = oldChunk;
 519     }
 520
 521     UChar *destString = &fChunks->fStrings[fChunks->fLimit];
 522     u_strcpy(destString, s);
 523     fChunks->fLimit += (length + 1);
 524     uhash_put(fHash, destString, destString, &status);
 525     return destString;
 526 }
 527
 528
 529 //
 530 //  ZNStringPool::adopt()    Put a string into the hash, but do not copy the string data
 531 //                           into the pool's storage.  Used for strings from resource bundles,
 532 //                           which will perisist for the life of the zone string formatter, and
 533 //                           therefore can be used directly without copying.
 534 const UChar *ZNStringPool::adopt(const UChar * s, UErrorCode &status) {
 535     const UChar *pooledString;
 536     if (U_FAILURE(status)) {
 537         return &EmptyString;
 538     }
 539     if (s != NULL) {
 540         pooledString = static_cast<UChar *>(uhash_get(fHash, s));
 541         if (pooledString == NULL) {
 542             UChar *ncs = const_cast<UChar *>(s);
 543             uhash_put(fHash, ncs, ncs, &status);
 544         }
 545     }
 546     return s;
 547 }
 548
 549
 550 const UChar *ZNStringPool::get(const UnicodeString &s, UErrorCode &status) {
 551     UnicodeString &nonConstStr = const_cast<UnicodeString &>(s);
 552     return this->get(nonConstStr.getTerminatedBuffer(), status);
 553 }
 554
 555 /*
 556  * freeze().   Close the hash table that maps to the pooled strings.
 557  *             After freezing, the pool can not be searched or added to,
 558  *             but all existing references to pooled strings remain valid.
 559  *
 560  *             The main purpose is to recover the storage used for the hash.
 561  */
 562 void ZNStringPool::freeze() {
 563     uhash_close(fHash);
 564     fHash = NULL;
 565 }
 566
 567
 568 /**
 569  * This class stores name data for a meta zone or time zone.
 570  */
 571 class ZNames : public UMemory {
 572 private:
 573     friend class TimeZoneNamesImpl;
 574
 575     static UTimeZoneNameTypeIndex getTZNameTypeIndex(UTimeZoneNameType type) {
 576         switch(type) {
 577         case UTZNM_EXEMPLAR_LOCATION: return UTZNM_INDEX_EXEMPLAR_LOCATION;
 578         case UTZNM_LONG_GENERIC: return UTZNM_INDEX_LONG_GENERIC;
 579         case UTZNM_LONG_STANDARD: return UTZNM_INDEX_LONG_STANDARD;
 580         case UTZNM_LONG_DAYLIGHT: return UTZNM_INDEX_LONG_DAYLIGHT;
 581         case UTZNM_SHORT_GENERIC: return UTZNM_INDEX_SHORT_GENERIC;
 582         case UTZNM_SHORT_STANDARD: return UTZNM_INDEX_SHORT_STANDARD;
 583         case UTZNM_SHORT_DAYLIGHT: return UTZNM_INDEX_SHORT_DAYLIGHT;
 584         default: return UTZNM_INDEX_UNKNOWN;
 585         }
 586     }
 587     static UTimeZoneNameType getTZNameType(UTimeZoneNameTypeIndex index) {
 588         switch(index) {
 589         case UTZNM_INDEX_EXEMPLAR_LOCATION: return UTZNM_EXEMPLAR_LOCATION;
 590         case UTZNM_INDEX_LONG_GENERIC: return UTZNM_LONG_GENERIC;
 591         case UTZNM_INDEX_LONG_STANDARD: return UTZNM_LONG_STANDARD;
 592         case UTZNM_INDEX_LONG_DAYLIGHT: return UTZNM_LONG_DAYLIGHT;
 593         case UTZNM_INDEX_SHORT_GENERIC: return UTZNM_SHORT_GENERIC;
 594         case UTZNM_INDEX_SHORT_STANDARD: return UTZNM_SHORT_STANDARD;
 595         case UTZNM_INDEX_SHORT_DAYLIGHT: return UTZNM_SHORT_DAYLIGHT;
 596         default: return UTZNM_UNKNOWN;
 597         }
 598     }
 599
 600     const UChar* fNames[UTZNM_INDEX_COUNT];
 601     UBool fDidAddIntoTrie;
 602
 603     // Whether we own the location string, if computed rather than loaded from a bundle.
 604     // A meta zone names instance never has an exemplar location string.
 605     UBool fOwnsLocationName;
 606
 607     ZNames(const UChar* names[], const UChar* locationName)
 608             : fDidAddIntoTrie(FALSE) {
 609         uprv_memcpy(fNames, names, sizeof(fNames));
 610         if (locationName != NULL) {
 611             fOwnsLocationName = TRUE;
 612             fNames[UTZNM_INDEX_EXEMPLAR_LOCATION] = locationName;
 613         } else {
 614             fOwnsLocationName = FALSE;
 615         }
 616     }
 617
 618 public:
 619     ~ZNames() {
 620         if (fOwnsLocationName) {
 621             const UChar* locationName = fNames[UTZNM_INDEX_EXEMPLAR_LOCATION];
 622             U_ASSERT(locationName != NULL);
 623             uprv_free((void*) locationName);
 624         }
 625     }
 626
 627 private:
 628     static void* createMetaZoneAndPutInCache(UHashtable* cache, const UChar* names[],
 629             const UnicodeString& mzID, UErrorCode& status) {
 630         if (U_FAILURE(status)) { return NULL; }
 631         U_ASSERT(names != NULL);
 632
 633         // Use the persistent ID as the resource key, so we can
 634         // avoid duplications.
 635         // TODO: Is there a more efficient way, like intern() in Java?
 636         void* key = (void*) ZoneMeta::findMetaZoneID(mzID);
 637         void* value;
 638         if (uprv_memcmp(names, EMPTY_NAMES, sizeof(EMPTY_NAMES)) == 0) {
 639             value = (void*) EMPTY;
 640         } else {
 641             value = (void*) (new ZNames(names, NULL));
 642             if (value == NULL) {
 643                 status = U_MEMORY_ALLOCATION_ERROR;
 644                 return NULL;
 645             }
 646         }
 647         uhash_put(cache, key, value, &status);
 648         return value;
 649     }
 650
 651     static void* createTimeZoneAndPutInCache(UHashtable* cache, const UChar* names[],
 652             const UnicodeString& tzID, UErrorCode& status) {
 653         if (U_FAILURE(status)) { return NULL; }
 654         U_ASSERT(names != NULL);
 655
 656         // If necessary, compute the location name from the time zone name.
 657         UChar* locationName = NULL;
 658         if (names[UTZNM_INDEX_EXEMPLAR_LOCATION] == NULL) {
 659             UnicodeString locationNameUniStr;
 660             TimeZoneNamesImpl::getDefaultExemplarLocationName(tzID, locationNameUniStr);
 661
 662             // Copy the computed location name to the heap
 663             if (locationNameUniStr.length() > 0) {
 664                 const UChar* buff = locationNameUniStr.getTerminatedBuffer();
 665                 int32_t len = sizeof(UChar) * (locationNameUniStr.length() + 1);
 666                 locationName = (UChar*) uprv_malloc(len);
 667                 if (locationName == NULL) {
 668                     status = U_MEMORY_ALLOCATION_ERROR;
 669                     return NULL;
 670                 }
 671                 uprv_memcpy(locationName, buff, len);
 672             }
 673         }
 674
 675         // Use the persistent ID as the resource key, so we can
 676         // avoid duplications.
 677         // TODO: Is there a more efficient way, like intern() in Java?
 678         void* key = (void*) ZoneMeta::findTimeZoneID(tzID);
 679         void* value = (void*) (new ZNames(names, locationName));
 680         if (value == NULL) {
 681             status = U_MEMORY_ALLOCATION_ERROR;
 682             return NULL;
 683         }
 684         uhash_put(cache, key, value, &status);
 685         return value;
 686     }
 687
 688     const UChar* getName(UTimeZoneNameType type) const {
 689         UTimeZoneNameTypeIndex index = getTZNameTypeIndex(type);
 690         return index >= 0 ? fNames[index] : NULL;
 691     }
 692
 693     void addAsMetaZoneIntoTrie(const UChar* mzID, TextTrieMap& trie, UErrorCode& status) {
 694         addNamesIntoTrie(mzID, NULL, trie, status);
 695     }
 696     void addAsTimeZoneIntoTrie(const UChar* tzID, TextTrieMap& trie, UErrorCode& status) {
 697         addNamesIntoTrie(NULL, tzID, trie, status);
 698     }
 699
 700     void addNamesIntoTrie(const UChar* mzID, const UChar* tzID, TextTrieMap& trie,
 701             UErrorCode& status) {
 702         if (U_FAILURE(status)) { return; }
 703         if (fDidAddIntoTrie) { return; }
 704         fDidAddIntoTrie = TRUE;
 705
 706         for (int32_t i = 0; i < UTZNM_INDEX_COUNT; i++) {
 707             const UChar* name = fNames[i];
 708             if (name != NULL) {
 709                 ZNameInfo *nameinfo = (ZNameInfo *)uprv_malloc(sizeof(ZNameInfo));
 710                 if (nameinfo == NULL) {
 711                     status = U_MEMORY_ALLOCATION_ERROR;
 712                     return;
 713                 }
 714                 nameinfo->mzID = mzID;
 715                 nameinfo->tzID = tzID;
 716                 nameinfo->type = getTZNameType((UTimeZoneNameTypeIndex)i);
 717                 trie.put(name, nameinfo, status); // trie.put() takes ownership of the key
 718                 if (U_FAILURE(status)) {
 719                     return;
 720                 }
 721             }
 722         }
 723     }
 724
 725 public:
 726     struct ZNamesLoader;
 727 };
 728
 729 struct ZNames::ZNamesLoader : public ResourceSink {
 730     const UChar *names[UTZNM_INDEX_COUNT];
 731
 732     ZNamesLoader() {
 733         clear();
 734     }
 735     virtual ~ZNamesLoader();
 736
 737     /** Reset for loading another set of names. */
 738     void clear() {
 739         uprv_memcpy(names, EMPTY_NAMES, sizeof(names));
 740     }
 741
 742     void loadMetaZone(const UResourceBundle* zoneStrings, const UnicodeString& mzID, UErrorCode& errorCode) {
 743         if (U_FAILURE(errorCode)) { return; }
 744
 745         char key[ZID_KEY_MAX + 1];
 746         mergeTimeZoneKey(mzID, key);
 747
 748         loadNames(zoneStrings, key, errorCode);
 749     }
 750
 751     void loadTimeZone(const UResourceBundle* zoneStrings, const UnicodeString& tzID, UErrorCode& errorCode) {
 752         // Replace "/" with ":".
 753         UnicodeString uKey(tzID);
 754         for (int32_t i = 0; i < uKey.length(); i++) {
 755             if (uKey.charAt(i) == (UChar)0x2F) {
 756                 uKey.setCharAt(i, (UChar)0x3A);
 757             }
 758         }
 759
 760         char key[ZID_KEY_MAX + 1];
 761         uKey.extract(0, uKey.length(), key, sizeof(key), US_INV);
 762
 763         loadNames(zoneStrings, key, errorCode);
 764     }
 765
 766     void loadNames(const UResourceBundle* zoneStrings, const char* key, UErrorCode& errorCode) {
 767         U_ASSERT(zoneStrings != NULL);
 768         U_ASSERT(key != NULL);
 769         U_ASSERT(key[0] != '\0');
 770
 771         UErrorCode localStatus = U_ZERO_ERROR;
 772         clear();
 773         ures_getAllItemsWithFallback(zoneStrings, key, *this, localStatus);
 774
 775         // Ignore errors, but propogate possible warnings.
 776         if (U_SUCCESS(localStatus)) {
 777             errorCode = localStatus;
 778         }
 779     }
 780
 781     void setNameIfEmpty(const char* key, const ResourceValue* value, UErrorCode& errorCode) {
 782         UTimeZoneNameTypeIndex type = nameTypeFromKey(key);
 783         if (type == UTZNM_INDEX_UNKNOWN) { return; }
 784         if (names[type] == NULL) {
 785             int32_t length;
 786             // 'NO_NAME' indicates internally that this field should remain empty.  It will be
 787             // replaced by 'NULL' in getNames()
 788             names[type] = (value == NULL) ? NO_NAME : value->getString(length, errorCode);
 789         }
 790     }
 791
 792     virtual void put(const char* key, ResourceValue& value, UBool /*noFallback*/,
 793             UErrorCode &errorCode) {
 794         ResourceTable namesTable = value.getTable(errorCode);
 795         if (U_FAILURE(errorCode)) { return; }
 796         for (int32_t i = 0; namesTable.getKeyAndValue(i, key, value); ++i) {
 797             if (value.isNoInheritanceMarker()) {
 798                 setNameIfEmpty(key, NULL, errorCode);
 799             } else {
 800                 setNameIfEmpty(key, &value, errorCode);
 801             }
 802         }
 803     }
 804
 805     static UTimeZoneNameTypeIndex nameTypeFromKey(const char *key) {
 806         char c0, c1;
 807         if ((c0 = key[0]) == 0 || (c1 = key[1]) == 0 || key[2] != 0) {
 808             return UTZNM_INDEX_UNKNOWN;
 809         }
 810         if (c0 == 'l') {
 811             return c1 == 'g' ? UTZNM_INDEX_LONG_GENERIC :
 812                     c1 == 's' ? UTZNM_INDEX_LONG_STANDARD :
 813                         c1 == 'd' ? UTZNM_INDEX_LONG_DAYLIGHT : UTZNM_INDEX_UNKNOWN;
 814         } else if (c0 == 's') {
 815             return c1 == 'g' ? UTZNM_INDEX_SHORT_GENERIC :
 816                     c1 == 's' ? UTZNM_INDEX_SHORT_STANDARD :
 817                         c1 == 'd' ? UTZNM_INDEX_SHORT_DAYLIGHT : UTZNM_INDEX_UNKNOWN;
 818         } else if (c0 == 'e' && c1 == 'c') {
 819             return UTZNM_INDEX_EXEMPLAR_LOCATION;
 820         }
 821         return UTZNM_INDEX_UNKNOWN;
 822     }
 823
 824     /**
 825     * Returns an array of names.  It is the caller's responsibility to copy the data into a
 826     * permanent location, as the returned array is owned by the loader instance and may be
 827     * cleared or leave scope.
 828     *
 829     * This is different than Java, where the array will no longer be modified and null
 830     * may be returned.
 831     */
 832     const UChar** getNames() {
 833         // Remove 'NO_NAME' references in the array and replace with 'NULL'
 834         for (int32_t i = 0; i < UTZNM_INDEX_COUNT; ++i) {
 835             if (names[i] == NO_NAME) {
 836                 names[i] = NULL;
 837             }
 838         }
 839         return names;
 840     }
 841 };
 842
 843 ZNames::ZNamesLoader::~ZNamesLoader() {}
 844
 845
 846 // ---------------------------------------------------
 847 // The meta zone ID enumeration class
 848 // ---------------------------------------------------
 849 class MetaZoneIDsEnumeration : public StringEnumeration {
 850 public:
 851     MetaZoneIDsEnumeration();
 852     MetaZoneIDsEnumeration(const UVector& mzIDs);
 853     MetaZoneIDsEnumeration(UVector* mzIDs);
 854     virtual ~MetaZoneIDsEnumeration();
 855     static UClassID U_EXPORT2 getStaticClassID(void);
 856     virtual UClassID getDynamicClassID(void) const;
 857     virtual const UnicodeString* snext(UErrorCode& status);
 858     virtual void reset(UErrorCode& status);
 859     virtual int32_t count(UErrorCode& status) const;
 860 private:
 861     int32_t fLen;
 862     int32_t fPos;
 863     const UVector* fMetaZoneIDs;
 864     UVector *fLocalVector;
 865 };
 866
 867 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(MetaZoneIDsEnumeration)
 868
 869 MetaZoneIDsEnumeration::MetaZoneIDsEnumeration()
 870 : fLen(0), fPos(0), fMetaZoneIDs(NULL), fLocalVector(NULL) {
 871 }
 872
 873 MetaZoneIDsEnumeration::MetaZoneIDsEnumeration(const UVector& mzIDs)
 874 : fPos(0), fMetaZoneIDs(&mzIDs), fLocalVector(NULL) {
 875     fLen = fMetaZoneIDs->size();
 876 }
 877
 878 MetaZoneIDsEnumeration::MetaZoneIDsEnumeration(UVector *mzIDs)
 879 : fLen(0), fPos(0), fMetaZoneIDs(mzIDs), fLocalVector(mzIDs) {
 880     if (fMetaZoneIDs) {
 881         fLen = fMetaZoneIDs->size();
 882     }
 883 }
 884
 885 const UnicodeString*
 886 MetaZoneIDsEnumeration::snext(UErrorCode& status) {
 887     if (U_SUCCESS(status) && fMetaZoneIDs != NULL && fPos < fLen) {
 888         unistr.setTo((const UChar*)fMetaZoneIDs->elementAt(fPos++), -1);
 889         return &unistr;
 890     }
 891     return NULL;
 892 }
 893
 894 void
 895 MetaZoneIDsEnumeration::reset(UErrorCode& /*status*/) {
 896     fPos = 0;
 897 }
 898
 899 int32_t
 900 MetaZoneIDsEnumeration::count(UErrorCode& /*status*/) const {
 901     return fLen;
 902 }
 903
 904 MetaZoneIDsEnumeration::~MetaZoneIDsEnumeration() {
 905     if (fLocalVector) {
 906         delete fLocalVector;
 907     }
 908 }
 909
 910
 911 // ---------------------------------------------------
 912 // ZNameSearchHandler
 913 // ---------------------------------------------------
 914 class ZNameSearchHandler : public TextTrieMapSearchResultHandler {
 915 public:
 916     ZNameSearchHandler(uint32_t types);
 917     virtual ~ZNameSearchHandler();
 918
 919     UBool handleMatch(int32_t matchLength, const CharacterNode *node, UErrorCode &status);
 920     TimeZoneNames::MatchInfoCollection* getMatches(int32_t& maxMatchLen);
 921
 922 private:
 923     uint32_t fTypes;
 924     int32_t fMaxMatchLen;
 925     TimeZoneNames::MatchInfoCollection* fResults;
 926 };
 927
 928 ZNameSearchHandler::ZNameSearchHandler(uint32_t types)
 929 : fTypes(types), fMaxMatchLen(0), fResults(NULL) {
 930 }
 931
 932 ZNameSearchHandler::~ZNameSearchHandler() {
 933     if (fResults != NULL) {
 934         delete fResults;
 935     }
 936 }
 937
 938 UBool
 939 ZNameSearchHandler::handleMatch(int32_t matchLength, const CharacterNode *node, UErrorCode &status) {
 940     if (U_FAILURE(status)) {
 941         return FALSE;
 942     }
 943     if (node->hasValues()) {
 944         int32_t valuesCount = node->countValues();
 945         for (int32_t i = 0; i < valuesCount; i++) {
 946             ZNameInfo *nameinfo = (ZNameInfo *)node->getValue(i);
 947             if (nameinfo == NULL) {
 948                 continue;
 949             }
 950             if ((nameinfo->type & fTypes) != 0) {
 951                 // matches a requested type
 952                 if (fResults == NULL) {
 953                     fResults = new TimeZoneNames::MatchInfoCollection();
 954                     if (fResults == NULL) {
 955                         status = U_MEMORY_ALLOCATION_ERROR;
 956                     }
 957                 }
 958                 if (U_SUCCESS(status)) {
 959                     U_ASSERT(fResults != NULL);
 960                     if (nameinfo->tzID) {
 961                         fResults->addZone(nameinfo->type, matchLength, UnicodeString(nameinfo->tzID, -1), status);
 962                     } else {
 963                         U_ASSERT(nameinfo->mzID);
 964                         fResults->addMetaZone(nameinfo->type, matchLength, UnicodeString(nameinfo->mzID, -1), status);
 965                     }
 966                     if (U_SUCCESS(status) && matchLength > fMaxMatchLen) {
 967                         fMaxMatchLen = matchLength;
 968                     }
 969                 }
 970             }
 971         }
 972     }
 973     return TRUE;
 974 }
 975
 976 TimeZoneNames::MatchInfoCollection*
 977 ZNameSearchHandler::getMatches(int32_t& maxMatchLen) {
 978     // give the ownership to the caller
 979     TimeZoneNames::MatchInfoCollection* results = fResults;
 980     maxMatchLen = fMaxMatchLen;
 981
 982     // reset
 983     fResults = NULL;
 984     fMaxMatchLen = 0;
 985     return results;
 986 }
 987
 988 // ---------------------------------------------------
 989 // TimeZoneNamesImpl
 990 //
 991 // TimeZoneNames implementation class. This is the main
 992 // part of this module.
 993 // ---------------------------------------------------
 994
 995 U_CDECL_BEGIN
 996 /**
 997  * Deleter for ZNames
 998  */
 999 static void U_CALLCONV
1000 deleteZNames(void *obj) {
1001     if (obj != EMPTY) {
1002         delete (ZNames*) obj;
1003     }
1004 }
1005
1006 /**
1007  * Deleter for ZNameInfo
1008  */
1009 static void U_CALLCONV
1010 deleteZNameInfo(void *obj) {
1011     uprv_free(obj);
1012 }
1013
1014 U_CDECL_END
1015
1016 TimeZoneNamesImpl::TimeZoneNamesImpl(const Locale& locale, UErrorCode& status)
1017 : fLocale(locale),
1018   fZoneStrings(NULL),
1019   fTZNamesMap(NULL),
1020   fMZNamesMap(NULL),
1021   fNamesTrieFullyLoaded(FALSE),
1022   fNamesFullyLoaded(FALSE),
1023   fNamesTrie(TRUE, deleteZNameInfo) {
1024     initialize(locale, status);
1025 }
1026
1027 void
1028 TimeZoneNamesImpl::initialize(const Locale& locale, UErrorCode& status) {
1029     if (U_FAILURE(status)) {
1030         return;
1031     }
1032
1033     // Load zoneStrings bundle
1034     UErrorCode tmpsts = U_ZERO_ERROR;   // OK with fallback warning..
1035     fZoneStrings = ures_open(U_ICUDATA_ZONE, locale.getName(), &tmpsts);
1036     fZoneStrings = ures_getByKeyWithFallback(fZoneStrings, gZoneStrings, fZoneStrings, &tmpsts);
1037     if (U_FAILURE(tmpsts)) {
1038         status = tmpsts;
1039         cleanup();
1040         return;
1041     }
1042
1043     // Initialize hashtables holding time zone/meta zone names
1044     fMZNamesMap = uhash_open(uhash_hashUChars, uhash_compareUChars, NULL, &status);
1045     fTZNamesMap = uhash_open(uhash_hashUChars, uhash_compareUChars, NULL, &status);
1046     if (U_FAILURE(status)) {
1047         cleanup();
1048         return;
1049     }
1050
1051     uhash_setValueDeleter(fMZNamesMap, deleteZNames);
1052     uhash_setValueDeleter(fTZNamesMap, deleteZNames);
1053     // no key deleters for name maps
1054
1055     // preload zone strings for the default zone
1056     TimeZone *tz = TimeZone::createDefault();
1057     const UChar *tzID = ZoneMeta::getCanonicalCLDRID(*tz);
1058     if (tzID != NULL) {
1059         loadStrings(UnicodeString(tzID), status);
1060     }
1061     delete tz;
1062
1063     return;
1064 }
1065
1066 /*
1067  * This method updates the cache and must be called with a lock,
1068  * except initializer.
1069  */
1070 void
1071 TimeZoneNamesImpl::loadStrings(const UnicodeString& tzCanonicalID, UErrorCode& status) {
1072     loadTimeZoneNames(tzCanonicalID, status);
1073     LocalPointer<StringEnumeration> mzIDs(getAvailableMetaZoneIDs(tzCanonicalID, status));
1074     if (U_FAILURE(status)) { return; }
1075     U_ASSERT(!mzIDs.isNull());
1076
1077     const UnicodeString *mzID;
1078     while (((mzID = mzIDs->snext(status)) != NULL) && U_SUCCESS(status)) {
1079         loadMetaZoneNames(*mzID, status);
1080     }
1081 }
1082
1083 TimeZoneNamesImpl::~TimeZoneNamesImpl() {
1084     cleanup();
1085 }
1086
1087 void
1088 TimeZoneNamesImpl::cleanup() {
1089     if (fZoneStrings != NULL) {
1090         ures_close(fZoneStrings);
1091         fZoneStrings = NULL;
1092     }
1093     if (fMZNamesMap != NULL) {
1094         uhash_close(fMZNamesMap);
1095         fMZNamesMap = NULL;
1096     }
1097     if (fTZNamesMap != NULL) {
1098         uhash_close(fTZNamesMap);
1099         fTZNamesMap = NULL;
1100     }
1101 }
1102
1103 UBool
1104 TimeZoneNamesImpl::operator==(const TimeZoneNames& other) const {
1105     if (this == &other) {
1106         return TRUE;
1107     }
1108     // No implementation for now
1109     return FALSE;
1110 }
1111
1112 TimeZoneNames*
1113 TimeZoneNamesImpl::clone() const {
1114     UErrorCode status = U_ZERO_ERROR;
1115     return new TimeZoneNamesImpl(fLocale, status);
1116 }
1117
1118 StringEnumeration*
1119 TimeZoneNamesImpl::getAvailableMetaZoneIDs(UErrorCode& status) const {
1120     return TimeZoneNamesImpl::_getAvailableMetaZoneIDs(status);
1121 }
1122
1123 // static implementation of getAvailableMetaZoneIDs(UErrorCode&)
1124 StringEnumeration*
1125 TimeZoneNamesImpl::_getAvailableMetaZoneIDs(UErrorCode& status) {
1126     if (U_FAILURE(status)) {
1127         return NULL;
1128     }
1129     const UVector* mzIDs = ZoneMeta::getAvailableMetazoneIDs();
1130     if (mzIDs == NULL) {
1131         return new MetaZoneIDsEnumeration();
1132     }
1133     return new MetaZoneIDsEnumeration(*mzIDs);
1134 }
1135
1136 StringEnumeration*
1137 TimeZoneNamesImpl::getAvailableMetaZoneIDs(const UnicodeString& tzID, UErrorCode& status) const {
1138     return TimeZoneNamesImpl::_getAvailableMetaZoneIDs(tzID, status);
1139 }
1140
1141 // static implementation of getAvailableMetaZoneIDs(const UnicodeString&, UErrorCode&)
1142 StringEnumeration*
1143 TimeZoneNamesImpl::_getAvailableMetaZoneIDs(const UnicodeString& tzID, UErrorCode& status) {
1144     if (U_FAILURE(status)) {
1145         return NULL;
1146     }
1147     const UVector* mappings = ZoneMeta::getMetazoneMappings(tzID);
1148     if (mappings == NULL) {
1149         return new MetaZoneIDsEnumeration();
1150     }
1151
1152     MetaZoneIDsEnumeration *senum = NULL;
1153     UVector* mzIDs = new UVector(NULL, uhash_compareUChars, status);
1154     if (mzIDs == NULL) {
1155         status = U_MEMORY_ALLOCATION_ERROR;
1156     }
1157     if (U_SUCCESS(status)) {
1158         U_ASSERT(mzIDs != NULL);
1159         for (int32_t i = 0; U_SUCCESS(status) && i < mappings->size(); i++) {
1160
1161             OlsonToMetaMappingEntry *map = (OlsonToMetaMappingEntry *)mappings->elementAt(i);
1162             const UChar *mzID = map->mzid;
1163             if (!mzIDs->contains((void *)mzID)) {
1164                 mzIDs->addElement((void *)mzID, status);
1165             }
1166         }
1167         if (U_SUCCESS(status)) {
1168             senum = new MetaZoneIDsEnumeration(mzIDs);
1169         } else {
1170             delete mzIDs;
1171         }
1172     }
1173     return senum;
1174 }
1175
1176 UnicodeString&
1177 TimeZoneNamesImpl::getMetaZoneID(const UnicodeString& tzID, UDate date, UnicodeString& mzID) const {
1178     return TimeZoneNamesImpl::_getMetaZoneID(tzID, date, mzID);
1179 }
1180
1181 // static implementation of getMetaZoneID
1182 UnicodeString&
1183 TimeZoneNamesImpl::_getMetaZoneID(const UnicodeString& tzID, UDate date, UnicodeString& mzID) {
1184     ZoneMeta::getMetazoneID(tzID, date, mzID);
1185     return mzID;
1186 }
1187
1188 UnicodeString&
1189 TimeZoneNamesImpl::getReferenceZoneID(const UnicodeString& mzID, const char* region, UnicodeString& tzID) const {
1190     return TimeZoneNamesImpl::_getReferenceZoneID(mzID, region, tzID);
1191 }
1192
1193 // static implementaion of getReferenceZoneID
1194 UnicodeString&
1195 TimeZoneNamesImpl::_getReferenceZoneID(const UnicodeString& mzID, const char* region, UnicodeString& tzID) {
1196     ZoneMeta::getZoneIdByMetazone(mzID, UnicodeString(region, -1, US_INV), tzID);
1197     return tzID;
1198 }
1199
1200 UnicodeString&
1201 TimeZoneNamesImpl::getMetaZoneDisplayName(const UnicodeString& mzID,
1202                                           UTimeZoneNameType type,
1203                                           UnicodeString& name) const {
1204     name.setToBogus();  // cleanup result.
1205     if (mzID.isEmpty()) {
1206         return name;
1207     }
1208
1209     ZNames *znames = NULL;
1210     TimeZoneNamesImpl *nonConstThis = const_cast<TimeZoneNamesImpl *>(this);
1211
1212     {
1213         Mutex lock(&gDataMutex);
1214         UErrorCode status = U_ZERO_ERROR;
1215         znames = nonConstThis->loadMetaZoneNames(mzID, status);
1216         if (U_FAILURE(status)) { return name; }
1217     }
1218
1219     if (znames != NULL) {
1220         const UChar* s = znames->getName(type);
1221         if (s != NULL) {
1222             name.setTo(TRUE, s, -1);
1223         }
1224     }
1225     return name;
1226 }
1227
1228 UnicodeString&
1229 TimeZoneNamesImpl::getTimeZoneDisplayName(const UnicodeString& tzID, UTimeZoneNameType type, UnicodeString& name) const {
1230     name.setToBogus();  // cleanup result.
1231     if (tzID.isEmpty()) {
1232         return name;
1233     }
1234
1235     ZNames *tznames = NULL;
1236     TimeZoneNamesImpl *nonConstThis = const_cast<TimeZoneNamesImpl *>(this);
1237
1238     {
1239         Mutex lock(&gDataMutex);
1240         UErrorCode status = U_ZERO_ERROR;
1241         tznames = nonConstThis->loadTimeZoneNames(tzID, status);
1242         if (U_FAILURE(status)) { return name; }
1243     }
1244
1245     if (tznames != NULL) {
1246         const UChar *s = tznames->getName(type);
1247         if (s != NULL) {
1248             name.setTo(TRUE, s, -1);
1249         }
1250     }
1251     return name;
1252 }
1253
1254 UnicodeString&
1255 TimeZoneNamesImpl::getExemplarLocationName(const UnicodeString& tzID, UnicodeString& name) const {
1256     name.setToBogus();  // cleanup result.
1257     const UChar* locName = NULL;
1258     ZNames *tznames = NULL;
1259     TimeZoneNamesImpl *nonConstThis = const_cast<TimeZoneNamesImpl *>(this);
1260
1261     {
1262         Mutex lock(&gDataMutex);
1263         UErrorCode status = U_ZERO_ERROR;
1264         tznames = nonConstThis->loadTimeZoneNames(tzID, status);
1265         if (U_FAILURE(status)) { return name; }
1266     }
1267
1268     if (tznames != NULL) {
1269         locName = tznames->getName(UTZNM_EXEMPLAR_LOCATION);
1270     }
1271     if (locName != NULL) {
1272         name.setTo(TRUE, locName, -1);
1273     }
1274
1275     return name;
1276 }
1277
1278
1279 // Merge the MZ_PREFIX and mzId
1280 static void mergeTimeZoneKey(const UnicodeString& mzID, char* result) {
1281     if (mzID.isEmpty()) {
1282         result[0] = '\0';
1283         return;
1284     }
1285
1286     char mzIdChar[ZID_KEY_MAX + 1];
1287     int32_t keyLen;
1288     int32_t prefixLen = uprv_strlen(gMZPrefix);
1289     keyLen = mzID.extract(0, mzID.length(), mzIdChar, ZID_KEY_MAX + 1, US_INV);
1290     uprv_memcpy((void *)result, (void *)gMZPrefix, prefixLen);
1291     uprv_memcpy((void *)(result + prefixLen), (void *)mzIdChar, keyLen);
1292     result[keyLen + prefixLen] = '\0';
1293 }
1294
1295 /*
1296  * This method updates the cache and must be called with a lock
1297  */
1298 ZNames*
1299 TimeZoneNamesImpl::loadMetaZoneNames(const UnicodeString& mzID, UErrorCode& status) {
1300     if (U_FAILURE(status)) { return NULL; }
1301     U_ASSERT(mzID.length() <= ZID_KEY_MAX - MZ_PREFIX_LEN);
1302
1303     UChar mzIDKey[ZID_KEY_MAX + 1];
1304     mzID.extract(mzIDKey, ZID_KEY_MAX + 1, status);
1305     U_ASSERT(U_SUCCESS(status));   // already checked length above
1306     mzIDKey[mzID.length()] = 0;
1307
1308     void* mznames = uhash_get(fMZNamesMap, mzIDKey);
1309     if (mznames == NULL) {
1310         ZNames::ZNamesLoader loader;
1311         loader.loadMetaZone(fZoneStrings, mzID, status);
1312         mznames = ZNames::createMetaZoneAndPutInCache(fMZNamesMap, loader.getNames(), mzID, status);
1313         if (U_FAILURE(status)) { return NULL; }
1314     }
1315
1316     if (mznames != EMPTY) {
1317         return (ZNames*)mznames;
1318     } else {
1319         return NULL;
1320     }
1321 }
1322
1323 /*
1324  * This method updates the cache and must be called with a lock
1325  */
1326 ZNames*
1327 TimeZoneNamesImpl::loadTimeZoneNames(const UnicodeString& tzID, UErrorCode& status) {
1328     if (U_FAILURE(status)) { return NULL; }
1329     U_ASSERT(tzID.length() <= ZID_KEY_MAX);
1330
1331     UChar tzIDKey[ZID_KEY_MAX + 1];
1332     int32_t tzIDKeyLen = tzID.extract(tzIDKey, ZID_KEY_MAX + 1, status);
1333     U_ASSERT(U_SUCCESS(status));   // already checked length above
1334     tzIDKey[tzIDKeyLen] = 0;
1335
1336     void *tznames = uhash_get(fTZNamesMap, tzIDKey);
1337     if (tznames == NULL) {
1338         ZNames::ZNamesLoader loader;
1339         loader.loadTimeZone(fZoneStrings, tzID, status);
1340         tznames = ZNames::createTimeZoneAndPutInCache(fTZNamesMap, loader.getNames(), tzID, status);
1341         if (U_FAILURE(status)) { return NULL; }
1342     }
1343
1344     // tznames is never EMPTY
1345     return (ZNames*)tznames;
1346 }
1347
1348 TimeZoneNames::MatchInfoCollection*
1349 TimeZoneNamesImpl::find(const UnicodeString& text, int32_t start, uint32_t types, UErrorCode& status) const {
1350     ZNameSearchHandler handler(types);
1351     TimeZoneNames::MatchInfoCollection* matches;
1352     TimeZoneNamesImpl* nonConstThis = const_cast<TimeZoneNamesImpl*>(this);
1353
1354     // Synchronize so that data is not loaded multiple times.
1355     // TODO: Consider more fine-grained synchronization.
1356     {
1357         Mutex lock(&gDataMutex);
1358
1359         // First try of lookup.
1360         matches = doFind(handler, text, start, status);
1361         if (U_FAILURE(status)) { return NULL; }
1362         if (matches != NULL) {
1363             return matches;
1364         }
1365
1366         // All names are not yet loaded into the trie.
1367         // We may have loaded names for formatting several time zones,
1368         // and might be parsing one of those.
1369         // Populate the parsing trie from all of the already-loaded names.
1370         nonConstThis->addAllNamesIntoTrie(status);
1371
1372         // Second try of lookup.
1373         matches = doFind(handler, text, start, status);
1374         if (U_FAILURE(status)) { return NULL; }
1375         if (matches != NULL) {
1376             return matches;
1377         }
1378
1379         // There are still some names we haven't loaded into the trie yet.
1380         // Load everything now.
1381         nonConstThis->internalLoadAllDisplayNames(status);
1382         nonConstThis->addAllNamesIntoTrie(status);
1383         nonConstThis->fNamesTrieFullyLoaded = TRUE;
1384         if (U_FAILURE(status)) { return NULL; }
1385
1386         // Third try: we must return this one.
1387         return doFind(handler, text, start, status);
1388     }
1389 }
1390
1391 TimeZoneNames::MatchInfoCollection*
1392 TimeZoneNamesImpl::doFind(ZNameSearchHandler& handler,
1393         const UnicodeString& text, int32_t start, UErrorCode& status) const {
1394
1395     fNamesTrie.search(text, start, (TextTrieMapSearchResultHandler *)&handler, status);
1396     if (U_FAILURE(status)) { return NULL; }
1397
1398     int32_t maxLen = 0;
1399     TimeZoneNames::MatchInfoCollection* matches = handler.getMatches(maxLen);
1400     if (matches != NULL && ((maxLen == (text.length() - start)) || fNamesTrieFullyLoaded)) {
1401         // perfect match, or no more names available
1402         return matches;
1403     }
1404     delete matches;
1405     return NULL;
1406 }
1407
1408 // Caller must synchronize.
1409 void TimeZoneNamesImpl::addAllNamesIntoTrie(UErrorCode& status) {
1410     if (U_FAILURE(status)) return;
1411     int32_t pos;
1412     const UHashElement* element;
1413
1414     pos = UHASH_FIRST;
1415     while ((element = uhash_nextElement(fMZNamesMap, &pos)) != NULL) {
1416         if (element->value.pointer == EMPTY) { continue; }
1417         UChar* mzID = (UChar*) element->key.pointer;
1418         ZNames* znames = (ZNames*) element->value.pointer;
1419         znames->addAsMetaZoneIntoTrie(mzID, fNamesTrie, status);
1420         if (U_FAILURE(status)) { return; }
1421     }
1422
1423     pos = UHASH_FIRST;
1424     while ((element = uhash_nextElement(fTZNamesMap, &pos)) != NULL) {
1425         if (element->value.pointer == EMPTY) { continue; }
1426         UChar* tzID = (UChar*) element->key.pointer;
1427         ZNames* znames = (ZNames*) element->value.pointer;
1428         znames->addAsTimeZoneIntoTrie(tzID, fNamesTrie, status);
1429         if (U_FAILURE(status)) { return; }
1430     }
1431 }
1432
1433 U_CDECL_BEGIN
1434 static void U_CALLCONV
1435 deleteZNamesLoader(void* obj) {
1436     if (obj == DUMMY_LOADER) { return; }
1437     const ZNames::ZNamesLoader* loader = (const ZNames::ZNamesLoader*) obj;
1438     delete loader;
1439 }
1440 U_CDECL_END
1441
1442 struct TimeZoneNamesImpl::ZoneStringsLoader : public ResourceSink {
1443     TimeZoneNamesImpl& tzn;
1444     UHashtable* keyToLoader;
1445
1446     ZoneStringsLoader(TimeZoneNamesImpl& _tzn, UErrorCode& status)
1447             : tzn(_tzn) {
1448         keyToLoader = uhash_open(uhash_hashChars, uhash_compareChars, NULL, &status);
1449         if (U_FAILURE(status)) { return; }
1450         uhash_setKeyDeleter(keyToLoader, uprv_free);
1451         uhash_setValueDeleter(keyToLoader, deleteZNamesLoader);
1452     }
1453     virtual ~ZoneStringsLoader();
1454
1455     void* createKey(const char* key, UErrorCode& status) {
1456         int32_t len = sizeof(char) * (uprv_strlen(key) + 1);
1457         char* newKey = (char*) uprv_malloc(len);
1458         if (newKey == NULL) {
1459             status = U_MEMORY_ALLOCATION_ERROR;
1460             return NULL;
1461         }
1462         uprv_memcpy(newKey, key, len);
1463         newKey[len-1] = '\0';
1464         return (void*) newKey;
1465     }
1466
1467     UBool isMetaZone(const char* key) {
1468         return (uprv_strlen(key) >= MZ_PREFIX_LEN && uprv_memcmp(key, gMZPrefix, MZ_PREFIX_LEN) == 0);
1469     }
1470
1471     UnicodeString mzIDFromKey(const char* key) {
1472         return UnicodeString(key + MZ_PREFIX_LEN, uprv_strlen(key) - MZ_PREFIX_LEN, US_INV);
1473     }
1474
1475     UnicodeString tzIDFromKey(const char* key) {
1476         UnicodeString tzID(key, -1, US_INV);
1477         // Replace all colons ':' with slashes '/'
1478         for (int i=0; i<tzID.length(); i++) {
1479             if (tzID.charAt(i) == 0x003A) {
1480                 tzID.setCharAt(i, 0x002F);
1481             }
1482         }
1483         return tzID;
1484     }
1485
1486     void load(UErrorCode& status) {
1487         ures_getAllItemsWithFallback(tzn.fZoneStrings, "", *this, status);
1488         if (U_FAILURE(status)) { return; }
1489
1490         int32_t pos = UHASH_FIRST;
1491         const UHashElement* element;
1492         while ((element = uhash_nextElement(keyToLoader, &pos)) != NULL) {
1493             if (element->value.pointer == DUMMY_LOADER) { continue; }
1494             ZNames::ZNamesLoader* loader = (ZNames::ZNamesLoader*) element->value.pointer;
1495             char* key = (char*) element->key.pointer;
1496
1497             if (isMetaZone(key)) {
1498                 UnicodeString mzID = mzIDFromKey(key);
1499                 ZNames::createMetaZoneAndPutInCache(tzn.fMZNamesMap, loader->getNames(), mzID, status);
1500             } else {
1501                 UnicodeString tzID = tzIDFromKey(key);
1502                 ZNames::createTimeZoneAndPutInCache(tzn.fTZNamesMap, loader->getNames(), tzID, status);
1503             }
1504             if (U_FAILURE(status)) { return; }
1505         }
1506     }
1507
1508     void consumeNamesTable(const char *key, ResourceValue &value, UBool noFallback,
1509             UErrorCode &status) {
1510         if (U_FAILURE(status)) { return; }
1511
1512         void* loader = uhash_get(keyToLoader, key);
1513         if (loader == NULL) {
1514             if (isMetaZone(key)) {
1515                 UnicodeString mzID = mzIDFromKey(key);
1516                 void* cacheVal = uhash_get(tzn.fMZNamesMap, mzID.getTerminatedBuffer());
1517                 if (cacheVal != NULL) {
1518                     // We have already loaded the names for this meta zone.
1519                     loader = (void*) DUMMY_LOADER;
1520                 } else {
1521                     loader = (void*) new ZNames::ZNamesLoader();
1522                     if (loader == NULL) {
1523                         status = U_MEMORY_ALLOCATION_ERROR;
1524                         return;
1525                     }
1526                 }
1527             } else {
1528                 UnicodeString tzID = tzIDFromKey(key);
1529                 void* cacheVal = uhash_get(tzn.fTZNamesMap, tzID.getTerminatedBuffer());
1530                 if (cacheVal != NULL) {
1531                     // We have already loaded the names for this time zone.
1532                     loader = (void*) DUMMY_LOADER;
1533                 } else {
1534                     loader = (void*) new ZNames::ZNamesLoader();
1535                     if (loader == NULL) {
1536                         status = U_MEMORY_ALLOCATION_ERROR;
1537                         return;
1538                     }
1539                 }
1540             }
1541
1542             void* newKey = createKey(key, status);
1543             if (U_FAILURE(status)) {
1544                 deleteZNamesLoader(loader);
1545                 return;
1546             }
1547
1548             uhash_put(keyToLoader, newKey, loader, &status);
1549             if (U_FAILURE(status)) { return; }
1550         }
1551
1552         if (loader != DUMMY_LOADER) {
1553             // Let the ZNamesLoader consume the names table.
1554             ((ZNames::ZNamesLoader*)loader)->put(key, value, noFallback, status);
1555         }
1556     }
1557
1558     virtual void put(const char *key, ResourceValue &value, UBool noFallback,
1559             UErrorCode &status) {
1560         ResourceTable timeZonesTable = value.getTable(status);
1561         if (U_FAILURE(status)) { return; }
1562         for (int32_t i = 0; timeZonesTable.getKeyAndValue(i, key, value); ++i) {
1563             U_ASSERT(!value.isNoInheritanceMarker());
1564             if (value.getType() == URES_TABLE) {
1565                 consumeNamesTable(key, value, noFallback, status);
1566             } else {
1567                 // Ignore fields that aren't tables (e.g., fallbackFormat and regionFormatStandard).
1568                 // All time zone fields are tables.
1569             }
1570             if (U_FAILURE(status)) { return; }
1571         }
1572     }
1573 };
1574
1575 // Virtual destructors must be defined out of line.
1576 TimeZoneNamesImpl::ZoneStringsLoader::~ZoneStringsLoader() {
1577     uhash_close(keyToLoader);
1578 }
1579
1580 void TimeZoneNamesImpl::loadAllDisplayNames(UErrorCode& status) {
1581     if (U_FAILURE(status)) return;
1582
1583     {
1584         Mutex lock(&gDataMutex);
1585         internalLoadAllDisplayNames(status);
1586     }
1587 }
1588
1589 void TimeZoneNamesImpl::getDisplayNames(const UnicodeString& tzID,
1590         const UTimeZoneNameType types[], int32_t numTypes,
1591         UDate date, UnicodeString dest[], UErrorCode& status) const {
1592     if (U_FAILURE(status)) return;
1593
1594     if (tzID.isEmpty()) { return; }
1595     void* tznames = NULL;
1596     void* mznames = NULL;
1597     TimeZoneNamesImpl *nonConstThis = const_cast<TimeZoneNamesImpl*>(this);
1598
1599     // Load the time zone strings
1600     {
1601         Mutex lock(&gDataMutex);
1602         tznames = (void*) nonConstThis->loadTimeZoneNames(tzID, status);
1603         if (U_FAILURE(status)) { return; }
1604     }
1605     U_ASSERT(tznames != NULL);
1606
1607     // Load the values into the dest array
1608     for (int i = 0; i < numTypes; i++) {
1609         UTimeZoneNameType type = types[i];
1610         const UChar* name = ((ZNames*)tznames)->getName(type);
1611         if (name == NULL) {
1612             if (mznames == NULL) {
1613                 // Load the meta zone name
1614                 UnicodeString mzID;
1615                 getMetaZoneID(tzID, date, mzID);
1616                 if (mzID.isEmpty()) {
1617                     mznames = (void*) EMPTY;
1618                 } else {
1619                     // Load the meta zone strings
1620                     // Mutex is scoped to the "else" statement
1621                     Mutex lock(&gDataMutex);
1622                     mznames = (void*) nonConstThis->loadMetaZoneNames(mzID, status);
1623                     if (U_FAILURE(status)) { return; }
1624                     // Note: when the metazone doesn't exist, in Java, loadMetaZoneNames returns
1625                     // a dummy object instead of NULL.
1626                     if (mznames == NULL) {
1627                         mznames = (void*) EMPTY;
1628                     }
1629                 }
1630             }
1631             U_ASSERT(mznames != NULL);
1632             if (mznames != EMPTY) {
1633                 name = ((ZNames*)mznames)->getName(type);
1634             }
1635         }
1636         if (name != NULL) {
1637             dest[i].setTo(TRUE, name, -1);
1638         } else {
1639             dest[i].setToBogus();
1640         }
1641     }
1642 }
1643
1644 // Caller must synchronize.
1645 void TimeZoneNamesImpl::internalLoadAllDisplayNames(UErrorCode& status) {
1646     if (!fNamesFullyLoaded) {
1647         fNamesFullyLoaded = TRUE;
1648
1649         ZoneStringsLoader loader(*this, status);
1650         loader.load(status);
1651         if (U_FAILURE(status)) { return; }
1652
1653         const UnicodeString *id;
1654
1655         // load strings for all zones
1656         StringEnumeration *tzIDs = TimeZone::createTimeZoneIDEnumeration(
1657             UCAL_ZONE_TYPE_CANONICAL, NULL, NULL, status);
1658         if (U_SUCCESS(status)) {
1659             while ((id = tzIDs->snext(status)) != NULL) {
1660                 if (U_FAILURE(status)) {
1661                     break;
1662                 }
1663                 UnicodeString copy(*id);
1664                 void* value = uhash_get(fTZNamesMap, copy.getTerminatedBuffer());
1665                 if (value == NULL) {
1666                     // loadStrings also loads related metazone strings
1667                     loadStrings(*id, status);
1668                 }
1669             }
1670         }
1671         if (tzIDs != NULL) {
1672             delete tzIDs;
1673         }
1674     }
1675 }
1676
1677
1678
1679 static const UChar gEtcPrefix[]         = { 0x45, 0x74, 0x63, 0x2F }; // "Etc/"
1680 static const int32_t gEtcPrefixLen      = 4;
1681 static const UChar gSystemVPrefix[]     = { 0x53, 0x79, 0x73, 0x74, 0x65, 0x6D, 0x56, 0x2F }; // "SystemV/
1682 static const int32_t gSystemVPrefixLen  = 8;
1683 static const UChar gRiyadh8[]           = { 0x52, 0x69, 0x79, 0x61, 0x64, 0x68, 0x38 }; // "Riyadh8"
1684 static const int32_t gRiyadh8Len       = 7;
1685
1686 UnicodeString& U_EXPORT2
1687 TimeZoneNamesImpl::getDefaultExemplarLocationName(const UnicodeString& tzID, UnicodeString& name) {
1688     if (tzID.isEmpty() || tzID.startsWith(gEtcPrefix, gEtcPrefixLen)
1689         || tzID.startsWith(gSystemVPrefix, gSystemVPrefixLen) || tzID.indexOf(gRiyadh8, gRiyadh8Len, 0) > 0) {
1690         name.setToBogus();
1691         return name;
1692     }
1693
1694     int32_t sep = tzID.lastIndexOf((UChar)0x2F /* '/' */);
1695     if (sep > 0 && sep + 1 < tzID.length()) {
1696         name.setTo(tzID, sep + 1);
1697         name.findAndReplace(UnicodeString((UChar)0x5f /* _ */),
1698                             UnicodeString((UChar)0x20 /* space */));
1699     } else {
1700         name.setToBogus();
1701     }
1702     return name;
1703 }
1704
1705 // ---------------------------------------------------
1706 // TZDBTimeZoneNames and its supporting classes
1707 //
1708 // TZDBTimeZoneNames is an implementation class of
1709 // TimeZoneNames holding the IANA tz database abbreviations.
1710 // ---------------------------------------------------
1711
1712 class TZDBNames : public UMemory {
1713 public:
1714     virtual ~TZDBNames();
1715
1716     static TZDBNames* createInstance(UResourceBundle* rb, const char* key);
1717     const UChar* getName(UTimeZoneNameType type) const;
1718     const char** getParseRegions(int32_t& numRegions) const;
1719
1720 protected:
1721     TZDBNames(const UChar** names, char** regions, int32_t numRegions);
1722
1723 private:
1724     const UChar** fNames;
1725     char** fRegions;
1726     int32_t fNumRegions;
1727 };
1728
1729 TZDBNames::TZDBNames(const UChar** names, char** regions, int32_t numRegions)
1730     :   fNames(names),
1731         fRegions(regions),
1732         fNumRegions(numRegions) {
1733 }
1734
1735 TZDBNames::~TZDBNames() {
1736     if (fNames != NULL) {
1737         uprv_free(fNames);
1738     }
1739     if (fRegions != NULL) {
1740         char **p = fRegions;
1741         for (int32_t i = 0; i < fNumRegions; p++, i++) {
1742             uprv_free(*p);
1743         }
1744         uprv_free(fRegions);
1745     }
1746 }
1747
1748 TZDBNames*
1749 TZDBNames::createInstance(UResourceBundle* rb, const char* key) {
1750     if (rb == NULL || key == NULL || *key == 0) {
1751         return NULL;
1752     }
1753
1754     UErrorCode status = U_ZERO_ERROR;
1755
1756     const UChar **names = NULL;
1757     char** regions = NULL;
1758     int32_t numRegions = 0;
1759
1760     int32_t len = 0;
1761
1762     UResourceBundle* rbTable = NULL;
1763     rbTable = ures_getByKey(rb, key, rbTable, &status);
1764     if (U_FAILURE(status)) {
1765         return NULL;
1766     }
1767
1768     names = (const UChar **)uprv_malloc(sizeof(const UChar*) * TZDBNAMES_KEYS_SIZE);
1769     UBool isEmpty = TRUE;
1770     if (names != NULL) {
1771         for (int32_t i = 0; i < TZDBNAMES_KEYS_SIZE; i++) {
1772             status = U_ZERO_ERROR;
1773             const UChar *value = ures_getStringByKey(rbTable, TZDBNAMES_KEYS[i], &len, &status);
1774             if (U_FAILURE(status) || len == 0) {
1775                 names[i] = NULL;
1776             } else {
1777                 names[i] = value;
1778                 isEmpty = FALSE;
1779             }
1780         }
1781     }
1782
1783     if (isEmpty) {
1784         if (names != NULL) {
1785             uprv_free(names);
1786         }
1787         return NULL;
1788     }
1789
1790     UResourceBundle *regionsRes = ures_getByKey(rbTable, "parseRegions", NULL, &status);
1791     UBool regionError = FALSE;
1792     if (U_SUCCESS(status)) {
1793         numRegions = ures_getSize(regionsRes);
1794         if (numRegions > 0) {
1795             regions = (char**)uprv_malloc(sizeof(char*) * numRegions);
1796             if (regions != NULL) {
1797                 char **pRegion = regions;
1798                 for (int32_t i = 0; i < numRegions; i++, pRegion++) {
1799                     *pRegion = NULL;
1800                 }
1801                 // filling regions
1802                 pRegion = regions;
1803                 for (int32_t i = 0; i < numRegions; i++, pRegion++) {
1804                     status = U_ZERO_ERROR;
1805                     const UChar *uregion = ures_getStringByIndex(regionsRes, i, &len, &status);
1806                     if (U_FAILURE(status)) {
1807                         regionError = TRUE;
1808                         break;
1809                     }
1810                     *pRegion = (char*)uprv_malloc(sizeof(char) * (len + 1));
1811                     if (*pRegion == NULL) {
1812                         regionError = TRUE;
1813                         break;
1814                     }
1815                     u_UCharsToChars(uregion, *pRegion, len);
1816                     (*pRegion)[len] = 0;
1817                 }
1818             }
1819         }
1820     }
1821     ures_close(regionsRes);
1822     ures_close(rbTable);
1823
1824     if (regionError) {
1825         if (names != NULL) {
1826             uprv_free(names);
1827         }
1828         if (regions != NULL) {
1829             char **p = regions;
1830             for (int32_t i = 0; i < numRegions; p++, i++) {
1831                 uprv_free(*p);
1832             }
1833             uprv_free(regions);
1834         }
1835         return NULL;
1836     }
1837
1838     return new TZDBNames(names, regions, numRegions);
1839 }
1840
1841 const UChar*
1842 TZDBNames::getName(UTimeZoneNameType type) const {
1843     if (fNames == NULL) {
1844         return NULL;
1845     }
1846     const UChar *name = NULL;
1847     switch(type) {
1848     case UTZNM_SHORT_STANDARD:
1849         name = fNames[0];
1850         break;
1851     case UTZNM_SHORT_DAYLIGHT:
1852         name = fNames[1];
1853         break;
1854     default:
1855         name = NULL;
1856     }
1857     return name;
1858 }
1859
1860 const char**
1861 TZDBNames::getParseRegions(int32_t& numRegions) const {
1862     if (fRegions == NULL) {
1863         numRegions = 0;
1864     } else {
1865         numRegions = fNumRegions;
1866     }
1867     return (const char**)fRegions;
1868 }
1869
1870 U_CDECL_BEGIN
1871 /**
1872  * TZDBNameInfo stores metazone name information for the IANA abbreviations
1873  * in the trie
1874  */
1875 typedef struct TZDBNameInfo {
1876     const UChar*        mzID;
1877     UTimeZoneNameType   type;
1878     UBool               ambiguousType;
1879     const char**        parseRegions;
1880     int32_t             nRegions;
1881 } TZDBNameInfo;
1882 U_CDECL_END
1883
1884
1885 class TZDBNameSearchHandler : public TextTrieMapSearchResultHandler {
1886 public:
1887     TZDBNameSearchHandler(uint32_t types, const char* region);
1888     virtual ~TZDBNameSearchHandler();
1889
1890     UBool handleMatch(int32_t matchLength, const CharacterNode *node, UErrorCode &status);
1891     TimeZoneNames::MatchInfoCollection* getMatches(int32_t& maxMatchLen);
1892
1893 private:
1894     uint32_t fTypes;
1895     int32_t fMaxMatchLen;
1896     TimeZoneNames::MatchInfoCollection* fResults;
1897     const char* fRegion;
1898 };
1899
1900 TZDBNameSearchHandler::TZDBNameSearchHandler(uint32_t types, const char* region)
1901 : fTypes(types), fMaxMatchLen(0), fResults(NULL), fRegion(region) {
1902 }
1903
1904 TZDBNameSearchHandler::~TZDBNameSearchHandler() {
1905     if (fResults != NULL) {
1906         delete fResults;
1907     }
1908 }
1909
1910 UBool
1911 TZDBNameSearchHandler::handleMatch(int32_t matchLength, const CharacterNode *node, UErrorCode &status) {
1912     if (U_FAILURE(status)) {
1913         return FALSE;
1914     }
1915
1916     TZDBNameInfo *match = NULL;
1917     TZDBNameInfo *defaultRegionMatch = NULL;
1918
1919     if (node->hasValues()) {
1920         int32_t valuesCount = node->countValues();
1921         for (int32_t i = 0; i < valuesCount; i++) {
1922             TZDBNameInfo *ninfo = (TZDBNameInfo *)node->getValue(i);
1923             if (ninfo == NULL) {
1924                 continue;
1925             }
1926             if ((ninfo->type & fTypes) != 0) {
1927                 // Some tz database abbreviations are ambiguous. For example,
1928                 // CST means either Central Standard Time or China Standard Time.
1929                 // Unlike CLDR time zone display names, this implementation
1930                 // does not use unique names. And TimeZoneFormat does not expect
1931                 // multiple results returned for the same time zone type.
1932                 // For this reason, this implementation resolve one among same
1933                 // zone type with a same name at this level.
1934                 if (ninfo->parseRegions == NULL) {
1935                     // parseRegions == null means this is the default metazone
1936                     // mapping for the abbreviation.
1937                     if (defaultRegionMatch == NULL) {
1938                         match = defaultRegionMatch = ninfo;
1939                     }
1940                 } else {
1941                     UBool matchRegion = FALSE;
1942                     // non-default metazone mapping for an abbreviation
1943                     // comes with applicable regions. For example, the default
1944                     // metazone mapping for "CST" is America_Central,
1945                     // but if region is one of CN/MO/TW, "CST" is parsed
1946                     // as metazone China (China Standard Time).
1947                     for (int32_t i = 0; i < ninfo->nRegions; i++) {
1948                         const char *region = ninfo->parseRegions[i];
1949                         if (uprv_strcmp(fRegion, region) == 0) {
1950                             match = ninfo;
1951                             matchRegion = TRUE;
1952                             break;
1953                         }
1954                     }
1955                     if (matchRegion) {
1956                         break;
1957                     }
1958                     if (match == NULL) {
1959                         match = ninfo;
1960                     }
1961                 }
1962             }
1963         }
1964
1965         if (match != NULL) {
1966             UTimeZoneNameType ntype = match->type;
1967             // Note: Workaround for duplicated standard/daylight names
1968             // The tz database contains a few zones sharing a
1969             // same name for both standard time and daylight saving
1970             // time. For example, Australia/Sydney observes DST,
1971             // but "EST" is used for both standard and daylight.
1972             // When both SHORT_STANDARD and SHORT_DAYLIGHT are included
1973             // in the find operation, we cannot tell which one was
1974             // actually matched.
1975             // TimeZoneFormat#parse returns a matched name type (standard
1976             // or daylight) and DateFormat implementation uses the info to
1977             // to adjust actual time. To avoid false type information,
1978             // this implementation replaces the name type with SHORT_GENERIC.
1979             if (match->ambiguousType
1980                     && (ntype == UTZNM_SHORT_STANDARD || ntype == UTZNM_SHORT_DAYLIGHT)
1981                     && (fTypes & UTZNM_SHORT_STANDARD) != 0
1982                     && (fTypes & UTZNM_SHORT_DAYLIGHT) != 0) {
1983                 ntype = UTZNM_SHORT_GENERIC;
1984             }
1985
1986             if (fResults == NULL) {
1987                 fResults = new TimeZoneNames::MatchInfoCollection();
1988                 if (fResults == NULL) {
1989                     status = U_MEMORY_ALLOCATION_ERROR;
1990                 }
1991             }
1992             if (U_SUCCESS(status)) {
1993                 U_ASSERT(fResults != NULL);
1994                 U_ASSERT(match->mzID != NULL);
1995                 fResults->addMetaZone(ntype, matchLength, UnicodeString(match->mzID, -1), status);
1996                 if (U_SUCCESS(status) && matchLength > fMaxMatchLen) {
1997                     fMaxMatchLen = matchLength;
1998                 }
1999             }
2000         }
2001     }
2002     return TRUE;
2003 }
2004
2005 TimeZoneNames::MatchInfoCollection*
2006 TZDBNameSearchHandler::getMatches(int32_t& maxMatchLen) {
2007     // give the ownership to the caller
2008     TimeZoneNames::MatchInfoCollection* results = fResults;
2009     maxMatchLen = fMaxMatchLen;
2010
2011     // reset
2012     fResults = NULL;
2013     fMaxMatchLen = 0;
2014     return results;
2015 }
2016
2017 U_CDECL_BEGIN
2018 /**
2019  * Deleter for TZDBNames
2020  */
2021 static void U_CALLCONV
2022 deleteTZDBNames(void *obj) {
2023     if (obj != EMPTY) {
2024         delete (TZDBNames *)obj;
2025     }
2026 }
2027
2028 static void U_CALLCONV initTZDBNamesMap(UErrorCode &status) {
2029     gTZDBNamesMap = uhash_open(uhash_hashUChars, uhash_compareUChars, NULL, &status);
2030     if (U_FAILURE(status)) {
2031         gTZDBNamesMap = NULL;
2032         return;
2033     }
2034     // no key deleters for tzdb name maps
2035     uhash_setValueDeleter(gTZDBNamesMap, deleteTZDBNames);
2036     ucln_i18n_registerCleanup(UCLN_I18N_TZDBTIMEZONENAMES, tzdbTimeZoneNames_cleanup);
2037 }
2038
2039 /**
2040  * Deleter for TZDBNameInfo
2041  */
2042 static void U_CALLCONV
2043 deleteTZDBNameInfo(void *obj) {
2044     if (obj != NULL) {
2045         uprv_free(obj);
2046     }
2047 }
2048
2049 static void U_CALLCONV prepareFind(UErrorCode &status) {
2050     if (U_FAILURE(status)) {
2051         return;
2052     }
2053     gTZDBNamesTrie = new TextTrieMap(TRUE, deleteTZDBNameInfo);
2054     if (gTZDBNamesTrie == NULL) {
2055         status = U_MEMORY_ALLOCATION_ERROR;
2056         return;
2057     }
2058
2059     const UnicodeString *mzID;
2060     StringEnumeration *mzIDs = TimeZoneNamesImpl::_getAvailableMetaZoneIDs(status);
2061     if (U_SUCCESS(status)) {
2062         while ((mzID = mzIDs->snext(status)) && U_SUCCESS(status)) {
2063             const TZDBNames *names = TZDBTimeZoneNames::getMetaZoneNames(*mzID, status);
2064             if (U_FAILURE(status)) {
2065                 break;
2066             }
2067             if (names == NULL) {
2068                 continue;
2069             }
2070             const UChar *std = names->getName(UTZNM_SHORT_STANDARD);
2071             const UChar *dst = names->getName(UTZNM_SHORT_DAYLIGHT);
2072             if (std == NULL && dst == NULL) {
2073                 continue;
2074             }
2075             int32_t numRegions = 0;
2076             const char **parseRegions = names->getParseRegions(numRegions);
2077
2078             // The tz database contains a few zones sharing a
2079             // same name for both standard time and daylight saving
2080             // time. For example, Australia/Sydney observes DST,
2081             // but "EST" is used for both standard and daylight.
2082             // we need to store the information for later processing.
2083             UBool ambiguousType = (std != NULL && dst != NULL && u_strcmp(std, dst) == 0);
2084
2085             const UChar *uMzID = ZoneMeta::findMetaZoneID(*mzID);
2086             if (std != NULL) {
2087                 TZDBNameInfo *stdInf = (TZDBNameInfo *)uprv_malloc(sizeof(TZDBNameInfo));
2088                 if (stdInf == NULL) {
2089                     status = U_MEMORY_ALLOCATION_ERROR;
2090                     break;
2091                 }
2092                 stdInf->mzID = uMzID;
2093                 stdInf->type = UTZNM_SHORT_STANDARD;
2094                 stdInf->ambiguousType = ambiguousType;
2095                 stdInf->parseRegions = parseRegions;
2096                 stdInf->nRegions = numRegions;
2097                 gTZDBNamesTrie->put(std, stdInf, status);
2098             }
2099             if (U_SUCCESS(status) && dst != NULL) {
2100                 TZDBNameInfo *dstInf = (TZDBNameInfo *)uprv_malloc(sizeof(TZDBNameInfo));
2101                 if (dstInf == NULL) {
2102                     status = U_MEMORY_ALLOCATION_ERROR;
2103                     break;
2104                 }
2105                 dstInf->mzID = uMzID;
2106                 dstInf->type = UTZNM_SHORT_DAYLIGHT;
2107                 dstInf->ambiguousType = ambiguousType;
2108                 dstInf->parseRegions = parseRegions;
2109                 dstInf->nRegions = numRegions;
2110                 gTZDBNamesTrie->put(dst, dstInf, status);
2111             }
2112         }
2113     }
2114     delete mzIDs;
2115
2116     if (U_FAILURE(status)) {
2117         delete gTZDBNamesTrie;
2118         gTZDBNamesTrie = NULL;
2119         return;
2120     }
2121
2122     ucln_i18n_registerCleanup(UCLN_I18N_TZDBTIMEZONENAMES, tzdbTimeZoneNames_cleanup);
2123 }
2124
2125 U_CDECL_END
2126
2127 TZDBTimeZoneNames::TZDBTimeZoneNames(const Locale& locale)
2128 : fLocale(locale) {
2129     UBool useWorld = TRUE;
2130     const char* region = fLocale.getCountry();
2131     int32_t regionLen = uprv_strlen(region);
2132     if (regionLen == 0) {
2133         UErrorCode status = U_ZERO_ERROR;
2134         char loc[ULOC_FULLNAME_CAPACITY];
2135         uloc_addLikelySubtags(fLocale.getName(), loc, sizeof(loc), &status);
2136         regionLen = uloc_getCountry(loc, fRegion, sizeof(fRegion), &status);
2137         if (U_SUCCESS(status) && regionLen < (int32_t)sizeof(fRegion)) {
2138             useWorld = FALSE;
2139         }
2140     } else if (regionLen < (int32_t)sizeof(fRegion)) {
2141         uprv_strcpy(fRegion, region);
2142         useWorld = FALSE;
2143     }
2144     if (useWorld) {
2145         uprv_strcpy(fRegion, "001");
2146     }
2147 }
2148
2149 TZDBTimeZoneNames::~TZDBTimeZoneNames() {
2150 }
2151
2152 UBool
2153 TZDBTimeZoneNames::operator==(const TimeZoneNames& other) const {
2154     if (this == &other) {
2155         return TRUE;
2156     }
2157     // No implementation for now
2158     return FALSE;
2159 }
2160
2161 TimeZoneNames*
2162 TZDBTimeZoneNames::clone() const {
2163     return new TZDBTimeZoneNames(fLocale);
2164 }
2165
2166 StringEnumeration*
2167 TZDBTimeZoneNames::getAvailableMetaZoneIDs(UErrorCode& status) const {
2168     return TimeZoneNamesImpl::_getAvailableMetaZoneIDs(status);
2169 }
2170
2171 StringEnumeration*
2172 TZDBTimeZoneNames::getAvailableMetaZoneIDs(const UnicodeString& tzID, UErrorCode& status) const {
2173     return TimeZoneNamesImpl::_getAvailableMetaZoneIDs(tzID, status);
2174 }
2175
2176 UnicodeString&
2177 TZDBTimeZoneNames::getMetaZoneID(const UnicodeString& tzID, UDate date, UnicodeString& mzID) const {
2178     return TimeZoneNamesImpl::_getMetaZoneID(tzID, date, mzID);
2179 }
2180
2181 UnicodeString&
2182 TZDBTimeZoneNames::getReferenceZoneID(const UnicodeString& mzID, const char* region, UnicodeString& tzID) const {
2183     return TimeZoneNamesImpl::_getReferenceZoneID(mzID, region, tzID);
2184 }
2185
2186 UnicodeString&
2187 TZDBTimeZoneNames::getMetaZoneDisplayName(const UnicodeString& mzID,
2188                                           UTimeZoneNameType type,
2189                                           UnicodeString& name) const {
2190     name.setToBogus();
2191     if (mzID.isEmpty()) {
2192         return name;
2193     }
2194
2195     UErrorCode status = U_ZERO_ERROR;
2196     const TZDBNames *tzdbNames = TZDBTimeZoneNames::getMetaZoneNames(mzID, status);
2197     if (U_SUCCESS(status)) {
2198         if (tzdbNames != NULL) {
2199             const UChar *s = tzdbNames->getName(type);
2200             if (s != NULL) {
2201                 name.setTo(TRUE, s, -1);
2202             }
2203         }
2204     }
2205
2206     return name;
2207 }
2208
2209 UnicodeString&
2210 TZDBTimeZoneNames::getTimeZoneDisplayName(const UnicodeString& /* tzID */, UTimeZoneNameType /* type */, UnicodeString& name) const {
2211     // No abbreviations associated a zone directly for now.
2212     name.setToBogus();
2213     return name;
2214 }
2215
2216 TZDBTimeZoneNames::MatchInfoCollection*
2217 TZDBTimeZoneNames::find(const UnicodeString& text, int32_t start, uint32_t types, UErrorCode& status) const {
2218     umtx_initOnce(gTZDBNamesTrieInitOnce, &prepareFind, status);
2219     if (U_FAILURE(status)) {
2220         return NULL;
2221     }
2222
2223     TZDBNameSearchHandler handler(types, fRegion);
2224     gTZDBNamesTrie->search(text, start, (TextTrieMapSearchResultHandler *)&handler, status);
2225     if (U_FAILURE(status)) {
2226         return NULL;
2227     }
2228     int32_t maxLen = 0;
2229     return handler.getMatches(maxLen);
2230 }
2231
2232 const TZDBNames*
2233 TZDBTimeZoneNames::getMetaZoneNames(const UnicodeString& mzID, UErrorCode& status) {
2234     umtx_initOnce(gTZDBNamesMapInitOnce, &initTZDBNamesMap, status);
2235     if (U_FAILURE(status)) {
2236         return NULL;
2237     }
2238
2239     TZDBNames* tzdbNames = NULL;
2240
2241     UChar mzIDKey[ZID_KEY_MAX + 1];
2242     mzID.extract(mzIDKey, ZID_KEY_MAX + 1, status);
2243     U_ASSERT(status == U_ZERO_ERROR);   // already checked length above
2244     mzIDKey[mzID.length()] = 0;
2245
2246     umtx_lock(&gTZDBNamesMapLock);
2247     {
2248         void *cacheVal = uhash_get(gTZDBNamesMap, mzIDKey);
2249         if (cacheVal == NULL) {
2250             UResourceBundle *zoneStringsRes = ures_openDirect(U_ICUDATA_ZONE, "tzdbNames", &status);
2251             zoneStringsRes = ures_getByKey(zoneStringsRes, gZoneStrings, zoneStringsRes, &status);
2252             if (U_SUCCESS(status)) {
2253                 char key[ZID_KEY_MAX + 1];
2254                 mergeTimeZoneKey(mzID, key);
2255                 tzdbNames = TZDBNames::createInstance(zoneStringsRes, key);
2256
2257                 if (tzdbNames == NULL) {
2258                     cacheVal = (void *)EMPTY;
2259                 } else {
2260                     cacheVal = tzdbNames;
2261                 }
2262                 // Use the persistent ID as the resource key, so we can
2263                 // avoid duplications.
2264                 // TODO: Is there a more efficient way, like intern() in Java?
2265                 void* newKey = (void*) ZoneMeta::findMetaZoneID(mzID);
2266                 if (newKey != NULL) {
2267                     uhash_put(gTZDBNamesMap, newKey, cacheVal, &status);
2268                     if (U_FAILURE(status)) {
2269                         if (tzdbNames != NULL) {
2270                             delete tzdbNames;
2271                             tzdbNames = NULL;
2272                         }
2273                     }
2274                 } else {
2275                     // Should never happen with a valid input
2276                     if (tzdbNames != NULL) {
2277                         // It's not possible that we get a valid tzdbNames with unknown ID.
2278                         // But just in case..
2279                         delete tzdbNames;
2280                         tzdbNames = NULL;
2281                     }
2282                 }
2283             }
2284             ures_close(zoneStringsRes);
2285         } else if (cacheVal != EMPTY) {
2286             tzdbNames = (TZDBNames *)cacheVal;
2287         }
2288     }
2289     umtx_unlock(&gTZDBNamesMapLock);
2290
2291     return tzdbNames;
2292 }
2293
2294 U_NAMESPACE_END
2295
2296
2297 #endif /* #if !UCONFIG_NO_FORMATTING */
2298
2299 //eof