tree.c File Reference

#include <rosdhcp.h>

Include dependency graph for tree.c:

Go to the source code of this file.

Functions
static TIME tree_evaluate_recurse	PROTO ((int *, unsigned char **, int *, struct tree *))
static TIME do_host_lookup	PROTO ((int *, unsigned char **, int *, struct dns_host_entry *))
static void do_data_copy	PROTO ((int *, unsigned char **, int *, unsigned char *, int))
pair	cons (caddr_t car, pair cdr)
struct tree_cache *	tree_cache (struct tree *tree)
struct tree *	tree_host_lookup (char *name)
struct dns_host_entry *	enter_dns_host (char *name)
struct tree *	tree_const (unsigned char *data, int len)
struct tree *	tree_concat (struct tree *left, struct tree *right)
struct tree *	tree_limit (struct tree *tree, int limit)
int	tree_evaluate (struct tree_cache *tree_cache)
static TIME	tree_evaluate_recurse (int *bufix, unsigned char **bufp, int *bufcount, struct tree *tree)
static TIME	do_host_lookup (int *bufix, unsigned char **bufp, int *bufcount, struct dns_host_entry *dns)
static void	do_data_copy (int *bufix, unsigned char **bufp, int *bufcount, unsigned char *data, int len)

Variables
static char	copyright []

Function Documentation

cons()

pair cons	(	caddr_t	car,
		pair	cdr
	)

Definition at line 57 of file tree.c.

{
    pair foo = (pair)dmalloc (sizeof *foo, "cons");
    if (!foo)
        error ("no memory for cons.");
    foo -> car = car;
    foo -> cdr = cdr;
    return foo;
}

Referenced by xmlParseConditionalSections(), xmlParseContentInternal(), xmlParseExternalSubset(), xmlParseInternalSubset(), and xmlParseStartTag2().

do_data_copy()

static void do_data_copy ( int *  bufix, unsigned char **  bufp, int *  bufcount, unsigned char *  data, int  len  )

static

Definition at line 394 of file tree.c.

{
    int space = *bufcount - *bufix;

    /* If there's more space than we need, use only what we need. */
    if (space > len)
        space = len;

    /* Copy as much data as will fit, then increment the buffer index
       by the amount we actually had to copy, which could be more. */
    if (space > 0)
        memcpy (*bufp + *bufix, data, space);
    *bufix += len;
}

Referenced by do_host_lookup(), and tree_evaluate_recurse().

do_host_lookup()

static TIME do_host_lookup ( int *  bufix, unsigned char **  bufp, int *  bufcount, struct dns_host_entry *  dns  )

static

Definition at line 284 of file tree.c.

{
    struct hostent *h;
    int i;
    int new_len;

#ifdef DEBUG_EVAL
    debug ("time: now = %d  dns = %d %d  diff = %d",
           cur_time, dns -> timeout, cur_time - dns -> timeout);
#endif

    /* If the record hasn't timed out, just copy the data and return. */
    if (cur_time <= dns -> timeout) {
#ifdef DEBUG_EVAL
        debug ("easy copy: %x %d %x",
               dns -> data, dns -> data_len,
               dns -> data ? *(int *)(dns -> data) : 0);
#endif
        do_data_copy (bufix, bufp, bufcount,
                  dns -> data, dns -> data_len);
        return dns -> timeout;
    }
#ifdef DEBUG_EVAL
    debug ("Looking up %s", dns -> hostname);
#endif

    /* Otherwise, look it up... */
    h = gethostbyname (dns -> hostname);
    if (!h) {
#ifndef NO_H_ERRNO
        switch (h_errno) {
              case HOST_NOT_FOUND:
#endif
            warn ("%s: host unknown.", dns -> hostname);
#ifndef NO_H_ERRNO
            break;
              case TRY_AGAIN:
            warn ("%s: temporary name server failure",
                  dns -> hostname);
            break;
              case NO_RECOVERY:
            warn ("%s: name server failed", dns -> hostname);
            break;
              case NO_DATA:
            warn ("%s: no A record associated with address",
                  dns -> hostname);
        }
#endif /* !NO_H_ERRNO */

        /* Okay to try again after a minute. */
        return cur_time + 60;
    }

#ifdef DEBUG_EVAL
    debug ("Lookup succeeded; first address is %x",
           h -> h_addr_list [0]);
#endif

    /* Count the number of addresses we got... */
    for (i = 0; h -> h_addr_list [i]; i++)
        ;

    /* Do we need to allocate more memory? */
    new_len = i * h -> h_length;
    if (dns -> buf_len < i) {
        unsigned char *buf =
            (unsigned char *)dmalloc (new_len, "do_host_lookup");
        /* If we didn't get more memory, use what we have. */
        if (!buf) {
            new_len = dns -> buf_len;
            if (!dns -> buf_len) {
                dns -> timeout = cur_time + 60;
                return dns -> timeout;
            }
        } else {
            if (dns -> data)
                dfree (dns -> data, "do_host_lookup");
            dns -> data = buf;
            dns -> buf_len = new_len;
        }
    }

    /* Addresses are conveniently stored one to the buffer, so we
       have to copy them out one at a time... :'( */
    for (i = 0; i < new_len / h -> h_length; i++) {
        memcpy (dns -> data + h -> h_length * i,
            h -> h_addr_list [i], h -> h_length);
    }
#ifdef DEBUG_EVAL
    debug ("dns -> data: %x  h -> h_addr_list [0]: %x",
           *(int *)(dns -> data), h -> h_addr_list [0]);
#endif
    dns -> data_len = new_len;

    /* Set the timeout for an hour from now.
       XXX This should really use the time on the DNS reply. */
    dns -> timeout = cur_time + 3600;

#ifdef DEBUG_EVAL
    debug ("hard copy: %x %d %x",
           dns -> data, dns -> data_len, *(int *)(dns -> data));
#endif
    do_data_copy (bufix, bufp, bufcount, dns -> data, dns -> data_len);
    return dns -> timeout;
}

