sql_list.h

/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
 *
 *  Copyright (C) 2008 Sun Microsystems, Inc.
 *
 *  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; version 2 of the License.
 *
 *  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.
 *
 *  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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#pragma once

#include <cstdlib>
#include <cassert>
#include <utility>
#include <algorithm>
#include <drizzled/memory/sql_alloc.h>
#include <drizzled/visibility.h>

namespace drizzled {

struct SQL_LIST 
{
  uint32_t elements;
  unsigned char *first;
  unsigned char **next;

  void clear()
  {
    elements=0;
    first=0;
    next= &first;
  }

  size_t size() const
  {
    return elements;
  }

  void link_in_list(unsigned char *element,unsigned char **next_ptr)
  {
    elements++;
    (*next)=element;
    next= next_ptr;
    *next=0;
  }
  void save_and_clear(SQL_LIST *save)
  {
    *save= *this;
    clear();
  }
  void push_front(SQL_LIST *save)
  {
    *save->next= first;       /* link current list last */
    first= save->first;
    elements+= save->elements;
  }
  void push_back(SQL_LIST *save)
  {
    if (save->first)
    {
      *next= save->first;
      next= save->next;
      elements+= save->elements;
    }
  }
};

/*
  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.
*/


struct list_node : public memory::SqlAlloc
{
  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;
  }
};

extern DRIZZLED_API list_node end_of_list;

class base_list :public memory::SqlAlloc
{
protected:
  list_node *first,**last;
  uint32_t elements;
public:

  void clear() { elements=0; first= &end_of_list; last=&first;}
  base_list() { clear(); }
  base_list(const base_list &tmp) :memory::SqlAlloc()
  {
    elements= tmp.elements;
    first= tmp.first;
    last= elements ? tmp.last : &first;
  }
  base_list(bool) { }
  void push_back(void *info)
  {
    *last = new list_node(info, &end_of_list);
    last= &(*last)->next;
    elements++;
  }
  void push_back(void *info, memory::Root& mem)
  {
    *last = new (mem) list_node(info, &end_of_list);
    last= &(*last)->next;
    elements++;
  }
  void push_front(void *info)
  {
    list_node *node=new list_node(info,first);
    if (last == &first)
      last= &node->next;
      first=node;
      elements++;
  }
  void remove(list_node **prev)
  {
    list_node *node=(*prev)->next;
    if (!--elements)
      last= &first;
    else if (last == &(*prev)->next)
      last= prev;
    delete *prev;
    *prev=node;
  }
  void concat(base_list *list)
  {
    if (!list->is_empty())
    {
      *last= list->first;
      last= list->last;
      elements+= list->elements;
    }
  }
  void *pop()
  {
    if (first == &end_of_list) return 0;
    list_node *tmp=first;
    first=first->next;
    if (!--elements)
      last= &first;
    return tmp->info;
  }
  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;
  }
  void prepand(base_list *list)
  {
    if (!list->is_empty())
    {
      *list->last= first;
      first= list->first;
      elements+= list->elements;
    }
  }
  void swap(base_list &rhs)
  {
    std::swap(first, rhs.first);
    std::swap(last, rhs.last);
    std::swap(elements, rhs.elements);
  }
  bool is_empty() { return first == &end_of_list ; }
  friend class base_list_iterator;

#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)
  {
    list_node *node= first;
    uint32_t cnt= 0;

    while (node->next != &end_of_list)
    {
      if (!node->info)
      {
        return false;
      }
      node= node->next;
      cnt++;
    }
    if (last != &(node->next))
    {
      return false;
    }
    if (cnt+1 != elements)
    {
      return false;
    }
    return true;
  }
#endif // LIST_EXTRA_DEBUG

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
{
protected:
  base_list *list;
  list_node **el,**prev,*current;
public:
  void sublist(base_list &ls, uint32_t elm) const
  {
    ls.first= *el;
    ls.last= list->last;
    ls.elements= elm;
  }
  base_list_iterator()
    :list(0), el(0), prev(0), current(0)
  {}

  base_list_iterator(base_list &list_par, list_node** el0)
    :list(&list_par), el(el0), prev(0), current(0)
  {
  }

  void *replace(base_list &new_list)
  {
    void *ret_value=current->info;
    if (!new_list.is_empty())
    {
      *new_list.last=current->next;
      current->info=new_list.first->info;
      current->next=new_list.first->next;
      if (list->last == &current->next && new_list.elements > 1)
        list->last= new_list.last;
      list->elements+=new_list.elements-1;
    }
    return ret_value;       // return old element
  }
  void remove()     // 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;
  }
};

template <class T> class List_iterator;

template <class T> class List : public base_list
{
public:
  typedef List_iterator<T> iterator;

  friend class List_iterator<T>;

  List() {}
  List(const List<T> &tmp) : base_list(tmp) {}
  List(const List<T> &tmp, memory::Root *mem_root) : base_list(tmp, mem_root) {}
  T& front() {return *static_cast<T*>(first->info); }
  T* pop()  {return static_cast<T*>(base_list::pop()); }
  void concat(List<T> *list) { base_list::concat(list); }
  void disjoin(List<T> *list) { base_list::disjoin(list); }
  void prepand(List<T> *list) { base_list::prepand(list); }
  void delete_elements()
  {
    list_node *element,*next;
    for (element=first; element != &end_of_list; element=next)
    {
      next=element->next;
      delete (T*) element->info;
    }
    clear();
  }

  iterator begin()
  {
    return iterator(*this, &first);
  }

  size_t size() const
  {
    return elements;
  }

  void set_size(size_t v)
  {
    elements = v;
  }
};

template <class T> class List_iterator : public base_list_iterator
{
public:
  List_iterator(List<T>& a, list_node** b) : base_list_iterator(a, b) {};
  List_iterator() {};
  T *operator++(int) { prev=el; current= *el; el= &current->next; return (T*)current->info; }
  T *replace(T *a)   { T* old = (T*) current->info; current->info= a; return old; }
  void replace(List<T> &a) { base_list_iterator::replace(a); }
  T** ref() { return (T**) &current->info; }

  T& operator*()
  {
    return *(T*)current->info;
  }

  T* operator->()
  {
    return (T*)current->info;
  }
};

} /* namespace drizzled */