text: // Simple grep.  Only supports ^ . * $ operators.
  
  #include "types.h"
  #include "stat.h"
  #include "user.h"
  
  char buf[1024];
  int match(char*, char*);
  
  void
  grep(char *pattern, int fd)
  {
    int n, m;
    char *p, *q;
    
    m = 0;
    while((n = read(fd, buf+m, sizeof(buf)-m)) > 0){
      m += n;
      p = buf;
      while((q = strchr(p, '\n')) != 0){
        *q = 0;
        if(match(pattern, p)){
          *q = '\n';
          write(1, p, q+1 - p);
        }
        p = q+1;
      }
      if(p == buf)
        m = 0;
      if(m > 0){
        m -= p - buf;
        memmove(buf, p, m);
      }
    }
  }
  
  int
  main(int argc, char *argv[])
  {
    int fd, i;
    char *pattern;
    
    if(argc <= 1){
      printf(2, "usage: grep pattern [file ...]\n");
      exit(0);
    }
    pattern = argv[1];
    
    if(argc <= 2){
      grep(pattern, 0);
      exit(0);
    }
  
    for(i = 2; i < argc; i++){
      if((fd = open(argv[i], 0)) < 0){
        printf(1, "grep: cannot open %s\n", argv[i]);
        exit(1);
      }
      grep(pattern, fd);
      close(fd);
    }
    exit(0);
  }
  
  // Regexp matcher from Kernighan & Pike,
  // The Practice of Programming, Chapter 9.
  
  int matchhere(char*, char*);
  int matchstar(int, char*, char*);
  
  int
  match(char *re, char *text)
  {
    if(re[0] == '^')
      return matchhere(re+1, text);
    do{  // must look at empty string
      if(matchhere(re, text))
        return 1;
    }while(*text++ != '\0');
    return 0;
  }
  
  // matchhere: search for re at beginning of text
  int matchhere(char *re, char *text)
  {
    if(re[0] == '\0')
      return 1;
    if(re[1] == '*')
      return matchstar(re[0], re+2, text);
    if(re[0] == '$' && re[1] == '\0')
      return *text == '\0';
    if(*text!='\0' && (re[0]=='.' || re[0]==*text))
      return matchhere(re+1, text+1);
    return 0;
  }
  
  // matchstar: search for c*re at beginning of text
  int matchstar(int c, char *re, char *text)
  {
    do{  // a * matches zero or more instances
      if(matchhere(re, text))
        return 1;
    }while(*text!='\0' && (*text++==c || c=='.'));
    return 0;
  }
  
  