sql_list.h 13.5 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000-2003 MySQL AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4
   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
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
6

unknown's avatar
unknown committed
7 8 9 10
   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.
unknown's avatar
unknown committed
11

unknown's avatar
unknown committed
12 13 14 15 16
   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 */


17
#ifdef USE_PRAGMA_INTERFACE
unknown's avatar
unknown committed
18 19 20
#pragma interface			/* gcc class implementation */
#endif

21
/* mysql standard class memory allocator */
unknown's avatar
unknown committed
22 23 24 25

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

unknown's avatar
unknown committed
53 54
};

55

unknown's avatar
unknown committed
56
/*
57 58 59 60 61 62 63
  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.
unknown's avatar
unknown committed
64 65
*/

unknown's avatar
unknown committed
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
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;
};

83

unknown's avatar
unknown committed
84 85
extern list_node end_of_list;

86 87
class base_list :public Sql_alloc
{
unknown's avatar
unknown committed
88 89 90 91 92 93
protected:
  list_node *first,**last;

public:
  uint elements;

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

unknown's avatar
unknown committed
246 247 248 249 250 251 252 253 254 255 256 257 258 259
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
{
260
protected:
unknown's avatar
unknown committed
261
  base_list *list;
unknown's avatar
unknown committed
262
  list_node **el,**prev,*current;
263 264 265 266 267 268
  void sublist(base_list &ls, uint elm)
  {
    ls.first= *el;
    ls.last= list->last;
    ls.elements= elm;
  }
unknown's avatar
unknown committed
269
public:
270 271
  base_list_iterator() 
    :list(0), el(0), prev(0), current(0)
unknown's avatar
unknown committed
272
  {}
273

274 275 276 277 278 279 280 281 282 283 284
  base_list_iterator(base_list &list_par) 
  { init(list_par); }

  inline void init(base_list &list_par)
  {
    list= &list_par;
    el= &list_par.first;
    prev= 0;
    current= 0;
  }

unknown's avatar
unknown committed
285 286 287
  inline void *next(void)
  {
    prev=el;
unknown's avatar
unknown committed
288
    current= *el;
unknown's avatar
unknown committed
289 290 291
    el= &current->next;
    return current->info;
  }
unknown's avatar
unknown committed
292 293 294 295 296 297 298
  inline void *next_fast(void)
  {
    list_node *tmp;
    tmp= *el;
    el= &tmp->next;
    return tmp->info;
  }
unknown's avatar
unknown committed
299 300 301 302
  inline void rewind(void)
  {
    el= &list->first;
  }
unknown's avatar
unknown committed
303
  inline void *replace(void *element)
unknown's avatar
unknown committed
304 305
  {						// Return old element
    void *tmp=current->info;
306
    DBUG_ASSERT(current->info != 0);
unknown's avatar
unknown committed
307 308 309 310 311 312
    current->info=element;
    return tmp;
  }
  void *replace(base_list &new_list)
  {
    void *ret_value=current->info;
unknown's avatar
unknown committed
313
    if (!new_list.is_empty())
unknown's avatar
unknown committed
314 315 316 317
    {
      *new_list.last=current->next;
      current->info=new_list.first->info;
      current->next=new_list.first->next;
unknown's avatar
unknown committed
318 319
      if ((list->last == &current->next) && (new_list.elements > 1))
	list->last= new_list.last;
unknown's avatar
unknown committed
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
      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)
  {
unknown's avatar
unknown committed
342
    return el == &list->last_ref()->next;
unknown's avatar
unknown committed
343
  }
unknown's avatar
unknown committed
344
  friend class error_list_iterator;
unknown's avatar
unknown committed
345 346 347 348 349 350 351 352
};

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); }
unknown's avatar
unknown committed
353 354
  inline bool push_back(T *a, MEM_ROOT *mem_root)
  { return base_list::push_back(a, mem_root); }
unknown's avatar
unknown committed
355 356 357 358
  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(); }
