1 /* $NetBSD: prop_number.c,v 1.22 2009/03/15 22:29:11 cegger Exp $ */
4 * Copyright (c) 2006 The NetBSD Foundation, Inc.
7 * This code is derived from software contributed to The NetBSD Foundation
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
32 #include <libprop/prop_number.h>
33 #include "prop_object_impl.h"
34 #include "prop_rb_impl.h"
37 #include <sys/systm.h>
38 #define strtoll strtoq
39 #define strtoull strtouq
40 #define sprintf ksprintf
41 #elif defined(_STANDALONE)
42 #include <sys/param.h>
43 #include <lib/libkern/libkern.h>
50 struct _prop_object pn_obj;
51 struct rb_node pn_link;
52 struct _prop_number_value {
55 uint64_t pnu_unsigned;
57 #define pnv_signed pnv_un.pnu_signed
58 #define pnv_unsigned pnv_un.pnu_unsigned
59 unsigned int pnv_is_unsigned :1,
64 #define RBNODE_TO_PN(n) \
65 ((struct _prop_number *) \
66 ((uintptr_t)n - offsetof(struct _prop_number, pn_link)))
68 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr")
70 static _prop_object_free_rv_t
71 _prop_number_free(prop_stack_t, prop_object_t *);
72 static bool _prop_number_externalize(
73 struct _prop_object_externalize_context *,
75 static _prop_object_equals_rv_t
76 _prop_number_equals(prop_object_t, prop_object_t,
78 prop_object_t *, prop_object_t *);
80 static void _prop_number_lock(void);
81 static void _prop_number_unlock(void);
83 static const struct _prop_object_type _prop_object_type_number = {
84 .pot_type = PROP_TYPE_NUMBER,
85 .pot_free = _prop_number_free,
86 .pot_extern = _prop_number_externalize,
87 .pot_equals = _prop_number_equals,
88 .pot_lock = _prop_number_lock,
89 .pot_unlock = _prop_number_unlock,
92 #define prop_object_is_number(x) \
93 ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number)
96 * Number objects are immutable, and we are likely to have many number
97 * objects that have the same value. So, to save memory, we unique'ify
98 * numbers so we only have one copy of each.
102 _prop_number_compare_values(const struct _prop_number_value *pnv1,
103 const struct _prop_number_value *pnv2)
106 /* Signed numbers are sorted before unsigned numbers. */
108 if (pnv1->pnv_is_unsigned) {
109 if (! pnv2->pnv_is_unsigned)
111 if (pnv1->pnv_unsigned < pnv2->pnv_unsigned)
113 if (pnv1->pnv_unsigned > pnv2->pnv_unsigned)
118 if (pnv2->pnv_is_unsigned)
120 if (pnv1->pnv_signed < pnv2->pnv_signed)
122 if (pnv1->pnv_signed > pnv2->pnv_signed)
128 _prop_number_rb_compare_nodes(const struct rb_node *n1,
129 const struct rb_node *n2)
131 const prop_number_t pn1 = RBNODE_TO_PN(n1);
132 const prop_number_t pn2 = RBNODE_TO_PN(n2);
134 return (_prop_number_compare_values(&pn1->pn_value, &pn2->pn_value));
138 _prop_number_rb_compare_key(const struct rb_node *n,
141 const prop_number_t pn = RBNODE_TO_PN(n);
142 const struct _prop_number_value *pnv = v;
144 return (_prop_number_compare_values(&pn->pn_value, pnv));
147 static const struct rb_tree_ops _prop_number_rb_tree_ops = {
148 .rbto_compare_nodes = _prop_number_rb_compare_nodes,
149 .rbto_compare_key = _prop_number_rb_compare_key,
152 static struct rb_tree _prop_number_tree;
153 _PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex)
156 static _prop_object_free_rv_t
157 _prop_number_free(prop_stack_t stack, prop_object_t *obj)
159 prop_number_t pn = *obj;
161 _prop_rb_tree_remove_node(&_prop_number_tree, &pn->pn_link);
163 _PROP_POOL_PUT(_prop_number_pool, pn);
165 return (_PROP_OBJECT_FREE_DONE);
168 _PROP_ONCE_DECL(_prop_number_init_once)
171 _prop_number_init(void)
174 _PROP_MUTEX_INIT(_prop_number_tree_mutex);
175 _prop_rb_tree_init(&_prop_number_tree,
176 &_prop_number_rb_tree_ops);
181 _prop_number_lock(void)
183 /* XXX: init necessary? */
184 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
185 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
189 _prop_number_unlock(void)
191 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
195 _prop_number_externalize(struct _prop_object_externalize_context *ctx,
198 prop_number_t pn = v;
202 * For unsigned numbers, we output in hex. For signed numbers,
203 * we output in decimal.
205 if (pn->pn_value.pnv_is_unsigned)
206 sprintf(tmpstr, "0x%" PRIx64, pn->pn_value.pnv_unsigned);
208 sprintf(tmpstr, "%" PRIi64, pn->pn_value.pnv_signed);
210 if (_prop_object_externalize_start_tag(ctx, "integer") == false ||
211 _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
212 _prop_object_externalize_end_tag(ctx, "integer") == false)
219 static _prop_object_equals_rv_t
220 _prop_number_equals(prop_object_t v1, prop_object_t v2,
221 void **stored_pointer1, void **stored_pointer2,
222 prop_object_t *next_obj1, prop_object_t *next_obj2)
224 prop_number_t num1 = v1;
225 prop_number_t num2 = v2;
228 * There is only ever one copy of a number object at any given
229 * time, so we can reduce this to a simple pointer equality check
230 * in the common case.
233 return (_PROP_OBJECT_EQUALS_TRUE);
236 * If the numbers are the same signed-ness, then we know they
237 * cannot be equal because they would have had pointer equality.
239 if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned)
240 return (_PROP_OBJECT_EQUALS_FALSE);
243 * We now have one signed value and one unsigned value. We can
245 * - The unsigned value is not larger than the signed value
247 * - The signed value is not smaller than the unsigned value
250 if (num1->pn_value.pnv_is_unsigned) {
252 * num1 is unsigned and num2 is signed.
254 if (num1->pn_value.pnv_unsigned > INT64_MAX)
255 return (_PROP_OBJECT_EQUALS_FALSE);
256 if (num2->pn_value.pnv_signed < 0)
257 return (_PROP_OBJECT_EQUALS_FALSE);
260 * num1 is signed and num2 is unsigned.
262 if (num1->pn_value.pnv_signed < 0)
263 return (_PROP_OBJECT_EQUALS_FALSE);
264 if (num2->pn_value.pnv_unsigned > INT64_MAX)
265 return (_PROP_OBJECT_EQUALS_FALSE);
268 if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed)
269 return _PROP_OBJECT_EQUALS_TRUE;
271 return _PROP_OBJECT_EQUALS_FALSE;
275 _prop_number_alloc(const struct _prop_number_value *pnv)
277 prop_number_t opn, pn;
281 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
284 * Check to see if this already exists in the tree. If it does,
285 * we just retain it and return it.
287 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
288 n = _prop_rb_tree_find(&_prop_number_tree, pnv);
290 opn = RBNODE_TO_PN(n);
291 prop_object_retain(opn);
292 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
295 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
298 * Not in the tree. Create it now.
301 pn = _PROP_POOL_GET(_prop_number_pool);
305 _prop_object_init(&pn->pn_obj, &_prop_object_type_number);
310 * We dropped the mutex when we allocated the new object, so
311 * we have to check again if it is in the tree.
313 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
314 n = _prop_rb_tree_find(&_prop_number_tree, pnv);
316 opn = RBNODE_TO_PN(n);
317 prop_object_retain(opn);
318 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
319 _PROP_POOL_PUT(_prop_number_pool, pn);
322 rv = _prop_rb_tree_insert_node(&_prop_number_tree, &pn->pn_link);
323 _PROP_ASSERT(rv == true);
324 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
329 * prop_number_create_integer --
330 * Create a prop_number_t and initialize it with the
331 * provided integer value.
334 prop_number_create_integer(int64_t val)
336 struct _prop_number_value pnv;
338 memset(&pnv, 0, sizeof(pnv));
339 pnv.pnv_signed = val;
340 pnv.pnv_is_unsigned = false;
342 return (_prop_number_alloc(&pnv));
346 * prop_number_create_unsigned_integer --
347 * Create a prop_number_t and initialize it with the
348 * provided unsigned integer value.
351 prop_number_create_unsigned_integer(uint64_t val)
353 struct _prop_number_value pnv;
355 memset(&pnv, 0, sizeof(pnv));
356 pnv.pnv_unsigned = val;
357 pnv.pnv_is_unsigned = true;
359 return (_prop_number_alloc(&pnv));
363 * prop_number_copy --
364 * Copy a prop_number_t.
367 prop_number_copy(prop_number_t opn)
370 if (! prop_object_is_number(opn))
374 * Because we only ever allocate one object for any given
375 * value, this can be reduced to a simple retain operation.
377 prop_object_retain(opn);
382 * prop_number_unsigned --
383 * Returns true if the prop_number_t has an unsigned value.
386 prop_number_unsigned(prop_number_t pn)
389 return (pn->pn_value.pnv_is_unsigned);
393 * prop_number_size --
394 * Return the size, in bits, required to hold the value of
395 * the specified number.
398 prop_number_size(prop_number_t pn)
400 struct _prop_number_value *pnv;
402 if (! prop_object_is_number(pn))
407 if (pnv->pnv_is_unsigned) {
408 if (pnv->pnv_unsigned > UINT32_MAX)
410 if (pnv->pnv_unsigned > UINT16_MAX)
412 if (pnv->pnv_unsigned > UINT8_MAX)
417 if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
419 if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
421 if (pnv->pnv_signed > INT8_MAX || pnv->pnv_signed < INT8_MIN)
427 * prop_number_integer_value --
428 * Get the integer value of a prop_number_t.
431 prop_number_integer_value(prop_number_t pn)
435 * XXX Impossible to distinguish between "not a prop_number_t"
436 * XXX and "prop_number_t has a value of 0".
438 if (! prop_object_is_number(pn))
441 return (pn->pn_value.pnv_signed);
445 * prop_number_unsigned_integer_value --
446 * Get the unsigned integer value of a prop_number_t.
449 prop_number_unsigned_integer_value(prop_number_t pn)
453 * XXX Impossible to distinguish between "not a prop_number_t"
454 * XXX and "prop_number_t has a value of 0".
456 if (! prop_object_is_number(pn))
459 return (pn->pn_value.pnv_unsigned);
463 * prop_number_equals --
464 * Return true if two numbers are equivalent.
467 prop_number_equals(prop_number_t num1, prop_number_t num2)
469 if (!prop_object_is_number(num1) || !prop_object_is_number(num2))
472 return (prop_object_equals(num1, num2));
476 * prop_number_equals_integer --
477 * Return true if the number is equivalent to the specified integer.
480 prop_number_equals_integer(prop_number_t pn, int64_t val)
483 if (! prop_object_is_number(pn))
486 if (pn->pn_value.pnv_is_unsigned &&
487 (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
490 return (pn->pn_value.pnv_signed == val);
494 * prop_number_equals_unsigned_integer --
495 * Return true if the number is equivalent to the specified
499 prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
502 if (! prop_object_is_number(pn))
505 if (! pn->pn_value.pnv_is_unsigned &&
506 (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
509 return (pn->pn_value.pnv_unsigned == val);
513 _prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx,
514 struct _prop_number_value *pnv)
518 _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) ==
524 pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0);
525 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
526 if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE)
529 pnv->pnv_is_unsigned = true;
536 _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
537 struct _prop_number_value *pnv)
541 _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t));
546 pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0);
547 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
548 if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
552 pnv->pnv_is_unsigned = false;
559 * _prop_number_internalize --
560 * Parse a <number>...</number> and return the object created from
561 * the external representation.
565 _prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
566 struct _prop_object_internalize_context *ctx)
568 struct _prop_number_value pnv;
570 memset(&pnv, 0, sizeof(pnv));
572 /* No attributes, no empty elements. */
573 if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element)
577 * If the first character is '-', then we treat as signed.
578 * If the first two characters are "0x" (i.e. the number is
579 * in hex), then we treat as unsigned. Otherwise, we try
580 * signed first, and if that fails (presumably due to ERANGE),
581 * then we switch to unsigned.
583 if (ctx->poic_cp[0] == '-') {
584 if (_prop_number_internalize_signed(ctx, &pnv) == false)
586 } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') {
587 if (_prop_number_internalize_unsigned(ctx, &pnv) == false)
590 if (_prop_number_internalize_signed(ctx, &pnv) == false &&
591 _prop_number_internalize_unsigned(ctx, &pnv) == false)
595 if (_prop_object_internalize_find_tag(ctx, "integer",
596 _PROP_TAG_TYPE_END) == false)
599 *obj = _prop_number_alloc(&pnv);