source/common/unifiedcache.h

   1 /*
   2 ******************************************************************************
   3 * Copyright (C) 2015, International Business Machines Corporation and
   4 * others. All Rights Reserved.
   5 ******************************************************************************
   6 *
   7 * File UNIFIEDCACHE.H - The ICU Unified cache.
   8 ******************************************************************************
   9 */
  10
  11 #ifndef __UNIFIED_CACHE_H__
  12 #define __UNIFIED_CACHE_H__
  13
  14 #include "utypeinfo.h"  // for 'typeid' to work
  15
  16 #include "unicode/uobject.h"
  17 #include "unicode/locid.h"
  18 #include "sharedobject.h"
  19 #include "unicode/unistr.h"
  20 #include "cstring.h"
  21 #include "ustr_imp.h"
  22
  23 struct UHashtable;
  24 struct UHashElement;
  25
  26 U_NAMESPACE_BEGIN
  27
  28 class UnifiedCache;
  29
  30 /**
  31  * A base class for all cache keys.
  32  */
  33 class U_COMMON_API CacheKeyBase : public UObject {
  34  public:
  35    CacheKeyBase() : fCreationStatus(U_ZERO_ERROR), fIsMaster(FALSE) {}
  36
  37    /**
  38     * Copy constructor. Needed to support cloning.
  39     */
  40    CacheKeyBase(const CacheKeyBase &other)
  41            : UObject(other), fCreationStatus(other.fCreationStatus), fIsMaster(FALSE) { }
  42    virtual ~CacheKeyBase();
  43
  44    /**
  45     * Returns the hash code for this object.
  46     */
  47    virtual int32_t hashCode() const = 0;
  48
  49    /**
  50     * Clones this object polymorphically. Caller owns returned value.
  51     */
  52    virtual CacheKeyBase *clone() const = 0;
  53
  54    /**
  55     * Equality operator.
  56     */
  57    virtual UBool operator == (const CacheKeyBase &other) const = 0;
  58
  59    /**
  60     * Create a new object for this key. Called by cache on cache miss.
  61     * createObject must add a reference to the object it returns. Note
  62     * that getting an object from the cache and returning it without calling
  63     * removeRef on it satisfies this requirement. It can also return NULL
  64     * and set status to an error.
  65     *
  66     * @param creationContext the context in which the object is being
  67     *                        created. May be NULL.
  68     * @param status          Implementations can return a failure here.
  69     *                        In addition, implementations may return a
  70     *                        non NULL object and set a warning status.
  71     */
  72    virtual const SharedObject *createObject(
  73            const void *creationContext, UErrorCode &status) const = 0;
  74
  75    /**
  76     * Writes a description of this key to buffer and returns buffer. Written
  77     * description is NULL terminated.
  78     */
  79    virtual char *writeDescription(char *buffer, int32_t bufSize) const = 0;
  80
  81    /**
  82     * Inequality operator.
  83     */
  84    UBool operator != (const CacheKeyBase &other) const {
  85        return !(*this == other);
  86    }
  87  private:
  88    mutable UErrorCode fCreationStatus;
  89    mutable UBool fIsMaster;
  90    friend class UnifiedCache;
  91 };
  92
  93
  94
  95 /**
  96  * Templated version of CacheKeyBase.
  97  * A key of type LocaleCacheKey<T> maps to a value of type T.
  98  */
  99 template<typename T>
 100 class CacheKey : public CacheKeyBase {
 101  public:
 102    virtual ~CacheKey() { }
 103    /**
 104     * The template parameter, T, determines the hash code returned.
 105     */
 106    virtual int32_t hashCode() const {
 107        const char *s = typeid(T).name();
 108        return ustr_hashCharsN(s, uprv_strlen(s));
 109    }
 110
 111    /**
 112     * Use the value type, T,  as the description.
 113     */
 114    virtual char *writeDescription(char *buffer, int32_t bufLen) const {
 115        const char *s = typeid(T).name();
 116        uprv_strncpy(buffer, s, bufLen);
 117        buffer[bufLen - 1] = 0;
 118        return buffer;
 119    }
 120
 121    /**
 122     * Two objects are equal if they are of the same type.
 123     */
 124    virtual UBool operator == (const CacheKeyBase &other) const {
 125        return typeid(*this) == typeid(other);
 126    }
 127 };
 128
 129 /**
 130  * Cache key based on locale.
 131  * A key of type LocaleCacheKey<T> maps to a value of type T.
 132  */
 133 template<typename T>
 134 class LocaleCacheKey : public CacheKey<T> {
 135  protected:
 136    Locale   fLoc;
 137  public:
 138    LocaleCacheKey(const Locale &loc) : fLoc(loc) {};
 139    LocaleCacheKey(const LocaleCacheKey<T> &other)
 140            : CacheKey<T>(other), fLoc(other.fLoc) { }
 141    virtual ~LocaleCacheKey() { }
 142    virtual int32_t hashCode() const {
 143        return 37 *CacheKey<T>::hashCode() + fLoc.hashCode();
 144    }
 145    virtual UBool operator == (const CacheKeyBase &other) const {
 146        // reflexive
 147        if (this == &other) {
 148            return TRUE;
 149        }
 150        if (!CacheKey<T>::operator == (other)) {
 151            return FALSE;
 152        }
 153        // We know this and other are of same class because operator== on
 154        // CacheKey returned true.
 155        const LocaleCacheKey<T> *fOther =
 156                static_cast<const LocaleCacheKey<T> *>(&other);
 157        return fLoc == fOther->fLoc;
 158    }
 159    virtual CacheKeyBase *clone() const {
 160        return new LocaleCacheKey<T>(*this);
 161    }
 162    virtual const T *createObject(
 163            const void *creationContext, UErrorCode &status) const;
 164    /**
 165     * Use the locale id as the description.
 166     */
 167    virtual char *writeDescription(char *buffer, int32_t bufLen) const {
 168        const char *s = fLoc.getName();
 169        uprv_strncpy(buffer, s, bufLen);
 170        buffer[bufLen - 1] = 0;
 171        return buffer;
 172    }
 173
 174 };
 175
 176 /**
 177  * The unified cache. A singleton type.
 178  * Design doc here:
 179  * https://docs.google.com/document/d/1RwGQJs4N4tawNbf809iYDRCvXoMKqDJihxzYt1ysmd8/edit?usp=sharing
 180  */
 181 class U_COMMON_API UnifiedCache : public UnifiedCacheBase {
 182  public:
 183    /**
 184     * @internal
 185     * Do not call directly. Instead use UnifiedCache::getInstance() as
 186     * there should be only one UnifiedCache in an application.
 187     */
 188    UnifiedCache(UErrorCode &status);
 189
 190    /**
 191     * Returns the cache instance.
 192     */
 193    static UnifiedCache *getInstance(UErrorCode &status);
 194
 195    /**
 196     * Fetches a value from the cache by key. Equivalent to
 197     * get(key, NULL, ptr, status);
 198     */
 199    template<typename T>
 200    void get(
 201            const CacheKey<T>& key,
 202            const T *&ptr,
 203            UErrorCode &status) const {
 204        get(key, NULL, ptr, status);
 205    }
 206
 207    /**
 208     * Fetches value from the cache by key.
 209     *
 210     * @param key             the cache key.
 211     * @param creationContext passed verbatim to createObject method of key
 212     * @param ptr             On entry, ptr must be NULL or be included if
 213     *                        the reference count of the object it points
 214     *                        to. On exit, ptr points to the fetched object
 215     *                        from the cache or is left unchanged on
 216     *                        failure. Caller must call removeRef on ptr
 217     *                        if set to a non NULL value.
 218     * @param status          Any error returned here. May be set to a
 219     *                        warning value even if ptr is set.
 220     */
 221    template<typename T>
 222    void get(
 223            const CacheKey<T>& key,
 224            const void *creationContext,
 225            const T *&ptr,
 226            UErrorCode &status) const {
 227        if (U_FAILURE(status)) {
 228            return;
 229        }
 230        UErrorCode creationStatus = U_ZERO_ERROR;
 231        const SharedObject *value = NULL;
 232        _get(key, value, creationContext, creationStatus);
 233        const T *tvalue = (const T *) value;
 234        if (U_SUCCESS(creationStatus)) {
 235            SharedObject::copyPtr(tvalue, ptr);
 236        }
 237        SharedObject::clearPtr(tvalue);
 238        // Take care not to overwrite a warning status passed in with
 239        // another warning or U_ZERO_ERROR.
 240        if (status == U_ZERO_ERROR || U_FAILURE(creationStatus)) {
 241            status = creationStatus;
 242        }
 243    }
 244
 245 #ifdef UNIFIED_CACHE_DEBUG
 246    /**
 247     * Dumps the contents of this cache to standard error. Used for testing of
 248     * cache only.
 249     */
 250    void dumpContents() const;
 251 #endif
 252
 253    /**
 254     * Convenience method to get a value of type T from cache for a
 255     * particular locale with creationContext == NULL.
 256     * @param loc    the locale
 257     * @param ptr    On entry, must be NULL or included in the ref count
 258     *               of the object to which it points.
 259     *               On exit, fetched value stored here or is left
 260     *               unchanged on failure. Caller must call removeRef on
 261     *               ptr if set to a non NULL value.
 262     * @param status Any error returned here. May be set to a
 263     *               warning value even if ptr is set.
 264     */
 265    template<typename T>
 266    static void getByLocale(
 267            const Locale &loc, const T *&ptr, UErrorCode &status) {
 268        const UnifiedCache *cache = getInstance(status);
 269        if (U_FAILURE(status)) {
 270            return;
 271        }
 272        cache->get(LocaleCacheKey<T>(loc), ptr, status);
 273    }
 274
 275 #ifdef UNIFIED_CACHE_DEBUG
 276    /**
 277     * Dumps the cache contents to stderr. For testing only.
 278     */
 279    static void dump();
 280 #endif
 281
 282    /**
 283     * Returns the number of keys in this cache. For testing only.
 284     */
 285    int32_t keyCount() const;
 286
 287    /**
 288     * Removes any values from cache that are not referenced outside
 289     * the cache.
 290     */
 291    void flush() const;
 292
 293    /**
 294     * Configures at what point evcition of unused entries will begin.
 295     * Eviction is triggered whenever the number of unused entries exeeds
 296     * BOTH count AND (number of in-use items) * (percentageOfInUseItems / 100).
 297     * Once the number of unused entries drops below one of these,
 298     * eviction ceases. Because eviction happens incrementally,
 299     * the actual unused entry count may exceed both these numbers
 300     * from time to time.
 301     *
 302     * A cache entry is defined as unused if it is not essential to guarantee
 303     * that for a given key X, the cache returns the same reference to the
 304     * same value as long as the client already holds a reference to that
 305     * value.
 306     *
 307     * If this method is never called, the default settings are 1000 and 100%.
 308     *
 309     * Although this method is thread-safe, it is designed to be called at
 310     * application startup. If it is called in the middle of execution, it
 311     * will have no immediate effect on the cache. However over time, the
 312     * cache will perform eviction slices in an attempt to honor the new
 313     * settings.
 314     *
 315     * If a client already holds references to many different unique values
 316     * in the cache such that the number of those unique values far exeeds
 317     * "count" then the cache may not be able to maintain this maximum.
 318     * However, if this happens, the cache still guarantees that the number of
 319     * unused entries will remain only a small percentage of the total cache
 320     * size.
 321     *
 322     * If the parameters passed are negative, setEvctionPolicy sets status to
 323     * U_ILLEGAL_ARGUMENT_ERROR.
 324     */
 325    void setEvictionPolicy(
 326            int32_t count, int32_t percentageOfInUseItems, UErrorCode &status);
 327
 328
 329    /**
 330     * Returns how many entries have been auto evicted during the lifetime
 331     * of this cache. This only includes auto evicted entries, not
 332     * entries evicted because of a call to flush().
 333     */
 334    int64_t autoEvictedCount() const;
 335
 336    /**
 337     * Returns the unused entry count in this cache. For testing only,
 338     * Regular clients will not need this.
 339     */
 340    int32_t unusedCount() const;
 341
 342    virtual void incrementItemsInUse() const;
 343    virtual void decrementItemsInUseWithLockingAndEviction() const;
 344    virtual void decrementItemsInUse() const;
 345    virtual ~UnifiedCache();
 346  private:
 347    UHashtable *fHashtable;
 348    mutable int32_t fEvictPos;
 349    mutable int32_t fItemsInUseCount;
 350    int32_t fMaxUnused;
 351    int32_t fMaxPercentageOfInUse;
 352    mutable int64_t fAutoEvictedCount;
 353    UnifiedCache(const UnifiedCache &other);
 354    UnifiedCache &operator=(const UnifiedCache &other);
 355    UBool _flush(UBool all) const;
 356    void _get(
 357            const CacheKeyBase &key,
 358            const SharedObject *&value,
 359            const void *creationContext,
 360            UErrorCode &status) const;
 361    UBool _poll(
 362            const CacheKeyBase &key,
 363            const SharedObject *&value,
 364            UErrorCode &status) const;
 365    void _putNew(
 366            const CacheKeyBase &key,
 367            const SharedObject *value,
 368            const UErrorCode creationStatus,
 369            UErrorCode &status) const;
 370    void _putIfAbsentAndGet(
 371            const CacheKeyBase &key,
 372            const SharedObject *&value,
 373            UErrorCode &status) const;
 374    const UHashElement *_nextElement() const;
 375    int32_t _computeCountOfItemsToEvict() const;
 376    void _runEvictionSlice() const;
 377    void _registerMaster(
 378         const CacheKeyBase *theKey, const SharedObject *value) const;
 379    void _put(
 380            const UHashElement *element,
 381            const SharedObject *value,
 382            const UErrorCode status) const;
 383 #ifdef UNIFIED_CACHE_DEBUG
 384    void _dumpContents() const;
 385 #endif
 386    static void copyPtr(const SharedObject *src, const SharedObject *&dest);
 387    static void clearPtr(const SharedObject *&ptr);
 388    static void _fetch(
 389            const UHashElement *element,
 390            const SharedObject *&value,
 391            UErrorCode &status);
 392    static UBool _inProgress(const UHashElement *element);
 393    static UBool _inProgress(
 394            const SharedObject *theValue, UErrorCode creationStatus);
 395    static UBool _isEvictable(const UHashElement *element);
 396 };
 397
 398 U_NAMESPACE_END
 399
 400 #endif