DEF_TEST(ImageCache_doubleAdd, r) {
    // Adding the same key twice should be safe.
    SkScaledImageCache cache(1024);

    SkBitmap original;
    original.setConfig(SkBitmap::kARGB_8888_Config, 40, 40);
    original.allocPixels();

    SkBitmap scaled;
    scaled.setConfig(SkBitmap::kARGB_8888_Config, 20, 20);
    scaled.allocPixels();

    SkScaledImageCache::ID* id1 = cache.addAndLock(original, 0.5f, 0.5f, scaled);
    SkScaledImageCache::ID* id2 = cache.addAndLock(original, 0.5f, 0.5f, scaled);
    // We don't really care if id1 == id2 as long as unlocking both works.
    cache.unlock(id1);
    cache.unlock(id2);
}

bool
DOMStorageDBParent::RecvPreload(const nsCString& aScope,
                                const uint32_t& aAlreadyLoadedCount,
                                InfallibleTArray<nsString>* aKeys,
                                InfallibleTArray<nsString>* aValues,
                                nsresult* aRv)
{
  DOMStorageDBBridge* db = DOMStorageCache::StartDatabase();
  if (!db) {
    return false;
  }

  nsRefPtr<SyncLoadCacheHelper> cache(
    new SyncLoadCacheHelper(aScope, aAlreadyLoadedCount, aKeys, aValues, aRv));

  db->SyncPreload(cache, true);
  return true;
}

 int numDistinct(string s, string t) {
     //dynamic programming cache
     vector<vector<int>> cache(s.length()+1, vector<int>(t.length()+1, 0));
     
     //base cases
     cache[0][0] = 1;                             //all s and t letters lined up perfectly w/ this recursion
     for (int i=1; i<s.length(); i++) cache[i][0] = 1;  //some s letters were left, but all t letters consumed. Delete all s letters.
     for (int i=1; i<t.length(); i++) cache[0][i] = 0;  //some t letters left over. This is invalid
     
     for (int si = 1; si <= s.length(); si++) {
         for (int ti = 1; ti <= t.length(); ti++) {
             int cand1 = (s[si-1] == t[ti-1]) ? cache[si-1][ti-1] : 0; //matched this letter in s and t, try prev ones!
             int cand2 = cache[si-1][ti];                              //delete this letter in s, and keep trying to match
             cache[si][ti] = cand1 + cand2;
         }
     }
     return cache[s.length()][t.length()];
 }

int main()
{
	Cache cache(1024, 2, 32, Write_Allocate, LRU);
	CachedNum::setLength(8);
	CachedNum::setCache(&cache);

	CachedArray2 A(9, 8, 0x0300);
	CachedArray2 B(8, 8, 0x1500);
	CachedArray2 C(8, 8, 0x2100);

	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			B(i,j) = A(i,j) + C(i,j) + A(i+1, j);

	cache.printStats();

	return 0;
}

