← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_list.h

  • Committer: Monty Taylor
  • Date: 2008-10-07 19:30:18 UTC
  • mfrom: (322.2.8 stdize-code)
  • mto: This revision was merged to the branch mainline in revision 491.
  • Revision ID: monty@inaugust.com-20081007193018-22fhaywc990akeqa
Merged code from Mats that I should have merged a while ago.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/sql_list.h
1
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
3
 *
4
 
 *  Copyright (C) 2008 Sun Microsystems, Inc.
 
4
 *  Copyright (C) 2008 Sun Microsystems
5
5
 *
6
6
 *  This program is free software; you can redistribute it and/or modify
7
7
 *  it under the terms of the GNU General Public License as published by
17
17
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
18
 */
19
19
 
20
 
#ifndef DRIZZLED_SQL_LIST_H
21
 
#define DRIZZLED_SQL_LIST_H
22
 
 
23
 
#include <cstdlib>
24
 
#include <cassert>
 
20
#ifndef INCLUDES_DRIZZLE_SQL_LIST_H
 
21
#define INCLUDES_DRIZZLE_SQL_LIST_H
 
22
 
 
23
 
 
24
#ifdef USE_PRAGMA_INTERFACE
 
25
#pragma interface                       /* gcc class implementation */
 
26
#endif
 
27
 
25
28
#include <utility>
26
29
#include <algorithm>
27
 
#include <drizzled/memory/sql_alloc.h>
28
 
#include <drizzled/visibility.h>
29
 
 
30
 
