binaryurp/source/cache.hxx

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