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