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.28 1993/11/28 19:31:36 bostic Exp $ (Berkeley) $Date: 1993/11/28 19:31:36 $";
  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         TAG *tp;
 427         size_t len, maxlen;
 428         int cnt;
 429         char *name;
 430
 431         exp = EXP(sp);
 432         if ((tp = exp->tagq.tqh_first) == NULL) {
 433                 (void)ex_printf(EXCOOKIE, "No tags to display.\n");
 434                 return (0);
 435         }
 436
 437         /*
 438          * Figure out the formatting.  MNOC is the maximum
 439          * number of file name columns before we split the line.
 440          */
 441 #define MNOC    15
 442         for (maxlen = 0,
 443             tp = exp->tagq.tqh_first; tp != NULL; tp = tp->q.tqe_next) {
 444                 len = tp->frp->nlen;            /* The original name. */
 445                 name = tp->frp->name;
 446                 if (maxlen < len && len < MNOC)
 447                         maxlen = len;
 448         }
 449
 450         for (cnt = 1,
 451             tp = exp->tagq.tqh_first; tp != NULL;
 452             ++cnt, tp = tp->q.tqe_next) {
 453                 len = tp->frp->nlen;            /* The original name. */
 454                 name = tp->frp->name;
 455                 if (len > maxlen || len + tp->slen > sp->cols)
 456                         if (tp == NULL || tp->search == NULL)
 457                                 (void)ex_printf(EXCOOKIE,
 458                                     "%2d %s\n", cnt, name);
 459                         else
 460                                 (void)ex_printf(EXCOOKIE,
 461                                      "%2d %s\n** %*.*s %s\n", cnt, name,
 462                                      (int)maxlen, (int)maxlen, "", tp->search);
 463                 else
 464                         if (tp == NULL || tp->search == NULL)
 465                                 (void)ex_printf(EXCOOKIE, "%2d %*.*s\n",
 466                                     cnt, (int)maxlen, (int)len, name);
 467                         else
 468                                 (void)ex_printf(EXCOOKIE, "%2d %*.*s %s\n",
 469                                     cnt, (int)maxlen, (int)len, name,
 470                                     tp->search);
 471         }
 472         return (0);
 473 }
 474
 475 /*
 476  * ex_tagalloc --
 477  *      Create a new list of tag files.
 478  */
 479 int
 480 ex_tagalloc(sp, str)
 481         SCR *sp;
 482         char *str;
 483 {
 484         EX_PRIVATE *exp;
 485         TAGF *tp;
 486         size_t len;
 487         char *p, *t;
 488
 489         /* Free current queue. */
 490         exp = EXP(sp);
 491         while ((tp = exp->tagfq.tqh_first) != NULL)
 492                 FREETAGF(tp);
 493
 494         /* Create new queue. */
 495         for (p = t = str;; ++p) {
 496                 if (*p == '\0' || isblank(*p)) {
 497                         if ((len = p - t) > 1) {
 498                                 if ((tp = malloc(sizeof(TAGF))) == NULL ||
 499                                     (tp->name = malloc(len + 1)) == NULL) {
 500                                         if (tp != NULL)
 501                                                 FREE(tp, sizeof(TAGF));
 502                                         msgq(sp, M_SYSERR, NULL);
 503                                         return (1);
 504                                 }
 505                                 memmove(tp->name, t, len);
 506                                 tp->name[len] = '\0';
 507                                 tp->flags = 0;
 508                                 TAILQ_INSERT_TAIL(&exp->tagfq, tp, q);
 509                         }
 510                         t = p + 1;
 511                 }
 512                 if (*p == '\0')
 513                          break;
 514         }
 515         return (0);
 516 }
 517                                                 /* Free previous queue. */
 518 /*
 519  * ex_tagfree --
 520  *      Free the tags file list.
 521  */
 522 int
 523 ex_tagfree(sp)
 524         SCR *sp;
 525 {
 526         EX_PRIVATE *exp;
 527         TAG *tp;
 528         TAGF *tfp;
 529
 530         /* Free up tag information. */
 531         exp = EXP(sp);
 532         while ((tp = exp->tagq.tqh_first) != NULL)
 533                 FREETAG(tp);
 534         while ((tfp = exp->tagfq.tqh_first) != NULL)
 535                 FREETAGF(tfp);
 536         FREE(exp->tlast, strlen(exp->tlast) + 1);
 537         return (0);
 538 }
 539
 540 /*
 541  * ex_tagcopy --
 542  *      Copy a screen's tag structures.
 543  */
 544 int
 545 ex_tagcopy(orig, sp)
 546         SCR *orig, *sp;
 547 {
 548         EX_PRIVATE *oexp, *nexp;
 549         TAG *ap, *tp;
 550         TAGF *atfp, *tfp;
 551
 552         /* Copy tag stack. */
 553         oexp = EXP(orig);
 554         nexp = EXP(sp);
 555         for (ap = oexp->tagq.tqh_first; ap != NULL; ap = ap->q.tqe_next) {
 556                 if ((tp = malloc(sizeof(TAG))) == NULL)
 557                         goto nomem;
 558                 *tp = *ap;
 559                 if (ap->search != NULL &&
 560                     (tp->search = strdup(ap->search)) == NULL)
 561                         goto nomem;
 562                 TAILQ_INSERT_TAIL(&nexp->tagq, tp, q);
 563         }
 564
 565         /* Copy list of tag files. */
 566         for (atfp = oexp->tagfq.tqh_first;
 567             atfp != NULL; atfp = atfp->q.tqe_next) {
 568                 if ((tfp = malloc(sizeof(TAGF))) == NULL)
 569                         goto nomem;
 570                 *tfp = *atfp;
 571                 if ((tfp->name = strdup(atfp->name)) == NULL)
 572                         goto nomem;
 573                 TAILQ_INSERT_TAIL(&nexp->tagfq, tfp, q);
 574         }
 575
 576         /* Copy the last tag. */
 577         if (oexp->tlast != NULL &&
 578             (nexp->tlast = strdup(oexp->tlast)) == NULL) {
 579 nomem:          msgq(sp, M_SYSERR, NULL);
 580                 return (1);
 581         }
 582         return (0);
 583 }
 584
 585 /*
 586  * tag_get --
 587  *      Get a tag from the tags files.
 588  */
 589 static int
 590 tag_get(sp, tag, tagp, filep, searchp)
 591         SCR *sp;
 592         char *tag, **tagp, **filep, **searchp;
 593 {
 594         EX_PRIVATE *exp;
 595         TAGF *tfp;
 596         int dne;
 597         char *p;
 598
 599         /*
 600          * Find the tag, only display missing file messages once, and
 601          * then only if we didn't find the tag.
 602          */
 603         dne = 0;
 604         exp = EXP(sp);
 605         for (p = NULL, tfp = exp->tagfq.tqh_first;
 606             tfp != NULL && p == NULL; tfp = tfp->q.tqe_next) {
 607                 errno = 0;
 608                 F_CLR(tfp, TAGF_DNE);
 609                 if (search(sp, tfp->name, tag, &p))
 610                         if (errno == ENOENT) {
 611                                 if (!F_ISSET(tfp, TAGF_DNE_WARN)) {
 612                                         dne = 1;
 613                                         F_SET(tfp, TAGF_DNE);
 614                                 }
 615                         } else
 616                                 msgq(sp, M_SYSERR, tfp->name);
 617         }
 618
 619         if (p == NULL) {
 620                 msgq(sp, M_ERR, "%s: tag not found.", tag);
 621                 if (dne)
 622                         for (tfp = exp->tagfq.tqh_first;
 623                             tfp != NULL; tfp = tfp->q.tqe_next)
 624                                 if (F_ISSET(tfp, TAGF_DNE)) {
 625                                         errno = ENOENT;
 626                                         msgq(sp, M_SYSERR, tfp->name);
 627                                         F_SET(tfp, TAGF_DNE_WARN);
 628                                 }
 629                 return (1);
 630         }
 631
 632         /*
 633          * Set the return pointers; tagp points to the tag, and, incidentally
 634          * the allocated string, filep points to the nul-terminated file name,
 635          * searchp points to the nul-terminated search string.
 636          */
 637         for (*tagp = p; *p && !isblank(*p); ++p);
 638         if (*p == '\0')
 639                 goto malformed;
 640         for (*p++ = '\0'; isblank(*p); ++p);
 641         for (*filep = p; *p && !isblank(*p); ++p);
 642         if (*p == '\0')
 643                 goto malformed;
 644         for (*p++ = '\0'; isblank(*p); ++p);
 645         *searchp = p;
 646         if (*p == '\0') {
 647 malformed:      free(*tagp);
 648                 msgq(sp, M_ERR, "%s: corrupted tag in %s.", tag, tfp->name);
 649                 return (1);
 650         }
 651         return (0);
 652 }
 653
 654 #define EQUAL           0
 655 #define GREATER         1
 656 #define LESS            (-1)
 657
 658 /*
 659  * search --
 660  *      Search a file for a tag.
 661  */
 662 static int
 663 search(sp, name, tname, tag)
 664         SCR *sp;
 665         char *name, *tname, **tag;
 666 {
 667         struct stat sb;
 668         int fd, len;
 669         char *endp, *back, *front, *map, *p;
 670
 671         if ((fd = open(name, O_RDONLY, 0)) < 0)
 672                 return (1);
 673
 674         /*
 675          * XXX
 676          * We'd like to test if the file is too big to mmap.  Since we don't
 677          * know what size or type off_t's or size_t's are, what the largest
 678          * unsigned integral type is, or what random insanity the local C
 679          * compiler will perpetrate, doing the comparison in a portable way
 680          * is flatly impossible.  Hope that malloc fails if the file is too
 681          * large.
 682          */
 683         if (fstat(fd, &sb) || (map = mmap(NULL, (size_t)sb.st_size,
 684             PROT_READ, MAP_PRIVATE, fd, (off_t)0)) == (caddr_t)-1) {
 685                 (void)close(fd);
 686                 return (1);
 687         }
 688         front = map;
 689         back = front + sb.st_size;
 690
 691         front = binary_search(tname, front, back);
 692         front = linear_search(tname, front, back);
 693
 694         if (front == NULL || (endp = strchr(front, '\n')) == NULL) {
 695                 *tag = NULL;
 696                 goto done;
 697         }
 698
 699         len = endp - front;
 700         if ((p = malloc(len + 1)) == NULL) {
 701                 msgq(sp, M_SYSERR, NULL);
 702                 *tag = NULL;
 703                 goto done;
 704         }
 705         memmove(p, front, len);
 706         p[len] = '\0';
 707         *tag = p;
 708
 709 done:   if (munmap(map, (size_t)sb.st_size))
 710                 msgq(sp, M_SYSERR, "munmap");
 711         if (close(fd))
 712                 msgq(sp, M_SYSERR, "close");
 713         return (0);
 714 }
 715
 716 /*
 717  * Binary search for "string" in memory between "front" and "back".
 718  *
 719  * This routine is expected to return a pointer to the start of a line at
 720  * *or before* the first word matching "string".  Relaxing the constraint
 721  * this way simplifies the algorithm.
 722  *
 723  * Invariants:
 724  *      front points to the beginning of a line at or before the first
 725  *      matching string.
 726  *
 727  *      back points to the beginning of a line at or after the first
 728  *      matching line.
 729  *
 730  * Base of the Invariants.
 731  *      front = NULL;
 732  *      back = EOF;
 733  *
 734  * Advancing the Invariants:
 735  *
 736  *      p = first newline after halfway point from front to back.
 737  *
 738  *      If the string at "p" is not greater than the string to match,
 739  *      p is the new front.  Otherwise it is the new back.
 740  *
 741  * Termination:
 742  *
 743  *      The definition of the routine allows it return at any point,
 744  *      since front is always at or before the line to print.
 745  *
 746  *      In fact, it returns when the chosen "p" equals "back".  This
 747  *      implies that there exists a string is least half as long as
 748  *      (back - front), which in turn implies that a linear search will
 749  *      be no more expensive than the cost of simply printing a string or two.
 750  *
 751  *      Trying to continue with binary search at this point would be
 752  *      more trouble than it's worth.
 753  */
 754 #define SKIP_PAST_NEWLINE(p, back)      while (p < back && *p++ != '\n');
 755
 756 static char *
 757 binary_search(string, front, back)
 758         register char *string, *front, *back;
 759 {
 760         register char *p;
 761
 762         p = front + (back - front) / 2;
 763         SKIP_PAST_NEWLINE(p, back);
 764
 765         while (p != back) {
 766                 if (compare(string, p, back) == GREATER)
 767                         front = p;
 768                 else
 769                         back = p;
 770                 p = front + (back - front) / 2;
 771                 SKIP_PAST_NEWLINE(p, back);
 772         }
 773         return (front);
 774 }
 775
 776 /*
 777  * Find the first line that starts with string, linearly searching from front
 778  * to back.
 779  *
 780  * Return NULL for no such line.
 781  *
 782  * This routine assumes:
 783  *
 784  *      o front points at the first character in a line.
 785  *      o front is before or at the first line to be printed.
 786  */
 787 static char *
 788 linear_search(string, front, back)
 789         char *string, *front, *back;
 790 {
 791         while (front < back) {
 792                 switch (compare(string, front, back)) {
 793                 case EQUAL:             /* Found it. */
 794                         return (front);
 795                         break;
 796                 case LESS:              /* No such string. */
 797                         return (NULL);
 798                         break;
 799                 case GREATER:           /* Keep going. */
 800                         break;
 801                 }
 802                 SKIP_PAST_NEWLINE(front, back);
 803         }
 804         return (NULL);
 805 }
 806
 807 /*
 808  * Return LESS, GREATER, or EQUAL depending on how the string1 compares
 809  * with string2 (s1 ??? s2).
 810  *
 811  *      o Matches up to len(s1) are EQUAL.
 812  *      o Matches up to len(s2) are GREATER.
 813  *
 814  * The string "s1" is null terminated.  The string s2 is '\t', space, (or
 815  * "back") terminated.
 816  *
 817  * !!!
 818  * Reasonably modern ctags programs use tabs as separators, not spaces.
 819  * However, historic programs did use spaces, and, I got complaints.
 820  */
 821 static int
 822 compare(s1, s2, back)
 823         register char *s1, *s2, *back;
 824 {
 825         for (; *s1 && s2 < back && (*s2 != '\t' && *s2 != ' '); ++s1, ++s2)
 826                 if (*s1 != *s2)
 827                         return (*s1 < *s2 ? LESS : GREATER);
 828         return (*s1 ? GREATER : s2 < back &&
 829             (*s2 != '\t' && *s2 != ' ') ? LESS : EQUAL);
 830 }