#include <sys/types.h>
#include <dirent.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>

#define true 1
#define false 0

// Function prototypes
void search(char *file, char *path);
int isdir(char *pathname);
int match(char *file1, char *file2);

/*
 * Look for a file in the specified file hierarchy
 * Don't follow soft links
 *
 * usage: search file path
 */
int main(int argc, char *argv[]) {
  char *file = argv[1];
  char *path = argv[2];

  if(argc == 2)
    path = ".";

  if(argc != 2 && argc != 3) {
    printf("usage: search <file> {<path>}\n");
    exit(-1);
  }

  // Verify that <path> is a directory
  if(!isdir(path)) {
    printf("%s is not a directory\n");
    exit(-1);
  }

  // Get rid of any trailing / in path
  if(path[strlen(path)-1] == '/')
    path[strlen(path)-1] = 0;

  printf("Searching for \"%s\" in path \"%s\"\n", file, path);

  // Recursively search for <file> in <path>
  search(file, path);

  exit(0);
}


/*
 * Recursively search for <file> in <path>
 */
void search(char *file, char *path) {
  DIR *dent;
  struct dirent *dirent;
  char curfile[256];

  // Verify that <path> is a directory and open it
  // Open the directory
  dent = opendir(path);
  if(dent == (DIR *)-1) {
    printf("Error opening directory %\n", path);
    if(errno == EACCES)
      printf("Invalid permissions\n");
    return;
  }
  
  // For each file in the directory, see if
  // that file match <file>
  // If the file is a directory, continue the
  // search recursively, reporting all match
  while(1) {
    dirent = readdir(dent);

    // If dirent == NULL, we have read everything in the
    // directory
    if(dirent == NULL)
      break;

    // Skip . and .. 
    // and OldFiles (this part is ugly hack to avoid CATS problem)
    if(match(dirent->d_name, ".") 
       || match(dirent->d_name, "..") 
       || match(dirent->d_name, "OldFiles"))
      continue;

    // Create a full pathname for this file
    sprintf(curfile, "%s/%s", path, dirent->d_name);

    // See if it is one we are looking for
    if(match(file, dirent->d_name))
      printf("%s\n", curfile);

    // See if it is a directory, and if so, recursively
    // search it
    if(isdir(curfile))
      search(file, curfile);
  }
}


/*
 * See if the specified path is a directory
 */
int isdir(char *path) {
  int retval;
  struct stat statbuf;

  // Make sure the path exists, and is a directory
  retval = lstat(path, &statbuf);

  // If something bad happened while doing the stat
  if(retval == -1) {
    if(errno == ENOENT) 
      printf("Error: Specified path \"%s\" doesn't exist\n", path);
    else if (errno == EACCES)
      printf("Error: Invalid permissions for specified path \"%s\"\n", path);
    else
      printf("Error calling stat on \"%s\"\n", path);
    
    exit(-1);
  }

  // Is it actually a directory?
  return(S_ISDIR(statbuf.st_mode));
}


/*
 * Compare two filenames using one of 
 * several incrementally different
 * matching algorithms
 */
int match(char *file1, char *file2) {
  return match2(file1, file2);
}

/*
 * Compare two filenames
 * For now, don't use wildcards
 */
int match1(char *file1, char *file2) {
  
  // strcmp returns 0 if they are equal
  // and non-zero if they are not equal
  // We need to reverse that so we return
  // true (1) if they are equal and
  // false (0) if they are not equal

  if(strcmp(file1, file2) != 0)
    return(0);
  else
    return(1);
}

/*
 * Compare two filenames with * and ? (one of each)
 */
int match2(char *file1, char *file2) {
  int size;
  
  // Compare the plain strings
  // myindexof() returns true and size==strlen(file2) if they are equal
  if(myindexof(file1, file2, &size, 0) == 0 && size == strlen(file2))
    return(true);
  else
    return(false);
}

/*
 * Find the index of file1 in file2
 */
int myindexof(char *file1, char *file2, int *size, int right) {
  char special;
  int sindex;
  char first[256];
  char *second;
  int firstloc;
  int secondloc;
  int size1;
  int size2;
  char *ptr;
  char *ptr2;
  int stringsize;
  int index;
  int remaining;
  
#ifdef DEBUG  
  printf("Match2: file1 = %s, file2 = %s\n", file1, file2);
#endif

  // If there is a * in the string
  special = '*';
  ptr = (char *)strchr(file1, special);

  // If no *, look for a ?
  if(ptr == NULL) {
    special = '?';
    ptr = (char *)strchr(file1, special);
  }

  // If there are no wildcards
  if(ptr == NULL) {

    // Find out if file1 appears in file2
    ptr = (char *)strstr(file2, file1);

    // Find the rightmost instance of file1 in file2
    if(right)
      while((ptr2 = (char *)strstr(ptr+1, file1)) != NULL)
	ptr = ptr2;

    // If it isn't there, return -1
    if(ptr == NULL)
      return(-1);

    // If it is there, set up the return values
    stringsize = (int)strlen(file1);
    index = ptr - file2;

  } else {  // If there are wildcards

    // Figure out when the special character is
    sindex = ptr - file1;

    // If it is the first character
    if(sindex == 0) {
      // Anything at the beginning of the string matches
      firstloc = 0;
      size1 = 0;
    } else {

      // It isn't the first character
      strncpy(first, file1, sindex);
      first[sindex] = 0;

      // Recursively determine what matches the first part of the string
      firstloc = myindexof(first, file2, &size1, 0);
      if(firstloc == -1)
	return(-1);
    }

    // If the wildcare is the last character
    if(sindex == strlen(file1)-1) {
      // Anything matches at the end
      second = "";
      secondloc = 0;

      // Figure out how much of the rest of the string matches
      if(special == '*') {
	// If it's a star, any number match
	remaining = 0;
      } else {
	// If it's a ?, only on character matches
	remaining = strlen(file2) - (firstloc + size1) - 1;
      }

    } else {

      // Figure out if the the second part
      second = &file2[firstloc + size1];
      secondloc = myindexof(&file1[sindex+1], second, &size2, 1); 
      remaining = strlen(second)-(secondloc+size2);

      if(secondloc == -1)
	return(-1);

      // For ?, check to see if the second part is
      // exactly one character after the first
      if(special == '?')
	if(secondloc != 1)
	  return(-1);
    }

    // If we get here, file1 was found in file2
    stringsize = strlen(file2) - firstloc - remaining;
    index = firstloc;
  }

  // Set up the return values
  *size = stringsize;
  return(index);
}