unknown's avatar
unknown committed
359 360
  inline void concat(List<T> *list) { base_list::concat(list); }
  inline void disjoin(List<T> *list) { base_list::disjoin(list); }
unknown's avatar
unknown committed
361
  inline void prepand(List<T> *list) { base_list::prepand(list); }
unknown's avatar
unknown committed
362 363 364
  void delete_elements(void)
  {
    list_node *element,*next;
unknown's avatar
unknown committed
365
    for (element=first; element != &end_of_list; element=next)
unknown's avatar
unknown committed
366 367 368 369 370 371 372 373 374 375 376 377 378
    {
      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) {}
379 380
  List_iterator() : base_list_iterator() {}
  inline void init(List<T> &a) { base_list_iterator::init(a); }
unknown's avatar
unknown committed
381 382 383
  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); }
384 385
  inline void rewind(void)  { base_list_iterator::rewind(); }
  inline void remove()      { base_list_iterator::remove(); }
unknown's avatar
unknown committed
386 387
  inline void after(T *a)   { base_list_iterator::after(a); }
  inline T** ref(void)	    { return (T**) base_list_iterator::ref(); }
unknown's avatar
unknown committed
388 389
};

390

unknown's avatar
unknown committed
391 392 393 394 395 396 397 398 399 400
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:
unknown's avatar
unknown committed
401
  inline List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
402 403
  inline List_iterator_fast() : base_list_iterator() {}
  inline void init(List<T> &a) { base_list_iterator::init(a); }
unknown's avatar
unknown committed
404 405
  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
  inline void rewind(void)  { base_list_iterator::rewind(); }
406
  void sublist(List<T> &list_arg, uint el_arg)
407
  {
408
    base_list_iterator::sublist(list_arg, el_arg);
409
  }
unknown's avatar
unknown committed
410 411 412 413
};


/*
414 415
  A simple intrusive list which automaticly removes element from list
  on delete (for THD element)
unknown's avatar
unknown committed
416 417
*/

418 419
struct ilink
{
unknown's avatar
unknown committed
420
  struct ilink **prev,*next;
unknown's avatar
unknown committed
421 422 423 424 425 426 427 428 429
  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));
  }

unknown's avatar
unknown committed
430 431 432 433 434 435 436 437 438 439 440 441 442 443
  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 */
};

444

445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
/* Needed to be able to have an I_List of char* strings in mysqld.cc. */

class i_string: public ilink
{
public:
  const char* ptr;
  i_string():ptr(0) { }
  i_string(const char* s) : ptr(s) {}
};

/* needed for linked list of two strings for replicate-rewrite-db */
class i_string_pair: public ilink
{
public:
  const char* key;
  const char* val;
  i_string_pair():key(0),val(0) { }
  i_string_pair(const char* key_arg, const char* val_arg) : 
    key(key_arg),val(val_arg) {}
};


unknown's avatar
unknown committed
467 468
template <class T> class I_List_iterator;

469 470 471 472 473
/*
  WARNING: copy constructor of this class does not create a usable
  copy, as its members may point at each other.
*/

474 475
class base_ilist
{
476
public:
unknown's avatar
unknown committed
477
  struct ilink *first,last;
unknown's avatar
unknown committed
478 479
  inline void empty() { first= &last; last.prev= &first; }
  base_ilist() { empty(); }
unknown's avatar
unknown committed
480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500
  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;
  }
501 502 503 504
  inline struct ilink *head()
  {
    return (first != &last) ? first : 0;
  }
unknown's avatar
unknown committed
505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527
  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>
528 529
class I_List :private base_ilist
{
unknown's avatar
unknown committed
530 531
public:
  I_List() :base_ilist()	{}
unknown's avatar
unknown committed
532
  inline void empty()		{ base_ilist::empty(); }
unknown's avatar
unknown committed
533 534 535 536
  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(); }
537
  inline T* head()		{ return (T*) base_ilist::head(); }
unknown's avatar
unknown committed
538 539 540 541 542 543 544 545 546 547 548 549
#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(); }
};