cs.hpp

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
#ifndef NFD_DAEMON_TABLE_CS_HPP
#define NFD_DAEMON_TABLE_CS_HPP

#include "common.hpp"
#include "cs-skip-list-entry.hpp"

#include <boost/multi_index/member.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>

#include <queue>

namespace nfd {

typedef std::list<cs::skip_list::Entry*> SkipListLayer;
typedef std::list<SkipListLayer*> SkipList;

class StalenessComparator
{
public:
  bool
  operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
  {
    return entry1->getStaleTime() < entry2->getStaleTime();
  }
};

class UnsolicitedComparator
{
public:
  bool
  operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
  {
    return entry1->isUnsolicited();
  }

  bool
  operator()(bool isUnsolicited, const cs::skip_list::Entry* entry) const
  {
    if (isUnsolicited)
      return true;
    else
      return !entry->isUnsolicited();
  }
};

// tags
class unsolicited;
class byStaleness;
class byArrival;

typedef boost::multi_index_container<
  cs::skip_list::Entry*,
  boost::multi_index::indexed_by<

    // by arrival (FIFO)
    boost::multi_index::sequenced<
      boost::multi_index::tag<byArrival>
    >,

    // index by staleness time
    boost::multi_index::ordered_non_unique<
      boost::multi_index::tag<byStaleness>,
      boost::multi_index::identity<cs::skip_list::Entry*>,
      StalenessComparator
    >,

    // unsolicited Data is in the front
    boost::multi_index::ordered_non_unique<
      boost::multi_index::tag<unsolicited>,
      boost::multi_index::identity<cs::skip_list::Entry*>,
      UnsolicitedComparator
    >

  >
> CleanupIndex;

class Cs : noncopyable
{
public:
  explicit
  Cs(size_t nMaxPackets = 10);

  ~Cs();

  bool
  insert(const Data& data, bool isUnsolicited = false);

  const Data*
  find(const Interest& interest) const;

  void
  erase(const Name& exactName);

  void
  setLimit(size_t nMaxPackets);

  size_t
  getLimit() const;

  size_t
  size() const;

public: // enumeration
  class const_iterator;

  const_iterator
  begin() const;

  const_iterator
  end() const;

  class const_iterator : public std::iterator<std::forward_iterator_tag, const cs::Entry>
  {
  public:
    const_iterator() = default;

    const_iterator(SkipListLayer::const_iterator it);

    ~const_iterator();

    reference
    operator*() const;

    pointer
    operator->() const;

    const_iterator&
    operator++();

    const_iterator
    operator++(int);

    bool
    operator==(const const_iterator& other) const;

    bool
    operator!=(const const_iterator& other) const;

  private:
    SkipListLayer::const_iterator m_skipListIterator;
  };

protected:
  bool
  evictItem();

private:
  bool
  isFull() const;

  size_t
  pickRandomLayer() const;

  std::pair<cs::skip_list::Entry*, bool>
  insertToSkipList(const Data& data, bool isUnsolicited = false);

  bool
  eraseFromSkipList(cs::skip_list::Entry* entry);

  void
  printSkipList() const;

  const Data*
  selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const;

  bool
  doesComplyWithSelectors(const Interest& interest,
                          cs::skip_list::Entry* entry,
                          bool doesInterestContainDigest) const;

  bool
  recognizeInterestWithDigest(const Interest& interest, cs::skip_list::Entry* entry) const;

private:
  SkipList m_skipList;
  CleanupIndex m_cleanupIndex;
  size_t m_nMaxPackets; // user defined maximum size of the Content Store in packets
  size_t m_nPackets;    // current number of packets in Content Store
  std::queue<cs::skip_list::Entry*> m_freeCsEntries; // memory pool
};

inline Cs::const_iterator
Cs::begin() const
{
  return const_iterator(m_skipList.front()->begin());
}

inline Cs::const_iterator
Cs::end() const
{
  return const_iterator(m_skipList.front()->end());
}

inline
Cs::const_iterator::const_iterator(SkipListLayer::const_iterator it)
  : m_skipListIterator(it)
{
}

inline
Cs::const_iterator::~const_iterator()
{
}

inline Cs::const_iterator&
Cs::const_iterator::operator++()
{
  ++m_skipListIterator;
  return *this;
}

inline Cs::const_iterator
Cs::const_iterator::operator++(int)
{
  Cs::const_iterator temp(*this);
  ++(*this);
  return temp;
}

inline Cs::const_iterator::reference
Cs::const_iterator::operator*() const
{
  return *(this->operator->());
}

inline Cs::const_iterator::pointer
Cs::const_iterator::operator->() const
{
  return *m_skipListIterator;
}

inline bool
Cs::const_iterator::operator==(const Cs::const_iterator& other) const
{
  return m_skipListIterator == other.m_skipListIterator;
}

inline bool
Cs::const_iterator::operator!=(const Cs::const_iterator& other) const
{
  return !(*this == other);
}

} // namespace nfd

#endif // NFD_DAEMON_TABLE_CS_HPP