tree.c revision 1590
11590Srgrimes/* 21590Srgrimes * Copyright (c) 1987, 1993, 1994 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * Redistribution and use in source and binary forms, with or without 61590Srgrimes * modification, are permitted provided that the following conditions 71590Srgrimes * are met: 81590Srgrimes * 1. Redistributions of source code must retain the above copyright 91590Srgrimes * notice, this list of conditions and the following disclaimer. 101590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111590Srgrimes * notice, this list of conditions and the following disclaimer in the 121590Srgrimes * documentation and/or other materials provided with the distribution. 131590Srgrimes * 3. All advertising materials mentioning features or use of this software 141590Srgrimes * must display the following acknowledgement: 151590Srgrimes * This product includes software developed by the University of 161590Srgrimes * California, Berkeley and its contributors. 171590Srgrimes * 4. Neither the name of the University nor the names of its contributors 181590Srgrimes * may be used to endorse or promote products derived from this software 191590Srgrimes * without specific prior written permission. 201590Srgrimes * 211590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311590Srgrimes * SUCH DAMAGE. 321590Srgrimes */ 331590Srgrimes 341590Srgrimes#ifndef lint 351590Srgrimesstatic char sccsid[] = "@(#)tree.c 8.3 (Berkeley) 4/2/94"; 361590Srgrimes#endif /* not lint */ 371590Srgrimes 381590Srgrimes#include <err.h> 391590Srgrimes#include <limits.h> 401590Srgrimes#include <stdio.h> 411590Srgrimes#include <stdlib.h> 421590Srgrimes#include <string.h> 431590Srgrimes 441590Srgrimes#include "ctags.h" 451590Srgrimes 461590Srgrimesstatic void add_node __P((NODE *, NODE *)); 471590Srgrimesstatic void free_tree __P((NODE *)); 481590Srgrimes 491590Srgrimes/* 501590Srgrimes * pfnote -- 511590Srgrimes * enter a new node in the tree 521590Srgrimes */ 531590Srgrimesvoid 541590Srgrimespfnote(name, ln) 551590Srgrimes char *name; 561590Srgrimes int ln; 571590Srgrimes{ 581590Srgrimes NODE *np; 591590Srgrimes char *fp; 601590Srgrimes char nbuf[MAXTOKEN]; 611590Srgrimes 621590Srgrimes /*NOSTRICT*/ 631590Srgrimes if (!(np = (NODE *)malloc(sizeof(NODE)))) { 641590Srgrimes warnx("too many entries to sort"); 651590Srgrimes put_entries(head); 661590Srgrimes free_tree(head); 671590Srgrimes /*NOSTRICT*/ 681590Srgrimes if (!(head = np = (NODE *)malloc(sizeof(NODE)))) 691590Srgrimes err(1, "out of space"); 701590Srgrimes } 711590Srgrimes if (!xflag && !strcmp(name, "main")) { 721590Srgrimes if (!(fp = strrchr(curfile, '/'))) 731590Srgrimes fp = curfile; 741590Srgrimes else 751590Srgrimes ++fp; 761590Srgrimes (void)sprintf(nbuf, "M%s", fp); 771590Srgrimes fp = strrchr(nbuf, '.'); 781590Srgrimes if (fp && !fp[2]) 791590Srgrimes *fp = EOS; 801590Srgrimes name = nbuf; 811590Srgrimes } 821590Srgrimes if (!(np->entry = strdup(name))) 831590Srgrimes err(1, NULL); 841590Srgrimes np->file = curfile; 851590Srgrimes np->lno = ln; 861590Srgrimes np->left = np->right = 0; 871590Srgrimes if (!(np->pat = strdup(lbuf))) 881590Srgrimes err(1, NULL); 891590Srgrimes if (!head) 901590Srgrimes head = np; 911590Srgrimes else 921590Srgrimes add_node(np, head); 931590Srgrimes} 941590Srgrimes 951590Srgrimesstatic void 961590Srgrimesadd_node(node, cur_node) 971590Srgrimes NODE *node, 981590Srgrimes *cur_node; 991590Srgrimes{ 1001590Srgrimes int dif; 1011590Srgrimes 1021590Srgrimes dif = strcmp(node->entry, cur_node->entry); 1031590Srgrimes if (!dif) { 1041590Srgrimes if (node->file == cur_node->file) { 1051590Srgrimes if (!wflag) 1061590Srgrimes fprintf(stderr, "Duplicate entry in file %s, line %d: %s\nSecond entry ignored\n", node->file, lineno, node->entry); 1071590Srgrimes return; 1081590Srgrimes } 1091590Srgrimes if (!cur_node->been_warned) 1101590Srgrimes if (!wflag) 1111590Srgrimes fprintf(stderr, "Duplicate entry in files %s and %s: %s (Warning only)\n", node->file, cur_node->file, node->entry); 1121590Srgrimes cur_node->been_warned = YES; 1131590Srgrimes } 1141590Srgrimes else if (dif < 0) 1151590Srgrimes if (cur_node->left) 1161590Srgrimes add_node(node, cur_node->left); 1171590Srgrimes else 1181590Srgrimes cur_node->left = node; 1191590Srgrimes else if (cur_node->right) 1201590Srgrimes add_node(node, cur_node->right); 1211590Srgrimes else 1221590Srgrimes cur_node->right = node; 1231590Srgrimes} 1241590Srgrimes 1251590Srgrimesstatic void 1261590Srgrimesfree_tree(node) 1271590Srgrimes NODE *node; 1281590Srgrimes{ 1291590Srgrimes while (node) { 1301590Srgrimes if (node->right) 1311590Srgrimes free_tree(node->right); 1321590Srgrimes free(node); 1331590Srgrimes node = node->left; 1341590Srgrimes } 1351590Srgrimes} 136