Referenced by tree_evaluate_recurse().

enter_dns_host()

struct dns_host_entry* enter_dns_host

(

char *

name

)

Definition at line 96 of file tree.c.

{
    struct dns_host_entry *dh;

    if (!(dh = (struct dns_host_entry *)dmalloc
          (sizeof (struct dns_host_entry), "enter_dns_host"))
        || !(dh -> hostname = dmalloc (strlen (name) + 1,
                       "enter_dns_host")))
        error ("Can't allocate space for new host.");
    strcpy (dh -> hostname, name);
    dh -> data = (unsigned char *)0;
    dh -> data_len = 0;
    dh -> buf_len = 0;
    dh -> timeout = 0;
    return dh;
}

Referenced by tree_host_lookup().

PROTO() [1/3]

static TIME tree_evaluate_recurse PROTO ( (int *, unsigned char **, int *, struct tree *)  )

static

PROTO() [2/3]

static TIME do_host_lookup PROTO ( (int *, unsigned char **, int *, struct dns_host_entry *)  )

static

PROTO() [3/3]

static void do_data_copy PROTO ( (int *, unsigned char **, int *, unsigned char *, int)  )

static

tree_cache()

struct tree_cache* tree_cache

(

struct tree *

tree

)

Definition at line 69 of file tree.c.

{
    struct tree_cache *tc;

    tc = new_tree_cache ("tree_cache");
    if (!tc)
        return 0;
    tc -> value = (unsigned char *)0;
    tc -> len = tc -> buf_size = 0;
    tc -> timeout = 0;
    tc -> tree = tree;
    return tc;
}

tree_concat()

struct tree* tree_concat	(	struct tree *	left,
		struct tree *	right
	)

Definition at line 129 of file tree.c.

{
    struct tree *nt;

    /* If we're concatenating a null tree to a non-null tree, just
       return the non-null tree; if both trees are null, return
       a null tree. */
    if (!left)
        return right;
    if (!right)
        return left;

    /* If both trees are constant, combine them. */
    if (left -> op == TREE_CONST && right -> op == TREE_CONST) {
        unsigned char *buf = dmalloc (left -> data.const_val.len
                          + right -> data.const_val.len,
                          "tree_concat");
        if (!buf)
            error ("No memory to concatenate constants.");
        memcpy (buf, left -> data.const_val.data,
            left -> data.const_val.len);
        memcpy (buf + left -> data.const_val.len,
            right -> data.const_val.data,
            right -> data.const_val.len);
        dfree (left -> data.const_val.data, "tree_concat");
        dfree (right -> data.const_val.data, "tree_concat");
        left -> data.const_val.data = buf;
        left -> data.const_val.len += right -> data.const_val.len;
        free_tree (right, "tree_concat");
        return left;
    }

    /* Otherwise, allocate a new node to concatenate the two. */
    if (!(nt = new_tree ("tree_concat")))
        error ("No memory for data tree concatenation node.");
    nt -> op = TREE_CONCAT;
    nt -> data.concat.left = left;
    nt -> data.concat.right = right;
    return nt;
}

tree_const()

