1 //
2 // ========================================================================
3 // Copyright (c) 1995-2013 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 }