ReactOS 0.4.15-dev-5664-g3bf4ef6
tree.c
Go to the documentation of this file.
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
44static 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
50static TIME tree_evaluate_recurse PROTO ((int *, unsigned char **, int *,
51 struct tree *));
52static TIME do_host_lookup PROTO ((int *, unsigned char **, int *,
53 struct dns_host_entry *));
54static void do_data_copy PROTO ((int *, unsigned char **, int *,
55 unsigned char *, int));
56
57pair 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
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
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
96struct 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
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
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
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
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;
237 return 1;
238}
239
240static 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
284static 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
394static 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}
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
char * strcpy(char *DstString, const char *SrcString)
Definition: utclib.c:388
void dfree(void *ptr, char *name)
Definition: alloc.c:79
char * hostname
Definition: ftp.c:88
struct tree * tree_concat(struct tree *left, struct tree *right)
Definition: tree.c:129
static void do_data_copy(int *bufix, unsigned char **bufp, int *bufcount, unsigned char *data, int len)
Definition: tree.c:394
struct tree * tree_const(unsigned char *data, int len)
Definition: tree.c:114
int tree_evaluate(struct tree_cache *tree_cache)
Definition: tree.c:194
static TIME do_host_lookup(int *bufix, unsigned char **bufp, int *bufcount, struct dns_host_entry *dns)
Definition: tree.c:284
static TIME tree_evaluate_recurse(int *bufix, unsigned char **bufp, int *bufcount, struct tree *tree)
Definition: tree.c:240
static char copyright[]
Definition: tree.c:44
struct tree * tree_limit(struct tree *tree, int limit)
Definition: tree.c:171
struct dns_host_entry * enter_dns_host(char *name)
Definition: tree.c:96
pair cons(caddr_t car, pair cdr)
Definition: tree.c:57
struct tree * tree_host_lookup(char *name)
Definition: tree.c:84
void * dmalloc(int size, char *name)
Definition: util.c:104
PBATCH_CONTEXT bc
Definition: batch.c:67
NTSTATUS NTSTATUS void free_tree(tree *t) __attribute__((nonnull(1)))
struct _tree tree
#define MAX_TIME
Definition: dhcpd.h:278
time_t cur_time
UINT op
Definition: effect.c:236
PHOSTENT WSAAPI gethostbyname(IN const char FAR *name)
Definition: getxbyxx.c:221
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
const GLfloat * tc
Definition: glext.h:8925
GLdouble GLdouble right
Definition: glext.h:10859
GLint limit
Definition: glext.h:10326
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLint left
Definition: glext.h:7726
GLenum GLsizei len
Definition: glext.h:6722
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define debug(msg)
Definition: key_call.c:71
#define error(str)
Definition: mkdosfs.c:1605
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
IMAGE_NT_HEADERS nt
Definition: module.c:50
__int64 TIME
Definition: ms-dtyp.idl:32
#define warn(...)
char * caddr_t
Definition: rosdhcp.h:36
#define PROTO(x)
Definition: rosdhcp.h:57
short h_length
Definition: winsock.h:137
char ** h_addr_list
Definition: winsock.h:138
Definition: name.c:39
Definition: _pair.h:47
Definition: dhcpd.h:245
int buf_size
Definition: tree.h:51
unsigned char * value
Definition: tree.h:49
Definition: pdh_main.c:94
#define NO_DATA
Definition: winsock.h:229
#define NO_RECOVERY
Definition: winsock.h:228
#define HOST_NOT_FOUND
Definition: winsock.h:226
#define h_errno
Definition: winsock.h:225
#define TRY_AGAIN
Definition: winsock.h:227