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