ReactOS  0.4.13-dev-249-gcba1a2f
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 
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 
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;
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
__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
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
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
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
void free_tree(tree *t)
Definition: treefuncs.c:260
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
UINT op
Definition: effect.c:223
#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