tree.c revision 97581
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 3487628Sdwmalone#if 0 3587628Sdwmalone#ifndef lint 3687628Sdwmalonestatic char sccsid[] = "@(#)tree.c 8.3 (Berkeley) 4/2/94"; 3787628Sdwmalone#endif 3887628Sdwmalone#endif 3987628Sdwmalone 4087249Smarkm#include <sys/cdefs.h> 4187249Smarkm__FBSDID("$FreeBSD: head/usr.bin/ctags/tree.c 97581 2002-05-30 11:43:20Z tjr $"); 4287249Smarkm 431590Srgrimes#include <err.h> 441590Srgrimes#include <limits.h> 451590Srgrimes#include <stdio.h> 461590Srgrimes#include <stdlib.h> 471590Srgrimes#include <string.h> 481590Srgrimes 491590Srgrimes#include "ctags.h" 501590Srgrimes 5192920Simpstatic void add_node(NODE *, NODE *); 5292920Simpstatic void free_tree(NODE *); 531590Srgrimes 541590Srgrimes/* 551590Srgrimes * pfnote -- 561590Srgrimes * enter a new node in the tree 571590Srgrimes */ 581590Srgrimesvoid 591590Srgrimespfnote(name, ln) 6087215Smarkm const char *name; 611590Srgrimes int ln; 621590Srgrimes{ 631590Srgrimes NODE *np; 641590Srgrimes char *fp; 651590Srgrimes char nbuf[MAXTOKEN]; 661590Srgrimes 671590Srgrimes /*NOSTRICT*/ 681590Srgrimes if (!(np = (NODE *)malloc(sizeof(NODE)))) { 691590Srgrimes warnx("too many entries to sort"); 701590Srgrimes put_entries(head); 711590Srgrimes free_tree(head); 721590Srgrimes /*NOSTRICT*/ 731590Srgrimes if (!(head = np = (NODE *)malloc(sizeof(NODE)))) 7487750Scharnier errx(1, "out of space"); 751590Srgrimes } 761590Srgrimes if (!xflag && !strcmp(name, "main")) { 771590Srgrimes if (!(fp = strrchr(curfile, '/'))) 781590Srgrimes fp = curfile; 791590Srgrimes else 801590Srgrimes ++fp; 8197574Stjr (void)snprintf(nbuf, sizeof(nbuf), "M%s", fp); 821590Srgrimes fp = strrchr(nbuf, '.'); 831590Srgrimes if (fp && !fp[2]) 841590Srgrimes *fp = EOS; 851590Srgrimes name = nbuf; 861590Srgrimes } 871590Srgrimes if (!(np->entry = strdup(name))) 881590Srgrimes err(1, NULL); 891590Srgrimes np->file = curfile; 901590Srgrimes np->lno = ln; 911590Srgrimes np->left = np->right = 0; 921590Srgrimes if (!(np->pat = strdup(lbuf))) 931590Srgrimes err(1, NULL); 941590Srgrimes if (!head) 951590Srgrimes head = np; 961590Srgrimes else 971590Srgrimes add_node(np, head); 981590Srgrimes} 991590Srgrimes 1001590Srgrimesstatic void 1011590Srgrimesadd_node(node, cur_node) 1021590Srgrimes NODE *node, 1031590Srgrimes *cur_node; 1041590Srgrimes{ 1051590Srgrimes int dif; 1061590Srgrimes 10797581Stjr dif = strcoll(node->entry, cur_node->entry); 1081590Srgrimes if (!dif) { 1091590Srgrimes if (node->file == cur_node->file) { 1101590Srgrimes if (!wflag) 1111590Srgrimes fprintf(stderr, "Duplicate entry in file %s, line %d: %s\nSecond entry ignored\n", node->file, lineno, node->entry); 1121590Srgrimes return; 1131590Srgrimes } 1141590Srgrimes if (!cur_node->been_warned) 1151590Srgrimes if (!wflag) 1161590Srgrimes fprintf(stderr, "Duplicate entry in files %s and %s: %s (Warning only)\n", node->file, cur_node->file, node->entry); 1171590Srgrimes cur_node->been_warned = YES; 1181590Srgrimes } 1191590Srgrimes else if (dif < 0) 1201590Srgrimes if (cur_node->left) 1211590Srgrimes add_node(node, cur_node->left); 1221590Srgrimes else 1231590Srgrimes cur_node->left = node; 1241590Srgrimes else if (cur_node->right) 1251590Srgrimes add_node(node, cur_node->right); 1261590Srgrimes else 1271590Srgrimes cur_node->right = node; 1281590Srgrimes} 1291590Srgrimes 1301590Srgrimesstatic void 1311590Srgrimesfree_tree(node) 1321590Srgrimes NODE *node; 1331590Srgrimes{ 1341590Srgrimes while (node) { 1351590Srgrimes if (node->right) 1361590Srgrimes free_tree(node->right); 1371590Srgrimes free(node); 1381590Srgrimes node = node->left; 1391590Srgrimes } 1401590Srgrimes} 141