1 /* $NetBSD: prop_array.c,v 1.3 2006/05/28 03:53:51 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_array.h> 40 #include "prop_object_impl.h" 41 42 struct _prop_array { 43 struct _prop_object pa_obj; 44 prop_object_t * pa_array; 45 unsigned int pa_capacity; 46 unsigned int pa_count; 47 int pa_flags; 48 49 uint32_t pa_version; 50 }; 51 52 #define PA_F_IMMUTABLE 0x01 /* array is immutable */ 53 54 _PROP_POOL_INIT(_prop_array_pool, sizeof(struct _prop_array), "proparay") 55 _PROP_MALLOC_DEFINE(M_PROP_ARRAY, "prop array", 56 "property array container object") 57 58 static void _prop_array_free(void *); 59 static boolean_t _prop_array_externalize( 60 struct _prop_object_externalize_context *, 61 void *); 62 static boolean_t _prop_array_equals(void *, void *); 63 64 static const struct _prop_object_type _prop_object_type_array = { 65 .pot_type = PROP_TYPE_ARRAY, 66 .pot_free = _prop_array_free, 67 .pot_extern = _prop_array_externalize, 68 .pot_equals = _prop_array_equals, 69 }; 70 71 #define prop_object_is_array(x) \ 72 ((x)->pa_obj.po_type == &_prop_object_type_array) 73 74 #define prop_array_is_immutable(x) (((x)->pa_flags & PA_F_IMMUTABLE) != 0) 75 76 struct _prop_array_iterator { 77 struct _prop_object_iterator pai_base; 78 unsigned int pai_index; 79 }; 80 81 #define EXPAND_STEP 16 82 83 static void 84 _prop_array_free(void *v) 85 { 86 prop_array_t pa = v; 87 prop_object_t po; 88 unsigned int idx; 89 90 _PROP_ASSERT(pa->pa_count <= pa->pa_capacity); 91 _PROP_ASSERT((pa->pa_capacity == 0 && pa->pa_array == NULL) || 92 (pa->pa_capacity != 0 && pa->pa_array != NULL)); 93 94 for (idx = 0; idx < pa->pa_count; idx++) { 95 po = pa->pa_array[idx]; 96 _PROP_ASSERT(po != NULL); 97 prop_object_release(po); 98 } 99 100 if (pa->pa_array != NULL) 101 _PROP_FREE(pa->pa_array, M_PROP_ARRAY); 102 103 _PROP_POOL_PUT(_prop_array_pool, pa); 104 } 105 106 static boolean_t 107 _prop_array_externalize(struct _prop_object_externalize_context *ctx, 108 void *v) 109 { 110 prop_array_t pa = v; 111 struct _prop_object *po; 112 prop_object_iterator_t pi; 113 unsigned int i; 114 115 if (pa->pa_count == 0) 116 return (_prop_object_externalize_empty_tag(ctx, "array")); 117 118 /* XXXJRT Hint "count" for the internalize step? */ 119 if (_prop_object_externalize_start_tag(ctx, "array") == FALSE || 120 _prop_object_externalize_append_char(ctx, '\n') == FALSE) 121 return (FALSE); 122 123 pi = prop_array_iterator(pa); 124 if (pi == NULL) 125 return (FALSE); 126 127 ctx->poec_depth++; 128 _PROP_ASSERT(ctx->poec_depth != 0); 129 130 while ((po = prop_object_iterator_next(pi)) != NULL) { 131 if ((*po->po_type->pot_extern)(ctx, po) == FALSE) { 132 prop_object_iterator_release(pi); 133 return (FALSE); 134 } 135 } 136 137 prop_object_iterator_release(pi); 138 139 ctx->poec_depth--; 140 for (i = 0; i < ctx->poec_depth; i++) { 141 if (_prop_object_externalize_append_char(ctx, '\t') == FALSE) 142 return (FALSE); 143 } 144 if (_prop_object_externalize_end_tag(ctx, "array") == FALSE) 145 return (FALSE); 146 147 return (TRUE); 148 } 149 150 static boolean_t 151 _prop_array_equals(void *v1, void *v2) 152 { 153 prop_array_t array1 = v1; 154 prop_array_t array2 = v2; 155 unsigned int idx; 156 157 _PROP_ASSERT(prop_object_is_array(array1)); 158 _PROP_ASSERT(prop_object_is_array(array2)); 159 160 if (array1 == array2) 161 return (TRUE); 162 if (array1->pa_count != array2->pa_count) 163 return (FALSE); 164 165 for (idx = 0; idx < array1->pa_count; idx++) { 166 if (prop_object_equals(array1->pa_array[idx], 167 array2->pa_array[idx]) == FALSE) 168 return (FALSE); 169 } 170 171 return (TRUE); 172 } 173 174 static prop_array_t 175 _prop_array_alloc(unsigned int capacity) 176 { 177 prop_array_t pa; 178 prop_object_t *array; 179 180 if (capacity != 0) { 181 array = _PROP_CALLOC(capacity * sizeof(prop_object_t), 182 M_PROP_ARRAY); 183 if (array == NULL) 184 return (NULL); 185 } else 186 array = NULL; 187 188 189 pa = _PROP_POOL_GET(_prop_array_pool); 190 if (pa != NULL) { 191 _prop_object_init(&pa->pa_obj, &_prop_object_type_array); 192 pa->pa_obj.po_type = &_prop_object_type_array; 193 194 pa->pa_array = array; 195 pa->pa_capacity = capacity; 196 pa->pa_count = 0; 197 pa->pa_flags = 0; 198 199 pa->pa_version = 0; 200 } else if (array != NULL) 201 _PROP_FREE(array, M_PROP_ARRAY); 202 203 return (pa); 204 } 205 206 static boolean_t 207 _prop_array_expand(prop_array_t pa, unsigned int capacity) 208 { 209 prop_object_t *array, *oarray; 210 211 oarray = pa->pa_array; 212 213 array = _PROP_CALLOC(capacity * sizeof(*array), M_PROP_ARRAY); 214 if (array == NULL) 215 return (FALSE); 216 if (oarray != NULL) 217 memcpy(array, oarray, pa->pa_capacity * sizeof(*array)); 218 pa->pa_array = array; 219 pa->pa_capacity = capacity; 220 221 if (oarray != NULL) 222 _PROP_FREE(oarray, M_PROP_ARRAY); 223 224 return (TRUE); 225 } 226 227 static prop_object_t 228 _prop_array_iterator_next_object(void *v) 229 { 230 struct _prop_array_iterator *pai = v; 231 prop_array_t pa = pai->pai_base.pi_obj; 232 prop_object_t po; 233 234 _PROP_ASSERT(prop_object_is_array(pa)); 235 236 if (pa->pa_version != pai->pai_base.pi_version) 237 return (NULL); /* array changed during iteration */ 238 239 _PROP_ASSERT(pai->pai_index <= pa->pa_count); 240 241 if (pai->pai_index == pa->pa_count) 242 return (NULL); /* we've iterated all objects */ 243 244 po = pa->pa_array[pai->pai_index]; 245 pai->pai_index++; 246 247 return (po); 248 } 249 250 static void 251 _prop_array_iterator_reset(void *v) 252 { 253 struct _prop_array_iterator *pai = v; 254 prop_array_t pa = pai->pai_base.pi_obj; 255 256 _PROP_ASSERT(prop_object_is_array(pa)); 257 258 pai->pai_index = 0; 259 pai->pai_base.pi_version = pa->pa_version; 260 } 261 262 /* 263 * prop_array_create -- 264 * Create an empty array. 265 */ 266 prop_array_t 267 prop_array_create(void) 268 { 269 270 return (_prop_array_alloc(0)); 271 } 272 273 /* 274 * prop_array_create_with_capacity -- 275 * Create an array with the capacity to store N objects. 276 */ 277 prop_array_t 278 prop_array_create_with_capacity(unsigned int capacity) 279 { 280 281 return (_prop_array_alloc(capacity)); 282 } 283 284 /* 285 * prop_array_copy -- 286 * Copy an array. The new array has an initial capacity equal to 287 * the number of objects stored in the original array. The new 288 * array contains references to the original array's objects, not 289 * copies of those objects (i.e. a shallow copy). 290 */ 291 prop_array_t 292 prop_array_copy(prop_array_t opa) 293 { 294 prop_array_t pa; 295 prop_object_t po; 296 unsigned int idx; 297 298 _PROP_ASSERT(prop_object_is_array(opa)); 299 300 pa = _prop_array_alloc(opa->pa_count); 301 if (pa != NULL) { 302 for (idx = 0; idx < opa->pa_count; idx++) { 303 po = opa->pa_array[idx]; 304 prop_object_retain(po); 305 pa->pa_array[idx] = po; 306 } 307 pa->pa_count = opa->pa_count; 308 pa->pa_flags = opa->pa_flags; 309 } 310 return (pa); 311 } 312 313 /* 314 * prop_array_copy_mutable -- 315 * Like prop_array_copy(), but the resulting array is mutable. 316 */ 317 prop_array_t 318 prop_array_copy_mutable(prop_array_t opa) 319 { 320 prop_array_t pa; 321 322 pa = prop_array_copy(opa); 323 if (pa != NULL) 324 pa->pa_flags &= ~PA_F_IMMUTABLE; 325 326 return (pa); 327 } 328 329 /* 330 * prop_array_capacity -- 331 * Return the capacity of the array. 332 */ 333 unsigned int 334 prop_array_capacity(prop_array_t pa) 335 { 336 337 _PROP_ASSERT(prop_object_is_array(pa)); 338 return (pa->pa_capacity); 339 } 340 341 /* 342 * prop_array_count -- 343 * Return the number of objects stored in the array. 344 */ 345 unsigned int 346 prop_array_count(prop_array_t pa) 347 { 348 349 _PROP_ASSERT(prop_object_is_array(pa)); 350 return (pa->pa_count); 351 } 352 353 /* 354 * prop_array_ensure_capacity -- 355 * Ensure that the array has the capacity to store the specified 356 * total number of objects (inluding the objects already stored 357 * in the array). 358 */ 359 boolean_t 360 prop_array_ensure_capacity(prop_array_t pa, unsigned int capacity) 361 { 362 363 _PROP_ASSERT(prop_object_is_array(pa)); 364 if (capacity > pa->pa_capacity) 365 return (_prop_array_expand(pa, capacity)); 366 return (TRUE); 367 } 368 369 /* 370 * prop_array_iterator -- 371 * Return an iterator for the array. The array is retained by 372 * the iterator. 373 */ 374 prop_object_iterator_t 375 prop_array_iterator(prop_array_t pa) 376 { 377 struct _prop_array_iterator *pai; 378 379 _PROP_ASSERT(prop_object_is_array(pa)); 380 381 pai = _PROP_CALLOC(sizeof(*pai), M_TEMP); 382 if (pai == NULL) 383 return (NULL); 384 pai->pai_base.pi_next_object = _prop_array_iterator_next_object; 385 pai->pai_base.pi_reset = _prop_array_iterator_reset; 386 prop_object_retain(pa); 387 pai->pai_base.pi_obj = pa; 388 pai->pai_base.pi_version = pa->pa_version; 389 390 _prop_array_iterator_reset(pai); 391 392 return (&pai->pai_base); 393 } 394 395 /* 396 * prop_array_make_immutable -- 397 * Make the array immutable. 398 */ 399 void 400 prop_array_make_immutable(prop_array_t pa) 401 { 402 403 if (prop_array_is_immutable(pa) == FALSE) 404 pa->pa_flags |= PA_F_IMMUTABLE; 405 } 406 407 /* 408 * prop_array_mutable -- 409 * Returns TRUE if the array is mutable. 410 */ 411 boolean_t 412 prop_array_mutable(prop_array_t pa) 413 { 414 415 return (prop_array_is_immutable(pa) == FALSE); 416 } 417 418 /* 419 * prop_array_get -- 420 * Return the object stored at the specified array index. 421 */ 422 prop_object_t 423 prop_array_get(prop_array_t pa, unsigned int idx) 424 { 425 prop_object_t po; 426 427 _PROP_ASSERT(prop_object_is_array(pa)); 428 if (idx >= pa->pa_count) 429 return (NULL); 430 po = pa->pa_array[idx]; 431 _PROP_ASSERT(po != NULL); 432 return (po); 433 } 434 435 /* 436 * prop_array_set -- 437 * Store a reference to an object at the specified array index. 438 * This method is not allowed to create holes in the array; the 439 * caller must either be setting the object just beyond the existing 440 * count or replacing an already existing object reference. 441 */ 442 boolean_t 443 prop_array_set(prop_array_t pa, unsigned int idx, prop_object_t po) 444 { 445 prop_object_t opo; 446 447 _PROP_ASSERT(prop_object_is_array(pa)); 448 449 if (prop_array_is_immutable(pa)) 450 return (FALSE); 451 452 if (idx == pa->pa_count) 453 return (prop_array_add(pa, po)); 454 455 _PROP_ASSERT(idx < pa->pa_count); 456 457 opo = pa->pa_array[idx]; 458 _PROP_ASSERT(opo != NULL); 459 460 prop_object_retain(po); 461 pa->pa_array[idx] = po; 462 pa->pa_version++; 463 464 prop_object_release(opo); 465 466 return (TRUE); 467 } 468 469 /* 470 * prop_array_add -- 471 * Add a refrerence to an object to the specified array, appending 472 * to the end and growing the array's capacity, if necessary. 473 */ 474 boolean_t 475 prop_array_add(prop_array_t pa, prop_object_t po) 476 { 477 478 _PROP_ASSERT(prop_object_is_array(pa)); 479 _PROP_ASSERT(pa->pa_count <= pa->pa_capacity); 480 481 if (prop_array_is_immutable(pa) || 482 (pa->pa_count == pa->pa_capacity && 483 _prop_array_expand(pa, pa->pa_capacity + EXPAND_STEP) == FALSE)) 484 return (FALSE); 485 486 prop_object_retain(po); 487 pa->pa_array[pa->pa_count++] = po; 488 pa->pa_version++; 489 490 return (TRUE); 491 } 492 493 /* 494 * prop_array_remove -- 495 * Remove the reference to an object from an array at the specified 496 * index. The array will be compacted following the removal. 497 */ 498 void 499 prop_array_remove(prop_array_t pa, unsigned int idx) 500 { 501 prop_object_t po; 502 503 _PROP_ASSERT(prop_object_is_array(pa)); 504 _PROP_ASSERT(idx < pa->pa_count); 505 506 /* XXX Should this be a _PROP_ASSERT()? */ 507 if (prop_array_is_immutable(pa)) 508 return; 509 510 po = pa->pa_array[idx]; 511 _PROP_ASSERT(po != NULL); 512 513 for (++idx; idx < pa->pa_count; idx++) 514 pa->pa_array[idx - 1] = pa->pa_array[idx]; 515 pa->pa_count--; 516 pa->pa_version++; 517 518 prop_object_release(po); 519 } 520 521 /* 522 * prop_array_equals -- 523 * Return TRUE if the two arrays are equivalent. Note we do a 524 * by-value comparison of the objects in the array. 525 */ 526 boolean_t 527 prop_array_equals(prop_array_t array1, prop_array_t array2) 528 { 529 530 return (_prop_array_equals(array1, array2)); 531 } 532 533 /* 534 * _prop_array_internalize -- 535 * Parse an <array>...</array> and return the object created from the 536 * external representation. 537 */ 538 prop_object_t 539 _prop_array_internalize(struct _prop_object_internalize_context *ctx) 540 { 541 prop_array_t array; 542 prop_object_t obj; 543 544 /* We don't currently understand any attributes. */ 545 if (ctx->poic_tagattr != NULL) 546 return (NULL); 547 548 array = prop_array_create(); 549 if (array == NULL) 550 return (NULL); 551 552 if (ctx->poic_is_empty_element) 553 return (array); 554 555 for (;;) { 556 /* Fetch the next tag. */ 557 if (_prop_object_internalize_find_tag(ctx, NULL, 558 _PROP_TAG_TYPE_EITHER) == FALSE) 559 goto bad; 560 561 /* Check to see if this is the end of the array. */ 562 if (_PROP_TAG_MATCH(ctx, "array") && 563 ctx->poic_tag_type == _PROP_TAG_TYPE_END) 564 break; 565 566 /* Fetch the object. */ 567 obj = _prop_object_internalize_by_tag(ctx); 568 if (obj == NULL) 569 goto bad; 570 571 if (prop_array_add(array, obj) == FALSE) { 572 prop_object_release(obj); 573 goto bad; 574 } 575 prop_object_release(obj); 576 } 577 578 return (array); 579 580 bad: 581 prop_object_release(array); 582 return (NULL); 583 } 584