void Vehicle::debugWheels(btScalar* m, const btCollisionShape* shape, const btVector3& color,int	debugMode,const btVector3& worldBoundsMin,const btVector3& worldBoundsMax){
	ShapeCache*	sc=cache((btConvexShape*)shape);

	btShapeHull* hull = &sc->m_shapehull; //(btShapeHull*)shape->getUserPointer();

	if (hull->numTriangles () > 0)
	{
		int index = 0;
		const unsigned int* idx = hull->getIndexPointer();
		const btVector3* vtx = hull->getVertexPointer();
		glColor3f(1.0f, 0.0f, .0f);
		glBegin (GL_TRIANGLES);

		for (int i = 0; i < hull->numTriangles (); i++)
		{
			int i1 = index++;
			int i2 = index++;
			int i3 = index++;
			btAssert(i1 < hull->numIndices () &&
				i2 < hull->numIndices () &&
				i3 < hull->numIndices ());

			int index1 = idx[i1];
			int index2 = idx[i2];
			int index3 = idx[i3];
			btAssert(index1 < hull->numVertices () &&
				index2 < hull->numVertices () &&
				index3 < hull->numVertices ());

			btVector3 v1 = vtx[index1];
			btVector3 v2 = vtx[index2];
			btVector3 v3 = vtx[index3];
			btVector3 normal = (v3-v1).cross(v2-v1);
			normal.normalize ();
			glNormal3f(normal.getX(),normal.getY(),normal.getZ());
			glVertex3f (v1.x(), v1.y(), v1.z());
			glVertex3f (v2.x(), v2.y(), v2.z());
			glVertex3f (v3.x(), v3.y(), v3.z());

		}
		glEnd ();
	}
	glNormal3f(0,1,0);
}

  render_result work(render_job job) {
    render_result p;
    
    p.coord = job.coord;
    p.operations.reset(new image_operations);
    p.level = job.level;
    p.cache_hit = false;

    p.path = job.path;
    
    time_t mod = p.level->modification_time();
    std::stringstream ss;
    ss << boost::format("%d.%d.cmap") % job.coord.get_x() % job.coord.get_z();
    std::string basename = ss.str();

    cache_file cache(mc::utils::level_dir(r.cache_dir, job.coord.get_x(), job.coord.get_z()), basename, mod, r.cache_compress);
    
    if (r.cache_use) {
      if (cache.exists()) {
        if (cache.read(p.operations)) {
          p.cache_hit = true;
          return p;
        }
        
        cache.clear();
      }
    }
    
    p.signs = job.level->get_signs();
    job.engine->render(job.level, p.operations);
    
    if (r.cache_use) {
      // create the necessary directories required when caching
      cache.create_directories();
      
      // ignore failure while writing the operations to cache
      if (!cache.write(p.operations)) {
        // on failure, remove the cache file - this will prompt c10t to regenerate it next time
        cache.clear();
      }
    }
    
    return p;
  }

void HarfBuzzFontTest::layout() {
    HarfBuzzFont font;
    CORRADE_VERIFY(font.openFile(Utility::Directory::join(FREETYPEFONT_TEST_DIR, "Oxygen.ttf"), 16.0f));

    /* Fill the cache with some fake glyphs */
    GlyphCache cache(Vector2i(256));
    cache.insert(font.glyphId(U'W'), {25, 34}, {{0, 8}, {16, 128}});
    cache.insert(font.glyphId(U'e'), {25, 12}, {{16, 4}, {64, 32}});

    std::unique_ptr<AbstractLayouter> layouter = font.layout(cache, 0.5f, "Wave");
    CORRADE_VERIFY(layouter);
    CORRADE_COMPARE(layouter->glyphCount(), 4);

    Vector2 cursorPosition;
    Rectangle rectangle;
    Rectangle position;
    Rectangle textureCoordinates;

    /* Difference between this and FreeTypeFont should be _only_ in advances */

    /* 'W' */
    std::tie(position, textureCoordinates) = layouter->renderGlyph(0, cursorPosition = {}, rectangle);
    CORRADE_COMPARE(position, Rectangle({0.78125f, 1.0625f}, {1.28125f, 4.8125f}));
    CORRADE_COMPARE(textureCoordinates, Rectangle({0, 0.03125f}, {0.0625f, 0.5f}));
    CORRADE_COMPARE(cursorPosition, Vector2(0.702637f, 0.0f));

    /* 'a' (not in cache) */
    std::tie(position, textureCoordinates) = layouter->renderGlyph(1, cursorPosition = {}, rectangle);
    CORRADE_COMPARE(position, Rectangle());
    CORRADE_COMPARE(textureCoordinates, Rectangle());
    CORRADE_COMPARE(cursorPosition, Vector2(0.35498f, 0.0f));

    /* 'v' (not in cache) */
    std::tie(position, textureCoordinates) = layouter->renderGlyph(2, cursorPosition = {}, rectangle);
    CORRADE_COMPARE(position, Rectangle());
    CORRADE_COMPARE(textureCoordinates, Rectangle());
    CORRADE_COMPARE(cursorPosition, Vector2(0.34375f, 0.0f));

    /* 'e' */
    std::tie(position, textureCoordinates) = layouter->renderGlyph(3, cursorPosition = {}, rectangle);
    CORRADE_COMPARE(position, Rectangle({0.78125f, 0.375f}, {2.28125f, 1.25f}));
    CORRADE_COMPARE(textureCoordinates, Rectangle({0.0625f, 0.015625f}, {0.25f, 0.125f}));
    CORRADE_COMPARE(cursorPosition, Vector2(0.358398f, 0.0f));
}

