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 19package org.eclipse.jetty.util; 20 21import java.io.Externalizable; 22import java.util.AbstractMap; 23import java.util.Collections; 24import java.util.HashMap; 25import java.util.HashSet; 26import java.util.Map; 27import 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 */ 41public 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} 696