thread_list.h

多线程库

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

//
// This is an internal list, implemented here because the original uses
// alloc too cumbersomely and breaks the program.
// 
#ifndef __THREADS_LIST
#define __THREADS_LIST

#define _THREAD_SAFE
#include <thread_alloc.h>
#include <iostream.h>

template<class T>
struct _list_node {
  typedef void* void_ptr;
  void_ptr n_next;
  void_ptr n_prev;
  T data;
};

template<class T, class Ref, class Ptr>
struct _list_iterator {
  typedef _list_iterator<T, T&, T*>             iterator;
  typedef _list_iterator<T, const T&, const T*> const_iterator;
  typedef _list_iterator<T, Ref, Ptr>           self;

  typedef T              value_type;
  typedef Ptr            pointer;
  typedef Ref            reference;
  typedef _list_node<T>* link_type;

  link_type i_node;

  _list_iterator(link_type x) : i_node(x) { };
  _list_iterator() { };
  _list_iterator(const iterator& x) : i_node(x.i_node) { };

  bool operator==(const self& x) const { return i_node == x.i_node; };
  bool operator!=(const self& x) const { return i_node != x.i_node; };
  reference operator*() const { return (*i_node).data; };

  self& operator++() {
    i_node = (link_type)((*i_node).n_next);
    return *this;
  }
  self operator++(int) {
    self tmp = *this;
    ++*this;
    return tmp;
  }
  self& operator--() {
    i_node = (link_type)((*i_node).n_next);
    return *this;
  }
  self operator--(int) {
    self tmp = *this;
    --*this;
    return tmp;
  }
};

template<class T, class Alloc = alloc>
class list {
 protected:
  typedef void* void_ptr;
  typedef _list_node<T> list_node;
  typedef simple_alloc<list_node, Alloc> list_node_allocator;
 public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef list_node* link_type;

  typedef _list_iterator<T, T&, T*>             iterator;
  typedef _list_iterator<T, const T&, const T*> const_iterator;

 protected:
  link_type get_node() { return list_node_allocator::allocate(); };
  void put_node(link_type p) { list_node_allocator::deallocate(p); };

  link_type create_node(const T& x) {
    link_type p = get_node();
    try {
      p->data = x;
    }
    catch(...) { put_node(p); throw; };
    return p;
  }
  void destroy_node(link_type p) {
    (&p->data)->~T();
    put_node(p);
  };

  void empty_init() {
    l_head = get_node();
    l_head->n_next = l_head;
    l_head->n_prev = l_head;
  }

 private:
  link_type l_head;

 public:
  list() { empty_init(); }
  ~list() { };

  iterator begin() { return (link_type)((*l_head).n_next); }
  const_iterator begin() const { return (link_type)((l_head).n_next); }
  iterator end() { return l_head; }
  const_iterator end() const { return l_head; }

  bool empty() const { return l_head->n_next == l_head; }

  reference front() { return *begin(); }
  reference back() { return *end(); }

  iterator insert(iterator pos, const T& x) {
    link_type tmp = create_node(x);
    tmp->n_next = pos.i_node;
    tmp->n_prev = pos.i_node->n_prev;
    (link_type(pos.i_node->n_prev))->n_next = tmp;
    pos.i_node->n_prev = tmp;
    return tmp;
  }
  iterator insert(iterator pos) { return insert(pos, T()); }

  iterator find(const T& val) {
    iterator i;
    for(i=begin();i!=end();i++)
      if ((*i) == val)
	return i;
    return end();
  }

  void push_front(const T& x) { insert(begin(), x); }
  void push_back(const T& x) { insert(end(), x); }

  iterator erase(iterator pos) {
    link_type nn = link_type(pos.i_node->n_next);
    link_type pn = link_type(pos.i_node->n_prev);
    pn->n_next = nn;
    nn->n_prev = pn;
    destroy_node(pos.i_node);
    return iterator(nn);
  }

  void pop_front() { erase(begin()); }
  void pop_back() {
    iterator tmp = end();
    erase(--tmp);
  }

};

#endif /* __THREAD_LIST */