Branch data     Line data    Source code

       1                 :            : // $Id: PrefixTable.h 969 2005-01-04 06:36:21Z vern $
       2                 :            : 
       3                 :            : #ifndef PREFIXTABLE_H
       4                 :            : #define PREFIXTABLE_H
       5                 :            : 
       6                 :            : #include "Val.h"
       7                 :            : #include "net_util.h"
       8                 :            : 
       9                 :            : extern "C" {
      10                 :            :         #include "patricia.h"
      11                 :            : }
      12                 :            : 
      13                 :            : class PrefixTable {
      14                 :            : private:
      15                 :            :         struct iterator {
      16                 :            :                 patricia_node_t* Xstack[PATRICIA_MAXBITS+1];
      17                 :            :                 patricia_node_t** Xsp;
      18                 :            :                 patricia_node_t* Xrn;
      19                 :            :                 patricia_node_t* Xnode;
      20                 :            :         };
      21                 :            : 
      22                 :            : public:
      23                 :         24 :         PrefixTable()   { tree = New_Patricia(128); }
      24                 :          0 :         ~PrefixTable()  { Destroy_Patricia(tree, 0); }
      25                 :            : 
      26                 :            :         // Addr in network byte order. If data is zero, acts like a set.
      27                 :            :         // Returns ptr to old data if already existing.
      28                 :            :         // For existing items without data, returns non-nil if found.
      29                 :            :         void* Insert(const_addr_type addr, int width, void* data = 0);
      30                 :            : 
      31                 :            :         // Value may be addr or subnet.
      32                 :            :         void* Insert(const Val* value, void* data = 0);
      33                 :            : 
      34                 :            :         // Returns nil if not found, pointer to data otherwise.
      35                 :            :         // For items without data, returns non-nil if found.
      36                 :            :         // If exact is false, performs exact rather than longest-prefix match.
      37                 :            :         void* Lookup(const_addr_type addr, int width, bool exact = false) const;
      38                 :            :         void* Lookup(const Val* value, bool exact = false) const;
      39                 :            : 
      40                 :            :         // Returns pointer to data or nil if not found.
      41                 :            :         void* Remove(const_addr_type addr, int width);
      42                 :            :         void* Remove(const Val* value);
      43                 :            : 
      44                 :            :         void Clear()    { Clear_Patricia(tree, 0); }
      45                 :            : 
      46                 :            :         iterator InitIterator();
      47                 :            :         void* GetNext(iterator* i);
      48                 :            : 
      49                 :            :         patricia_tree_t* tree;
      50                 :            : };
      51                 :            : 
      52                 :            : #endif