src/routingTree.hpp

   1 /*
   2  *  anytun
   3  *
   4  *  The secure anycast tunneling protocol (satp) defines a protocol used
   5  *  for communication between any combination of unicast and anycast
   6  *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
   7  *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
   8  *  ethernet, ip, arp ...). satp directly includes cryptography and
   9  *  message authentication based on the methodes used by SRTP.  It is
  10  *  intended to deliver a generic, scaleable and secure solution for
  11  *  tunneling and relaying of packets of any protocol.
  12  *
  13  *
  14  *  Copyright (C) 2007-2008 Othmar Gsenger, Erwin Nindl,
  15  *                          Christian Pointner <satp@wirdorange.org>
  16  *
  17  *  This file is part of Anytun.
  18  *
  19  *  Anytun is free software: you can redistribute it and/or modify
  20  *  it under the terms of the GNU General Public License version 3 as
  21  *  published by the Free Software Foundation.
  22  *
  23  *  Anytun is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26  *  GNU General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU General Public License
  29  *  along with anytun.  If not, see <http://www.gnu.org/licenses/>.
  30  */
  31
  32 #ifndef __ROUTING_TREE_
  33 #define __ROUTING_TREE_
  34
  35 #include "anytunError.h"
  36
  37 class RoutingTree {
  38
  39 public:
  40   template <class BinaryType>
  41   static void walk(BinaryType bytes ,RoutingTreeNode * node,u_int8_t length,u_int16_t mux)
  42   {
  43     for (int i=0; i<(length/8); i++)
  44     {
  45       if (!node->nodes_[bytes[i]])
  46         node->nodes_[bytes[i]] = new RoutingTreeNode;
  47       node=node->nodes_[bytes[i]];
  48     }
  49     if (length%8)
  50     {
  51       unsigned char idx=0xff;
  52       idx <<=8-(length%8);
  53       idx &= bytes[length/8];
  54       unsigned char maxidx=0xff;
  55       maxidx>>=(length%8);
  56       maxidx|=idx;
  57       for (unsigned char i=idx; i<=maxidx; i++)
  58       {
  59         if (!node->nodes_[i])
  60           node->nodes_[i] = new RoutingTreeNode;
  61         node->nodes_[i]->valid_=true;
  62         node->nodes_[i]->mux_=mux;
  63       }
  64     } else {
  65       node->valid_=true;
  66       node->mux_=mux;
  67     }
  68   }
  69
  70   template <class BinaryType>
  71   static u_int16_t find(BinaryType bytes ,RoutingTreeNode & root )
  72   {
  73     bool valid=0;
  74     u_int16_t mux=0;
  75     RoutingTreeNode * node = &root;
  76     if (root.valid_)
  77     {
  78       mux=root.mux_;
  79       valid=1;
  80     }
  81     for (size_t level=0;level<bytes.size();level++)
  82     {
  83       if (node->nodes_[bytes[level]])
  84       {
  85         node=node->nodes_[bytes[level]];
  86         if(node->valid_)
  87         {
  88           mux=node->mux_;
  89           valid=1;
  90         }
  91       } else {
  92         break;
  93       }
  94     }
  95     if(!valid)
  96       AnytunError::throwErr() << "no route";
  97     return mux;
  98   }
  99
 100 };
 101
 102 #endif
 103
 104