Branch data Line data Source code
1 : : // $Id: PrefixTable.cc 1016 2005-01-31 21:23:50Z vern $
2 : :
3 : : #include "PrefixTable.h"
4 : :
5 : : // IPv4 version.
6 : 4235 : inline static prefix_t* make_prefix(const uint32 addr, int width)
7 : : {
8 : 4235 : prefix_t* prefix = (prefix_t*) safe_malloc(sizeof(prefix_t));
9 : :
10 : 4235 : memcpy(&prefix->add.sin, &addr, sizeof(prefix->add.sin)) ;
11 : 4235 : prefix->family = AF_INET;
12 : 4235 : prefix->bitlen = width;
13 : 4235 : prefix->ref_count = 1;
14 : :
15 : 4235 : return prefix;
16 : : }
17 : :
18 : : #ifdef BROv6
19 : : inline static prefix_t* make_prefix(const uint32* addr, int width)
20 : : {
21 : : prefix_t* prefix = (prefix_t*) safe_malloc(sizeof(prefix_t));
22 : :
23 : : memcpy(&prefix->add.sin6, addr, 4 * sizeof(uint32));
24 : : prefix->family = AF_INET6;
25 : : prefix->bitlen = width;
26 : : prefix->ref_count = 1;
27 : :
28 : : return prefix;
29 : : }
30 : : #endif
31 : :
32 : 14 : void* PrefixTable::Insert(const_addr_type addr, int width, void* data)
33 : : {
34 : 14 : prefix_t* prefix = make_prefix(addr, width);
35 : 14 : patricia_node_t* node = patricia_lookup(tree, prefix);
36 : 14 : Deref_Prefix(prefix);
37 : :
38 [ - + ]: 14 : if ( ! node )
39 : 0 : internal_error("Cannot create node in patricia tree");
40 : :
41 : 14 : void* old = node->data;
42 : :
43 : : // If there is no data to be associated with addr, we take the
44 : : // node itself.
45 [ + - ]: 14 : node->data = data ? data : node;
46 : :
47 : 14 : return old;
48 : : }
49 : :
50 : 14 : void* PrefixTable::Insert(const Val* value, void* data)
51 : : {
52 : : // [elem] -> elem
53 [ + + ][ + - ]: 14 : if ( value->Type()->Tag() == TYPE_LIST &&
[ + + ]
54 : : value->AsListVal()->Length() == 1 )
55 : 1 : value = value->AsListVal()->Index(0);
56 : :
57 [ - + - ]: 14 : switch ( value->Type()->Tag() ) {
58 : : case TYPE_ADDR:
59 : 0 : return Insert(value->AsAddr(), NUM_ADDR_WORDS * 32, data);
60 : : break;
61 : :
62 : : case TYPE_SUBNET:
63 : : return Insert(value->AsSubNet()->net,
64 : 14 : value->AsSubNet()->width, data);
65 : : break;
66 : :
67 : : default:
68 : 14 : internal_error("Wrong index type for PrefixTable");
69 : : return 0;
70 : : }
71 : : }
72 : :
73 : 4221 : void* PrefixTable::Lookup(const_addr_type addr, int width, bool exact) const
74 : : {
75 : 4221 : prefix_t* prefix = make_prefix(addr, width);
76 : : patricia_node_t* node =
77 : : exact ? patricia_search_exact(tree, prefix) :
78 [ + + ]: 4221 : patricia_search_best(tree, prefix);
79 : :
80 : 4221 : Deref_Prefix(prefix);
81 [ - + ]: 4221 : return node ? node->data : 0;
82 : : }
83 : :
84 : 4221 : void* PrefixTable::Lookup(const Val* value, bool exact) const
85 : : {
86 : : // [elem] -> elem
87 [ + + ][ + - ]: 4221 : if ( value->Type()->Tag() == TYPE_LIST &&
[ + + ]
88 : : value->AsListVal()->Length() == 1 )
89 : 1 : value = value->AsListVal()->Index(0);
90 : :
91 [ + + - ]: 4221 : switch ( value->Type()->Tag() ) {
92 : : case TYPE_ADDR:
93 : 4207 : return Lookup(value->AsAddr(), NUM_ADDR_WORDS * 32, exact);
94 : : break;
95 : :
96 : : case TYPE_SUBNET:
97 : : return Lookup(value->AsSubNet()->net,
98 : 14 : value->AsSubNet()->width, exact);
99 : : break;
100 : :
101 : : default:
102 : : internal_error(fmt("Wrong index type %d for PrefixTable",
103 : 4221 : value->Type()->Tag()));
104 : : return 0;
105 : : }
106 : : }
107 : :
108 : 0 : void* PrefixTable::Remove(const_addr_type addr, int width)
109 : : {
110 : 0 : prefix_t* prefix = make_prefix(addr, width);
111 : 0 : patricia_node_t* node = patricia_search_exact(tree, prefix);
112 : 0 : Deref_Prefix(prefix);
113 : :
114 [ # # ]: 0 : if ( ! node )
115 : 0 : return 0;
116 : :
117 : 0 : void* old = node->data;
118 : 0 : patricia_remove(tree, node);
119 : :
120 : 0 : return old;
121 : : }
122 : :
123 : 0 : void* PrefixTable::Remove(const Val* value)
124 : : {
125 : : // [elem] -> elem
126 [ # # ][ # # ]: 0 : if ( value->Type()->Tag() == TYPE_LIST &&
[ # # ]
127 : : value->AsListVal()->Length() == 1 )
128 : 0 : value = value->AsListVal()->Index(0);
129 : :
130 [ # # # ]: 0 : switch ( value->Type()->Tag() ) {
131 : : case TYPE_ADDR:
132 : 0 : return Remove(value->AsAddr(), NUM_ADDR_WORDS * 32);
133 : : break;
134 : :
135 : : case TYPE_SUBNET:
136 : 0 : return Remove(value->AsSubNet()->net, value->AsSubNet()->width);
137 : : break;
138 : :
139 : : default:
140 : 0 : internal_error("Wrong index type for PrefixTable");
141 : : return 0;
142 : : }
143 : : }
144 : :
145 : 0 : PrefixTable::iterator PrefixTable::InitIterator()
146 : : {
147 : : iterator i;
148 : 0 : i.Xsp = i.Xstack;
149 : 0 : i.Xrn = tree->head;
150 : 0 : i.Xnode = 0;
151 : : return i;
152 : : }
153 : :
154 : 0 : void* PrefixTable::GetNext(iterator* i)
155 : : {
156 : 0 : while ( 1 )
157 : : {
158 : 0 : i->Xnode = i->Xrn;
159 [ # # ]: 0 : if ( ! i->Xnode )
160 : 0 : return 0;
161 : :
162 [ # # ]: 0 : if ( i->Xrn->l )
163 : : {
164 [ # # ]: 0 : if (i->Xrn->r)
165 : 0 : *i->Xsp++ = i->Xrn->r;
166 : :
167 : 0 : i->Xrn = i->Xrn->l;
168 : : }
169 : :
170 [ # # ]: 0 : else if ( i->Xrn->r )
171 : 0 : i->Xrn = i->Xrn->r;
172 : :
173 [ # # ]: 0 : else if (i->Xsp != i->Xstack)
174 : 0 : i->Xrn = *(--i->Xsp);
175 : :
176 : : else
177 : 0 : i->Xrn = (patricia_node_t*) 0;
178 : :
179 [ # # ]: 0 : if ( i->Xnode->prefix )
180 : 0 : return (void*) i->Xnode->data;
181 : : }
182 : :
183 : : // Not reached.
184 [ + - ][ + - ]: 6 : }
|
