blob: e4c1ae660f1926e9340aebe2183947c5d7f00614 [file] [log] [blame]
Junxiao Shi0fcb41e2014-01-24 10:29:43 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (C) 2014 Named Data Networking Project
4 * See COPYING for copyright and distribution information.
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -08005 *
6 * Author: Ilya Moiseenko <iliamo@ucla.edu>
Junxiao Shi0fcb41e2014-01-24 10:29:43 -07007 */
8
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -08009#ifndef NFD_TABLE_CS_HPP
10#define NFD_TABLE_CS_HPP
11
12#include "common.hpp"
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070013#include "cs-entry.hpp"
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080014
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080015namespace nfd {
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070016
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080017typedef std::list< shared_ptr<cs::Entry> > SkipListLayer;
18typedef std::list<SkipListLayer*> SkipList;
19
20/** \brief represents Content Store
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070021 */
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -080022class Cs : noncopyable
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070023{
24public:
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080025 explicit
26 Cs(int nMaxPackets = 65536); // ~500MB with average packet size = 8KB
27
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070028 ~Cs();
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080029
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070030 /** \brief inserts a Data packet
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080031 * This method does not consider the payload of the Data packet.
32 *
33 * Packets are considered duplicate if the name matches.
34 * The new Data packet with the identical name, but a different payload
35 * is not placed in the Content Store
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070036 * \return{ whether the Data is added }
37 */
38 bool
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080039 insert(const Data& data, bool isUnsolicited = false);
40
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070041 /** \brief finds the best match Data for an Interest
Alexander Afanasyevc9765df2014-01-25 19:24:27 -080042 * \return{ the best match, if any; otherwise 0 }
Junxiao Shi0fcb41e2014-01-24 10:29:43 -070043 */
Alexander Afanasyevc9765df2014-01-25 19:24:27 -080044 const Data*
Ilya Moiseenko76cf77a2014-03-05 14:35:51 -080045 find(const Interest& interest) const;
46
47 /** \brief deletes CS entry by the exact name
48 */
49 void
50 erase(const Name& exactName);
51
52 /** \brief sets maximum allowed size of Content Store (in packets)
53 */
54 void
55 setLimit(size_t nMaxPackets);
56
57 /** \brief returns maximum allowed size of Content Store (in packets)
58 * \return{ number of packets that can be stored in Content Store }
59 */
60 size_t
61 getLimit() const;
62
63 /** \brief returns current size of Content Store measured in packets
64 * \return{ number of packets located in Content Store }
65 */
66 size_t
67 size() const;
68
69protected:
70 /** \brief removes one Data packet from Content Store based on replacement policy
71 * \return{ whether the Data was removed }
72 */
73 bool
74 evictItem();
75
76private:
77 /** \brief returns True if the Content Store is at its maximum capacity
78 * \return{ True if Content Store is full; otherwise False}
79 */
80 bool
81 isFull() const;
82
83 /** \brief Computes the layer where new Content Store Entry is placed
84 *
85 * Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
86 * \return{ returns random layer (number) in a skip list}
87 */
88 int
89 pickRandomLayer() const;
90
91 /** \brief Inserts a new Content Store Entry in a skip list
92 * \return{ returns a pair containing a pointer to the CS Entry,
93 * and a flag indicating if the entry was newly created (True) or refreshed (False) }
94 */
95 std::pair< shared_ptr<cs::Entry>, bool>
96 insertToSkipList(const Data& data, bool isUnsolicited = false);
97
98 /** \brief Removes a specific CS Entry from all layers of a skip list
99 * \return{ returns True if CS Entry was succesfully removed and False if CS Entry was not found}
100 */
101 bool
102 eraseFromSkipList(shared_ptr<cs::Entry> entry);
103
104 /** \brief Prints contents of the skip list, starting from the top layer
105 */
106 void
107 printSkipList() const;
108
109 /** \brief Implements child selector (leftmost, rightmost, undeclared).
110 * Operates on the first layer of a skip list.
111 *
112 * startingPoint must be less than Interest Name.
113 * startingPoint can be equal to Interest Name only when the item is in the begin() position.
114 *
115 * Iterates toward greater Names, terminates when CS entry falls out of Interest prefix.
116 * When childSelector = leftmost, returns first CS entry that satisfies other selectors.
117 * When childSelector = rightmost, it goes till the end, and returns CS entry that satisfies
118 * other selectors. Returned CS entry is the leftmost child of the rightmost child.
119 * \return{ the best match, if any; otherwise 0 }
120 */
121 const Data*
122 selectChild(const Interest& interest, SkipListLayer::iterator startingPoint) const;
123
124 /** \brief checks if Content Store entry satisfies Interest selectors (MinSuffixComponents,
125 * MaxSuffixComponents, Implicit Digest, MustBeFresh)
126 * \return{ true if satisfies all selectors; false otherwise }
127 */
128 bool
129 doesComplyWithSelectors(const Interest& interest, shared_ptr<cs::Entry> entry) const;
130
131 /** \brief interprets minSuffixComponent and name lengths to understand if Interest contains
132 * implicit digest of the data
133 * \return{ True if Interest name contains digest; False otherwise }
134 */
135 bool
136 recognizeInterestWithDigest(const Interest& interest, shared_ptr<cs::Entry> entry) const;
137
138private:
139 class StalenessComparator
140 {
141 public:
142 bool
143 operator() (shared_ptr<cs::Entry> entry1, shared_ptr<cs::Entry> entry2)
144 {
145 return entry1->getStaleTime() > entry2->getStaleTime();
146 }
147 };
148
149 SkipList m_skipList;
150 size_t m_nMaxPackets; //user defined maximum size of the Content Store in packets
151
152 std::queue< shared_ptr<cs::Entry> > m_unsolicitedContent; //FIFO for unsolicited Data
153 std::queue< shared_ptr<cs::Entry> > m_contentByArrival; //FIFO index
154 std::priority_queue< shared_ptr<cs::Entry>, std::vector< shared_ptr<cs::Entry> >, StalenessComparator> m_contentByStaleness; //index by staleness time
Junxiao Shi0fcb41e2014-01-24 10:29:43 -0700155};
156
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800157} // namespace nfd
Alexander Afanasyevb927a3a2014-01-24 10:41:47 -0800158
159#endif // NFD_TABLE_CS_HPP