Branch data     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                 :     109525 : template< typename T > class Cache: private boost::noncopyable {
      41                 :            : public:
      42                 :     109531 :     explicit Cache(std::size_t size):
      43 [ +  - ][ +  - ]:     109531 :         size_(size), first_(map_.end()), last_(map_.end())
                 [ +  - ]
      44                 :            :     {
      45                 :            :         assert(size < cache::ignore);
      46                 :     109531 :     }
      47                 :            : 
      48                 :    1406348 :     sal_uInt16 add(T const & content, bool * found) {
      49                 :            :         assert(found != 0);
      50 [ +  - ][ +  - ]:    1406348 :         typename Map::iterator i(map_.find(content));
                 [ +  - ]
      51                 :    1406348 :         *found = i != map_.end();
      52   [ +  +  +  +  :    1406348 :         if (i == map_.end()) {
                   +  + ]
      53                 :     877237 :             typename Map::size_type n = map_.size();
      54   [ +  +  +  +  :     877237 :             if (n < size_) {
                   +  - ]
      55 [ +  - ][ +  - ]:     450278 :                 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 [ +  + ][ +  +  :     450278 :                 if (first_ == map_.end()) {
             +  +  +  + ]
      64                 :     109531 :                     last_ = i;
      65                 :            :                 } else {
      66                 :     340747 :                     first_->second.prev = i;
      67                 :            :                 }
      68                 :     450278 :                 first_ = i;
      69 [ +  - ][ +  - ]:     426959 :             } else if (last_ != map_.end()) {
                 [ #  # ]
      70 [ +  - ][ +  - ]:     426959 :                 i =
                 [ #  # ]
      71                 :            :                     (map_.insert(
      72                 :            :                         typename Map::value_type(
      73                 :            :                             content,
      74                 :            :                             Entry(last_->second.index, map_.end(), first_)))).
      75                 :            :                     first;
      76                 :     426959 :                 first_->second.prev = i;
      77                 :     426959 :                 first_ = i;
      78                 :     426959 :                 typename Map::iterator j(last_);
      79                 :     426959 :                 last_ = last_->second.prev;
      80                 :     426959 :                 last_->second.next = map_.end();
      81 [ +  - ][ #  # ]:     426959 :                 map_.erase(j);
                 [ +  - ]
      82                 :            :             } else {
      83                 :            :                 // Reached iff size_ == 0:
      84                 :          0 :                 return cache::ignore;
      85                 :            :             }
      86 [ +  + ][ +  + ]:     529111 :         } else if (i != first_) {
                 [ +  + ]
      87                 :            :             // Move to front (reached only if size_ > 1):
      88                 :     298337 :             i->second.prev->second.next = i->second.next;
      89   [ +  +  -  +  :     298337 :             if (i->second.next == map_.end()) {
                   -  + ]
      90                 :     118435 :                 last_ = i->second.prev;
      91                 :            :             } else {
      92                 :     179902 :                 i->second.next->second.prev = i->second.prev;
      93                 :            :             }
      94                 :     298337 :             i->second.prev = map_.end();
      95                 :     298337 :             i->second.next = first_;
      96                 :     298337 :             first_->second.prev = i;
      97                 :     298337 :             first_ = i;
      98                 :            :         }
      99                 :    1406348 :         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                 :     877237 :         Entry(
     113                 :            :             sal_uInt16 theIndex, typename Map::iterator thePrev,
     114                 :            :             typename Map::iterator theNext):
     115                 :     877237 :             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: */