1#ifndef INCLUDES_MYSQL_SQL_LIST_H
2#define INCLUDES_MYSQL_SQL_LIST_H
3/* Copyright (c) 2000, 2012, Oracle and/or its affiliates.
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 as published by
7 the Free Software Foundation; version 2 of the License.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
17
18#ifdef USE_PRAGMA_INTERFACE
19#pragma interface /* gcc class implementation */
20#endif
21
22#include "sql_alloc.h"
23
24/**
25 Simple intrusive linked list.
26
27 @remark Similar in nature to base_list, but intrusive. It keeps a
28 a pointer to the first element in the list and a indirect
29 reference to the last element.
30*/
31
32template <typename T>
33class SQL_I_List :public Sql_alloc
34{
35public:
36 uint elements;
37 /** The first element in the list. */
38 T *first;
39 /** A reference to the next element in the list. */
40 T **next;
41
42 SQL_I_List() { empty(); }
43
44 SQL_I_List(const SQL_I_List &tmp) : Sql_alloc()
45 {
46 elements= tmp.elements;
47 first= tmp.first;
48 next= elements ? tmp.next : &first;
49 }
50
51 inline void empty()
52 {
53 elements= 0;
54 first= NULL;
55 next= &first;
56 }
57
58 inline void link_in_list(T *element, T **next_ptr)
59 {
60 elements++;
61 (*next)= element;
62 next= next_ptr;
63 *next= NULL;
64 }
65
66 inline void save_and_clear(SQL_I_List<T> *save)
67 {
68 *save= *this;
69 empty();
70 }
71
72 inline void push_front(SQL_I_List<T> *save)
73 {
74 /* link current list last */
75 *save->next= first;
76 first= save->first;
77 elements+= save->elements;
78 }
79
80 inline void push_back(SQL_I_List<T> *save)
81 {
82 if (save->first)
83 {
84 *next= save->first;
85 next= save->next;
86 elements+= save->elements;
87 }
88 }
89};
90
91
92/*
93 Basic single linked list
94 Used for item and item_buffs.
95 All list ends with a pointer to the 'end_of_list' element, which
96 data pointer is a null pointer and the next pointer points to itself.
97 This makes it very fast to traverse lists as we don't have to
98 test for a specialend condition for list that can't contain a null
99 pointer.
100*/
101
102
103/**
104 list_node - a node of a single-linked list.
105 @note We never call a destructor for instances of this class.
106*/
107
108struct list_node :public Sql_alloc
109{
110 list_node *next;
111 void *info;
112 list_node(void *info_par,list_node *next_par)
113 :next(next_par),info(info_par)
114 {}
115 list_node() /* For end_of_list */
116 {
117 info= 0;
118 next= this;
119 }
120};
121
122typedef bool List_eq(void *a, void *b);
123
124extern MYSQL_PLUGIN_IMPORT list_node end_of_list;
125
126class base_list :public Sql_alloc
127{
128protected:
129 list_node *first,**last;
130
131public:
132 uint elements;
133
134 bool operator==(const base_list &rhs) const
135 {
136 return
137 elements == rhs.elements &&
138 first == rhs.first &&
139 last == rhs.last;
140 }
141 base_list& operator=(const base_list &rhs)
142 {
143 elements= rhs.elements;
144 first= rhs.first;
145 last= elements ? rhs.last : &first;
146 return *this;
147 }
148
149 inline void empty() { elements=0; first= &end_of_list; last=&first;}
150 inline base_list() { empty(); }
151 /**
152 This is a shallow copy constructor that implicitly passes the ownership
153 from the source list to the new instance. The old instance is not
154 updated, so both objects end up sharing the same nodes. If one of
155 the instances then adds or removes a node, the other becomes out of
156 sync ('last' pointer), while still operational. Some old code uses and
157 relies on this behaviour. This logic is quite tricky: please do not use
158 it in any new code.
159 */
160 inline base_list(const base_list &tmp) :Sql_alloc()
161 {
162 *this= tmp;
163 }
164 /**
165 Construct a deep copy of the argument in memory root mem_root.
166 The elements themselves are copied by pointer. If you also
167 need to copy elements by value, you should employ
168 list_copy_and_replace_each_value after creating a copy.
169 */
170 bool copy(const base_list *rhs, MEM_ROOT *mem_root);
171 base_list(const base_list &rhs, MEM_ROOT *mem_root) { copy(&rhs, mem_root); }
172 inline base_list(bool) {}
173 inline bool push_back(void *info)
174 {
175 if (((*last)=new list_node(info, &end_of_list)))
176 {
177 last= &(*last)->next;
178 elements++;
179 return 0;
180 }
181 return 1;
182 }
183 inline bool push_back(void *info, MEM_ROOT *mem_root)
184 {
185 if (((*last)=new (mem_root) list_node(info, &end_of_list)))
186 {
187 last= &(*last)->next;
188 elements++;
189 return 0;
190 }
191 return 1;
192 }
193 bool push_front_impl(list_node *node)
194 {
195 if (node)
196 {
197 if (last == &first)
198 last= &node->next;
199 first=node;
200 elements++;
201 return 0;
202 }
203 return 1;
204 }
205 inline bool push_front(void *info)
206 { return push_front_impl(new list_node(info, first)); }
207 inline bool push_front(void *info, MEM_ROOT *mem_root)
208 { return push_front_impl(new (mem_root) list_node(info,first)); }
209 void remove(list_node **prev)
210 {
211 list_node *node=(*prev)->next;
212 if (!--elements)
213 last= &first;
214 else if (last == &(*prev)->next)
215 last= prev;
216 delete *prev;
217 *prev=node;
218 }
219 inline void append(base_list *list)
220 {
221 if (!list->is_empty())
222 {
223 if (is_empty())
224 {
225 *this= *list;
226 return;
227 }
228 *last= list->first;
229 last= list->last;
230 elements+= list->elements;
231 }
232 }
233 inline void *pop(void)
234 {
235 if (first == &end_of_list) return 0;
236 list_node *tmp=first;
237 first=first->next;
238 if (!--elements)
239 last= &first;
240 return tmp->info;
241 }
242
243 /*
244 Remove from this list elements that are contained in the passed list.
245 We assume that the passed list is a tail of this list (that is, the whole
246 list_node* elements are shared).
247 */
248 inline void disjoin(const base_list *list)
249 {
250 list_node **prev= &first;
251 list_node *node= first;
252 list_node *list_first= list->first;
253 elements=0;
254 while (node != &end_of_list && node != list_first)
255 {
256 prev= &node->next;
257 node= node->next;
258 elements++;
259 if (node == &end_of_list)
260 return;
261 }
262 *prev= &end_of_list;
263 last= prev;
264 }
265 inline void prepend(base_list *list)
266 {
267 if (!list->is_empty())
268 {
269 if (is_empty())
270 last= list->last;
271 *list->last= first;
272 first= list->first;
273 elements+= list->elements;
274 }
275 }
276 /**
277 Swap two lists.
278 */
279 inline void swap(base_list &rhs)
280 {
281 swap_variables(list_node *, first, rhs.first);
282 swap_variables(list_node **, last, rhs.last);
283 swap_variables(uint, elements, rhs.elements);
284 }
285 inline list_node* last_node() { return *last; }
286 inline list_node* first_node() { return first;}
287 inline void *head() { return first->info; }
288 inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
289 inline bool is_empty() { return first == &end_of_list ; }
290 inline list_node *last_ref() { return &end_of_list; }
291 inline bool add_unique(void *info, List_eq *eq)
292 {
293 list_node *node= first;
294 for (;
295 node != &end_of_list && (!(*eq)(node->info, info));
296 node= node->next) ;
297 if (node == &end_of_list)
298 return push_back(info);
299 return 1;
300 }
301 friend class base_list_iterator;
302 friend class error_list;
303 friend class error_list_iterator;
304
305 /*
306 Return N-th element in the list, or NULL if the list has
307 less than N elements.
308 */
309 void *elem(uint n)
310 {
311 list_node *node= first;
312 void *data= NULL;
313 for (uint i= 0; i <= n; i++)
314 {
315 if (node == &end_of_list)
316 {
317 data= NULL;
318 break;
319 }
320 data= node->info;
321 node= node->next;
322 }
323 return data;
324 }
325
326#ifdef LIST_EXTRA_DEBUG
327 /*
328 Check list invariants and print results into trace. Invariants are:
329 - (*last) points to end_of_list
330 - There are no NULLs in the list.
331 - base_list::elements is the number of elements in the list.
332
333 SYNOPSIS
334 check_list()
335 name Name to print to trace file
336
337 RETURN
338 1 The list is Ok.
339 0 List invariants are not met.
340 */
341
342 bool check_list(const char *name)
343 {
344 base_list *list= this;
345 list_node *node= first;
346 uint cnt= 0;
347
348 while (node->next != &end_of_list)
349 {
350 if (!node->info)
351 {
352 DBUG_PRINT("list_invariants",("%s: error: NULL element in the list",
353 name));
354 return FALSE;
355 }
356 node= node->next;
357 cnt++;
358 }
359 if (last != &(node->next))
360 {
361 DBUG_PRINT("list_invariants", ("%s: error: wrong last pointer", name));
362 return FALSE;
363 }
364 if (cnt+1 != elements)
365 {
366 DBUG_PRINT("list_invariants", ("%s: error: wrong element count", name));
367 return FALSE;
368 }
369 DBUG_PRINT("list_invariants", ("%s: list is ok", name));
370 return TRUE;
371 }
372#endif // LIST_EXTRA_DEBUG
373
374protected:
375 void after(void *info,list_node *node)
376 {
377 list_node *new_node=new list_node(info,node->next);
378 node->next=new_node;
379 elements++;
380 if (last == &(node->next))
381 last= &new_node->next;
382 }
383};
384
385
386class base_list_iterator
387{
388protected:
389 base_list *list;
390 list_node **el,**prev,*current;
391 void sublist(base_list &ls, uint elm)
392 {
393 ls.first= *el;
394 ls.last= list->last;
395 ls.elements= elm;
396 }
397public:
398 base_list_iterator()
399 :list(0), el(0), prev(0), current(0)
400 {}
401
402 base_list_iterator(base_list &list_par)
403 { init(list_par); }
404
405 inline void init(base_list &list_par)
406 {
407 list= &list_par;
408 el= &list_par.first;
409 prev= 0;
410 current= 0;
411 }
412
413 inline void *next(void)
414 {
415 prev=el;
416 current= *el;
417 el= &current->next;
418 return current->info;
419 }
420 /* Get what calling next() would return, without moving the iterator */
421 inline void *peek()
422 {
423 return (*el)->info;
424 }
425 inline void *next_fast(void)
426 {
427 list_node *tmp;
428 tmp= *el;
429 el= &tmp->next;
430 return tmp->info;
431 }
432 inline void rewind(void)
433 {
434 el= &list->first;
435 }
436 inline void *replace(void *element)
437 { // Return old element
438 void *tmp=current->info;
439 DBUG_ASSERT(current->info != 0);
440 current->info=element;
441 return tmp;
442 }
443 void *replace(base_list &new_list)
444 {
445 void *ret_value=current->info;
446 if (!new_list.is_empty())
447 {
448 *new_list.last=current->next;
449 current->info=new_list.first->info;
450 current->next=new_list.first->next;
451 if ((list->last == &current->next) && (new_list.elements > 1))
452 list->last= new_list.last;
453 list->elements+=new_list.elements-1;
454 }
455 return ret_value; // return old element
456 }
457 inline void remove(void) // Remove current
458 {
459 list->remove(prev);
460 el=prev;
461 current=0; // Safeguard
462 }
463 void after(void *element) // Insert element after current
464 {
465 list->after(element,current);
466 current=current->next;
467 el= &current->next;
468 }
469 inline void **ref(void) // Get reference pointer
470 {
471 return &current->info;
472 }
473 inline bool is_last(void)
474 {
475 return el == &list->last_ref()->next;
476 }
477 inline bool at_end()
478 {
479 return current == &end_of_list;
480 }
481 friend class error_list_iterator;
482};
483
484template <class T> class List :public base_list
485{
486public:
487 inline List() :base_list() {}
488 inline List(const List<T> &tmp) :base_list(tmp) {}
489 inline List(const List<T> &tmp, MEM_ROOT *mem_root) :
490 base_list(tmp, mem_root) {}
491 inline bool push_back(T *a) { return base_list::push_back(a); }
492 inline bool push_back(T *a, MEM_ROOT *mem_root)
493 { return base_list::push_back((void*) a, mem_root); }
494 inline bool push_front(T *a) { return base_list::push_front(a); }
495 inline bool push_front(T *a, MEM_ROOT *mem_root)
496 { return base_list::push_front((void*) a, mem_root); }
497 inline T* head() {return (T*) base_list::head(); }
498 inline T** head_ref() {return (T**) base_list::head_ref(); }
499 inline T* pop() {return (T*) base_list::pop(); }
500 inline void append(List<T> *list) { base_list::append(list); }
501 inline void prepend(List<T> *list) { base_list::prepend(list); }
502 inline void disjoin(List<T> *list) { base_list::disjoin(list); }
503 inline bool add_unique(T *a, bool (*eq)(T *a, T *b))
504 { return base_list::add_unique(a, (List_eq *)eq); }
505 inline bool copy(const List<T> *list, MEM_ROOT *root)
506 { return base_list::copy(list, root); }
507 void delete_elements(void)
508 {
509 list_node *element,*next;
510 for (element=first; element != &end_of_list; element=next)
511 {
512 next=element->next;
513 delete (T*) element->info;
514 }
515 empty();
516 }
517 T *elem(uint n) { return (T*) base_list::elem(n); }
518};
519
520
521template <class T> class List_iterator :public base_list_iterator
522{
523public:
524 List_iterator(List<T> &a) : base_list_iterator(a) {}
525 List_iterator() : base_list_iterator() {}
526 inline void init(List<T> &a) { base_list_iterator::init(a); }
527 inline T* operator++(int) { return (T*) base_list_iterator::next(); }
528 inline T* peek() { return (T*) base_list_iterator::peek(); }
529 inline T *replace(T *a) { return (T*) base_list_iterator::replace(a); }
530 inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
531 inline void rewind(void) { base_list_iterator::rewind(); }
532 inline void remove() { base_list_iterator::remove(); }
533 inline void after(T *a) { base_list_iterator::after(a); }
534 inline T** ref(void) { return (T**) base_list_iterator::ref(); }
535};
536
537
538template <class T> class List_iterator_fast :public base_list_iterator
539{
540protected:
541 inline T *replace(T *) { return (T*) 0; }
542 inline T *replace(List<T> &) { return (T*) 0; }
543 inline void remove(void) {}
544 inline void after(T *) {}
545 inline T** ref(void) { return (T**) 0; }
546
547public:
548 inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
549 inline List_iterator_fast() : base_list_iterator() {}
550 inline void init(List<T> &a) { base_list_iterator::init(a); }
551 inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
552 inline void rewind(void) { base_list_iterator::rewind(); }
553 void sublist(List<T> &list_arg, uint el_arg)
554 {
555 base_list_iterator::sublist(list_arg, el_arg);
556 }
557};
558
559
560/*
561 Bubble sort algorithm for List<T>.
562 This sort function is supposed to be used only for very short list.
563 Currently it is used for the lists of Item_equal objects and
564 for some lists in the table elimination algorithms. In both
565 cases the sorted lists are very short.
566*/
567
568template <class T>
569inline void bubble_sort(List<T> *list_to_sort,
570 int (*sort_func)(T *a, T *b, void *arg), void *arg)
571{
572 bool swap;
573 T **ref1= 0;
574 T **ref2= 0;
575 List_iterator<T> it(*list_to_sort);
576 do
577 {
578 T **last_ref= ref1;
579 T *item1= it++;
580 ref1= it.ref();
581 T *item2;
582
583 swap= FALSE;
584 while ((item2= it++) && (ref2= it.ref()) != last_ref)
585 {
586 if (sort_func(item1, item2, arg) > 0)
587 {
588 *ref1= item2;
589 *ref2= item1;
590 swap= TRUE;
591 }
592 else
593 item1= item2;
594 ref1= ref2;
595 }
596 it.rewind();
597 } while (swap);
598}
599
600
601/*
602 A simple intrusive list which automaticly removes element from list
603 on delete (for THD element)
604*/
605
606struct ilink
607{
608 struct ilink **prev,*next;
609 static void *operator new(size_t size) throw ()
610 {
611 return (void*)my_malloc((uint)size, MYF(MY_WME | MY_FAE | ME_FATALERROR));
612 }
613 static void operator delete(void* ptr_arg, size_t)
614 {
615 my_free(ptr_arg);
616 }
617
618 inline ilink()
619 {
620 prev=0; next=0;
621 }
622 inline void unlink()
623 {
624 /* Extra tests because element doesn't have to be linked */
625 if (prev) *prev= next;
626 if (next) next->prev=prev;
627 prev=0 ; next=0;
628 }
629 inline void assert_linked()
630 {
631 DBUG_ASSERT(prev != 0 && next != 0);
632 }
633 inline void assert_not_linked()
634 {
635 DBUG_ASSERT(prev == 0 && next == 0);
636 }
637 virtual ~ilink() { unlink(); } /*lint -e1740 */
638};
639
640
641/* Needed to be able to have an I_List of char* strings in mysqld.cc. */
642
643class i_string: public ilink
644{
645public:
646 const char* ptr;
647 i_string():ptr(0) { }
648 i_string(const char* s) : ptr(s) {}
649};
650
651/* needed for linked list of two strings for replicate-rewrite-db */
652class i_string_pair: public ilink
653{
654public:
655 const char* key;
656 const char* val;
657 i_string_pair():key(0),val(0) { }
658 i_string_pair(const char* key_arg, const char* val_arg) :
659 key(key_arg),val(val_arg) {}
660};
661
662
663template <class T> class I_List_iterator;
664
665
666class base_ilist
667{
668 struct ilink *first;
669 struct ilink last;
670public:
671 inline void empty() { first= &last; last.prev= &first; }
672 base_ilist() { empty(); }
673 inline bool is_empty() { return first == &last; }
674 // Returns true if p is the last "real" object in the list,
675 // i.e. p->next points to the sentinel.
676 inline bool is_last(ilink *p) { return p->next == NULL || p->next == &last; }
677 inline void append(ilink *a)
678 {
679 first->prev= &a->next;
680 a->next=first; a->prev= &first; first=a;
681 }
682 inline void push_back(ilink *a)
683 {
684 *last.prev= a;
685 a->next= &last;
686 a->prev= last.prev;
687 last.prev= &a->next;
688 }
689 inline struct ilink *get()
690 {
691 struct ilink *first_link=first;
692 if (first_link == &last)
693 return 0;
694 first_link->unlink(); // Unlink from list
695 return first_link;
696 }
697 inline struct ilink *head()
698 {
699 return (first != &last) ? first : 0;
700 }
701
702 /**
703 Moves list elements to new owner, and empties current owner (i.e. this).
704
705 @param[in,out] new_owner The new owner of the list elements.
706 Should be empty in input.
707 */
708
709 void move_elements_to(base_ilist *new_owner)
710 {
711 DBUG_ASSERT(new_owner->is_empty());
712 new_owner->first= first;
713 new_owner->last= last;
714 empty();
715 }
716
717 friend class base_ilist_iterator;
718 private:
719 /*
720 We don't want to allow copying of this class, as that would give us
721 two list heads containing the same elements.
722 So we declare, but don't define copy CTOR and assignment operator.
723 */
724 base_ilist(const base_ilist&);
725 void operator=(const base_ilist&);
726};
727
728
729class base_ilist_iterator
730{
731 base_ilist *list;
732 struct ilink **el,*current;
733public:
734 base_ilist_iterator(base_ilist &list_par) :list(&list_par),
735 el(&list_par.first),current(0) {}
736 void *next(void)
737 {
738 /* This is coded to allow push_back() while iterating */
739 current= *el;
740 if (current == &list->last) return 0;
741 el= &current->next;
742 return current;
743 }
744};
745
746
747template <class T>
748class I_List :private base_ilist
749{
750public:
751 I_List() :base_ilist() {}
752 inline bool is_last(T *p) { return base_ilist::is_last(p); }
753 inline void empty() { base_ilist::empty(); }
754 inline bool is_empty() { return base_ilist::is_empty(); }
755 inline void append(T* a) { base_ilist::append(a); }
756 inline void push_back(T* a) { base_ilist::push_back(a); }
757 inline T* get() { return (T*) base_ilist::get(); }
758 inline T* head() { return (T*) base_ilist::head(); }
759 inline void move_elements_to(I_List<T>* new_owner) {
760 base_ilist::move_elements_to(new_owner);
761 }
762#ifndef _lint
763 friend class I_List_iterator<T>;
764#endif
765};
766
767
768template <class T> class I_List_iterator :public base_ilist_iterator
769{
770public:
771 I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
772 inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
773};
774
775/**
776 Make a deep copy of each list element.
777
778 @note A template function and not a template method of class List
779 is employed because of explicit template instantiation:
780 in server code there are explicit instantiations of List<T> and
781 an explicit instantiation of a template requires that any method
782 of the instantiated class used in the template can be resolved.
783 Evidently not all template arguments have clone() method with
784 the right signature.
785
786 @return You must query the error state in THD for out-of-memory
787 situation after calling this function.
788*/
789
790template <typename T>
791inline
792void
793list_copy_and_replace_each_value(List<T> &list, MEM_ROOT *mem_root)
794{
795 /* Make a deep copy of each element */
796 List_iterator<T> it(list);
797 T *el;
798 while ((el= it++))
799 it.replace(el->clone(mem_root));
800}
801
802void free_list(I_List <i_string_pair> *list);
803void free_list(I_List <i_string> *list);
804
805#endif // INCLUDES_MYSQL_SQL_LIST_H
806