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