1//
2//  ========================================================================
3//  Copyright (c) 1995-2014 Mort Bay Consulting Pty. Ltd.
4//  ------------------------------------------------------------------------
5//  All rights reserved. This program and the accompanying materials
6//  are made available under the terms of the Eclipse Public License v1.0
7//  and Apache License v2.0 which accompanies this distribution.
8//
9//      The Eclipse Public License is available at
10//      http://www.eclipse.org/legal/epl-v10.html
11//
12//      The Apache License v2.0 is available at
13//      http://www.opensource.org/licenses/apache2.0.php
14//
15//  You may elect to redistribute this code under either of these licenses.
16//  ========================================================================
17//
18
19package org.eclipse.jetty.util;
20
21import java.util.BitSet;
22import java.util.HashMap;
23import java.util.Map;
24import java.util.StringTokenizer;
25
26
27/* ------------------------------------------------------------ */
28/**
29 * Internet address map to object
30 * <p>
31 * Internet addresses may be specified as absolute address or as a combination of
32 * four octet wildcard specifications (a.b.c.d) that are defined as follows.
33 * </p>
34 * <pre>
35 * nnn - an absolute value (0-255)
36 * mmm-nnn - an inclusive range of absolute values,
37 *           with following shorthand notations:
38 *           nnn- => nnn-255
39 *           -nnn => 0-nnn
40 *           -    => 0-255
41 * a,b,... - a list of wildcard specifications
42 * </pre>
43 */
44@SuppressWarnings("serial")
45public class IPAddressMap<TYPE> extends HashMap<String, TYPE>
46{
47    private final HashMap<String,IPAddrPattern> _patterns = new HashMap<String,IPAddrPattern>();
48
49    /* --------------------------------------------------------------- */
50    /** Construct empty IPAddressMap.
51     */
52    public IPAddressMap()
53    {
54        super(11);
55    }
56
57    /* --------------------------------------------------------------- */
58    /** Construct empty IPAddressMap.
59     *
60     * @param capacity initial capacity
61     */
62    public IPAddressMap(int capacity)
63    {
64        super (capacity);
65    }
66
67    /* ------------------------------------------------------------ */
68    /**
69     * Insert a new internet address into map
70     *
71     * @see java.util.HashMap#put(java.lang.Object, java.lang.Object)
72     */
73    @Override
74    public TYPE put(String addrSpec, TYPE object)
75        throws IllegalArgumentException
76    {
77        if (addrSpec == null || addrSpec.trim().length() == 0)
78            throw new IllegalArgumentException("Invalid IP address pattern: "+addrSpec);
79
80        String spec = addrSpec.trim();
81        if (_patterns.get(spec) == null)
82            _patterns.put(spec,new IPAddrPattern(spec));
83
84        return super.put(spec, object);
85    }
86
87    /* ------------------------------------------------------------ */
88    /**
89     * Retrieve the object mapped to the specified internet address literal
90     *
91     * @see java.util.HashMap#get(java.lang.Object)
92     */
93    @Override
94    public TYPE get(Object key)
95    {
96        return super.get(key);
97    }
98
99    /* ------------------------------------------------------------ */
100    /**
101     * Retrieve the first object that is associated with the specified
102     * internet address by taking into account the wildcard specifications.
103     *
104     * @param addr internet address
105     * @return associated object
106     */
107    public TYPE match(String addr)
108    {
109        Map.Entry<String, TYPE> entry = getMatch(addr);
110        return entry==null ? null : entry.getValue();
111    }
112
113    /* ------------------------------------------------------------ */
114    /**
115     * Retrieve the first map entry that is associated with the specified
116     * internet address by taking into account the wildcard specifications.
117     *
118     * @param addr internet address
119     * @return map entry associated
120     */
121    public Map.Entry<String, TYPE> getMatch(String addr)
122    {
123        if (addr != null)
124        {
125            for(Map.Entry<String, TYPE> entry: super.entrySet())
126            {
127                if (_patterns.get(entry.getKey()).match(addr))
128                {
129                    return entry;
130                }
131            }
132        }
133        return null;
134    }
135
136    /* ------------------------------------------------------------ */
137    /**
138     * Retrieve a lazy list of map entries associated with specified
139     * internet address by taking into account the wildcard specifications.
140     *
141     * @param addr  internet address
142     * @return lazy list of map entries
143     */
144    public Object getLazyMatches(String addr)
145    {
146        if (addr == null)
147            return LazyList.getList(super.entrySet());
148
149        Object entries = null;
150        for(Map.Entry<String, TYPE> entry: super.entrySet())
151        {
152            if (_patterns.get(entry.getKey()).match(addr))
153            {
154                entries = LazyList.add(entries,entry);
155            }
156        }
157        return entries;
158    }
159
160    /* ------------------------------------------------------------ */
161    /**
162     * IPAddrPattern
163     *
164     * Represents internet address wildcard.
165     * Matches the wildcard to provided internet address.
166     */
167    private static class IPAddrPattern
168    {
169        private final OctetPattern[] _octets = new OctetPattern[4];
170        /* ------------------------------------------------------------ */
171        /**
172         * Create new IPAddrPattern
173         *
174         * @param value internet address wildcard specification
175         * @throws IllegalArgumentException if wildcard specification is invalid
176         */
177        public IPAddrPattern(String value)
178            throws IllegalArgumentException
179        {
180            if (value == null || value.trim().length() == 0)
181                throw new IllegalArgumentException("Invalid IP address pattern: "+value);
182
183            try
184            {
185                StringTokenizer parts = new StringTokenizer(value, ".");
186
187                String part;
188                for (int idx=0; idx<4; idx++)
189                {
190                    part = parts.hasMoreTokens() ? parts.nextToken().trim() : "0-255";
191
192                    int len = part.length();
193                    if (len == 0 && parts.hasMoreTokens())
194                        throw new IllegalArgumentException("Invalid IP address pattern: "+value);
195
196                    _octets[idx] = new OctetPattern(len==0 ? "0-255" : part);
197                }
198            }
199            catch (IllegalArgumentException ex)
200            {
201                throw new IllegalArgumentException("Invalid IP address pattern: "+value, ex);
202            }
203        }
204
205        /* ------------------------------------------------------------ */
206        /**
207         * Match the specified internet address against the wildcard
208         *
209         * @param value internet address
210         * @return true if specified internet address matches wildcard specification
211         *
212         * @throws IllegalArgumentException if specified internet address is invalid
213         */
214        public boolean match(String value)
215            throws IllegalArgumentException
216        {
217            if (value == null || value.trim().length() == 0)
218                throw new IllegalArgumentException("Invalid IP address: "+value);
219
220            try
221            {
222                StringTokenizer parts = new StringTokenizer(value, ".");
223
224                boolean result = true;
225                for (int idx=0; idx<4; idx++)
226                {
227                    if (!parts.hasMoreTokens())
228                        throw new IllegalArgumentException("Invalid IP address: "+value);
229
230                    if (!(result &= _octets[idx].match(parts.nextToken())))
231                        break;
232                }
233                return result;
234            }
235            catch (IllegalArgumentException ex)
236            {
237                throw new IllegalArgumentException("Invalid IP address: "+value, ex);
238            }
239        }
240    }
241
242    /* ------------------------------------------------------------ */
243    /**
244     * OctetPattern
245     *
246     * Represents a single octet wildcard.
247     * Matches the wildcard to the specified octet value.
248     */
249    private static class OctetPattern extends BitSet
250    {
251        private final BitSet _mask = new BitSet(256);
252
253        /* ------------------------------------------------------------ */
254        /**
255         * Create new OctetPattern
256         *
257         * @param octetSpec octet wildcard specification
258         * @throws IllegalArgumentException if wildcard specification is invalid
259         */
260        public OctetPattern(String octetSpec)
261            throws IllegalArgumentException
262        {
263            try
264            {
265                if (octetSpec != null)
266                {
267                    String spec = octetSpec.trim();
268                    if(spec.length() == 0)
269                    {
270                        _mask.set(0,255);
271                    }
272                    else
273                    {
274                        StringTokenizer parts = new StringTokenizer(spec,",");
275                        while (parts.hasMoreTokens())
276                        {
277                            String part = parts.nextToken().trim();
278                            if (part.length() > 0)
279                            {
280                                if (part.indexOf('-') < 0)
281                                {
282                                    Integer value = Integer.valueOf(part);
283                                    _mask.set(value);
284                                }
285                                else
286                                {
287                                    int low = 0, high = 255;
288
289                                    String[] bounds = part.split("-",-2);
290                                    if (bounds.length != 2)
291                                    {
292                                        throw new IllegalArgumentException("Invalid octet spec: "+octetSpec);
293                                    }
294
295                                    if (bounds[0].length() > 0)
296                                    {
297                                        low = Integer.parseInt(bounds[0]);
298                                    }
299                                    if (bounds[1].length() > 0)
300                                    {
301                                        high = Integer.parseInt(bounds[1]);
302                                    }
303
304                                    if (low > high)
305                                    {
306                                        throw new IllegalArgumentException("Invalid octet spec: "+octetSpec);
307                                    }
308
309                                    _mask.set(low, high+1);
310                                }
311                            }
312                        }
313                    }
314                }
315            }
316            catch (NumberFormatException ex)
317            {
318                throw new IllegalArgumentException("Invalid octet spec: "+octetSpec, ex);
319            }
320        }
321
322        /* ------------------------------------------------------------ */
323        /**
324         * Match specified octet value against the wildcard
325         *
326         * @param value octet value
327         * @return true if specified octet value matches the wildcard
328         * @throws IllegalArgumentException if specified octet value is invalid
329         */
330        public boolean match(String value)
331            throws IllegalArgumentException
332        {
333            if (value == null || value.trim().length() == 0)
334                throw new IllegalArgumentException("Invalid octet: "+value);
335
336            try
337            {
338                int number = Integer.parseInt(value);
339                return match(number);
340            }
341            catch (NumberFormatException ex)
342            {
343                throw new IllegalArgumentException("Invalid octet: "+value);
344            }
345        }
346
347        /* ------------------------------------------------------------ */
348        /**
349         * Match specified octet value against the wildcard
350         *
351         * @param number octet value
352         * @return true if specified octet value matches the wildcard
353         * @throws IllegalArgumentException if specified octet value is invalid
354         */
355        public boolean match(int number)
356            throws IllegalArgumentException
357        {
358            if (number < 0 || number > 255)
359                throw new IllegalArgumentException("Invalid octet: "+number);
360
361            return _mask.get(number);
362        }
363    }
364}
365