sql_list.h 9.11 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown 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.
unknown's avatar
unknown committed
7

unknown's avatar
unknown 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.
unknown's avatar
unknown committed
12

unknown's avatar
unknown committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
   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 */


/* mysql standard open memoryallocator */

#ifdef __GNUC__
#pragma interface			/* gcc class implementation */
#endif


class Sql_alloc
{
public:
unknown's avatar
unknown committed
28 29 30 31 32 33 34 35
  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);
  }
unknown's avatar
unknown committed
36
  static void operator delete(void *ptr, size_t size) {} /*lint -e715 */
unknown's avatar
unknown committed
37
  static void operator delete[](void *ptr, size_t size) {}
38 39 40 41 42 43 44 45 46
#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
47 48 49 50 51
};

/*
** basic single linked list
** Used for item and item_buffs.
unknown's avatar
unknown committed
52 53 54 55 56
** 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
57 58
*/

unknown's avatar
unknown committed
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
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;
};

extern list_node end_of_list;

unknown's avatar
unknown committed
78 79 80 81 82 83 84
class base_list :public Sql_alloc {
protected:
  list_node *first,**last;

public:
  uint elements;

unknown's avatar
unknown committed
85
  inline void empty() { elements=0; first= &end_of_list; last=&first;}
unknown's avatar
unknown committed
86 87 88 89 90 91 92
  inline base_list() { empty(); }
  inline base_list(const base_list &tmp) :Sql_alloc()
  {
    elements=tmp.elements;
    first=tmp.first;
    last=tmp.last;
  }
unknown's avatar
unknown committed
93
  inline base_list(bool error) { }
unknown's avatar
unknown committed
94 95
  inline bool push_back(void *info)
  {
unknown's avatar
unknown committed
96
    if (((*last)=new list_node(info, &end_of_list)))
unknown's avatar
unknown committed
97 98 99 100 101 102 103 104 105 106 107 108
    {
      last= &(*last)->next;
      elements++;
      return 0;
    }
    return 1;
  }
  inline bool push_front(void *info)
  {
    list_node *node=new list_node(info,first);
    if (node)
    {
unknown's avatar
unknown committed
109
      if (last == &first)
unknown's avatar
unknown committed
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
	last= &node->next;
      first=node;
      elements++;
      return 0;
    }
    return 1;
  }
  void remove(list_node **prev)
  {
    list_node *node=(*prev)->next;
    delete *prev;
    *prev=node;
    if (!--elements)
      last= &first;
  }
  inline void *pop(void)
  {
unknown's avatar
unknown committed
127
    if (first == &end_of_list) return 0;
unknown's avatar
unknown committed
128 129 130 131 132 133
    list_node *tmp=first;
    first=first->next;
    if (!--elements)
      last= &first;
    return tmp->info;
  }
unknown's avatar
unknown committed
134 135
  inline list_node* last_node() { return *last; }
  inline list_node* first_node() { return first;}
unknown's avatar
unknown committed
136 137 138 139
  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
140
  friend class base_list_iterator;
unknown's avatar
unknown committed
141
  friend class error_list;
unknown's avatar
unknown committed
142
  friend class error_list_iterator;
unknown's avatar
unknown committed
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158

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
{
  base_list *list;
unknown's avatar
unknown committed
159
  list_node **el,**prev,*current;
unknown's avatar
unknown committed
160 161 162 163 164 165 166
public:
  base_list_iterator(base_list &list_par) :list(&list_par),el(&list_par.first),
    prev(0),current(0)
  {}
  inline void *next(void)
  {
    prev=el;
unknown's avatar
unknown committed
167
    current= *el;
unknown's avatar
unknown committed
168 169 170
    el= &current->next;
    return current->info;
  }
unknown's avatar
unknown committed
171 172 173 174 175 176 177
  inline void *next_fast(void)
  {
    list_node *tmp;
    tmp= *el;
    el= &tmp->next;
    return tmp->info;
  }
unknown's avatar
unknown committed
178 179 180 181
  inline void rewind(void)
  {
    el= &list->first;
  }
unknown's avatar
unknown committed
182
  inline void *replace(void *element)
unknown's avatar
unknown committed
183 184 185 186 187 188 189 190
  {						// Return old element
    void *tmp=current->info;
    current->info=element;
    return tmp;
  }
  void *replace(base_list &new_list)
  {
    void *ret_value=current->info;
unknown's avatar
unknown committed
191
    if (!new_list.is_empty())
unknown's avatar
unknown committed
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
    {
      *new_list.last=current->next;
      current->info=new_list.first->info;
      current->next=new_list.first->next;
      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
218
    return el == &list->last_ref()->next;
unknown's avatar
unknown committed
219
  }
unknown's avatar
unknown committed
220
  friend class error_list_iterator;
unknown's avatar
unknown committed
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
};


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); }
  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(); }
  void delete_elements(void)
  {
    list_node *element,*next;
unknown's avatar
unknown committed
237
    for (element=first; element != &end_of_list; element=next)
unknown's avatar
unknown committed
238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
    {
      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); }
  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
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
};

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:
  List_iterator_fast(List<T> &a) : base_list_iterator(a) {}
  inline T* operator++(int) { return (T*) base_list_iterator::next_fast(); }
  inline void rewind(void)  { base_list_iterator::rewind(); }
unknown's avatar
unknown committed
271 272 273 274
};


/*
unknown's avatar
unknown committed
275
** A simple intrusive list which automaticly removes element from list
unknown's avatar
unknown committed
276 277 278 279 280
** on delete (for THD element)
*/

struct ilink {
  struct ilink **prev,*next;
unknown's avatar
unknown committed
281 282 283 284 285 286 287 288 289
  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
290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
  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 */
};

template <class T> class I_List_iterator;

class base_ilist {
  public:
  struct ilink *first,last;
  base_ilist() { first= &last; last.prev= &first; }
  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;
  }
  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>
class I_List :private base_ilist {
public:
  I_List() :base_ilist()	{}
  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(); }
#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(); }
};