ex/ex_tag.c

   1 /*-
   2  * Copyright (c) 1992, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * David Hitz of Auspex Systems, Inc.
   7  *
   8  * %sccs.include.redist.c%
   9  */
  10
  11 #ifndef lint
  12 static char sccsid[] = "$Id: ex_tag.c,v 8.26 1993/11/23 12:51:26 bostic Exp $ (Berkeley) $Date: 1993/11/23 12:51:26 $";
  13 #endif /* not lint */
  14
  15 #include <sys/types.h>
  16 #include <sys/mman.h>
  17 #include <sys/stat.h>
  18
  19 #include <ctype.h>
  20 #include <errno.h>
  21 #include <fcntl.h>
  22 #include <stddef.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <unistd.h>
  26
  27 #include "vi.h"
  28 #include "excmd.h"
  29 #include "tag.h"
  30
  31 static char     *binary_search __P((char *, char *, char *));
  32 static int       compare __P((char *, char *, char *));
  33 static char     *linear_search __P((char *, char *, char *));
  34 static int       search __P((SCR *, char *, char *, char **));
  35 static int       tag_get __P((SCR *, char *, char **, char **, char **));
  36
  37 /*
  38  * ex_tagfirst --
  39  *      The tag code can be entered from main, i.e. "vi -t tag".
  40  */
  41 int
  42 ex_tagfirst(sp, tagarg)
  43         SCR *sp;
  44         char *tagarg;
  45 {
  46         FREF *frp;
  47         MARK m;
  48         long tl;
  49         u_int flags;
  50         int sval;
  51         char *p, *tag, *name, *search;
  52
  53         /* Taglength may limit the number of characters. */
  54         if ((tl = O_VAL(sp, O_TAGLENGTH)) != 0 && strlen(tagarg) > tl)
  55                 tagarg[tl] = '\0';
  56
  57         /* Get the tag information. */
  58         if (tag_get(sp, tagarg, &tag, &name, &search))
  59                 return (1);
  60
  61         /* Create the file entry. */
  62         if ((frp = file_add(sp, NULL, name, 0)) == NULL)
  63                 return (1);
  64         if (file_init(sp, frp, NULL, 0))
  65                 return (1);
  66
  67         /*
  68          * !!!
  69          * Historic vi accepted a line number as well as a search
  70          * string, and people are apparently still using the format.
  71          */
  72         if (isdigit(search[0])) {
  73                 m.lno = atoi(search);
  74                 m.cno = 0;
  75         } else {
  76                 /*
  77                  * Search for the tag; cheap fallback for C functions if
  78                  * the name is the same but the arguments have changed.
  79                  */
  80                 m.lno = 1;
  81                 m.cno = 0;
  82                 flags = SEARCH_FILE | SEARCH_TAG | SEARCH_TERM;
  83                 sval = f_search(sp, sp->ep, &m, &m, search, NULL, &flags);
  84                 if (sval && (p = strrchr(search, '(')) != NULL) {
  85                         p[1] = '\0';
  86                         sval = f_search(sp, sp->ep,
  87                             &m, &m, search, NULL, &flags);
  88                 }
  89                 if (sval)
  90                         msgq(sp, M_ERR, "%s: search pattern not found.", tag);
  91         }
  92
  93         /* Set up the screen. */
  94         frp->lno = m.lno;
  95         frp->cno = m.cno;
  96         F_SET(frp, FR_CURSORSET);
  97
  98         /* Might as well make this the default tag. */
  99         if ((EXP(sp)->tlast = strdup(tagarg)) == NULL) {
 100                 msgq(sp, M_SYSERR, NULL);
 101                 return (1);
 102         }
 103         return (0);
 104 }
 105
 106 /*
 107  * ex_tagpush -- :tag [file]
 108  *      Move to a new tag.
 109  */
 110 int
 111 ex_tagpush(sp, ep, cmdp)
 112         SCR *sp;
 113         EXF *ep;
 114         EXCMDARG *cmdp;
 115 {
 116         enum {TC_CHANGE, TC_CURRENT} which;
 117         EX_PRIVATE *exp;
 118         FREF *frp;
 119         MARK m;
 120         TAG *tp;
 121         u_int flags;
 122         int sval;
 123         long tl;
 124         char *name, *p, *search, *tag;
 125
 126         exp = EXP(sp);
 127         switch (cmdp->argc) {
 128         case 1:
 129                 if (exp->tlast != NULL)
 130                         FREE(exp->tlast, strlen(exp->tlast) + 1);
 131                 if ((exp->tlast = strdup((char *)cmdp->argv[0])) == NULL) {
 132                         msgq(sp, M_SYSERR, NULL);
 133                         return (1);
 134                 }
 135                 break;
 136         case 0:
 137                 if (exp->tlast == NULL) {
 138                         msgq(sp, M_ERR, "No previous tag entered.");
 139                         return (1);
 140                 }
 141                 break;
 142         default:
 143                 abort();
 144         }
 145
 146         /* Taglength may limit the number of characters. */
 147         if ((tl = O_VAL(sp, O_TAGLENGTH)) != 0 && strlen(exp->tlast) > tl)
 148                 exp->tlast[tl] = '\0';
 149
 150         /* Get the tag information. */
 151         if (tag_get(sp, exp->tlast, &tag, &name, &search))
 152                 return (1);
 153
 154         /* Get a new FREF structure. */
 155         if ((frp = file_add(sp, sp->frp, name, 1)) == NULL) {
 156                 FREE(tag, strlen(tag));
 157                 return (1);
 158         }
 159
 160         /*
 161          * The tags stacks in nvi are a bit tricky.  The first record on the
 162          * stack is the place where we first did a tag, so it has no search
 163          * string.  The second record is the first tag, and so on.  This means
 164          * that the "current" tag is always on the stack.  Each tag contains
 165          * a file name, search string, and line/column numbers.  The search
 166          * string is only used for the first access and to display to the user.
 167          * we use the saved line/column number when returning to a file.
 168          */
 169         if ((tp = calloc(1, sizeof(TAG))) == NULL)
 170                 msgq(sp, M_SYSERR, NULL);
 171         if (exp->tagq.tqh_first == NULL) {
 172                 tp->frp = sp->frp;
 173                 tp->lno = sp->lno;
 174                 tp->cno = sp->cno;
 175                 TAILQ_INSERT_HEAD(&exp->tagq, tp, q);
 176
 177                 if ((tp = calloc(1, sizeof(TAG))) == NULL)
 178                         msgq(sp, M_SYSERR, NULL);
 179         }
 180
 181         if (tp != NULL) {
 182                 /* Copy the search pattern. */
 183                 if ((tp->search = strdup(search)) == NULL)
 184                         msgq(sp, M_SYSERR, NULL);
 185                 else
 186                         tp->slen = strlen(search);
 187
 188                 /* Save the file. */
 189                 tp->frp = frp;
 190         }
 191
 192         /* Switch to the new file. */
 193         if (sp->frp == frp)
 194                 which = TC_CURRENT;
 195         else {
 196                 MODIFY_CHECK(sp, sp->ep, F_ISSET(cmdp, E_FORCE));
 197
 198                 if (file_init(sp, frp, NULL, 0)) {
 199                         if (tp != NULL)
 200                                 FREE(tp, sizeof(TAG));
 201                         FREE(tag, strlen(tag));
 202                         return (1);
 203                 }
 204                 which = TC_CHANGE;
 205         }
 206
 207         /*
 208          * !!!
 209          * Historic vi accepted a line number as well as a search
 210          * string, and people are apparently still using the format.
 211          */
 212         if (isdigit(search[0])) {
 213                 m.lno = atoi(search);
 214                 m.cno = 0;
 215                 sval = 0;
 216         } else {
 217                 /*
 218                  * Search for the tag; cheap fallback for C functions
 219                  * if the name is the same but the arguments have changed.
 220                  */
 221                 m.lno = 1;
 222                 m.cno = 0;
 223                 flags = SEARCH_FILE | SEARCH_TAG | SEARCH_TERM;
 224                 sval = f_search(sp, sp->ep, &m, &m, search, NULL, &flags);
 225                 if (sval && (p = strrchr(search, '(')) != NULL) {
 226                         p[1] = '\0';
 227                         sval = f_search(sp, sp->ep,
 228                              &m, &m, search, NULL, &flags);
 229                 }
 230                 if (sval)
 231                         msgq(sp, M_ERR, "%s: search pattern not found.", tag);
 232         }
 233         FREE(tag, strlen(tag));
 234
 235         switch (which) {
 236         case TC_CHANGE:
 237                 frp->lno = m.lno;
 238                 frp->cno = m.cno;
 239                 F_SET(frp, FR_CURSORSET);
 240                 F_SET(sp, S_FSWITCH);
 241                 break;
 242         case TC_CURRENT:
 243                 if (sval)
 244                         return (1);
 245                 sp->lno = m.lno;
 246                 sp->cno = m.cno;
 247                 break;
 248         }
 249
 250         /* Push the tag onto the stack. */
 251         if (tp != NULL) {
 252                 tp->lno = m.lno;
 253                 tp->cno = m.cno;
 254                 TAILQ_INSERT_HEAD(&exp->tagq, tp, q);
 255         }
 256
 257         return (0);
 258 }
 259
 260 /* Free a tag or tagf structure from a queue. */
 261 #define FREETAG(tp) {                                                   \
 262         TAILQ_REMOVE(&exp->tagq, (tp), q);                              \
 263         if ((tp)->search != NULL)                                       \
 264                 FREE((tp)->search, (tp)->slen);                         \
 265         FREE((tp), sizeof(TAGF));                                       \
 266 }
 267 #define FREETAGF(tfp) {                                                 \
 268         TAILQ_REMOVE(&exp->tagfq, (tfp), q);                            \
 269         FREE((tfp)->name, strlen((tfp)->name) + 1);                     \
 270         FREE((tfp), sizeof(TAGF));                                      \
 271 }
 272
 273 /*
 274  * ex_tagpop -- :tagp[op][!] [number | file]
 275  *      Pop the tag stack.
 276  */
 277 int
 278 ex_tagpop(sp, ep, cmdp)
 279         SCR *sp;
 280         EXF *ep;
 281         EXCMDARG *cmdp;
 282 {
 283         EX_PRIVATE *exp;
 284         TAG *ntp, *tp;
 285         long off;
 286         size_t arglen;
 287         char *arg, *p, *t;
 288
 289         /* Check for an empty stack. */
 290         exp = EXP(sp);
 291         if (exp->tagq.tqh_first == NULL) {
 292                 msgq(sp, M_INFO, "The tags stack is empty.");
 293                 return (1);
 294         }
 295
 296         switch (cmdp->argc) {
 297         case 0:
 298                 /* Toss the current record. */
 299                 tp = exp->tagq.tqh_first;
 300                 FREETAG(tp);
 301                 break;
 302         case 1:
 303                 arg = cmdp->argv[0];
 304                 off = strtol(arg, &p, 10);
 305                 if (*p == '\0') {
 306                         if (off < 1)
 307                                 return (0);
 308                         while (off-- > 1) {
 309                                 tp = exp->tagq.tqh_first;
 310                                 FREETAG(tp);
 311                         }
 312                 } else {
 313                         arglen = strlen(arg);
 314                         for (tp = exp->tagq.tqh_first;
 315                             tp != NULL; tp = tp->q.tqe_next) {
 316                                 /* Use the user's original file name. */
 317                                 p = tp->frp->name;
 318                                 if ((t = strrchr(p, '/')) == NULL)
 319                                         t = p;
 320                                 else
 321                                         ++t;
 322                                 if (!strncmp(arg, t, arglen)) {
 323                                         ntp = tp;
 324                                         break;
 325                                 }
 326                         }
 327                         if (tp == NULL) {
 328                                 msgq(sp, M_ERR,
 329 "No file named %s on the tags stack; use :display to see the tags stack.",
 330                                     arg);
 331                                 return (1);
 332                         }
 333                         for (;;) {
 334                                 tp = exp->tagq.tqh_first;
 335                                 if (tp == ntp)
 336                                         break;
 337                                 FREETAG(tp);
 338                         }
 339                 }
 340                 break;
 341         default:
 342                 abort();
 343         }
 344
 345         /* If not switching files, it's easy; else do the work. */
 346         tp = exp->tagq.tqh_first;
 347         if (tp->frp == sp->frp) {
 348                 sp->lno = tp->lno;
 349                 sp->cno = tp->cno;
 350         } else {
 351                 MODIFY_CHECK(sp, ep, F_ISSET(cmdp, E_FORCE));
 352
 353                 if (file_init(sp, tp->frp, NULL, 0))
 354                         return (1);
 355
 356                 tp->frp->lno = tp->lno;
 357                 tp->frp->cno = tp->cno;
 358                 F_SET(sp->frp, FR_CURSORSET);
 359
 360                 F_SET(sp, S_FSWITCH);
 361         }
 362
 363         /* If returning to the first tag, the stack is now empty. */
 364         if (tp->q.tqe_next == NULL)
 365                 FREETAG(tp);
 366         return (0);
 367 }
 368
 369 /*
 370  * ex_tagtop -- :tagt[op][!]
 371  *      Clear the tag stack.
 372  */
 373 int
 374 ex_tagtop(sp, ep, cmdp)
 375         SCR *sp;
 376         EXF *ep;
 377         EXCMDARG *cmdp;
 378 {
 379         EX_PRIVATE *exp;
 380         TAG *tp, tmp;
 381         int found;
 382
 383         /* Pop to oldest saved information. */
 384         exp = EXP(sp);
 385         for (found = 0; (tp = exp->tagq.tqh_first) != NULL; found = 1) {
 386                 if (exp->tagq.tqh_first == NULL)
 387                         tmp = *tp;
 388                 FREETAG(tp);
 389         }
 390
 391         if (!found) {
 392                 msgq(sp, M_INFO, "The tags stack is empty.");
 393                 return (1);
 394         }
 395
 396         /* If not switching files, it's easy; else do the work. */
 397         if (tmp.frp == sp->frp) {
 398                 sp->lno = tmp.lno;
 399                 sp->cno = tmp.cno;
 400         } else {
 401                 MODIFY_CHECK(sp, sp->ep, F_ISSET(cmdp, E_FORCE));
 402
 403                 if (file_init(sp, tmp.frp, NULL, 0))
 404                         return (1);
 405
 406                 tmp.frp->lno = tmp.lno;
 407                 tmp.frp->cno = tmp.cno;
 408
 409                 F_SET(sp->frp, FR_CURSORSET);
 410
 411                 F_SET(sp, S_FSWITCH);
 412         }
 413         return (0);
 414 }
 415
 416 /*
 417  * ex_tagdisplay --
 418  *      Display the list of tags.
 419  */
 420 int
 421 ex_tagdisplay(sp, ep)
 422         SCR *sp;
 423         EXF *ep;
 424 {
 425         EX_PRIVATE *exp;
 426         FREF *frp;
 427         TAG *tp;
 428         size_t len, maxlen;
 429         int cnt;
 430         char *name;
 431
 432         exp = EXP(sp);
 433         if ((tp = exp->tagq.tqh_first) == NULL) {
 434                 (void)ex_printf(EXCOOKIE, "No tags to display.\n");
 435                 return (0);
 436         }
 437
 438         /*
 439          * Figure out the formatting.  MNOC is the maximum
 440          * number of file name columns before we split the line.
 441          */
 442 #define MNOC    15
 443         for (maxlen = 0,
 444             tp = exp->tagq.tqh_first; tp != NULL; tp = tp->q.tqe_next) {
 445                 len = tp->frp->nlen;            /* The original name. */
 446                 name = tp->frp->name;
 447                 if (maxlen < len && len < MNOC)
 448                         maxlen = len;
 449         }
 450
 451         for (cnt = 1,
 452             tp = exp->tagq.tqh_first; tp != NULL;
 453             ++cnt, tp = tp->q.tqe_next) {
 454                 len = tp->frp->nlen;            /* The original name. */
 455                 name = tp->frp->name;
 456                 if (len > maxlen || len + tp->slen > sp->cols)
 457                         if (tp == NULL || tp->search == NULL)
 458                                 (void)ex_printf(EXCOOKIE,
 459                                     "%2d %s\n", cnt, name);
 460                         else
 461                                 (void)ex_printf(EXCOOKIE,
 462                                      "%2d %s\n** %*.*s %s\n", cnt, name,
 463                                      (int)maxlen, (int)maxlen, "", tp->search);
 464                 else
 465                         if (tp == NULL || tp->search == NULL)
 466                                 (void)ex_printf(EXCOOKIE, "%2d %*.*s\n",
 467                                     cnt, (int)maxlen, (int)len, name);
 468                         else
 469                                 (void)ex_printf(EXCOOKIE, "%2d %*.*s %s\n",
 470                                     cnt, (int)maxlen, (int)len, name,
 471                                     tp->search);
 472         }
 473         return (0);
 474 }
 475
 476 /*
 477  * ex_tagalloc --
 478  *      Create a new list of tag files.
 479  */
 480 int
 481 ex_tagalloc(sp, str)
 482         SCR *sp;
 483         char *str;
 484 {
 485         EX_PRIVATE *exp;
 486         TAGF *tp;
 487         size_t len;
 488         char *p, *t;
 489
 490         /* Free current queue. */
 491         exp = EXP(sp);
 492         while ((tp = exp->tagfq.tqh_first) != NULL)
 493                 FREETAGF(tp);
 494
 495         /* Create new queue. */
 496         for (p = t = str;; ++p) {
 497                 if (*p == '\0' || isblank(*p)) {
 498                         if ((len = p - t) > 1) {
 499                                 if ((tp = malloc(sizeof(TAGF))) == NULL ||
 500                                     (tp->name = malloc(len + 1)) == NULL) {
 501                                         if (tp != NULL)
 502                                                 FREE(tp, sizeof(TAGF));
 503                                         msgq(sp, M_SYSERR, NULL);
 504                                         return (1);
 505                                 }
 506                                 memmove(tp->name, t, len);
 507                                 tp->name[len] = '\0';
 508                                 tp->flags = 0;
 509                                 TAILQ_INSERT_TAIL(&exp->tagfq, tp, q);
 510                         }
 511                         t = p + 1;
 512                 }
 513                 if (*p == '\0')
 514                          break;
 515         }
 516         return (0);
 517 }
 518                                                 /* Free previous queue. */
 519 /*
 520  * ex_tagfree --
 521  *      Free the tags file list.
 522  */
 523 int
 524 ex_tagfree(sp)
 525         SCR *sp;
 526 {
 527         EX_PRIVATE *exp;
 528         TAG *tp;
 529         TAGF *tfp;
 530
 531         /* Free up tag information. */
 532         exp = EXP(sp);
 533         while ((tp = exp->tagq.tqh_first) != NULL)
 534                 FREETAG(tp);
 535         while ((tfp = exp->tagfq.tqh_first) != NULL)
 536                 FREETAGF(tfp);
 537         FREE(exp->tlast, strlen(exp->tlast) + 1);
 538         return (0);
 539 }
 540
 541 /*
 542  * ex_tagcopy --
 543  *      Copy a screen's tag structures.
 544  */
 545 int
 546 ex_tagcopy(orig, sp)
 547         SCR *orig, *sp;
 548 {
 549         EX_PRIVATE *oexp, *nexp;
 550         TAG *ap, *tp;
 551         TAGF *atfp, *tfp;
 552
 553         /* Copy tag stack. */
 554         oexp = EXP(orig);
 555         nexp = EXP(sp);
 556         for (ap = oexp->tagq.tqh_first; ap != NULL; ap = ap->q.tqe_next) {
 557                 if ((tp = malloc(sizeof(TAG))) == NULL)
 558                         goto nomem;
 559                 *tp = *ap;
 560                 if (ap->search != NULL &&
 561                     (tp->search = strdup(ap->search)) == NULL)
 562                         goto nomem;
 563                 TAILQ_INSERT_TAIL(&nexp->tagq, tp, q);
 564         }
 565
 566         /* Copy list of tag files. */
 567         for (atfp = oexp->tagfq.tqh_first;
 568             ap != NULL; atfp = atfp->q.tqe_next) {
 569                 if ((tfp = malloc(sizeof(TAGF))) == NULL)
 570                         goto nomem;
 571                 *tfp = *atfp;
 572                 if ((tfp->name = strdup(atfp->name)) == NULL)
 573                         goto nomem;
 574                 TAILQ_INSERT_TAIL(&nexp->tagfq, tfp, q);
 575         }
 576
 577         /* Copy the last tag. */
 578         if (oexp->tlast != NULL &&
 579             (nexp->tlast = strdup(oexp->tlast)) == NULL) {
 580 nomem:          msgq(sp, M_SYSERR, NULL);
 581                 return (1);
 582         }
 583         return (0);
 584 }
 585
 586 /*
 587  * tag_get --
 588  *      Get a tag from the tags files.
 589  */
 590 static int
 591 tag_get(sp, tag, tagp, filep, searchp)
 592         SCR *sp;
 593         char *tag, **tagp, **filep, **searchp;
 594 {
 595         EX_PRIVATE *exp;
 596         TAGF *tfp;
 597         int dne;
 598         char *p;
 599
 600         /*
 601          * Find the tag, only display missing file messages once, and
 602          * then only if we didn't find the tag.
 603          */
 604         dne = 0;
 605         exp = EXP(sp);
 606         for (p = NULL, tfp = exp->tagfq.tqh_first;
 607             tfp != NULL && p == NULL; tfp = tfp->q.tqe_next) {
 608                 errno = 0;
 609                 F_CLR(tfp, TAGF_DNE);
 610                 if (search(sp, tfp->name, tag, &p))
 611                         if (errno == ENOENT) {
 612                                 if (!F_ISSET(tfp, TAGF_DNE_WARN)) {
 613                                         dne = 1;
 614                                         F_SET(tfp, TAGF_DNE);
 615                                 }
 616                         } else
 617                                 msgq(sp, M_SYSERR, tfp->name);
 618         }
 619
 620         if (p == NULL) {
 621                 msgq(sp, M_ERR, "%s: tag not found.", tag);
 622                 if (dne)
 623                         for (tfp = exp->tagfq.tqh_first;
 624                             tfp != NULL; tfp = tfp->q.tqe_next)
 625                                 if (F_ISSET(tfp, TAGF_DNE)) {
 626                                         errno = ENOENT;
 627                                         msgq(sp, M_SYSERR, tfp->name);
 628                                         F_SET(tfp, TAGF_DNE_WARN);
 629                                 }
 630                 return (1);
 631         }
 632
 633         /*
 634          * Set the return pointers; tagp points to the tag, and, incidentally
 635          * the allocated string, filep points to the nul-terminated file name,
 636          * searchp points to the nul-terminated search string.
 637          */
 638         for (*tagp = p; *p && !isblank(*p); ++p);
 639         if (*p == '\0')
 640                 goto malformed;
 641         for (*p++ = '\0'; isblank(*p); ++p);
 642         for (*filep = p; *p && !isblank(*p); ++p);
 643         if (*p == '\0')
 644                 goto malformed;
 645         for (*p++ = '\0'; isblank(*p); ++p);
 646         *searchp = p;
 647         if (*p == '\0') {
 648 malformed:      free(*tagp);
 649                 msgq(sp, M_ERR, "%s: corrupted tag in %s.", tag, tfp->name);
 650                 return (1);
 651         }
 652         return (0);
 653 }
 654
 655 #define EQUAL           0
 656 #define GREATER         1
 657 #define LESS            (-1)
 658
 659 /*
 660  * search --
 661  *      Search a file for a tag.
 662  */
 663 static int
 664 search(sp, name, tname, tag)
 665         SCR *sp;
 666         char *name, *tname, **tag;
 667 {
 668         struct stat sb;
 669         int fd, len;
 670         char *endp, *back, *front, *map, *p;
 671
 672         if ((fd = open(name, O_RDONLY, 0)) < 0)
 673                 return (1);
 674
 675         /*
 676          * XXX
 677          * We'd like to test if the file is too big to mmap.  Since we don't
 678          * know what size or type off_t's or size_t's are, what the largest
 679          * unsigned integral type is, or what random insanity the local C
 680          * compiler will perpetrate, doing the comparison in a portable way
 681          * is flatly impossible.  Hope that malloc fails if the file is too
 682          * large.
 683          */
 684         if (fstat(fd, &sb) || (map = mmap(NULL, (size_t)sb.st_size,
 685             PROT_READ, MAP_PRIVATE, fd, (off_t)0)) == (caddr_t)-1) {
 686                 (void)close(fd);
 687                 return (1);
 688         }
 689         front = map;
 690         back = front + sb.st_size;
 691
 692         front = binary_search(tname, front, back);
 693         front = linear_search(tname, front, back);
 694
 695         if (front == NULL || (endp = strchr(front, '\n')) == NULL) {
 696                 *tag = NULL;
 697                 goto done;
 698         }
 699
 700         len = endp - front;
 701         if ((p = malloc(len + 1)) == NULL) {
 702                 msgq(sp, M_SYSERR, NULL);
 703                 *tag = NULL;
 704                 goto done;
 705         }
 706         memmove(p, front, len);
 707         p[len] = '\0';
 708         *tag = p;
 709
 710 done:   if (munmap(map, (size_t)sb.st_size))
 711                 msgq(sp, M_SYSERR, "munmap");
 712         if (close(fd))
 713                 msgq(sp, M_SYSERR, "close");
 714         return (0);
 715 }
 716
 717 /*
 718  * Binary search for "string" in memory between "front" and "back".
 719  *
 720  * This routine is expected to return a pointer to the start of a line at
 721  * *or before* the first word matching "string".  Relaxing the constraint
 722  * this way simplifies the algorithm.
 723  *
 724  * Invariants:
 725  *      front points to the beginning of a line at or before the first
 726  *      matching string.
 727  *
 728  *      back points to the beginning of a line at or after the first
 729  *      matching line.
 730  *
 731  * Base of the Invariants.
 732  *      front = NULL;
 733  *      back = EOF;
 734  *
 735  * Advancing the Invariants:
 736  *
 737  *      p = first newline after halfway point from front to back.
 738  *
 739  *      If the string at "p" is not greater than the string to match,
 740  *      p is the new front.  Otherwise it is the new back.
 741  *
 742  * Termination:
 743  *
 744  *      The definition of the routine allows it return at any point,
 745  *      since front is always at or before the line to print.
 746  *
 747  *      In fact, it returns when the chosen "p" equals "back".  This
 748  *      implies that there exists a string is least half as long as
 749  *      (back - front), which in turn implies that a linear search will
 750  *      be no more expensive than the cost of simply printing a string or two.
 751  *
 752  *      Trying to continue with binary search at this point would be
 753  *      more trouble than it's worth.
 754  */
 755 #define SKIP_PAST_NEWLINE(p, back)      while (p < back && *p++ != '\n');
 756
 757 static char *
 758 binary_search(string, front, back)
 759         register char *string, *front, *back;
 760 {
 761         register char *p;
 762
 763         p = front + (back - front) / 2;
 764         SKIP_PAST_NEWLINE(p, back);
 765
 766         while (p != back) {
 767                 if (compare(string, p, back) == GREATER)
 768                         front = p;
 769                 else
 770                         back = p;
 771                 p = front + (back - front) / 2;
 772                 SKIP_PAST_NEWLINE(p, back);
 773         }
 774         return (front);
 775 }
 776
 777 /*
 778  * Find the first line that starts with string, linearly searching from front
 779  * to back.
 780  *
 781  * Return NULL for no such line.
 782  *
 783  * This routine assumes:
 784  *
 785  *      o front points at the first character in a line.
 786  *      o front is before or at the first line to be printed.
 787  */
 788 static char *
 789 linear_search(string, front, back)
 790         char *string, *front, *back;
 791 {
 792         while (front < back) {
 793                 switch (compare(string, front, back)) {
 794                 case EQUAL:             /* Found it. */
 795                         return (front);
 796                         break;
 797                 case LESS:              /* No such string. */
 798                         return (NULL);
 799                         break;
 800                 case GREATER:           /* Keep going. */
 801                         break;
 802                 }
 803                 SKIP_PAST_NEWLINE(front, back);
 804         }
 805         return (NULL);
 806 }
 807
 808 /*
 809  * Return LESS, GREATER, or EQUAL depending on how the string1 compares
 810  * with string2 (s1 ??? s2).
 811  *
 812  *      o Matches up to len(s1) are EQUAL.
 813  *      o Matches up to len(s2) are GREATER.
 814  *
 815  * The string "s1" is null terminated.  The string s2 is '\t', space, (or
 816  * "back") terminated.
 817  *
 818  * !!!
 819  * Reasonably modern ctags programs use tabs as separators, not spaces.
 820  * However, historic programs did use spaces, and, I got complaints.
 821  */
 822 static int
 823 compare(s1, s2, back)
 824         register char *s1, *s2, *back;
 825 {
 826         for (; *s1 && s2 < back && (*s2 != '\t' && *s2 != ' '); ++s1, ++s2)
 827                 if (*s1 != *s2)
 828                         return (*s1 < *s2 ? LESS : GREATER);
 829         return (*s1 ? GREATER : s2 < back &&
 830             (*s2 != '\t' && *s2 != ' ') ? LESS : EQUAL);
 831 }