Jonathan Hart | 382623d | 2014-04-03 09:48:11 -0700 | [diff] [blame] | 1 | package net.onrc.onos.apps.bgproute; |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 2 | |
Jonathan Hart | 66dffed | 2013-07-16 11:36:00 +1200 | [diff] [blame] | 3 | /* |
| 4 | * TODO This Ptree needs to be refactored if we're going to use it permenantly. |
| 5 | * |
| 6 | * The biggest problem is it leaks PTreeNode references - these need to stay within |
| 7 | * the Ptree as they contain data fundamental to the structure of the tree. |
| 8 | * You should put RIB entries in and get RIB entries out. |
| 9 | * Also we need to get rid of the referencing scheme to determine when to delete nodes. |
Ray Milkey | 5d40601 | 2014-04-08 14:44:41 -0700 | [diff] [blame] | 10 | * Deletes should be explicit, and there's no need to keep track of references if |
Jonathan Hart | 66dffed | 2013-07-16 11:36:00 +1200 | [diff] [blame] | 11 | * we don't leak them out the the Ptree. |
| 12 | */ |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 13 | public class Ptree { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 14 | private int maxKeyBits; |
| 15 | private int maxKeyOctets; |
| 16 | //private int refCount; |
| 17 | private PtreeNode top; |
Ray Milkey | 45614c5 | 2014-04-07 16:30:54 -0700 | [diff] [blame] | 18 | private byte[] maskBits = {(byte) 0x00, (byte) 0x80, (byte) 0xc0, (byte) 0xe0, (byte) 0xf0, (byte) 0xf8, (byte) 0xfc, (byte) 0xfe, (byte) 0xff}; |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 19 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 20 | public Ptree(int maxKeyBits) { |
| 21 | this.maxKeyBits = maxKeyBits; |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 22 | maxKeyOctets = bitToOctet(maxKeyBits); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 23 | //refCount = 0; |
| 24 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 25 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 26 | public synchronized PtreeNode acquire(byte[] key) { |
| 27 | return acquire(key, maxKeyBits); |
| 28 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 29 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 30 | public synchronized PtreeNode acquire(byte[] key, int keyBits) { |
| 31 | if (keyBits > maxKeyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 32 | return null; |
| 33 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 34 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 35 | PtreeNode node = top; |
| 36 | PtreeNode match = null; |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 37 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 38 | while (node != null |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 39 | && node.keyBits <= keyBits |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 40 | && keyMatch(node.key, node.keyBits, key, keyBits)) { |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 41 | if (node.keyBits == keyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 42 | return addReference(node); |
| 43 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 44 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 45 | match = node; |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 46 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 47 | if (bitCheck(key, node.keyBits)) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 48 | node = node.right; |
| 49 | } else { |
| 50 | node = node.left; |
| 51 | } |
| 52 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 53 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 54 | PtreeNode add = null; |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 55 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 56 | if (node == null) { |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 57 | add = new PtreeNode(key, keyBits, maxKeyOctets); |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 58 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 59 | if (match != null) { |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 60 | nodeLink(match, add); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 61 | } else { |
| 62 | top = add; |
| 63 | } |
| 64 | } else { |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 65 | add = nodeCommon(node, key, keyBits); |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 66 | |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 67 | if (match != null) { |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 68 | nodeLink(match, add); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 69 | } else { |
| 70 | top = add; |
| 71 | } |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 72 | nodeLink(add, node); |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 73 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 74 | if (add.keyBits != keyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 75 | match = add; |
| 76 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 77 | add = new PtreeNode(key, keyBits, maxKeyOctets); |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 78 | nodeLink(match, add); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 79 | } |
| 80 | } |
| 81 | |
| 82 | return addReference(add); |
| 83 | } |
| 84 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 85 | public synchronized PtreeNode lookup(byte[] key, int keyBits) { |
| 86 | if (keyBits > maxKeyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 87 | return null; |
| 88 | } |
| 89 | |
| 90 | PtreeNode node = top; |
| 91 | |
| 92 | while (node != null |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 93 | && node.keyBits <= keyBits |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 94 | && keyMatch(node.key, node.keyBits, key, keyBits)) { |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 95 | if (node.keyBits == keyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 96 | return addReference(node); |
| 97 | } |
| 98 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 99 | if (bitCheck(key, node.keyBits)) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 100 | node = node.right; |
| 101 | } else { |
| 102 | node = node.left; |
| 103 | } |
| 104 | } |
| 105 | return null; |
| 106 | } |
| 107 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 108 | public synchronized PtreeNode match(byte[] key, int keyBits) { |
| 109 | if (keyBits > maxKeyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 110 | return null; |
| 111 | } |
| 112 | PtreeNode node = top; |
| 113 | PtreeNode matched = null; |
| 114 | |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 115 | if (node != null) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 116 | |
| 117 | while (node != null |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 118 | && node.keyBits <= keyBits |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 119 | && keyMatch(node.key, node.keyBits, key, keyBits)) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 120 | matched = node; |
| 121 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 122 | if (bitCheck(key, node.keyBits)) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 123 | node = node.right; |
| 124 | } else { |
| 125 | node = node.left; |
| 126 | } |
| 127 | } |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 128 | } |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 129 | |
| 130 | if (matched != null) { |
| 131 | return addReference(matched); |
| 132 | } |
| 133 | |
| 134 | return null; |
| 135 | } |
| 136 | |
| 137 | public synchronized PtreeNode begin() { |
| 138 | if (top == null) { |
| 139 | return null; |
| 140 | } |
| 141 | return addReference(top); |
| 142 | } |
| 143 | |
| 144 | public synchronized PtreeNode next(PtreeNode node) { |
| 145 | PtreeNode next; |
| 146 | |
| 147 | if (node.left != null) { |
| 148 | next = node.left; |
| 149 | addReference(next); |
| 150 | delReference(node); |
| 151 | return next; |
| 152 | } |
| 153 | if (node.right != null) { |
| 154 | next = node.right; |
| 155 | addReference(next); |
| 156 | delReference(node); |
| 157 | return next; |
| 158 | } |
| 159 | |
| 160 | PtreeNode start = node; |
| 161 | while (node.parent != null) { |
| 162 | if (node.parent.left == node && node.parent.right != null) { |
| 163 | next = node.parent.right; |
| 164 | addReference(next); |
| 165 | delReference(start); |
| 166 | return next; |
| 167 | } |
| 168 | node = node.parent; |
| 169 | } |
| 170 | |
| 171 | delReference(start); |
| 172 | |
| 173 | return null; |
| 174 | } |
| 175 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 176 | public static int bitToOctet(int keyBits) { |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 177 | return Math.max((keyBits + 7) / 8, 1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 178 | } |
| 179 | |
| 180 | private PtreeNode addReference(PtreeNode node) { |
| 181 | node.refCount++; |
| 182 | return node; |
| 183 | } |
| 184 | |
| 185 | public synchronized void delReference(PtreeNode node) { |
| 186 | if (node.refCount > 0) { |
| 187 | node.refCount--; |
| 188 | } |
| 189 | if (node.refCount == 0) { |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 190 | nodeRemove(node); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 191 | } |
| 192 | } |
| 193 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 194 | private boolean keyMatch(byte[] key1, int key1Len, byte[] key2, int key2Len) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 195 | int offset; |
| 196 | int shift; |
| 197 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 198 | if (key1Len > key2Len) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 199 | return false; |
| 200 | } |
| 201 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 202 | offset = (Math.min(key1Len, key2Len)) / 8; |
| 203 | shift = (Math.min(key1Len, key2Len)) % 8; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 204 | |
| 205 | if (shift != 0) { |
| 206 | if ((maskBits[shift] & (key1[offset] ^ key2[offset])) != 0) { |
| 207 | return false; |
| 208 | } |
| 209 | } |
| 210 | |
| 211 | while (offset != 0) { |
| 212 | offset--; |
| 213 | if (key1[offset] != key2[offset]) { |
| 214 | return false; |
| 215 | } |
| 216 | } |
| 217 | return true; |
| 218 | } |
| 219 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 220 | private boolean bitCheck(byte[] key, int keyBits) { |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 221 | int offset = keyBits / 8; |
| 222 | int shift = 7 - (keyBits % 8); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 223 | int bit = key[offset] & 0xff; |
| 224 | |
| 225 | bit >>= shift; |
| 226 | |
Ray Milkey | 4985f21 | 2014-04-10 16:57:05 -0700 | [diff] [blame] | 227 | return ((bit & 1) == 1); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 228 | } |
| 229 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 230 | private void nodeLink(PtreeNode node, PtreeNode add) { |
| 231 | boolean bit = bitCheck(add.key, node.keyBits); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 232 | |
Ray Milkey | 6c4f2fe | 2014-04-11 09:47:23 -0700 | [diff] [blame] | 233 | if (bit) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 234 | node.right = add; |
| 235 | } else { |
| 236 | node.left = add; |
| 237 | } |
| 238 | add.parent = node; |
| 239 | } |
| 240 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 241 | private PtreeNode nodeCommon(PtreeNode node, byte[] key, int keyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 242 | int i; |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 243 | int limit = Math.min(node.keyBits, keyBits) / 8; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 244 | |
| 245 | for (i = 0; i < limit; i++) { |
| 246 | if (node.key[i] != key[i]) { |
| 247 | break; |
| 248 | } |
| 249 | } |
| 250 | |
Ray Milkey | 2476cac | 2014-04-08 11:03:21 -0700 | [diff] [blame] | 251 | int commonLen = i * 8; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 252 | int boundary = 0; |
| 253 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 254 | if (commonLen != keyBits) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 255 | byte diff = (byte) (node.key[i] ^ key[i]); |
| 256 | byte mask = (byte) 0x80; |
Ray Milkey | 2476cac | 2014-04-08 11:03:21 -0700 | [diff] [blame] | 257 | int shiftMask = 0; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 258 | |
Ray Milkey | 9526d6f | 2014-04-10 14:54:15 -0700 | [diff] [blame] | 259 | while (commonLen < keyBits && ((mask & diff) == 0)) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 260 | boundary = 1; |
| 261 | |
Ray Milkey | 2476cac | 2014-04-08 11:03:21 -0700 | [diff] [blame] | 262 | shiftMask = (mask & 0xff); |
| 263 | shiftMask >>= 1; |
| 264 | mask = (byte) shiftMask; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 265 | |
Ray Milkey | 2476cac | 2014-04-08 11:03:21 -0700 | [diff] [blame] | 266 | commonLen++; |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 267 | } |
| 268 | } |
| 269 | |
Ray Milkey | 2476cac | 2014-04-08 11:03:21 -0700 | [diff] [blame] | 270 | PtreeNode add = new PtreeNode(null, commonLen, maxKeyOctets); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 271 | |
| 272 | int j; |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 273 | for (j = 0; j < i; j++) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 274 | add.key[j] = node.key[j]; |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 275 | } |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 276 | |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 277 | if (boundary != 0) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 278 | add.key[j] = (byte) (node.key[j] & maskBits[add.keyBits % 8]); |
Ray Milkey | b29e626 | 2014-04-09 16:02:14 -0700 | [diff] [blame] | 279 | } |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 280 | |
| 281 | return add; |
| 282 | } |
| 283 | |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 284 | private void nodeRemove(PtreeNode node) { |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 285 | PtreeNode child; |
| 286 | PtreeNode parent; |
| 287 | |
| 288 | if (node.left != null && node.right != null) { |
| 289 | return; |
| 290 | } |
| 291 | |
| 292 | if (node.left != null) { |
| 293 | child = node.left; |
| 294 | } else { |
| 295 | child = node.right; |
| 296 | } |
| 297 | |
| 298 | parent = node.parent; |
| 299 | |
| 300 | if (child != null) { |
| 301 | child.parent = parent; |
| 302 | } |
| 303 | |
| 304 | if (parent != null) { |
| 305 | if (parent.left == node) { |
| 306 | parent.left = child; |
| 307 | } else { |
| 308 | parent.right = child; |
| 309 | } |
| 310 | } else { |
| 311 | top = child; |
| 312 | } |
| 313 | |
| 314 | if (parent != null && parent.refCount == 0) { |
Ray Milkey | 7531a34 | 2014-04-11 15:08:12 -0700 | [diff] [blame^] | 315 | nodeRemove(parent); |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 316 | } |
| 317 | } |
pingping-lin | a2cbfad | 2013-03-07 08:39:21 +0800 | [diff] [blame] | 318 | } |