File indexing completed on 2024-05-19 15:12:19

0001 /*
0002     Large image displaying library.
0003 
0004     Copyright (C) 2004,2005 Maks Orlovich (maksim@kde.org)
0005 
0006     Permission is hereby granted, free of charge, to any person obtaining a copy
0007     of this software and associated documentation files (the "Software"), to deal
0008     in the Software without restriction, including without limitation the rights
0009     to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0010     copies of the Software, and to permit persons to whom the Software is
0011     furnished to do so, subject to the following conditions:
0012 
0013     The above copyright notice and this permission notice shall be included in
0014     all copies or substantial portions of the Software.
0015 
0016     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0017     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0018     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
0019     AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
0020     AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
0021     CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
0022 
0023 */
0024 
0025 #ifndef TILE_CACHE_H
0026 #define TILE_CACHE_H
0027 
0028 #include <assert.h>
0029 
0030 #include "tile.h"
0031 
0032 namespace khtmlImLoad
0033 {
0034 
0035 class TileCacheNode
0036 {
0037 public:
0038     //Interface to the cache LRU chains
0039     TileCacheNode *cacheNext;
0040     TileCacheNode *cachePrev;
0041 
0042     void unlink()
0043     {
0044         cacheNext->cachePrev = cachePrev;
0045         cachePrev->cacheNext = cacheNext;
0046         cacheNext = nullptr;
0047         cachePrev = nullptr;
0048     }
0049 
0050     void linkBefore(TileCacheNode *node)
0051     {
0052         this->cacheNext = node;
0053         this->cachePrev = node->cachePrev;
0054 
0055         node->cachePrev = this;
0056         this->cachePrev->cacheNext = this;
0057     }
0058 
0059     Tile *tile;
0060 
0061     TileCacheNode(): cacheNext(nullptr), cachePrev(nullptr), tile(nullptr)
0062     {}
0063 };
0064 
0065 /**
0066  An LRU-replacement cache for tiles.
0067 */
0068 class TileCache
0069 {
0070 public:
0071     typedef TileCacheNode Node;
0072 
0073     Node *poolHead;
0074 
0075     //### TODO: consider smarter allocation for these?.
0076     Node *create()
0077     {
0078         if (poolHead) {
0079             Node *toRet = poolHead;
0080             poolHead    = poolHead->cacheNext;
0081             return toRet;
0082         } else {
0083             return new Node();
0084         }
0085     }
0086 
0087     void release(Node *entry)
0088     {
0089         //### TODO: Limit ??
0090         entry->cacheNext = poolHead;
0091         poolHead         = entry;
0092     }
0093 
0094 private:
0095     int sizeLimit;
0096     int size;
0097 
0098     /**
0099      We keep tiles in a double-linked list, with the most recent one being at the rear
0100     */
0101     Node *front;
0102     Node *rear;
0103 
0104     /**
0105      Discard the node, and removes it from the list. Does not free the node.
0106     */
0107     void doDiscard(Node *node)
0108     {
0109         assert(node->tile->cacheNode == node);
0110         node->tile->discard();
0111         node->tile->cacheNode = nullptr;
0112         node->unlink();
0113         --size;
0114         assert(size >= 0);
0115     }
0116 public:
0117 
0118     TileCache(int _sizeLimit): sizeLimit(_sizeLimit), size(0)
0119     {
0120         front = new Node;
0121         rear  = new Node;
0122 
0123         front->cacheNext = rear;
0124         rear ->cachePrev = front;
0125 
0126         poolHead = nullptr;
0127     }
0128 
0129     /**
0130      Add an entry to the cache.
0131      */
0132     void addEntry(Tile *tile)
0133     {
0134         assert(tile->cacheNode == nullptr);
0135 
0136         Node *node;
0137 
0138         //Must have room
0139         if (size >= sizeLimit) {
0140             //Remove the front entry, reuse it
0141             //for the new node
0142             node = front->cacheNext;
0143             doDiscard(node);
0144         } else {
0145             node = create();
0146         }
0147 
0148         //Link in before the end sentinel, i.e. at the very last spot, increment usage count
0149         node->tile            = tile;
0150         tile->cacheNode       = node;
0151         node->linkBefore(rear);
0152         size++;
0153     }
0154 
0155     /**
0156      "Touches" the entry, making it the most recent
0157      (i.e. moves the entry to the rear of the chain)
0158      */
0159     void touchEntry(Tile *tile)
0160     {
0161         Node *node = tile->cacheNode;
0162         node->unlink();
0163         node->linkBefore(rear);
0164     }
0165 
0166     /**
0167      Removes the entry from the cache, discards it.
0168      */
0169     void removeEntry(Tile *tile)
0170     {
0171         Node *node = tile->cacheNode;
0172         doDiscard(node);
0173 
0174         release(node);
0175     }
0176 };
0177 
0178 }
0179 
0180 #endif