binaryurp/source/cache.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*************************************************************************
   3 *
   4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5 *
   6 * Copyright 2000, 2011 Oracle and/or its affiliates.
   7 *
   8 * OpenOffice.org - a multi-platform office productivity suite
   9 *
  10 * This file is part of OpenOffice.org.
  11 *
  12 * OpenOffice.org is free software: you can redistribute it and/or modify
  13 * it under the terms of the GNU Lesser General Public License version 3
  14 * only, as published by the Free Software Foundation.
  15 *
  16 * OpenOffice.org is distributed in the hope that it will be useful,
  17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 * GNU Lesser General Public License version 3 for more details
  20 * (a copy is included in the LICENSE file that accompanied this code).
  21 *
  22 * You should have received a copy of the GNU Lesser General Public License
  23 * version 3 along with OpenOffice.org.  If not, see
  24 * <http://www.openoffice.org/license.html>
  25 * for a copy of the LGPLv3 License.
  26 *
  27 ************************************************************************/
  28
  29 #ifndef INCLUDED_BINARYURP_SOURCE_CACHE_HXX
  30 #define INCLUDED_BINARYURP_SOURCE_CACHE_HXX
  31
  32 #include "sal/config.h"
  33
  34 #include <cstddef>
  35 #include <map>
  36
  37 #include "boost/noncopyable.hpp"
  38 #include "osl/diagnose.h"
  39 #include "sal/types.h"
  40
  41 namespace binaryurp {
  42
  43 namespace cache {
  44
  45 enum { size = 256, ignore = 0xFFFF };
  46
  47 }
  48
  49 template< typename T > class Cache: private boost::noncopyable {
  50 public:
  51     explicit Cache(std::size_t size):
  52         size_(size), first_(map_.end()), last_(map_.end())
  53     {
  54         OSL_ASSERT(size < cache::ignore);
  55     }
  56
  57     sal_uInt16 add(T const & content, bool * found) {
  58         OSL_ASSERT(found != 0);
  59         typename Map::iterator i(map_.find(content));
  60         *found = i != map_.end();
  61         if (i == map_.end()) {
  62             typename Map::size_type n = map_.size();
  63             if (n < size_) {
  64                 i =
  65                     (map_.insert(
  66                         typename Map::value_type(
  67                             content,
  68                             Entry(
  69                                 static_cast< sal_uInt16 >(n), map_.end(),
  70                                 first_)))).
  71                     first;
  72                 if (first_ == map_.end()) {
  73                     last_ = i;
  74                 } else {
  75                     first_->second.prev = i;
  76                 }
  77                 first_ = i;
  78             } else if (last_ != map_.end()) {
  79                 i =
  80                     (map_.insert(
  81                         typename Map::value_type(
  82                             content,
  83                             Entry(last_->second.index, map_.end(), first_)))).
  84                     first;
  85                 first_->second.prev = i;
  86                 first_ = i;
  87                 typename Map::iterator j(last_);
  88                 last_ = last_->second.prev;
  89                 last_->second.next = map_.end();
  90                 map_.erase(j);
  91             } else {
  92                 // Reached iff size_ == 0:
  93                 return cache::ignore;
  94             }
  95         } else if (i != first_) {
  96             // Move to front (reached only if size_ > 1):
  97             i->second.prev->second.next = i->second.next;
  98             if (i->second.next == map_.end()) {
  99                 last_ = i->second.prev;
 100             } else {
 101                 i->second.next->second.prev = i->second.prev;
 102             }
 103             i->second.prev = map_.end();
 104             i->second.next = first_;
 105             first_->second.prev = i;
 106             first_ = i;
 107         }
 108         return i->second.index;
 109     }
 110
 111 private:
 112     struct Entry;
 113
 114     typedef std::map< T, Entry > Map;
 115
 116     struct Entry {
 117         sal_uInt16 index;
 118         typename Map::iterator prev;
 119         typename Map::iterator next;
 120
 121         Entry(
 122             sal_uInt16 theIndex, typename Map::iterator thePrev,
 123             typename Map::iterator theNext):
 124             index(theIndex), prev(thePrev), next(theNext) {}
 125     };
 126
 127     std::size_t size_;
 128     Map map_;
 129     typename Map::iterator first_;
 130     typename Map::iterator last_;
 131 };
 132
 133 }
 134
 135 #endif
 136
 137 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */