001: // IPMatcher.java
002: // $Id: IPMatcher.java,v 1.3 2000/08/16 21:37:34 ylafon Exp $
003: // (c) COPYRIGHT MIT and INRIA, 1996.
004: // Please first read the full copyright statement in file COPYRIGHT.html
005:
006: package org.w3c.jigsaw.auth;
007:
008: import java.io.PrintStream;
009:
010: import java.util.Vector;
011:
012: import java.net.InetAddress;
013:
014: class IPMatcherNode {
015: short part = -1;
016: Object closure = null;
017: Vector elems = null;
018:
019: /**
020: * Set this node closure object.
021: * @param obj The new closure for the node.
022: */
023:
024: protected void setClosure(Object obj) {
025: this .closure = obj;
026: }
027:
028: /**
029: * Get this node closure object.
030: * @return An instance of Object.
031: */
032:
033: protected Object getClosure() {
034: return closure;
035: }
036:
037: /**
038: * Lookup this byte of IP adress in this node.
039: * If we are requested to create a new node, than we create and return it.
040: */
041:
042: IPMatcherNode step(short iadr, Object closure) {
043: IPMatcherNode node = null;
044: int lo = 0;
045: int hi = elems.size() - 1;
046: int idx = -1;
047: if (hi >= lo) {
048: // Nodes are kept sorted:
049: while ((hi - lo) > 1) {
050: idx = (hi - lo) / 2 + lo;
051: node = (IPMatcherNode) elems.elementAt(idx);
052: if (node.part == 256) {
053: // A star, matches everything below
054: return node;
055: } else if (node.part > iadr) {
056: hi = idx;
057: } else if (node.part < iadr) {
058: lo = idx;
059: } else {
060: return node;
061: }
062: }
063: switch (hi - lo) {
064: case 0:
065: node = (IPMatcherNode) elems.elementAt(hi);
066: if ((node.part == iadr) || (node.part == 256))
067: return node;
068: idx = (node.part < iadr) ? hi + 1 : hi;
069: break;
070: case 1:
071: IPMatcherNode lonode = (IPMatcherNode) elems
072: .elementAt(lo);
073: IPMatcherNode hinode = (IPMatcherNode) elems
074: .elementAt(hi);
075: if ((lonode.part == iadr) || (lonode.part == 256))
076: return lonode;
077: if ((hinode.part == iadr) || (hinode.part == 256))
078: return hinode;
079: // Decide wich of the three available position we should use
080: if (iadr < lonode.part) {
081: idx = lo;
082: } else if (iadr < hinode.part) {
083: idx = hi;
084: } else {
085: idx = hi + 1;
086: }
087: break;
088: default:
089: throw new RuntimeException(
090: "IPMatcherNode: inconsistent.");
091: }
092: }
093: // The node doesn't exist, create it:
094: if (closure != null) {
095: if (idx < 0)
096: idx = 0;
097: node = new IPMatcherNode(iadr);
098: elems.insertElementAt(node, idx);
099: return node;
100: } else {
101: return null;
102: }
103: }
104:
105: /**
106: * Print the tree starting at this node.
107: * @param out The print stream to print to.
108: * @param pref The prefix string (printed before all infos).
109: */
110:
111: public void print(PrintStream out, String pref) {
112: System.out.println(pref + "{" + part + "}" + ":");
113: for (int i = 0; i < elems.size(); i++)
114: ((IPMatcherNode) elems.elementAt(i))
115: .print(out, pref + "\t");
116: }
117:
118: /**
119: * Create a new node for a given sub-space.
120: * @param part The IP address part to register in this node.
121: */
122:
123: IPMatcherNode(short part) {
124: this .part = part;
125: this .elems = new Vector(2);
126: }
127:
128: /**
129: * Create the root node.
130: */
131:
132: IPMatcherNode() {
133: this .elems = new Vector();
134: }
135:
136: }
137:
138: /**
139: * A fast way of associating IP adresses to any Object.
140: * This IPMatcher classes maps IP adresses to objects. It understands wild
141: * cards, encoded as ((short) 256). Wild card will match any adress below it.
142: */
143:
144: public class IPMatcher {
145: IPMatcherNode root = null;
146:
147: /**
148: * Associate the given IP adress to the given object.
149: * This method takes as parameter an array of <em>short</em> in order
150: * to extend natural IP adresses bytes with the wild card character.
151: * @param a The adress to use as a key for the association.
152: * @param closure The associated object.
153: */
154:
155: public void add(short a[], Object closure) {
156: IPMatcherNode node = root;
157: for (int i = 0; i < a.length; i++)
158: node = node.step(a[i], closure);
159: node.setClosure(closure);
160: return;
161: }
162:
163: /**
164: * Lookup the adress for an association.
165: * @param a The adress to look for.
166: * @return The object associated to the given IP address, or
167: * <strong>null</strong> if none was found.
168: */
169:
170: public Object lookup(byte a[]) {
171: IPMatcherNode node = root;
172: for (int i = 0; (node != null) && (i < a.length); i++)
173: node = node.step((short) (((short) a[i]) & 0xff), null);
174: return (node == null) ? null : node.closure;
175: }
176:
177: /**
178: * Lookup the given InetAdress for any association.
179: * @param inetadr The inet adress to look for.
180: * @return The object associated to the given IP adress, or
181: * <strong>null</strong> if none was found.
182: */
183:
184: public Object lookup(InetAddress inetadr) {
185: return lookup(inetadr.getAddress());
186: }
187:
188: /**
189: * Print the IP matcher internal tree.
190: */
191:
192: public void print(PrintStream out) {
193: root.print(out, "");
194: }
195:
196: public IPMatcher() {
197: this .root = new IPMatcherNode();
198: }
199: }
|