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 * 4. Neither the name of the University nor the names of its contributors 141590Srgrimes * may be used to endorse or promote products derived from this software 151590Srgrimes * without specific prior written permission. 161590Srgrimes * 171590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271590Srgrimes * SUCH DAMAGE. 281590Srgrimes */ 291590Srgrimes 3087628Sdwmalone#if 0 3187628Sdwmalone#ifndef lint 3287628Sdwmalonestatic char sccsid[] = "@(#)tree.c 8.3 (Berkeley) 4/2/94"; 3387628Sdwmalone#endif 3487628Sdwmalone#endif 3587628Sdwmalone 3687249Smarkm#include <sys/cdefs.h> 3787249Smarkm__FBSDID("$FreeBSD$"); 3887249Smarkm 391590Srgrimes#include <err.h> 401590Srgrimes#include <limits.h> 411590Srgrimes#include <stdio.h> 421590Srgrimes#include <stdlib.h> 431590Srgrimes#include <string.h> 441590Srgrimes 451590Srgrimes#include "ctags.h" 461590Srgrimes 4792920Simpstatic void add_node(NODE *, NODE *); 4892920Simpstatic void free_tree(NODE *); 491590Srgrimes 501590Srgrimes/* 511590Srgrimes * pfnote -- 521590Srgrimes * enter a new node in the tree 531590Srgrimes */ 541590Srgrimesvoid 55100822Sdwmalonepfnote(const char *name, int ln) 561590Srgrimes{ 571590Srgrimes NODE *np; 581590Srgrimes char *fp; 591590Srgrimes char nbuf[MAXTOKEN]; 601590Srgrimes 611590Srgrimes /*NOSTRICT*/ 621590Srgrimes if (!(np = (NODE *)malloc(sizeof(NODE)))) { 631590Srgrimes warnx("too many entries to sort"); 641590Srgrimes put_entries(head); 651590Srgrimes free_tree(head); 661590Srgrimes /*NOSTRICT*/ 671590Srgrimes if (!(head = np = (NODE *)malloc(sizeof(NODE)))) 6887750Scharnier errx(1, "out of space"); 691590Srgrimes } 701590Srgrimes if (!xflag && !strcmp(name, "main")) { 711590Srgrimes if (!(fp = strrchr(curfile, '/'))) 721590Srgrimes fp = curfile; 731590Srgrimes else 741590Srgrimes ++fp; 7597574Stjr (void)snprintf(nbuf, sizeof(nbuf), "M%s", fp); 761590Srgrimes fp = strrchr(nbuf, '.'); 771590Srgrimes if (fp && !fp[2]) 781590Srgrimes *fp = EOS; 791590Srgrimes name = nbuf; 801590Srgrimes } 811590Srgrimes if (!(np->entry = strdup(name))) 821590Srgrimes err(1, NULL); 831590Srgrimes np->file = curfile; 841590Srgrimes np->lno = ln; 851590Srgrimes np->left = np->right = 0; 861590Srgrimes if (!(np->pat = strdup(lbuf))) 871590Srgrimes err(1, NULL); 881590Srgrimes if (!head) 891590Srgrimes head = np; 901590Srgrimes else 911590Srgrimes add_node(np, head); 921590Srgrimes} 931590Srgrimes 941590Srgrimesstatic void 95100822Sdwmaloneadd_node(NODE *node, NODE *cur_node) 961590Srgrimes{ 971590Srgrimes int dif; 981590Srgrimes 9997581Stjr dif = strcoll(node->entry, cur_node->entry); 1001590Srgrimes if (!dif) { 1011590Srgrimes if (node->file == cur_node->file) { 1021590Srgrimes if (!wflag) 1031590Srgrimes fprintf(stderr, "Duplicate entry in file %s, line %d: %s\nSecond entry ignored\n", node->file, lineno, node->entry); 1041590Srgrimes return; 1051590Srgrimes } 1061590Srgrimes if (!cur_node->been_warned) 1071590Srgrimes if (!wflag) 1081590Srgrimes fprintf(stderr, "Duplicate entry in files %s and %s: %s (Warning only)\n", node->file, cur_node->file, node->entry); 1091590Srgrimes cur_node->been_warned = YES; 1101590Srgrimes } 1111590Srgrimes else if (dif < 0) 1121590Srgrimes if (cur_node->left) 1131590Srgrimes add_node(node, cur_node->left); 1141590Srgrimes else 1151590Srgrimes cur_node->left = node; 1161590Srgrimes else if (cur_node->right) 1171590Srgrimes add_node(node, cur_node->right); 1181590Srgrimes else 1191590Srgrimes cur_node->right = node; 1201590Srgrimes} 1211590Srgrimes 1221590Srgrimesstatic void 123100822Sdwmalonefree_tree(NODE *node) 1241590Srgrimes{ 125166501Srse NODE *node_next; 1261590Srgrimes while (node) { 1271590Srgrimes if (node->right) 1281590Srgrimes free_tree(node->right); 129166501Srse node_next = node->left; 1301590Srgrimes free(node); 131166501Srse node = node_next; 1321590Srgrimes } 1331590Srgrimes} 134