1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.eclipse.jetty.http;
20
21 import java.util.Collections;
22 import java.util.HashMap;
23 import java.util.List;
24 import java.util.Map;
25 import java.util.StringTokenizer;
26
27 import org.eclipse.jetty.util.ArrayTernaryTrie;
28 import org.eclipse.jetty.util.LazyList;
29 import org.eclipse.jetty.util.Trie;
30 import org.eclipse.jetty.util.URIUtil;
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 public class PathMap<O> extends HashMap<String,O>
64 {
65
66 private static String __pathSpecSeparators = ":,";
67
68
69
70
71
72
73
74
75 public static void setPathSpecSeparators(String s)
76 {
77 __pathSpecSeparators=s;
78 }
79
80
81 Trie<MappedEntry<O>> _prefixMap=new ArrayTernaryTrie<>(false);
82 Trie<MappedEntry<O>> _suffixMap=new ArrayTernaryTrie<>(false);
83 final Map<String,MappedEntry<O>> _exactMap=new HashMap<>();
84
85 List<MappedEntry<O>> _defaultSingletonList=null;
86 MappedEntry<O> _prefixDefault=null;
87 MappedEntry<O> _default=null;
88 boolean _nodefault=false;
89
90
91 public PathMap()
92 {
93 this(11);
94 }
95
96
97 public PathMap(boolean noDefault)
98 {
99 this(11, noDefault);
100 }
101
102
103 public PathMap(int capacity)
104 {
105 this(capacity, false);
106 }
107
108
109 private PathMap(int capacity, boolean noDefault)
110 {
111 super(capacity);
112 _nodefault=noDefault;
113 }
114
115
116
117
118 public PathMap(Map<String, ? extends O> m)
119 {
120 putAll(m);
121 }
122
123
124
125
126
127
128
129 @Override
130 public O put(String pathSpec, O object)
131 {
132 if ("".equals(pathSpec.trim()))
133 {
134 MappedEntry<O> entry = new MappedEntry<>("",object);
135 entry.setMapped("");
136 _exactMap.put("", entry);
137 return super.put("", object);
138 }
139
140 StringTokenizer tok = new StringTokenizer(pathSpec,__pathSpecSeparators);
141 O old =null;
142
143 while (tok.hasMoreTokens())
144 {
145 String spec=tok.nextToken();
146
147 if (!spec.startsWith("/") && !spec.startsWith("*."))
148 throw new IllegalArgumentException("PathSpec "+spec+". must start with '/' or '*.'");
149
150 old = super.put(spec,object);
151
152
153 MappedEntry<O> entry = new MappedEntry<>(spec,object);
154
155 if (entry.getKey().equals(spec))
156 {
157 if (spec.equals("/*"))
158 _prefixDefault=entry;
159 else if (spec.endsWith("/*"))
160 {
161 String mapped=spec.substring(0,spec.length()-2);
162 entry.setMapped(mapped);
163 while (!_prefixMap.put(mapped,entry))
164 _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_prefixMap,1.5);
165 }
166 else if (spec.startsWith("*."))
167 {
168 String suffix=spec.substring(2);
169 while(!_suffixMap.put(suffix,entry))
170 _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedEntry<O>>)_suffixMap,1.5);
171 }
172 else if (spec.equals(URIUtil.SLASH))
173 {
174 if (_nodefault)
175 _exactMap.put(spec,entry);
176 else
177 {
178 _default=entry;
179 _defaultSingletonList=Collections.singletonList(_default);
180 }
181 }
182 else
183 {
184 entry.setMapped(spec);
185 _exactMap.put(spec,entry);
186 }
187 }
188 }
189
190 return old;
191 }
192
193
194
195
196
197
198 public O match(String path)
199 {
200 MappedEntry<O> entry = getMatch(path);
201 if (entry!=null)
202 return entry.getValue();
203 return null;
204 }
205
206
207
208
209
210
211
212 public MappedEntry<O> getMatch(String path)
213 {
214 if (path==null)
215 return null;
216
217 int l=path.length();
218
219 MappedEntry<O> entry=null;
220
221
222 if (l == 1 && path.charAt(0)=='/')
223 {
224 entry = _exactMap.get("");
225 if (entry != null)
226 return entry;
227 }
228
229
230 entry=_exactMap.get(path);
231 if (entry!=null)
232 return entry;
233
234
235 int i=l;
236 final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
237 while(i>=0)
238 {
239 entry=prefix_map.getBest(path,0,i);
240 if (entry==null)
241 break;
242 String key = entry.getKey();
243 if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
244 return entry;
245 i=key.length()-3;
246 }
247
248
249 if (_prefixDefault!=null)
250 return _prefixDefault;
251
252
253 i=0;
254 final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
255 while ((i=path.indexOf('.',i+1))>0)
256 {
257 entry=suffix_map.get(path,i+1,l-i-1);
258 if (entry!=null)
259 return entry;
260 }
261
262
263 return _default;
264 }
265
266
267
268
269
270
271
272 public Object getLazyMatches(String path)
273 {
274 MappedEntry<O> entry;
275 Object entries=null;
276
277 if (path==null)
278 return LazyList.getList(entries);
279
280
281 entry=_exactMap.get(path);
282 if (entry!=null)
283 entries=LazyList.add(entries,entry);
284
285
286 int l=path.length();
287 int i=l;
288 final Trie<PathMap.MappedEntry<O>> prefix_map=_prefixMap;
289 while(i>=0)
290 {
291 entry=prefix_map.getBest(path,0,i);
292 if (entry==null)
293 break;
294 String key = entry.getKey();
295 if (key.length()-2>=path.length() || path.charAt(key.length()-2)=='/')
296 entries=LazyList.add(entries,entry);
297
298 i=key.length()-3;
299 }
300
301
302 if (_prefixDefault!=null)
303 entries=LazyList.add(entries,_prefixDefault);
304
305
306 i=0;
307 final Trie<PathMap.MappedEntry<O>> suffix_map=_suffixMap;
308 while ((i=path.indexOf('.',i+1))>0)
309 {
310 entry=suffix_map.get(path,i+1,l-i-1);
311 if (entry!=null)
312 entries=LazyList.add(entries,entry);
313 }
314
315
316 if (_default!=null)
317 {
318
319 if (entries==null)
320 return _defaultSingletonList;
321
322 entries=LazyList.add(entries,_default);
323 }
324
325 return entries;
326 }
327
328
329
330
331
332
333
334 public List<Map.Entry<String,O>> getMatches(String path)
335 {
336 return LazyList.getList(getLazyMatches(path));
337 }
338
339
340
341
342
343
344
345 public boolean containsMatch(String path)
346 {
347 MappedEntry<?> match = getMatch(path);
348 return match!=null && !match.equals(_default);
349 }
350
351
352 @Override
353 public O remove(Object pathSpec)
354 {
355 if (pathSpec!=null)
356 {
357 String spec=(String) pathSpec;
358 if (spec.equals("/*"))
359 _prefixDefault=null;
360 else if (spec.endsWith("/*"))
361 _prefixMap.remove(spec.substring(0,spec.length()-2));
362 else if (spec.startsWith("*."))
363 _suffixMap.remove(spec.substring(2));
364 else if (spec.equals(URIUtil.SLASH))
365 {
366 _default=null;
367 _defaultSingletonList=null;
368 }
369 else
370 _exactMap.remove(spec);
371 }
372 return super.remove(pathSpec);
373 }
374
375
376 @Override
377 public void clear()
378 {
379 _exactMap.clear();
380 _prefixMap=new ArrayTernaryTrie<>(false);
381 _suffixMap=new ArrayTernaryTrie<>(false);
382 _default=null;
383 _defaultSingletonList=null;
384 super.clear();
385 }
386
387
388
389
390
391 public static boolean match(String pathSpec, String path)
392 throws IllegalArgumentException
393 {
394 return match(pathSpec, path, false);
395 }
396
397
398
399
400
401 public static boolean match(String pathSpec, String path, boolean noDefault)
402 throws IllegalArgumentException
403 {
404 if (pathSpec.length()==0)
405 return "/".equals(path);
406
407 char c = pathSpec.charAt(0);
408 if (c=='/')
409 {
410 if (!noDefault && pathSpec.length()==1 || pathSpec.equals(path))
411 return true;
412
413 if(isPathWildcardMatch(pathSpec, path))
414 return true;
415 }
416 else if (c=='*')
417 return path.regionMatches(path.length()-pathSpec.length()+1,
418 pathSpec,1,pathSpec.length()-1);
419 return false;
420 }
421
422
423 private static boolean isPathWildcardMatch(String pathSpec, String path)
424 {
425
426 int cpl=pathSpec.length()-2;
427 if (pathSpec.endsWith("/*") && path.regionMatches(0,pathSpec,0,cpl))
428 {
429 if (path.length()==cpl || '/'==path.charAt(cpl))
430 return true;
431 }
432 return false;
433 }
434
435
436
437
438
439
440 public static String pathMatch(String pathSpec, String path)
441 {
442 char c = pathSpec.charAt(0);
443
444 if (c=='/')
445 {
446 if (pathSpec.length()==1)
447 return path;
448
449 if (pathSpec.equals(path))
450 return path;
451
452 if (isPathWildcardMatch(pathSpec, path))
453 return path.substring(0,pathSpec.length()-2);
454 }
455 else if (c=='*')
456 {
457 if (path.regionMatches(path.length()-(pathSpec.length()-1),
458 pathSpec,1,pathSpec.length()-1))
459 return path;
460 }
461 return null;
462 }
463
464
465
466
467
468 public static String pathInfo(String pathSpec, String path)
469 {
470 if ("".equals(pathSpec))
471 return path;
472
473 char c = pathSpec.charAt(0);
474
475 if (c=='/')
476 {
477 if (pathSpec.length()==1)
478 return null;
479
480 boolean wildcard = isPathWildcardMatch(pathSpec, path);
481
482
483 if (pathSpec.equals(path) && !wildcard)
484 return null;
485
486 if (wildcard)
487 {
488 if (path.length()==pathSpec.length()-2)
489 return null;
490 return path.substring(pathSpec.length()-2);
491 }
492 }
493 return null;
494 }
495
496
497
498
499
500
501
502
503
504 public static String relativePath(String base,
505 String pathSpec,
506 String path )
507 {
508 String info=pathInfo(pathSpec,path);
509 if (info==null)
510 info=path;
511
512 if( info.startsWith( "./"))
513 info = info.substring( 2);
514 if( base.endsWith( URIUtil.SLASH))
515 if( info.startsWith( URIUtil.SLASH))
516 path = base + info.substring(1);
517 else
518 path = base + info;
519 else
520 if( info.startsWith( URIUtil.SLASH))
521 path = base + info;
522 else
523 path = base + URIUtil.SLASH + info;
524 return path;
525 }
526
527
528
529
530 public static class MappedEntry<O> implements Map.Entry<String,O>
531 {
532 private final String key;
533 private final O value;
534 private String mapped;
535
536 MappedEntry(String key, O value)
537 {
538 this.key=key;
539 this.value=value;
540 }
541
542 @Override
543 public String getKey()
544 {
545 return key;
546 }
547
548 @Override
549 public O getValue()
550 {
551 return value;
552 }
553
554 @Override
555 public O setValue(O o)
556 {
557 throw new UnsupportedOperationException();
558 }
559
560 @Override
561 public String toString()
562 {
563 return key+"="+value;
564 }
565
566 public String getMapped()
567 {
568 return mapped;
569 }
570
571 void setMapped(String mapped)
572 {
573 this.mapped = mapped;
574 }
575 }
576 }