--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/servlib/prophet/Table.h Thu Apr 21 14:57:45 2011 +0100
@@ -0,0 +1,240 @@
+/*
+ * Copyright 2007 Baylor University
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _PROPHET_TABLE_H_
+#define _PROPHET_TABLE_H_
+
+#include "Util.h"
+#include "Node.h"
+#include "Bundle.h"
+#include "BundleCore.h"
+
+#include <map>
+#include <list>
+
+namespace prophet
+{
+
+class Dictionary;
+
+/**
+ * Compare object for Heap
+ */
+struct heap_compare {
+ bool operator() (Node* a, Node* b) {
+ if (a == NULL || b == NULL) return false;
+ return ((*a).p_value() > (*b).p_value());
+ }
+};
+
+/**
+ * Swap object for NodeHeap
+ */
+struct heap_pos {
+ inline void operator()(Node* a, size_t pos)
+ {
+ a->set_heap_pos(pos);
+ }
+};
+
+/**
+ * Container for Prophet nodes (routes and predictability values).
+ * Assumes ownership of memory pointed to by member Node*'s
+ */
+class Table
+{
+public:
+ typedef std::map<std::string,Node*,less_string> rib_table;
+ typedef std::map<std::string,Node*,less_string>::const_iterator
+ const_iterator;
+ typedef std::vector<Node*> Sequence;
+ typedef Sequence::const_iterator heap_iterator;
+
+ /**
+ * Default constructor
+ */
+ Table(BundleCore* core,
+ const std::string& name,
+ bool persistent = false);
+
+ /**
+ * Copy constructor
+ */
+ Table(const Table& t);
+
+ /**
+ * Destructor
+ */
+ ~Table();
+
+ /**
+ * Find and return route for given destination ID; else return NULL
+ */
+ const Node* find(const std::string& dest_id) const;
+
+ /**
+ * Table takes ownership of memory pointed to by Node*, updating
+ * its member list (replacing element if n->dest_id() already exists)
+ */
+ void update(Node* n);
+
+ /**
+ * Convenience function for updating directly-encountered route in
+ * table. Adds new node to table, or updates if route already exists.
+ * On success, post-condition is that update_pvalue is called on the
+ * node, then the node is updated in Table.
+ */
+ void update_route(const std::string& dest_id,
+ bool relay = Node::DEFAULT_RELAY,
+ bool custody = Node::DEFAULT_CUSTODY,
+ bool internet = Node::DEFAULT_INTERNET);
+
+ /**
+ * Convenience function for updating transitively-discovered route
+ * in table. Creates new node, else updates existing. On success,
+ * post-condition is update_transitive is called on node, then node
+ * is updated in Table.
+ */
+ void update_transitive(const std::string& dest_id,
+ const std::string& peer_id,
+ double peer_pvalue,
+ bool relay = Node::DEFAULT_RELAY,
+ bool custody = Node::DEFAULT_CUSTODY,
+ bool internet = Node::DEFAULT_INTERNET);
+
+ /**
+ * Convenience wrapper around update_transitive to import entire RIB
+ */
+ void update_transitive(const std::string& peer_id,
+ const RIBNodeList& nodes,
+ const Dictionary& ribd);
+
+ /**
+ * Convenience function for looking up predictability of a given route
+ */
+ double p_value(const std::string& dest_id) const;
+
+ /**
+ * Convenience function for lookup of predictability of route to b's dest
+ */
+ double p_value(const Bundle* b) const;
+
+ /**
+ * Create duplicate list of Nodes, return number of elements
+ */
+ size_t clone(NodeList& list) const;
+
+ /**
+ * Returns number of routes held by Table
+ */
+ size_t size() const { return table_.size(); }
+
+ /**
+ * Set upper limit on number of routes retained by Table
+ */
+ void set_max_route(u_int max_route)
+ {
+ max_route_ = max_route;
+ enforce_quota();
+ }
+
+ /**
+ * The predictability of Nodes should diminish with time; to allow for
+ * maintenance of routes, the Prophet spec allows for removing routes
+ * whose predictability falls below some arbitrary epsilon.
+ *
+ * Given epsilon as a minimum predictability, remove all routes whose
+ * predictability is below epsilon. Return the number of routes
+ * removed.
+ */
+ size_t truncate(double epsilon);
+
+ /**
+ * Update Table from peer's RIB
+ */
+ void assign(const RIBNodeList& list,
+ const Dictionary& ribd);
+
+ /**
+ * Persistent storage interface: clear contents of Table and assign
+ * from deserialization routine
+ */
+ void assign(const std::list<const Node*>& list,
+ const NodeParams* params);
+
+ /**
+ * For maintenance routines, visit each Node in table and invoke its
+ * aging algorithm; return the number of Nodes visited.
+ */
+ size_t age_nodes();
+
+ ///@{ Iterators
+ const_iterator begin() const { return table_.begin(); }
+ const_iterator end() const { return table_.end(); }
+ heap_iterator heap_begin() const { return heap_.sequence().begin(); }
+ heap_iterator heap_end() const { return heap_.sequence().end(); }
+ ///@}
+
+protected:
+ typedef rib_table::iterator iterator;
+ typedef Heap<Node*,
+ std::vector<Node*>,
+ struct heap_compare,
+ struct heap_pos> NodeHeap;
+
+ /**
+ * Add route to heap
+ */
+ void heap_add(Node* n);
+
+ /**
+ * Remove node from heap
+ */
+ void heap_del(Node* n);
+
+ /**
+ * Enforce upper bound by eliminating minimum routes
+ */
+ void enforce_quota();
+
+ /**
+ * Clean up memory and remove pointer from internal map for this
+ * element
+ */
+ void remove(iterator* i);
+
+ /**
+ * Clean up memory pointed to by each Node*
+ */
+ void free();
+
+ /**
+ * Utility function for finding route by dest_id
+ */
+ bool find(const std::string& dest_id, iterator* i);
+
+ BundleCore* const core_; ///< facade interface into Bundle host
+ rib_table table_; ///< Mapped collection of <dest_id,Node*> pairs
+ NodeHeap heap_; ///< Min-heap for quota-enforcement eviction ordering
+ bool persistent_; ///< whether to utilize BundleCore's persistent
+ /// storage interface for Nodes
+ std::string name_; ///< object name
+ u_int max_route_; ///< upper limit to number of routes to retain
+}; //class Table
+
+}; //namespace prophet
+
+#endif // _PROPHET_TABLE_H_