ReactOS  0.4.11-dev-946-g431643b
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
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 
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 
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 }
char ** h_addr_list
Definition: winsock.h:138
Definition: get.c:139
__int64 TIME
Definition: ms-dtyp.idl:32
#define warn(...)
#define error(str)
Definition: mkdosfs.c:1605
LPBATCH_CONTEXT bc
Definition: batch.c:66
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
void dfree(void *ptr, char *name)
Definition: alloc.c:79
struct _tree tree
time_t cur_time
tree * free_tree(tree *t)
Definition: treefuncs.c:284
Definition: dhcpd.h:245
struct tree_cache * tree_cache(struct tree *tree)
Definition: tree.c:69
char * caddr_t
Definition: rosdhcp.h:36
GLbitfield GLuint64 timeout
Definition: glext.h:7164
IMAGE_NT_HEADERS nt
Definition: module.c:50
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLint limit
Definition: glext.h:10326
char * hostname
Definition: ftp.c:88
GLenum GLclampf GLint i
Definition: glfuncs.h:14
UINT op
Definition: effect.c:223
struct tree * tree_host_lookup(char *name)
Definition: tree.c:84
short h_length
Definition: winsock.h:137
static void do_data_copy(int *bufix, unsigned char **bufp, int *bufcount, unsigned char *data, int len)
Definition: tree.c:394
const GLfloat * tc
Definition: glext.h:8925
static char copyright[]
Definition: tree.c:44
PHOSTENT WSAAPI gethostbyname(IN const char FAR *name)
Definition: getxbyxx.c:221
pair cons(caddr_t car, pair cdr)
Definition: tree.c:57
int foo()
GLint left
Definition: glext.h:7726
struct _pair * pair
GLdouble GLdouble right
Definition: glext.h:10859
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
int tree_evaluate(struct tree_cache *tree_cache)
Definition: tree.c:194
struct tree * tree_const(unsigned char *data, int len)
Definition: tree.c:114
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum GLsizei len
Definition: glext.h:6722
static TIME tree_evaluate_recurse(int *bufix, unsigned char **bufp, int *bufcount, struct tree *tree)
Definition: tree.c:240
GLsizei const GLfloat * value
Definition: glext.h:6069
#define HOST_NOT_FOUND
Definition: winsock.h:226
#define NO_RECOVERY
Definition: winsock.h:228
struct tree * tree_concat(struct tree *left, struct tree *right)
Definition: tree.c:129
#define TRY_AGAIN
Definition: winsock.h:227
Definition: _pair.h:47
int buf_size
Definition: tree.h:51
static TIME do_host_lookup(int *bufix, unsigned char **bufp, int *bufcount, struct dns_host_entry *dns)
Definition: tree.c:284
#define MAX_TIME
Definition: dhcpd.h:278
struct tree * tree_limit(struct tree *tree, int limit)
Definition: tree.c:171
static TIME tree_evaluate_recurse PROTO((int *, unsigned char **, int *, struct tree *))
Definition: name.c:36
char * strcpy(char *DstString, const char *SrcString)
Definition: utclib.c:388
#define debug(msg)
Definition: key_call.c:71
#define h_errno
Definition: winsock.h:225
#define NO_DATA
Definition: winsock.h:229
void * dmalloc(int size, char *name)
Definition: util.c:104
struct dns_host_entry * enter_dns_host(char *name)
Definition: tree.c:96
GLuint const GLchar * name
Definition: glext.h:6031