1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 * This file incorporates work covered by the following license notice:
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
20 #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX
21 #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX
23 #include <sal/config.h>
30 #include <sal/types.h>
36 enum { size
= 256, ignore
= 0xFFFF };
40 template< typename T
> class Cache
{
42 typedef sal_uInt16 IdxType
;
44 explicit Cache(std::size_t size
):
47 assert(size
< cache::ignore
);
50 IdxType
add( const T
& rContent
, bool* pbFound
) {
51 assert( pbFound
!= nullptr);
56 // try to insert into the map
57 list_
.push_front( rContent
); // create a temp entry
58 auto const [it
, inserted
] = map_
.emplace( list_
.begin(), 0 );
61 if( !inserted
) { // insertion not needed => found the entry
62 list_
.pop_front(); // remove the temp entry
63 list_
.splice( list_
.begin(), list_
, it
->first
); // the found entry is moved to front
67 // test insertion successful => it was new so we keep it
68 IdxType n
= static_cast<IdxType
>( map_
.size() - 1);
69 if( n
>= size_
) { // cache full => replace the LRU entry
70 // find the least recently used element in the map
71 typename
LruItMap::iterator lru
= map_
.find( --list_
.end());
73 map_
.erase( lru
); // remove it from the map
74 list_
.pop_back(); // remove from the list
81 Cache(const Cache
&) = delete;
82 Cache
& operator=(const Cache
&) = delete;
84 typedef std::list
<T
> LruList
; // last recently used list
85 typedef typename
LruList::iterator LruListIt
;
86 struct CmpT
{ bool operator()( const LruListIt
& rA
, const LruListIt
& rB
) const { return (*rA
<*rB
);}};
87 typedef std::map
< LruListIt
, IdxType
, CmpT
> LruItMap
; // a map into a LruList
98 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */