sql_list.h 12.3 KB
Newer Older
monty@narttu.mysql.fi's avatar
monty@narttu.mysql.fi committed
1
/* Copyright (C) 2000-2003 MySQL AB
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
2

bk@work.mysql.com's avatar
bk@work.mysql.com committed
3 4 5 6
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
7

bk@work.mysql.com's avatar
bk@work.mysql.com committed
8 9 10 11
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
12

bk@work.mysql.com's avatar
bk@work.mysql.com committed
13 14 15 16 17
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


18
#ifdef USE_PRAGMA_INTERFACE
bk@work.mysql.com's avatar
bk@work.mysql.com committed
19 20 21
#pragma interface			/* gcc class implementation */
#endif

22
/* mysql standard class memory allocator */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
23 24 25 26

class Sql_alloc
{
public:
27 28 29 30 31 32 33 34
  static void *operator new(size_t size)
  {
    return (void*) sql_alloc((uint) size);
  }
  static void *operator new[](size_t size)
  {
    return (void*) sql_alloc((uint) size);
  }
35 36
  static void *operator new(size_t size, MEM_ROOT *mem_root)
  { return (void*) alloc_root(mem_root, (uint) size); }
37
  static void operator delete(void *ptr, size_t size) { TRASH(ptr, size); }
38 39
  static void operator delete(void *ptr, MEM_ROOT *mem_root)
  { /* never called */ }
40
  static void operator delete[](void *ptr, size_t size) { TRASH(ptr, size); }
41 42 43 44 45 46 47 48 49
#ifdef HAVE_purify
  bool dummy;
  inline Sql_alloc() :dummy(0) {}
  inline ~Sql_alloc() {}
#else
  inline Sql_alloc() {}
  inline ~Sql_alloc() {}
#endif

bk@work.mysql.com's avatar
bk@work.mysql.com committed
50 51
};

52

bk@work.mysql.com's avatar
bk@work.mysql.com committed
53
/*
54 55 56 57 58 59 60
  Basic single linked list
  Used for item and item_buffs.
  All list ends with a pointer to the 'end_of_list' element, which
  data pointer is a null pointer and the next pointer points to itself.
  This makes it very fast to traverse lists as we don't have to
  test for a specialend condition for list that can't contain a null
  pointer.
bk@work.mysql.com's avatar
bk@work.mysql.com committed
61 62
*/

monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
class list_node :public Sql_alloc
{
public:
  list_node *next;
  void *info;
  list_node(void *info_par,list_node *next_par)
    :next(next_par),info(info_par)
    {}
  list_node()					/* For end_of_list */
    {
      info=0;
      next= this;
    }
  friend class base_list;
  friend class base_list_iterator;
};

80

monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
81 82
extern list_node end_of_list;