ClipRects* RenderLayerClipper::storeClipRectsInCache(const ClipRectsContext& context, ClipRects* parentClipRects, const ClipRects& clipRects) const
{
    ClipRectsCache::Entry& entry = cache().get(context.cacheSlot);
    entry.root = context.rootLayer;
#if ENABLE(ASSERT)
    entry.scrollbarRelevancy = context.scrollbarRelevancy;
#endif

    if (parentClipRects) {
        // If our clip rects match the clip rects of our parent, we share storage.
        if (clipRects == *parentClipRects) {
            entry.clipRects = parentClipRects;
            return parentClipRects;
        }
    }

    entry.clipRects = ClipRects::create(clipRects);
    return entry.clipRects.get();
}

TEST_F(CacheTest, RefreshShouldNotGetKeysForOtherPurpose) {
    KeysCollectionCache cache("test", catalogClient());

    KeysCollectionDocument origKey0(
        0, "dummy", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(100, 0)));
    ASSERT_OK(insertToConfigCollection(
        operationContext(), KeysCollectionDocument::ConfigNS, origKey0.toBSON()));

    {
        auto refreshStatus = cache.refresh(operationContext());
        ASSERT_EQ(ErrorCodes::KeyNotFound, refreshStatus.getStatus());

        auto emptyKeyStatus = cache.getKey(LogicalTime(Timestamp(50, 0)));
        ASSERT_EQ(ErrorCodes::KeyNotFound, emptyKeyStatus.getStatus());
    }

    KeysCollectionDocument origKey1(
        1, "test", TimeProofService::generateRandomKey(), LogicalTime(Timestamp(105, 0)));
    ASSERT_OK(insertToConfigCollection(
        operationContext(), KeysCollectionDocument::ConfigNS, origKey1.toBSON()));

    {
        auto refreshStatus = cache.refresh(operationContext());
        ASSERT_OK(refreshStatus.getStatus());

        auto key = refreshStatus.getValue();
        ASSERT_EQ(1, key.getKeyId());
        ASSERT_EQ(origKey1.getKey(), key.getKey());
        ASSERT_EQ("test", key.getPurpose());
        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
    }

    auto keyStatus = cache.getKey(LogicalTime(Timestamp(60, 1)));
    ASSERT_OK(keyStatus.getStatus());

    {
        auto key = keyStatus.getValue();
        ASSERT_EQ(1, key.getKeyId());
        ASSERT_EQ(origKey1.getKey(), key.getKey());
        ASSERT_EQ("test", key.getPurpose());
        ASSERT_EQ(Timestamp(105, 0), key.getExpiresAt().asTimestamp());
    }
}

void DocLoader::clearPreloads()
{
#if PRELOAD_DEBUG
    printPreloadStats();
#endif
    if (!m_preloads)
        return;

    ListHashSet<CachedResource*>::iterator end = m_preloads->end();
    for (ListHashSet<CachedResource*>::iterator it = m_preloads->begin(); it != end; ++it) {
        CachedResource* res = *it;
        res->decreasePreloadCount();
        if (res->canDelete() && !res->inCache())
            delete res;
        else if (res->preloadResult() == CachedResource::PreloadNotReferenced)
            cache()->remove(res);
    }
    m_preloads.clear();
}

	/** Test {@link VectorCache} without storage, i.e. limit zero. */
	void VectorCacheTest::testLimitZero () {
		const double data[] = { 1.0, 2.0 };
		const size_t dim = sizeof( data ) / sizeof( data[0] );
		AutoVector v( dim ), w( dim );
		VectorCache cache( dim, 0 );

		v.fill( data );
		w.fill( -9.0 );

		assert_false( "Zero cache initially empty", cache.retrieve( 0, w ) );
		assert_eq( "Zero cache w[0]", -9.0, w.get( 0 ) );
		assert_eq( "Zero cache w[1]", -9.0, w.get( 1 ) );

		cache.store( 0, v );

		assert_false( "Zero cache full is empty", cache.retrieve( 0, w ) );
		assert_eq( "Zero cache still w[0]", -9.0, w.get( 0 ) );
		assert_eq( "Zero cache still w[1]", -9.0, w.get( 1 ) );
	}

