← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to sql/sql_list.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/sql_list.h
 
1
#ifndef INCLUDES_MYSQL_SQL_LIST_H
 
2
#define INCLUDES_MYSQL_SQL_LIST_H
 
3
/* Copyright (C) 2000-2003 MySQL AB
 
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
17
 
 
18
 
 
19
#ifdef USE_PRAGMA_INTERFACE
 
20
#pragma interface                       /* gcc class implementation */
 
21
#endif
 
22
 
 
23
/* mysql standard class memory allocator */
 
24
 
 
25
class Sql_alloc
 
26
{
 
27
public:
 
28
  static void *operator new(size_t size) throw ()
 
29
  {
 
30
    return sql_alloc(size);
 
31
  }
 
32
  static void *operator new[](size_t size)
 
33
  {
 
34
    return sql_alloc(size);
 
35
  }
 
36
  static void *operator new[](size_t size, MEM_ROOT *mem_root) throw ()
 
37
  { return alloc_root(mem_root, size); }
 
38
  static void *operator new(size_t size, MEM_ROOT *mem_root) throw ()
 
39
  { return alloc_root(mem_root, size); }
 
40
  static void operator delete(void *ptr, size_t size) { TRASH(ptr, size); }
 
41
  static void operator delete(void *ptr, MEM_ROOT *mem_root)
 
42
  { /* never called */ }
 
43
  static void operator delete[](void *ptr, MEM_ROOT *mem_root)
 
44
  { /* never called */ }
 
45
  static void operator delete[](void *ptr, size_t size) { TRASH(ptr, size); }
 
46
#ifdef HAVE_purify
 
47
  bool dummy;
 
48
  inline Sql_alloc() :dummy(0) {}
 
49
  inline ~Sql_alloc() {}
 
50
#else
 
51
  inline Sql_alloc() {}
 
52
  inline ~Sql_alloc() {}
 
53
#endif
 
54
 
 
55
};
 
56
 
 
57
 
 
58
/*
 
59
  Basic single linked list
 
60
  Used for item and item_buffs.
 
61
  All list ends with a pointer to the 'end_of_list' element, which
 
62
  data pointer is a null pointer and the next pointer points to itself.
 
63
  This makes it very fast to traverse lists as we don't have to
 
64
  test for a specialend condition for list that can't contain a null
 
65
  pointer.
 
66
*/
 
67
 
 
68
 
 
69
/**
 
70
  list_node - a node of a single-linked list.
 
71
  @note We never call a destructor for instances of this class.
 
72
*/
 
73
 
 
74
struct list_node :public Sql_alloc
 
75
{
 
76
  list_node *next;
 
77
  void *info;
 
78
  list_node(void *info_par,list_node *next_par)
 
79
    :next(next_par),info(info_par)
 
80
  {}
 
81
  list_node()                                   /* For end_of_list */
 
82
  {
 
83
    info= 0;
 
84
    next= this;
 
85
  }
 
86
};
 
87
 
 
88
 
 
89
extern list_node end_of_list;
 
90
 
 
91
class base_list :public Sql_alloc
 
