include/list.h

// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef GESTURES_LIST_H__
#define GESTURES_LIST_H__

#include "gestures/include/logging.h"
#include "gestures/include/memory_manager.h"

namespace gestures {

// Elt must have the following members:
// Elt* next_;
// Elt* prev_;

template<typename Elt>
class List {
 public:
  List() { Init(); }
  ~List() { DeleteAll(); }

  // inserts new_elt before existing. Assumes existing is in list already.
  void InsertBefore(Elt *existing, Elt* new_elt) {
    size_++;
    Elt* pre_new = existing->prev_;
    pre_new->next_ = new_elt;
    new_elt->prev_ = pre_new;
    new_elt->next_ = existing;
    existing->prev_ = new_elt;
  }

  Elt* Unlink(Elt* existing) {
    if (Empty()) {
      Err("Can't pop from empty list!");
      return NULL;
    }
    size_--;
    existing->prev_->next_ = existing->next_;
    existing->next_->prev_ = existing->prev_;
    existing->prev_ = existing->next_ = NULL;
    return existing;
  }

  void PushFront(Elt* elt) { InsertBefore(sentinel_.next_, elt); }
  Elt* PopFront() { return Unlink(sentinel_.next_); }
  void PushBack(Elt* elt) { InsertBefore(&sentinel_, elt); }
  Elt* PopBack() { return Unlink(sentinel_.prev_); }

  virtual void DeleteAll() {
    while (!Empty())
      PopFront();
  }

  Elt* Head() const { return sentinel_.next_; }
  Elt* Tail() const { return sentinel_.prev_; }
  size_t size() const { return size_; }
  bool Empty() const { return size() == 0; }

  // Iterator-like methods
  Elt* Begin() const { return Head(); }
  Elt* End() const { return const_cast<Elt*>(&sentinel_); }

  void Init() {
    size_ = 0;
    sentinel_.next_ = sentinel_.prev_ = &sentinel_;
  }

 private:
  // sentinel element
  Elt sentinel_;

  size_t size_;
};


template<typename Elt>
class MemoryManagedList : public List<Elt> {
 public:
  using List<Elt>::Empty;
  using List<Elt>::PopBack;
  using List<Elt>::PopFront;
  using List<Elt>::PushBack;
  using List<Elt>::PushFront;

  MemoryManagedList() { };
  ~MemoryManagedList() { DeleteAll(); }

  void Init(MemoryManager<Elt>* memory_manager) {
    memory_manager_ = memory_manager;
    List<Elt>::Init();
  }

  Elt* NewElt() {
    Elt* elt = memory_manager_->Allocate();
    AssertWithReturnValue(elt, NULL);
    elt->next_ = elt->prev_ = NULL;
    return elt;
  }

  Elt* PushNewEltBack() {
    AssertWithReturnValue(memory_manager_, NULL);
    Elt* elt = NewElt();
    AssertWithReturnValue(elt, NULL);
    PushBack(elt);
    return elt;
  }

  Elt* PushNewEltFront() {
    AssertWithReturnValue(memory_manager_, NULL);
    Elt* elt = NewElt();
    AssertWithReturnValue(elt, NULL);
    PushFront(elt);
    return elt;
  }

  void DeleteFront() {
    AssertWithReturn(memory_manager_);
    memory_manager_->Free(PopFront());
  }

  void DeleteBack() {
    AssertWithReturn(memory_manager_);
    memory_manager_->Free(PopBack());
  }

  virtual void DeleteAll() {
    while (!Empty())
      DeleteFront();
  }
 private:
  MemoryManager<Elt>* memory_manager_;
};


}  // namespace gestures

#endif  // GESTURES_LIST_H__