/*
 * 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 */