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}