Imported Upstream version 3.1.0

[debian/amanda] / ndmp-src / ndml_bstf.c

/*
 * Copyright 2000
 *      Traakan, Inc., Los Altos, CA
 *      All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice unmodified, this list of conditions, and the following
 *    disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

/*
 * Project:  NDMJOB
 * Ident:    $Id: $
 *
 * Description:
 *      Binary Search Text File (BSTF)
 *
 *      Use conventional binary search method on a sorted text
 *      file. The file MUST be sorted in ascending, lexicographic
 *      order. This is the default order of sort(1).
 */


#include "ndmlib.h"



#ifdef SELF_TEST
int     n_seek, n_align, n_line, n_getc;
#endif


#define MIN_DELTA       2048



/*
 * ndmbstf_first()
 * ndmbstf_first_with_bounds()
 *
 * Returns:
 *      <0      Error
 *         -1   EOF
 *         -2   Malformed line/file
 *         -3   fseek() to determine file size failed
 *         -4   fseek() to hop failed
 *      =0      First line found in buf[], does not match key
 *      >0      Length of first matching line in buf[]
 */

int
ndmbstf_first (
  FILE *fp,                     /* the file to search */
  char *key,                    /* what we're looking for */
  char *buf,                    /* returned line */
  unsigned max_buf)             /* maximum lenght of buf (sizeof (buf)) */
{
        return ndmbstf_first_with_bounds (fp, key, buf, max_buf, 0, 0);
}

int
ndmbstf_first_with_bounds (
  FILE *fp,                     /* the file to search */
  char *key,                    /* what we're looking for */
  char *buf,                    /* returned line */
  unsigned max_buf,             /* maximum lenght of buf (sizeof (buf)) */
  off_t lower_bound,            /* offset, to skip headers, usually 0 */
  off_t upper_bound)            /* 0->don't know, >0 limit */
{
        off_t           off;
        off_t           lower, upper;           /* bounds */
        off_t           delta;
        int             rc, buf_len;

        if (upper_bound == 0) {
                off_t   end_off;

                /*
                 * Determine the file size using fseek()/ftell()
                 */

                fseeko (fp, 0, SEEK_END);
                end_off = ftello (fp);
                if (end_off == -1)
                        return -3;
                upper_bound = end_off;
        }

        /*
         * Set lower and upper bounds of the binary search
         */
        lower = lower_bound;
        upper = upper_bound;
        for (;;) {
                /*
                 * Determine the delta (distance) between the current
                 * lower and upper bounds. If delta is small, it is more
                 * efficient to do a linear search than to continue
                 * seeking. This is because stdio will pre-read
                 * portions no matter what and fseek()ing will discard
                 * the pre-read portions. MIN_DELTA is the approximation
                 * of the stdio pre-read size. Better to just
                 * linearly process the pre-read portion in the
                 * hopes that our answer is already sitting in the
                 * stdio buffer.
                 */
                delta = upper - lower;
                if (delta <= MIN_DELTA)
                        break;

                /*
                 * Seek to the first line after the midpoint
                 * between the lower and upper bounds.
                 */

                off = lower + delta / 2;
                rc = ndmbstf_seek_and_align (fp, &off);
                if (rc < 0) {
                        if (rc == EOF) {
                                /*
                                 * Alignment found a very long line without
                                 * a \n at the end of the file. All we
                                 * can do now is try a linear search
                                 * from the current lower bound.
                                 */
                        }
                        return -4;      /* fseek() for hop failed */
                }

                /*
                 * Read the next line up into buf[].
                 */

                buf_len = ndmbstf_getline (fp, buf, max_buf);
                if (buf_len <= 0) {
                        /*
                         * EOF, or malformed line. All we can do now
                         * is try a linear search from the current
                         * lower bound.
                         */
                        break;
                }

                /*
                 * This is the crucial point.
                 *
                 *   buf[]  contains a line just read.
                 *   off    points the the line we just read.
                 *   key[]  is what we're looking for.
                 *
                 * Is the objective line (what we're trying to find)
                 * somewhere between lower..off or between off..upper.
                 */
                rc = ndmbstf_compare (key, buf);
                if (rc > 0) {
                        /* key>buf. Objective somewhere in off..upper */
                        lower = off;
                } else {
                        /*
                         * key<=buf. Objective somewhere in lower..off
                         * Notice that if key==buf, there still might
                         * be a line ==key before the one we just
                         * read. There might be hundreds of such
                         * lines. The objective is the FIRST line
                         * greater than or equal to the key.
                         * This might be it. It might not.
                         * So, keep searching.
                         */
                        upper = off;
                }
        }

        /*
         * Do an unbounded linear search begining at the
         * lower bound.
         */

        off = lower;
        rc = ndmbstf_seek_and_align (fp, &off);
        if (rc < 0) {
                if (rc == EOF) {
                        /*
                         * Alignment found a very long line without
                         * a \n at the end of the file. All we
                         * can do is give up.
                         */
                        return -2;
                }
                return -4;      /* fseek() for hop failed */
        }

        /*
         * Read the next line up into buf[].
         */
        for (;;) {
                buf_len = ndmbstf_getline (fp, buf, max_buf);

                if (buf_len <= 0) {
                        if (buf_len == EOF)
                                break;          /* at end of file */
                        return -2;
                }

                rc = ndmbstf_compare (key, buf);
                if (rc == 0) {
                        /* match */
                        return buf_len;
                }
                if (rc < 0)
                        return 0;       /* have line but it doesn't match */
        }

        return EOF;
}

