1 #ifndef DISCRETE_INTERVAL_INCLUDED 2 #define DISCRETE_INTERVAL_INCLUDED 3 4 /* Copyright (c) 2000, 2015, 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 Foundation, 24 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */ 25 26 /* 27 Such interval is "discrete": it is the set of 28 { auto_inc_interval_min + k * increment, 29 0 <= k <= (auto_inc_interval_values-1) } 30 Where "increment" is maintained separately by the user of this class (and is 31 currently only thd->variables.auto_increment_increment). 32 It mustn't derive from Sql_alloc, because SET INSERT_ID needs to 33 allocate memory which must stay allocated for use by the next statement. 34 */ 35 class Discrete_interval { 36 private: 37 ulonglong interval_min; 38 ulonglong interval_values; 39 ulonglong interval_max; // excluded bound. Redundant. 40 public: 41 Discrete_interval *next; // used when linked into Discrete_intervals_list 42 43 /// Determine if the given value is within the interval in_range(const ulonglong value)44 bool in_range(const ulonglong value) const 45 { 46 return ((value >= interval_min) && (value < interval_max)); 47 } 48 replace(ulonglong start,ulonglong val,ulonglong incr)49 void replace(ulonglong start, ulonglong val, ulonglong incr) 50 { 51 interval_min= start; 52 interval_values= val; 53 interval_max= (val == ULLONG_MAX) ? val : start + val * incr; 54 } Discrete_interval(ulonglong start,ulonglong val,ulonglong incr)55 Discrete_interval(ulonglong start, ulonglong val, ulonglong incr) : 56 next(NULL) { replace(start, val, incr); }; Discrete_interval()57 Discrete_interval() : next(NULL) { replace(0, 0, 0); }; minimum()58 ulonglong minimum() const { return interval_min; }; values()59 ulonglong values() const { return interval_values; }; maximum()60 ulonglong maximum() const { return interval_max; }; 61 /* 62 If appending [3,5] to [1,2], we merge both in [1,5] (they should have the 63 same increment for that, user of the class has to ensure that). That is 64 just a space optimization. Returns 0 if merge succeeded. 65 */ merge_if_contiguous(ulonglong start,ulonglong val,ulonglong incr)66 bool merge_if_contiguous(ulonglong start, ulonglong val, ulonglong incr) 67 { 68 if (interval_max == start) 69 { 70 if (val == ULLONG_MAX) 71 { 72 interval_values= interval_max= val; 73 } 74 else 75 { 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 86 class Discrete_intervals_list { 87 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 */ 105 Discrete_interval first_interval; 106 Discrete_interval *head; 107 Discrete_interval *tail; 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 */ 114 Discrete_interval *current; 115 uint elements; ///< number of elements 116 void operator=(Discrete_intervals_list &); // prevent use of this append(Discrete_interval * new_interval)117 bool append(Discrete_interval *new_interval) 118 { 119 if (unlikely(new_interval == NULL)) 120 return true; 121 DBUG_PRINT("info",("adding new auto_increment interval")); 122 if (head == NULL) 123 head= current= new_interval; 124 else 125 tail->next= new_interval; 126 tail= new_interval; 127 elements++; 128 return false; 129 } copy_shallow(const Discrete_intervals_list * other)130 void copy_shallow(const Discrete_intervals_list *other) 131 { 132 const Discrete_interval *o_first_interval= &other->first_interval; 133 first_interval= other->first_interval; 134 head= other->head == o_first_interval ? &first_interval : other->head; 135 tail= other->tail == o_first_interval ? &first_interval : other->tail; 136 current= 137 other->current == o_first_interval ? &first_interval : other->current; 138 elements= other->elements; 139 } Discrete_intervals_list(const Discrete_intervals_list & other)140 Discrete_intervals_list(const Discrete_intervals_list &other) 141 { copy_shallow(&other); } 142 143 public: Discrete_intervals_list()144 Discrete_intervals_list() 145 : head(NULL), tail(NULL), current(NULL), elements(0) {} empty()146 void empty() 147 { 148 if (head) 149 { 150 // first element, not on heap, should not be delete-d; start with next: 151 for (Discrete_interval *i= head->next; i;) 152 { 153 #ifdef DISCRETE_INTERVAL_LIST_HAS_MAX_ONE_ELEMENT 154 DBUG_ASSERT(0); 155 #endif 156 Discrete_interval *next= i->next; 157 delete i; 158 i= next; 159 } 160 } 161 head= tail= current= NULL; 162 elements= 0; 163 } swap(Discrete_intervals_list * other)164 void swap(Discrete_intervals_list *other) 165 { 166 const Discrete_intervals_list tmp(*other); 167 other->copy_shallow(this); 168 copy_shallow(&tmp); 169 } get_next()170 const Discrete_interval *get_next() 171 { 172 const Discrete_interval *tmp= current; 173 if (current != NULL) 174 current= current->next; 175 return tmp; 176 } ~Discrete_intervals_list()177 ~Discrete_intervals_list() { empty(); }; 178 /** 179 Appends an interval to the list. 180 181 @param start start of interval 182 @val how many values it contains 183 @param incr what increment between each value 184 @retval true error 185 @retval false success 186 */ append(ulonglong start,ulonglong val,ulonglong incr)187 bool append(ulonglong start, ulonglong val, ulonglong incr) 188 { 189 // If there are no intervals, add one. 190 if (head == NULL) 191 { 192 first_interval.replace(start, val, incr); 193 return append(&first_interval); 194 } 195 // If this interval can be merged with previous, do that. 196 if (tail->merge_if_contiguous(start, val, incr) == 0) 197 return false; 198 // If this interval cannot be merged, append it. 199 #ifdef DISCRETE_INTERVAL_LIST_HAS_MAX_ONE_ELEMENT 200 /* 201 We cannot create yet another interval as we already contain one. This 202 situation can happen. Assume innodb_autoinc_lock_mode>=1 and 203 CREATE TABLE T(A INT AUTO_INCREMENT PRIMARY KEY) ENGINE=INNODB; 204 INSERT INTO T VALUES (NULL),(NULL),(1025),(NULL); 205 Then InnoDB will reserve [1,4] (because of 4 rows) then 206 [1026,1026]. Only the first interval is important for 207 statement-based binary logging as it tells the starting point. So we 208 ignore the second interval: 209 */ 210 return false; 211 #else 212 return append(new Discrete_interval(start, val, incr)); 213 #endif 214 } minimum()215 ulonglong minimum() const { return (head ? head->minimum() : 0); }; maximum()216 ulonglong maximum() const { return (head ? tail->maximum() : 0); }; nb_elements()217 uint nb_elements() const { return elements; } 218 }; 219 220 #endif /* DISCRETE_INTERVAL_INCLUDED */ 221