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