Home | History | Annotate | Line # | Download | only in ctags 
      1 /*	$NetBSD: tree.c,v 1.12 2006/04/05 19:38:47 dsl Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1987, 1993, 1994
      5  *	The Regents of the University of California.  All rights reserved.
      6  *
      7  * Redistribution and use in source and binary forms, with or without
      8  * modification, are permitted provided that the following conditions
      9  * are met:
     10  * 1. Redistributions of source code must retain the above copyright
     11  *    notice, this list of conditions and the following disclaimer.
     12  * 2. Redistributions in binary form must reproduce the above copyright
     13  *    notice, this list of conditions and the following disclaimer in the
     14  *    documentation and/or other materials provided with the distribution.
     15  * 3. Neither the name of the University nor the names of its contributors
     16  *    may be used to endorse or promote products derived from this software
     17  *    without specific prior written permission.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     29  * SUCH DAMAGE.
     30  */
     31 
     32 #if HAVE_NBTOOL_CONFIG_H
     33 #include "nbtool_config.h"
     34 #endif
     35 
     36 #include <sys/cdefs.h>
     37 #if defined(__RCSID) && !defined(lint)
     38 #if 0
     39 static char sccsid[] = "@(#)tree.c	8.3 (Berkeley) 4/2/94";
     40 #else
     41 __RCSID("$NetBSD: tree.c,v 1.12 2006/04/05 19:38:47 dsl Exp $");
     42 #endif
     43 #endif /* not lint */
     44 
     45 #include <err.h>
     46 #include <limits.h>
     47 #include <stdio.h>
     48 #include <stdlib.h>
     49 #include <string.h>
     50 
     51 #include "ctags.h"
     52 
     53 static void	add_node(NODE *, NODE *);
     54 static void	free_tree(NODE *);
     55 
     56 /*
     57  * pfnote --
     58  *	enter a new node in the tree
     59  */
     60 void
     61 pfnote(const char *name, int ln)
     62 {
     63 	NODE	*np;
     64 	char	*fp;
     65 	char	nbuf[MAXTOKEN];
     66 
     67 	/*NOSTRICT*/
     68 	if (!(np = (NODE *)malloc(sizeof(NODE)))) {
     69 		warnx("too many entries to sort");
     70 		put_entries(head);
     71 		free_tree(head);
     72 		/*NOSTRICT*/
     73 		if (!(head = np = (NODE *)malloc(sizeof(NODE))))
     74 			err(1, "out of space");
     75 	}
     76 	if (!xflag && !strcmp(name, "main")) {
     77 		if (!(fp = strrchr(curfile, '/')))
     78 			fp = curfile;
     79 		else
     80 			++fp;
     81 		(void)snprintf(nbuf, sizeof(nbuf), "M%s", fp);
     82 		fp = strrchr(nbuf, '.');
     83 		if (fp && !fp[2])
     84 			*fp = EOS;
     85 		name = nbuf;
     86 	}
     87 	if (!(np->entry = strdup(name)))
     88 		err(1, "strdup");
     89 	np->file = curfile;
     90 	np->lno = ln;
     91 	np->left = np->right = 0;
     92 	if (!(np->pat = strdup(lbuf)))
     93 		err(1, "strdup");
     94 	if (!head)
     95 		head = np;
     96 	else
     97 		add_node(np, head);
     98 }
     99 
    100 static void
    101 add_node(NODE *node, NODE *cur_node)
    102 {
    103 	int	dif;
    104 
    105 	dif = strcmp(node->entry, cur_node->entry);
    106 	if (!dif) {
    107 		if (node->file == cur_node->file) {
    108 			if (!wflag)
    109 				fprintf(stderr, "Duplicate entry in file %s, line %d: %s\nSecond entry ignored\n", node->file, lineno, node->entry);
    110 			return;
    111 		}
    112 		if (!cur_node->been_warned)
    113 			if (!wflag)
    114 				fprintf(stderr, "Duplicate entry in files %s and %s: %s (Warning only)\n", node->file, cur_node->file, node->entry);
    115 		cur_node->been_warned = YES;
    116 	}
    117 	else if (dif < 0) {
    118 		if (cur_node->left)
    119 			add_node(node, cur_node->left);
    120 		else
    121 			cur_node->left = node;
    122 	} else {
    123 		if (cur_node->right)
    124 			add_node(node, cur_node->right);
    125 		else
    126 			cur_node->right = node;
    127 	}
    128 }
    129 
    130 static void
    131 free_tree(NODE *node)
    132 {
    133 	NODE *nnode;
    134 
    135 	for (; node != NULL; node = nnode) {
    136 		nnode = node->left;
    137 		if (node->right) {
    138 			if (nnode == NULL)
    139 				nnode = node->right;
    140 			else
    141 				free_tree(node->right);
    142 		}
    143 		free(node);
    144 	}
    145 }
    146