92
{
 
93
protected:
 
94
  list_node *first,**last;
 
95
 
 
96
public:
 
97
  uint elements;
 
98
 
 
99
  inline void empty() { elements=0; first= &end_of_list; last=&first;}
 
100
  inline base_list() { empty(); }
 
101
  /**
 
102
    This is a shallow copy constructor that implicitly passes the ownership
 
103
    from the source list to the new instance. The old instance is not
 
104
    updated, so both objects end up sharing the same nodes. If one of
 
105
    the instances then adds or removes a node, the other becomes out of
 
106
    sync ('last' pointer), while still operational. Some old code uses and
 
107
    relies on this behaviour. This logic is quite tricky: please do not use
 
108
    it in any new code.
 
109
  */
 
110
  inline base_list(const base_list &tmp) :Sql_alloc()
 
111
  {
 
112
    elements= tmp.elements;
 
113
    first= tmp.first;
 
114
    last= elements ? tmp.last : &first;
 
115
  }
 
116
  /**
 
117
    Construct a deep copy of the argument in memory root mem_root.
 
118
    The elements themselves are copied by pointer. If you also
 
119
    need to copy elements by value, you should employ
 
120
    list_copy_and_replace_each_value after creating a copy.
 
121
  */
 
122
  base_list(const base_list &rhs, MEM_ROOT *mem_root);
 
123
  inline base_list(bool error) { }
 
124
  inline bool push_back(void *info)
 
125
  {
 
126
    if (((*last)=new list_node(info, &end_of_list)))
 
127
    {
 
128
      last= &(*last)->next;
 
129
      elements++;
 
130
      return 0;
 
131
    }
 
132
    return 1;
 
133
  }
 
134
  inline bool push_back(void *info, MEM_ROOT *mem_root)
 
135
  {
 
136
    if (((*last)=new (mem_root) list_node(info, &end_of_list)))
 
137
    {
 
138
      last= &(*last)->next;
 
139
      elements++;
 
140
      return 0;
 
141
    }
 
142
    return 1;
 
143
  }
 
144
  inline bool push_front(void *info)
 
145
  {
 
146
    list_node *node=new list_node(info,first);
 
147
    if (node)
 
148
    {
 
149
      if (last == &first)
 
150
        last= &node->next;
 
151
      first=node;
 
152
      elements++;
 
153
      return 0;
 
154
    }
 
155
    return 1;
 
156
  }
 
157
  void remove(list_node **prev)
 
158
  {
 
159
    list_node *node=(*prev)->next;
 
160
    if (!--elements)
 
161
      last= &first;
 
162
    else if (last == &(*prev)->next)
 
163
      last= prev;
 
164
    delete *prev;
 
165
    *prev=node;
 
166
  }
 
167
  inline void concat(base_list *list)
 
168
  {
 
169
    if (!list->is_empty())
 
170
    {
 
171
      *last= list->first;
 
172
      last= list->last;
 
173
      elements+= list->elements;
 
174
    }
 
175
  }
 
176
  inline void *pop(void)
 
177
  {
 
178
    if (first == &end_of_list) return 0;
 
179
    list_node *tmp=first;
 
180
    first=first->next;
 
181
    if (!--elements)
 
182
      last= &first;
 
183
    return tmp->info;
 
184
  }
 
185
  inline void disjoin(base_list *list)
 
186
  {
 
187
    list_node **prev= &first;
 
188
    list_node *node= first;
 
189
    list_node *list_first= list->first;
 
190
    elements=0;
 
191
    while (node && node != list_first)
 
192
    {
 
193
      prev= &node->next;
 
194
      node= node->next;
 
195
      elements++;
 
196
    }
 
197
    *prev= *last;
 
198
    last= prev;
 
199
  }
 
200
  inline void prepand(base_list *list)
 
201
  {
 
202
    if (!list->is_empty())
 
203
    {
 
204
      *list->last= first;
 
205
      first= list->first;
 
206
      elements+= list->elements;
 
207
    }
 
208
  }
 
209
  /**
 
210
    Swap two lists.
 
211
  */
 
212
  inline void swap(base_list &rhs)
 
213
  {
 
214
    swap_variables(list_node *, first, rhs.first);
 
215
    swap_variables(list_node **, last, rhs.last);
 
216
    swap_variables(uint, elements, rhs.elements);
 
217
  }
 
218
  inline list_node* last_node() { return *last; }
 
219
  inline list_node* first_node() { return first;}
 
220
  inline void *head() { return first->info; }
 
221
  inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
 
222
  inline bool is_empty() { return first == &end_of_list ; }
 
223
  inline list_node *last_ref() { return &end_of_list; }
 
224
  friend class base_list_iterator;
 
225
  friend class error_list;
 
226
  friend class error_list_iterator;
 
227
 
 
228
#ifdef LIST_EXTRA_DEBUG
 
229
  /*
 
230
    Check list invariants and print results into trace. Invariants are:
 
231
      - (*last) points to end_of_list
 
232
      - There are no NULLs in the list.
 
233
      - base_list::elements is the number of elements in the list.
 
234
 
 
235
    SYNOPSIS
 
236
      check_list()
 
237
        name  Name to print to trace file
 
238
 
 
239
    RETURN 
 
240
      1  The list is Ok.
 
241
      0  List invariants are not met.
 
242
  */
 
243
 
 
244
  bool check_list(const char *name)
 
245
  {
 
246
    base_list *list= this;
 
247
    list_node *node= first;
 
248
    uint cnt= 0;
 
249
 
 
250
    while (node->next != &end_of_list)
 
251
    {
 
252
      if (!node->info)
 
253
      {
 
254
        DBUG_PRINT("list_invariants",("%s: error: NULL element in the list", 
 
255
                                      name));
 
256
        return FALSE;
 
257
      }
 
258
      node= node->next;
 
259
      cnt++;
 
260
    }
 
261
    if (last != &(node->next))
 
262
    {
 
263
      DBUG_PRINT("list_invariants", ("%s: error: wrong last pointer", name));
 
264
      return FALSE;
 
265
    }
 
266
    if (cnt+1 != elements)
 
267
    {
 
268
      DBUG_PRINT("list_invariants", ("%s: error: wrong element count", name));
 
269
      return FALSE;
 
270
    }
 
271
    DBUG_PRINT("list_invariants", ("%s: list is ok", name));
 
272
    return TRUE;
 
273
  }
 
274
#endif // LIST_EXTRA_DEBUG
 
275
 
 
276
protected:
 
277
  void after(void *info,list_node *node)
 
278
  {
 
279
    list_node *new_node=new list_node(info,node->next);
 
280
    node->next=new_node;
 
281
    elements++;
 
282
    if (last == &(node->next))
 
283
      last= &new_node->next;
 
284
  }
 
285
};
 
