home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume6 / bsearchstr / bsearchstr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  5.1 KB  |  221 lines
  1. static char Uni_id[] = "@(#)28.1";
  2. /* UNISRC_ID: @(#)bsearchstr.c    28.1    86/01/04  */
  3. /*
  4.  * Binary search routine for sorted file of strings (lines).
  5.  * Compile with -DDEBUG for standalone testing and extra output.
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <ctype.h>
  10.  
  11. #define    chNull    ('\0')
  12. #define    cpNull    ((char *) NULL)
  13.  
  14.  
  15. #ifdef DEBUG
  16. /*
  17.  * Test usage:  cmd file pattern [caseins [tellnext]]
  18.  *
  19.  * If there is a third  argument, sends caseins  == 1.
  20.  * If there is a fourth argument, sends tellnext == 1.
  21.  */
  22.  
  23. main (argc, argv)
  24.     int    argc;
  25.     char    **argv;
  26. {
  27.     FILE    *fp;
  28.     char    buf[BUFSIZ];
  29.  
  30.     fp = fopen (argv[1], "r");
  31.     printf ("==min=== ==max=== ==pos1== ==pos2== cmp match\n");
  32.     printf ("Search returns %ld\n",
  33.         bsearchstr (fp, argv[2], (argc > 3), (argc > 4)));
  34.     printf ("%s\n", fgets (buf, BUFSIZ, fp));
  35. }
  36. #endif /* DEBUG */
  37.  
  38.  
  39. /***************************************************************************
  40.  * B S E A R C H S T R
  41.  *
  42.  * Binary search a stream consisting of sorted lines of data for the first
  43.  * line that starts with the given pattern, or the next line if none and
  44.  * tellnext == 1.  Set the file location to the first byte of that line
  45.  * and return the offset.
  46.  *
  47.  * When caseins is set, takes pains not to modify the memory pointed to by
  48.  * pattern.  Uses multi-statement macros for efficiency.
  49.  *
  50.  * See bsearchstr(3) for more information.
  51.  *
  52.  * Author:  Alan Silverstein, Hewlett-Packard Fort Collins Systems Division
  53.  */
  54.  
  55. #define    LT 0
  56. #define    EQ 1
  57. #define    GT 2
  58.  
  59. #define    RETURN(value)    { if (caseins) free (pattern); return (value); }
  60. #define    SETPOS        { if (fseek (filep, pos, 0) < 0) RETURN (-2L); }
  61.  
  62. long bsearchstr (filep, pattern, caseins, tellnext)
  63.     FILE    *filep;            /* file to search       */
  64.     char    *pattern;        /* start of line to match  */
  65.     int    caseins;        /* case insensitive?       */
  66.     int    tellnext;        /* tell next if not found? */
  67. {
  68.     /* start of first line not yet compared (lower limit) */
  69.     long    min = 0;
  70.     /* start of line after last line not yet compared (upper limit) */
  71.     long    max;
  72.  
  73.      long    pos;            /* current offset in file  */
  74.      char    *patp;            /* pattern pointer       */
  75.      /* warning: this must be an int, not a char */
  76. register int    ch;            /* current char to compare */
  77. register int    cmp;            /* results of comparison   */
  78.      int    match = 0;        /* true if match found       */
  79.  
  80.      char    *malloc();
  81.  
  82. /*
  83.  * PREPARE PATTERN FOR CASE-INSENSITIVE SEARCH:
  84.  *
  85.  * Use toupper(), not tolower(), to be compatible with the actual function
  86.  * of sort -f.
  87.  */
  88.  
  89.     if (caseins)
  90.     {
  91.         int      len = strlen (pattern) + 1;    /* chars to uppercase    */
  92.         char  *cp;                /* for copying data    */
  93.         char  *cpend;            /* end of copy range    */
  94.  
  95.         if ((cp = patp = malloc (len)) == cpNull)
  96.         return (-2L);
  97.  
  98.         /* now remember to free (pattern) before returning    */
  99.         /* can use the RETURN() macro to accomplish this    */
  100.  
  101.         cpend = cp + len;
  102.  
  103.         while (cp < cpend)            /* copy chNull also         */
  104.         *cp++ = toupper (*pattern++);    /* toupper() is not a macro! */
  105.  
  106.         pattern = patp;            /* "move" to new location */
  107.     }
  108.  
  109. /*
  110.  * SET MAX TO END OF FILE (byte past last) by seeking there:
  111.  */
  112.  
  113.     if ((fseek (filep, 0L, 2) < 0) || ((max = ftell (filep)) < 0))
  114.         RETURN (-2L);
  115.  
  116. /*
  117.  * SET NEXT STARTING POSITION (where to find string and compare):
  118.  */
  119.  
  120.     while (min < max)            /* do until closure happens */
  121.     {
  122.         pos = (min + max) / 2;
  123.         SETPOS;
  124.  
  125. #ifdef DEBUG
  126.         printf ("%8ld %8ld %8ld ", min, max, pos);
  127. #endif
  128.  
  129. /*
  130.  * LOOK FOR THE NEXT END OF LINE IN THE FORWARD DIRECTION:
  131.  */
  132.  
  133.         while ((pos < max) && (getc (filep) != '\n'))
  134.         pos++;
  135.  
  136.         pos++;                /* skip newline */
  137.  
  138. /*
  139.  * If we ran into max, we are nearly done, assuming the current last line is
  140.  * not really huge compared to all the others (but this will work out OK too).
  141.  * Simply reset pos = min and check the first current line.
  142.  */
  143.  
  144.         if (pos >= max)
  145.         pos = min;
  146.  
  147. /*
  148.  * COMPARE THE CURRENT LINE TO THE PATTERN:
  149.  *
  150.  * If pattern[0] == chNull, never does the for loop, so it matches anything.
  151.  */
  152.  
  153.         SETPOS;
  154.  
  155.         for (cmp = EQ, patp = pattern; (*patp != chNull); patp++)
  156.         {
  157.         ch = caseins ? toupper (getc (filep)) : getc (filep);
  158.  
  159.         if ((ch < *patp) || (ch == '\n') || (ch == EOF))
  160.         {                /* line < pattern */
  161.             cmp = LT;
  162.             break;
  163.         }
  164.         else if (ch > *patp)        /* line > pattern */
  165.         {
  166.             cmp = GT;
  167.             break;
  168.         }
  169.         }
  170.  
  171.         match += (cmp == EQ);        /* note a match */
  172.  
  173. #ifdef DEBUG
  174.         printf ("%8ld  %c  %5d\n", pos,
  175.             ((cmp == LT) ? '<' : ((cmp == EQ) ? '=' : '>')), match);
  176. #endif
  177.         
  178. /*
  179.  * MOVE MIN OR MAX according to the results of comparison:
  180.  *
  181.  * If pattern[0] == chNull, cmp == EQ, which is "safe".
  182.  */
  183.  
  184.         if (cmp == LT)                /* min => next line */
  185.         {
  186.         min = pos + (patp - pattern);
  187.  
  188.         while ((ch != '\n') && (min < max))    /* find end */
  189.         {
  190.             ch = getc (filep);
  191.             min++;
  192.         }
  193.         min++;                    /* skip newline */
  194.         }
  195.         else                    /* max => this line */
  196.         {
  197.         max = pos;
  198.         }
  199.  
  200.     } /* while */
  201.  
  202. /*
  203.  * FINISH UP:
  204.  *
  205.  * Note that min could be one too large if the last line is unterminated
  206.  * and less than pattern, so we use max instead.
  207.  */
  208.  
  209.     if (match || tellnext)            /* success */
  210.     {
  211.         pos = max;
  212.         SETPOS;
  213.         RETURN (pos);
  214.     }
  215.     else                    /* failure */
  216.     {
  217.         RETURN (-1L);
  218.     }
  219.  
  220. } /* bsearchstr */
  221.