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