1/*
2*******************************************************************************
3* Copyright (C) 2007-2010, International Business Machines Corporation and    *
4* others. All Rights Reserved.                                                *
5*******************************************************************************
6*/
7
8#include "unicode/utypes.h"
9
10#if !UCONFIG_NO_FORMATTING
11
12#include "zstrfmt.h"
13
14#include "unicode/ustring.h"
15#include "unicode/putil.h"
16#include "unicode/msgfmt.h"
17#include "unicode/basictz.h"
18#include "unicode/simpletz.h"
19#include "unicode/rbtz.h"
20#include "unicode/vtzone.h"
21
22#include "uvector.h"
23#include "cstring.h"
24#include "cmemory.h"
25#include "uresimp.h"
26#include "zonemeta.h"
27#include "olsontz.h"
28#include "umutex.h"
29#include "ucln_in.h"
30#include "uassert.h"
31#include "ureslocs.h"
32
33/**
34 * global ZoneStringFormatCache stuffs
35 */
36static UMTX gZSFCacheLock = NULL;
37static U_NAMESPACE_QUALIFIER ZSFCache *gZoneStringFormatCache = NULL;
38
39U_CDECL_BEGIN
40/**
41 * ZoneStringFormatCache cleanup callback func
42 */
43static UBool U_CALLCONV zoneStringFormat_cleanup(void)
44{
45    umtx_destroy(&gZSFCacheLock);
46    if (gZoneStringFormatCache != NULL) {
47        delete gZoneStringFormatCache;
48        gZoneStringFormatCache = NULL;
49    }
50    gZoneStringFormatCache = NULL;
51    return TRUE;
52}
53
54/**
55 * Deleter for ZoneStringInfo
56 */
57static void U_CALLCONV
58deleteZoneStringInfo(void *obj) {
59    delete (U_NAMESPACE_QUALIFIER ZoneStringInfo*)obj;
60}
61
62/**
63 * Deleter for ZoneStrings
64 */
65static void U_CALLCONV
66deleteZoneStrings(void *obj) {
67    delete (U_NAMESPACE_QUALIFIER ZoneStrings*)obj;
68}
69U_CDECL_END
70
71U_NAMESPACE_BEGIN
72
73#define ZID_KEY_MAX 128
74
75static const char gCountriesTag[]       = "Countries";
76static const char gZoneStringsTag[]     = "zoneStrings";
77static const char gShortGenericTag[]    = "sg";
78static const char gShortStandardTag[]   = "ss";
79static const char gShortDaylightTag[]   = "sd";
80static const char gLongGenericTag[]     = "lg";
81static const char gLongStandardTag[]    = "ls";
82static const char gLongDaylightTag[]    = "ld";
83static const char gExemplarCityTag[]    = "ec";
84static const char gCommonlyUsedTag[]    = "cu";
85static const char gFallbackFormatTag[]  = "fallbackFormat";
86static const char gRegionFormatTag[]    = "regionFormat";
87
88#define MZID_PREFIX_LEN 5
89static const char gMetazoneIdPrefix[]   = "meta:";
90
91#define MAX_METAZONES_PER_ZONE 10
92
93static const UChar gDefFallbackPattern[]    = {0x7B, 0x31, 0x7D, 0x20, 0x28, 0x7B, 0x30, 0x7D, 0x29, 0x00}; // "{1} ({0})"
94static const UChar gDefRegionPattern[]      = {0x7B, 0x30, 0x7D, 0x00}; // "{0}"
95static const UChar gCommonlyUsedTrue[]      = {0x31, 0x00}; // "1"
96
97static const double kDstCheckRange      = (double)184*U_MILLIS_PER_DAY;
98
99static int32_t
100getTimeZoneTranslationTypeIndex(TimeZoneTranslationType type) {
101    int32_t typeIdx = 0;
102    switch (type) {
103        case LOCATION:
104            typeIdx = ZSIDX_LOCATION;
105            break;
106        case GENERIC_LONG:
107            typeIdx = ZSIDX_LONG_GENERIC;
108            break;
109        case GENERIC_SHORT:
110            typeIdx = ZSIDX_SHORT_GENERIC;
111            break;
112        case STANDARD_LONG:
113            typeIdx = ZSIDX_LONG_STANDARD;
114            break;
115        case STANDARD_SHORT:
116            typeIdx = ZSIDX_SHORT_STANDARD;
117            break;
118        case DAYLIGHT_LONG:
119            typeIdx = ZSIDX_LONG_DAYLIGHT;
120            break;
121        case DAYLIGHT_SHORT:
122            typeIdx = ZSIDX_SHORT_DAYLIGHT;
123            break;
124    }
125    return typeIdx;
126}
127
128static int32_t
129getTimeZoneTranslationType(TimeZoneTranslationTypeIndex typeIdx) {
130    int32_t type = 0;
131    switch (typeIdx) {
132        case ZSIDX_LOCATION:
133            type = LOCATION;
134            break;
135        case ZSIDX_LONG_GENERIC:
136            type = GENERIC_LONG;
137            break;
138        case ZSIDX_SHORT_GENERIC:
139            type = GENERIC_SHORT;
140            break;
141        case ZSIDX_LONG_STANDARD:
142            type = STANDARD_LONG;
143            break;
144        case ZSIDX_SHORT_STANDARD:
145            type = STANDARD_SHORT;
146            break;
147        case ZSIDX_LONG_DAYLIGHT:
148            type = DAYLIGHT_LONG;
149            break;
150        case ZSIDX_COUNT:
151        case ZSIDX_SHORT_DAYLIGHT:
152            type = DAYLIGHT_SHORT;
153            break;
154        default:
155            break;
156    }
157    return type;
158}
159
160#define DEFAULT_CHARACTERNODE_CAPACITY 1
161
162// ----------------------------------------------------------------------------
163void CharacterNode::clear() {
164    uprv_memset(this, 0, sizeof(*this));
165}
166
167void CharacterNode::deleteValues() {
168    if (fValues == NULL) {
169        // Do nothing.
170    } else if (!fHasValuesVector) {
171        deleteZoneStringInfo(fValues);
172    } else {
173        delete (UVector *)fValues;
174    }
175}
176
177void
178CharacterNode::addValue(void *value, UErrorCode &status) {
179    if (U_FAILURE(status)) {
180        deleteZoneStringInfo(value);
181        return;
182    }
183    if (fValues == NULL) {
184        fValues = value;
185    } else {
186        // At least one value already.
187        if (!fHasValuesVector) {
188            // There is only one value so far, and not in a vector yet.
189            // Create a vector and add the old value.
190            UVector *values = new UVector(deleteZoneStringInfo, NULL, DEFAULT_CHARACTERNODE_CAPACITY, status);
191            if (U_FAILURE(status)) {
192                deleteZoneStringInfo(value);
193                return;
194            }
195            values->addElement(fValues, status);
196            fValues = values;
197            fHasValuesVector = TRUE;
198        }
199        // Add the new value.
200        ((UVector *)fValues)->addElement(value, status);
201    }
202}
203
204//----------------------------------------------------------------------------
205// Virtual destructor to avoid warning
206TextTrieMapSearchResultHandler::~TextTrieMapSearchResultHandler(){
207}
208
209// ----------------------------------------------------------------------------
210TextTrieMap::TextTrieMap(UBool ignoreCase)
211: fIgnoreCase(ignoreCase), fNodes(NULL), fNodesCapacity(0), fNodesCount(0),
212  fLazyContents(NULL), fIsEmpty(TRUE) {
213}
214
215TextTrieMap::~TextTrieMap() {
216    int32_t index;
217    for (index = 0; index < fNodesCount; ++index) {
218        fNodes[index].deleteValues();
219    }
220    uprv_free(fNodes);
221    if (fLazyContents != NULL) {
222        for (int32_t i=0; i<fLazyContents->size(); i+=2) {
223            ZoneStringInfo *zsinf = (ZoneStringInfo *)fLazyContents->elementAt(i+1);
224            delete zsinf;
225        }
226        delete fLazyContents;
227    }
228}
229
230int32_t TextTrieMap::isEmpty() const {
231    // Use a separate field for fIsEmpty because it will remain unchanged once the
232    //   Trie is built, while fNodes and fLazyContents change with the lazy init
233    //   of the nodes structure.  Trying to test the changing fields has
234    //   thread safety complications.
235    return fIsEmpty;
236}
237
238
239//  We defer actually building the TextTrieMap node structure until the first time a
240//     search is performed.  put() simply saves the parameters in case we do
241//     eventually need to build it.
242//
243void
244TextTrieMap::put(const UnicodeString &key, void *value, ZSFStringPool &sp, UErrorCode &status) {
245    fIsEmpty = FALSE;
246    if (fLazyContents == NULL) {
247        fLazyContents = new UVector(status);
248        if (fLazyContents == NULL) {
249            status = U_MEMORY_ALLOCATION_ERROR;
250        }
251    }
252    if (U_FAILURE(status)) {
253        return;
254    }
255    UChar *s = const_cast<UChar *>(sp.get(key, status));
256    fLazyContents->addElement(s, status);
257    fLazyContents->addElement(value, status);
258}
259
260
261void
262TextTrieMap::putImpl(const UnicodeString &key, void *value, UErrorCode &status) {
263    if (fNodes == NULL) {
264        fNodesCapacity = 512;
265        fNodes = (CharacterNode *)uprv_malloc(fNodesCapacity * sizeof(CharacterNode));
266        fNodes[0].clear();  // Init root node.
267        fNodesCount = 1;
268    }
269
270    UnicodeString foldedKey;
271    const UChar *keyBuffer;
272    int32_t keyLength;
273    if (fIgnoreCase) {
274        // Ok to use fastCopyFrom() because we discard the copy when we return.
275        foldedKey.fastCopyFrom(key).foldCase();
276        keyBuffer = foldedKey.getBuffer();
277        keyLength = foldedKey.length();
278    } else {
279        keyBuffer = key.getBuffer();
280        keyLength = key.length();
281    }
282
283    CharacterNode *node = fNodes;
284    int32_t index;
285    for (index = 0; index < keyLength; ++index) {
286        node = addChildNode(node, keyBuffer[index], status);
287    }
288    node->addValue(value, status);
289}
290
291UBool
292TextTrieMap::growNodes() {
293    if (fNodesCapacity == 0xffff) {
294        return FALSE;  // We use 16-bit node indexes.
295    }
296    int32_t newCapacity = fNodesCapacity + 1000;
297    if (newCapacity > 0xffff) {
298        newCapacity = 0xffff;
299    }
300    CharacterNode *newNodes = (CharacterNode *)uprv_malloc(newCapacity * sizeof(CharacterNode));
301    if (newNodes == NULL) {
302        return FALSE;
303    }
304    uprv_memcpy(newNodes, fNodes, fNodesCount * sizeof(CharacterNode));
305    uprv_free(fNodes);
306    fNodes = newNodes;
307    fNodesCapacity = newCapacity;
308    return TRUE;
309}
310
311CharacterNode*
312TextTrieMap::addChildNode(CharacterNode *parent, UChar c, UErrorCode &status) {
313    if (U_FAILURE(status)) {
314        return NULL;
315    }
316    // Linear search of the sorted list of children.
317    uint16_t prevIndex = 0;
318    uint16_t nodeIndex = parent->fFirstChild;
319    while (nodeIndex > 0) {
320        CharacterNode *current = fNodes + nodeIndex;
321        UChar childCharacter = current->fCharacter;
322        if (childCharacter == c) {
323            return current;
324        } else if (childCharacter > c) {
325            break;
326        }
327        prevIndex = nodeIndex;
328        nodeIndex = current->fNextSibling;
329    }
330
331    // Ensure capacity. Grow fNodes[] if needed.
332    if (fNodesCount == fNodesCapacity) {
333        int32_t parentIndex = (int32_t)(parent - fNodes);
334        if (!growNodes()) {
335            status = U_MEMORY_ALLOCATION_ERROR;
336            return NULL;
337        }
338        parent = fNodes + parentIndex;
339    }
340
341    // Insert a new child node with c in sorted order.
342    CharacterNode *node = fNodes + fNodesCount;
343    node->clear();
344    node->fCharacter = c;
345    node->fNextSibling = nodeIndex;
346    if (prevIndex == 0) {
347        parent->fFirstChild = (uint16_t)fNodesCount;
348    } else {
349        fNodes[prevIndex].fNextSibling = (uint16_t)fNodesCount;
350    }
351    ++fNodesCount;
352    return node;
353}
354
355CharacterNode*
356TextTrieMap::getChildNode(CharacterNode *parent, UChar c) const {
357    // Linear search of the sorted list of children.
358    uint16_t nodeIndex = parent->fFirstChild;
359    while (nodeIndex > 0) {
360        CharacterNode *current = fNodes + nodeIndex;
361        UChar childCharacter = current->fCharacter;
362        if (childCharacter == c) {
363            return current;
364        } else if (childCharacter > c) {
365            break;
366        }
367        nodeIndex = current->fNextSibling;
368    }
369    return NULL;
370}
371
372// Mutex for protecting the lazy creation of the Trie node structure on the first call to search().
373static UMTX TextTrieMutex;
374
375// buildTrie() - The Trie node structure is needed.  Create it from the data that was
376//               saved at the time the ZoneStringFormatter was created.  The Trie is only
377//               needed for parsing operations, which are less common than formatting,
378//               and the Trie is big, which is why its creation is deferred until first use.
379void TextTrieMap::buildTrie(UErrorCode &status) {
380    umtx_lock(&TextTrieMutex);
381    if (fLazyContents != NULL) {
382        for (int32_t i=0; i<fLazyContents->size(); i+=2) {
383            const UChar *key = (UChar *)fLazyContents->elementAt(i);
384            void  *val = fLazyContents->elementAt(i+1);
385            UnicodeString keyString(TRUE, key, -1);  // Aliasing UnicodeString constructor.
386            putImpl(keyString, val, status);
387        }
388        delete fLazyContents;
389        fLazyContents = NULL;
390    }
391    umtx_unlock(&TextTrieMutex);
392}
393
394
395void
396TextTrieMap::search(const UnicodeString &text, int32_t start,
397                  TextTrieMapSearchResultHandler *handler, UErrorCode &status) const {
398    UBool trieNeedsInitialization = FALSE;
399    UMTX_CHECK(&TextTrieMutex, fLazyContents != NULL, trieNeedsInitialization);
400    if (trieNeedsInitialization) {
401        TextTrieMap *nonConstThis = const_cast<TextTrieMap *>(this);
402        nonConstThis->buildTrie(status);
403    }
404    if (fNodes == NULL) {
405        return;
406    }
407    search(fNodes, text, start, start, handler, status);
408}
409
410void
411TextTrieMap::search(CharacterNode *node, const UnicodeString &text, int32_t start,
412                  int32_t index, TextTrieMapSearchResultHandler *handler, UErrorCode &status) const {
413    if (U_FAILURE(status)) {
414        return;
415    }
416    if (node->hasValues()) {
417        if (!handler->handleMatch(index - start, node, status)) {
418            return;
419        }
420        if (U_FAILURE(status)) {
421            return;
422        }
423    }
424    UChar32 c = text.char32At(index);
425    if (fIgnoreCase) {
426        // size of character may grow after fold operation
427        UnicodeString tmp(c);
428        tmp.foldCase();
429        int32_t tmpidx = 0;
430        while (tmpidx < tmp.length()) {
431            c = tmp.char32At(tmpidx);
432            node = getChildNode(node, c);
433            if (node == NULL) {
434                break;
435            }
436            tmpidx = tmp.moveIndex32(tmpidx, 1);
437        }
438    } else {
439        node = getChildNode(node, c);
440    }
441    if (node != NULL) {
442        search(node, text, start, index+1, handler, status);
443    }
444}
445
446// ----------------------------------------------------------------------------
447ZoneStringInfo::ZoneStringInfo(const UnicodeString &id, const UnicodeString &str,
448                               TimeZoneTranslationType type, ZSFStringPool &sp, UErrorCode &status)
449: fType(type) {
450    fId = sp.get(id, status);
451    fStr = sp.get(str, status);
452}
453
454ZoneStringInfo::~ZoneStringInfo() {
455}
456
457
458// ----------------------------------------------------------------------------
459ZoneStringSearchResultHandler::ZoneStringSearchResultHandler(UErrorCode &status)
460: fResults(status)
461{
462    clear();
463}
464
465ZoneStringSearchResultHandler::~ZoneStringSearchResultHandler() {
466    clear();
467}
468
469UBool
470ZoneStringSearchResultHandler::handleMatch(int32_t matchLength, const CharacterNode *node, UErrorCode &status) {
471    if (U_FAILURE(status)) {
472        return FALSE;
473    }
474    if (node->hasValues()) {
475        int32_t valuesCount = node->countValues();
476        for (int32_t i = 0; i < valuesCount; i++) {
477            ZoneStringInfo *zsinfo = (ZoneStringInfo*)node->getValue(i);
478            if (zsinfo == NULL) {
479                break;
480            }
481            // Update the results
482            UBool foundType = FALSE;
483            for (int32_t j = 0; j < fResults.size(); j++) {
484                ZoneStringInfo *tmp = (ZoneStringInfo*)fResults.elementAt(j);
485                if (zsinfo->fType == tmp->fType) {
486                    int32_t lenidx = getTimeZoneTranslationTypeIndex(tmp->fType);
487                    if (matchLength > fMatchLen[lenidx]) {
488                        // Same type, longer match
489                        fResults.setElementAt(zsinfo, j);
490                        fMatchLen[lenidx] = matchLength;
491                    }
492                    foundType = TRUE;
493                    break;
494                }
495            }
496            if (!foundType) {
497                // not found in the current list
498                fResults.addElement(zsinfo, status);
499                fMatchLen[getTimeZoneTranslationTypeIndex(zsinfo->fType)] = matchLength;
500            }
501        }
502    }
503    return TRUE;
504}
505
506int32_t
507ZoneStringSearchResultHandler::countMatches(void) {
508    return fResults.size();
509}
510
511const ZoneStringInfo*
512ZoneStringSearchResultHandler::getMatch(int32_t index, int32_t &matchLength) {
513    ZoneStringInfo *zsinfo = NULL;
514    if (index < fResults.size()) {
515        zsinfo = (ZoneStringInfo*)fResults.elementAt(index);
516        matchLength = fMatchLen[getTimeZoneTranslationTypeIndex(zsinfo->fType)];
517    }
518    return zsinfo;
519}
520
521void
522ZoneStringSearchResultHandler::clear(void) {
523    fResults.removeAllElements();
524    for (int32_t i = 0; i < (int32_t)(sizeof(fMatchLen)/sizeof(fMatchLen[0])); i++) {
525        fMatchLen[i] = 0;
526    }
527}
528// ----------------------------------------------------------------------------
529ZoneStringFormat::ZoneStringFormat(const UnicodeString* const* strings,
530                                   int32_t rowCount, int32_t columnCount, UErrorCode &status)
531: fLocale(""),
532  fTzidToStrings(NULL),
533  fMzidToStrings(NULL),
534  fZoneStringsTrie(TRUE),
535  fStringPool(status),
536  fZoneStringsArray(NULL),
537  fMetazoneItem(NULL),
538  fZoneItem(NULL)
539{
540    if (U_FAILURE(status)) {
541        return;
542    }
543    fLocale.setToBogus();
544    if (strings == NULL || columnCount <= 0 || rowCount <= 0) {
545        status = U_ILLEGAL_ARGUMENT_ERROR;
546        return;
547    }
548    fTzidToStrings = uhash_open(uhash_hashUChars,     // key hash function
549                                uhash_compareUChars,  // key comparison function
550                                NULL,                 // Value comparison function
551                                &status);
552    fMzidToStrings = uhash_open(uhash_hashUChars,
553                                uhash_compareUChars,
554                                NULL,
555                                &status);
556
557    uhash_setValueDeleter(fTzidToStrings, deleteZoneStrings);
558    uhash_setValueDeleter(fMzidToStrings, deleteZoneStrings);
559
560    for (int32_t row = 0; row < rowCount; row++) {
561        if (strings[row][0].isEmpty()) {
562            continue;
563        }
564        UnicodeString *names = new UnicodeString[ZSIDX_COUNT];
565        for (int32_t col = 1; col < columnCount; col++) {
566            if (!strings[row][col].isEmpty()) {
567                int32_t typeIdx = -1;
568                switch (col) {
569                    case 1:
570                        typeIdx = ZSIDX_LONG_STANDARD;
571                        break;
572                    case 2:
573                        typeIdx = ZSIDX_SHORT_STANDARD;
574                        break;
575                    case 3:
576                        typeIdx = ZSIDX_LONG_DAYLIGHT;
577                        break;
578                    case 4:
579                        typeIdx = ZSIDX_SHORT_DAYLIGHT;
580                        break;
581                    case 5:
582                        typeIdx = ZSIDX_LOCATION;
583                        break;
584                    case 6:
585                        typeIdx = ZSIDX_LONG_GENERIC;
586                        break;
587                    case 7:
588                        typeIdx = ZSIDX_SHORT_GENERIC;
589                        break;
590                }
591                if (typeIdx != -1) {
592                    names[typeIdx].setTo(strings[row][col]);
593
594                    // Put the name into the trie
595                    int32_t type = getTimeZoneTranslationType((TimeZoneTranslationTypeIndex)typeIdx);
596                    ZoneStringInfo *zsinf = new ZoneStringInfo(strings[row][0],
597                                                               strings[row][col],
598                                                               (TimeZoneTranslationType)type,
599                                                               fStringPool,
600                                                               status);
601                    fZoneStringsTrie.put(strings[row][col], zsinf, fStringPool, status);
602                    if (U_FAILURE(status)) {
603                        delete zsinf;
604                        goto error_cleanup;
605                    }
606                }
607            }
608        }
609        // Note:  ZoneStrings constructor adopts and delete the names array.
610        ZoneStrings *zstrings = new ZoneStrings(names, ZSIDX_COUNT, TRUE, NULL, 0, 0,
611                                                fStringPool, status);
612        UChar *utzid = const_cast<UChar *>(fStringPool.get(strings[row][0], status));
613        uhash_put(fTzidToStrings, utzid, zstrings, &status);
614        if (U_FAILURE(status)) {
615            delete zstrings;
616            goto error_cleanup;
617        }
618    }
619    fStringPool.freeze();
620    return;
621
622error_cleanup:
623    return;
624}
625
626ZoneStringFormat::ZoneStringFormat(const Locale &locale, UErrorCode &status)
627: fLocale(locale),
628  fTzidToStrings(NULL),
629  fMzidToStrings(NULL),
630  fZoneStringsTrie(TRUE),
631  fStringPool(status),
632  fZoneStringsArray(NULL),
633  fMetazoneItem(NULL),
634  fZoneItem(NULL)
635{
636    if (U_FAILURE(status)) {
637        return;
638    }
639    fTzidToStrings = uhash_open(uhash_hashUChars,     // key hash function
640                                uhash_compareUChars,  // key comparison function
641                                NULL,                 // Value comparison function
642                                &status);
643    fMzidToStrings = uhash_open(uhash_hashUChars,     // key hash function
644                                uhash_compareUChars,  // key comparison function
645                                NULL,                 // Value comparison function
646                                &status);
647    uhash_setValueDeleter(fTzidToStrings, deleteZoneStrings);
648    uhash_setValueDeleter(fMzidToStrings, deleteZoneStrings);
649
650    fZoneStringsArray = ures_open(U_ICUDATA_ZONE, locale.getName(), &status);
651    fZoneStringsArray = ures_getByKeyWithFallback(fZoneStringsArray, gZoneStringsTag, fZoneStringsArray, &status);
652    if (U_FAILURE(status)) {
653        // If no locale bundles are available, zoneStrings will be null.
654        // We still want to go through the rest of zone strings initialization,
655        // because generic location format is generated from tzid for the case.
656        // The rest of code should work even zoneStrings is null.
657        status = U_ZERO_ERROR;
658        ures_close(fZoneStringsArray);
659        fZoneStringsArray = NULL;
660    }
661
662    StringEnumeration *tzids = NULL;
663    MessageFormat *fallbackFmt = NULL;
664    MessageFormat *regionFmt = NULL;
665
666    char zidkey[ZID_KEY_MAX];
667    const UChar *zstrarray[ZSIDX_COUNT];
668    const UChar *mzstrarray[ZSIDX_COUNT];
669    UnicodeString mzPartialLoc[MAX_METAZONES_PER_ZONE][4];
670
671    UnicodeString region;
672    getRegion(region);
673
674    fallbackFmt = getFallbackFormat(locale, status);
675    if (U_FAILURE(status)) {
676        goto error_cleanup;
677    }
678    regionFmt = getRegionFormat(locale, status);
679    if (U_FAILURE(status)) {
680        goto error_cleanup;
681    }
682
683    tzids = TimeZone::createEnumeration();
684    const char *tzid;
685    while ((tzid = tzids->next(NULL, status))) {
686        if (U_FAILURE(status)) {
687            goto error_cleanup;
688        }
689        // Skip non-canonical IDs
690        UnicodeString utzid(tzid, -1, US_INV);
691        UnicodeString canonicalID;
692        TimeZone::getCanonicalID(utzid, canonicalID, status);
693        if (U_FAILURE(status)) {
694            // Ignore unknown ID - we should not get here, but just in case.
695            status = U_ZERO_ERROR;
696            continue;
697        }
698        if (utzid != canonicalID) {
699            continue;
700        }
701
702        uprv_strcpy(zidkey, tzid);
703
704        // Replace '/' with ':'
705        char *pCity = NULL;
706        char *p = zidkey;
707        while (*p) {
708            if (*p == '/') {
709                *p = ':';
710                pCity = p + 1;
711            }
712            p++;
713        }
714
715        if (fZoneStringsArray != NULL) {
716            fZoneItem = ures_getByKeyWithFallback(fZoneStringsArray, zidkey, fZoneItem, &status);
717            if (U_FAILURE(status)) {
718                // If failed to open the zone item, create only location string
719                ures_close(fZoneItem);
720                fZoneItem = NULL;
721                status = U_ZERO_ERROR;
722            }
723        }
724        zstrarray[ZSIDX_LONG_STANDARD]  = getZoneStringFromBundle(fZoneItem, gLongStandardTag);
725        zstrarray[ZSIDX_SHORT_STANDARD] = getZoneStringFromBundle(fZoneItem, gShortStandardTag);
726        zstrarray[ZSIDX_LONG_DAYLIGHT]  = getZoneStringFromBundle(fZoneItem, gLongDaylightTag);
727        zstrarray[ZSIDX_SHORT_DAYLIGHT] = getZoneStringFromBundle(fZoneItem, gShortDaylightTag);
728        zstrarray[ZSIDX_LONG_GENERIC]   = getZoneStringFromBundle(fZoneItem, gLongGenericTag);
729        zstrarray[ZSIDX_SHORT_GENERIC]  = getZoneStringFromBundle(fZoneItem, gShortGenericTag);
730
731        // Compose location format string
732        UnicodeString location;
733        UnicodeString country;
734        UnicodeString city;
735        UnicodeString countryCode;
736        ZoneMeta::getCanonicalCountry(utzid, countryCode);
737        if (!countryCode.isEmpty()) {
738            const UChar* tmpCity = getZoneStringFromBundle(fZoneItem, gExemplarCityTag);
739            if (tmpCity != NULL) {
740                city.setTo(TRUE, tmpCity, -1);
741            } else {
742                city.setTo(UnicodeString(pCity, -1, US_INV));
743                // Replace '_' with ' '
744                for (int32_t i = 0; i < city.length(); i++) {
745                    if (city.charAt(i) == (UChar)0x5F /*'_'*/) {
746                        city.setCharAt(i, (UChar)0x20 /*' '*/);
747                    }
748                }
749            }
750            getLocalizedCountry(countryCode, locale, country);
751            UnicodeString singleCountry;
752            ZoneMeta::getSingleCountry(utzid, singleCountry);
753            FieldPosition fpos;
754            if (singleCountry.isEmpty()) {
755                Formattable params [] = {
756                    Formattable(city),
757                    Formattable(country)
758                };
759                fallbackFmt->format(params, 2, location, fpos, status);
760            } else {
761                // If the zone is only one zone in the country, do not add city
762                Formattable params [] = {
763                    Formattable(country)
764                };
765                regionFmt->format(params, 1, location, fpos, status);
766            }
767            if (U_FAILURE(status)) {
768                goto error_cleanup;
769            }
770
771            zstrarray[ZSIDX_LOCATION] = location.getTerminatedBuffer();
772        } else {
773            if (uprv_strlen(tzid) > 4 && uprv_strncmp(tzid, "Etc/", 4) == 0) {
774                // "Etc/xxx" is not associated with a specific location, so localized
775                // GMT format is always used as generic location format.
776                zstrarray[ZSIDX_LOCATION] = NULL;
777            } else {
778                // When a new time zone ID, which is actually associated with a specific
779                // location, is added in tzdata, but the current CLDR data does not have
780                // the information yet, ICU creates a generic location string based on
781                // the ID.  This implementation supports canonical time zone round trip
782                // with format pattern "VVVV".  See #6602 for the details.
783                UnicodeString loc(utzid);
784                int32_t slashIdx = loc.lastIndexOf((UChar)0x2f);
785                if (slashIdx == -1) {
786                    // A time zone ID without slash in the tz database is not
787                    // associated with a specific location.  For instances,
788                    // MET, CET, EET and WET fall into this category.
789                    // In this case, we still use GMT format as fallback.
790                    zstrarray[ZSIDX_LOCATION] = NULL;
791                } else {
792                    FieldPosition fpos;
793                    Formattable params[] = {
794                        Formattable(loc)
795                    };
796                    regionFmt->format(params, 1, location, fpos, status);
797                    if (U_FAILURE(status)) {
798                        goto error_cleanup;
799                    }
800                    zstrarray[ZSIDX_LOCATION] = location.getTerminatedBuffer();
801                }
802            }
803        }
804
805        UBool commonlyUsed = isCommonlyUsed(fZoneItem);
806
807        // Resolve metazones used by this zone
808        int32_t mzPartialLocIdx = 0;
809        const UVector *metazoneMappings = ZoneMeta::getMetazoneMappings(utzid);
810        if (metazoneMappings != NULL) {
811            for (int32_t i = 0; i < metazoneMappings->size(); i++) {
812                const OlsonToMetaMappingEntry *mzmap =
813                        (const OlsonToMetaMappingEntry*)metazoneMappings->elementAt(i);
814                UnicodeString mzid(mzmap->mzid);
815                const ZoneStrings *mzStrings =
816                    (const ZoneStrings*)uhash_get(fMzidToStrings, mzid.getTerminatedBuffer());
817                if (mzStrings == NULL) {
818                    // If the metazone strings are not yet processed, do it now.
819                    char mzidkey[ZID_KEY_MAX];
820                    uprv_strcpy(mzidkey, gMetazoneIdPrefix);
821                    u_UCharsToChars(mzmap->mzid, mzidkey + MZID_PREFIX_LEN, u_strlen(mzmap->mzid) + 1);
822                    fMetazoneItem = ures_getByKeyWithFallback(fZoneStringsArray, mzidkey, fMetazoneItem, &status);
823                    if (U_FAILURE(status)) {
824                        // No resources available for this metazone
825                        // Resource bundle will be cleaned up after end of the loop.
826                        status = U_ZERO_ERROR;
827                        continue;
828                    }
829                    UBool mzCommonlyUsed = isCommonlyUsed(fMetazoneItem);
830                    mzstrarray[ZSIDX_LONG_STANDARD] = getZoneStringFromBundle(fMetazoneItem, gLongStandardTag);
831                    mzstrarray[ZSIDX_SHORT_STANDARD] = getZoneStringFromBundle(fMetazoneItem, gShortStandardTag);
832                    mzstrarray[ZSIDX_LONG_DAYLIGHT] = getZoneStringFromBundle(fMetazoneItem, gLongDaylightTag);
833                    mzstrarray[ZSIDX_SHORT_DAYLIGHT] = getZoneStringFromBundle(fMetazoneItem, gShortDaylightTag);
834                    mzstrarray[ZSIDX_LONG_GENERIC] = getZoneStringFromBundle(fMetazoneItem, gLongGenericTag);
835                    mzstrarray[ZSIDX_SHORT_GENERIC] = getZoneStringFromBundle(fMetazoneItem, gShortGenericTag);
836                    mzstrarray[ZSIDX_LOCATION] = NULL;
837
838                    int32_t lastNonNullIdx = ZSIDX_COUNT - 1;
839                    while (lastNonNullIdx >= 0) {
840                        if (mzstrarray[lastNonNullIdx] != NULL) {
841                            break;
842                        }
843                        lastNonNullIdx--;
844                    }
845                    UnicodeString *strings_mz = NULL;
846                    ZoneStrings *tmp_mzStrings = NULL;
847                    if (lastNonNullIdx >= 0) {
848                        // Create UnicodeString array and put strings to the zone string trie
849                        strings_mz = new UnicodeString[lastNonNullIdx + 1];
850
851                        UnicodeString preferredIdForLocale;
852                        ZoneMeta::getZoneIdByMetazone(mzid, region, preferredIdForLocale);
853
854                        for (int32_t typeidx = 0; typeidx <= lastNonNullIdx; typeidx++) {
855                            if (mzstrarray[typeidx] != NULL) {
856                                strings_mz[typeidx].setTo(TRUE, mzstrarray[typeidx], -1);
857
858                                // Add a metazone string to the zone string trie
859                                int32_t type = getTimeZoneTranslationType((TimeZoneTranslationTypeIndex)typeidx);
860                                ZoneStringInfo *zsinfo = new ZoneStringInfo(
861                                                                preferredIdForLocale,
862                                                                strings_mz[typeidx],
863                                                                (TimeZoneTranslationType)type,
864                                                                fStringPool,
865                                                                status);
866                                fZoneStringsTrie.put(strings_mz[typeidx], zsinfo, fStringPool, status);
867                                if (U_FAILURE(status)) {
868                                    delete []strings_mz;
869                                    goto error_cleanup;
870                                }
871                            }
872                        }
873                        // Note: ZoneStrings constructor adopts and deletes the strings_mz array.
874                        tmp_mzStrings = new ZoneStrings(strings_mz, lastNonNullIdx + 1,
875                                                        mzCommonlyUsed, NULL, 0, 0, fStringPool, status);
876                    } else {
877                        // Create ZoneStrings with empty contents
878                        tmp_mzStrings = new ZoneStrings(NULL, 0, FALSE, NULL, 0, 0, fStringPool, status);
879                    }
880
881                    UChar *umzid = const_cast<UChar *>(fStringPool.get(mzid, status));
882                    uhash_put(fMzidToStrings, umzid, tmp_mzStrings, &status);
883                    if (U_FAILURE(status)) {
884                        goto error_cleanup;
885                    }
886
887                    mzStrings = tmp_mzStrings;
888                }
889
890                // Compose generic partial location format
891                UnicodeString lg;
892                UnicodeString sg;
893
894                mzStrings->getString(ZSIDX_LONG_GENERIC, lg);
895                mzStrings->getString(ZSIDX_SHORT_GENERIC, sg);
896
897                if (!lg.isEmpty() || !sg.isEmpty()) {
898                    UBool addMzPartialLocationNames = TRUE;
899                    for (int32_t j = 0; j < mzPartialLocIdx; j++) {
900                        if (mzPartialLoc[j][0] == mzid) {
901                            // already processed
902                            addMzPartialLocationNames = FALSE;
903                            break;
904                        }
905                    }
906                    if (addMzPartialLocationNames) {
907                        UnicodeString *locationPart = NULL;
908                        // Check if the zone is the preferred zone for the territory associated with the zone
909                        UnicodeString preferredID;
910                        ZoneMeta::getZoneIdByMetazone(mzid, countryCode, preferredID);
911                        if (utzid == preferredID) {
912                            // Use country for the location
913                            locationPart = &country;
914                        } else {
915                            // Use city for the location
916                            locationPart = &city;
917                        }
918                        // Reset the partial location string array
919                        mzPartialLoc[mzPartialLocIdx][0].setTo(mzid);
920                        mzPartialLoc[mzPartialLocIdx][1].remove();
921                        mzPartialLoc[mzPartialLocIdx][2].remove();
922                        mzPartialLoc[mzPartialLocIdx][3].remove();
923
924                        if (locationPart->length() != 0) {
925                            FieldPosition fpos;
926                            if (!lg.isEmpty()) {
927                                Formattable params [] = {
928                                    Formattable(*locationPart),
929                                    Formattable(lg)
930                                };
931                                fallbackFmt->format(params, 2, mzPartialLoc[mzPartialLocIdx][1], fpos, status);
932                            }
933                            if (!sg.isEmpty()) {
934                                Formattable params [] = {
935                                    Formattable(*locationPart),
936                                    Formattable(sg)
937                                };
938                                fallbackFmt->format(params, 2, mzPartialLoc[mzPartialLocIdx][2], fpos, status);
939                                if (mzStrings->isShortFormatCommonlyUsed()) {
940                                    mzPartialLoc[mzPartialLocIdx][3].setTo(TRUE, gCommonlyUsedTrue, -1);
941                                }
942                            }
943                            if (U_FAILURE(status)) {
944                                goto error_cleanup;
945                            }
946                        }
947                        mzPartialLocIdx++;
948                    }
949                }
950            }
951        }
952        // Collected names for a zone
953
954        // Create UnicodeString array for localized zone strings
955        int32_t lastIdx = ZSIDX_COUNT - 1;
956        while (lastIdx >= 0) {
957            if (zstrarray[lastIdx] != NULL) {
958                break;
959            }
960            lastIdx--;
961        }
962        UnicodeString *strings = NULL;
963        int32_t stringsCount = lastIdx + 1;
964
965        if (stringsCount > 0) {
966            strings = new UnicodeString[stringsCount];
967            for (int32_t i = 0; i < stringsCount; i++) {
968                if (zstrarray[i] != NULL) {
969                    strings[i].setTo(zstrarray[i], -1);
970
971                    // Add names to the trie
972                    int32_t type = getTimeZoneTranslationType((TimeZoneTranslationTypeIndex)i);
973                    ZoneStringInfo *zsinfo = new ZoneStringInfo(utzid,
974                                                                strings[i],
975                                                                (TimeZoneTranslationType)type,
976                                                                fStringPool,
977                                                                status);
978                    fZoneStringsTrie.put(strings[i], zsinfo, fStringPool, status);
979                    if (U_FAILURE(status)) {
980                        delete zsinfo;
981                        delete[] strings;
982                        goto error_cleanup;
983                    }
984                }
985            }
986        }
987
988        // Create UnicodeString array for generic partial location strings
989        UnicodeString **genericPartialLocationNames = NULL;
990        int32_t genericPartialRowCount = mzPartialLocIdx;
991        int32_t genericPartialColCount = 4;
992
993        if (genericPartialRowCount != 0) {
994            genericPartialLocationNames =
995                     (UnicodeString**)uprv_malloc(genericPartialRowCount * sizeof(UnicodeString*));
996            if (genericPartialLocationNames == NULL) {
997                status = U_MEMORY_ALLOCATION_ERROR;
998                delete[] strings;
999                goto error_cleanup;
1000            }
1001            for (int32_t i = 0; i < genericPartialRowCount; i++) {
1002                genericPartialLocationNames[i] = new UnicodeString[genericPartialColCount];
1003                for (int32_t j = 0; j < genericPartialColCount; j++) {
1004                    genericPartialLocationNames[i][j].setTo(mzPartialLoc[i][j]);
1005                    // Add names to the trie
1006                    if ((j == 1 || j == 2) &&!genericPartialLocationNames[i][j].isEmpty()) {
1007                        ZoneStringInfo *zsinfo;
1008                        TimeZoneTranslationType type = (j == 1) ? GENERIC_LONG : GENERIC_SHORT;
1009                        zsinfo = new ZoneStringInfo(utzid, genericPartialLocationNames[i][j], type,
1010                                                    fStringPool, status);
1011                        fZoneStringsTrie.put(genericPartialLocationNames[i][j], zsinfo, fStringPool, status);
1012                        if (U_FAILURE(status)) {
1013                            delete[] genericPartialLocationNames[i];
1014                            uprv_free(genericPartialLocationNames);
1015                            delete[] strings;
1016                            goto error_cleanup;
1017                        }
1018                    }
1019                }
1020            }
1021        }
1022
1023        // Finally, create ZoneStrings instance and put it into the tzidToStinrgs map
1024        ZoneStrings *zstrings = new ZoneStrings(strings, stringsCount, commonlyUsed,
1025                                                genericPartialLocationNames, genericPartialRowCount,
1026                                                genericPartialColCount, fStringPool, status);
1027
1028        UChar *uutzid = const_cast<UChar *>(fStringPool.get(utzid, status));
1029        uhash_put(fTzidToStrings, uutzid, zstrings, &status);
1030        if (U_FAILURE(status)) {
1031            delete zstrings;
1032            goto error_cleanup;
1033        }
1034    }
1035
1036error_cleanup:
1037    if (fallbackFmt != NULL) {
1038        delete fallbackFmt;
1039    }
1040    if (regionFmt != NULL) {
1041        delete regionFmt;
1042    }
1043    if (tzids != NULL) {
1044        delete tzids;
1045    }
1046    fStringPool.freeze();
1047}
1048
1049ZoneStringFormat::~ZoneStringFormat() {
1050    uhash_close(fTzidToStrings);
1051    uhash_close(fMzidToStrings);
1052    ures_close(fZoneItem);
1053    ures_close(fMetazoneItem);
1054    ures_close(fZoneStringsArray);
1055}
1056
1057SafeZoneStringFormatPtr*
1058ZoneStringFormat::getZoneStringFormat(const Locale& locale, UErrorCode &status) {
1059    umtx_lock(&gZSFCacheLock);
1060    if (gZoneStringFormatCache == NULL) {
1061        gZoneStringFormatCache = new ZSFCache(10 /* capacity */);
1062        ucln_i18n_registerCleanup(UCLN_I18N_ZSFORMAT, zoneStringFormat_cleanup);
1063    }
1064    umtx_unlock(&gZSFCacheLock);
1065
1066    return gZoneStringFormatCache->get(locale, status);
1067}
1068
1069
1070UnicodeString**
1071ZoneStringFormat::createZoneStringsArray(UDate date, int32_t &rowCount, int32_t &colCount, UErrorCode &status) const {
1072    if (U_FAILURE(status)) {
1073        return NULL;
1074    }
1075    UnicodeString **result = NULL;
1076    rowCount = 0;
1077    colCount = 0;
1078
1079    // Collect canonical time zone IDs
1080    UVector canonicalIDs(uhash_deleteUnicodeString, uhash_compareUnicodeString, status);
1081    if (U_FAILURE(status)) {
1082        return NULL;
1083    }
1084    StringEnumeration *tzids = TimeZone::createEnumeration();
1085    const UChar *tzid;
1086    while ((tzid = tzids->unext(NULL, status))) {
1087        if (U_FAILURE(status)) {
1088            delete tzids;
1089            return NULL;
1090        }
1091        UnicodeString utzid(tzid);
1092        UnicodeString canonicalID;
1093        TimeZone::getCanonicalID(UnicodeString(tzid), canonicalID, status);
1094        if (U_FAILURE(status)) {
1095            // Ignore unknown ID - we should not get here, but just in case.
1096            status = U_ZERO_ERROR;
1097            continue;
1098        }
1099        if (utzid == canonicalID) {
1100            canonicalIDs.addElement(new UnicodeString(utzid), status);
1101            if (U_FAILURE(status)) {
1102                delete tzids;
1103                return NULL;
1104            }
1105        }
1106    }
1107    delete tzids;
1108
1109    // Allocate array
1110    result = (UnicodeString**)uprv_malloc(canonicalIDs.size() * sizeof(UnicodeString*));
1111    if (result == NULL) {
1112        status = U_MEMORY_ALLOCATION_ERROR;
1113        return NULL;
1114    }
1115    for (int32_t i = 0; i < canonicalIDs.size(); i++) {
1116        result[i] = new UnicodeString[8];
1117        UnicodeString *id = (UnicodeString*)canonicalIDs.elementAt(i);
1118        result[i][0].setTo(*id);
1119        getLongStandard(*id, date, result[i][1]);
1120        getShortStandard(*id, date, FALSE, result[i][2]);
1121        getLongDaylight(*id, date, result[i][3]);
1122        getShortDaylight(*id, date, FALSE, result[i][4]);
1123        getGenericLocation(*id, result[i][5]);
1124        getLongGenericNonLocation(*id, date, result[i][6]);
1125        getShortGenericNonLocation(*id, date, FALSE, result[i][7]);
1126    }
1127
1128    rowCount = canonicalIDs.size();
1129    colCount = 8;
1130    return result;
1131}
1132
1133UnicodeString&
1134ZoneStringFormat::getSpecificLongString(const Calendar &cal, UnicodeString &result,
1135                                        UErrorCode &status) const {
1136    result.remove();
1137    if (U_FAILURE(status)) {
1138        return result;
1139    }
1140    UnicodeString tzid;
1141    cal.getTimeZone().getID(tzid);
1142    UDate date = cal.getTime(status);
1143    if (cal.get(UCAL_DST_OFFSET, status) == 0) {
1144        return getString(tzid, ZSIDX_LONG_STANDARD, date, FALSE /*not used*/, result);
1145    } else {
1146        return getString(tzid, ZSIDX_LONG_DAYLIGHT, date, FALSE /*not used*/, result);
1147    }
1148}
1149
1150UnicodeString&
1151ZoneStringFormat::getSpecificShortString(const Calendar &cal, UBool commonlyUsedOnly,
1152                                         UnicodeString &result, UErrorCode &status) const {
1153    result.remove();
1154    if (U_FAILURE(status)) {
1155        return result;
1156    }
1157    UnicodeString tzid;
1158    cal.getTimeZone().getID(tzid);
1159    UDate date = cal.getTime(status);
1160    if (cal.get(UCAL_DST_OFFSET, status) == 0) {
1161        return getString(tzid, ZSIDX_SHORT_STANDARD, date, commonlyUsedOnly, result);
1162    } else {
1163        return getString(tzid, ZSIDX_SHORT_DAYLIGHT, date, commonlyUsedOnly, result);
1164    }
1165}
1166
1167UnicodeString&
1168ZoneStringFormat::getGenericLongString(const Calendar &cal, UnicodeString &result,
1169                                       UErrorCode &status) const {
1170    return getGenericString(cal, FALSE /*long*/, FALSE /* not used */, result, status);
1171}
1172
1173UnicodeString&
1174ZoneStringFormat::getGenericShortString(const Calendar &cal, UBool commonlyUsedOnly,
1175                                        UnicodeString &result, UErrorCode &status) const {
1176    return getGenericString(cal, TRUE /*short*/, commonlyUsedOnly, result, status);
1177}
1178
1179UnicodeString&
1180ZoneStringFormat::getGenericLocationString(const Calendar &cal, UnicodeString &result,
1181                                           UErrorCode &status) const {
1182    UnicodeString tzid;
1183    cal.getTimeZone().getID(tzid);
1184    UDate date = cal.getTime(status);
1185    return getString(tzid, ZSIDX_LOCATION, date, FALSE /*not used*/, result);
1186}
1187
1188const ZoneStringInfo*
1189ZoneStringFormat::findSpecificLong(const UnicodeString &text, int32_t start,
1190                                   int32_t &matchLength, UErrorCode &status) const {
1191    return find(text, start, STANDARD_LONG | DAYLIGHT_LONG, matchLength, status);
1192}
1193
1194const ZoneStringInfo*
1195ZoneStringFormat::findSpecificShort(const UnicodeString &text, int32_t start,
1196                                    int32_t &matchLength, UErrorCode &status) const {
1197    return find(text, start, STANDARD_SHORT | DAYLIGHT_SHORT, matchLength, status);
1198}
1199
1200const ZoneStringInfo*
1201ZoneStringFormat::findGenericLong(const UnicodeString &text, int32_t start,
1202                                  int32_t &matchLength, UErrorCode &status) const {
1203    return find(text, start, GENERIC_LONG | STANDARD_LONG | LOCATION, matchLength, status);
1204}
1205
1206const ZoneStringInfo*
1207ZoneStringFormat::findGenericShort(const UnicodeString &text, int32_t start,
1208                                   int32_t &matchLength, UErrorCode &status) const {
1209    return find(text, start, GENERIC_SHORT | STANDARD_SHORT | LOCATION, matchLength, status);
1210}
1211
1212const ZoneStringInfo*
1213ZoneStringFormat::findGenericLocation(const UnicodeString &text, int32_t start,
1214                                      int32_t &matchLength, UErrorCode &status) const {
1215    return find(text, start, LOCATION, matchLength, status);
1216}
1217
1218UnicodeString&
1219ZoneStringFormat::getString(const UnicodeString &tzid, TimeZoneTranslationTypeIndex typeIdx, UDate date,
1220                            UBool commonlyUsedOnly, UnicodeString& result) const {
1221    result.remove();
1222
1223    // ICU's own array does not have entries for aliases
1224    UnicodeString canonicalID;
1225    UErrorCode status = U_ZERO_ERROR;
1226    TimeZone::getCanonicalID(tzid, canonicalID, status);
1227    if (U_FAILURE(status)) {
1228        // Unknown ID, but users might have their own data.
1229        canonicalID.setTo(tzid);
1230    }
1231
1232    if (uhash_count(fTzidToStrings) > 0) {
1233        ZoneStrings *zstrings = (ZoneStrings*)uhash_get(fTzidToStrings, canonicalID.getTerminatedBuffer());
1234        if (zstrings != NULL) {
1235            switch (typeIdx) {
1236                case ZSIDX_LONG_STANDARD:
1237                case ZSIDX_LONG_DAYLIGHT:
1238                case ZSIDX_LONG_GENERIC:
1239                case ZSIDX_LOCATION:
1240                    zstrings->getString(typeIdx, result);
1241                    break;
1242                case ZSIDX_SHORT_STANDARD:
1243                case ZSIDX_SHORT_DAYLIGHT:
1244                case ZSIDX_COUNT: //added to avoid warning
1245                case ZSIDX_SHORT_GENERIC:
1246                    if (!commonlyUsedOnly || zstrings->isShortFormatCommonlyUsed()) {
1247                        zstrings->getString(typeIdx, result);
1248                    }
1249                    break;
1250                default:
1251                    break;
1252            }
1253        }
1254    }
1255    if (result.isEmpty() && uhash_count(fMzidToStrings) > 0 && typeIdx != ZSIDX_LOCATION) {
1256        // Try metazone
1257        UnicodeString mzid;
1258        ZoneMeta::getMetazoneID(canonicalID, date, mzid);
1259        if (!mzid.isEmpty()) {
1260            ZoneStrings *mzstrings = (ZoneStrings*)uhash_get(fMzidToStrings, mzid.getTerminatedBuffer());
1261            if (mzstrings != NULL) {
1262                switch (typeIdx) {
1263                    case ZSIDX_LONG_STANDARD:
1264                    case ZSIDX_LONG_DAYLIGHT:
1265                    case ZSIDX_LONG_GENERIC:
1266                    case ZSIDX_LOCATION:
1267                        mzstrings->getString(typeIdx, result);
1268                        break;
1269                    case ZSIDX_SHORT_STANDARD:
1270                    case ZSIDX_SHORT_DAYLIGHT:
1271                    case ZSIDX_COUNT: //added to avoid warning
1272                    case ZSIDX_SHORT_GENERIC:
1273                        if (!commonlyUsedOnly || mzstrings->isShortFormatCommonlyUsed()) {
1274                            mzstrings->getString(typeIdx, result);
1275                        }
1276                        break;
1277                    default:
1278                        break;
1279                }
1280            }
1281        }
1282    }
1283    return result;
1284}
1285
1286UnicodeString&
1287ZoneStringFormat::getGenericString(const Calendar &cal, UBool isShort, UBool commonlyUsedOnly,
1288                                   UnicodeString &result, UErrorCode &status) const {
1289    result.remove();
1290    UDate time = cal.getTime(status);
1291    if (U_FAILURE(status)) {
1292        return result;
1293    }
1294    const TimeZone &tz = cal.getTimeZone();
1295    UnicodeString tzid;
1296    tz.getID(tzid);
1297
1298    // ICU's own array does not have entries for aliases
1299    UnicodeString canonicalID;
1300    TimeZone::getCanonicalID(tzid, canonicalID, status);
1301    if (U_FAILURE(status)) {
1302        // Unknown ID, but users might have their own data.
1303        status = U_ZERO_ERROR;
1304        canonicalID.setTo(tzid);
1305    }
1306
1307    ZoneStrings *zstrings = NULL;
1308    if (uhash_count(fTzidToStrings) > 0) {
1309        zstrings = (ZoneStrings*)uhash_get(fTzidToStrings, canonicalID.getTerminatedBuffer());
1310        if (zstrings != NULL) {
1311            if (isShort) {
1312                if (!commonlyUsedOnly || zstrings->isShortFormatCommonlyUsed()) {
1313                    zstrings->getString(ZSIDX_SHORT_GENERIC, result);
1314                }
1315            } else {
1316                zstrings->getString(ZSIDX_LONG_GENERIC, result);
1317            }
1318        }
1319    }
1320    if (result.isEmpty() && uhash_count(fMzidToStrings) > 0) {
1321        // try metazone
1322        int32_t raw, sav;
1323        UnicodeString mzid;
1324        ZoneMeta::getMetazoneID(canonicalID, time, mzid);
1325        if (!mzid.isEmpty()) {
1326            UBool useStandard = FALSE;
1327            sav = cal.get(UCAL_DST_OFFSET, status);
1328            if (U_FAILURE(status)) {
1329                return result;
1330            }
1331            if (sav == 0) {
1332                useStandard = TRUE;
1333                // Check if the zone actually uses daylight saving time around the time
1334                TimeZone *tmptz = tz.clone();
1335                BasicTimeZone *btz = NULL;
1336                if (tmptz->getDynamicClassID() == OlsonTimeZone::getStaticClassID()
1337                    || tmptz->getDynamicClassID() == SimpleTimeZone::getStaticClassID()
1338                    || tmptz->getDynamicClassID() == RuleBasedTimeZone::getStaticClassID()
1339                    || tmptz->getDynamicClassID() == VTimeZone::getStaticClassID()) {
1340                    btz = (BasicTimeZone*)tmptz;
1341                }
1342
1343                if (btz != NULL) {
1344                    TimeZoneTransition before;
1345                    UBool beforTrs = btz->getPreviousTransition(time, TRUE, before);
1346                    if (beforTrs
1347                            && (time - before.getTime() < kDstCheckRange)
1348                            && before.getFrom()->getDSTSavings() != 0) {
1349                        useStandard = FALSE;
1350                    } else {
1351                        TimeZoneTransition after;
1352                        UBool afterTrs = btz->getNextTransition(time, FALSE, after);
1353                        if (afterTrs
1354                                && (after.getTime() - time < kDstCheckRange)
1355                                && after.getTo()->getDSTSavings() != 0) {
1356                            useStandard = FALSE;
1357                        }
1358                    }
1359                } else {
1360                    // If not BasicTimeZone... only if the instance is not an ICU's implementation.
1361                    // We may get a wrong answer in edge case, but it should practically work OK.
1362                    tmptz->getOffset(time - kDstCheckRange, FALSE, raw, sav, status);
1363                    if (sav != 0) {
1364                        useStandard = FALSE;
1365                    } else {
1366                        tmptz->getOffset(time + kDstCheckRange, FALSE, raw, sav, status);
1367                        if (sav != 0){
1368                            useStandard = FALSE;
1369                        }
1370                    }
1371                    if (U_FAILURE(status)) {
1372                        delete tmptz;
1373                        result.remove();
1374                        return result;
1375                    }
1376                }
1377                delete tmptz;
1378            }
1379            if (useStandard) {
1380                getString(canonicalID, (isShort ? ZSIDX_SHORT_STANDARD : ZSIDX_LONG_STANDARD),
1381                    time, commonlyUsedOnly, result);
1382
1383                // Note:
1384                // In CLDR 1.5.1, a same localization is used for both generic and standard
1385                // for some metazones in some locales.  This is actually data bugs and should
1386                // be resolved in later versions of CLDR.  For now, we check if the standard
1387                // name is different from its generic name below.
1388                if (!result.isEmpty()) {
1389                    UnicodeString genericNonLocation;
1390                    getString(canonicalID, (isShort ? ZSIDX_SHORT_GENERIC : ZSIDX_LONG_GENERIC),
1391                        time, commonlyUsedOnly, genericNonLocation);
1392                    if (!genericNonLocation.isEmpty() && result == genericNonLocation) {
1393                        result.remove();
1394                    }
1395                }
1396            }
1397            if (result.isEmpty()) {
1398                ZoneStrings *mzstrings = (ZoneStrings*)uhash_get(fMzidToStrings, mzid.getTerminatedBuffer());
1399                if (mzstrings != NULL) {
1400                    if (isShort) {
1401                        if (!commonlyUsedOnly || mzstrings->isShortFormatCommonlyUsed()) {
1402                            mzstrings->getString(ZSIDX_SHORT_GENERIC, result);
1403                        }
1404                    } else {
1405                        mzstrings->getString(ZSIDX_LONG_GENERIC, result);
1406                    }
1407                }
1408                if (!result.isEmpty()) {
1409                    // Check if the offsets at the given time matches the preferred zone's offsets
1410                    UnicodeString preferredId;
1411                    UnicodeString region;
1412                    ZoneMeta::getZoneIdByMetazone(mzid, getRegion(region), preferredId);
1413                    if (canonicalID != preferredId) {
1414                        // Check if the offsets at the given time are identical with the preferred zone
1415                        raw = cal.get(UCAL_ZONE_OFFSET, status);
1416                        if (U_FAILURE(status)) {
1417                            result.remove();
1418                            return result;
1419                        }
1420                        TimeZone *preferredZone = TimeZone::createTimeZone(preferredId);
1421                        int32_t prfRaw, prfSav;
1422                        // Check offset in preferred time zone with wall time.
1423                        // With getOffset(time, false, preferredOffsets),
1424                        // you may get incorrect results because of time overlap at DST->STD
1425                        // transition.
1426                        preferredZone->getOffset(time + raw + sav, TRUE, prfRaw, prfSav, status);
1427                        delete preferredZone;
1428
1429                        if (U_FAILURE(status)) {
1430                            result.remove();
1431                            return result;
1432                        }
1433                        if ((raw != prfRaw || sav != prfSav) && zstrings != NULL) {
1434                            // Use generic partial location string as fallback
1435                            zstrings->getGenericPartialLocationString(mzid, isShort, commonlyUsedOnly, result);
1436                        }
1437                    }
1438                }
1439            }
1440        }
1441    }
1442    if (result.isEmpty()) {
1443        // Use location format as the final fallback
1444        getString(canonicalID, ZSIDX_LOCATION, time, FALSE /*not used*/, result);
1445    }
1446
1447    return result;
1448}
1449
1450UnicodeString&
1451ZoneStringFormat::getGenericPartialLocationString(const UnicodeString &tzid, UBool isShort,
1452                                                  UDate date, UBool commonlyUsedOnly, UnicodeString &result) const {
1453    result.remove();
1454    if (uhash_count(fTzidToStrings) <= 0) {
1455        return result;
1456    }
1457
1458    UnicodeString canonicalID;
1459    UErrorCode status = U_ZERO_ERROR;
1460    TimeZone::getCanonicalID(tzid, canonicalID, status);
1461    if (U_FAILURE(status)) {
1462        // Unknown ID, so no corresponding meta data.
1463        return result;
1464    }
1465
1466    UnicodeString mzid;
1467    ZoneMeta::getMetazoneID(canonicalID, date, mzid);
1468
1469    if (!mzid.isEmpty()) {
1470        ZoneStrings *zstrings = (ZoneStrings*)uhash_get(fTzidToStrings, canonicalID.getTerminatedBuffer());
1471        if (zstrings != NULL) {
1472            zstrings->getGenericPartialLocationString(mzid, isShort, commonlyUsedOnly, result);
1473        }
1474    }
1475    return result;
1476}
1477
1478const ZoneStringInfo*
1479ZoneStringFormat::find(const UnicodeString &text, int32_t start, int32_t types,
1480                       int32_t &matchLength, UErrorCode &status) const {
1481    matchLength = 0;
1482    if (U_FAILURE(status)) {
1483        return NULL;
1484    }
1485    if (fZoneStringsTrie.isEmpty()) {
1486        return NULL;
1487    }
1488    const ZoneStringInfo *result = NULL;
1489    const ZoneStringInfo *fallback = NULL;
1490    int32_t fallbackMatchLen = 0;
1491
1492    ZoneStringSearchResultHandler handler(status);
1493    fZoneStringsTrie.search(text, start, (TextTrieMapSearchResultHandler*)&handler, status);
1494    if (U_SUCCESS(status)) {
1495        int32_t numMatches = handler.countMatches();
1496        for (int32_t i = 0; i < numMatches; i++) {
1497            int32_t tmpMatchLen = 0; // init. output only param to silence gcc
1498            const ZoneStringInfo *tmp = handler.getMatch(i, tmpMatchLen);
1499            if ((types & tmp->fType) != 0) {
1500                if (result == NULL || matchLength < tmpMatchLen) {
1501                    result = tmp;
1502                    matchLength = tmpMatchLen;
1503                } else if (matchLength == tmpMatchLen) {
1504                    // Tie breaker - there are some examples that a
1505                    // long standard name is identical with a location
1506                    // name - for example, "Uruguay Time".  In this case,
1507                    // we interpret it as generic, not specific.
1508                    if (tmp->isGeneric() && !result->isGeneric()) {
1509                        result = tmp;
1510                    }
1511                }
1512            } else if (result == NULL) {
1513                if (fallback == NULL || fallbackMatchLen < tmpMatchLen) {
1514                    fallback = tmp;
1515                    fallbackMatchLen = tmpMatchLen;
1516                } else if (fallbackMatchLen == tmpMatchLen) {
1517                    if (tmp->isGeneric() && !fallback->isGeneric()) {
1518                        fallback = tmp;
1519                    }
1520                }
1521            }
1522        }
1523        if (result == NULL && fallback != NULL) {
1524            result = fallback;
1525            matchLength = fallbackMatchLen;
1526        }
1527    }
1528    return result;
1529}
1530
1531
1532UnicodeString&
1533ZoneStringFormat::getRegion(UnicodeString &region) const {
1534    const char* country = fLocale.getCountry();
1535    // TODO: Utilize addLikelySubtag in Locale to resolve default region
1536    // when the implementation is ready.
1537    region.setTo(UnicodeString(country, -1, US_INV));
1538    return region;
1539}
1540
1541MessageFormat*
1542ZoneStringFormat::getFallbackFormat(const Locale &locale, UErrorCode &status) {
1543    if (U_FAILURE(status)) {
1544        return NULL;
1545    }
1546    UnicodeString pattern(TRUE, gDefFallbackPattern, -1);
1547    UResourceBundle *zoneStringsArray = ures_open(U_ICUDATA_ZONE, locale.getName(), &status);
1548    zoneStringsArray = ures_getByKeyWithFallback(zoneStringsArray, gZoneStringsTag, zoneStringsArray, &status);
1549    int32_t len;
1550    const UChar *flbkfmt = ures_getStringByKeyWithFallback(zoneStringsArray, gFallbackFormatTag, &len, &status);
1551    if (U_SUCCESS(status)) {
1552        pattern.setTo(flbkfmt);
1553    } else {
1554        status = U_ZERO_ERROR;
1555    }
1556    ures_close(zoneStringsArray);
1557
1558    MessageFormat *fallbackFmt = new MessageFormat(pattern, status);
1559    return fallbackFmt;
1560}
1561
1562MessageFormat*
1563ZoneStringFormat::getRegionFormat(const Locale& locale, UErrorCode &status) {
1564    if (U_FAILURE(status)) {
1565        return NULL;
1566    }
1567    UnicodeString pattern(TRUE, gDefRegionPattern, -1);
1568    UResourceBundle *zoneStringsArray = ures_open(U_ICUDATA_ZONE, locale.getName(), &status);
1569    zoneStringsArray = ures_getByKeyWithFallback(zoneStringsArray, gZoneStringsTag, zoneStringsArray, &status);
1570    int32_t len;
1571    const UChar *regionfmt = ures_getStringByKeyWithFallback(zoneStringsArray, gRegionFormatTag, &len, &status);
1572    if (U_SUCCESS(status)) {
1573        pattern.setTo(regionfmt);
1574    } else {
1575        status = U_ZERO_ERROR;
1576    }
1577    ures_close(zoneStringsArray);
1578
1579    MessageFormat *regionFmt = new MessageFormat(pattern, status);
1580    return regionFmt;
1581}
1582
1583const UChar*
1584ZoneStringFormat::getZoneStringFromBundle(const UResourceBundle *zoneitem, const char *key) {
1585    const UChar *str = NULL;
1586    if (zoneitem != NULL) {
1587        UErrorCode status = U_ZERO_ERROR;
1588        int32_t len;
1589        str = ures_getStringByKeyWithFallback(zoneitem, key, &len, &status);
1590        str = fStringPool.adopt(str, status);
1591        if (U_FAILURE(status)) {
1592            str = NULL;
1593        }
1594    }
1595    return str;
1596}
1597
1598UBool
1599ZoneStringFormat::isCommonlyUsed(const UResourceBundle *zoneitem) {
1600    if (zoneitem == NULL) {
1601        return TRUE;
1602    }
1603
1604    UBool commonlyUsed = FALSE;
1605    UErrorCode status = U_ZERO_ERROR;
1606    UResourceBundle *cuRes = ures_getByKey(zoneitem, gCommonlyUsedTag, NULL, &status);
1607    int32_t cuValue = ures_getInt(cuRes, &status);
1608    if (U_SUCCESS(status)) {
1609        if (cuValue == 1) {
1610            commonlyUsed = TRUE;
1611        }
1612    }
1613    ures_close(cuRes);
1614    return commonlyUsed;
1615}
1616
1617UnicodeString&
1618ZoneStringFormat::getLocalizedCountry(const UnicodeString &countryCode, const Locale &locale, UnicodeString &displayCountry) {
1619    // We do not want to use display country names only from the target language bundle
1620    // Note: we should do this in better way.
1621    displayCountry.remove();
1622    int32_t ccLen = countryCode.length();
1623    if (ccLen > 0 && ccLen < ULOC_COUNTRY_CAPACITY) {
1624        UErrorCode status = U_ZERO_ERROR;
1625        UResourceBundle *localeBundle = ures_open(NULL, locale.getName(), &status);
1626        if (U_SUCCESS(status)) {
1627            const char *bundleLocStr = ures_getLocale(localeBundle, &status);
1628            if (U_SUCCESS(status) && uprv_strlen(bundleLocStr) > 0) {
1629                Locale bundleLoc(bundleLocStr);
1630                if (uprv_strcmp(bundleLocStr, "root") != 0 &&
1631                    uprv_strcmp(bundleLoc.getLanguage(), locale.getLanguage()) == 0) {
1632                    // Create a fake locale strings
1633                    char tmpLocStr[ULOC_COUNTRY_CAPACITY + 3];
1634                    uprv_strcpy(tmpLocStr, "xx_");
1635                    u_UCharsToChars(countryCode.getBuffer(), &tmpLocStr[3], ccLen);
1636                    tmpLocStr[3 + ccLen] = 0;
1637
1638                    Locale tmpLoc(tmpLocStr);
1639                    tmpLoc.getDisplayCountry(locale, displayCountry);
1640                }
1641            }
1642        }
1643        ures_close(localeBundle);
1644    }
1645    if (displayCountry.isEmpty()) {
1646        // Use the country code as the fallback
1647        displayCountry.setTo(countryCode);
1648    }
1649    return displayCountry;
1650}
1651
1652// ----------------------------------------------------------------------------
1653/*
1654 * ZoneStrings constructor adopts (and promptly copies and deletes)
1655 *    the input UnicodeString arrays.
1656 */
1657ZoneStrings::ZoneStrings(UnicodeString *strings,
1658                         int32_t stringsCount,
1659                         UBool commonlyUsed,
1660                         UnicodeString **genericPartialLocationStrings,
1661                         int32_t genericRowCount,
1662                         int32_t genericColCount,
1663                         ZSFStringPool &sp,
1664                         UErrorCode &status)
1665:   fStrings(NULL),
1666    fStringsCount(stringsCount),
1667    fIsCommonlyUsed(commonlyUsed),
1668    fGenericPartialLocationStrings(NULL),
1669    fGenericPartialLocationRowCount(genericRowCount),
1670    fGenericPartialLocationColCount(genericColCount)
1671{
1672    if (U_FAILURE(status)) {
1673        return;
1674    }
1675    int32_t i, j;
1676    if (strings != NULL) {
1677        fStrings = (const UChar **)uprv_malloc(sizeof(const UChar **) * stringsCount);
1678        if (fStrings == NULL) {
1679            status = U_MEMORY_ALLOCATION_ERROR;
1680            return;
1681        }
1682        for (i=0; i<fStringsCount; i++) {
1683            fStrings[i] = sp.get(strings[i], status);
1684        }
1685        delete[] strings;
1686    }
1687    if (genericPartialLocationStrings != NULL) {
1688        fGenericPartialLocationStrings =
1689            (const UChar ***)uprv_malloc(sizeof(const UChar ***) * genericRowCount);
1690        if (fGenericPartialLocationStrings == NULL) {
1691            status = U_MEMORY_ALLOCATION_ERROR;
1692            return;
1693        }
1694        for (i=0; i < fGenericPartialLocationRowCount; i++) {
1695            fGenericPartialLocationStrings[i] =
1696                (const UChar **)uprv_malloc(sizeof(const UChar **) * genericColCount);
1697            if (fGenericPartialLocationStrings[i] == NULL) {
1698                status = U_MEMORY_ALLOCATION_ERROR;
1699                continue;   // Continue so that fGenericPartialLocationStrings will not contain uninitialized junk,
1700            }               //   which would crash the destructor.
1701            for (j=0; j<genericColCount; j++) {
1702                fGenericPartialLocationStrings[i][j] =
1703                        sp.get(genericPartialLocationStrings[i][j], status);
1704            }
1705            delete[] genericPartialLocationStrings[i];
1706        }
1707        uprv_free(genericPartialLocationStrings);
1708    }
1709}
1710
1711ZoneStrings::~ZoneStrings() {
1712    uprv_free(fStrings);
1713    if (fGenericPartialLocationStrings != NULL) {
1714        for (int32_t i = 0; i < fGenericPartialLocationRowCount; i++) {
1715            uprv_free(fGenericPartialLocationStrings[i]);
1716        }
1717        uprv_free(fGenericPartialLocationStrings);
1718    }
1719}
1720
1721
1722UnicodeString&
1723ZoneStrings::getString(int32_t typeIdx, UnicodeString &result) const {
1724    if (typeIdx >= 0 && typeIdx < fStringsCount) {
1725        result.setTo(fStrings[typeIdx], -1);
1726    } else {
1727        result.remove();
1728    }
1729    return result;
1730}
1731
1732UnicodeString&
1733ZoneStrings::getGenericPartialLocationString(const UnicodeString &mzid, UBool isShort,
1734                                        UBool commonlyUsedOnly, UnicodeString &result) const {
1735    UBool isSet = FALSE;
1736    if (fGenericPartialLocationColCount >= 2) {
1737        for (int32_t i = 0; i < fGenericPartialLocationRowCount; i++) {
1738            if (mzid.compare(fGenericPartialLocationStrings[i][0], -1) == 0) {
1739                if (isShort) {
1740                    if (fGenericPartialLocationColCount >= 3) {
1741                        if (!commonlyUsedOnly ||
1742                            fGenericPartialLocationColCount == 3 ||
1743                            fGenericPartialLocationStrings[i][3][0] != 0) {
1744                                result.setTo(fGenericPartialLocationStrings[i][2], -1);
1745                            isSet = TRUE;
1746                        }
1747                    }
1748                } else {
1749                    result.setTo(fGenericPartialLocationStrings[i][1], -1);
1750                    isSet = TRUE;
1751                }
1752                break;
1753            }
1754        }
1755    }
1756    if (!isSet) {
1757        result.remove();
1758    }
1759    return result;
1760}
1761
1762// --------------------------------------------------------------
1763SafeZoneStringFormatPtr::SafeZoneStringFormatPtr(ZSFCacheEntry *cacheEntry)
1764: fCacheEntry(cacheEntry) {
1765}
1766
1767SafeZoneStringFormatPtr::~SafeZoneStringFormatPtr() {
1768    fCacheEntry->delRef();
1769}
1770
1771const ZoneStringFormat*
1772SafeZoneStringFormatPtr::get() const {
1773    return fCacheEntry->getZoneStringFormat();
1774}
1775
1776ZSFCacheEntry::ZSFCacheEntry(const Locale &locale, ZoneStringFormat *zsf, ZSFCacheEntry *next)
1777: fLocale(locale), fZoneStringFormat(zsf),
1778 fNext(next), fRefCount(1)
1779{
1780}
1781
1782ZSFCacheEntry::~ZSFCacheEntry () {
1783    delete fZoneStringFormat;
1784}
1785
1786const ZoneStringFormat*
1787ZSFCacheEntry::getZoneStringFormat(void) {
1788    return (const ZoneStringFormat*)fZoneStringFormat;
1789}
1790
1791void
1792ZSFCacheEntry::delRef(void) {
1793    umtx_lock(&gZSFCacheLock);
1794    --fRefCount;
1795    umtx_unlock(&gZSFCacheLock);
1796}
1797
1798ZSFCache::ZSFCache(int32_t capacity)
1799: fCapacity(capacity), fFirst(NULL) {
1800}
1801
1802ZSFCache::~ZSFCache() {
1803    ZSFCacheEntry *entry = fFirst;
1804    while (entry) {
1805        ZSFCacheEntry *next = entry->fNext;
1806        delete entry;
1807        entry = next;
1808    }
1809}
1810
1811SafeZoneStringFormatPtr*
1812ZSFCache::get(const Locale &locale, UErrorCode &status) {
1813    SafeZoneStringFormatPtr *result = NULL;
1814
1815    // Search the cache entry list
1816    ZSFCacheEntry *entry = NULL;
1817    ZSFCacheEntry *next, *prev;
1818
1819    umtx_lock(&gZSFCacheLock);
1820    entry = fFirst;
1821    prev = NULL;
1822    while (entry) {
1823        next = entry->fNext;
1824        if (entry->fLocale == locale) {
1825            // Add reference count
1826            entry->fRefCount++;
1827
1828            // move the entry to the top
1829            if (entry != fFirst) {
1830                prev->fNext = next;
1831                entry->fNext = fFirst;
1832                fFirst = entry;
1833            }
1834            break;
1835        }
1836        prev = entry;
1837        entry = next;
1838    }
1839    umtx_unlock(&gZSFCacheLock);
1840
1841    // Create a new ZoneStringFormat
1842    if (entry == NULL) {
1843        ZoneStringFormat *zsf = new ZoneStringFormat(locale, status);
1844        if (U_FAILURE(status)) {
1845            delete zsf;
1846            return NULL;
1847        }
1848        if (zsf == NULL) {
1849            status = U_MEMORY_ALLOCATION_ERROR;
1850            return NULL;
1851        }
1852        // Now add the new entry
1853        umtx_lock(&gZSFCacheLock);
1854        // Make sure no other threads already created the one for the same locale
1855        entry = fFirst;
1856        prev = NULL;
1857        while (entry) {
1858            next = entry->fNext;
1859            if (entry->fLocale == locale) {
1860                // Add reference count
1861                entry->fRefCount++;
1862
1863                // move the entry to the top
1864                if (entry != fFirst) {
1865                    prev->fNext = next;
1866                    entry->fNext = fFirst;
1867                    fFirst = entry;
1868                }
1869                break;
1870            }
1871            prev = entry;
1872            entry = next;
1873        }
1874        if (entry == NULL) {
1875            // Add the new one to the top
1876            next = fFirst;
1877            entry = new ZSFCacheEntry(locale, zsf, next);
1878            fFirst = entry;
1879        } else {
1880            delete zsf;
1881        }
1882        umtx_unlock(&gZSFCacheLock);
1883    }
1884
1885    result = new SafeZoneStringFormatPtr(entry);
1886
1887    // Now, delete unused cache entries beyond the capacity
1888    umtx_lock(&gZSFCacheLock);
1889    entry = fFirst;
1890    prev = NULL;
1891    int32_t idx = 1;
1892    while (entry) {
1893        next = entry->fNext;
1894        if (idx >= fCapacity && entry->fRefCount == 0) {
1895            if (entry == fFirst) {
1896                fFirst = next;
1897            } else {
1898                prev->fNext = next;
1899            }
1900            delete entry;
1901        } else {
1902            prev = entry;
1903        }
1904        entry = next;
1905        idx++;
1906    }
1907    umtx_unlock(&gZSFCacheLock);
1908
1909    return result;
1910}
1911
1912
1913/*
1914 * Zone String Formatter String Pool Implementation
1915 *
1916 *    String pool for (UChar *) strings.  Avoids having repeated copies of the same string.
1917 */
1918
1919static const int32_t POOL_CHUNK_SIZE = 2000;
1920struct ZSFStringPoolChunk: public UMemory {
1921    ZSFStringPoolChunk    *fNext;                       // Ptr to next pool chunk
1922    int32_t               fLimit;                       // Index to start of unused area at end of fStrings
1923    UChar                 fStrings[POOL_CHUNK_SIZE];    //  Strings array
1924    ZSFStringPoolChunk();
1925};
1926
1927ZSFStringPoolChunk::ZSFStringPoolChunk() {
1928    fNext = NULL;
1929    fLimit = 0;
1930}
1931
1932ZSFStringPool::ZSFStringPool(UErrorCode &status) {
1933    fChunks = NULL;
1934    fHash   = NULL;
1935    if (U_FAILURE(status)) {
1936        return;
1937    }
1938    fChunks = new ZSFStringPoolChunk;
1939    if (fChunks == NULL) {
1940        status = U_MEMORY_ALLOCATION_ERROR;
1941        return;
1942    }
1943
1944    fHash   = uhash_open(uhash_hashUChars      /* keyHash */,
1945                         uhash_compareUChars   /* keyComp */,
1946                         uhash_compareUChars   /* valueComp */,
1947                         &status);
1948    if (U_FAILURE(status)) {
1949        return;
1950    }
1951}
1952
1953
1954ZSFStringPool::~ZSFStringPool() {
1955    if (fHash != NULL) {
1956        uhash_close(fHash);
1957        fHash = NULL;
1958    }
1959
1960    while (fChunks != NULL) {
1961        ZSFStringPoolChunk *nextChunk = fChunks->fNext;
1962        delete fChunks;
1963        fChunks = nextChunk;
1964    }
1965}
1966
1967static const UChar EmptyString = 0;
1968
1969const UChar *ZSFStringPool::get(const UChar *s, UErrorCode &status) {
1970    const UChar *pooledString;
1971    if (U_FAILURE(status)) {
1972        return &EmptyString;
1973    }
1974
1975    pooledString = static_cast<UChar *>(uhash_get(fHash, s));
1976    if (pooledString != NULL) {
1977        return pooledString;
1978    }
1979
1980    int32_t length = u_strlen(s);
1981    int32_t remainingLength = POOL_CHUNK_SIZE - fChunks->fLimit;
1982    if (remainingLength <= length) {
1983        U_ASSERT(length < POOL_CHUNK_SIZE);
1984        if (length >= POOL_CHUNK_SIZE) {
1985            status = U_INTERNAL_PROGRAM_ERROR;
1986            return &EmptyString;
1987        }
1988        ZSFStringPoolChunk *oldChunk = fChunks;
1989        fChunks = new ZSFStringPoolChunk;
1990        if (fChunks == NULL) {
1991            status = U_MEMORY_ALLOCATION_ERROR;
1992            return &EmptyString;
1993        }
1994        fChunks->fNext = oldChunk;
1995    }
1996
1997    UChar *destString = &fChunks->fStrings[fChunks->fLimit];
1998    u_strcpy(destString, s);
1999    fChunks->fLimit += (length + 1);
2000    uhash_put(fHash, destString, destString, &status);
2001    return destString;
2002}
2003
2004
2005//
2006//  ZSFStringPool::adopt()   Put a string into the hash, but do not copy the string data
2007//                           into the pool's storage.  Used for strings from resource bundles,
2008//                           which will perisist for the life of the zone string formatter, and
2009//                           therefore can be used directly without copying.
2010const UChar *ZSFStringPool::adopt(const UChar * s, UErrorCode &status) {
2011    const UChar *pooledString;
2012    if (U_FAILURE(status)) {
2013        return &EmptyString;
2014    }
2015    if (s != NULL) {
2016        pooledString = static_cast<UChar *>(uhash_get(fHash, s));
2017        if (pooledString == NULL) {
2018            UChar *ncs = const_cast<UChar *>(s);
2019            uhash_put(fHash, ncs, ncs, &status);
2020        }
2021    }
2022    return s;
2023}
2024
2025
2026const UChar *ZSFStringPool::get(const UnicodeString &s, UErrorCode &status) {
2027    UnicodeString &nonConstStr = const_cast<UnicodeString &>(s);
2028    return this->get(nonConstStr.getTerminatedBuffer(), status);
2029}
2030
2031/*
2032 * freeze().   Close the hash table that maps to the pooled strings.
2033 *             After freezing, the pool can not be searched or added to,
2034 *             but all existing references to pooled strings remain valid.
2035 *
2036 *             The main purpose is to recover the storage used for the hash.
2037 */
2038void ZSFStringPool::freeze() {
2039    uhash_close(fHash);
2040    fHash = NULL;
2041}
2042
2043U_NAMESPACE_END
2044
2045#endif /* #if !UCONFIG_NO_FORMATTING */
2046