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