Jake Slack | 03928ae | 2014-05-13 18:41:56 -0700 | [diff] [blame] | 1 | // |
| 2 | // ======================================================================== |
| 3 | // Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd. |
| 4 | // ------------------------------------------------------------------------ |
| 5 | // All rights reserved. This program and the accompanying materials |
| 6 | // are made available under the terms of the Eclipse Public License v1.0 |
| 7 | // and Apache License v2.0 which accompanies this distribution. |
| 8 | // |
| 9 | // The Eclipse Public License is available at |
| 10 | // http://www.eclipse.org/legal/epl-v10.html |
| 11 | // |
| 12 | // The Apache License v2.0 is available at |
| 13 | // http://www.opensource.org/licenses/apache2.0.php |
| 14 | // |
| 15 | // You may elect to redistribute this code under either of these licenses. |
| 16 | // ======================================================================== |
| 17 | // |
| 18 | |
| 19 | package org.eclipse.jetty.util; |
| 20 | |
| 21 | import java.io.Externalizable; |
| 22 | import java.util.AbstractMap; |
| 23 | import java.util.Collections; |
| 24 | import java.util.HashMap; |
| 25 | import java.util.HashSet; |
| 26 | import java.util.Map; |
| 27 | import java.util.Set; |
| 28 | |
| 29 | /* ------------------------------------------------------------ */ |
| 30 | /** Map implementation Optimized for Strings keys.. |
| 31 | * This String Map has been optimized for mapping small sets of |
| 32 | * Strings where the most frequently accessed Strings have been put to |
| 33 | * the map first. |
| 34 | * |
| 35 | * It also has the benefit that it can look up entries by substring or |
| 36 | * sections of char and byte arrays. This can prevent many String |
| 37 | * objects from being created just to look up in the map. |
| 38 | * |
| 39 | * This map is NOT synchronized. |
| 40 | */ |
| 41 | public class StringMap extends AbstractMap implements Externalizable |
| 42 | { |
| 43 | public static final boolean CASE_INSENSTIVE=true; |
| 44 | protected static final int __HASH_WIDTH=17; |
| 45 | |
| 46 | /* ------------------------------------------------------------ */ |
| 47 | protected int _width=__HASH_WIDTH; |
| 48 | protected Node _root=new Node(); |
| 49 | protected boolean _ignoreCase=false; |
| 50 | protected NullEntry _nullEntry=null; |
| 51 | protected Object _nullValue=null; |
| 52 | protected HashSet _entrySet=new HashSet(3); |
| 53 | protected Set _umEntrySet=Collections.unmodifiableSet(_entrySet); |
| 54 | |
| 55 | /* ------------------------------------------------------------ */ |
| 56 | /** Constructor. |
| 57 | */ |
| 58 | public StringMap() |
| 59 | {} |
| 60 | |
| 61 | /* ------------------------------------------------------------ */ |
| 62 | /** Constructor. |
| 63 | * @param ignoreCase |
| 64 | */ |
| 65 | public StringMap(boolean ignoreCase) |
| 66 | { |
| 67 | this(); |
| 68 | _ignoreCase=ignoreCase; |
| 69 | } |
| 70 | |
| 71 | /* ------------------------------------------------------------ */ |
| 72 | /** Constructor. |
| 73 | * @param ignoreCase |
| 74 | * @param width Width of hash tables, larger values are faster but |
| 75 | * use more memory. |
| 76 | */ |
| 77 | public StringMap(boolean ignoreCase,int width) |
| 78 | { |
| 79 | this(); |
| 80 | _ignoreCase=ignoreCase; |
| 81 | _width=width; |
| 82 | } |
| 83 | |
| 84 | /* ------------------------------------------------------------ */ |
| 85 | /** Set the ignoreCase attribute. |
| 86 | * @param ic If true, the map is case insensitive for keys. |
| 87 | */ |
| 88 | public void setIgnoreCase(boolean ic) |
| 89 | { |
| 90 | if (_root._children!=null) |
| 91 | throw new IllegalStateException("Must be set before first put"); |
| 92 | _ignoreCase=ic; |
| 93 | } |
| 94 | |
| 95 | /* ------------------------------------------------------------ */ |
| 96 | public boolean isIgnoreCase() |
| 97 | { |
| 98 | return _ignoreCase; |
| 99 | } |
| 100 | |
| 101 | /* ------------------------------------------------------------ */ |
| 102 | /** Set the hash width. |
| 103 | * @param width Width of hash tables, larger values are faster but |
| 104 | * use more memory. |
| 105 | */ |
| 106 | public void setWidth(int width) |
| 107 | { |
| 108 | _width=width; |
| 109 | } |
| 110 | |
| 111 | /* ------------------------------------------------------------ */ |
| 112 | public int getWidth() |
| 113 | { |
| 114 | return _width; |
| 115 | } |
| 116 | |
| 117 | /* ------------------------------------------------------------ */ |
| 118 | @Override |
| 119 | public Object put(Object key, Object value) |
| 120 | { |
| 121 | if (key==null) |
| 122 | return put(null,value); |
| 123 | return put(key.toString(),value); |
| 124 | } |
| 125 | |
| 126 | /* ------------------------------------------------------------ */ |
| 127 | public Object put(String key, Object value) |
| 128 | { |
| 129 | if (key==null) |
| 130 | { |
| 131 | Object oldValue=_nullValue; |
| 132 | _nullValue=value; |
| 133 | if (_nullEntry==null) |
| 134 | { |
| 135 | _nullEntry=new NullEntry(); |
| 136 | _entrySet.add(_nullEntry); |
| 137 | } |
| 138 | return oldValue; |
| 139 | } |
| 140 | |
| 141 | Node node = _root; |
| 142 | int ni=-1; |
| 143 | Node prev = null; |
| 144 | Node parent = null; |
| 145 | |
| 146 | // look for best match |
| 147 | charLoop: |
| 148 | for (int i=0;i<key.length();i++) |
| 149 | { |
| 150 | char c=key.charAt(i); |
| 151 | |
| 152 | // Advance node |
| 153 | if (ni==-1) |
| 154 | { |
| 155 | parent=node; |
| 156 | prev=null; |
| 157 | ni=0; |
| 158 | node=(node._children==null)?null:node._children[c%_width]; |
| 159 | } |
| 160 | |
| 161 | // Loop through a node chain at the same level |
| 162 | while (node!=null) |
| 163 | { |
| 164 | // If it is a matching node, goto next char |
| 165 | if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c) |
| 166 | { |
| 167 | prev=null; |
| 168 | ni++; |
| 169 | if (ni==node._char.length) |
| 170 | ni=-1; |
| 171 | continue charLoop; |
| 172 | } |
| 173 | |
| 174 | // no char match |
| 175 | // if the first char, |
| 176 | if (ni==0) |
| 177 | { |
| 178 | // look along the chain for a char match |
| 179 | prev=node; |
| 180 | node=node._next; |
| 181 | } |
| 182 | else |
| 183 | { |
| 184 | // Split the current node! |
| 185 | node.split(this,ni); |
| 186 | i--; |
| 187 | ni=-1; |
| 188 | continue charLoop; |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | // We have run out of nodes, so as this is a put, make one |
| 193 | node = new Node(_ignoreCase,key,i); |
| 194 | |
| 195 | if (prev!=null) // add to end of chain |
| 196 | prev._next=node; |
| 197 | else if (parent!=null) // add new child |
| 198 | { |
| 199 | if (parent._children==null) |
| 200 | parent._children=new Node[_width]; |
| 201 | parent._children[c%_width]=node; |
| 202 | int oi=node._ochar[0]%_width; |
| 203 | if (node._ochar!=null && node._char[0]%_width!=oi) |
| 204 | { |
| 205 | if (parent._children[oi]==null) |
| 206 | parent._children[oi]=node; |
| 207 | else |
| 208 | { |
| 209 | Node n=parent._children[oi]; |
| 210 | while(n._next!=null) |
| 211 | n=n._next; |
| 212 | n._next=node; |
| 213 | } |
| 214 | } |
| 215 | } |
| 216 | else // this is the root. |
| 217 | _root=node; |
| 218 | break; |
| 219 | } |
| 220 | |
| 221 | // Do we have a node |
| 222 | if (node!=null) |
| 223 | { |
| 224 | // Split it if we are in the middle |
| 225 | if(ni>0) |
| 226 | node.split(this,ni); |
| 227 | |
| 228 | Object old = node._value; |
| 229 | node._key=key; |
| 230 | node._value=value; |
| 231 | _entrySet.add(node); |
| 232 | return old; |
| 233 | } |
| 234 | return null; |
| 235 | } |
| 236 | |
| 237 | /* ------------------------------------------------------------ */ |
| 238 | @Override |
| 239 | public Object get(Object key) |
| 240 | { |
| 241 | if (key==null) |
| 242 | return _nullValue; |
| 243 | if (key instanceof String) |
| 244 | return get((String)key); |
| 245 | return get(key.toString()); |
| 246 | } |
| 247 | |
| 248 | /* ------------------------------------------------------------ */ |
| 249 | public Object get(String key) |
| 250 | { |
| 251 | if (key==null) |
| 252 | return _nullValue; |
| 253 | |
| 254 | Map.Entry entry = getEntry(key,0,key.length()); |
| 255 | if (entry==null) |
| 256 | return null; |
| 257 | return entry.getValue(); |
| 258 | } |
| 259 | |
| 260 | /* ------------------------------------------------------------ */ |
| 261 | /** Get a map entry by substring key. |
| 262 | * @param key String containing the key |
| 263 | * @param offset Offset of the key within the String. |
| 264 | * @param length The length of the key |
| 265 | * @return The Map.Entry for the key or null if the key is not in |
| 266 | * the map. |
| 267 | */ |
| 268 | public Map.Entry getEntry(String key,int offset, int length) |
| 269 | { |
| 270 | if (key==null) |
| 271 | return _nullEntry; |
| 272 | |
| 273 | Node node = _root; |
| 274 | int ni=-1; |
| 275 | |
| 276 | // look for best match |
| 277 | charLoop: |
| 278 | for (int i=0;i<length;i++) |
| 279 | { |
| 280 | char c=key.charAt(offset+i); |
| 281 | |
| 282 | // Advance node |
| 283 | if (ni==-1) |
| 284 | { |
| 285 | ni=0; |
| 286 | node=(node._children==null)?null:node._children[c%_width]; |
| 287 | } |
| 288 | |
| 289 | // Look through the node chain |
| 290 | while (node!=null) |
| 291 | { |
| 292 | // If it is a matching node, goto next char |
| 293 | if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c) |
| 294 | { |
| 295 | ni++; |
| 296 | if (ni==node._char.length) |
| 297 | ni=-1; |
| 298 | continue charLoop; |
| 299 | } |
| 300 | |
| 301 | // No char match, so if mid node then no match at all. |
| 302 | if (ni>0) return null; |
| 303 | |
| 304 | // try next in chain |
| 305 | node=node._next; |
| 306 | } |
| 307 | return null; |
| 308 | } |
| 309 | |
| 310 | if (ni>0) return null; |
| 311 | if (node!=null && node._key==null) |
| 312 | return null; |
| 313 | return node; |
| 314 | } |
| 315 | |
| 316 | /* ------------------------------------------------------------ */ |
| 317 | /** Get a map entry by char array key. |
| 318 | * @param key char array containing the key |
| 319 | * @param offset Offset of the key within the array. |
| 320 | * @param length The length of the key |
| 321 | * @return The Map.Entry for the key or null if the key is not in |
| 322 | * the map. |
| 323 | */ |
| 324 | public Map.Entry getEntry(char[] key,int offset, int length) |
| 325 | { |
| 326 | if (key==null) |
| 327 | return _nullEntry; |
| 328 | |
| 329 | Node node = _root; |
| 330 | int ni=-1; |
| 331 | |
| 332 | // look for best match |
| 333 | charLoop: |
| 334 | for (int i=0;i<length;i++) |
| 335 | { |
| 336 | char c=key[offset+i]; |
| 337 | |
| 338 | // Advance node |
| 339 | if (ni==-1) |
| 340 | { |
| 341 | ni=0; |
| 342 | node=(node._children==null)?null:node._children[c%_width]; |
| 343 | } |
| 344 | |
| 345 | // While we have a node to try |
| 346 | while (node!=null) |
| 347 | { |
| 348 | // If it is a matching node, goto next char |
| 349 | if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c) |
| 350 | { |
| 351 | ni++; |
| 352 | if (ni==node._char.length) |
| 353 | ni=-1; |
| 354 | continue charLoop; |
| 355 | } |
| 356 | |
| 357 | // No char match, so if mid node then no match at all. |
| 358 | if (ni>0) return null; |
| 359 | |
| 360 | // try next in chain |
| 361 | node=node._next; |
| 362 | } |
| 363 | return null; |
| 364 | } |
| 365 | |
| 366 | if (ni>0) return null; |
| 367 | if (node!=null && node._key==null) |
| 368 | return null; |
| 369 | return node; |
| 370 | } |
| 371 | |
| 372 | /* ------------------------------------------------------------ */ |
| 373 | /** Get a map entry by byte array key, using as much of the passed key as needed for a match. |
| 374 | * A simple 8859-1 byte to char mapping is assumed. |
| 375 | * @param key char array containing the key |
| 376 | * @param offset Offset of the key within the array. |
| 377 | * @param maxLength The length of the key |
| 378 | * @return The Map.Entry for the key or null if the key is not in |
| 379 | * the map. |
| 380 | */ |
| 381 | public Map.Entry getBestEntry(byte[] key,int offset, int maxLength) |
| 382 | { |
| 383 | if (key==null) |
| 384 | return _nullEntry; |
| 385 | |
| 386 | Node node = _root; |
| 387 | int ni=-1; |
| 388 | |
| 389 | // look for best match |
| 390 | charLoop: |
| 391 | for (int i=0;i<maxLength;i++) |
| 392 | { |
| 393 | char c=(char)key[offset+i]; |
| 394 | |
| 395 | // Advance node |
| 396 | if (ni==-1) |
| 397 | { |
| 398 | ni=0; |
| 399 | |
| 400 | Node child = (node._children==null)?null:node._children[c%_width]; |
| 401 | |
| 402 | if (child==null && i>0) |
| 403 | return node; // This is the best match |
| 404 | node=child; |
| 405 | } |
| 406 | |
| 407 | // While we have a node to try |
| 408 | while (node!=null) |
| 409 | { |
| 410 | // If it is a matching node, goto next char |
| 411 | if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c) |
| 412 | { |
| 413 | ni++; |
| 414 | if (ni==node._char.length) |
| 415 | ni=-1; |
| 416 | continue charLoop; |
| 417 | } |
| 418 | |
| 419 | // No char match, so if mid node then no match at all. |
| 420 | if (ni>0) return null; |
| 421 | |
| 422 | // try next in chain |
| 423 | node=node._next; |
| 424 | } |
| 425 | return null; |
| 426 | } |
| 427 | |
| 428 | if (ni>0) return null; |
| 429 | if (node!=null && node._key==null) |
| 430 | return null; |
| 431 | return node; |
| 432 | } |
| 433 | |
| 434 | |
| 435 | /* ------------------------------------------------------------ */ |
| 436 | @Override |
| 437 | public Object remove(Object key) |
| 438 | { |
| 439 | if (key==null) |
| 440 | return remove(null); |
| 441 | return remove(key.toString()); |
| 442 | } |
| 443 | |
| 444 | /* ------------------------------------------------------------ */ |
| 445 | public Object remove(String key) |
| 446 | { |
| 447 | if (key==null) |
| 448 | { |
| 449 | Object oldValue=_nullValue; |
| 450 | if (_nullEntry!=null) |
| 451 | { |
| 452 | _entrySet.remove(_nullEntry); |
| 453 | _nullEntry=null; |
| 454 | _nullValue=null; |
| 455 | } |
| 456 | return oldValue; |
| 457 | } |
| 458 | |
| 459 | Node node = _root; |
| 460 | int ni=-1; |
| 461 | |
| 462 | // look for best match |
| 463 | charLoop: |
| 464 | for (int i=0;i<key.length();i++) |
| 465 | { |
| 466 | char c=key.charAt(i); |
| 467 | |
| 468 | // Advance node |
| 469 | if (ni==-1) |
| 470 | { |
| 471 | ni=0; |
| 472 | node=(node._children==null)?null:node._children[c%_width]; |
| 473 | } |
| 474 | |
| 475 | // While we have a node to try |
| 476 | while (node!=null) |
| 477 | { |
| 478 | // If it is a matching node, goto next char |
| 479 | if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c) |
| 480 | { |
| 481 | ni++; |
| 482 | if (ni==node._char.length) |
| 483 | ni=-1; |
| 484 | continue charLoop; |
| 485 | } |
| 486 | |
| 487 | // No char match, so if mid node then no match at all. |
| 488 | if (ni>0) return null; |
| 489 | |
| 490 | // try next in chain |
| 491 | node=node._next; |
| 492 | } |
| 493 | return null; |
| 494 | } |
| 495 | |
| 496 | if (ni>0) return null; |
| 497 | if (node!=null && node._key==null) |
| 498 | return null; |
| 499 | |
| 500 | Object old = node._value; |
| 501 | _entrySet.remove(node); |
| 502 | node._value=null; |
| 503 | node._key=null; |
| 504 | |
| 505 | return old; |
| 506 | } |
| 507 | |
| 508 | /* ------------------------------------------------------------ */ |
| 509 | @Override |
| 510 | public Set entrySet() |
| 511 | { |
| 512 | return _umEntrySet; |
| 513 | } |
| 514 | |
| 515 | /* ------------------------------------------------------------ */ |
| 516 | @Override |
| 517 | public int size() |
| 518 | { |
| 519 | return _entrySet.size(); |
| 520 | } |
| 521 | |
| 522 | /* ------------------------------------------------------------ */ |
| 523 | @Override |
| 524 | public boolean isEmpty() |
| 525 | { |
| 526 | return _entrySet.isEmpty(); |
| 527 | } |
| 528 | |
| 529 | /* ------------------------------------------------------------ */ |
| 530 | @Override |
| 531 | public boolean containsKey(Object key) |
| 532 | { |
| 533 | if (key==null) |
| 534 | return _nullEntry!=null; |
| 535 | return |
| 536 | getEntry(key.toString(),0,key==null?0:key.toString().length())!=null; |
| 537 | } |
| 538 | |
| 539 | /* ------------------------------------------------------------ */ |
| 540 | @Override |
| 541 | public void clear() |
| 542 | { |
| 543 | _root=new Node(); |
| 544 | _nullEntry=null; |
| 545 | _nullValue=null; |
| 546 | _entrySet.clear(); |
| 547 | } |
| 548 | |
| 549 | |
| 550 | /* ------------------------------------------------------------ */ |
| 551 | /* ------------------------------------------------------------ */ |
| 552 | /* ------------------------------------------------------------ */ |
| 553 | private static class Node implements Map.Entry |
| 554 | { |
| 555 | char[] _char; |
| 556 | char[] _ochar; |
| 557 | Node _next; |
| 558 | Node[] _children; |
| 559 | String _key; |
| 560 | Object _value; |
| 561 | |
| 562 | Node(){} |
| 563 | |
| 564 | Node(boolean ignoreCase,String s, int offset) |
| 565 | { |
| 566 | int l=s.length()-offset; |
| 567 | _char=new char[l]; |
| 568 | _ochar=new char[l]; |
| 569 | for (int i=0;i<l;i++) |
| 570 | { |
| 571 | char c=s.charAt(offset+i); |
| 572 | _char[i]=c; |
| 573 | if (ignoreCase) |
| 574 | { |
| 575 | char o=c; |
| 576 | if (Character.isUpperCase(c)) |
| 577 | o=Character.toLowerCase(c); |
| 578 | else if (Character.isLowerCase(c)) |
| 579 | o=Character.toUpperCase(c); |
| 580 | _ochar[i]=o; |
| 581 | } |
| 582 | } |
| 583 | } |
| 584 | |
| 585 | Node split(StringMap map,int offset) |
| 586 | { |
| 587 | Node split = new Node(); |
| 588 | int sl=_char.length-offset; |
| 589 | |
| 590 | char[] tmp=this._char; |
| 591 | this._char=new char[offset]; |
| 592 | split._char = new char[sl]; |
| 593 | System.arraycopy(tmp,0,this._char,0,offset); |
| 594 | System.arraycopy(tmp,offset,split._char,0,sl); |
| 595 | |
| 596 | if (this._ochar!=null) |
| 597 | { |
| 598 | tmp=this._ochar; |
| 599 | this._ochar=new char[offset]; |
| 600 | split._ochar = new char[sl]; |
| 601 | System.arraycopy(tmp,0,this._ochar,0,offset); |
| 602 | System.arraycopy(tmp,offset,split._ochar,0,sl); |
| 603 | } |
| 604 | |
| 605 | split._key=this._key; |
| 606 | split._value=this._value; |
| 607 | this._key=null; |
| 608 | this._value=null; |
| 609 | if (map._entrySet.remove(this)) |
| 610 | map._entrySet.add(split); |
| 611 | |
| 612 | split._children=this._children; |
| 613 | this._children=new Node[map._width]; |
| 614 | this._children[split._char[0]%map._width]=split; |
| 615 | if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split) |
| 616 | this._children[split._ochar[0]%map._width]=split; |
| 617 | |
| 618 | return split; |
| 619 | } |
| 620 | |
| 621 | public Object getKey(){return _key;} |
| 622 | public Object getValue(){return _value;} |
| 623 | public Object setValue(Object o){Object old=_value;_value=o;return old;} |
| 624 | @Override |
| 625 | public String toString() |
| 626 | { |
| 627 | StringBuilder buf=new StringBuilder(); |
| 628 | toString(buf); |
| 629 | return buf.toString(); |
| 630 | } |
| 631 | |
| 632 | private void toString(StringBuilder buf) |
| 633 | { |
| 634 | buf.append("{["); |
| 635 | if (_char==null) |
| 636 | buf.append('-'); |
| 637 | else |
| 638 | for (int i=0;i<_char.length;i++) |
| 639 | buf.append(_char[i]); |
| 640 | buf.append(':'); |
| 641 | buf.append(_key); |
| 642 | buf.append('='); |
| 643 | buf.append(_value); |
| 644 | buf.append(']'); |
| 645 | if (_children!=null) |
| 646 | { |
| 647 | for (int i=0;i<_children.length;i++) |
| 648 | { |
| 649 | buf.append('|'); |
| 650 | if (_children[i]!=null) |
| 651 | _children[i].toString(buf); |
| 652 | else |
| 653 | buf.append("-"); |
| 654 | } |
| 655 | } |
| 656 | buf.append('}'); |
| 657 | if (_next!=null) |
| 658 | { |
| 659 | buf.append(",\n"); |
| 660 | _next.toString(buf); |
| 661 | } |
| 662 | } |
| 663 | } |
| 664 | |
| 665 | /* ------------------------------------------------------------ */ |
| 666 | /* ------------------------------------------------------------ */ |
| 667 | private class NullEntry implements Map.Entry |
| 668 | { |
| 669 | public Object getKey(){return null;} |
| 670 | public Object getValue(){return _nullValue;} |
| 671 | public Object setValue(Object o) |
| 672 | {Object old=_nullValue;_nullValue=o;return old;} |
| 673 | @Override |
| 674 | public String toString(){return "[:null="+_nullValue+"]";} |
| 675 | } |
| 676 | |
| 677 | /* ------------------------------------------------------------ */ |
| 678 | public void writeExternal(java.io.ObjectOutput out) |
| 679 | throws java.io.IOException |
| 680 | { |
| 681 | HashMap map = new HashMap(this); |
| 682 | out.writeBoolean(_ignoreCase); |
| 683 | out.writeObject(map); |
| 684 | } |
| 685 | |
| 686 | /* ------------------------------------------------------------ */ |
| 687 | public void readExternal(java.io.ObjectInput in) |
| 688 | throws java.io.IOException, ClassNotFoundException |
| 689 | { |
| 690 | boolean ic=in.readBoolean(); |
| 691 | HashMap map = (HashMap)in.readObject(); |
| 692 | setIgnoreCase(ic); |
| 693 | this.putAll(map); |
| 694 | } |
| 695 | } |