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