xorp

real_trie.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 
00003 // Copyright (c) 2001-2009 XORP, Inc.
00004 //
00005 // This program is free software; you can redistribute it and/or modify
00006 // it under the terms of the GNU General Public License, Version 2, June
00007 // 1991 as published by the Free Software Foundation. Redistribution
00008 // and/or modification of this program under the terms of any other
00009 // version of the GNU General Public License is not permitted.
00010 // 
00011 // This program is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00014 // see the GNU General Public License, Version 2, a copy of which can be
00015 // found in the XORP LICENSE.gpl file.
00016 // 
00017 // XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00018 // http://xorp.net
00019 
00020 // $XORP: xorp/bgp/harness/real_trie.hh,v 1.13 2008/10/02 21:56:26 bms Exp $
00021 
00022 #ifndef __BGP_HARNESS_REAL_TRIE_HH_
00023 #define __BGP_HARNESS_REAL_TRIE_HH_
00024 
00025 template <class A>
00026 class RealTrie {
00027 public:
00028     RealTrie() : _debug(true), _pretty(true)  {
00029     }
00030 
00031     ~RealTrie();
00032 
00033     bool empty() const;
00034 
00035     typedef typename XorpCallback3<void, const UpdatePacket*,
00036               const IPNet<A>&,
00037               const TimeVal&>::RefPtr TreeWalker;
00038 
00039     void tree_walk_table(const TreeWalker& tw) const {
00040     A topbit;
00041     ++topbit;
00042     topbit = topbit << A::addr_bitlen() - 1;
00043     tree_walk_table(tw, &_head, A::ZERO(), 0, topbit);
00044     };
00045 
00046     bool insert(const IPNet<A>& net, TriePayload& p);
00047     bool insert(A address, size_t mask_length, TriePayload& p);
00048     void del() {
00049     del(&_head);
00050     }
00051     bool del(const IPNet<A>& net);
00052     bool del(A address, size_t mask_length);
00053     TriePayload find(const IPNet<A>& net) const;
00054     TriePayload find(A address, size_t mask_length) const;
00055     TriePayload find(const A& address) const;
00056 private:
00057     struct Tree {
00058     Tree *ptrs[2];
00059     TriePayload p;
00060 
00061     Tree() {
00062         ptrs[0] = ptrs[1] = 0;
00063     }
00064     };
00065 
00066     void tree_walk_table(const TreeWalker&, const Tree *ptr, 
00067              A address, size_t prefix_len, A orbit) const;
00068     void del(Tree *ptr);
00069     bool del(Tree *ptr, A address, size_t mask_length);
00070     
00071     bool _debug;
00072     bool _pretty;
00073 
00074     Tree _head;
00075 };
00076 
00077 template <class A>
00078 RealTrie<A>::~RealTrie()
00079 {
00080     del(&_head);
00081 }
00082 
00083 template <class A>
00084 bool
00085 RealTrie<A>::empty() const
00086 {
00087     return (0 ==_head.ptrs[0]) && (0 ==_head.ptrs[1]);
00088 }
00089 
00090 template <class A>
00091 void
00092 RealTrie<A>::tree_walk_table(const TreeWalker& tw, const Tree *ptr,
00093                  A address, size_t prefix_len, A orbit) const
00094 {
00095     debug_msg("Enter: %s/%u\n", address.str().c_str(),
00096           XORP_UINT_CAST(prefix_len));
00097 
00098     if(0 == ptr) {
00099     return;
00100     }
00101 
00102     TimeVal tv;
00103     const UpdatePacket *update = ptr->p.get(tv);
00104     if(0 != update) {
00105     debug_msg("Found %s/%u\n", address.str().c_str(),
00106           XORP_UINT_CAST(prefix_len));
00107     tw->dispatch(update, IPNet<A>(address, prefix_len), tv);
00108     }
00109 
00110     ++prefix_len;
00111     A save_orbit = orbit;
00112     orbit = orbit >> 1;
00113 
00114     tree_walk_table(tw, ptr->ptrs[0], address, prefix_len, orbit);
00115 
00116     address = address | save_orbit;
00117     tree_walk_table(tw, ptr->ptrs[1], address, prefix_len, orbit);
00118 }
00119 
00120 template <class A>
00121 bool
00122 RealTrie<A>::insert(const IPNet<A>& net, TriePayload& p)
00123 {
00124     return insert(net.masked_addr(), net.prefix_len(), p);
00125 }
00126 
00127 template <class A>
00128 bool
00129 RealTrie<A>::insert(A address, size_t mask_length, TriePayload& p)
00130 {
00131     debug_msg("%s/%u\n", address.str().c_str(),
00132           XORP_UINT_CAST(mask_length));
00133 #ifdef  PARANOIA
00134     if(0 == p.get()) {
00135     debug_msg("insert: Attempt to store an invalid entry\n");
00136     return false;
00137     }
00138 #endif
00139     Tree *ptr = &_head;
00140     for(size_t i = 0; i < mask_length; i++) {
00141     int index;
00142     if(address.bits(A::addr_bitlen() - 1, 1))
00143         index = 1;
00144     else
00145         index = 0;
00146     address = address << 1;
00147 
00148     debug_msg("address %s prefix_len %u depth %u index %d\n",
00149           address.str().c_str(), XORP_UINT_CAST(mask_length), 
00150           XORP_UINT_CAST(i), index);
00151 
00152     
00153     if(0 == ptr->ptrs[index]) {
00154         ptr->ptrs[index] = new Tree();
00155         if(0 == ptr->ptrs[index]) {
00156         if(_debug)
00157             debug_msg("insert: new failed\n");
00158         return false;
00159         }
00160     }
00161 
00162     ptr = ptr->ptrs[index];
00163     }
00164 
00165     if(0 != ptr->p.get()) {
00166     debug_msg("insert: value already assigned\n");
00167     return false;
00168     }
00169 
00170     ptr->p = p;
00171 
00172     return true;
00173 }
00174 
00175 template <class A>
00176 void
00177 RealTrie<A>::del(Tree *ptr)
00178 {
00179     if(0 == ptr)
00180     return;
00181     del(ptr->ptrs[0]);
00182     delete ptr->ptrs[0];
00183     ptr->ptrs[0] = 0;
00184     del(ptr->ptrs[1]);
00185     delete ptr->ptrs[1];
00186     ptr->ptrs[1] = 0;
00187 }
00188 
00189 template <class A>
00190 bool
00191 RealTrie<A>::del(const IPNet<A>& net)
00192 {
00193     return del(net.masked_addr(), net.prefix_len());
00194 }
00195 
00196 template <class A>
00197 bool
00198 RealTrie<A>::del(A address, size_t mask_length)
00199 {
00200     return del(&_head, address, mask_length);
00201 }
00202 
00203 template <class A>
00204 bool
00205 RealTrie<A>::del(Tree *ptr, A address, size_t mask_length)
00206 {
00207     if((0 == ptr) && (0 != mask_length)) {
00208     if(_debug)
00209         debug_msg("del:1 not in table\n");
00210     return false;
00211     }
00212     int index;
00213     if(address.bits(A::addr_bitlen() - 1, 1))
00214     index = 1;
00215     else
00216     index = 0;
00217     address = address << 1;
00218 
00219     if(0 == mask_length) {
00220     if(0 == ptr) {
00221         if(_debug)
00222         debug_msg("del:1 zero pointer\n");
00223         return false;
00224     }
00225     if(0 == ptr->p.get()) {
00226         if(_debug)
00227         debug_msg("del:2 not in table\n");
00228         return false;
00229     }
00230     ptr->p = TriePayload(); // Invalidate this entry.
00231     return true;
00232     }
00233 
00234     if(0 == ptr) {
00235     if(_debug)
00236         debug_msg("del:2 zero pointer\n");
00237     return false;
00238     }
00239 
00240     Tree *next = ptr->ptrs[index];
00241 
00242     bool status = del(next, address, --mask_length);
00243 
00244     if(0 == next) {
00245     if(_debug)
00246         debug_msg("del: no next pointer\n");
00247     return false;
00248     }
00249 
00250     if((0 == next->p.get()) && (0 == next->ptrs[0]) &&
00251        (0 == next->ptrs[1])) {
00252     delete ptr->ptrs[index];
00253     ptr->ptrs[index] = 0;
00254     }
00255 
00256     return status;
00257 }
00258 
00259 template <class A>
00260 TriePayload 
00261 RealTrie<A>::find(const IPNet<A>& net) const
00262 {
00263     return find(net.masked_addr(), net.prefix_len());
00264 }
00265 
00266 template <class A>
00267 TriePayload 
00268 RealTrie<A>::find(A address, size_t mask_length) const
00269 {
00270     const Tree *ptr = &_head;
00271     Tree *next;
00272 
00273     debug_msg("find: %s/%u\n", address.str().c_str(), 
00274           XORP_UINT_CAST(mask_length));
00275 
00276     // The loop should not require bounding. Defensive
00277     for(size_t i = 0; i <= A::addr_bitlen(); i++) {
00278     int index;
00279     if(address.bits(A::addr_bitlen() - 1, 1))
00280         index = 1;
00281     else
00282         index = 0;
00283     address = address << 1;
00284 
00285     if(_pretty)
00286         debug_msg("%d", index);
00287     TriePayload p = ptr->p;
00288     if(mask_length == i)
00289         return p;
00290     if(0 == (next = ptr->ptrs[index])) {
00291         if(_pretty)
00292         debug_msg("\n");
00293         return TriePayload();
00294     }
00295     ptr = next;
00296     }
00297     debug_msg("find: should never happen\n");
00298     return TriePayload();
00299 }
00300 #endif // __BGP_HARNESS_REAL_TRIE_HH_
 All Classes Namespaces Functions Variables Typedefs Enumerations