inline_slist.h

Go to the documentation of this file.

// Copyright 2012 Google Inc.

#ifndef PAGESPEED_KERNEL_BASE_INLINE_SLIST_H_
#define PAGESPEED_KERNEL_BASE_INLINE_SLIST_H_

#include <cstddef>

#include "base/logging.h"  
#include "pagespeed/kernel/base/basictypes.h"

namespace net_instaweb {

template<class T> class InlineSList;

template<class T>
class InlineSListElement {
 protected:
  InlineSListElement() : next_(NULL) {}

 private:
  friend class InlineSList<T>;
  T* next() { return next_; }
  void set_next(T* new_next) { next_ = new_next; }

  T* next_;
  
};

template<class T>
class InlineSList {
 private:
  class IterBase {
   protected:
    IterBase(const InlineSList<T>* list, T* node)
        : list_(list), node_(node) {
    }

    bool AtEnd() const {
      return (node_ == NULL);
    }

    void Advance() {
      DCHECK(!AtEnd());
      node_ = node_->next();
      if (node_ == list_->tail_) {
        node_ = NULL;
      }
    }

    T* Data() {
      return node_->next();
    }

    bool Equals(const IterBase& other) const {
      return (node_ == other.node_) && (list_ == other.list_);
    }

   private:
    friend class InlineSList<T>;
    const InlineSList<T>* list_;
    T* node_;
  };

 public:
  class Iterator : public IterBase {
   public:
    Iterator& operator++() {
      this->Advance();
      return *this;
    }

    T* Get() { return this->Data(); }
    T* operator->() { return this->Data(); }
    T& operator*() { return *this->Data(); }
    bool operator==(const Iterator& other) const { return this->Equals(other); }
    bool operator!=(const Iterator& other) const {
      return !this->Equals(other);
    }

   private:
    friend class InlineSList<T>;
    Iterator(const InlineSList<T>* list, T* prev) : IterBase(list, prev) {}
  };

  typedef Iterator iterator;

  class ConstIterator : public IterBase {
   public:
    ConstIterator& operator++() {
      this->Advance();
      return *this;
    }

    const T* Get() { return this->Data(); }
    const T* operator->() { return this->Data(); }
    const T& operator*() { return *this->Data(); }
    bool operator==(const ConstIterator& other) const {
      return this->Equals(other);
    }
    bool operator!=(const ConstIterator& other) const {
      return !this->Equals(other);
    }

   private:
    friend class InlineSList<T>;
    ConstIterator(const InlineSList<T>* list, T* prev) : IterBase(list, prev) {}
  };

  typedef ConstIterator const_iterator;

  InlineSList() : tail_(NULL) {
  }

  ~InlineSList();

  bool IsEmpty() const {
    return (tail_ == NULL);
  }

  void Append(T* node);

  void Erase(Iterator* iter);

  T* Last() {
    DCHECK(!IsEmpty());
    return tail_;
  }

  const T* Last() const {
    DCHECK(!IsEmpty());
    return tail_;
  }


  iterator begin() { return Iterator(this, tail_); }
  const_iterator begin() const { return ConstIterator(this, tail_); }

  iterator end() { return Iterator(this, NULL); }
  const_iterator end() const { return ConstIterator(this, NULL); }

 private:
  T* tail_;

  
};

template<class T>
inline InlineSList<T>::~InlineSList() {
  if (tail_ != NULL) {
    T* node = tail_->next(); 
    while (true) {
      T* next = node->next();
      delete node;
      if (node == tail_) {  
        break;
      } else {
        node = next;
      }
    }
  }
  tail_ = NULL;
}

template<class T>
inline void InlineSList<T>::Append(T* node) {
  if (tail_ == NULL) {
    tail_ = node;
    node->set_next(node);
  } else {
    node->set_next(tail_->next());
    tail_->set_next(node);
    tail_ = node;
  }
}

template<class T>
inline void InlineSList<T>::Erase(Iterator* iter) {
  DCHECK(!iter->AtEnd());

  T* iter_node = iter->node_;
  T* target_node = iter_node->next();

  if (iter_node == target_node) {
    tail_ = NULL;
    iter->node_ = NULL;
  } else {
    iter_node->set_next(target_node->next());
    if (target_node == tail_) {
      tail_ = iter_node;
      iter->node_ = NULL;
    }
  }
  delete target_node;
}

}  

#endif