From 1c16c9dd9fca28260793f8b89b5fe484e541715d Mon Sep 17 00:00:00 2001 From: Christian Pointner Date: Mon, 22 Dec 2008 18:51:03 +0000 Subject: cleaned up routingTree structure --- src/Makefile | 2 +- src/routingTable.cpp | 14 +++---- src/routingTree.hpp | 102 ++++++++++++++++++++++++++++++++++++++++++++++ src/routingTreeNode.cpp | 2 +- src/routingTreeNode.h | 16 +++++--- src/routingTreeWalker.hpp | 63 ---------------------------- 6 files changed, 122 insertions(+), 77 deletions(-) create mode 100644 src/routingTree.hpp delete mode 100644 src/routingTreeWalker.hpp (limited to 'src') diff --git a/src/Makefile b/src/Makefile index adbf1ea..75b65d8 100644 --- a/src/Makefile +++ b/src/Makefile @@ -205,7 +205,7 @@ authAlgoFactory.o: authAlgoFactory.cpp authAlgoFactory.h authAlgo.h keyDerivationFactory.o: keyDerivationFactory.cpp keyDerivationFactory.h keyDerivation.h $(CXX) $(CXXFLAGS) $< -c -routingTable.o: routingTable.cpp routingTable.h routingTreeWalker.hpp +routingTable.o: routingTable.cpp routingTable.h routingTree.hpp $(CXX) $(CXXFLAGS) $< -c syncCommand.o: syncCommand.cpp syncCommand.h diff --git a/src/routingTable.cpp b/src/routingTable.cpp index a1f8d67..608c420 100644 --- a/src/routingTable.cpp +++ b/src/routingTable.cpp @@ -33,7 +33,7 @@ #include "datatypes.h" #include "routingTable.h" -#include "routingTreeWalker.hpp" +#include "routingTree.hpp" RoutingTable* RoutingTable::inst = NULL; Mutex RoutingTable::instMutex; @@ -69,17 +69,17 @@ void RoutingTable::updateRouteTree(const NetworkPrefix & pref) ipv4_bytes_type bytes(pref.to_bytes_v4()); if (length>32) length=32; - routingTreeWalker(bytes, node, length, mux); + RoutingTree::walk(bytes, node, length, mux); } else if (type==ipv6) { ipv6_bytes_type bytes(pref.to_bytes_v6()); if (length>128) length=128; - routingTreeWalker(bytes, node, length, mux); + RoutingTree::walk(bytes, node, length, mux); } else if (type==ethernet) { ethernet_bytes_type bytes(pref.to_bytes_ethernet()); if (length>48) length=48; - routingTreeWalker(bytes, node, length, mux); + RoutingTree::walk(bytes, node, length, mux); } else { throw std::runtime_error("illegal protocoll type"); } @@ -121,15 +121,15 @@ u_int16_t RoutingTable::getRoute(const NetworkAddress & addr) if (type==ipv4) { ipv4_bytes_type bytes(addr.to_bytes_v4()); - return routingTreeFinder(bytes, root_[type]); + return RoutingTree::find(bytes, root_[type]); } else if (type==ipv6) { ipv6_bytes_type bytes(addr.to_bytes_v6()); - return routingTreeFinder(bytes, root_[type]); + return RoutingTree::find(bytes, root_[type]); } else if (type==ethernet) { //TODO Our model wont fit to ethernet addresses well. // maybe use hashmap or something like that instead ethernet_bytes_type bytes(addr.to_bytes_ethernet()); - return routingTreeFinder(bytes, root_[type]); + return RoutingTree::find(bytes, root_[type]); } else { throw std::runtime_error("illegal protocoll type"); } diff --git a/src/routingTree.hpp b/src/routingTree.hpp new file mode 100644 index 0000000..c75aef5 --- /dev/null +++ b/src/routingTree.hpp @@ -0,0 +1,102 @@ +/* + * anytun + * + * The secure anycast tunneling protocol (satp) defines a protocol used + * for communication between any combination of unicast and anycast + * tunnel endpoints. It has less protocol overhead than IPSec in Tunnel + * mode and allows tunneling of every ETHER TYPE protocol (e.g. + * ethernet, ip, arp ...). satp directly includes cryptography and + * message authentication based on the methodes used by SRTP. It is + * intended to deliver a generic, scaleable and secure solution for + * tunneling and relaying of packets of any protocol. + * + * + * Copyright (C) 2007-2008 Othmar Gsenger, Erwin Nindl, + * Christian Pointner + * + * This file is part of Anytun. + * + * Anytun is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 3 as + * published by the Free Software Foundation. + * + * Anytun 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 anytun. If not, see . + */ + +#ifndef __ROUTING_TREE_ +#define __ROUTING_TREE_ + +class RoutingTree { + +public: + template + static void walk(BinaryType bytes ,RoutingTreeNode * node,u_int8_t length,u_int16_t mux) + { + for (int i=0; i<(length/8); i++) + { + if (!node->nodes_[bytes[i]]) + node->nodes_[bytes[i]] = new RoutingTreeNode; + node=node->nodes_[bytes[i]]; + } + if (length%8) + { + unsigned char idx=0xff; + idx <<=8-(length%8); + idx &= bytes[length/8]; + unsigned char maxidx=0xff; + maxidx>>=(length%8); + maxidx|=idx; + for (unsigned char i=idx; i<=maxidx; i++) + { + if (!node->nodes_[i]) + node->nodes_[i] = new RoutingTreeNode; + node->nodes_[i]->valid_=true; + node->nodes_[i]->mux_=mux; + } + } else { + node->valid_=true; + node->mux_=mux; + } + } + + template + static u_int16_t find(BinaryType bytes ,RoutingTreeNode & root ) + { + bool valid=0; + u_int16_t mux=0; + RoutingTreeNode * node = &root; + if (root.valid_) + { + mux=root.mux_; + valid=1; + } + for (size_t level=0;levelnodes_[bytes[level]]) + { + node=node->nodes_[bytes[level]]; + if(node->valid_) + { + mux=node->mux_; + valid=1; + } + } else { + break; + } + } + if(!valid) + throw std::runtime_error("no route"); + return mux; + } + +}; + +#endif + + diff --git a/src/routingTreeNode.cpp b/src/routingTreeNode.cpp index 47dc0fc..eed501b 100644 --- a/src/routingTreeNode.cpp +++ b/src/routingTreeNode.cpp @@ -28,6 +28,7 @@ * You should have received a copy of the GNU General Public License * along with anytun. If not, see . */ + #include "routingTreeNode.h" RoutingTreeNode::RoutingTreeNode():mux_(0),valid_(false) @@ -55,7 +56,6 @@ void RoutingTreeNode::print(int level) const } } - RoutingTreeNode::~RoutingTreeNode() { for(int i=0; i<256; i++) diff --git a/src/routingTreeNode.h b/src/routingTreeNode.h index c09f2c9..3c2d33d 100644 --- a/src/routingTreeNode.h +++ b/src/routingTreeNode.h @@ -29,8 +29,8 @@ * along with anytun. If not, see . */ -#ifndef _ROUTINGTREENODE_H -#define _ROUTINGTREENODE_H +#ifndef _ROUTING_TREE_NODE_H +#define _ROUTING_TREE_NODE_H #include "threadUtils.hpp" @@ -38,16 +38,22 @@ #include "networkAddress.h" #include "networkPrefix.h" +class RoutingTree; + class RoutingTreeNode { public: RoutingTreeNode(); ~RoutingTreeNode(); + void print(int) const; + +private: +// Mutex mutex_; u_int16_t mux_; bool valid_; boost::array nodes_; - void print(int) const; -private: - Mutex mutex_; + + friend class RoutingTree; }; + #endif diff --git a/src/routingTreeWalker.hpp b/src/routingTreeWalker.hpp deleted file mode 100644 index 33e4ae6..0000000 --- a/src/routingTreeWalker.hpp +++ /dev/null @@ -1,63 +0,0 @@ -#ifndef __ROUTING_TREE_WALKER_ -#define __ROUTING_TREE_WALKER_ -template -void routingTreeWalker(BinaryType bytes ,RoutingTreeNode * node,u_int8_t length,u_int16_t mux) -{ - for (int i=0; i<(length/8); i++) - { - if (!node->nodes_[bytes[i]]) - node->nodes_[bytes[i]] = new RoutingTreeNode; - node=node->nodes_[bytes[i]]; - } - if (length%8) - { - unsigned char idx=0xff; - idx <<=8-(length%8); - idx &= bytes[length/8]; - unsigned char maxidx=0xff; - maxidx>>=(length%8); - maxidx|=idx; - for (unsigned char i=idx; i<=maxidx; i++) - { - if (!node->nodes_[i]) - node->nodes_[i] = new RoutingTreeNode; - node->nodes_[i]->valid_=true; - node->nodes_[i]->mux_=mux; - } - } else { - node->valid_=true; - node->mux_=mux; - } -} - -template -u_int16_t routingTreeFinder(BinaryType bytes ,RoutingTreeNode & root ) -{ - bool valid=0; - u_int16_t mux=0; - RoutingTreeNode * node = &root; - if (root.valid_) - { - mux=root.mux_; - valid=1; - } - for (size_t level=0;levelnodes_[bytes[level]]) - { - node=node->nodes_[bytes[level]]; - if(node->valid_) - { - mux=node->mux_; - valid=1; - } - } else { - break; - } - } - if(!valid) - throw std::runtime_error("no route"); - return mux; -} -#endif - -- cgit v1.2.3