MySQL  8.0.18
Source Code Documentation
sql_list.h
Go to the documentation of this file.
1 #ifndef INCLUDES_MYSQL_SQL_LIST_H
2 #define INCLUDES_MYSQL_SQL_LIST_H
3 /* Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights reserved.
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License, version 2.0,
7  as published by the Free Software Foundation.
8 
9  This program is also distributed with certain software (including
10  but not limited to OpenSSL) that is licensed under separate terms,
11  as designated in a particular file or component or in included license
12  documentation. The authors of MySQL hereby grant you an additional
13  permission to link the program and your derivative works with the
14  separately licensed software that they have included with MySQL.
15 
16  This program is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  GNU General Public License, version 2.0, for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with this program; if not, write to the Free Software
23  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
24 
25 #include <stddef.h>
26 #include <sys/types.h>
27 #include <algorithm>
28 #include <iterator>
29 #include <type_traits>
30 
31 #include "my_alloc.h"
32 #include "my_compiler.h"
33 #include "my_dbug.h"
34 #include "my_sharedlib.h"
35 #include "sql/thr_malloc.h"
36 
37 /**
38  Simple intrusive linked list.
39 
40  @remark Similar in nature to base_list, but intrusive. It keeps a
41  a pointer to the first element in the list and a indirect
42  reference to the last element.
43 */
44 template <typename T>
45 class SQL_I_List {
46  public:
48  /** The first element in the list. */
49  T *first;
50  /** A reference to the next element in the list. */
51  T **next;
52 
53  SQL_I_List() { empty(); }
54 
55  SQL_I_List(const SQL_I_List &tmp)
56  : elements(tmp.elements),
57  first(tmp.first),
58  next(elements ? tmp.next : &first) {}
59 
60  SQL_I_List(SQL_I_List &&) = default;
61 
62  inline void empty() {
63  elements = 0;
64  first = NULL;
65  next = &first;
66  }
67 
68  inline void link_in_list(T *element, T **next_ptr) {
69  elements++;
70  (*next) = element;
71  next = next_ptr;
72  *next = NULL;
73  }
74 
75  inline void save_and_clear(SQL_I_List<T> *save) {
76  *save = *this;
77  empty();
78  }
79 
80  inline void push_front(SQL_I_List<T> *save) {
81  /* link current list last */
82  *save->next = first;
83  first = save->first;
84  elements += save->elements;
85  }
86 
87  inline void push_back(SQL_I_List<T> *save) {
88  if (save->first) {
89  *next = save->first;
90  next = save->next;
91  elements += save->elements;
92  }
93  }
94 
95  inline uint size() const { return elements; }
96 
97  SQL_I_List &operator=(SQL_I_List &) = default;
98  SQL_I_List &operator=(SQL_I_List &&) = default;
99 };
100 
101 /*
102  Basic single linked list
103  Used for item and item_buffs.
104  All list ends with a pointer to the 'end_of_list' element, which
105  data pointer is a null pointer and the next pointer points to itself.
106  This makes it very fast to traverse lists as we don't have to
107  test for a specialend condition for list that can't contain a null
108  pointer.
109 */
110 
111 /**
112  list_node - a node of a single-linked list.
113  @note We never call a destructor for instances of this class.
114 */
115 
116 struct list_node {
118  void *info;
119  list_node(void *info_par, list_node *next_par)
120  : next(next_par), info(info_par) {}
121  list_node() /* For end_of_list */
122  {
123  info = 0;
124  next = this;
125  }
126 };
127 
129 
130 class base_list {
131  protected:
133 
134  public:
136 
137  bool operator==(const base_list &rhs) const {
138  return elements == rhs.elements && first == rhs.first && last == rhs.last;
139  }
140 
141  inline void empty() {
142  elements = 0;
143  first = &end_of_list;
144  last = &first;
145  }
146  inline base_list() { empty(); }
147  /**
148  This is a shallow copy constructor that implicitly passes the ownership
149  from the source list to the new instance. The old instance is not
150  updated, so both objects end up sharing the same nodes. If one of
151  the instances then adds or removes a node, the other becomes out of
152  sync ('last' pointer), while still operational. Some old code uses and
153  relies on this behaviour. This logic is quite tricky: please do not use
154  it in any new code.
155  */
156  base_list(const base_list &tmp)
157  : first(tmp.first),
158  last(tmp.elements ? tmp.last : &first),
159  elements(tmp.elements) {}
161  elements = tmp.elements;
162  first = tmp.first;
163  last = elements ? tmp.last : &first;
164  return *this;
165  }
166  /**
167  Construct a deep copy of the argument in memory root mem_root.
168  The elements themselves are copied by pointer.
169  */
170  base_list(const base_list &rhs, MEM_ROOT *mem_root);
171  inline bool push_back(void *info) {
172  if (((*last) = new (*THR_MALLOC) list_node(info, &end_of_list))) {
173  last = &(*last)->next;
174  elements++;
175  return 0;
176  }
177  return 1;
178  }
179  inline bool push_back(void *info, MEM_ROOT *mem_root) {
180  if (((*last) = new (mem_root) list_node(info, &end_of_list))) {
181  last = &(*last)->next;
182  elements++;
183  return 0;
184  }
185  return 1;
186  }
187  inline bool push_front(void *info) {
188  list_node *node = new (*THR_MALLOC) list_node(info, first);
189  if (node) {
190  if (last == &first) last = &node->next;
191  first = node;
192  elements++;
193  return 0;
194  }
195  return 1;
196  }
197  inline bool push_front(void *info, MEM_ROOT *mem_root) {
198  list_node *node = new (mem_root) list_node(info, first);
199  if (node) {
200  if (last == &first) last = &node->next;
201  first = node;
202  elements++;
203  return false;
204  }
205  return true;
206  }
207 
208  void remove(list_node **prev) {
209  list_node *node = (*prev)->next;
210  if (!--elements)
211  last = &first;
212  else if (last == &(*prev)->next)
213  last = prev;
214  destroy(*prev);
215  *prev = node;
216  }
217  inline void concat(base_list *list) {
218  if (!list->is_empty()) {
219  *last = list->first;
220  last = list->last;
221  elements += list->elements;
222  }
223  }
224  inline void *pop(void) {
225  if (first == &end_of_list) return 0;
226  list_node *tmp = first;
227  first = first->next;
228  if (!--elements) last = &first;
229  return tmp->info;
230  }
231  inline void disjoin(base_list *list) {
232  list_node **prev = &first;
233  list_node *node = first;
234  list_node *list_first = list->first;
235  elements = 0;
236  while (node && node != list_first) {
237  prev = &node->next;
238  node = node->next;
239  elements++;
240  }
241  *prev = *last;
242  last = prev;
243  }
244  inline void prepend(base_list *list) {
245  if (!list->is_empty()) {
246  *list->last = first;
247  if (is_empty()) last = list->last;
248  first = list->first;
249  elements += list->elements;
250  }
251  }
252  /**
253  Swap two lists.
254  */
255  inline void swap(base_list &rhs) {
256  std::swap(first, rhs.first);
257  std::swap(last, rhs.last);
259  }
260  inline list_node *last_node() { return *last; }
261  inline list_node *first_node() { return first; }
262  inline void *head() { return first->info; }
263  inline const void *head() const { return first->info; }
264  inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
265  inline bool is_empty() const { return first == &end_of_list; }
266  inline list_node *last_ref() { return &end_of_list; }
267  inline uint size() const { return elements; }
268  friend class base_list_iterator;
269  friend class error_list;
270  friend class error_list_iterator;
271 
272 #ifdef LIST_EXTRA_DEBUG
273  /*
274  Check list invariants and print results into trace. Invariants are:
275  - (*last) points to end_of_list
276  - There are no NULLs in the list.
277  - base_list::elements is the number of elements in the list.
278 
279  SYNOPSIS
280  check_list()
281  name Name to print to trace file
282 
283  RETURN
284  1 The list is Ok.
285  0 List invariants are not met.
286  */
287 
288  bool check_list(const char *name) {
289  base_list *list = this;
290  list_node *node = first;
291  uint cnt = 0;
292 
293  while (node->next != &end_of_list) {
294  if (!node->info) {
295  DBUG_PRINT("list_invariants",
296  ("%s: error: NULL element in the list", name));
297  return false;
298  }
299  node = node->next;
300  cnt++;
301  }
302  if (last != &(node->next)) {
303  DBUG_PRINT("list_invariants", ("%s: error: wrong last pointer", name));
304  return false;
305  }
306  if (cnt + 1 != elements) {
307  DBUG_PRINT("list_invariants", ("%s: error: wrong element count", name));
308  return false;
309  }
310  DBUG_PRINT("list_invariants", ("%s: list is ok", name));
311  return true;
312  }
313 #endif // LIST_EXTRA_DEBUG
314 
315  protected:
316  void after(void *info, list_node *node) {
317  list_node *new_node = new (*THR_MALLOC) list_node(info, node->next);
318  node->next = new_node;
319  elements++;
320  if (last == &(node->next)) last = &new_node->next;
321  }
322  bool after(void *info, list_node *node, MEM_ROOT *mem_root) {
323  list_node *new_node = new (mem_root) list_node(info, node->next);
324  if (!new_node) return true; // OOM
325 
326  node->next = new_node;
327  elements++;
328  if (last == &(node->next)) last = &new_node->next;
329 
330  return false;
331  }
332 };
333 
335  protected:
338  void sublist(base_list &ls, uint elm) {
339  ls.first = *el;
340  ls.last = list->last;
341  ls.elements = elm;
342  }
343 
344  public:
345  base_list_iterator() : list(0), el(0), prev(0), current(0) {}
346 
347  base_list_iterator(base_list &list_par) { init(list_par); }
348 
349  inline void init(base_list &list_par) {
350  list = &list_par;
351  el = &list_par.first;
352  prev = 0;
353  current = 0;
354  }
355 
356  inline void *next(void) {
357  prev = el;
358  current = *el;
359  el = &current->next;
360  return current->info;
361  }
362  inline void *next_fast(void) {
363  list_node *tmp;
364  tmp = *el;
365  el = &tmp->next;
366  return tmp->info;
367  }
368  inline void rewind(void) { el = &list->first; }
369  inline void *replace(void *element) { // Return old element
370  void *tmp = current->info;
371  DBUG_ASSERT(current->info != 0);
372  current->info = element;
373  return tmp;
374  }
375  void *replace(base_list &new_list) {
376  void *ret_value = current->info;
377  if (!new_list.is_empty()) {
378  *new_list.last = current->next;
379  current->info = new_list.first->info;
380  current->next = new_list.first->next;
381  if ((list->last == &current->next) && (new_list.elements > 1))
382  list->last = new_list.last;
383  list->elements += new_list.elements - 1;
384  }
385  return ret_value; // return old element
386  }
387  inline void remove(void) // Remove current
388  {
389  list->remove(prev);
390  el = prev;
391  current = 0; // Safeguard
392  }
393  void after(void *element) // Insert element after current
394  {
395  list->after(element, current);
396  current = current->next;
397  el = &current->next;
398  }
399  bool after(void *a, MEM_ROOT *mem_root) {
400  if (list->after(a, current, mem_root)) return true;
401 
402  current = current->next;
403  el = &current->next;
404  return false;
405  }
406  inline void **ref(void) // Get reference pointer
407  {
408  return &current->info;
409  }
410  inline bool is_last(void) { return el == list->last; }
411  inline bool is_before_first() const { return current == NULL; }
412  bool prepend(void *a, MEM_ROOT *mem_root) {
413  if (list->push_front(a, mem_root)) return true;
414 
415  el = &list->first;
416  prev = el;
417  el = &(*el)->next;
418 
419  return false;
420  }
421  friend class error_list_iterator;
422 };
423 
424 template <class T>
426 
427 template <class T>
428 class List : public base_list {
429  public:
430  List() : base_list() {}
431  inline List(const List<T> &tmp) : base_list(tmp) {}
432  List &operator=(const List &tmp) {
433  return static_cast<List &>(base_list::operator=(tmp));
434  }
435  inline List(const List<T> &tmp, MEM_ROOT *mem_root)
436  : base_list(tmp, mem_root) {}
437  /*
438  Typecasting to (void *) it's necessary if we want to declare List<T> with
439  constant T parameter (like List<const char>), since the untyped storage
440  is "void *", and assignment of const pointer to "void *" is a syntax error.
441  */
442  inline bool push_back(T *a) {
443  return base_list::push_back(const_cast<void *>(((const void *)a)));
444  }
445  inline bool push_back(T *a, MEM_ROOT *mem_root) {
446  return base_list::push_back(const_cast<void *>((const void *)a), mem_root);
447  }
448  inline bool push_front(T *a) {
449  return base_list::push_front(const_cast<void *>((const void *)a));
450  }
451  inline bool push_front(T *a, MEM_ROOT *mem_root) {
452  return base_list::push_front(const_cast<void *>((const void *)a), mem_root);
453  }
454  inline T *head() { return static_cast<T *>(base_list::head()); }
455  inline const T *head() const {
456  return static_cast<const T *>(base_list::head());
457  }
458  inline T **head_ref() { return (T **)base_list::head_ref(); }
459  inline T *pop() { return (T *)base_list::pop(); }
463  void delete_elements(void) {
464  list_node *element, *next;
465  for (element = first; element != &end_of_list; element = next) {
466  next = element->next;
467  delete (T *)element->info;
468  }
469  empty();
470  }
471 
472  void destroy_elements(void) {
473  list_node *element, *next;
474  for (element = first; element != &end_of_list; element = next) {
475  next = element->next;
476  destroy((T *)element->info);
477  }
478  empty();
479  }
480 
481  T *operator[](uint index) const {
483  list_node *current = first;
484  for (uint i = 0; i < index; ++i) current = current->next;
485  return static_cast<T *>(current->info);
486  }
487 
488  void replace(uint index, T *new_value) {
490  list_node *current = first;
491  for (uint i = 0; i < index; ++i) current = current->next;
492  current->info = new_value;
493  }
494 
495  bool swap_elts(uint index1, uint index2) {
496  if (index1 == index2) return false;
497 
498  if (index1 >= elements || index2 >= elements) return true; // error
499 
500  if (index2 < index1) std::swap(index1, index2);
501 
502  list_node *current1 = first;
503  for (uint i = 0; i < index1; ++i) current1 = current1->next;
504 
505  list_node *current2 = current1;
506  for (uint i = 0; i < index2 - index1; ++i) current2 = current2->next;
507 
508  std::swap(current1->info, current2->info);
509 
510  return false;
511  }
512 
513  /**
514  @brief
515  Sort the list
516 
517  @param cmp node comparison function
518 
519  @details
520  The function sorts list nodes by an exchange sort algorithm.
521  The order of list nodes isn't changed, values of info fields are
522  swapped instead. Due to this, list iterators that are initialized before
523  sort could be safely used after sort, i.e they wouldn't cause a crash.
524  As this isn't an effective algorithm the list to be sorted is supposed to
525  be short.
526  */
527  template <typename Node_cmp_func>
528  void sort(Node_cmp_func cmp) {
529  if (elements < 2) return;
530  for (list_node *n1 = first; n1 && n1 != &end_of_list; n1 = n1->next) {
531  for (list_node *n2 = n1->next; n2 && n2 != &end_of_list; n2 = n2->next) {
532  if (cmp(static_cast<T *>(n1->info), static_cast<T *>(n2->info)) > 0) {
533  void *tmp = n1->info;
534  n1->info = n2->info;
535  n2->info = tmp;
536  }
537  }
538  }
539  }
540 
541  // For C++11 range-based for loops.
543  iterator begin() { return iterator(first); }
545  // If the list overlaps another list, last isn't actually
546  // the last element, and if so, we'd give a different result from
547  // List_iterator_fast.
548  DBUG_ASSERT((*last)->next == &end_of_list);
549 
550  return iterator(*last);
551  }
552 
555  const_iterator end() const {
556  DBUG_ASSERT((*last)->next == &end_of_list);
557  return const_iterator(*last);
558  }
561  DBUG_ASSERT((*last)->next == &end_of_list);
562  return const_iterator(*last);
563  }
564 };
565 
566 template <class T>
567 class List_iterator : public base_list_iterator {
568  public:
571  inline void init(List<T> &a) { base_list_iterator::init(a); }
572  inline T *operator++(int) { return (T *)base_list_iterator::next(); }
573  inline T *replace(T *a) { return (T *)base_list_iterator::replace(a); }
574  inline T *replace(List<T> &a) { return (T *)base_list_iterator::replace(a); }
575  inline void rewind(void) { base_list_iterator::rewind(); }
576  inline void remove() { base_list_iterator::remove(); }
577  inline void after(T *a) { base_list_iterator::after(a); }
578  inline bool after(T *a, MEM_ROOT *mem_root) {
580  }
581  inline T **ref(void) { return (T **)base_list_iterator::ref(); }
582 };
583 
584 template <class T>
586  protected:
587  inline T *replace(T *) { return (T *)0; }
588  inline T *replace(List<T> &) { return (T *)0; }
589  inline void remove(void) {}
590  inline void after(T *) {}
591  inline T **ref(void) { return (T **)0; }
592 
593  public:
596  inline void init(List<T> &a) { base_list_iterator::init(a); }
597  inline T *operator++(int) { return (T *)base_list_iterator::next_fast(); }
598  inline void rewind(void) { base_list_iterator::rewind(); }
599  void sublist(List<T> &list_arg, uint el_arg) {
600  base_list_iterator::sublist(list_arg, el_arg);
601  }
602 };
603 
604 /*
605  Like List_iterator<T>, but with an STL-compatible interface
606  (ForwardIterator), so that you can use it in range-based for loops.
607  Prefer this to List_iterator<T> wherever possible, but also prefer
608  std::vector<T> or std::list<T> to List<T> wherever possible.
609  */
610 template <class T>
611 class List_STL_Iterator {
612  public:
613  explicit List_STL_Iterator(list_node *node) : m_current(node) {}
614 
615  // Iterator (required for InputIterator).
616  T &operator*() const { return *static_cast<T *>(m_current->info); }
617 
620  return *this;
621  }
622 
623  using difference_type = ptrdiff_t;
624  using value_type = T; // NOTE: std::remove_cv_t<T> from C++20.
625  using pointer = T *;
626  using reference = T &;
627  using iterator_category = std::forward_iterator_tag;
628 
629  // EqualityComparable (required for InputIterator).
630  bool operator==(const List_STL_Iterator &other) const {
631  return m_current == other.m_current;
632  }
633 
634  // InputIterator (required for ForwardIterator).
635  bool operator!=(const List_STL_Iterator &other) const {
636  return !(*this == other);
637  }
638 
639  T *operator->() const { return static_cast<T *>(m_current->info); }
640 
641  // DefaultConstructible (required for ForwardIterator).
643 
644  // ForwardIterator.
646  List_STL_Iterator copy = *this;
648  return copy;
649  }
650 
651  private:
653 };
654 
655 template <typename T>
657 template <typename T>
659 
660 /*
661  A simple intrusive list.
662 
663  NOTE: this inherently unsafe, since we rely on <T> to have
664  the same layout as ilink<T> (see base_ilist::sentinel).
665  Please consider using a different strategy for linking objects.
666 */
667 
668 template <typename T>
669 class ilink {
670  T **prev, *next;
671 
672  public:
673  ilink() : prev(NULL), next(NULL) {}
674 
675  void unlink() {
676  /* Extra tests because element doesn't have to be linked */
677  if (prev) *prev = next;
678  if (next) next->prev = prev;
679  prev = NULL;
680  next = NULL;
681  }
682 
683  friend class base_ilist<T>;
684  friend class base_ilist_iterator<T>;
685 };
686 
687 /* Needed to be able to have an I_List of char* strings in mysqld.cc. */
688 
689 class i_string : public ilink<i_string> {
690  public:
691  const char *ptr;
692  i_string() : ptr(0) {}
693  i_string(const char *s) : ptr(s) {}
694 };
695 
696 /* needed for linked list of two strings for replicate-rewrite-db */
697 class i_string_pair : public ilink<i_string_pair> {
698  public:
699  const char *key;
700  const char *val;
701  i_string_pair() : key(0), val(0) {}
702  i_string_pair(const char *key_arg, const char *val_arg)
703  : key(key_arg), val(val_arg) {}
704 };
705 
706 template <class T>
708 
709 template <typename T>
710 class base_ilist {
711  T *first;
713 
714  static_assert(!std::is_polymorphic<T>::value,
715  "Do not use this for classes with virtual members");
716 
717  public:
718  // The sentinel is not a T, but at least it is a POD
720  first = static_cast<T *>(&sentinel);
721  sentinel.prev = &first;
722  }
723  base_ilist() { empty(); }
724 
725  // The sentinel is not a T, but at least it is a POD
726  bool is_empty() const SUPPRESS_UBSAN {
727  return first == static_cast<const T *>(&sentinel);
728  }
729 
730  /// Pushes new element in front of list.
731  void push_front(T *a) {
732  first->prev = &a->next;
733  a->next = first;
734  a->prev = &first;
735  first = a;
736  }
737 
738  /// Pushes new element to the end of the list, i.e. in front of the sentinel.
739  void push_back(T *a) {
740  *sentinel.prev = a;
741  a->next = static_cast<T *>(&sentinel);
742  a->prev = sentinel.prev;
743  sentinel.prev = &a->next;
744  }
745 
746  // Unlink first element, and return it.
747  T *get() {
748  if (is_empty()) return NULL;
749  T *first_link = first;
750  first_link->unlink();
751  return first_link;
752  }
753 
754  T *head() { return is_empty() ? NULL : first; }
755 
756  /**
757  Moves list elements to new owner, and empties current owner (i.e. this).
758 
759  @param[in,out] new_owner The new owner of the list elements.
760  Should be empty in input.
761  */
762 
763  void move_elements_to(base_ilist *new_owner) {
764  DBUG_ASSERT(new_owner->is_empty());
765  new_owner->first = first;
766  new_owner->sentinel = sentinel;
767  empty();
768  }
769 
770  friend class base_ilist_iterator<T>;
771 
772  private:
773  /*
774  We don't want to allow copying of this class, as that would give us
775  two list heads containing the same elements.
776  So we declare, but don't define copy CTOR and assignment operator.
777  */
778  base_ilist(const base_ilist &);
779  void operator=(const base_ilist &);
780 };
781 
782 template <typename T>
783 class base_ilist_iterator {
785  T **el, *current;
786 
787  public:
789  : list(&list_par), el(&list_par.first), current(NULL) {}
790 
791  // The sentinel is not a T, but at least it is a POD
792  T *next(void) SUPPRESS_UBSAN {
793  /* This is coded to allow push_back() while iterating */
794  current = *el;
795  if (current == static_cast<T *>(&list->sentinel)) return NULL;
796  el = &current->next;
797  return current;
798  }
799 };
800 
801 template <class T>
802 class I_List : private base_ilist<T> {
803  public:
804  using base_ilist<T>::empty;
806  using base_ilist<T>::get;
809  using base_ilist<T>::head;
810  void move_elements_to(I_List<T> *new_owner) {
812  }
813  friend class I_List_iterator<T>;
814 };
815 
816 template <class T>
817 class I_List_iterator : public base_ilist_iterator<T> {
818  public:
820  inline T *operator++(int) { return base_ilist_iterator<T>::next(); }
821 };
822 
825 
826 template <class T>
827 List<T> *List_merge(T *head, List<T> *tail) {
828  tail->push_front(head);
829  return tail;
830 }
831 
832 #endif // INCLUDES_MYSQL_SQL_LIST_H
uint size() const
Definition: sql_list.h:267
Definition: sql_list.h:656
void concat(List< T > *list)
Definition: sql_list.h:460
bool push_back(T *a, MEM_ROOT *mem_root)
Definition: sql_list.h:445
static int cmp(Bigint *a, Bigint *b)
Definition: dtoa.cc:1074
T value_type
Definition: sql_list.h:624
friend class error_list
Definition: sql_list.h:269
ilink< T > sentinel
Definition: sql_list.h:712
void after(T *)
Definition: sql_list.h:590
list_node * last_ref()
Definition: sql_list.h:266
bool operator==(const base_list &rhs) const
Definition: sql_list.h:137
bool after(void *info, list_node *node, MEM_ROOT *mem_root)
Definition: sql_list.h:322
void after(T *a)
Definition: sql_list.h:577
const_iterator end() const
Definition: sql_list.h:555
T ** ref(void)
Definition: sql_list.h:581
std::forward_iterator_tag iterator_category
Definition: sql_list.h:627
void move_elements_to(base_ilist *new_owner)
Moves list elements to new owner, and empties current owner (i.e.
Definition: sql_list.h:763
void sublist(base_list &ls, uint elm)
Definition: sql_list.h:338
void after(void *info, list_node *node)
Definition: sql_list.h:316
#define SUPPRESS_UBSAN
Definition: my_compiler.h:130
const string name("\ame\)
T ** next
A reference to the next element in the list.
Definition: sql_list.h:51
bool swap_elts(uint index1, uint index2)
Definition: sql_list.h:495
void ** head_ref()
Definition: sql_list.h:264
uint size() const
Definition: sql_list.h:95
bool is_empty() const
Definition: sql_list.h:265
for(i=0;i< 3;i++)
Definition: do_ctype.cc:54
T * first
Definition: sql_list.h:711
void rewind(void)
Definition: sql_list.h:598
void * next(void)
Definition: sql_list.h:356
T * replace(T *)
Definition: sql_list.h:587
#define MYSQL_PLUGIN_IMPORT
Definition: my_sharedlib.h:70
void push_back(T *a)
Pushes new element to the end of the list, i.e. in front of the sentinel.
Definition: sql_list.h:739
T * replace(List< T > &)
Definition: sql_list.h:588
T * operator++(int)
Definition: sql_list.h:597
bool prepend(void *a, MEM_ROOT *mem_root)
Definition: sql_list.h:412
void destroy_elements(void)
Definition: sql_list.h:472
List< T > * List_merge(T *head, List< T > *tail)
Definition: sql_list.h:827
bool push_front(void *info)
Definition: sql_list.h:187
void save_and_clear(SQL_I_List< T > *save)
Definition: sql_list.h:75
void swap(base_list &rhs)
Swap two lists.
Definition: sql_list.h:255
base_list_iterator()
Definition: sql_list.h:345
T ** head_ref()
Definition: sql_list.h:458
const_iterator cend() const
Definition: sql_list.h:560
bool is_last(void)
Definition: sql_list.h:410
List_STL_Iterator & operator++()
Definition: sql_list.h:618
void ** ref(void)
Definition: sql_list.h:406
bool push_back(void *info, MEM_ROOT *mem_root)
Definition: sql_list.h:179
void push_front(SQL_I_List< T > *save)
Definition: sql_list.h:80
Simple intrusive linked list.
Definition: item.h:81
bool push_back(void *info)
Definition: sql_list.h:171
list_node * first
Definition: sql_list.h:132
void push_back(SQL_I_List< T > *save)
Definition: sql_list.h:87
Definition: sql_list.h:425
bool push_front(void *info, MEM_ROOT *mem_root)
Definition: sql_list.h:197
class udf_list * list
base_ilist()
Definition: sql_list.h:723
void rewind(void)
Definition: sql_list.h:368
List_STL_Iterator operator++(int)
Definition: sql_list.h:645
void concat(base_list *list)
Definition: sql_list.h:217
Definition: sql_list.h:334
bool is_before_first() const
Definition: sql_list.h:411
bool push_front(T *a, MEM_ROOT *mem_root)
Definition: sql_list.h:451
SQL_I_List(const SQL_I_List &tmp)
Definition: sql_list.h:55
List & operator=(const List &tmp)
Definition: sql_list.h:432
void * pop(void)
Definition: sql_list.h:224
T ** ref(void)
Definition: sql_list.h:591
iterator begin()
Definition: sql_list.h:543
base_ilist_iterator(base_ilist< T > &list_par)
Definition: sql_list.h:788
Functions related to handling of plugins and other dynamically loaded libraries.
void * replace(void *element)
Definition: sql_list.h:369
void link_in_list(T *element, T **next_ptr)
Definition: sql_list.h:68
void empty() SUPPRESS_UBSAN
Definition: sql_list.h:719
void init(base_list &list_par)
Definition: sql_list.h:349
list_node * first_node()
Definition: sql_list.h:261
void disjoin(List< T > *list)
Definition: sql_list.h:461
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:179
T * head()
Definition: sql_list.h:754
list_node * next
Definition: sql_list.h:117
list_node * current
Definition: sql_list.h:337
void remove(void)
Definition: sql_list.h:387
void empty()
Definition: sql_list.h:141
#define DBUG_ASSERT(A)
Definition: my_dbug.h:197
SQL_I_List & operator=(SQL_I_List &)=default
List_STL_Iterator< const T > const_iterator
Definition: sql_list.h:553
char * index(const char *, int c)
Definition: mysql.cc:2862
MYSQL_PLUGIN_IMPORT list_node end_of_list
Definition: sql_list.cc:28
Definition: sql_list.h:707
void operator=(const base_ilist &)
I_List_iterator(I_List< T > &a)
Definition: sql_list.h:819
const char * val
Definition: sql_list.h:700
T * operator++(int)
Definition: sql_list.h:820
List_iterator()
Definition: sql_list.h:570
friend class error_list_iterator
Definition: sql_list.h:421
Definition: aggregate_check.h:523
T & operator*() const
Definition: sql_list.h:616
base_list()
Definition: sql_list.h:146
i_string()
Definition: sql_list.h:692
list_node()
Definition: sql_list.h:121
const void * head() const
Definition: sql_list.h:263
void * head()
Definition: sql_list.h:262
List_iterator(List< T > &a)
Definition: sql_list.h:569
const char * ptr
Definition: sql_list.h:691
Header for compiler-dependent features.
Definition: sql_list.h:697
void remove(list_node **prev)
Definition: sql_list.h:208
void push_front(T *a)
Pushes new element in front of list.
Definition: sql_list.h:731
unsigned int uint
Definition: uca-dump.cc:29
List_STL_Iterator(list_node *node)
Definition: sql_list.h:613
SQL_I_List()
Definition: sql_list.h:53
void sort(Node_cmp_func cmp)
Sort the list.
Definition: sql_list.h:528
list_node * m_current
Definition: sql_list.h:652
bool operator!=(const List_STL_Iterator &other) const
Definition: sql_list.h:635
list_node(void *info_par, list_node *next_par)
Definition: sql_list.h:119
list_node * last_node()
Definition: sql_list.h:260
List(const List< T > &tmp)
Definition: sql_list.h:431
base_ilist< T > * list
Definition: sql_list.h:784
uint elements
Definition: sql_list.h:47
Definition: sql_list.h:658
T * next(void) SUPPRESS_UBSAN
Definition: sql_list.h:792
list_node - a node of a single-linked list.
Definition: sql_list.h:116
bool operator==(const List_STL_Iterator &other) const
Definition: sql_list.h:630
static MEM_ROOT mem_root
Definition: client_plugin.cc:107
List_STL_Iterator< T > iterator
Definition: sql_list.h:542
void * info
Definition: sql_list.h:118
bool is_empty() const SUPPRESS_UBSAN
Definition: sql_list.h:726
T & reference
Definition: sql_list.h:626
List_STL_Iterator()
Definition: sql_list.h:642
T * pop()
Definition: sql_list.h:459
T * replace(T *a)
Definition: sql_list.h:573
void disjoin(base_list *list)
Definition: sql_list.h:231
T * current
Definition: sql_list.h:785
void init(List< T > &a)
Definition: sql_list.h:571
Definition: sql_list.h:130
void free_list(I_List< i_string_pair > *list)
Definition: sql_list.cc:30
bool after(T *a, MEM_ROOT *mem_root)
Definition: sql_list.h:578
thread_local MEM_ROOT ** THR_MALLOC
Definition: mysqld.cc:1331
base_list * list
Definition: sql_list.h:336
uint elements
Definition: sql_list.h:135
const char * key
Definition: sql_list.h:699
i_string_pair()
Definition: sql_list.h:701
void move_elements_to(I_List< T > *new_owner)
Definition: sql_list.h:810
Definition: sql_list.h:585
void init(List< T > &a)
Definition: sql_list.h:596
T * operator[](uint index) const
Definition: sql_list.h:481
friend class error_list_iterator
Definition: sql_list.h:270
void prepend(List< T > *list)
Definition: sql_list.h:462
void destroy(T *ptr)
Definition: my_alloc.h:381
Definition: protocol_classic.h:45
void rewind(void)
Definition: sql_list.h:575
T * first
The first element in the list.
Definition: sql_list.h:49
#define NULL
Definition: types.h:55
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:595
base_list & operator=(const base_list &tmp)
Definition: sql_list.h:160
i_string_pair(const char *key_arg, const char *val_arg)
Definition: sql_list.h:702
void prepend(base_list *list)
Definition: sql_list.h:244
const_iterator cbegin() const
Definition: sql_list.h:559
T ** el
Definition: sql_list.h:785
base_list(const base_list &tmp)
This is a shallow copy constructor that implicitly passes the ownership from the source list to the n...
Definition: sql_list.h:156
const string value("\alue\)
list_node ** prev
Definition: sql_list.h:337
const_iterator begin() const
Definition: sql_list.h:554
T * replace(List< T > &a)
Definition: sql_list.h:574
Log info(cout, "NOTE")
List()
Definition: sql_list.h:430
T * pointer
Definition: sql_list.h:625
void delete_elements(void)
Definition: sql_list.h:463
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:77
void sublist(List< T > &list_arg, uint el_arg)
Definition: sql_list.h:599
Definition: item.h:79
bool push_back(T *a)
Definition: sql_list.h:442
void empty()
Definition: sql_list.h:62
list_node ** last
Definition: sql_list.h:132
void * next_fast(void)
Definition: sql_list.h:362
const T * head() const
Definition: sql_list.h:455
T * head()
Definition: sql_list.h:454
ptrdiff_t difference_type
Definition: sql_list.h:623
bool after(void *a, MEM_ROOT *mem_root)
Definition: sql_list.h:399
void * replace(base_list &new_list)
Definition: sql_list.h:375
iterator end()
Definition: sql_list.h:544
T * operator->() const
Definition: sql_list.h:639
List_iterator_fast()
Definition: sql_list.h:595
List(const List< T > &tmp, MEM_ROOT *mem_root)
Definition: sql_list.h:435
T * operator++(int)
Definition: sql_list.h:572
Definition: sql_list.h:689
void replace(uint index, T *new_value)
Definition: sql_list.h:488
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
list_node ** el
Definition: sql_list.h:337
bool push_front(T *a)
Definition: sql_list.h:448
base_list_iterator(base_list &list_par)
Definition: sql_list.h:347
List_iterator_fast(List< T > &a)
Definition: sql_list.h:594
void after(void *element)
Definition: sql_list.h:393
i_string(const char *s)
Definition: sql_list.h:693