MySQL 8.0.30
Source Code Documentation
discrete_interval.h
Go to the documentation of this file.
1#ifndef DISCRETE_INTERVAL_INCLUDED
2#define DISCRETE_INTERVAL_INCLUDED
3
4/* Copyright (c) 2000, 2022, Oracle and/or its affiliates.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License, version 2.0,
8 as published by the Free Software Foundation.
9
10 This program is also distributed with certain software (including
11 but not limited to OpenSSL) that is licensed under separate terms,
12 as designated in a particular file or component or in included license
13 documentation. The authors of MySQL hereby grant you an additional
14 permission to link the program and your derivative works with the
15 separately licensed software that they have included with MySQL.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License, version 2.0, for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25
26#include <limits.h>
27
28#include "my_dbug.h"
29#include "my_inttypes.h"
30
31/*
32 Such interval is "discrete": it is the set of
33 { auto_inc_interval_min + k * increment,
34 0 <= k <= (auto_inc_interval_values-1) }
35 Where "increment" is maintained separately by the user of this class (and is
36 currently only thd->variables.auto_increment_increment).
37 It mustn't be allocated on a MEM_ROOT, because SET INSERT_ID needs to
38 allocate memory which must stay allocated for use by the next statement.
39*/
41 private:
44 ulonglong interval_max; // excluded bound. Redundant.
45 public:
46 Discrete_interval *next; // used when linked into Discrete_intervals_list
47
48 /// Determine if the given value is within the interval
49 bool in_range(const ulonglong value) const {
50 return ((value >= interval_min) && (value < interval_max));
51 }
52
55 interval_values = val;
56 interval_max = (val == ULLONG_MAX) ? val : start + val * incr;
57 }
59 : next(nullptr) {
60 replace(start, val, incr);
61 }
63 ulonglong minimum() const { return interval_min; }
64 ulonglong values() const { return interval_values; }
65 ulonglong maximum() const { return interval_max; }
66 /*
67 If appending [3,5] to [1,2], we merge both in [1,5] (they should have the
68 same increment for that, user of the class has to ensure that). That is
69 just a space optimization. Returns 0 if merge succeeded.
70 */
72 if (interval_max == start) {
73 if (val == ULLONG_MAX) {
75 } else {
76 interval_values += val;
77 interval_max = start + val * incr;
78 }
79 return false;
80 }
81 return true;
82 }
83};
84
85/// List of Discrete_interval objects
87/**
88 Discrete_intervals_list objects are used to remember the
89 intervals of autoincrement values that have been used by the
90 current INSERT statement, so that the values can be written to the
91 binary log. However, the binary log can currently only store the
92 beginning of the first interval (because WL#3404 is not yet
93 implemented). Hence, it is currently not necessary to store
94 anything else than the first interval, in the list. When WL#3404 is
95 implemented, we should change the '# define' below.
96*/
97#define DISCRETE_INTERVAL_LIST_HAS_MAX_ONE_ELEMENT 1
98
99 private:
100 /**
101 To avoid heap allocation in the common case when there is only one
102 interval in the list, we store the first interval here.
103 */
107 /**
108 When many intervals are provided at the beginning of the execution of a
109 statement (in a replication slave or SET INSERT_ID), "current" points to
110 the interval being consumed by the thread now (so "current" goes from
111 "head" to "tail" then to NULL).
112 */
114 uint elements; ///< number of elements
115 void operator=(Discrete_intervals_list &); // prevent use of this
116 bool append(Discrete_interval *new_interval) {
117 if (unlikely(new_interval == nullptr)) return true;
118 DBUG_PRINT("info", ("adding new auto_increment interval"));
119 if (head == nullptr)
120 head = current = new_interval;
121 else
122 tail->next = new_interval;
123 tail = new_interval;
124 elements++;
125 return false;
126 }
128 const Discrete_interval *o_first_interval = &other->first_interval;
130 head = other->head == o_first_interval ? &first_interval : other->head;
131 tail = other->tail == o_first_interval ? &first_interval : other->tail;
132 current =
133 other->current == o_first_interval ? &first_interval : other->current;
134 elements = other->elements;
135 }
137 copy_shallow(&other);
138 }
139
140 public:
143 void clear() {
144 if (head) {
145 // first element, not on heap, should not be delete-d; start with next:
146 for (Discrete_interval *i = head->next; i;) {
147#ifdef DISCRETE_INTERVAL_LIST_HAS_MAX_ONE_ELEMENT
148 assert(0);
149#endif
150 Discrete_interval *next = i->next;
151 delete i;
152 i = next;
153 }
154 }
155 head = tail = current = nullptr;
156 elements = 0;
157 }
159 const Discrete_intervals_list tmp(*other);
160 other->copy_shallow(this);
161 copy_shallow(&tmp);
162 }
164 const Discrete_interval *tmp = current;
165 if (current != nullptr) current = current->next;
166 return tmp;
167 }
169 /**
170 Appends an interval to the list.
171
172 @param start start of interval
173 @param val how many values it contains
174 @param incr what increment between each value
175 @retval true error
176 @retval false success
177 */
179 // If there are no intervals, add one.
180 if (head == nullptr) {
181 first_interval.replace(start, val, incr);
182 return append(&first_interval);
183 }
184 // If this interval can be merged with previous, do that.
185 if (tail->merge_if_contiguous(start, val, incr) == 0) return false;
186 // If this interval cannot be merged, append it.
187#ifdef DISCRETE_INTERVAL_LIST_HAS_MAX_ONE_ELEMENT
188 /*
189 We cannot create yet another interval as we already contain one. This
190 situation can happen. Assume innodb_autoinc_lock_mode>=1 and
191 CREATE TABLE T(A INT AUTO_INCREMENT PRIMARY KEY) ENGINE=INNODB;
192 INSERT INTO T VALUES (NULL),(NULL),(1025),(NULL);
193 Then InnoDB will reserve [1,4] (because of 4 rows) then
194 [1026,1026]. Only the first interval is important for
195 statement-based binary logging as it tells the starting point. So we
196 ignore the second interval:
197 */
198 return false;
199#else
200 return append(new Discrete_interval(start, val, incr));
201#endif
202 }
203 ulonglong minimum() const { return (head ? head->minimum() : 0); }
204 ulonglong maximum() const { return (head ? tail->maximum() : 0); }
205 uint nb_elements() const { return elements; }
206};
207
208#endif /* DISCRETE_INTERVAL_INCLUDED */
Definition: discrete_interval.h:40
bool merge_if_contiguous(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:71
ulonglong interval_min
Definition: discrete_interval.h:42
Discrete_interval * next
Definition: discrete_interval.h:46
bool in_range(const ulonglong value) const
Determine if the given value is within the interval.
Definition: discrete_interval.h:49
ulonglong maximum() const
Definition: discrete_interval.h:65
Discrete_interval()
Definition: discrete_interval.h:62
ulonglong interval_values
Definition: discrete_interval.h:43
ulonglong interval_max
Definition: discrete_interval.h:44
ulonglong values() const
Definition: discrete_interval.h:64
ulonglong minimum() const
Definition: discrete_interval.h:63
void replace(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:53
Discrete_interval(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:58
List of Discrete_interval objects.
Definition: discrete_interval.h:86
ulonglong maximum() const
Definition: discrete_interval.h:204
uint nb_elements() const
Definition: discrete_interval.h:205
bool append(ulonglong start, ulonglong val, ulonglong incr)
Appends an interval to the list.
Definition: discrete_interval.h:178
void operator=(Discrete_intervals_list &)
Discrete_interval * tail
Definition: discrete_interval.h:106
bool append(Discrete_interval *new_interval)
Definition: discrete_interval.h:116
const Discrete_interval * get_next()
Definition: discrete_interval.h:163
Discrete_interval first_interval
To avoid heap allocation in the common case when there is only one interval in the list,...
Definition: discrete_interval.h:104
void copy_shallow(const Discrete_intervals_list *other)
Definition: discrete_interval.h:127
Discrete_intervals_list()
Definition: discrete_interval.h:141
uint elements
number of elements
Definition: discrete_interval.h:114
ulonglong minimum() const
Definition: discrete_interval.h:203
Discrete_interval * current
When many intervals are provided at the beginning of the execution of a statement (in a replication s...
Definition: discrete_interval.h:113
void swap(Discrete_intervals_list *other)
Definition: discrete_interval.h:158
~Discrete_intervals_list()
Definition: discrete_interval.h:168
Discrete_intervals_list(const Discrete_intervals_list &other)
Definition: discrete_interval.h:136
void clear()
Definition: discrete_interval.h:143
Discrete_interval * head
Definition: discrete_interval.h:105
Fido Client Authentication nullptr
Definition: fido_client_plugin.cc:221
static void start(mysql_harness::PluginFuncEnv *env)
Definition: http_auth_backend_plugin.cc:168
constexpr bool unlikely(bool expr)
Definition: my_compiler.h:55
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:180
Some integer typedefs for easier portability.
unsigned long long int ulonglong
Definition: my_inttypes.h:55
unsigned int uint
Definition: uca-dump.cc:29