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