286
 
 
287
 
 
288
class base_list_iterator
 
289
{
 
290
protected:
 
291
  base_list *list;
 
292
  list_node **el,**prev,*current;
 
293
  void sublist(base_list &ls, uint elm)
 
294
  {
 
295
    ls.first= *el;
 
296
    ls.last= list->last;
 
297
    ls.elements= elm;
 
298
  }
 
299
public:
 
300
  base_list_iterator() 
 
301
    :list(0), el(0), prev(0), current(0)
 
302
  {}
 
303
 
 
304
  base_list_iterator(base_list &list_par) 
 
305
  { init(list_par); }
 
306
 
 
307
  inline void init(base_list &list_par)
 
308
  {
 
309
    list= &list_par;
 
310
    el= &list_par.first;
 
311
    prev= 0;
 
312
    current= 0;
 
313
  }
 
314
 
 
315
  inline void *next(void)
 
316
  {
 
317
    prev=el;
 
318
    current= *el;
 
319
    el= &current->next;
 
320
    return current->info;
 
321
  }
 
322
  inline void *next_fast(void)
 
323
  {
 
324
    list_node *tmp;
 
325
    tmp= *el;
 
326
    el= &tmp->next;
 
327
    return tmp->info;
 
328
  }
 
329
  inline void rewind(void)
 
330
  {
 
331
    el= &list->first;
 
332
  }
 
333
  inline void *replace(void *element)
 
334
  {                                             // Return old element
 
335
    void *tmp=current->info;
 
336
    DBUG_ASSERT(current->info != 0);
 
337
    current->info=element;
 
338
    return tmp;
 
339
  }
 
340
  void *replace(base_list &new_list)
 
341
  {
 
342
    void *ret_value=current->info;
 
343
    if (!new_list.is_empty())
 
344
    {
 
345
      *new_list.last=current->next;
 
346
      current->info=new_list.first->info;
 
347
      current->next=new_list.first->next;
 
348
      if ((list->last == &current->next) && (new_list.elements > 1))
 
349
        list->last= new_list.last;
 
350
      list->elements+=new_list.elements-1;
 
351
    }
 
352
    return ret_value;                           // return old element
 
353
  }
 
354
  inline void remove(void)                      // Remove current
 
355
  {
 
356
    list->remove(prev);
 
357
    el=prev;
 
358
    current=0;                                  // Safeguard
 
359
  }
 
360
  void after(void *element)                     // Insert element after current
 
361
  {
 
362
    list->after(element,current);
 
363
    current=current->next;
 
364
    el= &current->next;
 
365
  }
 
366
  inline void **ref(void)                       // Get reference pointer
 
367
  {
 
368
    return &current->info;
 
369
  }
 
370
  inline bool is_last(void)
 
371
  {
 
372
    return el == &list->last_ref()->next;
 
373
  }
 
374
  friend class error_list_iterator;
 
375
};
 
376
 
 
377
template <class T> class List :public base_list
 
