[DHCP]
[reactos.git] / reactos / base / services / dhcp / tree.c
1 /* tree.c
2
3 Routines for manipulating parse trees... */
4
5 /*
6 * Copyright (c) 1995, 1996, 1997 The Internet Software Consortium.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of The Internet Software Consortium nor the names
19 * of its contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE INTERNET SOFTWARE CONSORTIUM AND
23 * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
24 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
26 * DISCLAIMED. IN NO EVENT SHALL THE INTERNET SOFTWARE CONSORTIUM OR
27 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * This software has been written for the Internet Software Consortium
37 * by Ted Lemon <mellon@fugue.com> in cooperation with Vixie
38 * Enterprises. To learn more about the Internet Software Consortium,
39 * see ``http://www.vix.com/isc''. To learn more about Vixie
40 * Enterprises, see ``http://www.vix.com''.
41 */
42
43 #ifndef lint
44 static char copyright[] =
45 "$Id: tree.c,v 1.10 1997/05/09 08:14:57 mellon Exp $ Copyright (c) 1995, 1996, 1997 The Internet Software Consortium. All rights reserved.\n";
46 #endif /* not lint */
47
48 #include "rosdhcp.h"
49
50 static TIME tree_evaluate_recurse PROTO ((int *, unsigned char **, int *,
51 struct tree *));
52 static TIME do_host_lookup PROTO ((int *, unsigned char **, int *,
53 struct dns_host_entry *));
54 static void do_data_copy PROTO ((int *, unsigned char **, int *,
55 unsigned char *, int));
56
57 pair cons (car, cdr)
58 caddr_t car;
59 pair cdr;
60 {
61 pair foo = (pair)dmalloc (sizeof *foo, "cons");
62 if (!foo)
63 error ("no memory for cons.");
64 foo -> car = car;
65 foo -> cdr = cdr;
66 return foo;
67 }
68
69 struct tree_cache *tree_cache (tree)
70 struct tree *tree;
71 {
72 struct tree_cache *tc;
73
74 tc = new_tree_cache ("tree_cache");
75 if (!tc)
76 return 0;
77 tc -> value = (unsigned char *)0;
78 tc -> len = tc -> buf_size = 0;
79 tc -> timeout = 0;
80 tc -> tree = tree;
81 return tc;
82 }
83
84 struct tree *tree_host_lookup (name)
85 char *name;
86 {
87 struct tree *nt;
88 nt = new_tree ("tree_host_lookup");
89 if (!nt)
90 error ("No memory for host lookup tree node.");
91 nt -> op = TREE_HOST_LOOKUP;
92 nt -> data.host_lookup.host = enter_dns_host (name);
93 return nt;
94 }
95
96 struct dns_host_entry *enter_dns_host (name)
97 char *name;
98 {
99 struct dns_host_entry *dh;
100
101 if (!(dh = (struct dns_host_entry *)dmalloc
102 (sizeof (struct dns_host_entry), "enter_dns_host"))
103 || !(dh -> hostname = dmalloc (strlen (name) + 1,
104 "enter_dns_host")))
105 error ("Can't allocate space for new host.");
106 strcpy (dh -> hostname, name);
107 dh -> data = (unsigned char *)0;
108 dh -> data_len = 0;
109 dh -> buf_len = 0;
110 dh -> timeout = 0;
111 return dh;
112 }
113
114 struct tree *tree_const (data, len)
115 unsigned char *data;
116 int len;
117 {
118 struct tree *nt;
119 if (!(nt = new_tree ("tree_const"))
120 || !(nt -> data.const_val.data =
121 (unsigned char *)dmalloc (len, "tree_const")))
122 error ("No memory for constant data tree node.");
123 nt -> op = TREE_CONST;
124 memcpy (nt -> data.const_val.data, data, len);
125 nt -> data.const_val.len = len;
126 return nt;
127 }
128
129 struct tree *tree_concat (left, right)
130 struct tree *left, *right;
131 {
132 struct tree *nt;
133
134 /* If we're concatenating a null tree to a non-null tree, just
135 return the non-null tree; if both trees are null, return
136 a null tree. */
137 if (!left)
138 return right;
139 if (!right)
140 return left;
141
142 /* If both trees are constant, combine them. */
143 if (left -> op == TREE_CONST && right -> op == TREE_CONST) {
144 unsigned char *buf = dmalloc (left -> data.const_val.len
145 + right -> data.const_val.len,
146 "tree_concat");
147 if (!buf)
148 error ("No memory to concatenate constants.");
149 memcpy (buf, left -> data.const_val.data,
150 left -> data.const_val.len);
151 memcpy (buf + left -> data.const_val.len,
152 right -> data.const_val.data,
153 right -> data.const_val.len);
154 dfree (left -> data.const_val.data, "tree_concat");
155 dfree (right -> data.const_val.data, "tree_concat");
156 left -> data.const_val.data = buf;
157 left -> data.const_val.len += right -> data.const_val.len;
158 free_tree (right, "tree_concat");
159 return left;
160 }
161
162 /* Otherwise, allocate a new node to concatenate the two. */
163 if (!(nt = new_tree ("tree_concat")))
164 error ("No memory for data tree concatenation node.");
165 nt -> op = TREE_CONCAT;
166 nt -> data.concat.left = left;
167 nt -> data.concat.right = right;
168 return nt;
169 }
170
171 struct tree *tree_limit (tree, limit)
172 struct tree *tree;
173 int limit;
174 {
175 struct tree *rv;
176
177 /* If the tree we're limiting is constant, limit it now. */
178 if (tree -> op == TREE_CONST) {
179 if (tree -> data.const_val.len > limit)
180 tree -> data.const_val.len = limit;
181 return tree;
182 }
183
184 /* Otherwise, put in a node which enforces the limit on evaluation. */
185 rv = new_tree ("tree_limit");
186 if (!rv)
187 return (struct tree *)0;
188 rv -> op = TREE_LIMIT;
189 rv -> data.limit.tree = tree;
190 rv -> data.limit.limit = limit;
191 return rv;
192 }
193
194 int tree_evaluate (tree_cache)
195 struct tree_cache *tree_cache;
196 {
197 unsigned char *bp = tree_cache -> value;
198 int bc = tree_cache -> buf_size;
199 int bufix = 0;
200
201 /* If there's no tree associated with this cache, it evaluates
202 to a constant and that was detected at startup. */
203 if (!tree_cache -> tree)
204 return 1;
205
206 /* Try to evaluate the tree without allocating more memory... */
207 tree_cache -> timeout = tree_evaluate_recurse (&bufix, &bp, &bc,
208 tree_cache -> tree);
209
210 /* No additional allocation needed? */
211 if (bufix <= bc) {
212 tree_cache -> len = bufix;
213 return 1;
214 }
215
216 /* If we can't allocate more memory, return with what we
217 have (maybe nothing). */
218 if (!(bp = (unsigned char *)dmalloc (bufix, "tree_evaluate")))
219 return 0;
220
221 /* Record the change in conditions... */
222 bc = bufix;
223 bufix = 0;
224
225 /* Note that the size of the result shouldn't change on the
226 second call to tree_evaluate_recurse, since we haven't
227 changed the ``current'' time. */
228 tree_evaluate_recurse (&bufix, &bp, &bc, tree_cache -> tree);
229
230 /* Free the old buffer if needed, then store the new buffer
231 location and size and return. */
232 if (tree_cache -> value)
233 dfree (tree_cache -> value, "tree_evaluate");
234 tree_cache -> value = bp;
235 tree_cache -> len = bufix;
236 tree_cache -> buf_size = bc;
237 return 1;
238 }
239
240 static TIME tree_evaluate_recurse (bufix, bufp, bufcount, tree)
241 int *bufix;
242 unsigned char **bufp;
243 int *bufcount;
244 struct tree *tree;
245 {
246 int limit;
247 TIME t1, t2;
248
249 switch (tree -> op) {
250 case TREE_CONCAT:
251 t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
252 tree -> data.concat.left);
253 t2 = tree_evaluate_recurse (bufix, bufp, bufcount,
254 tree -> data.concat.right);
255 if (t1 > t2)
256 return t2;
257 return t1;
258
259 case TREE_HOST_LOOKUP:
260 return do_host_lookup (bufix, bufp, bufcount,
261 tree -> data.host_lookup.host);
262
263 case TREE_CONST:
264 do_data_copy (bufix, bufp, bufcount,
265 tree -> data.const_val.data,
266 tree -> data.const_val.len);
267 t1 = MAX_TIME;
268 return t1;
269
270 case TREE_LIMIT:
271 limit = *bufix + tree -> data.limit.limit;
272 t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
273 tree -> data.limit.tree);
274 *bufix = limit;
275 return t1;
276
277 default:
278 warn ("Bad node id in tree: %d.");
279 t1 = MAX_TIME;
280 return t1;
281 }
282 }
283
284 static TIME do_host_lookup (bufix, bufp, bufcount, dns)
285 int *bufix;
286 unsigned char **bufp;
287 int *bufcount;
288 struct dns_host_entry *dns;
289 {
290 struct hostent *h;
291 int i;
292 int new_len;
293
294 #ifdef DEBUG_EVAL
295 debug ("time: now = %d dns = %d %d diff = %d",
296 cur_time, dns -> timeout, cur_time - dns -> timeout);
297 #endif
298
299 /* If the record hasn't timed out, just copy the data and return. */
300 if (cur_time <= dns -> timeout) {
301 #ifdef DEBUG_EVAL
302 debug ("easy copy: %x %d %x",
303 dns -> data, dns -> data_len,
304 dns -> data ? *(int *)(dns -> data) : 0);
305 #endif
306 do_data_copy (bufix, bufp, bufcount,
307 dns -> data, dns -> data_len);
308 return dns -> timeout;
309 }
310 #ifdef DEBUG_EVAL
311 debug ("Looking up %s", dns -> hostname);
312 #endif
313
314 /* Otherwise, look it up... */
315 h = gethostbyname (dns -> hostname);
316 if (!h) {
317 #ifndef NO_H_ERRNO
318 switch (h_errno) {
319 case HOST_NOT_FOUND:
320 #endif
321 warn ("%s: host unknown.", dns -> hostname);
322 #ifndef NO_H_ERRNO
323 break;
324 case TRY_AGAIN:
325 warn ("%s: temporary name server failure",
326 dns -> hostname);
327 break;
328 case NO_RECOVERY:
329 warn ("%s: name server failed", dns -> hostname);
330 break;
331 case NO_DATA:
332 warn ("%s: no A record associated with address",
333 dns -> hostname);
334 }
335 #endif /* !NO_H_ERRNO */
336
337 /* Okay to try again after a minute. */
338 return cur_time + 60;
339 }
340
341 #ifdef DEBUG_EVAL
342 debug ("Lookup succeeded; first address is %x",
343 h -> h_addr_list [0]);
344 #endif
345
346 /* Count the number of addresses we got... */
347 for (i = 0; h -> h_addr_list [i]; i++)
348 ;
349
350 /* Do we need to allocate more memory? */
351 new_len = i * h -> h_length;
352 if (dns -> buf_len < i) {
353 unsigned char *buf =
354 (unsigned char *)dmalloc (new_len, "do_host_lookup");
355 /* If we didn't get more memory, use what we have. */
356 if (!buf) {
357 new_len = dns -> buf_len;
358 if (!dns -> buf_len) {
359 dns -> timeout = cur_time + 60;
360 return dns -> timeout;
361 }
362 } else {
363 if (dns -> data)
364 dfree (dns -> data, "do_host_lookup");
365 dns -> data = buf;
366 dns -> buf_len = new_len;
367 }
368 }
369
370 /* Addresses are conveniently stored one to the buffer, so we
371 have to copy them out one at a time... :'( */
372 for (i = 0; i < new_len / h -> h_length; i++) {
373 memcpy (dns -> data + h -> h_length * i,
374 h -> h_addr_list [i], h -> h_length);
375 }
376 #ifdef DEBUG_EVAL
377 debug ("dns -> data: %x h -> h_addr_list [0]: %x",
378 *(int *)(dns -> data), h -> h_addr_list [0]);
379 #endif
380 dns -> data_len = new_len;
381
382 /* Set the timeout for an hour from now.
383 XXX This should really use the time on the DNS reply. */
384 dns -> timeout = cur_time + 3600;
385
386 #ifdef DEBUG_EVAL
387 debug ("hard copy: %x %d %x",
388 dns -> data, dns -> data_len, *(int *)(dns -> data));
389 #endif
390 do_data_copy (bufix, bufp, bufcount, dns -> data, dns -> data_len);
391 return dns -> timeout;
392 }
393
394 static void do_data_copy (bufix, bufp, bufcount, data, len)
395 int *bufix;
396 unsigned char **bufp;
397 int *bufcount;
398 unsigned char *data;
399 int len;
400 {
401 int space = *bufcount - *bufix;
402
403 /* If there's more space than we need, use only what we need. */
404 if (space > len)
405 space = len;
406
407 /* Copy as much data as will fit, then increment the buffer index
408 by the amount we actually had to copy, which could be more. */
409 if (space > 0)
410 memcpy (*bufp + *bufix, data, space);
411 *bufix += len;
412 }