TEST(MemoryCache, Basic)
{
  IntegerProvider provider;

  {
    Orthanc::MemoryCache cache(provider, 3);
    cache.Access("42");  // 42 -> exit
    cache.Access("43");  // 43, 42 -> exit
    cache.Access("45");  // 45, 43, 42 -> exit
    cache.Access("42");  // 42, 45, 43 -> exit
    cache.Access("43");  // 43, 42, 45 -> exit
    cache.Access("47");  // 45 is removed; 47, 43, 42 -> exit 
    cache.Access("44");  // 42 is removed; 44, 47, 43 -> exit
    cache.Access("42");  // 43 is removed; 42, 44, 47 -> exit
    // Closing the cache: 47, 44, 42 are successively removed
  }

  ASSERT_EQ("45 42 43 47 44 42 ", provider.log_);
}

static PyObject *
create(PyObject *self, PyObject *args)
{
    const char *name;

    if (!PyArg_ParseTuple(args, "s", &name)) {
        return NULL;
    }

    printf("name  %s\n", name);
    printf("block %lu\n", sizeof(potatocache::block_t));
    printf("entry %lu\n", sizeof(potatocache::hash_entry_t));
    printf("head  %lu\n", sizeof(potatocache::mem_header_t));

    potatocache::config config;
    potatocache::api cache(name, config);
    
    Py_RETURN_NONE;
}

CachedImage* DocLoader::requestImage(const String& url)
{
    if (Frame* f = frame()) {
        Settings* settings = f->settings();
        if (!f->loader()->client()->allowImages(!settings || settings->areImagesEnabled()))
            return 0;
    }
    CachedImage* resource = static_cast<CachedImage*>(requestResource(CachedResource::ImageResource, url, String()));
    if (autoLoadImages() && resource && resource->stillNeedsLoad()) {
#ifdef ANDROID_BLOCK_NETWORK_IMAGE
        if (shouldBlockNetworkImage(url)) {
            return resource;
        }
#endif
        resource->setLoading(true);
        cache()->loader()->load(this, resource, true);
    }
    return resource;
}

TEST(CacheTest1, KeepsAllValuesWithinCapacity) {
    cache::lru_cache<int, int> cache(TEST2_CACHE_CAPACITY);

    for (int i = 0; i < NUM_OF_TEST2_RECORDS; ++i) {
        cache.put(i, i);
    }

    for (int i = 0; i < NUM_OF_TEST2_RECORDS - TEST2_CACHE_CAPACITY; ++i) {
        EXPECT_FALSE(cache.exists(i));
    }

    for (int i = NUM_OF_TEST2_RECORDS - TEST2_CACHE_CAPACITY; i < NUM_OF_TEST2_RECORDS; ++i) {
        EXPECT_TRUE(cache.exists(i));
        EXPECT_EQ(i, cache.get(i));
    }

    size_t size = cache.size();
    EXPECT_EQ(TEST2_CACHE_CAPACITY, size);
}

