1 /* $OpenBSD: tree.c,v 1.11 2006/03/13 19:57:42 otto Exp $ */ 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 #include "dhcpd.h" 44 45 static time_t tree_evaluate_recurse(int *, unsigned char **, int *, 46 struct tree *); 47 static void do_data_copy(int *, unsigned char **, int *, unsigned char *, int); 48 49 pair 50 cons(caddr_t car, pair cdr) 51 { 52 pair foo = (pair)dmalloc(sizeof *foo, "cons"); 53 if (!foo) 54 error("no memory for cons."); 55 foo->car = car; 56 foo->cdr = cdr; 57 return foo; 58 } 59 60 struct tree_cache * 61 tree_cache(struct tree *tree) 62 { 63 struct tree_cache *tc; 64 65 tc = new_tree_cache("tree_cache"); 66 if (!tc) 67 return 0; 68 tc->value = NULL; 69 tc->len = tc->buf_size = 0; 70 tc->timeout = 0; 71 tc->tree = tree; 72 return tc; 73 } 74 75 struct tree * 76 tree_const(unsigned char *data, int len) 77 { 78 struct tree *nt; 79 80 if (!(nt = new_tree("tree_const")) || !(nt->data.const_val.data = 81 (unsigned char *)dmalloc(len, "tree_const"))) 82 error("No memory for constant data tree node."); 83 nt->op = TREE_CONST; 84 memcpy(nt->data.const_val.data, data, len); 85 nt->data.const_val.len = len; 86 return nt; 87 } 88 89 struct tree * 90 tree_concat(struct tree *left, struct tree *right) 91 { 92 struct tree *nt; 93 94 /* 95 * If we're concatenating a null tree to a non-null tree, just 96 * return the non-null tree; if both trees are null, return 97 * a null tree. 98 */ 99 if (!left) 100 return right; 101 if (!right) 102 return left; 103 104 /* If both trees are constant, combine them. */ 105 if (left->op == TREE_CONST && right->op == TREE_CONST) { 106 unsigned char *buf = dmalloc(left->data.const_val.len 107 + right->data.const_val.len, "tree_concat"); 108 109 if (!buf) 110 error("No memory to concatenate constants."); 111 memcpy(buf, left->data.const_val.data, 112 left->data.const_val.len); 113 memcpy(buf + left->data.const_val.len, 114 right->data.const_val.data, right->data.const_val.len); 115 dfree(left->data.const_val.data, "tree_concat"); 116 dfree(right->data.const_val.data, "tree_concat"); 117 left->data.const_val.data = buf; 118 left->data.const_val.len += right->data.const_val.len; 119 free_tree(right, "tree_concat"); 120 return left; 121 } 122 123 /* Otherwise, allocate a new node to concatenate the two. */ 124 if (!(nt = new_tree("tree_concat"))) 125 error("No memory for data tree concatenation node."); 126 nt->op = TREE_CONCAT; 127 nt->data.concat.left = left; 128 nt->data.concat.right = right; 129 return nt; 130 } 131 132 struct tree * 133 tree_limit(struct tree *tree, int limit) 134 { 135 struct tree *rv; 136 137 /* If the tree we're limiting is constant, limit it now. */ 138 if (tree->op == TREE_CONST) { 139 if (tree->data.const_val.len > limit) 140 tree->data.const_val.len = limit; 141 return tree; 142 } 143 144 /* Otherwise, put in a node which enforces the limit on evaluation. */ 145 rv = new_tree("tree_limit"); 146 if (!rv) 147 return NULL; 148 rv->op = TREE_LIMIT; 149 rv->data.limit.tree = tree; 150 rv->data.limit.limit = limit; 151 return rv; 152 } 153 154 int 155 tree_evaluate(struct tree_cache *tree_cache) 156 { 157 unsigned char *bp = tree_cache->value; 158 int bc = tree_cache->buf_size; 159 int bufix = 0; 160 161 /* 162 * If there's no tree associated with this cache, it evaluates to a 163 * constant and that was detected at startup. 164 */ 165 if (!tree_cache->tree) 166 return 1; 167 168 /* Try to evaluate the tree without allocating more memory... */ 169 tree_cache->timeout = tree_evaluate_recurse(&bufix, &bp, &bc, 170 tree_cache->tree); 171 172 /* No additional allocation needed? */ 173 if (bufix <= bc) { 174 tree_cache->len = bufix; 175 return 1; 176 } 177 178 /* 179 * If we can't allocate more memory, return with what we 180 * have (maybe nothing). 181 */ 182 if (!(bp = (unsigned char *)dmalloc(bufix, "tree_evaluate"))) 183 return 0; 184 185 /* Record the change in conditions... */ 186 bc = bufix; 187 bufix = 0; 188 189 /* 190 * Note that the size of the result shouldn't change on the 191 * second call to tree_evaluate_recurse, since we haven't 192 * changed the ``current'' time. 193 */ 194 tree_evaluate_recurse(&bufix, &bp, &bc, tree_cache->tree); 195 196 /* 197 * Free the old buffer if needed, then store the new buffer 198 * location and size and return. 199 */ 200 if (tree_cache->value) 201 dfree(tree_cache->value, "tree_evaluate"); 202 tree_cache->value = bp; 203 tree_cache->len = bufix; 204 tree_cache->buf_size = bc; 205 return 1; 206 } 207 208 static time_t 209 tree_evaluate_recurse(int *bufix, unsigned char **bufp, 210 int *bufcount, struct tree *tree) 211 { 212 int limit; 213 time_t t1, t2; 214 215 switch (tree->op) { 216 case TREE_CONCAT: 217 t1 = tree_evaluate_recurse(bufix, bufp, bufcount, 218 tree->data.concat.left); 219 t2 = tree_evaluate_recurse(bufix, bufp, bufcount, 220 tree->data.concat.right); 221 if (t1 > t2) 222 return t2; 223 return t1; 224 225 case TREE_CONST: 226 do_data_copy(bufix, bufp, bufcount, tree->data.const_val.data, 227 tree->data.const_val.len); 228 t1 = MAX_TIME; 229 return t1; 230 231 case TREE_LIMIT: 232 limit = *bufix + tree->data.limit.limit; 233 t1 = tree_evaluate_recurse(bufix, bufp, bufcount, 234 tree->data.limit.tree); 235 *bufix = limit; 236 return t1; 237 238 default: 239 warning("Bad node id in tree: %d.", tree->op); 240 t1 = MAX_TIME; 241 return t1; 242 } 243 } 244 245 static void 246 do_data_copy(int *bufix, unsigned char **bufp, int *bufcount, 247 unsigned char *data, int len) 248 { 249 int space = *bufcount - *bufix; 250 251 /* If there's more space than we need, use only what we need. */ 252 if (space > len) 253 space = len; 254 255 /* 256 * Copy as much data as will fit, then increment the buffer index 257 * by the amount we actually had to copy, which could be more. 258 */ 259 if (space > 0) 260 memcpy(*bufp + *bufix, data, space); 261 *bufix += len; 262 } 263