MySQL 8.3.0
Source Code Documentation
free_list.h
Go to the documentation of this file.
1/* Copyright (c) 2015, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef DD_CACHE__FREE_LIST_INCLUDED
24#define DD_CACHE__FREE_LIST_INCLUDED
25
26#include <assert.h>
27#include <vector> // vector
28
29#include "sql/malloc_allocator.h" // Malloc_allocator.
30#include "sql/psi_memory_key.h" // key_memory_DD_cache_infrastructure
31
32namespace dd {
33namespace cache {
34
35/**
36 Template for management of a free list based on a std::vector.
37
38 The free list template defines functions mostly wrapping the std::vector
39 functions, but additionally doing some asserts to ensure correct usage.
40
41 The first element in the free list is the least recently used element.
42 When a new element becomes unused, it is added to the end of the free list.
43 An element may also be removed from within the middle of the free list
44 when the element is being acquired. This use case means iterating through
45 the vector to find the correct element.
46
47 @tparam E Element type (a Cache_element wrapping some dictionary
48 object type).
49*/
50
51template <typename E>
52class Free_list {
53 private:
54 typedef std::vector<E *, Malloc_allocator<E *>> List_type;
55 List_type m_list; // The actual list.
56
57 public:
60
61 // Return the actual free list length.
62 size_t length() const { return m_list.size(); }
63
64 /**
65 Add an element to the end of the free list.
66
67 @param element Element to add to the end of the list.
68 */
69
70 void add_last(E *element) {
71 assert(element != nullptr && element->usage() == 0);
72 m_list.push_back(element);
73 }
74
75 /**
76 Remove an element from the free list.
77
78 @param element Element to be removed from the list.
79 */
80
81 void remove(E *element) {
82 assert(element != nullptr && element->usage() == 0);
83 assert(!m_list.empty());
84
85 for (typename List_type::iterator it = m_list.begin(); it != m_list.end();
86 ++it)
87 if (*it == element) {
88 m_list.erase(it);
89 return;
90 }
91
92 assert(false); /* purecov: deadcode */
93 }
94
95 /**
96 Get the least recently used element in the list, i.e., the first element.
97
98 @return The least recently used element in the list.
99 */
100
101 E *get_lru() const {
102 assert(!m_list.empty());
103 if (!m_list.empty()) return m_list.front();
104 return nullptr;
105 }
106
107 /**
108 Debug dump of the free list to stderr.
109 */
110 /* purecov: begin inspected */
111 void dump() const {
112#ifndef NDEBUG
113 if (m_list.empty()) {
114 fprintf(stderr, " lru-> NULL\n");
115 return;
116 }
117 fprintf(stderr, " lru-> ");
118 for (typename List_type::const_iterator it = m_list.begin();
119 it != m_list.end(); ++it)
120 fprintf(stderr, "%llu ", (*it)->object()->id());
121 fprintf(stderr, "\n");
122#endif
123 }
124 /* purecov: end */
125};
126
127} // namespace cache
128} // namespace dd
129
130#endif // DD_CACHE__FREE_LIST_INCLUDED
Malloc_allocator is a C++ STL memory allocator based on my_malloc/my_free.
Definition: malloc_allocator.h:62
Template for management of a free list based on a std::vector.
Definition: free_list.h:52
void dump() const
Debug dump of the free list to stderr.
Definition: free_list.h:111
List_type m_list
Definition: free_list.h:55
void remove(E *element)
Remove an element from the free list.
Definition: free_list.h:81
std::vector< E *, Malloc_allocator< E * > > List_type
Definition: free_list.h:54
Free_list()
Definition: free_list.h:58
size_t length() const
Definition: free_list.h:62
void add_last(E *element)
Add an element to the end of the free list.
Definition: free_list.h:70
E * get_lru() const
Get the least recently used element in the list, i.e., the first element.
Definition: free_list.h:101
The version of the current data dictionary table definitions.
Definition: dictionary_client.h:42
PSI_memory_key key_memory_DD_cache_infrastructure
Definition: psi_memory_key.cc:36