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