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 public Object put(Object key, Object value)
116 {
117 if (key==null)
118 return put(null,value);
119 return put(key.toString(),value);
120 }
121
122 /* ------------------------------------------------------------ */
123 public Object put(String key, Object value)
124 {
125 if (key==null)
126 {
127 Object oldValue=_nullValue;
128 _nullValue=value;
129 if (_nullEntry==null)
130 {
131 _nullEntry=new NullEntry();
132 _entrySet.add(_nullEntry);
133 }
134 return oldValue;
135 }
136
137 Node node = _root;
138 int ni=-1;
139 Node prev = null;
140 Node parent = null;
141
142 // look for best match
143 charLoop:
144 for (int i=0;i<key.length();i++)
145 {
146 char c=key.charAt(i);
147
148 // Advance node
149 if (ni==-1)
150 {
151 parent=node;
152 prev=null;
153 ni=0;
154 node=(node._children==null)?null:node._children[c%_width];
155 }
156
157 // Loop through a node chain at the same level
158 while (node!=null)
159 {
160 // If it is a matching node, goto next char
161 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
162 {
163 prev=null;
164 ni++;
165 if (ni==node._char.length)
166 ni=-1;
167 continue charLoop;
168 }
169
170 // no char match
171 // if the first char,
172 if (ni==0)
173 {
174 // look along the chain for a char match
175 prev=node;
176 node=node._next;
177 }
178 else
179 {
180 // Split the current node!
181 node.split(this,ni);
182 i--;
183 ni=-1;
184 continue charLoop;
185 }
186 }
187
188 // We have run out of nodes, so as this is a put, make one
189 node = new Node(_ignoreCase,key,i);
190
191 if (prev!=null) // add to end of chain
192 prev._next=node;
193 else if (parent!=null) // add new child
194 {
195 if (parent._children==null)
196 parent._children=new Node[_width];
197 parent._children[c%_width]=node;
198 int oi=node._ochar[0]%_width;
199 if (node._ochar!=null && node._char[0]%_width!=oi)
200 {
201 if (parent._children[oi]==null)
202 parent._children[oi]=node;
203 else
204 {
205 Node n=parent._children[oi];
206 while(n._next!=null)
207 n=n._next;
208 n._next=node;
209 }
210 }
211 }
212 else // this is the root.
213 _root=node;
214 break;
215 }
216
217 // Do we have a node
218 if (node!=null)
219 {
220 // Split it if we are in the middle
221 if(ni>0)
222 node.split(this,ni);
223
224 Object old = node._value;
225 node._key=key;
226 node._value=value;
227 _entrySet.add(node);
228 return old;
229 }
230 return null;
231 }
232
233 /* ------------------------------------------------------------ */
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 public Object remove(Object key)
432 {
433 if (key==null)
434 return remove(null);
435 return remove(key.toString());
436 }
437
438 /* ------------------------------------------------------------ */
439 public Object remove(String key)
440 {
441 if (key==null)
442 {
443 Object oldValue=_nullValue;
444 if (_nullEntry!=null)
445 {
446 _entrySet.remove(_nullEntry);
447 _nullEntry=null;
448 _nullValue=null;
449 }
450 return oldValue;
451 }
452
453 Node node = _root;
454 int ni=-1;
455
456 // look for best match
457 charLoop:
458 for (int i=0;i<key.length();i++)
459 {
460 char c=key.charAt(i);
461
462 // Advance node
463 if (ni==-1)
464 {
465 ni=0;
466 node=(node._children==null)?null:node._children[c%_width];
467 }
468
469 // While we have a node to try
470 while (node!=null)
471 {
472 // If it is a matching node, goto next char
473 if (node._char[ni]==c || _ignoreCase&&node._ochar[ni]==c)
474 {
475 ni++;
476 if (ni==node._char.length)
477 ni=-1;
478 continue charLoop;
479 }
480
481 // No char match, so if mid node then no match at all.
482 if (ni>0) return null;
483
484 // try next in chain
485 node=node._next;
486 }
487 return null;
488 }
489
490 if (ni>0) return null;
491 if (node!=null && node._key==null)
492 return null;
493
494 Object old = node._value;
495 _entrySet.remove(node);
496 node._value=null;
497 node._key=null;
498
499 return old;
500 }
501
502 /* ------------------------------------------------------------ */
503 public Set entrySet()
504 {
505 return _umEntrySet;
506 }
507
508 /* ------------------------------------------------------------ */
509 public int size()
510 {
511 return _entrySet.size();
512 }
513
514 /* ------------------------------------------------------------ */
515 public boolean isEmpty()
516 {
517 return _entrySet.isEmpty();
518 }
519
520 /* ------------------------------------------------------------ */
521 public boolean containsKey(Object key)
522 {
523 if (key==null)
524 return _nullEntry!=null;
525 return
526 getEntry(key.toString(),0,key==null?0:key.toString().length())!=null;
527 }
528
529 /* ------------------------------------------------------------ */
530 public void clear()
531 {
532 _root=new Node();
533 _nullEntry=null;
534 _nullValue=null;
535 _entrySet.clear();
536 }
537
538
539 /* ------------------------------------------------------------ */
540 /* ------------------------------------------------------------ */
541 /* ------------------------------------------------------------ */
542 private static class Node implements Map.Entry
543 {
544 char[] _char;
545 char[] _ochar;
546 Node _next;
547 Node[] _children;
548 String _key;
549 Object _value;
550
551 Node(){}
552
553 Node(boolean ignoreCase,String s, int offset)
554 {
555 int l=s.length()-offset;
556 _char=new char[l];
557 _ochar=new char[l];
558 for (int i=0;i<l;i++)
559 {
560 char c=s.charAt(offset+i);
561 _char[i]=c;
562 if (ignoreCase)
563 {
564 char o=c;
565 if (Character.isUpperCase(c))
566 o=Character.toLowerCase(c);
567 else if (Character.isLowerCase(c))
568 o=Character.toUpperCase(c);
569 _ochar[i]=o;
570 }
571 }
572 }
573
574 Node split(StringMap map,int offset)
575 {
576 Node split = new Node();
577 int sl=_char.length-offset;
578
579 char[] tmp=this._char;
580 this._char=new char[offset];
581 split._char = new char[sl];
582 System.arraycopy(tmp,0,this._char,0,offset);
583 System.arraycopy(tmp,offset,split._char,0,sl);
584
585 if (this._ochar!=null)
586 {
587 tmp=this._ochar;
588 this._ochar=new char[offset];
589 split._ochar = new char[sl];
590 System.arraycopy(tmp,0,this._ochar,0,offset);
591 System.arraycopy(tmp,offset,split._ochar,0,sl);
592 }
593
594 split._key=this._key;
595 split._value=this._value;
596 this._key=null;
597 this._value=null;
598 if (map._entrySet.remove(this))
599 map._entrySet.add(split);
600
601 split._children=this._children;
602 this._children=new Node[map._width];
603 this._children[split._char[0]%map._width]=split;
604 if (split._ochar!=null && this._children[split._ochar[0]%map._width]!=split)
605 this._children[split._ochar[0]%map._width]=split;
606
607 return split;
608 }
609
610 public Object getKey(){return _key;}
611 public Object getValue(){return _value;}
612 public Object setValue(Object o){Object old=_value;_value=o;return old;}
613 public String toString()
614 {
615 StringBuilder buf=new StringBuilder();
616 toString(buf);
617 return buf.toString();
618 }
619
620 private void toString(StringBuilder buf)
621 {
622 buf.append("{[");
623 if (_char==null)
624 buf.append('-');
625 else
626 for (int i=0;i<_char.length;i++)
627 buf.append(_char[i]);
628 buf.append(':');
629 buf.append(_key);
630 buf.append('=');
631 buf.append(_value);
632 buf.append(']');
633 if (_children!=null)
634 {
635 for (int i=0;i<_children.length;i++)
636 {
637 buf.append('|');
638 if (_children[i]!=null)
639 _children[i].toString(buf);
640 else
641 buf.append("-");
642 }
643 }
644 buf.append('}');
645 if (_next!=null)
646 {
647 buf.append(",\n");
648 _next.toString(buf);
649 }
650 }
651 }
652
653 /* ------------------------------------------------------------ */
654 /* ------------------------------------------------------------ */
655 private class NullEntry implements Map.Entry
656 {
657 public Object getKey(){return null;}
658 public Object getValue(){return _nullValue;}
659 public Object setValue(Object o)
660 {Object old=_nullValue;_nullValue=o;return old;}
661 public String toString(){return "[:null="+_nullValue+"]";}
662 }
663
664 /* ------------------------------------------------------------ */
665 public void writeExternal(java.io.ObjectOutput out)
666 throws java.io.IOException
667 {
668 HashMap map = new HashMap(this);
669 out.writeBoolean(_ignoreCase);
670 out.writeObject(map);
671 }
672
673 /* ------------------------------------------------------------ */
674 public void readExternal(java.io.ObjectInput in)
675 throws java.io.IOException, ClassNotFoundException
676 {
677 boolean ic=in.readBoolean();
678 HashMap map = (HashMap)in.readObject();
679 setIgnoreCase(ic);
680 this.putAll(map);
681 }
682 }