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