Source code: com/strangeberry/rendezvous/DNSCache.java
1 // Copyright (C) 2002 Strangeberry Inc.
2 // @(#)DNSCache.java, 1.11, 11/29/2002
3 //
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8 //
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13 //
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
18 package com.strangeberry.rendezvous;
19
20 import java.util.*;
21
22 /**
23 * A table of DNS entries. This is a closed hash table which
24 * can handle multiple entries with the same name. It provides
25 * iterators to efficiently iterate over all the entries with
26 * a given name.
27 *
28 * @author Arthur van Hoff
29 * @version 1.11, 11/29/2002
30 */
31 class DNSCache
32 {
33 final static float LOAD_FACTOR = 0.75f;
34
35 DNSEntry entries[];
36 int count;
37 float loadFactor;
38
39 /**
40 * Create a table with a given initial size.
41 */
42 DNSCache(int size)
43 {
44 size = Math.max(2, size * 2);
45 for (; (size % 2 == 0) || (size % 3 == 0) || (size % 5 == 0) ; size++);
46 this.entries = new DNSEntry[size];
47 }
48
49 /**
50 * Add an entry to the table. The table will be grown
51 * if it is more than 75% full.
52 */
53 void add(DNSEntry entry)
54 {
55 // rehash if necessary
56 if (count >= (entries.length * LOAD_FACTOR)) {
57 entries = rehash(entries, entries.length * 2);
58 }
59 add(entries, entry);
60 count++;
61 }
62
63 /**
64 * Add an entry to a table.
65 */
66 private void add(DNSEntry entries[], DNSEntry entry)
67 {
68 int i = Math.abs(entry.key.hashCode()) % entries.length;
69 while (entries[i] != null) {
70 i = ((i == 0) ? entries.length : i) - 1;
71 }
72 entries[i] = entry;
73 }
74
75 /**
76 * Rehash a table.
77 */
78 private DNSEntry[] rehash(DNSEntry entries[], int size)
79 {
80 for (; (size % 2 == 0) || (size % 3 == 0) || (size % 5 == 0) ; size++);
81
82 DNSEntry newentries[] = new DNSEntry[size];
83 for (int i = 0, n = entries.length ; i < n ; i++) {
84 if (entries[i] != null) {
85 add(newentries, entries[i]);
86 }
87 }
88 return newentries;
89 }
90
91 /**
92 * Remove a specific entry from the table. Returns true if the
93 * entry was found.
94 */
95 boolean remove(DNSEntry entry)
96 {
97 int i = Math.abs(entry.key.hashCode()) % entries.length;
98 while (true) {
99 DNSEntry e = entries[i];
100 if (e == null) {
101 return false;
102 }
103 if (e == entry) {
104 remove(i);
105 return true;
106 }
107 if (--i < 0) {
108 i = entries.length - 1;
109 }
110 }
111 }
112
113 /**
114 * Remove entry at a given index. Reshuffle as needed.
115 */
116 private void remove(int i)
117 {
118 int empty = i;
119 entries[empty] = null;
120 count--;
121 while (true) {
122 if (--i < 0) {
123 i = entries.length - 1;
124 }
125 DNSEntry e = entries[i];
126 if (e == null) {
127 return;
128 }
129 int j = Math.abs(e.key.hashCode()) % entries.length;
130 if ((i < empty) ? ((j < i) || (j >= empty)) : ((j < i) && (j >= empty))) {
131 entries[empty] = e;
132 empty = i;
133 entries[empty] = null;
134 }
135 }
136 }
137
138 /**
139 * Get a matching DNS entry from the table (using equals).
140 * Returns the entry that was found.
141 */
142 DNSEntry get(DNSEntry entry)
143 {
144 int i = Math.abs(entry.key.hashCode()) % entries.length;
145 while (true) {
146 DNSEntry e = entries[i];
147 if (e == null) {
148 return null;
149 }
150 if (e.equals(entry)) {
151 return e;
152 }
153 if (--i < 0) {
154 i = entries.length - 1;
155 }
156 }
157 }
158
159 /**
160 * Get a matching DNS entry from the table.
161 */
162 DNSEntry get(String name, int type, int clazz)
163 {
164 String key = name.toLowerCase();
165 int i = Math.abs(key.hashCode()) % entries.length;
166 while (true) {
167 DNSEntry e = entries[i];
168 if (e == null) {
169 return null;
170 }
171 if (key.equals(e.key) && (type == e.type) && (clazz == e.clazz)) {
172 return e;
173 }
174 if (--i < 0) {
175 i = entries.length - 1;
176 }
177 }
178 }
179
180 /**
181 * Iterate over all entries.
182 */
183 Iterator all()
184 {
185 return new IterateAll();
186 }
187
188 /**
189 * Iterate only over items with matching name.
190 */
191 Iterator find(String name)
192 {
193 return new IterateKey(name.toLowerCase());
194 }
195
196 /**
197 * Iterate over all entries.
198 */
199 private class IterateAll implements Iterator
200 {
201 int index;
202
203 IterateAll()
204 {
205 index = entries.length - 1;
206 }
207
208 public boolean hasNext()
209 {
210 for (; index >= 0 ; index--) {
211 if (entries[index] != null) {
212 return true;
213 }
214 }
215 return false;
216 }
217
218 public Object next()
219 {
220 return entries[index--];
221 }
222
223 public void remove()
224 {
225 DNSCache.this.remove(++index);
226 }
227 }
228
229 /**
230 * Iterate over some entries.
231 */
232 private class IterateKey implements Iterator
233 {
234 String key;
235 int index;
236
237 IterateKey(String key)
238 {
239 this.key = key;
240 this.index = Math.abs(key.hashCode()) % entries.length;
241 }
242
243 public boolean hasNext()
244 {
245 while (true) {
246 if (index < 0) {
247 index = entries.length - 1;
248 }
249 DNSEntry e = entries[index];
250 if (e == null) {
251 return false;
252 }
253 if (e.key.equals(key)) {
254 return true;
255 }
256 index--;
257 }
258 }
259
260 public Object next()
261 {
262 return entries[index--];
263 }
264
265 public void remove()
266 {
267 DNSCache.this.remove(++index);
268 }
269 }
270
271
272 /**
273 * List all entries for debugging.
274 */
275 void print()
276 {
277 for (Iterator i = all() ; i.hasNext() ;) {
278 System.out.println(i.next());
279 }
280 }
281 }