1
2
3
4
5
6
7
8
9
10
11
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
26
27
28
29
30
31
32
33
34
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
54
55 public StringMap()
56 {}
57
58
59
60
61
62 public StringMap(boolean ignoreCase)
63 {
64 this();
65 _ignoreCase=ignoreCase;
66 }
67
68
69
70
71
72
73
74 public StringMap(boolean ignoreCase,int width)
75 {
76 this();
77 _ignoreCase=ignoreCase;
78 _width=width;
79 }
80
81
82
83
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
100
101
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
144 charLoop:
145 for (int i=0;i<key.length();i++)
146 {
147 char c=key.charAt(i);
148
149
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
159 while (node!=null)
160 {
161
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
172
173 if (ni==0)
174 {
175
176 prev=node;
177 node=node._next;
178 }
179 else
180 {
181
182 node.split(this,ni);
183 i--;
184 ni=-1;
185 continue charLoop;
186 }
187 }
188
189
190 node = new Node(_ignoreCase,key,i);
191
192 if (prev!=null)
193 prev._next=node;
194 else if (parent!=null)
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
214 _root=node;
215 break;
216 }
217
218
219 if (node!=null)
220 {
221
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
259
260
261
262
263
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
274 charLoop:
275 for (int i=0;i<length;i++)
276 {
277 char c=key.charAt(offset+i);
278
279
280 if (ni==-1)
281 {
282 ni=0;
283 node=(node._children==null)?null:node._children[c%_width];
284 }
285
286
287 while (node!=null)
288 {
289
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
299 if (ni>0) return null;
300
301
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
315
316
317
318
319
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
330 charLoop:
331 for (int i=0;i<length;i++)
332 {
333 char c=key[offset+i];
334
335
336 if (ni==-1)
337 {
338 ni=0;
339 node=(node._children==null)?null:node._children[c%_width];
340 }
341
342
343 while (node!=null)
344 {
345
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
355 if (ni>0) return null;
356
357
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
371
372
373
374
375
376
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
387 charLoop:
388 for (int i=0;i<maxLength;i++)
389 {
390 char c=(char)key[offset+i];
391
392
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;
401 node=child;
402 }
403
404
405 while (node!=null)
406 {
407
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
417 if (ni>0) return null;
418
419
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
460 charLoop:
461 for (int i=0;i<key.length();i++)
462 {
463 char c=key.charAt(i);
464
465
466 if (ni==-1)
467 {
468 ni=0;
469 node=(node._children==null)?null:node._children[c%_width];
470 }
471
472
473 while (node!=null)
474 {
475
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
485 if (ni>0) return null;
486
487
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 }