blob: dcb6e83f99dc3f7b4dcb25ba25a94041c0e69d7a [file] [log] [blame]
pingping-lina2cbfad2013-03-07 08:39:21 +08001package net.floodlightcontroller.bgproute;
2
3public class Ptree {
4 int maxKeyBits;
5 int maxKeyOctets;
6 int refCount;
7 PtreeNode top;
8 byte maskBits[] = { (byte)0x00, (byte)0x80, (byte)0xc0, (byte)0xe0, (byte)0xf0, (byte)0xf8, (byte)0xfc, (byte)0xfe, (byte)0xff };
9
10 // Constructor.
11 Ptree(int max_key_bits) {
12 maxKeyBits = max_key_bits;
13 maxKeyOctets = bit_to_octet(max_key_bits);
14 refCount = 0;
15 }
pingping-line2a09ca2013-03-23 09:33:58 +080016
pingping-lina2cbfad2013-03-07 08:39:21 +080017 public PtreeNode acquire(byte [] key) {
18 return acquire(key, maxKeyBits);
19 }
20
21 public PtreeNode acquire(byte [] key, int key_bits) {
22 if (key_bits > maxKeyBits) {
23 return null;
24 }
25
26 PtreeNode node = top;
27 PtreeNode match = null;
28
29 while (node != null
30 && node.keyBits <= key_bits
31 && key_match(node.key, node.keyBits, key, key_bits) == true) {
32 if (node.keyBits == key_bits) {
33 return addReference(node);
34 }
35
36 match = node;
37
38 if (bit_check(key, node.keyBits) == true) {
39 node = node.right;
40 } else {
41 node = node.left;
42 }
43 }
44
45 PtreeNode add = null;
46
47 if (node == null) {
48 add = new PtreeNode(key, key_bits, maxKeyOctets);
49
50 if (match != null) {
51 node_link(match, add);
52 } else {
53 top = add;
54 }
55 } else {
56 add = node_common(node, key, key_bits);
57 if (add == null) {
58 return null;
59 }
60
61 if (match != null) {
62 node_link(match, add);
63 } else {
64 top = add;
65 }
66 node_link(add, node);
67
68 if (add.keyBits != key_bits) {
69 match = add;
70
71 add = new PtreeNode(key, key_bits, maxKeyOctets);
72 node_link(match, add);
73 }
74 }
75
76 return addReference(add);
77 }
78
79 public PtreeNode lookup(byte [] key, int key_bits) {
80 if (key_bits > maxKeyBits) {
81 return null;
82 }
83
84 PtreeNode node = top;
85
86 while (node != null
87 && node.keyBits <= key_bits
88 && key_match(node.key, node.keyBits, key, key_bits) == true) {
89 if (node.keyBits == key_bits) {
90 return addReference(node);
91 }
92
93 if (bit_check(key, node.keyBits) == true) {
94 node = node.right;
95 } else {
96 node = node.left;
97 }
98 }
99 return null;
100 }
101
102 public PtreeNode match(byte [] key, int key_bits) {
103 if (key_bits > maxKeyBits) {
104 return null;
105 }
106 PtreeNode node = top;
107 PtreeNode matched = null;
108
109 if(node!=null)
110
111 while (node != null
112 && node.keyBits <= key_bits
113 && key_match(node.key, node.keyBits, key, key_bits) == true) {
114 matched = node;
115
116 if (bit_check(key, node.keyBits) == true) {
117 node = node.right;
118 } else {
119 node = node.left;
120 }
121 }
122
123 if (matched != null) {
124 return addReference(matched);
125 }
126
127 return null;
128 }
129
130 public PtreeNode begin() {
131 if (top == null) {
132 return null;
133 }
134 return addReference(top);
135 }
136
137 public PtreeNode next(PtreeNode node) {
138 PtreeNode next;
139
140 if (node.left != null) {
141 next = node.left;
142 addReference(next);
143 delReference(node);
144 return next;
145 }
146 if (node.right != null) {
147 next = node.right;
148 addReference(next);
149 delReference(node);
150 return next;
151 }
152
153 PtreeNode start = node;
154 while (node.parent != null) {
155 if (node.parent.left == node && node.parent.right != null) {
156 next = node.parent.right;
157 addReference(next);
158 delReference(start);
159 return next;
160 }
161 node = node.parent;
162 }
163
164 delReference(start);
165
166 return null;
167 }
168
169 static public int bit_to_octet(int key_bits) {
170 return Math.max((key_bits + 7) / 8, 1);
171 }
172
173 private PtreeNode addReference(PtreeNode node) {
174 node.refCount++;
175 return node;
176 }
177
178 public void delReference(PtreeNode node) {
179 if (node.refCount > 0) {
180 node.refCount--;
181 }
182 if (node.refCount == 0) {
183 node_remove(node);
184 }
185 }
186
187 private boolean key_match(byte [] key1, int key1_len, byte [] key2, int key2_len) {
188 int offset;
189 int shift;
190
191 if (key1_len > key2_len) {
192 return false;
193 }
194
195 offset = (Math.min(key1_len, key2_len)) / 8;
196 shift = (Math.min(key1_len, key2_len)) % 8;
197
198 if (shift != 0) {
199 if ((maskBits[shift] & (key1[offset] ^ key2[offset])) != 0) {
200 return false;
201 }
202 }
203
204 while (offset != 0) {
205 offset--;
206 if (key1[offset] != key2[offset]) {
207 return false;
208 }
209 }
210 return true;
211 }
212
213 private boolean bit_check(byte [] key, int key_bits) {
214 int offset = key_bits / 8;
215 int shift = 7 - (key_bits % 8);
216 int bit = key[offset] & 0xff;
217
218 bit >>= shift;
219
220 if ((bit & 1) == 1) {
221 return true;
222 } else {
223 return false;
224 }
225 }
226
227 private void node_link(PtreeNode node, PtreeNode add) {
228 boolean bit = bit_check(add.key, node.keyBits);
229
230 if (bit == true) {
231 node.right = add;
232 } else {
233 node.left = add;
234 }
235 add.parent = node;
236 }
237
238 @SuppressWarnings("unused")
239 private PtreeNode node_common(PtreeNode node, byte [] key, int key_bits) {
240 int i;
241 int limit = Math.min(node.keyBits, key_bits) / 8;
242
243 for (i = 0; i < limit; i++) {
244 if (node.key[i] != key[i]) {
245 break;
246 }
247 }
248
249 int common_len = i * 8;
250 int boundary = 0;
251
252 if (common_len != key_bits) {
253 byte diff = (byte)(node.key[i] ^ key[i]);
254 byte mask = (byte)0x80;
255 int shift_mask = 0;
256
257 while (common_len < key_bits && ((mask & diff) == 0)) {
258 boundary = 1;
259
260 shift_mask = (mask & 0xff);
261 shift_mask >>= 1;
262 mask = (byte)shift_mask;
263
264 common_len++;
265 }
266 }
267
268 PtreeNode add = new PtreeNode(null, common_len, maxKeyOctets);
269 if (add == null)
270 return null;
271
272 int j;
273 for (j = 0; j < i; j++)
274 add.key[j] = node.key[j];
275
276 if (boundary != 0)
277 add.key[j] = (byte)(node.key[j] & maskBits[add.keyBits % 8]);
278
279 return add;
280 }
pingping-line2a09ca2013-03-23 09:33:58 +0800281 //add by linpp
282 private void clear() {
283
284 }
pingping-lina2cbfad2013-03-07 08:39:21 +0800285
286 private void node_remove(PtreeNode node) {
287 PtreeNode child;
288 PtreeNode parent;
289
290 if (node.left != null && node.right != null) {
291 return;
292 }
293
294 if (node.left != null) {
295 child = node.left;
296 } else {
297 child = node.right;
298 }
299
300 parent = node.parent;
301
302 if (child != null) {
303 child.parent = parent;
304 }
305
306 if (parent != null) {
307 if (parent.left == node) {
308 parent.left = child;
309 } else {
310 parent.right = child;
311 }
312 } else {
313 top = child;
314 }
315
316 if (parent != null && parent.refCount == 0) {
317 node_remove(parent);
318 }
319 }
320}