Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       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/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      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 .
      18             :  */
      19             : 
      20             : #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX
      21             : #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX
      22             : 
      23             : #include "sal/config.h"
      24             : 
      25             : #include <cassert>
      26             : #include <cstddef>
      27             : #include <map>
      28             : 
      29             : #include "boost/noncopyable.hpp"
      30             : #include "sal/types.h"
      31             : 
      32             : namespace binaryurp {
      33             : 
      34             : namespace cache {
      35             : 
      36             : enum { size = 256, ignore = 0xFFFF };
      37             : 
      38             : }
      39             : 
      40       21845 : template< typename T > class Cache: private boost::noncopyable {
      41             : public:
      42       21845 :     explicit Cache(std::size_t size):
      43       21845 :         size_(size), first_(map_.end()), last_(map_.end())
      44             :     {
      45             :         assert(size < cache::ignore);
      46       21845 :     }
      47             : 
      48      233016 :     sal_uInt16 add(T const & content, bool * found) {
      49             :         assert(found != 0);
      50      233016 :         typename Map::iterator i(map_.find(content));
      51      233016 :         *found = i != map_.end();
      52      233016 :         if (i == map_.end()) {
      53      161640 :             typename Map::size_type n = map_.size();
      54      161640 :             if (n < size_) {
      55       87380 :                 i =
      56             :                     (map_.insert(
      57             :                         typename Map::value_type(
      58             :                             content,
      59             :                             Entry(
      60             :                                 static_cast< sal_uInt16 >(n), map_.end(),
      61             :                                 first_)))).
      62             :                     first;
      63       87380 :                 if (first_ == map_.end()) {
      64       21845 :                     last_ = i;
      65             :                 } else {
      66       65535 :                     first_->second.prev = i;
      67             :                 }
      68       87380 :                 first_ = i;
      69       74260 :             } else if (last_ != map_.end()) {
      70       74260 :                 i =
      71             :                     (map_.insert(
      72             :                         typename Map::value_type(
      73             :                             content,
      74             :                             Entry(last_->second.index, map_.end(), first_)))).
      75             :                     first;
      76       74260 :                 first_->second.prev = i;
      77       74260 :                 first_ = i;
      78       74260 :                 typename Map::iterator j(last_);
      79       74260 :                 last_ = last_->second.prev;
      80       74260 :                 last_->second.next = map_.end();
      81       74260 :                 map_.erase(j);
      82             :             } else {
      83             :                 // Reached iff size_ == 0:
      84           0 :                 return cache::ignore;
      85             :             }
      86       71376 :         } else if (i != first_) {
      87             :             // Move to front (reached only if size_ > 1):
      88       40428 :             i->second.prev->second.next = i->second.next;
      89       40428 :             if (i->second.next == map_.end()) {
      90       23676 :                 last_ = i->second.prev;
      91             :             } else {
      92       16752 :                 i->second.next->second.prev = i->second.prev;
      93             :             }
      94       40428 :             i->second.prev = map_.end();
      95       40428 :             i->second.next = first_;
      96       40428 :             first_->second.prev = i;
      97       40428 :             first_ = i;
      98             :         }
      99      233016 :         return i->second.index;
     100             :     }
     101             : 
     102             : private:
     103             :     struct Entry;
     104             : 
     105             :     typedef std::map< T, Entry > Map;
     106             : 
     107             :     struct Entry {
     108             :         sal_uInt16 index;
     109             :         typename Map::iterator prev;
     110             :         typename Map::iterator next;
     111             : 
     112      161640 :         Entry(
     113             :             sal_uInt16 theIndex, typename Map::iterator thePrev,
     114             :             typename Map::iterator theNext):
     115      161640 :             index(theIndex), prev(thePrev), next(theNext) {}
     116             :     };
     117             : 
     118             :     std::size_t size_;
     119             :     Map map_;
     120             :     typename Map::iterator first_;
     121             :     typename Map::iterator last_;
     122             : };
     123             : 
     124             : }
     125             : 
     126             : #endif
     127             : 
     128             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */