|
1 /* |
|
2 * Copyright 2007 Baylor University |
|
3 * |
|
4 * Licensed under the Apache License, Version 2.0 (the "License"); |
|
5 * you may not use this file except in compliance with the License. |
|
6 * You may obtain a copy of the License at |
|
7 * |
|
8 * http://www.apache.org/licenses/LICENSE-2.0 |
|
9 * |
|
10 * Unless required by applicable law or agreed to in writing, software |
|
11 * distributed under the License is distributed on an "AS IS" BASIS, |
|
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
13 * See the License for the specific language governing permissions and |
|
14 * limitations under the License. |
|
15 */ |
|
16 |
|
17 #ifndef _PROPHET_REPOSITORY_H_ |
|
18 #define _PROPHET_REPOSITORY_H_ |
|
19 |
|
20 #include "Bundle.h" |
|
21 #include "BundleList.h" |
|
22 #include "QueuePolicy.h" |
|
23 |
|
24 #if defined(__GNUC__) |
|
25 # define PRINTFLIKE(fmt, arg) __attribute__((format (printf, fmt, arg))) |
|
26 #else |
|
27 # define PRINTFLIKE(a, b) |
|
28 #endif |
|
29 |
|
30 namespace prophet |
|
31 { |
|
32 |
|
33 /** |
|
34 * Implements a modified heap-based priority_queue with bounds enforcement. |
|
35 * Any change to a Bundle's priority (such as the act of forwarding a Bundle |
|
36 * over a link) requires a call-back to change_priority to preserve correct |
|
37 * heap ordering. Any change to a Bundle's size will result in undefined |
|
38 * behavior; at present, the best practice is to drop() the bundle before |
|
39 * the size change then add() it again after the size is finalized. Any |
|
40 * change in policy (ie, a new comparator) will cost n for the pass-thru |
|
41 * of reheaping; any change in max will also be at most a linear cost. |
|
42 */ |
|
43 class Repository |
|
44 { |
|
45 public: |
|
46 typedef BundleList::iterator iterator; |
|
47 typedef BundleList::const_iterator const_iterator; |
|
48 |
|
49 /** |
|
50 * Reduced interface into BundleCore to provide logging, drop_bundle |
|
51 * signal, and answer the query for bundle storage quota |
|
52 */ |
|
53 class BundleCoreRep |
|
54 { |
|
55 public: |
|
56 virtual ~BundleCoreRep() {} |
|
57 virtual void print_log(const char* name, int level, |
|
58 const char* fmt, ...) |
|
59 PRINTFLIKE(4,5) = 0; |
|
60 virtual void drop_bundle(const Bundle* bundle) = 0; |
|
61 virtual u_int64_t max_bundle_quota() const = 0; |
|
62 }; |
|
63 |
|
64 /** |
|
65 * Constructor. Repository assumes ownership of memory pointed to by qc, |
|
66 * but not for list (makes a copy). |
|
67 * @param core facade interface into Bundle host |
|
68 * @param qc Queue Policy comparator to sort by eviction order (such |
|
69 * that the next Bundle to be evicted is evaluated less-than |
|
70 * all other Bundles) |
|
71 * @param list initial list of Bundles to store |
|
72 */ |
|
73 Repository(BundleCoreRep* core, QueueComp* qc = NULL, |
|
74 const BundleList* list = NULL); |
|
75 |
|
76 /** |
|
77 * Destructor |
|
78 */ |
|
79 ~Repository(); |
|
80 |
|
81 /** |
|
82 * Add bundle to Repository, incrementing current utilization by |
|
83 * Bundle's storage size. |
|
84 * @param bundle pointer to Bundle to be added |
|
85 * @return whether bundle was added |
|
86 */ |
|
87 bool add(const Bundle* bundle); |
|
88 |
|
89 /** |
|
90 * Remove arbitrary Bundle from Repository, and decrement current |
|
91 * utilization accordingly. Assumes Bundle priority has not been |
|
92 * changed, and that underlying heap is in priority order. |
|
93 * @param bundle pointer to Bundle to be removed |
|
94 */ |
|
95 void del(const Bundle* bundle); |
|
96 |
|
97 /** |
|
98 * Change policy of Repository by replacing comparator; post condition |
|
99 * is that eviction order is resorted using the new comparator. |
|
100 * @param qc comparator used to sort Bundles in eviction order |
|
101 */ |
|
102 void set_comparator(QueueComp* qc); |
|
103 |
|
104 /** |
|
105 * Accessor to current comparator |
|
106 */ |
|
107 const QueueComp* get_comparator() const { return comp_; } |
|
108 |
|
109 /** |
|
110 * Callback to instruct Repository to query BundleCore on new max |
|
111 */ |
|
112 void handle_change_max(); |
|
113 |
|
114 /** |
|
115 * Callback for external notice to recalculate eviction order for |
|
116 * list, due to changed comparator state |
|
117 */ |
|
118 void change_priority(const Bundle* b); |
|
119 |
|
120 /** |
|
121 * Fetch const reference to internal list of Bundles (there is no |
|
122 * guarantee of meaningful order to returned list) |
|
123 */ |
|
124 const BundleList& get_bundles() const { return list_; } |
|
125 |
|
126 /** |
|
127 * Return boolean indicating whether Repository has any bundles. |
|
128 */ |
|
129 bool empty() const { return list_.empty(); } |
|
130 |
|
131 /** |
|
132 * Return number of Bundles in Repository |
|
133 */ |
|
134 size_t size() const { return list_.size(); } |
|
135 |
|
136 /** |
|
137 * Return the current upper limit imposed by Repository |
|
138 */ |
|
139 u_int get_max() const { return core_->max_bundle_quota(); } |
|
140 |
|
141 /** |
|
142 * Return current storage consumed by Bundles in Repository |
|
143 */ |
|
144 u_int get_current() const { return current_; } |
|
145 |
|
146 protected: |
|
147 /** |
|
148 * Evict the next candidate Bundle according to policy order |
|
149 */ |
|
150 void evict(); |
|
151 |
|
152 ///@{ Heap operations |
|
153 void make_heap(size_t first, size_t last); |
|
154 void push_heap(size_t first, size_t hole, size_t top, const Bundle* b); |
|
155 void pop_heap(size_t first, size_t last, size_t result, const Bundle* b); |
|
156 void adjust_heap(size_t first, size_t hole, size_t len, const Bundle* b); |
|
157 void remove_and_reheap(size_t hole); |
|
158 ///@} |
|
159 |
|
160 /** |
|
161 * Utility function for find |
|
162 */ |
|
163 bool find(const Bundle* b, iterator& i); |
|
164 |
|
165 BundleCoreRep* core_; ///< facade interface into Bundle host |
|
166 QueueComp* comp_; ///< queue policy Bundle comparator |
|
167 BundleList list_; ///< array-based eviction-ordered heap of Bundles |
|
168 u_int current_; ///< current utilization |
|
169 }; // class Repository |
|
170 |
|
171 }; // namespace prophet |
|
172 |
|
173 #endif // _PROPHET_REPOSITORY_H_ |