1 /* 2 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 #pragma ident "%Z%%M% %I% %E% SMI" 7 8 /* 9 * prof_tree.c --- these routines maintain the parse tree of the 10 * config file. 11 * 12 * All of the details of how the tree is stored is abstracted away in 13 * this file; all of the other profile routines build, access, and 14 * modify the tree via the accessor functions found in this file. 15 * 16 * Each node may represent either a relation or a section header. 17 * 18 * A section header must have its value field set to 0, and may a one 19 * or more child nodes, pointed to by first_child. 20 * 21 * A relation has as its value a pointer to allocated memory 22 * containing a string. Its first_child pointer must be null. 23 * 24 */ 25 26 27 #include "prof_int.h" 28 29 #include <stdio.h> 30 #include <string.h> 31 #ifdef HAVE_STDLIB_H 32 #include <stdlib.h> 33 #endif 34 #include <errno.h> 35 #include <ctype.h> 36 37 struct profile_node { 38 errcode_t magic; 39 char *name; 40 char *value; 41 int group_level; 42 int final:1; /* Indicate don't search next file */ 43 int deleted:1; 44 struct profile_node *first_child; 45 struct profile_node *parent; 46 struct profile_node *next, *prev; 47 }; 48 49 #define CHECK_MAGIC(node) \ 50 if ((node)->magic != PROF_MAGIC_NODE) \ 51 return PROF_MAGIC_NODE; 52 53 /* 54 * Free a node, and any children 55 */ 56 void profile_free_node(struct profile_node *node) 57 { 58 struct profile_node *child, *next; 59 60 if (node->magic != PROF_MAGIC_NODE) 61 return; 62 63 if (node->name) 64 free(node->name); 65 if (node->value) 66 free(node->value); 67 68 for (child=node->first_child; child; child = next) { 69 next = child->next; 70 profile_free_node(child); 71 } 72 node->magic = 0; 73 74 free(node); 75 } 76 77 #ifndef HAVE_STRDUP 78 #undef strdup 79 #define strdup MYstrdup 80 static char *MYstrdup (const char *s) 81 { 82 size_t sz = strlen(s) + 1; 83 char *p = malloc(sz); 84 if (p != 0) 85 memcpy(p, s, sz); 86 return p; 87 } 88 #endif 89 90 /* 91 * Create a node 92 */ 93 errcode_t profile_create_node(const char *name, const char *value, 94 struct profile_node **ret_node) 95 { 96 struct profile_node *new; 97 98 new = (struct profile_node *)malloc(sizeof(struct profile_node)); 99 if (!new) 100 return ENOMEM; 101 memset(new, 0, sizeof(struct profile_node)); 102 new->name = (char *) strdup(name); 103 if (new->name == 0) { 104 profile_free_node(new); 105 return ENOMEM; 106 } 107 if (value) { 108 new->value = (char *) strdup(value); 109 if (new->value == 0) { 110 profile_free_node(new); 111 return ENOMEM; 112 } 113 } 114 new->magic = PROF_MAGIC_NODE; 115 116 *ret_node = new; 117 return 0; 118 } 119 120 /* 121 * This function verifies that all of the representation invarients of 122 * the profile are true. If not, we have a programming bug somewhere, 123 * probably in this file. 124 */ 125 errcode_t profile_verify_node(struct profile_node *node) 126 { 127 struct profile_node *p, *last; 128 errcode_t retval; 129 130 CHECK_MAGIC(node); 131 132 if (node->value && node->first_child) 133 return PROF_SECTION_WITH_VALUE; 134 135 last = 0; 136 for (p = node->first_child; p; last = p, p = p->next) { 137 if (p->prev != last) 138 return PROF_BAD_LINK_LIST; 139 if (last && (last->next != p)) 140 return PROF_BAD_LINK_LIST; 141 if (node->group_level+1 != p->group_level) 142 return PROF_BAD_GROUP_LVL; 143 if (p->parent != node) 144 return PROF_BAD_PARENT_PTR; 145 retval = profile_verify_node(p); 146 if (retval) 147 return retval; 148 } 149 return 0; 150 } 151 152 /* 153 * Add a node to a particular section 154 */ 155 errcode_t profile_add_node(struct profile_node *section, const char *name, 156 const char *value, struct profile_node **ret_node) 157 { 158 errcode_t retval; 159 struct profile_node *p, *last, *new; 160 161 CHECK_MAGIC(section); 162 163 if (section->value) 164 return PROF_ADD_NOT_SECTION; 165 166 /* 167 * Find the place to insert the new node. We look for the 168 * place *after* the last match of the node name, since 169 * order matters. 170 */ 171 for (p=section->first_child, last = 0; p; last = p, p = p->next) { 172 int cmp; 173 cmp = strcmp(p->name, name); 174 if (cmp > 0) 175 break; 176 } 177 retval = profile_create_node(name, value, &new); 178 if (retval) 179 return retval; 180 new->group_level = section->group_level+1; 181 new->deleted = 0; 182 new->parent = section; 183 new->prev = last; 184 new->next = p; 185 if (p) 186 p->prev = new; 187 if (last) 188 last->next = new; 189 else 190 section->first_child = new; 191 if (ret_node) 192 *ret_node = new; 193 return 0; 194 } 195 196 /* 197 * Set the final flag on a particular node. 198 */ 199 errcode_t profile_make_node_final(struct profile_node *node) 200 { 201 CHECK_MAGIC(node); 202 203 node->final = 1; 204 return 0; 205 } 206 207 /* 208 * Check the final flag on a node 209 */ 210 int profile_is_node_final(struct profile_node *node) 211 { 212 return (node->final != 0); 213 } 214 215 /* 216 * Return the name of a node. (Note: this is for internal functions 217 * only; if the name needs to be returned from an exported function, 218 * strdup it first!) 219 */ 220 const char *profile_get_node_name(struct profile_node *node) 221 { 222 return node->name; 223 } 224 225 /* 226 * Return the value of a node. (Note: this is for internal functions 227 * only; if the name needs to be returned from an exported function, 228 * strdup it first!) 229 */ 230 const char *profile_get_node_value(struct profile_node *node) 231 { 232 return node->value; 233 } 234 235 /* 236 * Iterate through the section, returning the nodes which match 237 * the given name. If name is NULL, then interate through all the 238 * nodes in the section. If section_flag is non-zero, only return the 239 * section which matches the name; don't return relations. If value 240 * is non-NULL, then only return relations which match the requested 241 * value. (The value argument is ignored if section_flag is non-zero.) 242 * 243 * The first time this routine is called, the state pointer must be 244 * null. When this profile_find_node_relation() returns, if the state 245 * pointer is non-NULL, then this routine should be called again. 246 * (This won't happen if section_flag is non-zero, obviously.) 247 * 248 */ 249 errcode_t profile_find_node(struct profile_node *section, const char *name, 250 const char *value, int section_flag, void **state, 251 struct profile_node **node) 252 { 253 struct profile_node *p; 254 255 CHECK_MAGIC(section); 256 p = *state; 257 if (p) { 258 CHECK_MAGIC(p); 259 } else 260 p = section->first_child; 261 262 for (; p; p = p->next) { 263 if (name && (strcmp(p->name, name))) 264 continue; 265 if (section_flag) { 266 if (p->value) 267 continue; 268 } else { 269 if (!p->value) 270 continue; 271 if (value && (strcmp(p->value, value))) 272 continue; 273 } 274 if (p->deleted) 275 continue; 276 /* A match! */ 277 if (node) 278 *node = p; 279 break; 280 } 281 if (p == 0) { 282 *state = 0; 283 return section_flag ? PROF_NO_SECTION : PROF_NO_RELATION; 284 } 285 /* 286 * OK, we've found one match; now let's try to find another 287 * one. This way, if we return a non-zero state pointer, 288 * there's guaranteed to be another match that's returned. 289 */ 290 for (p = p->next; p; p = p->next) { 291 if (name && (strcmp(p->name, name))) 292 continue; 293 if (section_flag) { 294 if (p->value) 295 continue; 296 } else { 297 if (!p->value) 298 continue; 299 if (value && (strcmp(p->value, value))) 300 continue; 301 } 302 /* A match! */ 303 break; 304 } 305 *state = p; 306 return 0; 307 } 308 309 310 /* 311 * Iterate through the section, returning the relations which match 312 * the given name. If name is NULL, then interate through all the 313 * relations in the section. The first time this routine is called, 314 * the state pointer must be null. When this profile_find_node_relation() 315 * returns, if the state pointer is non-NULL, then this routine should 316 * be called again. 317 * 318 * The returned character string in value points to the stored 319 * character string in the parse string. Before this string value is 320 * returned to a calling application (profile_find_node_relation is not an 321 * exported interface), it should be strdup()'ed. 322 */ 323 errcode_t profile_find_node_relation(struct profile_node *section, 324 const char *name, void **state, 325 char **ret_name, char **value) 326 { 327 struct profile_node *p; 328 errcode_t retval; 329 330 retval = profile_find_node(section, name, 0, 0, state, &p); 331 if (retval) 332 return retval; 333 334 if (p) { 335 if (value) 336 *value = p->value; 337 if (ret_name) 338 *ret_name = p->name; 339 } 340 return 0; 341 } 342 343 /* 344 * Iterate through the section, returning the subsections which match 345 * the given name. If name is NULL, then interate through all the 346 * subsections in the section. The first time this routine is called, 347 * the state pointer must be null. When this profile_find_node_subsection() 348 * returns, if the state pointer is non-NULL, then this routine should 349 * be called again. 350 * 351 * This is (plus accessor functions for the name and value given a 352 * profile node) makes this function mostly syntactic sugar for 353 * profile_find_node. 354 */ 355 errcode_t profile_find_node_subsection(struct profile_node *section, 356 const char *name, void **state, 357 char **ret_name, 358 struct profile_node **subsection) 359 { 360 struct profile_node *p; 361 errcode_t retval; 362 363 if (section == (struct profile_node *)NULL) 364 return (PROF_NO_PROFILE); 365 366 retval = profile_find_node(section, name, 0, 1, state, &p); 367 if (retval) 368 return retval; 369 370 if (p) { 371 if (subsection) 372 *subsection = p; 373 if (ret_name) 374 *ret_name = p->name; 375 } 376 return 0; 377 } 378 379 /* 380 * This function returns the parent of a particular node. 381 */ 382 errcode_t profile_get_node_parent(struct profile_node *section, 383 struct profile_node **parent) 384 { 385 *parent = section->parent; 386 return 0; 387 } 388 389 /* 390 * This is a general-purpose iterator for returning all nodes that 391 * match the specified name array. 392 */ 393 struct profile_iterator { 394 prf_magic_t magic; 395 profile_t profile; 396 int flags; 397 const char *const *names; 398 const char *name; 399 prf_file_t file; 400 int file_serial; 401 int done_idx; 402 struct profile_node *node; 403 int num; 404 }; 405 406 errcode_t profile_node_iterator_create(profile_t profile, 407 const char *const *names, int flags, 408 void **ret_iter) 409 { 410 struct profile_iterator *iter; 411 int done_idx = 0; 412 413 if (profile == 0) 414 return PROF_NO_PROFILE; 415 if (profile->magic != PROF_MAGIC_PROFILE) 416 return PROF_MAGIC_PROFILE; 417 if (!names) 418 return PROF_BAD_NAMESET; 419 if (!(flags & PROFILE_ITER_LIST_SECTION)) { 420 if (!names[0]) 421 return PROF_BAD_NAMESET; 422 done_idx = 1; 423 } 424 425 if ((iter = (struct profile_iterator *) 426 malloc(sizeof(struct profile_iterator))) == NULL) 427 return ENOMEM; 428 429 iter->magic = PROF_MAGIC_ITERATOR; 430 iter->profile = profile; 431 iter->names = names; 432 iter->flags = flags; 433 iter->file = profile->first_file; 434 iter->done_idx = done_idx; 435 iter->node = 0; 436 iter->num = 0; 437 *ret_iter = iter; 438 return 0; 439 } 440 441 void profile_node_iterator_free(void **iter_p) 442 { 443 struct profile_iterator *iter; 444 445 if (!iter_p) 446 return; 447 iter = *iter_p; 448 if (!iter || iter->magic != PROF_MAGIC_ITERATOR) 449 return; 450 free(iter); 451 *iter_p = 0; 452 } 453 454 /* 455 * Note: the returned character strings in ret_name and ret_value 456 * points to the stored character string in the parse string. Before 457 * this string value is returned to a calling application 458 * (profile_node_iterator is not an exported interface), it should be 459 * strdup()'ed. 460 */ 461 errcode_t profile_node_iterator(void **iter_p, struct profile_node **ret_node, 462 char **ret_name, char **ret_value) 463 { 464 struct profile_iterator *iter = *iter_p; 465 struct profile_node *section, *p; 466 const char *const *cpp; 467 errcode_t retval; 468 int skip_num = 0; 469 470 if (!iter || iter->magic != PROF_MAGIC_ITERATOR) 471 return PROF_MAGIC_ITERATOR; 472 if (iter->file && iter->file->magic != PROF_MAGIC_FILE) 473 return PROF_MAGIC_FILE; 474 if (iter->file && iter->file->data->magic != PROF_MAGIC_FILE_DATA) 475 return PROF_MAGIC_FILE_DATA; 476 /* 477 * If the file has changed, then the node pointer is invalid, 478 * so we'll have search the file again looking for it. 479 */ 480 if (iter->file) { 481 retval = k5_mutex_lock(&iter->file->data->lock); 482 if (retval) 483 return retval; 484 } 485 if (iter->node && (iter->file->data->upd_serial != iter->file_serial)) { 486 iter->flags &= ~PROFILE_ITER_FINAL_SEEN; 487 skip_num = iter->num; 488 iter->node = 0; 489 } 490 if (iter->node && iter->node->magic != PROF_MAGIC_NODE) { 491 if (iter->file) 492 k5_mutex_unlock(&iter->file->data->lock); 493 return PROF_MAGIC_NODE; 494 } 495 get_new_file: 496 if (iter->node == 0) { 497 if (iter->file == 0 || 498 (iter->flags & PROFILE_ITER_FINAL_SEEN)) { 499 if (iter->file) 500 k5_mutex_unlock(&iter->file->data->lock); 501 profile_node_iterator_free(iter_p); 502 if (ret_node) 503 *ret_node = 0; 504 if (ret_name) 505 *ret_name = 0; 506 if (ret_value) 507 *ret_value =0; 508 return 0; 509 } 510 k5_mutex_unlock(&iter->file->data->lock); 511 if ((retval = profile_update_file(iter->file))) { 512 if (retval == ENOENT || retval == EACCES) { 513 /* XXX memory leak? */ 514 iter->file = iter->file->next; 515 if (iter->file) { 516 retval = k5_mutex_lock(&iter->file->data->lock); 517 if (retval) { 518 profile_node_iterator_free(iter_p); 519 return retval; 520 } 521 } 522 skip_num = 0; 523 retval = 0; 524 goto get_new_file; 525 } else { 526 profile_node_iterator_free(iter_p); 527 return retval; 528 } 529 } 530 retval = k5_mutex_lock(&iter->file->data->lock); 531 if (retval) { 532 profile_node_iterator_free(iter_p); 533 return retval; 534 } 535 iter->file_serial = iter->file->data->upd_serial; 536 /* 537 * Find the section to list if we are a LIST_SECTION, 538 * or find the containing section if not. 539 */ 540 section = iter->file->data->root; 541 for (cpp = iter->names; cpp[iter->done_idx]; cpp++) { 542 for (p=section->first_child; p; p = p->next) { 543 if (!strcmp(p->name, *cpp) && !p->value) 544 break; 545 } 546 if (!p) { 547 section = 0; 548 break; 549 } 550 section = p; 551 if (p->final) 552 iter->flags |= PROFILE_ITER_FINAL_SEEN; 553 } 554 if (!section) { 555 k5_mutex_unlock(&iter->file->data->lock); 556 iter->file = iter->file->next; 557 if (iter->file) { 558 retval = k5_mutex_lock(&iter->file->data->lock); 559 if (retval) { 560 profile_node_iterator_free(iter_p); 561 return retval; 562 } 563 } 564 skip_num = 0; 565 goto get_new_file; 566 } 567 iter->name = *cpp; 568 iter->node = section->first_child; 569 } 570 /* 571 * OK, now we know iter->node is set up correctly. Let's do 572 * the search. 573 */ 574 for (p = iter->node; p; p = p->next) { 575 if (iter->name && strcmp(p->name, iter->name)) 576 continue; 577 if ((iter->flags & PROFILE_ITER_SECTIONS_ONLY) && 578 p->value) 579 continue; 580 if ((iter->flags & PROFILE_ITER_RELATIONS_ONLY) && 581 !p->value) 582 continue; 583 if (skip_num > 0) { 584 skip_num--; 585 continue; 586 } 587 break; 588 } 589 iter->num++; 590 if (!p) { 591 k5_mutex_unlock(&iter->file->data->lock); 592 iter->file = iter->file->next; 593 if (iter->file) { 594 retval = k5_mutex_lock(&iter->file->data->lock); 595 if (retval) { 596 profile_node_iterator_free(iter_p); 597 return retval; 598 } 599 } 600 iter->node = 0; 601 skip_num = 0; 602 goto get_new_file; 603 } 604 k5_mutex_unlock(&iter->file->data->lock); 605 if ((iter->node = p->next) == NULL) 606 iter->file = iter->file->next; 607 if (ret_node) 608 *ret_node = p; 609 if (ret_name) 610 *ret_name = p->name; 611 if (ret_value) 612 *ret_value = p->value; 613 return 0; 614 } 615 616 /* 617 * Remove a particular node. 618 * 619 * TYT, 2/25/99 620 */ 621 errcode_t profile_remove_node(struct profile_node *node) 622 { 623 CHECK_MAGIC(node); 624 625 if (node->parent == 0) 626 return PROF_EINVAL; /* Can't remove the root! */ 627 628 node->deleted = 1; 629 630 return 0; 631 } 632 633 /* 634 * Set the value of a specific node containing a relation. 635 * 636 * TYT, 2/25/99 637 */ 638 errcode_t profile_set_relation_value(struct profile_node *node, 639 const char *new_value) 640 { 641 char *cp; 642 643 CHECK_MAGIC(node); 644 645 if (!node->value) 646 return PROF_SET_SECTION_VALUE; 647 648 cp = (char *) malloc(strlen(new_value)+1); 649 if (!cp) 650 return ENOMEM; 651 652 strcpy(cp, new_value); 653 free(node->value); 654 node->value = cp; 655 656 return 0; 657 } 658 659 /* 660 * Rename a specific node 661 * 662 * TYT 2/25/99 663 */ 664 errcode_t profile_rename_node(struct profile_node *node, const char *new_name) 665 { 666 char *new_string; 667 struct profile_node *p, *last; 668 669 CHECK_MAGIC(node); 670 671 if (strcmp(new_name, node->name) == 0) 672 return 0; /* It's the same name, return */ 673 674 /* 675 * Make sure we can allocate memory for the new name, first! 676 */ 677 new_string = (char *) malloc(strlen(new_name)+1); 678 if (!new_string) 679 return ENOMEM; 680 strcpy(new_string, new_name); 681 682 /* 683 * Find the place to where the new node should go. We look 684 * for the place *after* the last match of the node name, 685 * since order matters. 686 */ 687 for (p=node->parent->first_child, last = 0; p; last = p, p = p->next) { 688 if (strcmp(p->name, new_name) > 0) 689 break; 690 } 691 692 /* 693 * If we need to move the node, do it now. 694 */ 695 if ((p != node) && (last != node)) { 696 /* 697 * OK, let's detach the node 698 */ 699 if (node->prev) 700 node->prev->next = node->next; 701 else 702 node->parent->first_child = node->next; 703 if (node->next) 704 node->next->prev = node->prev; 705 706 /* 707 * Now let's reattach it in the right place. 708 */ 709 if (p) 710 p->prev = node; 711 if (last) 712 last->next = node; 713 else 714 node->parent->first_child = node; 715 node->next = p; 716 node->prev = last; 717 } 718 719 free(node->name); 720 node->name = new_string; 721 return 0; 722 } 723