index.cc

早期freebsd实现

// -*- C++ -*-
/* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
     Written by James Clark ([e-mail])

This file is part of groff.

groff is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.

groff is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with groff; see the file COPYING.  If not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

#include "posix.h"
#include "lib.h"
#include "cset.h"
#include "cmap.h"
#include "errarg.h"
#include "error.h"

#include "refid.h"
#include "search.h"
#include "index.h"
#include "defs.h"

// Interface to mmap.
extern "C" {
  void *mapread(int fd, int len);
  int unmap(void *, int len);
}

const int minus_one = -1;

int verify_flag = 0;

struct word_list;

class index_search_item : public search_item {
  search_item *out_of_date_files;
  index_header header;
  char *buffer;
  void *map_addr;
  int map_len;
  tag *tags;
  int *table;
  int *lists;
  char *pool;
  char *key_buffer;
  char *filename_buffer;
  int filename_buflen;
  char **common_words_table;
  int common_words_table_size;
  const char *ignore_fields;
  time_t mtime;

  const char *do_verify();
  const int *search1(const char **pp, const char *end);
  const int *search(const char *ptr, int length, int **temp_listp);
  const char *munge_filename(const char *);
  void read_common_words_file();
  void add_out_of_date_file(int fd, const char *filename, int fid);
public:
  index_search_item(const char *, int);
  ~index_search_item();
  int load(int fd);
  search_item_iterator *make_search_item_iterator(const char *);
  int verify();
  void check_files();
  int next_filename_id() const;
  friend class index_search_item_iterator;
};

class index_search_item_iterator : public search_item_iterator {
  index_search_item *indx;
  search_item_iterator *out_of_date_files_iter;
  search_item *next_out_of_date_file;
  const int *found_list;
  int *temp_list;
  char *buf;
  int buflen;
  linear_searcher searcher;
  char *query;
  int get_tag(int tagno, const linear_searcher &, const char **, int *,
	      reference_id *);
public:
  index_search_item_iterator(index_search_item *, const char *);
  ~index_search_item_iterator();
  int next(const linear_searcher &, const char **, int *, reference_id *);
};


index_search_item::index_search_item(const char *filename, int fid)
: search_item(filename, fid), out_of_date_files(0), key_buffer(0),
  filename_buffer(0), filename_buflen(0), common_words_table(0),
  map_addr(0), map_len(0), buffer(0)
{
}

index_search_item::~index_search_item()
{
  if (buffer)
    free(buffer);
  if (map_addr) {
    if (unmap(map_addr, map_len) < 0)
      error("unmap: %1", strerror(errno));
  }
  while (out_of_date_files) {
    search_item *tem = out_of_date_files;
    out_of_date_files = out_of_date_files->next;
    delete tem;
  }
  a_delete filename_buffer;
  a_delete key_buffer;
  if (common_words_table) {
    for (int i = 0; i < common_words_table_size; i++)
      a_delete common_words_table[i];
    a_delete common_words_table;
  }
}

class file_closer {
  int *fdp;
public:
  file_closer(int &fd) : fdp(&fd) { }
  ~file_closer() { close(*fdp); }
};
  
int index_search_item::load(int fd)
{
  file_closer fd_closer(fd);	// close fd on return
  struct stat sb;
  if (fstat(fd, &sb) < 0) {
    error("can't fstat `%1': %2", name, strerror(errno));
    return 0;
  }
  if (!S_ISREG(sb.st_mode)) {
    error("`%1' is not a regular file", name);
    return 0;
  }
  mtime = sb.st_mtime;
  int size = int(sb.st_size);
  char *addr;
  map_addr = mapread(fd, size);
  if (map_addr) {
    addr = (char *)map_addr;
    map_len = size;
  }
  else {
    addr = buffer = (char *)malloc(size);
    if (buffer == 0) {
      error("can't allocate buffer for `%1'", name);
      return 0;
    }
    char *ptr = buffer;
    int bytes_to_read = size;
    while (bytes_to_read > 0) {
      int nread = read(fd, ptr, bytes_to_read);
      if (nread == 0) {
	error("unexpected EOF on `%1'", name);
	return 0;
      }
      if (nread < 0) {
	error("read error on `%1': %2", name, strerror(errno));
	return 0;
      }
      bytes_to_read -= nread;
      ptr += nread;
    }
  }
  header = *(index_header *)addr;
  if (header.magic != INDEX_MAGIC) {
    error("`%1' is not an index file: wrong magic number", name);
    return 0;
  }
  if (header.version != INDEX_VERSION) {
    error("version number in `%1' is wrong: was %2, should be %3",
	  name, header.version, INDEX_VERSION);
    return 0;
  }
  int sz = (header.tags_size * sizeof(tag)
	    + header.lists_size * sizeof(int)
	    + header.table_size * sizeof(int)
	    + header.strings_size
	    + sizeof(header));
  if (sz != size) {
    error("size of `%1' is wrong: was %2, should be %3",
	  name, size, sz);
    return 0;
  }
  tags = (tag *)(addr + sizeof(header));
  lists = (int *)(tags + header.tags_size);
  table = (int *)(lists + header.lists_size);
  pool = (char *)(table + header.table_size);
  ignore_fields = strchr(strchr(pool, '\0') + 1, '\0') + 1;
  key_buffer = new char[header.truncate];
  read_common_words_file();
  return 1;
}

const char *index_search_item::do_verify()
{
  if (tags == 0)
    return "not loaded";
  if (lists[header.lists_size - 1] >= 0)
    return "last list element not negative";
  int i;
  for (i = 0; i < header.table_size; i++) {
    int li = table[i];
    if (li >= header.lists_size)
      return "bad list index";
    if (li >= 0) {
      for (int *ptr = lists + li; *ptr >= 0; ptr++) {
	if (*ptr >= header.tags_size)
	  return "bad tag index";
	if (*ptr >= ptr[1] && ptr[1] >= 0)
	  return "list not ordered";
      }
    }
  }
  for (i = 0; i < header.tags_size; i++) {
    if (tags[i].filename_index >= header.strings_size)
      return "bad index in tags";
    if (tags[i].length < 0)
      return "bad length in tags";
    if (tags[i].start < 0)
      return "bad start in tags";
  }
  if (pool[header.strings_size - 1] != '\0')
    return "last character in pool not nul";
  return 0;
}

int index_search_item::verify()
{
  const char *reason = do_verify();
  if (!reason)
    return 1;
  error("`%1' is bad: %2", name, reason);
  return 0;
}

int index_search_item::next_filename_id() const
{
  return filename_id + header.strings_size + 1;
}

search_item_iterator *index_search_item::make_search_item_iterator(
  const char *query)
{
  return new index_search_item_iterator(this, query);
}

search_item *make_index_search_item(const char *filename, int fid)
{
  char *index_filename = new char[strlen(filename) + sizeof(INDEX_SUFFIX)];
  strcpy(index_filename, filename);
  strcat(index_filename, INDEX_SUFFIX);
  int fd = open(index_filename, O_RDONLY);
  if (fd < 0)
    return 0;
  index_search_item *item = new index_search_item(index_filename, fid);
  a_delete index_filename;
  if (!item->load(fd)) {
    close(fd);
    delete item;
    return 0;
  }
  else if (verify_flag && !item->verify()) {
    delete item;
    return 0;
  }
  else {
    item->check_files();
    return item;
  }
}


index_search_item_iterator::index_search_item_iterator(index_search_item *ind,
						       const char *q)
: indx(ind), buf(0), buflen(0), temp_list(0), query(strsave(q)),
  searcher(q, strlen(q), ind->ignore_fields, ind->header.truncate),
  out_of_date_files_iter(0), next_out_of_date_file(0)
{
  found_list = indx->search(q, strlen(q), &temp_list);
  if (!found_list) {
    found_list = &minus_one;
    warning("all keys would have been discarded in constructing index `%1'",
	    indx->name);
  }
}

index_search_item_iterator::~index_search_item_iterator()
{
  a_delete temp_list;
  a_delete buf;