MySQL  8.0.18
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, 2018, Oracle and/or its affiliates. All rights reserved.
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(NULL) {
60  replace(start, val, incr);
61  }
62  Discrete_interval() : next(NULL) { replace(0, 0, 0); }
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 0;
80  }
81  return 1;
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 == NULL)) return true;
118  DBUG_PRINT("info", ("adding new auto_increment interval"));
119  if (head == NULL)
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:
142  : head(NULL), tail(NULL), current(NULL), elements(0) {}
143  void empty() {
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  DBUG_ASSERT(0);
149 #endif
150  Discrete_interval *next = i->next;
151  delete i;
152  i = next;
153  }
154  }
155  head = tail = current = NULL;
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 != NULL) 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 == NULL) {
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 */
unsigned long long int ulonglong
Definition: my_inttypes.h:55
void swap(Discrete_intervals_list *other)
Definition: discrete_interval.h:158
Some integer typedefs for easier portability.
bool in_range(const ulonglong value) const
Determine if the given value is within the interval.
Definition: discrete_interval.h:49
bool append(Discrete_interval *new_interval)
Definition: discrete_interval.h:116
ulonglong minimum() const
Definition: discrete_interval.h:63
uint nb_elements() const
Definition: discrete_interval.h:205
Discrete_interval(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:58
ulonglong interval_min
Definition: discrete_interval.h:42
void replace(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:53
bool append(ulonglong start, ulonglong val, ulonglong incr)
Appends an interval to the list.
Definition: discrete_interval.h:178
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:179
Discrete_interval * tail
Definition: discrete_interval.h:106
#define DBUG_ASSERT(A)
Definition: my_dbug.h:197
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
Discrete_intervals_list(const Discrete_intervals_list &other)
Definition: discrete_interval.h:136
Discrete_intervals_list()
Definition: discrete_interval.h:141
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 incr(ENGINE_HANDLE *h, ENGINE_HANDLE_V1 *h1)
Definition: suite_stubs.c:109
bool unlikely(bool expr)
Definition: my_compiler.h:65
bool merge_if_contiguous(ulonglong start, ulonglong val, ulonglong incr)
Definition: discrete_interval.h:71
unsigned int uint
Definition: uca-dump.cc:29
ulonglong interval_max
Definition: discrete_interval.h:44
const Discrete_interval * get_next()
Definition: discrete_interval.h:163
Discrete_interval * next
Definition: discrete_interval.h:46
ulonglong interval_values
Definition: discrete_interval.h:43
Discrete_interval * head
Definition: discrete_interval.h:105
Discrete_interval()
Definition: discrete_interval.h:62
#define NULL
Definition: types.h:55
static void start(PluginFuncEnv *env)
Definition: http_server_plugin.cc:572
const string value("\alue\)
~Discrete_intervals_list()
Definition: discrete_interval.h:168
void copy_shallow(const Discrete_intervals_list *other)
Definition: discrete_interval.h:127
void operator=(Discrete_intervals_list &)
List of Discrete_interval objects.
Definition: discrete_interval.h:86
uint elements
number of elements
Definition: discrete_interval.h:114
ulonglong values() const
Definition: discrete_interval.h:64
Definition: discrete_interval.h:40
ulonglong minimum() const
Definition: discrete_interval.h:203
ulonglong maximum() const
Definition: discrete_interval.h:65
void empty()
Definition: discrete_interval.h:143
ulonglong maximum() const
Definition: discrete_interval.h:204