//-----------------------------------------------------------------------------
U32 convertUTF8toUTF16(const UTF8 *unistring, UTF16 *outbuffer, U32 len)
{
   AssertFatal(len >= 1, "Buffer for unicode conversion must be large enough to hold at least the null terminator.");
   PROFILE_SCOPE(convertUTF8toUTF16);

#ifdef TORQUE_ENABLE_UTF16_CACHE
   // If we have cached this conversion already, don't do it again
   U32 hashKey = Torque::hash((const U8 *)unistring, dStrlen(unistring), 0);
   UTF16CacheTable::Iterator cacheItr = sgUTF16Cache.find(hashKey);
   if(cacheItr != sgUTF16Cache.end())
   {
      const UTF16Cache &cache = (*cacheItr).value;
      cache.copyToBuffer(outbuffer, len);
      outbuffer[len-1] = '\0';
      return getMin(cache.mLength,len - 1);
   }
#endif

   U32 walked, nCodepoints;
   UTF32 middleman;
   
   nCodepoints=0;
   while(*unistring != '\0' && nCodepoints < len)
   {
      walked = 1;
      middleman = oneUTF8toUTF32(unistring,&walked);
      outbuffer[nCodepoints] = oneUTF32toUTF16(middleman);
      unistring+=walked;
      nCodepoints++;
   }

   nCodepoints = getMin(nCodepoints,len - 1);
   outbuffer[nCodepoints] = '\0';

#ifdef TORQUE_ENABLE_UTF16_CACHE
   // Cache the results.
   // FIXME As written, this will result in some unnecessary memory copying due to copy constructor calls.
   UTF16Cache cache(outbuffer, nCodepoints);
   sgUTF16Cache.insertUnique(hashKey, cache);
#endif
   
   return nCodepoints; 
}

TEST_F(CanvasFontCacheTest, PageVisibilityChange)
{
    context2d()->setFont("10px sans-serif");
    EXPECT_TRUE(cache()->isInCache("10px sans-serif"));
    page().page().setVisibilityState(PageVisibilityStateHidden, false);
    EXPECT_FALSE(cache()->isInCache("10px sans-serif"));

    context2d()->setFont("15px sans-serif");
    EXPECT_FALSE(cache()->isInCache("10px sans-serif"));
    EXPECT_TRUE(cache()->isInCache("15px sans-serif"));

    context2d()->setFont("10px sans-serif");
    EXPECT_TRUE(cache()->isInCache("10px sans-serif"));
    EXPECT_FALSE(cache()->isInCache("15px sans-serif"));

    page().page().setVisibilityState(PageVisibilityStateVisible, false);
    context2d()->setFont("15px sans-serif");
    context2d()->setFont("10px sans-serif");
    EXPECT_TRUE(cache()->isInCache("10px sans-serif"));
    EXPECT_TRUE(cache()->isInCache("15px sans-serif"));
}

void NAbstractWaveformBuilder::cacheLoad()
{
	QFile cache(m_cacheFile);

	if (m_cacheLoaded || !cache.exists())
		return;

	QByteArray compressed;
	cache.open(QIODevice::ReadOnly);
	QDataStream inFile(&cache);
	inFile >> compressed;
	cache.close();

	QByteArray buffer = qUncompress(compressed);
	QDataStream inBuffer(&buffer, QIODevice::ReadOnly);
	inBuffer >> m_peaksCache >> m_dateHash;

	m_cacheLoaded = true;
}

bool 
PostEffect::initialize (const std::string& filename)
{
    _filename   = filename;
    _shader        = 0;
    if (Ctr::ShaderMgr* shaderMgr = _device->shaderMgr())
    {
        if (!shaderMgr->addShader (_filename, _shader, true))
        {
            LOG ("could not create shader from file " << filename);            
            return false;
        }
    }

    create();
    cache();

    return true;
}

TEST(APITest, ExpireCache )
{
  MyCacheObj obj;
  obj.value = "This is a test";
  OSS::CacheManager cache(60);
  cache.add("123", obj);
  ASSERT_TRUE(cache.has("123"));
  OSS::Cacheable::Ptr data = cache.get("123");
  ASSERT_TRUE(!!data);
  MyCacheObj& cacheData = boost::any_cast<MyCacheObj&>(data->data());
  ASSERT_STREQ(cacheData.value.c_str(), "This is a test");
  cacheData.value = "This is a new value";
  data.reset();
  data = cache.get("123");
  ASSERT_TRUE(!!data);
  ASSERT_STREQ(boost::any_cast<MyCacheObj&>(data->data()).value.c_str(), "This is a new value");
  cache.remove("123");
  ASSERT_FALSE(cache.has("123"));
}