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