19b50d902SRodney W. Grimes /* 29b50d902SRodney W. Grimes * Copyright (c) 1987, 1993, 1994 39b50d902SRodney W. Grimes * The Regents of the University of California. All rights reserved. 49b50d902SRodney W. Grimes * 59b50d902SRodney W. Grimes * Redistribution and use in source and binary forms, with or without 69b50d902SRodney W. Grimes * modification, are permitted provided that the following conditions 79b50d902SRodney W. Grimes * are met: 89b50d902SRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 99b50d902SRodney W. Grimes * notice, this list of conditions and the following disclaimer. 109b50d902SRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 119b50d902SRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 129b50d902SRodney W. Grimes * documentation and/or other materials provided with the distribution. 139b50d902SRodney W. Grimes * 3. All advertising materials mentioning features or use of this software 149b50d902SRodney W. Grimes * must display the following acknowledgement: 159b50d902SRodney W. Grimes * This product includes software developed by the University of 169b50d902SRodney W. Grimes * California, Berkeley and its contributors. 179b50d902SRodney W. Grimes * 4. Neither the name of the University nor the names of its contributors 189b50d902SRodney W. Grimes * may be used to endorse or promote products derived from this software 199b50d902SRodney W. Grimes * without specific prior written permission. 209b50d902SRodney W. Grimes * 219b50d902SRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 229b50d902SRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 239b50d902SRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 249b50d902SRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 259b50d902SRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 269b50d902SRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 279b50d902SRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 289b50d902SRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 299b50d902SRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 309b50d902SRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 319b50d902SRodney W. Grimes * SUCH DAMAGE. 329b50d902SRodney W. Grimes */ 339b50d902SRodney W. Grimes 349f5b04e9SDavid Malone #if 0 359b50d902SRodney W. Grimes #ifndef lint 369f5b04e9SDavid Malone static char sccsid[] = "@(#)tree.c 8.3 (Berkeley) 4/2/94"; 371ac49cd8SMike Heffner #endif 389f5b04e9SDavid Malone #endif 399f5b04e9SDavid Malone 409f5b04e9SDavid Malone #include <sys/cdefs.h> 419f5b04e9SDavid Malone __FBSDID("$FreeBSD$"); 429b50d902SRodney W. Grimes 439b50d902SRodney W. Grimes #include <err.h> 449b50d902SRodney W. Grimes #include <limits.h> 459b50d902SRodney W. Grimes #include <stdio.h> 469b50d902SRodney W. Grimes #include <stdlib.h> 479b50d902SRodney W. Grimes #include <string.h> 489b50d902SRodney W. Grimes 499b50d902SRodney W. Grimes #include "ctags.h" 509b50d902SRodney W. Grimes 51f1bb2cd2SWarner Losh static void add_node(NODE *, NODE *); 52f1bb2cd2SWarner Losh static void free_tree(NODE *); 539b50d902SRodney W. Grimes 549b50d902SRodney W. Grimes /* 559b50d902SRodney W. Grimes * pfnote -- 569b50d902SRodney W. Grimes * enter a new node in the tree 579b50d902SRodney W. Grimes */ 589b50d902SRodney W. Grimes void 599b50d902SRodney W. Grimes pfnote(name, ln) 60acd1ad88SMark Murray const char *name; 619b50d902SRodney W. Grimes int ln; 629b50d902SRodney W. Grimes { 639b50d902SRodney W. Grimes NODE *np; 649b50d902SRodney W. Grimes char *fp; 659b50d902SRodney W. Grimes char nbuf[MAXTOKEN]; 669b50d902SRodney W. Grimes 679b50d902SRodney W. Grimes /*NOSTRICT*/ 689b50d902SRodney W. Grimes if (!(np = (NODE *)malloc(sizeof(NODE)))) { 699b50d902SRodney W. Grimes warnx("too many entries to sort"); 709b50d902SRodney W. Grimes put_entries(head); 719b50d902SRodney W. Grimes free_tree(head); 729b50d902SRodney W. Grimes /*NOSTRICT*/ 739b50d902SRodney W. Grimes if (!(head = np = (NODE *)malloc(sizeof(NODE)))) 7493b3633bSPhilippe Charnier errx(1, "out of space"); 759b50d902SRodney W. Grimes } 769b50d902SRodney W. Grimes if (!xflag && !strcmp(name, "main")) { 779b50d902SRodney W. Grimes if (!(fp = strrchr(curfile, '/'))) 789b50d902SRodney W. Grimes fp = curfile; 799b50d902SRodney W. Grimes else 809b50d902SRodney W. Grimes ++fp; 819b50d902SRodney W. Grimes (void)sprintf(nbuf, "M%s", fp); 829b50d902SRodney W. Grimes fp = strrchr(nbuf, '.'); 839b50d902SRodney W. Grimes if (fp && !fp[2]) 849b50d902SRodney W. Grimes *fp = EOS; 859b50d902SRodney W. Grimes name = nbuf; 869b50d902SRodney W. Grimes } 879b50d902SRodney W. Grimes if (!(np->entry = strdup(name))) 889b50d902SRodney W. Grimes err(1, NULL); 899b50d902SRodney W. Grimes np->file = curfile; 909b50d902SRodney W. Grimes np->lno = ln; 919b50d902SRodney W. Grimes np->left = np->right = 0; 929b50d902SRodney W. Grimes if (!(np->pat = strdup(lbuf))) 939b50d902SRodney W. Grimes err(1, NULL); 949b50d902SRodney W. Grimes if (!head) 959b50d902SRodney W. Grimes head = np; 969b50d902SRodney W. Grimes else 979b50d902SRodney W. Grimes add_node(np, head); 989b50d902SRodney W. Grimes } 999b50d902SRodney W. Grimes 1009b50d902SRodney W. Grimes static void 1019b50d902SRodney W. Grimes add_node(node, cur_node) 1029b50d902SRodney W. Grimes NODE *node, 1039b50d902SRodney W. Grimes *cur_node; 1049b50d902SRodney W. Grimes { 1059b50d902SRodney W. Grimes int dif; 1069b50d902SRodney W. Grimes 1079b50d902SRodney W. Grimes dif = strcmp(node->entry, cur_node->entry); 1089b50d902SRodney W. Grimes if (!dif) { 1099b50d902SRodney W. Grimes if (node->file == cur_node->file) { 1109b50d902SRodney W. Grimes if (!wflag) 1119b50d902SRodney W. Grimes fprintf(stderr, "Duplicate entry in file %s, line %d: %s\nSecond entry ignored\n", node->file, lineno, node->entry); 1129b50d902SRodney W. Grimes return; 1139b50d902SRodney W. Grimes } 1149b50d902SRodney W. Grimes if (!cur_node->been_warned) 1159b50d902SRodney W. Grimes if (!wflag) 1169b50d902SRodney W. Grimes fprintf(stderr, "Duplicate entry in files %s and %s: %s (Warning only)\n", node->file, cur_node->file, node->entry); 1179b50d902SRodney W. Grimes cur_node->been_warned = YES; 1189b50d902SRodney W. Grimes } 1199b50d902SRodney W. Grimes else if (dif < 0) 1209b50d902SRodney W. Grimes if (cur_node->left) 1219b50d902SRodney W. Grimes add_node(node, cur_node->left); 1229b50d902SRodney W. Grimes else 1239b50d902SRodney W. Grimes cur_node->left = node; 1249b50d902SRodney W. Grimes else if (cur_node->right) 1259b50d902SRodney W. Grimes add_node(node, cur_node->right); 1269b50d902SRodney W. Grimes else 1279b50d902SRodney W. Grimes cur_node->right = node; 1289b50d902SRodney W. Grimes } 1299b50d902SRodney W. Grimes 1309b50d902SRodney W. Grimes static void 1319b50d902SRodney W. Grimes free_tree(node) 1329b50d902SRodney W. Grimes NODE *node; 1339b50d902SRodney W. Grimes { 1349b50d902SRodney W. Grimes while (node) { 1359b50d902SRodney W. Grimes if (node->right) 1369b50d902SRodney W. Grimes free_tree(node->right); 1379b50d902SRodney W. Grimes free(node); 1389b50d902SRodney W. Grimes node = node->left; 1399b50d902SRodney W. Grimes } 1409b50d902SRodney W. Grimes } 141