int
ndmbstf_next (
  FILE *fp,                     /* the file to search */
  char *key,                    /* what we're looking for */
  char *buf,                    /* returned line */
  unsigned max_buf)             /* maximum lenght of buf (sizeof (buf)) */
{
        int             rc, buf_len;

        /*
         * Read the next line up into buf[].
         */
        buf_len = ndmbstf_getline (fp, buf, max_buf);

        if (buf_len <= 0) {
                if (buf_len == EOF)
                        return EOF;             /* at end of file */
                return -2;                      /* malformed line */
        }

        rc = ndmbstf_compare (key, buf);
        if (rc == 0) {
                /* match */
                return buf_len;
        } else {
                return 0;       /* have line but it doesn't match */
        }
}


/*
 * ndmbstr_getline()
 *
 * Returns:
 *      <0      Error
 *         -1   EOF
 *         -2   Malformed line
 *      >=0     Length of buf
 */

int
ndmbstf_getline (FILE *fp, char *buf, unsigned max_buf)
{
        char *          p = buf;
        char *          p_end = buf + max_buf - 2;
        int             c;

        while ((c = getc(fp)) != EOF) {
#ifdef SELF_TEST
                n_getc++;
#endif
                if (c == '\n')
                        break;
                if (p < p_end)
                        *p++ = c;
        }
        *p = 0;

        if (c == EOF) {
                if (p > buf)
                        return -2;      /* malformed line */
                return EOF;
        }

#ifdef SELF_TEST
        n_line++;
#endif
        return p - buf;
}

int
ndmbstf_seek_and_align (FILE *fp, off_t *off)
{
        int             c;

        if (fseeko (fp, *off, SEEK_SET) == -1) {
                return -2;
        }
#ifdef SELF_TEST
        n_seek++;
#endif

        /*
         * There is a slim chance that we're at the
         * true begining of a line. Too slim.
         * Scan forward discarding the trailing
         * portion of the line we just fseek()ed
         * to, and leave the stdio stream positioned
         * for the subsequent line. Notice
         * we keep off upated so that it reflects
         * the seek position of the stdio stream.
         */

        while ((c = getc(fp)) != EOF) {
                *off += 1;
#ifdef SELF_TEST
                n_align++;
#endif
                if (c == '\n')
                        break;
        }
        if (c == EOF) {
                /* at end of file */
                return EOF;
        }

        return 0;
}



/*
 * ndmbstf_compare()
 *
 * Given a key[] and a buf[], return whether or not they match.
 * This effectively is strncmp (key, buf, strlen(key)).
 * Because of the cost of the call to strlen(), we implement
 * it ndmbstf_compare() here with the exact semantics.
 *
 * Return values are:
 *      <0      No match, key[] less than buf[]
 *      =0      Match, the key[] is a prefix for buf[]
 *      >0      No match, key[] greater than buf[]
 */

int
ndmbstf_compare (char *key, char *buf)
{
        char *          p = key;
        char *          q = buf;

        while (*p != 0 && *p == *q) {
                p++;
                q++;
        }

        if (*p == 0)
                return 0;       /* entire key matched */
        else
                return *p - *q;
}


/*
 * ndmbstf_match()
 *
 * A simple wrapper around ndmbstf_compare() with an
 * easy-to-use return value..
 *
 * Returns:
 *      !0      match
 *      =0      no match
 */

int
ndmbstf_match (char *key, char *buf)
{
        return ndmbstf_compare (key, buf) == 0;
}




#ifdef SELF_TEST
int
main (int ac, char *av[])
{
        int             i;
        FILE *          fp;
        int             verbose = 1;
        int             total_n_match = 0;
        int             total_n_no_match = 0;
        int             total_n_error = 0;

        i = 1;
        if (i < ac && strcmp (av[i], "-q") == 0) {
                i++;
                verbose = 0;
        }

        if (ac < i+2) {
                printf ("usage: %s [-q] FILE KEY ...\n", av[0]);
                return 1;
        }

        fp = fopen (av[i], "r");
        if (!fp) {
                perror (av[i]);
                return 2;
        }

        for (i++; i < ac; i++) {
                char            buf[512];
                char *          key = av[i];
                int             n_match = 0;
                int             rc;

                rc = ndmbstf_first (fp, key, buf, sizeof buf);
                if (rc < 0) {
                        printf ("Key '%s' err=%d\n", key, rc);
                        total_n_error++;
                        continue;
                }

                if (rc == 0) {
                        printf ("Key '%s' no matches\n", key);
                        total_n_no_match++;
                        continue;
                }

                if (verbose)
                        printf ("Key '%s'\n", key);
                for (; rc > 0; rc = ndmbstf_next (fp, key, buf, sizeof buf)) {
                        n_match++;
                        if (verbose)
                                printf ("    %2d: '%s'\n", n_match, buf);
                }
                total_n_match += n_match;
        }

        fclose (fp);

        printf ("n_match=%d n_miss=%d n_error=%d\n",
                total_n_match, total_n_no_match, total_n_error);
        printf ("n_seek=%d n_align=%d n_line=%d\n", n_seek, n_align, n_line);

        return 0;
}
#endif /* SELF_TEST */