1 /* $NetBSD: prop_number.c,v 1.22 2009/03/15 22:29:11 cegger 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 *
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.
30 */
31
32 #include <libprop/prop_number.h>
33 #include "prop_object_impl.h"
34 #include "prop_rb_impl.h"
35
36 #if defined(_KERNEL)
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>
44 #else
45 #include <errno.h>
46 #include <stdlib.h>
47 #endif
48
49 struct _prop_number {
50 struct _prop_object pn_obj;
51 struct rb_node pn_link;
52 struct _prop_number_value {
53 union {
54 int64_t pnu_signed;
55 uint64_t pnu_unsigned;
56 } pnv_un;
57 #define pnv_signed pnv_un.pnu_signed
58 #define pnv_unsigned pnv_un.pnu_unsigned
59 unsigned int pnv_is_unsigned :1,
60 :31;
61 } pn_value;
62 };
63
64 _PROP_POOL_INIT(_prop_number_pool, sizeof(struct _prop_number), "propnmbr");
65
66 static _prop_object_free_rv_t
67 _prop_number_free(prop_stack_t, prop_object_t *);
68 static bool _prop_number_externalize(
69 struct _prop_object_externalize_context *,
70 void *);
71 static _prop_object_equals_rv_t
72 _prop_number_equals(prop_object_t, prop_object_t,
73 void **, void **,
74 prop_object_t *, prop_object_t *);
75
76 static void _prop_number_lock(void);
77 static void _prop_number_unlock(void);
78
79 static const struct _prop_object_type _prop_object_type_number = {
80 .pot_type = PROP_TYPE_NUMBER,
81 .pot_free = _prop_number_free,
82 .pot_extern = _prop_number_externalize,
83 .pot_equals = _prop_number_equals,
84 .pot_lock = _prop_number_lock,
85 .pot_unlock = _prop_number_unlock,
86 };
87
88 #define prop_object_is_number(x) \
89 ((x) != NULL && (x)->pn_obj.po_type == &_prop_object_type_number)
90
91 /*
92 * Number objects are immutable, and we are likely to have many number
93 * objects that have the same value. So, to save memory, we unique'ify
94 * numbers so we only have one copy of each.
95 */
96
97 static int
_prop_number_compare_values(const struct _prop_number_value * pnv1,const struct _prop_number_value * pnv2)98 _prop_number_compare_values(const struct _prop_number_value *pnv1,
99 const struct _prop_number_value *pnv2)
100 {
101
102 /* Signed numbers are sorted before unsigned numbers. */
103
104 if (pnv1->pnv_is_unsigned) {
105 if (! pnv2->pnv_is_unsigned)
106 return (1);
107 if (pnv1->pnv_unsigned < pnv2->pnv_unsigned)
108 return (-1);
109 if (pnv1->pnv_unsigned > pnv2->pnv_unsigned)
110 return (1);
111 return (0);
112 }
113
114 if (pnv2->pnv_is_unsigned)
115 return (-1);
116 if (pnv1->pnv_signed < pnv2->pnv_signed)
117 return (-1);
118 if (pnv1->pnv_signed > pnv2->pnv_signed)
119 return (1);
120 return (0);
121 }
122
123 static int
124 /*ARGSUSED*/
_prop_number_rb_compare_nodes(void * ctx __unused,const void * n1,const void * n2)125 _prop_number_rb_compare_nodes(void *ctx __unused,
126 const void *n1, const void *n2)
127 {
128 const struct _prop_number *pn1 = n1;
129 const struct _prop_number *pn2 = n2;
130
131 return _prop_number_compare_values(&pn1->pn_value, &pn2->pn_value);
132 }
133
134 static int
135 /*ARGSUSED*/
_prop_number_rb_compare_key(void * ctx __unused,const void * n,const void * v)136 _prop_number_rb_compare_key(void *ctx __unused, const void *n, const void *v)
137 {
138 const struct _prop_number *pn = n;
139 const struct _prop_number_value *pnv = v;
140
141 return _prop_number_compare_values(&pn->pn_value, pnv);
142 }
143
144 static const rb_tree_ops_t _prop_number_rb_tree_ops = {
145 .rbto_compare_nodes = _prop_number_rb_compare_nodes,
146 .rbto_compare_key = _prop_number_rb_compare_key,
147 .rbto_node_offset = offsetof(struct _prop_number, pn_link),
148 .rbto_context = NULL
149 };
150
151 static struct rb_tree _prop_number_tree;
_PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex)152 _PROP_MUTEX_DECL_STATIC(_prop_number_tree_mutex)
153
154 /* ARGSUSED */
155 static _prop_object_free_rv_t
156 _prop_number_free(prop_stack_t stack, prop_object_t *obj)
157 {
158 prop_number_t pn = *obj;
159
160 _prop_rb_tree_remove_node(&_prop_number_tree, pn);
161
162 _PROP_POOL_PUT(_prop_number_pool, pn);
163
164 return (_PROP_OBJECT_FREE_DONE);
165 }
166
_PROP_ONCE_DECL(_prop_number_init_once)167 _PROP_ONCE_DECL(_prop_number_init_once)
168
169 static int
170 _prop_number_init(void)
171 {
172
173 _PROP_MUTEX_INIT(_prop_number_tree_mutex);
174 _prop_rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
175 return 0;
176 }
177
178 static void
_prop_number_lock(void)179 _prop_number_lock(void)
180 {
181 /* XXX: init necessary? */
182 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
183 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
184 }
185
186 static void
_prop_number_unlock(void)187 _prop_number_unlock(void)
188 {
189 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
190 }
191
192 static bool
_prop_number_externalize(struct _prop_object_externalize_context * ctx,void * v)193 _prop_number_externalize(struct _prop_object_externalize_context *ctx,
194 void *v)
195 {
196 prop_number_t pn = v;
197 char tmpstr[32];
198
199 /*
200 * For unsigned numbers, we output in hex. For signed numbers,
201 * we output in decimal.
202 */
203 if (pn->pn_value.pnv_is_unsigned)
204 sprintf(tmpstr, "0x%" PRIx64, pn->pn_value.pnv_unsigned);
205 else
206 sprintf(tmpstr, "%" PRIi64, pn->pn_value.pnv_signed);
207
208 if (_prop_object_externalize_start_tag(ctx, "integer") == false ||
209 _prop_object_externalize_append_cstring(ctx, tmpstr) == false ||
210 _prop_object_externalize_end_tag(ctx, "integer") == false)
211 return (false);
212
213 return (true);
214 }
215
216 /* ARGSUSED */
217 static _prop_object_equals_rv_t
_prop_number_equals(prop_object_t v1,prop_object_t v2,void ** stored_pointer1,void ** stored_pointer2,prop_object_t * next_obj1,prop_object_t * next_obj2)218 _prop_number_equals(prop_object_t v1, prop_object_t v2,
219 void **stored_pointer1, void **stored_pointer2,
220 prop_object_t *next_obj1, prop_object_t *next_obj2)
221 {
222 prop_number_t num1 = v1;
223 prop_number_t num2 = v2;
224
225 /*
226 * There is only ever one copy of a number object at any given
227 * time, so we can reduce this to a simple pointer equality check
228 * in the common case.
229 */
230 if (num1 == num2)
231 return (_PROP_OBJECT_EQUALS_TRUE);
232
233 /*
234 * If the numbers are the same signed-ness, then we know they
235 * cannot be equal because they would have had pointer equality.
236 */
237 if (num1->pn_value.pnv_is_unsigned == num2->pn_value.pnv_is_unsigned)
238 return (_PROP_OBJECT_EQUALS_FALSE);
239
240 /*
241 * We now have one signed value and one unsigned value. We can
242 * compare them iff:
243 * - The unsigned value is not larger than the signed value
244 * can represent.
245 * - The signed value is not smaller than the unsigned value
246 * can represent.
247 */
248 if (num1->pn_value.pnv_is_unsigned) {
249 /*
250 * num1 is unsigned and num2 is signed.
251 */
252 if (num1->pn_value.pnv_unsigned > INT64_MAX)
253 return (_PROP_OBJECT_EQUALS_FALSE);
254 if (num2->pn_value.pnv_signed < 0)
255 return (_PROP_OBJECT_EQUALS_FALSE);
256 } else {
257 /*
258 * num1 is signed and num2 is unsigned.
259 */
260 if (num1->pn_value.pnv_signed < 0)
261 return (_PROP_OBJECT_EQUALS_FALSE);
262 if (num2->pn_value.pnv_unsigned > INT64_MAX)
263 return (_PROP_OBJECT_EQUALS_FALSE);
264 }
265
266 if (num1->pn_value.pnv_signed == num2->pn_value.pnv_signed)
267 return _PROP_OBJECT_EQUALS_TRUE;
268 else
269 return _PROP_OBJECT_EQUALS_FALSE;
270 }
271
272 static prop_number_t
_prop_number_alloc(const struct _prop_number_value * pnv)273 _prop_number_alloc(const struct _prop_number_value *pnv)
274 {
275 prop_number_t opn, pn, rpn;
276
277 _PROP_ONCE_RUN(_prop_number_init_once, _prop_number_init);
278
279 /*
280 * Check to see if this already exists in the tree. If it does,
281 * we just retain it and return it.
282 */
283 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
284 opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
285 if (opn != NULL) {
286 prop_object_retain(opn);
287 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
288 return (opn);
289 }
290 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
291
292 /*
293 * Not in the tree. Create it now.
294 */
295
296 pn = _PROP_POOL_GET(_prop_number_pool);
297 if (pn == NULL)
298 return (NULL);
299
300 _prop_object_init(&pn->pn_obj, &_prop_object_type_number);
301
302 pn->pn_value = *pnv;
303
304 /*
305 * We dropped the mutex when we allocated the new object, so
306 * we have to check again if it is in the tree.
307 */
308 _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
309 opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
310 if (opn != NULL) {
311 prop_object_retain(opn);
312 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
313 _PROP_POOL_PUT(_prop_number_pool, pn);
314 return (opn);
315 }
316 rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn);
317 _PROP_ASSERT(rpn == pn);
318 _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
319 return (pn);
320 }
321
322 /*
323 * prop_number_create_integer --
324 * Create a prop_number_t and initialize it with the
325 * provided integer value.
326 */
327 prop_number_t
prop_number_create_integer(int64_t val)328 prop_number_create_integer(int64_t val)
329 {
330 struct _prop_number_value pnv;
331
332 memset(&pnv, 0, sizeof(pnv));
333 pnv.pnv_signed = val;
334 pnv.pnv_is_unsigned = false;
335
336 return (_prop_number_alloc(&pnv));
337 }
338
339 /*
340 * prop_number_create_unsigned_integer --
341 * Create a prop_number_t and initialize it with the
342 * provided unsigned integer value.
343 */
344 prop_number_t
prop_number_create_unsigned_integer(uint64_t val)345 prop_number_create_unsigned_integer(uint64_t val)
346 {
347 struct _prop_number_value pnv;
348
349 memset(&pnv, 0, sizeof(pnv));
350 pnv.pnv_unsigned = val;
351 pnv.pnv_is_unsigned = true;
352
353 return (_prop_number_alloc(&pnv));
354 }
355
356 /*
357 * prop_number_copy --
358 * Copy a prop_number_t.
359 */
360 prop_number_t
prop_number_copy(prop_number_t opn)361 prop_number_copy(prop_number_t opn)
362 {
363
364 if (! prop_object_is_number(opn))
365 return (NULL);
366
367 /*
368 * Because we only ever allocate one object for any given
369 * value, this can be reduced to a simple retain operation.
370 */
371 prop_object_retain(opn);
372 return (opn);
373 }
374
375 /*
376 * prop_number_unsigned --
377 * Returns true if the prop_number_t has an unsigned value.
378 */
379 bool
prop_number_unsigned(prop_number_t pn)380 prop_number_unsigned(prop_number_t pn)
381 {
382
383 return (pn->pn_value.pnv_is_unsigned);
384 }
385
386 /*
387 * prop_number_size --
388 * Return the size, in bits, required to hold the value of
389 * the specified number.
390 */
391 int
prop_number_size(prop_number_t pn)392 prop_number_size(prop_number_t pn)
393 {
394 struct _prop_number_value *pnv;
395
396 if (! prop_object_is_number(pn))
397 return (0);
398
399 pnv = &pn->pn_value;
400
401 if (pnv->pnv_is_unsigned) {
402 if (pnv->pnv_unsigned > UINT32_MAX)
403 return (64);
404 if (pnv->pnv_unsigned > UINT16_MAX)
405 return (32);
406 if (pnv->pnv_unsigned > UINT8_MAX)
407 return (16);
408 return (8);
409 }
410
411 if (pnv->pnv_signed > INT32_MAX || pnv->pnv_signed < INT32_MIN)
412 return (64);
413 if (pnv->pnv_signed > INT16_MAX || pnv->pnv_signed < INT16_MIN)
414 return (32);
415 if (pnv->pnv_signed > INT8_MAX || pnv->pnv_signed < INT8_MIN)
416 return (16);
417 return (8);
418 }
419
420 /*
421 * prop_number_integer_value --
422 * Get the integer value of a prop_number_t.
423 */
424 int64_t
prop_number_integer_value(prop_number_t pn)425 prop_number_integer_value(prop_number_t pn)
426 {
427
428 /*
429 * XXX Impossible to distinguish between "not a prop_number_t"
430 * XXX and "prop_number_t has a value of 0".
431 */
432 if (! prop_object_is_number(pn))
433 return (0);
434
435 return (pn->pn_value.pnv_signed);
436 }
437
438 /*
439 * prop_number_unsigned_integer_value --
440 * Get the unsigned integer value of a prop_number_t.
441 */
442 uint64_t
prop_number_unsigned_integer_value(prop_number_t pn)443 prop_number_unsigned_integer_value(prop_number_t pn)
444 {
445
446 /*
447 * XXX Impossible to distinguish between "not a prop_number_t"
448 * XXX and "prop_number_t has a value of 0".
449 */
450 if (! prop_object_is_number(pn))
451 return (0);
452
453 return (pn->pn_value.pnv_unsigned);
454 }
455
456 /*
457 * prop_number_equals --
458 * Return true if two numbers are equivalent.
459 */
460 bool
prop_number_equals(prop_number_t num1,prop_number_t num2)461 prop_number_equals(prop_number_t num1, prop_number_t num2)
462 {
463 if (!prop_object_is_number(num1) || !prop_object_is_number(num2))
464 return (false);
465
466 return (prop_object_equals(num1, num2));
467 }
468
469 /*
470 * prop_number_equals_integer --
471 * Return true if the number is equivalent to the specified integer.
472 */
473 bool
prop_number_equals_integer(prop_number_t pn,int64_t val)474 prop_number_equals_integer(prop_number_t pn, int64_t val)
475 {
476
477 if (! prop_object_is_number(pn))
478 return (false);
479
480 if (pn->pn_value.pnv_is_unsigned &&
481 (pn->pn_value.pnv_unsigned > INT64_MAX || val < 0))
482 return (false);
483
484 return (pn->pn_value.pnv_signed == val);
485 }
486
487 /*
488 * prop_number_equals_unsigned_integer --
489 * Return true if the number is equivalent to the specified
490 * unsigned integer.
491 */
492 bool
prop_number_equals_unsigned_integer(prop_number_t pn,uint64_t val)493 prop_number_equals_unsigned_integer(prop_number_t pn, uint64_t val)
494 {
495
496 if (! prop_object_is_number(pn))
497 return (false);
498
499 if (! pn->pn_value.pnv_is_unsigned &&
500 (pn->pn_value.pnv_signed < 0 || val > INT64_MAX))
501 return (false);
502
503 return (pn->pn_value.pnv_unsigned == val);
504 }
505
506 static bool
_prop_number_internalize_unsigned(struct _prop_object_internalize_context * ctx,struct _prop_number_value * pnv)507 _prop_number_internalize_unsigned(struct _prop_object_internalize_context *ctx,
508 struct _prop_number_value *pnv)
509 {
510 char *cp;
511
512 _PROP_ASSERT(/*CONSTCOND*/sizeof(unsigned long long) ==
513 sizeof(uint64_t));
514
515 #ifndef _KERNEL
516 errno = 0;
517 #endif
518 pnv->pnv_unsigned = (uint64_t) strtoull(ctx->poic_cp, &cp, 0);
519 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
520 if (pnv->pnv_unsigned == UINT64_MAX && errno == ERANGE)
521 return (false);
522 #endif
523 pnv->pnv_is_unsigned = true;
524 ctx->poic_cp = cp;
525
526 return (true);
527 }
528
529 static bool
_prop_number_internalize_signed(struct _prop_object_internalize_context * ctx,struct _prop_number_value * pnv)530 _prop_number_internalize_signed(struct _prop_object_internalize_context *ctx,
531 struct _prop_number_value *pnv)
532 {
533 char *cp;
534
535 _PROP_ASSERT(/*CONSTCOND*/sizeof(long long) == sizeof(int64_t));
536
537 #ifndef _KERNEL
538 errno = 0;
539 #endif
540 pnv->pnv_signed = (int64_t) strtoll(ctx->poic_cp, &cp, 0);
541 #ifndef _KERNEL /* XXX can't check for ERANGE in the kernel */
542 if ((pnv->pnv_signed == INT64_MAX || pnv->pnv_signed == INT64_MIN) &&
543 errno == ERANGE)
544 return (false);
545 #endif
546 pnv->pnv_is_unsigned = false;
547 ctx->poic_cp = cp;
548
549 return (true);
550 }
551
552 /*
553 * _prop_number_internalize --
554 * Parse a <number>...</number> and return the object created from
555 * the external representation.
556 */
557 /* ARGSUSED */
558 bool
_prop_number_internalize(prop_stack_t stack,prop_object_t * obj,struct _prop_object_internalize_context * ctx)559 _prop_number_internalize(prop_stack_t stack, prop_object_t *obj,
560 struct _prop_object_internalize_context *ctx)
561 {
562 struct _prop_number_value pnv;
563
564 memset(&pnv, 0, sizeof(pnv));
565
566 /* No attributes, no empty elements. */
567 if (ctx->poic_tagattr != NULL || ctx->poic_is_empty_element)
568 return (true);
569
570 /*
571 * If the first character is '-', then we treat as signed.
572 * If the first two characters are "0x" (i.e. the number is
573 * in hex), then we treat as unsigned. Otherwise, we try
574 * signed first, and if that fails (presumably due to ERANGE),
575 * then we switch to unsigned.
576 */
577 if (ctx->poic_cp[0] == '-') {
578 if (_prop_number_internalize_signed(ctx, &pnv) == false)
579 return (true);
580 } else if (ctx->poic_cp[0] == '0' && ctx->poic_cp[1] == 'x') {
581 if (_prop_number_internalize_unsigned(ctx, &pnv) == false)
582 return (true);
583 } else {
584 if (_prop_number_internalize_signed(ctx, &pnv) == false &&
585 _prop_number_internalize_unsigned(ctx, &pnv) == false)
586 return (true);
587 }
588
589 if (_prop_object_internalize_find_tag(ctx, "integer",
590 _PROP_TAG_TYPE_END) == false)
591 return (true);
592
593 *obj = _prop_number_alloc(&pnv);
594 return (true);
595 }
596