libstdc++
list_update_policy.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2021 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file list_update_policy.hpp
38  * Contains policies for list update containers.
39  */
40 
41 #ifndef PB_DS_LU_POLICY_HPP
42 #define PB_DS_LU_POLICY_HPP
43 
44 #include <bits/c++config.h>
45 #include <cstdlib>
49 
50 namespace __gnu_pbds
51 {
52  /**
53  * A list-update policy that unconditionally moves elements to the
54  * front of the list. A null type means that each link in a
55  * list-based container does not actually need metadata.
56  */
57  template<typename _Alloc = std::allocator<char> >
59  {
60  public:
61  typedef _Alloc allocator_type;
62 
63  /// Metadata on which this functor operates.
65 
66  public:
67  /// Reference to metadata on which this functor operates.
68  typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
70 
71  /// Creates a metadata object.
73  operator()() const
74  { return s_metadata; }
75 
76  /// Decides whether a metadata object should be moved to the front
77  /// of the list.
78  inline bool
79  operator()(metadata_reference r_metadata) const
80  { return true; }
81 
82  private:
83  static null_type s_metadata;
84  };
85 
86  /**
87  * A list-update policy that moves elements to the front of the
88  * list based on the counter algorithm.
89  */
90  template<std::size_t Max_Count = 5, typename _Alloc = std::allocator<char> >
92  : private detail::lu_counter_policy_base<typename _Alloc::size_type>
93  {
94  public:
95  typedef _Alloc allocator_type;
96  typedef typename allocator_type::size_type size_type;
97 
98  enum
99  {
100  /// When some element is accessed this number of times, it
101  /// will be moved to the front of the list.
102  max_count = Max_Count
103  };
104 
105  /// Metadata on which this functor operates.
107 
108  private:
110 
111  public:
112  /// Reference to metadata on which this functor operates.
113  typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
115 
116  /// Creates a metadata object.
118  operator()() const
119  { return base_type::operator()(max_count); }
120 
121  /// Decides whether a metadata object should be moved to the front
122  /// of the list.
123  bool
125  { return base_type::operator()(r_data, max_count); }
126  };
127 } // namespace __gnu_pbds
128 
129 #endif
metadata_type operator()() const
Creates a metadata object.
metadata_type operator()() const
Creates a metadata object.
A list-update metadata type that moves elements to the front of the list based on the counter algorit...
detail::rebind_traits< _Alloc, metadata_type >::reference metadata_reference
Reference to metadata on which this functor operates.
Base class for list-update counter policy.
Represents no type, or absence of type, for template tricks.
When some element is accessed this number of times, it will be moved to the front of the list...
bool operator()(metadata_reference r_metadata) const
Decides whether a metadata object should be moved to the front of the list.
detail::lu_counter_metadata< size_type > metadata_type
Metadata on which this functor operates.
bool operator()(metadata_reference r_data) const
Decides whether a metadata object should be moved to the front of the list.
null_type metadata_type
Metadata on which this functor operates.
GNU extensions for policy-based data structures for public use.
detail::rebind_traits< _Alloc, metadata_type >::reference metadata_reference
Reference to metadata on which this functor operates.