smallstack_type.hpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * OpenTTD 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.
 * OpenTTD 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 OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef SMALLSTACK_TYPE_HPP
#define SMALLSTACK_TYPE_HPP
 
#include <mutex>
 
template<typename Titem, typename Tindex, Tindex Tgrowth_step, Tindex Tmax_size>
class SimplePool {
public:
  inline SimplePool() : first_unused(0), first_free(0) {}
 
  inline std::mutex &GetMutex() { return this->mutex; }
 
  inline Titem &Get(Tindex index) { return this->data[index]; }
 
  inline Tindex Create()
  {
    Tindex index = this->FindFirstFree();
    if (index < Tmax_size) {
      this->data[index].valid = true;
      this->first_free = index + 1;
      this->first_unused = std::max(this->first_unused, this->first_free);
    }
    return index;
  }
 
  inline void Destroy(Tindex index)
  {
    this->data[index].valid = false;
    this->first_free = std::min(this->first_free, index);
  }
 
private:
 
  inline Tindex FindFirstFree()
  {
    Tindex index = this->first_free;
    for (; index < this->first_unused; index++) {
      if (!this->data[index].valid) return index;
    }
 
    if (index >= this->data.size() && index < Tmax_size) {
      this->data.resize(index + 1);
    }
    return index;
  }
 
  struct SimplePoolPoolItem : public Titem {
    bool valid;
  };
 
  Tindex first_unused;
  Tindex first_free;
 
  std::mutex mutex;
  std::vector<SimplePoolPoolItem> data;
};
 
template <typename Titem, typename Tindex>
struct SmallStackItem {
  Tindex next; 
  Titem value; 
 
  inline SmallStackItem(const Titem &value, Tindex next) :
    next(next), value(value) {}
  SmallStackItem() = default;
};
 
template <typename Titem, typename Tindex, Titem Tinvalid, Tindex Tgrowth_step, Tindex Tmax_size>
class SmallStack : public SmallStackItem<Titem, Tindex> {
public:
 
  typedef SmallStackItem<Titem, Tindex> Item;
 
  struct PooledSmallStack : public Item {
    Tindex branch_count; 
  };
 
  typedef SimplePool<PooledSmallStack, Tindex, Tgrowth_step, Tmax_size> SmallStackPool;
 
  inline SmallStack(const Titem &value = Tinvalid) : Item(value, Tmax_size) {}
 
  inline ~SmallStack()
  {
    /* Pop() locks the mutex and after each pop the pool is consistent.*/
    while (this->next != Tmax_size) this->Pop();
  }
 
  inline SmallStack(const SmallStack &other) : Item(other) { this->Branch(); }
 
  inline SmallStack &operator=(const SmallStack &other)
  {
    if (this == &other) return *this;
    while (this->next != Tmax_size) this->Pop();
    this->next = other.next;
    this->value = other.value;
    /* Deleting and branching are independent operations, so it's fine to
     * acquire separate locks for them. */
    this->Branch();
    return *this;
  }
 
  inline void Push(const Titem &item)
  {
    if (this->value != Tinvalid) {
      std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
      Tindex new_item = SmallStack::GetPool().Create();
      if (new_item != Tmax_size) {
        PooledSmallStack &pushed = SmallStack::GetPool().Get(new_item);
        pushed.value = this->value;
        pushed.next = this->next;
        pushed.branch_count = 0;
        this->next = new_item;
      }
    }
    this->value = item;
  }
 
  inline Titem Pop()
  {
    Titem ret = this->value;
    if (this->next == Tmax_size) {
      this->value = Tinvalid;
    } else {
      std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
      PooledSmallStack &popped = SmallStack::GetPool().Get(this->next);
      this->value = popped.value;
      if (popped.branch_count == 0) {
        SmallStack::GetPool().Destroy(this->next);
      } else {
        --popped.branch_count;
        /* We can't use Branch() here as we already have the mutex.*/
        if (popped.next != Tmax_size) {
          ++(SmallStack::GetPool().Get(popped.next).branch_count);
        }
      }
      /* Accessing popped here is no problem as the pool will only set
       * the validity flag, not actually delete the item, on Destroy().
       * It's impossible for another thread to acquire the same item in
       * the mean time because of the mutex. */
      this->next = popped.next;
    }
    return ret;
  }
 
  inline bool IsEmpty() const
  {
    return this->value == Tinvalid && this->next == Tmax_size;
  }
 
  inline bool Contains(const Titem &item) const
  {
    if (item == Tinvalid || item == this->value) return true;
    if (this->next != Tmax_size) {
      std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
      const SmallStack *in_list = this;
      do {
        in_list = static_cast<const SmallStack *>(
            static_cast<const Item *>(&SmallStack::GetPool().Get(in_list->next)));
        if (in_list->value == item) return true;
      } while (in_list->next != Tmax_size);
    }
    return false;
  }
 
protected:
  static SmallStackPool &GetPool()
  {
    static SmallStackPool pool;
    return pool;
  }
 
  inline void Branch()
  {
    if (this->next != Tmax_size) {
      std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
      ++(SmallStack::GetPool().Get(this->next).branch_count);
    }
  }
};
 
#endif