378
{
 
379
public:
 
380
  inline List() :base_list() {}
 
381
  inline List(const List<T> &tmp) :base_list(tmp) {}
 
382
  inline List(const List<T> &tmp, MEM_ROOT *mem_root) :
 
383
    base_list(tmp, mem_root) {}
 
384
  inline bool push_back(T *a) { return base_list::push_back(a); }
 
385
  inline bool push_back(T *a, MEM_ROOT *mem_root)
 
386
  { return base_list::push_back(a, mem_root); }
 
387
  inline bool push_front(T *a) { return base_list::push_front(a); }
 
388
  inline T* head() {return (T*) base_list::head(); }
 
389
  inline T** head_ref() {return (T**) base_list::head_ref(); }
 
390
  inline T* pop()  {return (T*) base_list::pop(); }
 
391
  inline void concat(List<T> *list) { base_list::concat(list); }
 
392
  inline void disjoin(List<T> *list) { base_list::disjoin(list); }
 
393
  inline void prepand(List<T> *list) { base_list::prepand(list); }
 
394
  void delete_elements(void)
 
395
  {
 
396
    list_node *element,*next;
 
397
    for (element=first; element != &end_of_list; element=next)
 
398
    {
 
399
      next=element->next;
 
400
      delete (T*) element->info;
 
401
    }
 
402
    empty();
 
403
  }
 
404
};
 
405
 
 
406
 
 
407
template <class T> class List_iterator :public base_list_iterator
 
408
{
 
409
public:
 
410
  List_iterator(List<T> &a) : base_list_iterator(a) {}
 
411
  List_iterator() : base_list_iterator() {}
 
412
  inline void init(List<T> &a) { base_list_iterator::init(a); }
 
413
  inline T* operator++(int) { return (T*) base_list_iterator::next(); }
 
414
  inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
 
415
  inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
 
416
  inline void rewind(void)  { base_list_iterator::rewind(); }
 
417
  inline void remove()      { base_list_iterator::remove(); }
 
418
  inline void after(T *a)   { base_list_iterator::after(a); }
 
419
  inline T** ref(void)      { return (T**) base_list_iterator::ref(); }
 
420
};
 
421
 
 
422
 
 
423
template <class T> class List_iterator_fast :public base_list_iterator
 
424
{
 
425
protected:
 
426
  inline T *replace(T *a)   { return (T*) 0; }
 
427
  inline T *replace(List<T> &a) { return (T*) 0; }
 
428
  inline void remove(void)  { }
 
429
  inline void after(T *a)   { }
 
430
  inline T** ref(void)      { return (T**) 0; }
 
431
 
 
432
public:
 
433
  inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
 
434
  inline List_iterator_fast() : base_list_iterator() {}
 
435
  inline void init(List<T> &a) { base_list_iterator::init(a); }
 
436
  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
 
437
  inline void rewind(void)  { base_list_iterator::rewind(); }
 
438
  void sublist(List<T> &list_arg, uint el_arg)
 
439
  {
 
440
    base_list_iterator::sublist(list_arg, el_arg);
 
441
  }
 
442
};
 
443
 
 
444
 
 
445
/*
 
446
  A simple intrusive list which automaticly removes element from list
 
447
  on delete (for THD element)
 
448
*/
 
449
 
 
450
struct ilink
 
451
{
 
452
  struct ilink **prev,*next;
 
453
  static void *operator new(size_t size)
 
454
  {
 
455
    return (void*)my_malloc((uint)size, MYF(MY_WME | MY_FAE | ME_FATALERROR));
 
456
  }
 
457
  static void operator delete(void* ptr_arg, size_t size)
 
458
  {
 
459
     my_free((uchar*)ptr_arg, MYF(MY_WME|MY_ALLOW_ZERO_PTR));
 
460
  }
 
461
 
 
462
  inline ilink()
 
463
  {
 
464
    prev=0; next=0;
 
465
  }
 
466
  inline void unlink()
 
467
  {
 
468
    /* Extra tests because element doesn't have to be linked */
 
469
    if (prev) *prev= next;
 
470
    if (next) next->prev=prev;
 
471
    prev=0 ; next=0;
 
472
  }
 
473
  virtual ~ilink() { unlink(); }                /*lint -e1740 */
 
474
};
 
475
 
 
476
 
 
477
/* Needed to be able to have an I_List of char* strings in mysqld.cc. */
 
478
 
 
479
class i_string: public ilink
 
480
{
 
481
public:
 
482
  const char* ptr;
 
483
  i_string():ptr(0) { }
 
484
  i_string(const char* s) : ptr(s) {}
 
485
};
 
