1 /* $NetBSD: prop_number.c,v 1.7 2006/10/03 15:45:04 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c) 2006 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 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. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the NetBSD 21 * Foundation, Inc. and its contributors. 22 * 4. Neither the name of The NetBSD Foundation nor the names of its 23 * contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 27 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 28 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 29 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 30 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 31 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 32 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 33 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 34 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 35 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 */ 38 39 #include <prop/prop_number.h> 40 #include "prop_object_impl.h" 41 #include "prop_rb_impl.h" 42 43 #if defined(_KERNEL) 44 #include <sys/systm.h> 45 #elif defined(_STANDALONE) 46 #include <sys/param.h> 47 #include <lib/libkern/libkern.h> 48 #else 49 #include <errno.h> 50 #include <stdlib.h> 51 #endif 52 53 struct _prop_number { 54 struct _prop_object pn_obj; 55 struct rb_node pn_link; 56 uint64_t pn_number; 57 }; 58 59 #define RBNODE_TO_PN(n) \ 60 ((struct _prop_number *) \ 61 ((uintptr_t)n - offsetof(struct _prop_number, pn_link))) 62 63 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr") 64 65 static void _prop_number_free(void *); 66 static boolean_t _prop_number_externalize( 67 struct _prop_object_externalize_context *, 68 void *); 69 static boolean_t _prop_number_equals(void *, void *); 70 71 static const struct _prop_object_type _prop_object_type_number = { 72 .pot_type = PROP_TYPE_NUMBER, 73 .pot_free = _prop_number_free, 74 .pot_extern = _prop_number_externalize, 75 .pot_equals = _prop_number_equals, 76 }; 77 78 #define prop_object_is_number(x) \ 79 ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number) 80 81 /* 82 * Number objects are immutable, and we are likely to have many number 83 * objects that have the same value. So, to save memory, we unique'ify 84 * numbers so we only have one copy of each. 85 */ 86 87 static int 88 _prop_number_rb_compare_nodes(const struct rb_node *n1, 89 const struct rb_node *n2) 90 { 91 const prop_number_t pn1 = RBNODE_TO_PN(n1); 92 const prop_number_t pn2 = RBNODE_TO_PN(n2); 93 94 if (pn1->pn_number < pn2->pn_number) 95 return (-1); 96 if (pn1->pn_number > pn2->pn_number) 97 return (1); 98 return (0); 99 } 100 101 static int 102 _prop_number_rb_compare_key(const struct rb_node *n, 103 const void *v) 104 { 105 const prop_number_t pn = RBNODE_TO_PN(n); 106 const uint64_t *valp = v; 107 108 if (pn->pn_number < *valp) 109 return (-1); 110 if (pn->pn_number > *valp) 111 return (1); 112 return (0); 113 } 114 115 static const struct rb_tree_ops _prop_number_rb_tree_ops = { 116 .rbto_compare_nodes = _prop_number_rb_compare_nodes, 117 .rbto_compare_key = _prop_number_rb_compare_key, 118 }; 119 120 static struct rb_tree _prop_number_tree; 121 static boolean_t _prop_number_tree_initialized; 122 123 _PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex) 124 125 static void 126 _prop_number_free(void *v) 127 { 128 prop_number_t pn = v; 129 130 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 131 _prop_rb_tree_remove_node(&_prop_number_tree, &pn->pn_link); 132 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 133 134 _PROP_POOL_PUT(_prop_number_pool, pn); 135 } 136 137 static boolean_t 138 _prop_number_externalize(struct _prop_object_externalize_context *ctx, 139 void *v) 140 { 141 prop_number_t pn = v; 142 char tmpstr[32]; 143 144 sprintf(tmpstr, "0x%" PRIx64, pn->pn_number); 145 146 if (_prop_object_externalize_start_tag(ctx, "integer") == FALSE || 147 _prop_object_externalize_append_cstring(ctx, tmpstr) == FALSE || 148 _prop_object_externalize_end_tag(ctx, "integer") == FALSE) 149 return (FALSE); 150 151 return (TRUE); 152 } 153 154 static boolean_t 155 _prop_number_equals(void *v1, void *v2) 156 { 157 prop_number_t num1 = v1; 158 prop_number_t num2 = v2; 159 160 if (! (prop_object_is_number(num1) && 161 prop_object_is_number(num2))) 162 return (FALSE); 163 164 /* 165 * There is only ever one copy of a number object at any given 166 * time, so we can reduce this to a simple pointer equality check. 167 */ 168 return (num1 == num2); 169 } 170 171 static prop_number_t 172 _prop_number_alloc(uint64_t val) 173 { 174 prop_number_t opn, pn; 175 struct rb_node *n; 176 177 /* 178 * Check to see if this already exists in the tree. If it does, 179 * we just retain it and return it. 180 */ 181 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 182 if (! _prop_number_tree_initialized) { 183 _prop_rb_tree_init(&_prop_number_tree, 184 &_prop_number_rb_tree_ops); 185 _prop_number_tree_initialized = TRUE; 186 } else { 187 n = _prop_rb_tree_find(&_prop_number_tree, &val); 188 if (n != NULL) { 189 opn = RBNODE_TO_PN(n); 190 prop_object_retain(opn); 191 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 192 return (opn); 193 } 194 } 195 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 196 197 /* 198 * Not in the tree. Create it now. 199 */ 200 201 pn = _PROP_POOL_GET(_prop_number_pool); 202 if (pn == NULL) 203 return (NULL); 204 205 _prop_object_init(&pn->pn_obj, &_prop_object_type_number); 206 207 pn->pn_number = val; 208 209 /* 210 * We dropped the mutex when we allocated the new object, so 211 * we have to check again if it is in the tree. 212 */ 213 _PROP_MUTEX_LOCK(_prop_number_tree_mutex); 214 n = _prop_rb_tree_find(&_prop_number_tree, &val); 215 if (n != NULL) { 216 opn = RBNODE_TO_PN(n); 217 prop_object_retain(opn); 218 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 219 _PROP_POOL_PUT(_prop_number_pool, pn); 220 return (opn); 221 } 222 _prop_rb_tree_insert_node(&_prop_number_tree, &pn->pn_link); 223 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex); 224 return (pn); 225 } 226 227 /* 228 * prop_number_create_integer -- 229 * Create a prop_number_t and initialize it with the 230 * provided integer value. 231 */ 232 prop_number_t 233 prop_number_create_integer(uint64_t val) 234 { 235 236 return (_prop_number_alloc(val)); 237 } 238 239 /* 240 * prop_number_copy -- 241 * Copy a prop_number_t. 242 */ 243 prop_number_t 244 prop_number_copy(prop_number_t opn) 245 { 246 247 if (! prop_object_is_number(opn)) 248 return (NULL); 249 250 /* 251 * Because we only ever allocate one object for any given 252 * value, this can be reduced to a simple retain operation. 253 */ 254 prop_object_retain(opn); 255 return (opn); 256 } 257 258 /* 259 * prop_number_size -- 260 * Return the size, in bits, required to hold the value of 261 * the specified number. 262 */ 263 int 264 prop_number_size(prop_number_t pn) 265 { 266 267 if (! prop_object_is_number(pn)) 268 return (0); 269 270 if (pn->pn_number > UINT32_MAX) 271 return (64); 272 if (pn->pn_number > UINT16_MAX) 273 return (32); 274 if (pn->pn_number > UINT8_MAX) 275 return (16); 276 return (8); 277 } 278 279 /* 280 * prop_number_integer_value -- 281 * Get the integer value of a prop_number_t. 282 */ 283 uint64_t 284 prop_number_integer_value(prop_number_t pn) 285 { 286 287 /* 288 * XXX Impossible to distinguish between "not a prop_number_t" 289 * XXX and "prop_number_t has a value of 0". 290 */ 291 if (! prop_object_is_number(pn)) 292 return (0); 293 294 return (pn->pn_number); 295 } 296 297 /* 298 * prop_number_equals -- 299 * Return TRUE if two numbers are equivalent. 300 */ 301 boolean_t 302 prop_number_equals(prop_number_t num1, prop_number_t num2) 303 { 304 305 return (_prop_number_equals(num1, num2)); 306 } 307 308 /* 309 * prop_number_equals_integer -- 310 * Return TRUE if the number is equivalent to the specified integer. 311 */ 312 boolean_t 313 prop_number_equals_integer(prop_number_t pn, uint64_t val) 314 { 315 316 if (! prop_object_is_number(pn)) 317 return (FALSE); 318 319 return (pn->pn_number == val); 320 } 321 322 /* 323 * _prop_number_internalize -- 324 * Parse a <number>...</number> and return the object created from 325 * the external representation. 326 */ 327 prop_object_t 328 _prop_number_internalize(struct _prop_object_internalize_context *ctx) 329 { 330 uint64_t val = 0; 331 char *cp; 332 333 /* No attributes, no empty elements. */ 334 if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element) 335 return (NULL); 336 337 #ifndef _KERNEL 338 errno = 0; 339 #endif 340 val = strtoumax(ctx->poic_cp, &cp, 0); 341 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */ 342 if (val == UINTMAX_MAX && errno == ERANGE) 343 return (NULL); 344 #endif 345 ctx->poic_cp = cp; 346 347 if (_prop_object_internalize_find_tag(ctx, "integer", 348 _PROP_TAG_TYPE_END) == FALSE) 349 return (NULL); 350 351 return (_prop_number_alloc(val)); 352 } 353