/* Copyright (c) 2002 Josha Foust (tivoweb@lightn.org) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <math.h>

#ifdef TIVO
#include <sys/types.h>
#include <stddef.h>
#include <features.h>
extern void *memrchr (__const void *__s, int __c, size_t __n);
#endif

#define CHUNK_SIZE 256 
#define MIN(x,y) (x) < (y) ? (x) : (y)
#define MAX(x,y) (x) > (y) ? (x) : (y)

int tsearch(char *map, char *searchstr, int *rc, int l, int u, int stype) {
   int cmp, mid, i, chunks;
   char *pos = NULL;
   static int ssize = 0;

   if (ssize == 0) {
      ssize = strlen(searchstr);
   }

   chunks = ((u - l)/2) + 1;
   mid = chunks - 1 + l;

   for (i = 0; i < chunks && pos==NULL; i+=CHUNK_SIZE) {
      if (mid+i < u) {
         pos = memchr(map + mid + i, '\n', MIN(u - (mid + i) - 1, CHUNK_SIZE));
      }
      if (pos == NULL) {
        pos = memrchr(map + (MAX(mid - i - CHUNK_SIZE, l)), '\n', MIN((mid - i) - l, CHUNK_SIZE));
      }
   }

#ifdef DEBUG
   printf("%d l = %6d, mid = %6d, u = %6d\n", stype, l, mid, u);
#endif


   if (pos == NULL) {
      if (l == 0 && stype != 2) {
         mid = 0;
      } else if (stype == 1) {
         *rc = u;
         return -1;
      } else if (stype == 2) {
         *rc = u;
         return 1;
      } else {
         mid = l;
      }
   } else {
     mid = (pos + 1) -  map;
   }
   *rc = mid;

   cmp = strncasecmp(searchstr, map+mid, ssize);
   if (cmp > 0 && mid == l) {
      *rc = u;
   }
   return cmp;

}

int search_index(char *map, int size, char *searchstr) {
   int c, lt, ut, match, cmp;
   int fc = 0, fl = 0, fu = 0;
   int lc = 0, ll = 0, lu = 0;
   char fstr[12];

   lt = 0;
   ut = size;

   match = 0;
   while (ut > lt) {
      switch (match) {
       case 0:
         cmp = tsearch(map, searchstr, &c, lt, ut, match);

         if (cmp == 0) {
            match = 1;
#ifdef DEBUG
            printf("Match\n");
#endif
            fl = lt;
            fu = c;
            ll = c;
            lu = ut;
         } else if (cmp > 0) {
            lt = c;
         } else {
            ut = c;
         }
	 break;
       case 1:
         cmp = tsearch(map, searchstr, &fc, fl, fu, match);

         if (cmp != 0) {
            fl = fc;
         } else {
            fu = fc;
         }
         if (fu == fl) {
            match = 2;
#ifdef DEBUG
            printf("Match 2\n");
#endif
         }
	 break;
       case 2:
         cmp = tsearch(map, searchstr, &lc, ll, lu, match);

         if (cmp < 0) {
            lu = lc;
         } else {
            ll = lc;
         }
         if (lu == ll) {
            match = 3;
#ifdef DEBUG
            printf("Match 3\n");
#endif
         }
	 break;
       default:
         sprintf(fstr, "%%%d.%ds", lu - fu, lu - fu);
#ifdef DEBUG
         printf("%d = %d - %d\n", lu - fu, lu, fu);
#endif
         printf(fstr, map + fu);
         return 0;
      }
   }
   return 0;
}

int main(int argc, char *argv[]) {
   int fd, size;
   char *map;
   struct stat st;

   if (argc <= 2) {
      printf("Usage: %s index-file search-string\n", argv[0]);
      return 1;
   }

   fd = open(argv[1], O_RDONLY);
   if (fd >= 0) {
      fstat(fd, &st);
      size = st.st_size;
      map = mmap(0, size, PROT_READ, MAP_PRIVATE, fd, 0);
      if (map == (char *)-1) {
         printf("mmap failed\n");
         return 1;
      }

      return search_index(map, size, argv[2]);

   } else {
      printf("Could not read %s\n", argv[1]);
      return 1;
   }
   return 0;
}