001/**
002 *
003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved.
004 *
005 * This library is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU Lesser General Public
007 * License as published by the Free Software Foundation; either 
008 * version 2.1 of the License, or (at your option) any later version.
009 * 
010 * This library is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013 * Lesser General Public License for more details.
014 * 
015 * You should have received a copy of the GNU Lesser General Public 
016 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
017 * 
018 **/
019package lucee.runtime.net.ipsettings;
020
021
022import java.net.InetAddress;
023import java.net.UnknownHostException;
024import java.util.ArrayList;
025import java.util.Collections;
026import java.util.List;
027
028
029public class IPRangeCollection {
030
031
032        private List<IPRangeNode> list = Collections.EMPTY_LIST;
033
034
035        void add( IPRangeNode child, boolean doCheck ) {
036
037                if ( list == Collections.EMPTY_LIST )
038                        list = new ArrayList();
039                else if ( doCheck ) {
040
041                        // scan for previous children in parent that should be moved under the newly added child after this addition
042
043                        int listSize = list.size();
044                        for ( int i=0; i < listSize; i++ ) {
045
046                                IPRangeNode sibling = list.get(i);
047
048                                if ( child.containsRange( sibling ) ) {                         // move sibling under new child
049
050                                        list.remove(i--);                                // adjust i and numChildren due to removal
051                                        listSize--;
052
053                                        child.addChild( sibling );
054                                }
055                        }
056                }
057
058                list.add( child );
059        }
060
061
062        public void add( IPRangeNode child ) {
063
064                this.add( child, true );
065        }
066
067
068
069
070        public IPRangeNode findFast( InetAddress iaddr, List<IPRangeNode> parents ) {
071
072                IPRangeNode needle, parent;
073
074                needle = new IPRangeNode( iaddr, iaddr );
075
076                int pos = Collections.binarySearch( list, needle, IPRangeNode.comparerRange );
077
078                if ( pos > -1 ) {
079
080                        parent = list.get(pos);
081                        return parent.findFast(iaddr, parents);
082                }
083
084                int tests = 2;
085                pos = Math.abs(pos);
086
087                pos = Math.max(0, pos - tests);
088                int max = Math.min( pos + tests, list.size() );
089
090                for (; pos < max; pos++ ) {
091
092                        if ( list.get( pos ).isInRange( iaddr ) ) {
093
094                                parent = list.get( pos );
095                                return parent.findFast(iaddr, parents);
096                        }
097                }
098
099                return null;
100        }
101
102
103
104        /**
105         * performs a binary search over a sorted list
106         *
107         * @param iaddr
108         * @return
109         */
110        public IPRangeNode findFast( InetAddress iaddr ) {
111
112                IPRangeNode needle, parent;
113
114                needle = new IPRangeNode( iaddr, iaddr );
115
116                int pos = Collections.binarySearch( list, needle, IPRangeNode.comparerRange );
117
118                if ( pos > -1 ) {
119
120                        parent = list.get(pos);
121                        return parent.findFast(iaddr);
122                }
123
124                int tests = 2;
125                pos = Math.abs(pos);
126
127                pos = Math.max(0, pos - tests);
128                int max = Math.min( pos + tests, list.size() );
129
130                for (; pos < max; pos++ ) {
131
132                        if ( list.get( pos ).isInRange( iaddr ) ) {
133
134                                parent = list.get( pos );
135                                return parent.findFast(iaddr);
136                        }
137                }
138
139                return null;
140        }
141
142
143        /**
144         * performs a binary search over sorted list
145         *
146         * @param addr
147         * @return
148         */
149        public IPRangeNode findFast( String addr ) {
150
151                InetAddress iaddr;
152
153                try {
154
155                        iaddr = InetAddress.getByName(addr);
156                }
157                catch (UnknownHostException ex) {
158
159                        return null;
160                }
161
162                return findFast( iaddr );
163        }
164
165
166        /**
167         * performs a linear scan for unsorted lists
168         *
169         * @param addr
170         * @return
171         */
172        public IPRangeNode findAddr( InetAddress addr ) {
173
174                for ( IPRangeNode c : this.list ) {
175
176                        IPRangeNode result = c.findAddr( addr );
177
178                        if ( result != null )
179                                return result;
180                }
181
182                return null;
183        }
184
185
186        /**
187         * performs a linear scan for unsorted lists
188         *
189         * @param child
190         * @return
191         */
192        public IPRangeNode findRange( IPRangeNode child ) {
193
194                for ( IPRangeNode c : this.list ) {
195
196                        IPRangeNode result = c.findRange( child );
197
198                        if ( result != null )
199                                return result;
200                }
201
202                return null;
203        }
204
205
206        public int size() {
207
208                return list.size();
209        }
210
211
212        private void sort() {
213
214                Collections.sort( this.list );
215        }
216
217
218        public void sortChildren() {
219
220                for ( IPRangeNode node : this.list ) {
221
222                        node.getChildren().sort();
223                }
224        }
225
226}