83 84
class base_list :public Sql_alloc
{
bk@work.mysql.com's avatar
bk@work.mysql.com committed
85 86 87 88 89 90
protected:
  list_node *first,**last;

public:
  uint elements;

monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
91
  inline void empty() { elements=0; first= &end_of_list; last=&first;}
bk@work.mysql.com's avatar
bk@work.mysql.com committed
92 93 94 95 96 97 98
  inline base_list() { empty(); }
  inline base_list(const base_list &tmp) :Sql_alloc()
  {
    elements=tmp.elements;
    first=tmp.first;
    last=tmp.last;
  }
venu@myvenu.com's avatar
venu@myvenu.com committed
99
  inline base_list(bool error) { }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
100 101
  inline bool push_back(void *info)
  {
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
102
    if (((*last)=new list_node(info, &end_of_list)))
bk@work.mysql.com's avatar
bk@work.mysql.com committed
103 104 105 106 107 108 109
    {
      last= &(*last)->next;
      elements++;
      return 0;
    }
    return 1;
  }
monty@mysql.com's avatar
monty@mysql.com committed
110 111 112 113 114 115 116 117 118 119
  inline bool push_back(void *info, MEM_ROOT *mem_root)
  {
    if (((*last)=new (mem_root) list_node(info, &end_of_list)))
    {
      last= &(*last)->next;
      elements++;
      return 0;
    }
    return 1;
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
120 121 122 123 124
  inline bool push_front(void *info)
  {
    list_node *node=new list_node(info,first);
    if (node)
    {
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
125
      if (last == &first)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
126 127 128 129 130 131 132 133 134 135 136 137
	last= &node->next;
      first=node;
      elements++;
      return 0;
    }
    return 1;
  }
  void remove(list_node **prev)
  {
    list_node *node=(*prev)->next;
    if (!--elements)
      last= &first;
138 139 140 141
    else if (last == &(*prev)->next)
      last= prev;
    delete *prev;
    *prev=node;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
142
  }
143 144 145 146 147 148 149 150 151
  inline void concat(base_list *list)
  {
    if (!list->is_empty())
    {
      *last= list->first;
      last= list->last;
      elements+= list->elements;
    }
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
152 153
  inline void *pop(void)
  {
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
154
    if (first == &end_of_list) return 0;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
155 156 157 158 159 160
    list_node *tmp=first;
    first=first->next;
    if (!--elements)
      last= &first;
    return tmp->info;
  }
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
  inline void disjoin(base_list *list)
  {
    list_node **prev= &first;
    list_node *node= first;
    list_node *list_first= list->first;
    elements=0;
    while (node && node != list_first)
    {
      prev= &node->next;
      node= node->next;
      elements++;
    }
    *prev= *last;
    last= prev;
  }
igor@rurik.mysql.com's avatar
igor@rurik.mysql.com committed
176 177 178 179 180 181 182 183
  inline void prepand(base_list *list)
  {
    if (!list->is_empty())
    {
      *list->last= first;
      first= list->first;
      elements+= list->elements;
    }
184
  }
185 186
  inline list_node* last_node() { return *last; }
  inline list_node* first_node() { return first;}
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
187 188 189 190
  inline void *head() { return first->info; }
  inline void **head_ref() { return first != &end_of_list ? &first->info : 0; }
  inline bool is_empty() { return first == &end_of_list ; }
  inline list_node *last_ref() { return &end_of_list; }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
191
  friend class base_list_iterator;
192
  friend class error_list;
venu@myvenu.com's avatar
venu@myvenu.com committed
193
  friend class error_list_iterator;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
194

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242
#ifdef LIST_EXTRA_DEBUG
  /*
    Check list invariants and print results into trace. Invariants are:
      - (*last) points to end_of_list
      - There are no NULLs in the list.
      - base_list::elements is the number of elements in the list.

    SYNOPSIS
      check_list()
        name  Name to print to trace file

    RETURN 
      1  The list is Ok.
      0  List invariants are not met.
  */

  bool check_list(const char *name)
  {
    base_list *list= this;
    list_node *node= first;
    uint cnt= 0;

    while (node->next != &end_of_list)
    {
      if (!node->info)
      {
        DBUG_PRINT("list_invariants",("%s: error: NULL element in the list", 
                                      name));
        return FALSE;
      }
      node= node->next;
      cnt++;
    }
    if (last != &(node->next))
    {
      DBUG_PRINT("list_invariants", ("%s: error: wrong last pointer", name));
      return FALSE;
    }
    if (cnt+1 != elements)
    {
      DBUG_PRINT("list_invariants", ("%s: error: wrong element count", name));
      return FALSE;
    }
    DBUG_PRINT("list_invariants", ("%s: list is ok", name));
    return TRUE;
  }
#endif // LIST_EXTRA_DEBUG

bk@work.mysql.com's avatar
bk@work.mysql.com committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256
protected:
  void after(void *info,list_node *node)
  {
    list_node *new_node=new list_node(info,node->next);
    node->next=new_node;
    elements++;
    if (last == &(node->next))
      last= &new_node->next;
  }
};


class base_list_iterator
{
257
protected:
bk@work.mysql.com's avatar
bk@work.mysql.com committed
258
  base_list *list;
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
259
  list_node **el,**prev,*current;
260 261 262 263 264 265
  void sublist(base_list &ls, uint elm)
  {
    ls.first= *el;
    ls.last= list->last;
    ls.elements= elm;
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
266
public:
267 268
  base_list_iterator(base_list &list_par) 
    :list(&list_par), el(&list_par.first), prev(0), current(0)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
269
  {}
270

bk@work.mysql.com's avatar
bk@work.mysql.com committed
271 272 273
  inline void *next(void)
  {
    prev=el;
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
274
    current= *el;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
275 276 277
    el= &current->next;
    return current->info;
  }
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
278 279 280 281 282 283 284
  inline void *next_fast(void)
  {
    list_node *tmp;
    tmp= *el;
    el= &tmp->next;
    return tmp->info;
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
285 286 287 288
  inline void rewind(void)
  {
    el= &list->first;
  }
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
289
  inline void *replace(void *element)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
290 291
  {						// Return old element
    void *tmp=current->info;
292
    DBUG_ASSERT(current->info != 0);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
293 294 295 296 297 298
    current->info=element;
    return tmp;
  }
  void *replace(base_list &new_list)
  {
    void *ret_value=current->info;
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
299
    if (!new_list.is_empty())
bk@work.mysql.com's avatar
bk@work.mysql.com committed
300 301 302 303
    {
      *new_list.last=current->next;
      current->info=new_list.first->info;
      current->next=new_list.first->next;
hf@deer.mysql.r18.ru's avatar
hf@deer.mysql.r18.ru committed
304 305
      if ((list->last == &current->next) && (new_list.elements > 1))
	list->last= new_list.last;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327
      list->elements+=new_list.elements-1;
    }
    return ret_value;				// return old element
  }
  inline void remove(void)			// Remove current
  {
    list->remove(prev);
    el=prev;
    current=0;					// Safeguard
  }
  void after(void *element)			// Insert element after current
  {
    list->after(element,current);
    current=current->next;
    el= &current->next;
  }
  inline void **ref(void)			// Get reference pointer
  {
    return &current->info;
  }
  inline bool is_last(void)
  {
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
328
    return el == &list->last_ref()->next;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
329
  }
330
  friend class error_list_iterator;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
331 332 333 334 335 336 337 338
};

template <class T> class List :public base_list
{
public:
  inline List() :base_list() {}
  inline List(const List<T> &tmp) :base_list(tmp) {}
  inline bool push_back(T *a) { return base_list::push_back(a); }
monty@mysql.com's avatar
monty@mysql.com committed
339 340
  inline bool push_back(T *a, MEM_ROOT *mem_root)
  { return base_list::push_back(a, mem_root); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
341 342 343 344
  inline bool push_front(T *a) { return base_list::push_front(a); }
  inline T* head() {return (T*) base_list::head(); }
  inline T** head_ref() {return (T**) base_list::head_ref(); }
  inline T* pop()  {return (T*) base_list::pop(); }
igor@rurik.mysql.com's avatar
igor@rurik.mysql.com committed
345 346
  inline void concat(List<T> *list) { base_list::concat(list); }
  inline void disjoin(List<T> *list) { base_list::disjoin(list); }
igor@rurik.mysql.com's avatar
igor@rurik.mysql.com committed
347
  inline void prepand(List<T> *list) { base_list::prepand(list); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
348 349 350
  void delete_elements(void)
  {
    list_node *element,*next;
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
351
    for (element=first; element != &end_of_list; element=next)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
    {
      next=element->next;
      delete (T*) element->info;
    }
    empty();
  }
};


template <class T> class List_iterator :public base_list_iterator
{
public:
  List_iterator(List<T> &a) : base_list_iterator(a) {}
  inline T* operator++(int) { return (T*) base_list_iterator::next(); }
  inline T *replace(T *a)   { return (T*) base_list_iterator::replace(a); }
  inline T *replace(List<T> &a) { return (T*) base_list_iterator::replace(a); }
368 369
  inline void rewind(void)  { base_list_iterator::rewind(); }
  inline void remove()      { base_list_iterator::remove(); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
370 371
  inline void after(T *a)   { base_list_iterator::after(a); }
  inline T** ref(void)	    { return (T**) base_list_iterator::ref(); }
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
372 373
};

374

monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
375 376 377 378 379 380 381 382 383 384
template <class T> class List_iterator_fast :public base_list_iterator
{
protected:
  inline T *replace(T *a)   { return (T*) 0; }
  inline T *replace(List<T> &a) { return (T*) 0; }
  inline void remove(void)  { }
  inline void after(T *a)   { }
  inline T** ref(void)	    { return (T**) 0; }

public:
serg@serg.mylan's avatar
serg@serg.mylan committed
385
  inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
monty@tik.mysql.fi's avatar
monty@tik.mysql.fi committed
386 387
  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
  inline void rewind(void)  { base_list_iterator::rewind(); }
388
  void sublist(List<T> &list_arg, uint el_arg)
389
  {
390
    base_list_iterator::sublist(list_arg, el_arg);
391
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
392 393 394 395
};


/*
396 397
  A simple intrusive list which automaticly removes element from list
  on delete (for THD element)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
398 399
*/

400 401
struct ilink
{
bk@work.mysql.com's avatar
bk@work.mysql.com committed
402
  struct ilink **prev,*next;
sasha@mysql.sashanet.com's avatar
sasha@mysql.sashanet.com committed
403 404 405 406 407 408 409 410 411
  static void *operator new(size_t size)
  {
    return (void*)my_malloc((uint)size, MYF(MY_WME | MY_FAE));
  }
  static void operator delete(void* ptr_arg, size_t size)
  {
     my_free((gptr)ptr_arg, MYF(MY_WME|MY_ALLOW_ZERO_PTR));
  }

bk@work.mysql.com's avatar
bk@work.mysql.com committed
412 413 414 415 416 417 418 419 420 421 422 423 424 425
  inline ilink()
  {
    prev=0; next=0;
  }
  inline void unlink()
  {
    /* Extra tests because element doesn't have to be linked */
    if (prev) *prev= next;
    if (next) next->prev=prev;
    prev=0 ; next=0;
  }
  virtual ~ilink() { unlink(); }		/*lint -e1740 */
};

426

bk@work.mysql.com's avatar
bk@work.mysql.com committed
427 428
template <class T> class I_List_iterator;

429 430
class base_ilist
{
bk@work.mysql.com's avatar
bk@work.mysql.com committed
431 432
  public:
  struct ilink *first,last;
433 434
  inline void empty() { first= &last; last.prev= &first; }
  base_ilist() { empty(); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455
  inline bool is_empty() {  return first == &last; }
  inline void append(ilink *a)
  {
    first->prev= &a->next;
    a->next=first; a->prev= &first; first=a;
  }
  inline void push_back(ilink *a)
  {
    *last.prev= a;
    a->next= &last;
    a->prev= last.prev;
    last.prev= &a->next;
  }
  inline struct ilink *get()
  {
    struct ilink *first_link=first;
    if (first_link == &last)
      return 0;
    first_link->unlink();			// Unlink from list
    return first_link;
  }
456 457 458 459
  inline struct ilink *head()
  {
    return (first != &last) ? first : 0;
  }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482
  friend class base_list_iterator;
};


class base_ilist_iterator
{
  base_ilist *list;
  struct ilink **el,*current;
public:
  base_ilist_iterator(base_ilist &list_par) :list(&list_par),
    el(&list_par.first),current(0) {}
  void *next(void)
  {
    /* This is coded to allow push_back() while iterating */
    current= *el;
    if (current == &list->last) return 0;
    el= &current->next;
    return current;
  }
};


template <class T>
483 484
class I_List :private base_ilist
{
bk@work.mysql.com's avatar
bk@work.mysql.com committed
485 486
public:
  I_List() :base_ilist()	{}
monty@mashka.mysql.fi's avatar
monty@mashka.mysql.fi committed
487
  inline void empty()		{ base_ilist::empty(); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
488 489 490 491
  inline bool is_empty()        { return base_ilist::is_empty(); } 
  inline void append(T* a)	{ base_ilist::append(a); }
  inline void push_back(T* a)	{ base_ilist::push_back(a); }
  inline T* get()		{ return (T*) base_ilist::get(); }
492
  inline T* head()		{ return (T*) base_ilist::head(); }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
493 494 495 496 497 498 499 500 501 502 503 504
#ifndef _lint
  friend class I_List_iterator<T>;
#endif
};


template <class T> class I_List_iterator :public base_ilist_iterator
{
public:
  I_List_iterator(I_List<T> &a) : base_ilist_iterator(a) {}
  inline T* operator++(int) { return (T*) base_ilist_iterator::next(); }
};