486
 
 
487
/* needed for linked list of two strings for replicate-rewrite-db */
 
488
class i_string_pair: public ilink
 
489
{
 
490
public:
 
491
  const char* key;
 
492
  const char* val;
 
493
  i_string_pair():key(0),val(0) { }
 
494
  i_string_pair(const char* key_arg, const char* val_arg) : 
 
495
    key(key_arg),val(val_arg) {}
 
496
};
 
497
 
 
498
 
 
499
template <class T> class I_List_iterator;
 
500
 
 
501
/*
 
502
  WARNING: copy constructor of this class does not create a usable
 
503
  copy, as its members may point at each other.
 
504
*/
 
505
 
 
506
class base_ilist
 
507
{
 
508
public:
 
509
  struct ilink *first,last;
 
510
  inline void empty() { first= &last; last.prev= &first; }
 
511
  base_ilist() { empty(); }
 
512
  inline bool is_empty() {  return first == &last; }
 
513
  inline void append(ilink *a)
 
514
  {
 
515
    first->prev= &a->next;
 
516
    a->next=first; a->prev= &first; first=a;
 
517
  }
 
518
  inline void push_back(ilink *a)
 
519
  {
 
520
    *last.prev= a;
 
521
    a->next= &last;
 
522
    a->prev= last.prev;
 
523
    last.prev= &a->next;
 
524
  }
 
525
  inline struct ilink *get()
 
526
  {
 
527
    struct ilink *first_link=first;
 
528
    if (first_link == &last)
 
529
      return 0;
 
530
    first_link->unlink();                       // Unlink from list
 
531
    return first_link;
 
532
  }
 
533
  inline struct ilink *head()
 
534
  {
 
535
    return (first != &last) ? first : 0;
 
536
  }
 
537
  friend class base_list_iterator;
 
538
};
 
539
 
 
540
 
 
541
class base_ilist_iterator
 
542
{
 
543
  base_ilist *list;
 
544
  struct ilink **el,*current;
 
545
public:
 
546
  base_ilist_iterator(base_ilist &list_par) :list(&list_par),
 
547
    el(&list_par.first),current(0) {}
 
548
  void *next(void)
 
549
  {
 
550
    /* This is coded to allow push_back() while iterating */
 
551
    current= *el;
 
552
    if (current == &list->last) return 0;
 
553
    el= &current->next;
 
554
    return current;
 
555
  }
 
556
};
 
557
 
 
558
 
 
559
template <class T>
 
560
class I_List :private base_ilist
 
561
{
 
562
public:
 
563
  I_List() :base_ilist()        {}
 
564
  inline void empty()           { base_ilist::empty(); }
 
565
  inline bool is_empty()        { return base_ilist::is_empty(); } 
 
566
  inline void append(T* a)      { base_ilist::append(a); }
 
567
  inline void push_back(T* a)   { base_ilist::push_back(a); }
 
568
  inline T* get()               { return (T*) base_ilist::get(); }
 
569
  inline T* head()              { return (T*) base_ilist::head(); }
 
570
#ifndef _lint
 
571
  friend class I_List_iterator<T>;
 
572
#endif
 
573
};
 
574
 
 
575
 
 
576
template <class T> class I_List_iterator :public base_ilist_iterator
 
577
{
 
578
public:
 
579
  I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
 
580
  inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
 
581
};
 
582
 
 
583
/**
 
584
  Make a deep copy of each list element.
 
585
 
 
586
  @note A template function and not a template method of class List
 
587
  is employed because of explicit template instantiation:
 
588
  in server code there are explicit instantiations of List<T> and
 
589
  an explicit instantiation of a template requires that any method
 
590
  of the instantiated class used in the template can be resolved.
 
591
  Evidently not all template arguments have clone() method with
 
592
  the right signature.
 
593
 
 
594
  @return You must query the error state in THD for out-of-memory
 
595
  situation after calling this function.
 
596
*/
 
597
 
 
598
template <typename T>
 
599
inline
 
600
void
 
601
list_copy_and_replace_each_value(List<T> &list, MEM_ROOT *mem_root)
 
602
{
 
603
  /* Make a deep copy of each element */
 
604
  List_iterator<T> it(list);
 
605
  T *el;
 
606
  while ((el= it++))
 
607
    it.replace(el->clone(mem_root));
 
608
}
 
609
 
 
610
#endif // INCLUDES_MYSQL_SQL_LIST_H