struct tree* tree_const	(	unsigned char *	data,
		int	len
	)

Definition at line 114 of file tree.c.

{
    struct tree *nt;
    if (!(nt = new_tree ("tree_const"))
        || !(nt -> data.const_val.data =
         (unsigned char *)dmalloc (len, "tree_const")))
        error ("No memory for constant data tree node.");
    nt -> op = TREE_CONST;
    memcpy (nt -> data.const_val.data, data, len);
    nt -> data.const_val.len = len;
    return nt;
}

tree_evaluate()

int tree_evaluate

(

struct tree_cache *

tree_cache

)

Definition at line 194 of file tree.c.

{
    unsigned char *bp = tree_cache -> value;
    int bc = tree_cache -> buf_size;
    int bufix = 0;

    /* If there's no tree associated with this cache, it evaluates
       to a constant and that was detected at startup. */
    if (!tree_cache -> tree)
        return 1;

    /* Try to evaluate the tree without allocating more memory... */
    tree_cache -> timeout = tree_evaluate_recurse (&bufix, &bp, &bc,
                               tree_cache -> tree);

    /* No additional allocation needed? */
    if (bufix <= bc) {
        tree_cache -> len = bufix;
        return 1;
    }

    /* If we can't allocate more memory, return with what we
       have (maybe nothing). */
    if (!(bp = (unsigned char *)dmalloc (bufix, "tree_evaluate")))
        return 0;

    /* Record the change in conditions... */
    bc = bufix;
    bufix = 0;

    /* Note that the size of the result shouldn't change on the
       second call to tree_evaluate_recurse, since we haven't
       changed the ``current'' time. */
    tree_evaluate_recurse (&bufix, &bp, &bc, tree_cache -> tree);

    /* Free the old buffer if needed, then store the new buffer
       location and size and return. */
    if (tree_cache -> value)
        dfree (tree_cache -> value, "tree_evaluate");
    tree_cache -> value = bp;
    tree_cache -> len = bufix;
    tree_cache -> buf_size = bc;
    return 1;
}

tree_evaluate_recurse()

static TIME tree_evaluate_recurse ( int *  bufix, unsigned char **  bufp, int *  bufcount, struct tree *  tree  )

static

Definition at line 240 of file tree.c.

{
    int limit;
    TIME t1, t2;

    switch (tree -> op) {
          case TREE_CONCAT:
        t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
                       tree -> data.concat.left);
        t2 = tree_evaluate_recurse (bufix, bufp, bufcount,
                       tree -> data.concat.right);
        if (t1 > t2)
            return t2;
        return t1;

          case TREE_HOST_LOOKUP:
        return do_host_lookup (bufix, bufp, bufcount,
                       tree -> data.host_lookup.host);

          case TREE_CONST:
        do_data_copy (bufix, bufp, bufcount,
                  tree -> data.const_val.data,
                  tree -> data.const_val.len);
        t1 = MAX_TIME;
        return t1;

          case TREE_LIMIT:
        limit = *bufix + tree -> data.limit.limit;
        t1 = tree_evaluate_recurse (bufix, bufp, bufcount,
                        tree -> data.limit.tree);
        *bufix = limit;
        return t1;

          default:
        warn ("Bad node id in tree: %d.");
        t1 = MAX_TIME;
        return t1;
    }
}

Referenced by tree_evaluate().

tree_host_lookup()

struct tree* tree_host_lookup

(

char *

name

)

Definition at line 84 of file tree.c.

{
    struct tree *nt;
    nt = new_tree ("tree_host_lookup");
    if (!nt)
        error ("No memory for host lookup tree node.");
    nt -> op = TREE_HOST_LOOKUP;
    nt -> data.host_lookup.host = enter_dns_host (name);
    return nt;
}

tree_limit()

struct tree* tree_limit	(	struct tree *	tree,
		int	limit
	)

Definition at line 171 of file tree.c.

{
    struct tree *rv;

    /* If the tree we're limiting is constant, limit it now. */
    if (tree -> op == TREE_CONST) {
        if (tree -> data.const_val.len > limit)
            tree -> data.const_val.len = limit;
        return tree;
    }

    /* Otherwise, put in a node which enforces the limit on evaluation. */
    rv = new_tree ("tree_limit");
    if (!rv)
        return (struct tree *)0;
    rv -> op = TREE_LIMIT;
    rv -> data.limit.tree = tree;
    rv -> data.limit.limit = limit;
    return rv;
}

Variable Documentation

copyright

char copyright[]

static

Initial value:

=
"$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"

Definition at line 44 of file tree.c.