namespace drizzled {
31
 
 
32
 
typedef struct st_sql_list 
33
 
{
 
30
 
 
31
/** Struct to handle simple linked lists. */
 
32
typedef struct st_sql_list {
34
33
  uint32_t elements;
35
34
  unsigned char *first;
36
35
  unsigned char **next;
37
36
 
38
 
  inline void clear()
 
37
  st_sql_list() {}                              /* Remove gcc warning */
 
38
  inline void empty()
39
39
  {
40
40
    elements=0;
41
41
    first=0;
51
51
  inline void save_and_clear(struct st_sql_list *save)
52
52
  {
53
53
    *save= *this;
54
 
    clear();
 
54
    empty();
55
55
  }
56
56
  inline void push_front(struct st_sql_list *save)
57
57
  {
70
70
  }
71
71
} SQL_LIST;
72
72
 
 
73
/* mysql standard class memory allocator */
 
74
class Sql_alloc
 
75
{
 
76
public:
 
77
  static void *operator new(size_t size) throw ()
 
78
  {
 
79
    return sql_alloc(size);
 
80
  }
 
81
  static void *operator new[](size_t size)
 
82
  {
 
83
    return sql_alloc(size);
 
84
  }
 
85
  static void *operator new[](size_t size, MEM_ROOT *mem_root) throw ()
 
86
  { return alloc_root(mem_root, size); }
 
87
  static void *operator new(size_t size, MEM_ROOT *mem_root) throw ()
 
88
  { return alloc_root(mem_root, size); }
 
89
  static void operator delete(void *ptr __attribute__((unused)),
 
90
                              size_t size __attribute__((unused)))
 
91
  { TRASH(ptr, size); }
 
92
  static void operator delete(void *ptr __attribute__((unused)),
 
93
                              MEM_ROOT *mem_root __attribute__((unused)))
 
94
  { /* never called */ }
 
95
  static void operator delete[](void *ptr __attribute__((unused)),
 
96
                                MEM_ROOT *mem_root __attribute__((unused)))
 
97
  { /* never called */ }
 
98
  static void operator delete[](void *ptr __attribute__((unused)),
 
99
                                size_t size __attribute__((unused)))
 
100
  { TRASH(ptr, size); }
 
101
#ifdef HAVE_purify
 
102
  bool dummy;
 
103
  inline Sql_alloc() :dummy(0) {}
 
104
  inline ~Sql_alloc() {}
 
105
#else
 
106
  inline Sql_alloc() {}
 
107
  inline ~Sql_alloc() {}
 
108
#endif
 
109
 
 
110
};
 
111
 
 
112
 
73
113
/*
74
114
  Basic single linked list
75
115
  Used for item and item_buffs.
86
126
  @note We never call a destructor for instances of this class.
87
127
*/
88
128
 
89
 
struct list_node : public memory::SqlAlloc
 
129
struct list_node :public Sql_alloc
90
130
{
91
131
  list_node *next;
92
132
  void *info;
101
141
};
102
142
 
103
143
 
104
 
extern DRIZZLED_API list_node end_of_list;
 
144
extern list_node end_of_list;
105
145
 
106
 
class base_list :public memory::SqlAlloc
 
146
class base_list :public Sql_alloc
107
147
{
108
148
protected:
109
149
  list_node *first,**last;
111
151
public:
112
152
  uint32_t elements;
113
153
 
114
 
  inline void clear() { elements=0; first= &end_of_list; last=&first;}
115
 
  inline base_list() { clear(); }
 
154
  inline void empty() { elements=0; first= &end_of_list; last=&first;}
 
155
  inline base_list() { empty(); }
116
156
  /**
117
157
    This is a shallow copy constructor that implicitly passes the ownership
118
158
    from the source list to the new instance. The old instance is not
122
162
    relies on this behaviour. This logic is quite tricky: please do not use
123
163
    it in any new code.
124
164
  */
125
 
  inline base_list(const base_list &tmp) :memory::SqlAlloc()
 
165
  inline base_list(const base_list &tmp) :Sql_alloc()
126
166
  {
127
167
    elements= tmp.elements;
128
168
    first= tmp.first;
129
169
    last= elements ? tmp.last : &first;
130
170
  }
131
 
  inline base_list(bool) { }
 
171
  /**
 
172
    Construct a deep copy of the argument in memory root mem_root.
 
173
    The elements themselves are copied by pointer. If you also
 
174
    need to copy elements by value, you should employ
 
175
    list_copy_and_replace_each_value after creating a copy.
 
176
  */
 
177
  base_list(const base_list &rhs, MEM_ROOT *mem_root);
 
178
  inline base_list(bool error __attribute__((unused))) { }
132
179
  inline bool push_back(void *info)
133
180
  {
134
181
    if (((*last)=new list_node(info, &end_of_list)))
139
186
    }
140
187
    return 1;
141
188
  }
142
 
  inline bool push_back(void *info, memory::Root *mem_root)
 
189
  inline bool push_back(void *info, MEM_ROOT *mem_root)
143
190
  {
144
191
    if (((*last)=new (mem_root) list_node(info, &end_of_list)))
145
192
    {
230
277
  inline bool is_empty() { return first == &end_of_list ; }
231
278
  inline list_node *last_ref() { return &end_of_list; }
232
279
  friend class base_list_iterator;
 
280
  friend class error_list;
 
281
  friend class error_list_iterator;
233
282
 
234
283
#ifdef LIST_EXTRA_DEBUG
235
284
  /*
242
291
      check_list()
243
292
        name  Name to print to trace file
244
293
 
245
 
    RETURN
 
294
    RETURN 
246
295
      1  The list is Ok.
247
296
      0  List invariants are not met.
248
297
  */
291
340
protected:
292
341
  base_list *list;
293
342
  list_node **el,**prev,*current;
294
 
public:
295
343
  void sublist(base_list &ls, uint32_t elm)
296
344
  {
297
345
    ls.first= *el;
298
346
    ls.last= list->last;
299
347
    ls.elements= elm;
300
348
  }
301
 
  base_list_iterator()
 
349
public:
 
350
  base_list_iterator() 
302
351
    :list(0), el(0), prev(0), current(0)
303
352
  {}
304
353
 
305
 
  base_list_iterator(base_list &list_par, list_node** el0)
306
 
    :list(&list_par), el(el0), prev(0), current(0)
 
354
  base_list_iterator(base_list &list_par) 
 
355
  { init(list_par); }
 
356
 
 
357
  inline void init(base_list &list_par)
307
358
  {
 
359
    list= &list_par;
 
360
    el= &list_par.first;
 
361
    prev= 0;
 
362
    current= 0;
308
363
  }
309
364
 
310
365
  inline void *next(void)
314
369
    el= &current->next;
315
370
    return current->info;
316
371
  }
 
372
  inline void *next_fast(void)
 
373
  {
 
374
    list_node *tmp;
 
375
    tmp= *el;
 
376
    el= &tmp->next;
 
377
    return tmp->info;
 
378
  }
 
379
  inline void rewind(void)
 
380
  {
 
381
    el= &list->first;
 
382
  }
317
383
  inline void *replace(void *element)
318
384
  {                                             // Return old element
319
385
    void *tmp=current->info;
355
421
  {
356
422
    return el == &list->last_ref()->next;
357
423
  }
 
424
  friend class error_list_iterator;
358
425
};
359
426
 
360
 
template <class T> class List_iterator;
361
 
 
362
427
template <class T> class List :public base_list
363
428
{
364
429
public:
365
 
  typedef List_iterator<T> iterator;
366
 
 
367
 
  friend class List_iterator<T>;
368
 
 
369
430
  inline List() :base_list() {}
370
431
  inline List(const List<T> &tmp) :base_list(tmp) {}
371
 
  inline List(const List<T> &tmp, memory::Root *mem_root) :
 
432
  inline List(const List<T> &tmp, MEM_ROOT *mem_root) :
372
433
    base_list(tmp, mem_root) {}
373
434
  inline bool push_back(T *a) { return base_list::push_back(a); }
374
 
  inline bool push_back(T *a, memory::Root *mem_root)
 
435
  inline bool push_back(T *a, MEM_ROOT *mem_root)
375
436
  { return base_list::push_back(a, mem_root); }
376
437
  inline bool push_front(T *a) { return base_list::push_front(a); }
377
 
  inline T* head() {return static_cast<T*>(base_list::head()); }
378
 
  inline T* pop()  {return static_cast<T*>(base_list::pop()); }
 
438
  inline T* head() {return (T*) base_list::head(); }
 
439
  inline T** head_ref() {return (T**) base_list::head_ref(); }
 
440
  inline T* pop()  {return (T*) base_list::pop(); }
379
441
  inline void concat(List<T> *list) { base_list::concat(list); }
380
442
  inline void disjoin(List<T> *list) { base_list::disjoin(list); }
381
443
  inline void prepand(List<T> *list) { base_list::prepand(list); }
387
449
      next=element->next;
388
450
      delete (T*) element->info;
389
451
    }
390
 
    clear();
391
 
  }
392
 
 
393
 
  iterator begin()
394
 
  {
395
 
    return iterator(*this, &first);
 
452
    empty();
396
453
  }
397
454
};
398
455
 
400
457
template <class T> class List_iterator :public base_list_iterator
401
458
{
402
459
public:
403
 
  List_iterator(List<T>& a, list_node** b) : base_list_iterator(a, b) {};
404
 
  List_iterator() {};
 
460
  List_iterator(List<T> &a) : base_list_iterator(a) {}
 
461
  List_iterator() : base_list_iterator() {}
 
462
  inline void init(List<T> &a) { base_list_iterator::init(a); }
405
463
  inline T* operator++(int) { return (T*) base_list_iterator::next(); }
406
464
  inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
407
465
  inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
 
466
  inline void rewind(void)  { base_list_iterator::rewind(); }
 
467
  inline void remove()      { base_list_iterator::remove(); }
 
468
  inline void after(T *a)   { base_list_iterator::after(a); }
408
469
  inline T** ref(void)      { return (T**) base_list_iterator::ref(); }
409
470
};
410
471
 
 
472
 
 
473
template <class T> class List_iterator_fast :public base_list_iterator
 
474
{
 
475
protected:
 
476
  inline T *replace(T *a __attribute__((unused)))   { return (T*) 0; }
 
477
  inline T *replace(List<T> &a __attribute__((unused))) { return (T*) 0; }
 
478
  inline void remove(void)  { }
 
479
  inline void after(T *a __attribute__((unused)))   { }
 
480
  inline T** ref(void)      { return (T**) 0; }
 
481
 
 
482
public:
 
483
  inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
 
484
  inline List_iterator_fast() : base_list_iterator() {}
 
485
  inline void init(List<T> &a) { base_list_iterator::init(a); }
 
486
  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
 
487
  inline void rewind(void)  { base_list_iterator::rewind(); }
 
488
  void sublist(List<T> &list_arg, uint32_t el_arg)
 
489
  {
 
490
    base_list_iterator::sublist(list_arg, el_arg);
 
491
  }
 
492
};
 
493
 
 
494
 
 
495
/*
 
496
  A simple intrusive list which automaticly removes element from list
 
497
  on delete (for THD element)
 
498
*/
 
499
 
 
500
struct ilink
 
501
{
 
502
  struct ilink **prev,*next;
 
503
  static void *operator new(size_t size)
 
504
  {
 
505
    return (void*)my_malloc((uint)size, MYF(MY_WME | MY_FAE | ME_FATALERROR));
 
506
  }
 
507
  static void operator delete(void* ptr_arg,
 
508
                              size_t size __attribute__((unused)))
 
509
  {
 
510
     free((unsigned char*)ptr_arg);
 
511
  }
 
512
 
 
513
  inline ilink()
 
514
  {
 
515
    prev=0; next=0;
 
516
  }
 
517
  inline void unlink()
 
518
  {
 
519
    /* Extra tests because element doesn't have to be linked */
 
520
    if (prev) *prev= next;
 
521
    if (next) next->prev=prev;
 
522
    prev=0 ; next=0;
 
523
  }
 
524
  virtual ~ilink() { unlink(); }                /*lint -e1740 */
 
525
};
 
526
 
 
527
 
 
528
/* Needed to be able to have an I_List of char* strings in mysqld.cc. */
 
529
 
 
530
class i_string: public ilink
 
531
{
 
532
public:
 
533
  const char* ptr;
 
534
  i_string():ptr(0) { }
 
535
  i_string(const char* s) : ptr(s) {}
 
536
};
 
537
 
 
538
/* needed for linked list of two strings for replicate-rewrite-db */
 
539
class i_string_pair: public ilink
 
540
{
 
541
public:
 
542
  const char* key;
 
543
  const char* val;
 
544
  i_string_pair():key(0),val(0) { }
 
545
  i_string_pair(const char* key_arg, const char* val_arg) : 
 
546
    key(key_arg),val(val_arg) {}
 
547
};
 
548
 
 
549
 
 
550
template <class T> class I_List_iterator;
 
551
 
 
552
/*
 
553
  WARNING: copy constructor of this class does not create a usable
 
554
  copy, as its members may point at each other.
 
555
*/
 
556
 
 
557
class base_ilist
 
558
{
 
559
public:
 
560
  struct ilink *first,last;
 
561
  inline void empty() { first= &last; last.prev= &first; }
 
562
  base_ilist() { empty(); }
 
563
  inline bool is_empty() {  return first == &last; }
 
564
  inline void append(ilink *a)
 
565
  {
 
566
    first->prev= &a->next;
 
567
    a->next=first; a->prev= &first; first=a;
 
568
  }
 
569
  inline void push_back(ilink *a)
 
570
  {
 
571
    *last.prev= a;
 
572
    a->next= &last;
 
573
    a->prev= last.prev;
 
574
    last.prev= &a->next;
 
575
  }
 
576
  inline struct ilink *get()
 
577
  {
 
578
    struct ilink *first_link=first;
 
579
    if (first_link == &last)
 
580
      return 0;
 
581
    first_link->unlink();                       // Unlink from list
 
582
    return first_link;
 
583
  }
 
584
  inline struct ilink *head()
 
585
  {
 
586
    return (first != &last) ? first : 0;
 
587
  }
 
588
  friend class base_list_iterator;
 
589
};
 
590
 
 
591
 
 
592
class base_ilist_iterator
 
593
{
 
594
  base_ilist *list;
 
595
  struct ilink **el,*current;
 
596
public:
 
597
  base_ilist_iterator(base_ilist &list_par) :list(&list_par),
 
598
    el(&list_par.first),current(0) {}
 
599
  void *next(void)
 
600
  {
 
601
    /* This is coded to allow push_back() while iterating */
 
602
    current= *el;
 
603
    if (current == &list->last) return 0;
 
604
    el= &current->next;
 
605
    return current;
 
606
  }
 
607
};
 
608
 
 
609
 
 
610
template <class T>
 
611
class I_List :private base_ilist
 
612
{
 
613
public:
 
614
  I_List() :base_ilist()        {}
 
615
  inline void empty()           { base_ilist::empty(); }
 
616
  inline bool is_empty()        { return base_ilist::is_empty(); } 
 
617
  inline void append(T* a)      { base_ilist::append(a); }
 
618
  inline void push_back(T* a)   { base_ilist::push_back(a); }
 
619
  inline T* get()               { return (T*) base_ilist::get(); }
 
620
  inline T* head()              { return (T*) base_ilist::head(); }
 
621
#ifndef _lint
 
622
  friend class I_List_iterator<T>;
 
623
#endif
 
624
};
 
625
 
 
626
 
 
627
template <class T> class I_List_iterator :public base_ilist_iterator
 
628
{
 
629
public:
 
630
  I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
 
631
  inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
 
632
};
 
633
 
411
634
/**
412
635
  Make a deep copy of each list element.
413
636
 
419
642
  Evidently not all template arguments have clone() method with
420
643
  the right signature.
421
644
 
422
 
  @return You must query the error state in Session for out-of-memory
 
645
  @return You must query the error state in THD for out-of-memory
423
646
  situation after calling this function.
424
647
*/
425
648
 
426
649
template <typename T>
427
 
void list_copy_and_replace_each_value(List<T> &list, memory::Root *mem_root)
 
650
inline
 
651
void
 
652
list_copy_and_replace_each_value(List<T> &list, MEM_ROOT *mem_root)
428
653
{
429
654
  /* Make a deep copy of each element */
430
 
  typename List<T>::iterator it(list.begin());
 
655
  List_iterator<T> it(list);
431
656
  T *el;
432
657
  while ((el= it++))
433
658
    it.replace(el->clone(mem_root));
434
659
}
435
660
 
436
 
} /* namespace drizzled */
437
 
 
438
 
#endif /* DRIZZLED_SQL_LIST_H */
 
661
#endif // INCLUDES_DRIZZLE_SQL_LIST_H