upstream/0.5.2/estraier.c

/*************************************************************************************************
 * Implementation of the core API
 *                                                      Copyright (C) 2004-2005 Mikio Hirabayashi
 * This file is part of Hyper Estraier.
 * Hyper Estraier is free software; you can redistribute it and/or modify it under the terms of
 * the GNU Lesser General Public License as published by the Free Software Foundation; either
 * version 2.1 of the License or any later version.  Hyper Estraier 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 Lesser General Public
 * License for more details.
 * You should have received a copy of the GNU Lesser General Public License along with Hyper
 * Estraier; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA 02111-1307 USA.
 *************************************************************************************************/


#include "estraier.h"
#include "myconf.h"

#define ESTNUMBUFSIZ   32                /* size of a buffer for a number */
#define ESTPATHBUFSIZ  4096              /* size of a buffer for a path */
#define ESTIOBUFSIZ    8192              /* size of a buffer for I/O */
#define ESTALLOCUNIT   1024              /* unit number of memory allocation */
#define ESTMINIBNUM    31                /* bucket number of map for attributes */

#define ESTMETADBNAME  "_meta"           /* name of the meta database */
#define ESTKEYIDXNUM   "_idxnum"         /* key for the number of inverted indexes */
#define ESTKEYDSEQ     "_dseq"           /* key for the sequence for document IDs */
#define ESTKEYDNUM     "_dnum"           /* key for the number of documents */
#define ESTKEYAMODE    "_amode"          /* key for the mode of text analyzer */
#define ESTKEYMETA     "_meta"           /* key for meta data */

#define ESTIDXDBNAME   "_idx"            /* name of the inverted index */
#define ESTIDXDBLRM    77                /* records in a leaf node of the inverted index */
#define ESTIDXDBNIM    160               /* records in a non-leaf node of the inverted index */
#define ESTIDXDBLCN    16                /* number of leaf cache of the inverted index */
#define ESTIDXDBNCN    16                /* number of non-leaf cache of the inverted index */
#define ESTIDXDBRLCN   128               /* number of leaf cache of the index reader */
#define ESTIDXDBRNCN   64                /* number of non-leaf cache of the index reader */

#define ESTFWMDBNAME   "_fwm"            /* name of the database for forward matching */
#define ESTFWMDBLRM    111               /* records in a leaf node of forward matching DB */
#define ESTFWMDBNIM    110               /* records in a non-leaf node of forward matching DB */
#define ESTFWMDBLCN    32                /* number of leaf cache of forward matching DB */
#define ESTFWMDBNCN    16                /* number of non-leaf cache of forward matching DB */

#define ESTATTRDBNAME  "_attr"           /* name of the database for attrutes */
#define ESTATTRDBBNUM  122869            /* bucket number of the database for attrutes */
#define ESTATTRDBDNUM  3                 /* division number of the database for attrutes */
#define ESTATTRDBALN   -5                /* alignment of the database for attrutes */

#define ESTTEXTDBNAME  "_text"           /* name of the database of texts */
#define ESTTEXTDBBNUM  30713             /* bucket number of the database for texts */
#define ESTTEXTDBDNUM  7                 /* division number of the database for texts */
#define ESTTEXTDBALN   -5                /* alignment of the database for texts */

#define ESTLISTDBNAME  "_list"           /* name of the database of document list */
#define ESTLISTDBLRM   99                /* records in a leaf node of document list DB */
#define ESTLISTDBNIM   200               /* records in a non-leaf node of document list DB */
#define ESTLISTDBLCN   32                /* number of leaf cache of document list DB */
#define ESTLISTDBNCN   16                /* number of non-leaf cache of document list DB */

#define ESTIDXCCBNUM   524288            /* bucket number of cache for the inverted index */
#define ESTIDXCCMAX    (1048576*64)      /* max size of the cache */
#define ESTOUTCCBNUM   131072            /* bucket number of cache for deleted documents */
#define ESTKEYCCMNUM   65536             /* bucket number of cache for keys for TF-IDF */
#define ESTATTRCCMNUM  8192              /* number of cache for attributes */
#define ESTTEXTCCMNUM  1024              /* number of cache for texts */
#define ESTCCCBFREQ    10000             /* frequency of callback for flushing words */

#define ESTDIRMODE     00755             /* permission of a creating directory */
#define ESTICCHECKSIZ  32768             /* size of checking character code */
#define ESTICMISSMAX   256               /* allowance number of missing characters */
#define ESTICALLWRAT   0.001             /* allowance ratio of missing characters */
#define ESTZCOMPLEVEL  5                 /* level of compression of zlib */
#define ESTOCPOINT     10                /* point per occurrence */
#define ESTJHASHNUM    251               /* hash number for a junction */
#define ESTWORDMAXLEN  48                /* maximum length of a word */
#define ESTWORDAVGLEN  8                 /* average length of a word */
#define ESTKEYSCALW    4                 /* allowance ratio of TF-IDF for keywords */
#define ESTMEMIRATIO   1.1               /* incremental ratio of memory allocation */

#define ESTSMLRKNUM    16                /* number of keywords to get candidates */
#define ESTSMLRUNUM    1024              /* number of adopted documents for a keyword */
#define ESTSMLRNMIN    0.5               /* the minimum value for narrowing */

enum {                                   /* enumeration for character categories */
  ESTSPACECHR,                           /* space characters */
  ESTDELIMCHR,                           /* delimiter characters */
  ESTWESTALPH,                           /* west alphabets */
  ESTEASTALPH                            /* east alphabets */
};

enum {                                   /* enumeration for text analizer modes */
  ESTAMNORMAL,                           /* normal */
  ESTAMPERFNG                            /* perfect N-gram */
};

typedef struct {                         /* type of structure for a hitting object */
  int id;                                /* ID of a document */
  int score;                             /* score tuned by TF-IDF */
  char *value;                           /* value of an attribute for sorting */
} ESTSCORE;

typedef struct {                         /* type of structure for a conditional attribute */
  char *name;                            /* name */
  int nsiz;                              /* size of the name */
  char *oper;                            /* operator */
  char *val;                             /* value */
  int vsiz;                              /* size of the value */
  const char *cop;                       /* canonical operator */
  int sign;                              /* positive or negative */
  char *sval;                            /* value of small cases */
  int ssiz;                              /* size of the small value */
  time_t num;                            /* numeric value */
} ESTCATTR;

typedef struct {                         /* type of structure for a hitting object */
  const char *word;                      /* face of keyword */
  int wsiz;                              /* size of the keyword */
  int pt;                                /* score tuned by TF-IDF */
} ESTKEYSC;


/* private function prototypes */
static int est_enc_miss(const char *ptr, int size, const char *icode, const char *ocode);
static void est_normalize_text(unsigned char *utext, int size, int *sp);
static void est_canonicalize_text(unsigned char *utext, int size, int funcspc);
static int est_char_category(int c);
static int est_char_category_perfng(int c);
static char *est_phrase_from_thumb(const char *sphrase);
static void est_snippet_add_text(const unsigned char *rtext, const unsigned char *ctext,
                                 int size, int awsiz, CBDATUM *res, const CBLIST *rwords);
static int est_str_fwmatch_wide(const unsigned char *haystack, int hsiz,
                                const unsigned char *needle, int nsiz);
static ESTIDX *est_idx_open(const char *name, int omode, int dnum);
static int est_idx_close(ESTIDX *idx);
static void est_idx_set_tuning(ESTIDX *idx, int lrecmax, int nidxmax, int lcnum, int ncnum);
static void est_idx_increment(ESTIDX *idx);
static int est_idx_add(ESTIDX *idx, const char *word, int wsiz, const char *vbuf, int vsiz);
static int est_idx_out(ESTIDX *idx, const char *word, int wsiz);
static char *est_idx_get(ESTIDX *idx, const char *word, int wsiz, int *sp);
static int est_idx_vsiz(ESTIDX *idx, const char *word, int wsiz);
static int est_idx_num(ESTIDX *idx);
static int est_idx_size(ESTIDX *idx);
static int est_idx_sync(ESTIDX *idx);
static int est_idx_optimize(ESTIDX *idx);
static void est_idx_set_current(ESTIDX *idx);
static int est_db_write_meta(ESTDB *db);
static void est_db_inform(ESTDB *db, const char *info);
static int est_db_used_cache_size(ESTDB *db);
static void est_db_prepare_meta(ESTDB *db);
static CBLIST *est_phrase_terms(const char *phrase);
static int est_score_compare_by_id(const void *ap, const void *bp);
static int est_score_compare_by_score(const void *ap, const void *bp);
static int est_score_compare_by_str_asc(const void *ap, const void *bp);
static int est_score_compare_by_str_desc(const void *ap, const void *bp);
static int est_score_compare_by_num_asc(const void *ap, const void *bp);
static int est_score_compare_by_num_desc(const void *ap, const void *bp);
static ESTSCORE *est_search_uvset(ESTDB *db, int *nump, CBMAP *hints, int add);
static void est_expand_word(ESTDB *db, const char *word, CBLIST *list);
static ESTSCORE *est_search_union(ESTDB *db, const char *term, int gstep,
                                  int *nump, CBMAP *hints, int add);
static int est_narrow_scores(ESTDB *db, const CBLIST *attrs, const char *order,
                             ESTSCORE *scores, int snum);
static int est_match_attr(const char *tval, int tsiz, const char *cop, int sign,
                          const char *oval, int osiz, const char *sval, int ssiz, int onum);
static int est_keysc_compare(const void *ap, const void *bp);
static ESTSCORE *est_search_similar(ESTDB *db, CBMAP *svmap, int *nump,
                                    int knum, int unum, int tfidf, double nmin);
static CBMAP *est_phrase_vector(const char *phrase);
static CBMAP *est_get_tvmap(ESTDB *db, int id, int vnum, int tfidf);
static void est_set_svec(CBMAP *svmap, int *svec, int vnum);
static void est_set_tvec(CBMAP *svmap, CBMAP *tvmap, int *tvec, int vnum);
static double est_vec_abs(const int *vec, int vnum);
static double est_vec_iprod(const int *avec, const int *bvec, int vnum);
static double est_vec_cos(const int *avec, const int *bvec, int vnum);
static void est_random_fclose(void);


/*************************************************************************************************
 * common settings
 *************************************************************************************************/


/* version of QDBM */
const char *est_version = _EST_VERSION;


/*************************************************************************************************
 * API for document
 *************************************************************************************************/


/* Create a document object. */
ESTDOC *est_doc_new(void){
  ESTDOC *doc;
  CB_MALLOC(doc, sizeof(ESTDOC));
  doc->id = -1;
  doc->attrs = NULL;
  doc->dtexts = NULL;
  return doc;
}


/* Create a document object made from draft data. */
ESTDOC *est_doc_new_from_draft(const char *draft){
  ESTDOC *doc;
  CBLIST *lines;
  const char *line;
  char *pv;
  int i;
  assert(draft);
  doc = est_doc_new();
  lines = cbsplit(draft, -1, "\n");
  for(i = 0; i < CB_LISTNUM(lines); i++){
    line = CB_LISTVAL(lines, i, NULL);
    while(*line > '\0' && *line <= ' '){
      line++;
    }
    if(line[0] == '\0'){
      i++;
      break;
    }
    if((pv = strchr(line, '=')) != NULL){
      *(pv++) = '\0';
      est_doc_add_attr(doc, line, pv);
    }
  }
  for(; i < CB_LISTNUM(lines); i++){
    line = CB_LISTVAL(lines, i, NULL);
    if(line[0] == '\t'){
      est_doc_add_hidden_text(doc, line + 1);
    } else {
      est_doc_add_text(doc, line);
    }
  }
  cblistclose(lines);
  return doc;
}


/* Destroy a document object. */
void est_doc_delete(ESTDOC *doc){
  assert(doc);
  if(doc->dtexts) cblistclose(doc->dtexts);
  if(doc->attrs) cbmapclose(doc->attrs);
  free(doc);
}


/* Add an attribute to a document object. */
void est_doc_add_attr(ESTDOC *doc, const char *name, const char *value){
  char *rbuf, *wp;
  assert(doc && name);
  if(name[0] == '\0') return;
  if(!doc->attrs) doc->attrs = cbmapopenex(ESTMINIBNUM);
  if(value){
    rbuf = cbmemdup(value, -1);
    for(wp = rbuf; *wp != '\0'; wp++){
      if(*wp > 0 && *wp < ' ') *wp = ' ';
    }
    cbstrsqzspc(rbuf);
    cbmapputvbuf(doc->attrs, name, strlen(name), rbuf, strlen(rbuf));
  } else {
    cbmapout(doc->attrs, name, -1);
  }
}


/* Add a sentence of text to a document object. */
void est_doc_add_text(ESTDOC *doc, const char *text){
  unsigned char *utext;
  char *rtext, *wp;
  int size;
  assert(doc && text);
  while(*text > '\0' && *text <= ' '){
    text++;
  }
  if(text[0] == '\0') return;
  if(!doc->dtexts) doc->dtexts = cblistopen();
  utext = (unsigned char *)est_uconv_in(text, strlen(text), &size);
  est_normalize_text(utext, size, &size);
  rtext = est_uconv_out((char *)utext, size, NULL);
  for(wp = rtext; *wp != '\0'; wp++){
    if(*wp > 0 && *wp < ' ') *wp = ' ';
  }
  cbstrsqzspc(rtext);
  if(rtext[0] != '\0'){
    cblistpushbuf(doc->dtexts, rtext, strlen(rtext));
  } else {
    free(rtext);
  }
  free(utext);
}


/* Add a hidden sentence to a document object. */
void est_doc_add_hidden_text(ESTDOC *doc, const char *text){
  unsigned char *utext;
  char *rtext, *wp;
  int size;
  assert(doc && text);
  while(*text > '\0' && *text <= ' '){
    text++;
  }
  if(text[0] == '\0') return;
  utext = (unsigned char *)est_uconv_in(text, strlen(text), &size);
  est_normalize_text(utext, size, &size);
  rtext = est_uconv_out((char *)utext, size, NULL);
  for(wp = rtext; *wp != '\0'; wp++){
    if(*wp > 0 && *wp < ' ') *wp = ' ';
  }
  cbstrsqzspc(rtext);
  if(rtext[0] != '\0'){
    if(!doc->attrs) doc->attrs = cbmapopenex(ESTMINIBNUM);
    if(cbmapget(doc->attrs, "", 0, NULL)) cbmapputcat(doc->attrs, "", 0, " ", 1);
    cbmapputcat(doc->attrs, "", 0, rtext, -1);
  }
  free(rtext);
  free(utext);
}


/* Get the ID number of a document object. */
int est_doc_id(ESTDOC *doc){
  assert(doc);
  return doc->id;
}


/* Get a list of attribute names of a document object. */
CBLIST *est_doc_attr_names(ESTDOC *doc){
  CBLIST *names;
  const char *kbuf;
  int ksiz;
  assert(doc);
  if(!doc->attrs) return cblistopen();
  names = cblistopen();
  cbmapiterinit(doc->attrs);
  while((kbuf = cbmapiternext(doc->attrs, &ksiz)) != NULL){
    if(ksiz > 0) cblistpush(names, kbuf, ksiz);
  }
  cblistsort(names);
  return names;
}


/* Get the value of an attribute of a document object. */
const char *est_doc_attr(ESTDOC *doc, const char *name){
  assert(doc && name);
  if(!doc->attrs || name[0] == '\0') return NULL;
  return cbmapget(doc->attrs, name, -1, NULL);
}


/* Get a list of sentences of the text of a document object. */
const CBLIST *est_doc_texts(ESTDOC *doc){
  assert(doc);
  if(!doc->dtexts) doc->dtexts = cblistopen();
  return doc->dtexts;
}


/* Concatenate sentences of the text of a document object. */
char *est_doc_cat_texts(ESTDOC *doc){
  CBDATUM *datum;
  const char *elem;
  int i, size;
  if(!doc->dtexts) return cbmemdup("", 0);
  datum = cbdatumopen("", 0);
  for(i = 0; i < CB_LISTNUM(doc->dtexts); i++){
    elem = CB_LISTVAL2(doc->dtexts, i, &size);
    if(i > 0) cbdatumcat(datum, " ", 1);
    cbdatumcat(datum, elem, size);
  }
  return cbdatumtomalloc(datum, NULL);
}


/* Dump draft data of a document object. */
char *est_doc_dump_draft(ESTDOC *doc){
  CBLIST *list;
  CBDATUM *datum;
  const char *kbuf, *vbuf;
  int i, ksiz, vsiz;
  assert(doc);
  datum = cbdatumopen("", 0);
  if(doc->attrs){
    list = est_doc_attr_names(doc);
    for(i = 0; i < CB_LISTNUM(list); i++){
      kbuf = CB_LISTVAL2(list, i, &ksiz);
      vbuf = cbmapget(doc->attrs, kbuf, ksiz, &vsiz);
      cbdatumcat(datum, kbuf, ksiz);
      cbdatumcat(datum, "=", 1);
      cbdatumcat(datum, vbuf, vsiz);
      cbdatumcat(datum, "\n", 1);
    }
    cblistclose(list);
  }
  cbdatumcat(datum, "\n", 1);
  if(doc->dtexts){
    for(i = 0; i < CB_LISTNUM(doc->dtexts); i++){
      kbuf = CB_LISTVAL2(doc->dtexts, i, &ksiz);
      cbdatumcat(datum, kbuf, ksiz);
      cbdatumcat(datum, "\n", 1);
    }
  }
  if(doc->attrs && (vbuf = cbmapget(doc->attrs, "", 0, &vsiz)) != NULL){
    cbdatumcat(datum, "\t", 1);
    cbdatumcat(datum, vbuf, vsiz);
    cbdatumcat(datum, "\n", 1);
  }
  return cbdatumtomalloc(datum, NULL);
}


/* Make a snippet of the body text of a document object. */
char *est_doc_make_snippet(ESTDOC *doc, const CBLIST *words, int wwidth, int hwidth, int awidth){
  CBDATUM *res, *sbuf;
  CBMAP *counts;
  CBLIST *rwords;
  const char *text, *word, *cval;
  const unsigned char *rword;
  unsigned char *rtext, *ctext;
  int i, j, k, bi, size, wsiz, rwsiz, mywidth, awsiz, csiz;
  assert(doc && words && wwidth >= 0 && hwidth >= 0 && awidth >= 0);
  if(!doc->dtexts) doc->dtexts = cblistopen();
  res = cbdatumopen("", 0);
  rwords = cblistopen();
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = CB_LISTVAL2(words, i, &wsiz);
    if(wsiz < 1 || !strcmp(word, ESTOPUVSET)) continue;
    rtext = (unsigned char *)est_uconv_in(word, wsiz, &size);
    est_canonicalize_text(rtext, size, TRUE);
    cblistpushbuf(rwords, (char *)rtext, size);
  }
  sbuf = cbdatumopen("", 0);
  for(i = 0; i < CB_LISTNUM(doc->dtexts); i++){
    text = CB_LISTVAL2(doc->dtexts, i, &size);
    if(i > 0) cbdatumcat(sbuf, " ", 1);
    cbdatumcat(sbuf, text, size);
  }
  rtext = (unsigned char *)est_uconv_in(CB_DATUMPTR(sbuf), CB_DATUMSIZE(sbuf), &size);
  ctext = (unsigned char *)cbmemdup((char *)rtext, size);
  est_canonicalize_text(ctext, size, FALSE);
  mywidth = hwidth;
  if(CB_LISTNUM(rwords) < 1) mywidth *= 3;
  if(mywidth > wwidth) mywidth = wwidth;
  for(i = 0; i < size && mywidth > 0; i += 2){
    mywidth -= est_char_category(rtext[i] * 0x100 + rtext[i+1]) == ESTEASTALPH ? 2 : 1;
  }
  awsiz = size - i;
  if(awsiz > ESTWORDMAXLEN) awsiz = ESTWORDMAXLEN;
  est_snippet_add_text(rtext, ctext, i, awsiz, res, rwords);
  wwidth -= hwidth;
  bi = i + 2;
  cbdatumcat(res, "\n", 1);
  hwidth = 1000;
  counts = cbmapopenex(ESTMINIBNUM);
  for(i = bi; i < size && wwidth >= 0; i += 2){
    for(j = 0; j < CB_LISTNUM(rwords); j++){
      rword = (unsigned char *)CB_LISTVAL2(rwords, j, &rwsiz);
      if(est_str_fwmatch_wide(ctext + i, size - i, rword, rwsiz) > 0 &&
         (!(cval = cbmapget(counts, (char *)rword, rwsiz, &csiz)) ||
          csiz < (wwidth > awidth * 1.2 ? 2 : 1))){
        cbmapputcat(counts, (char *)rword, rwsiz, "*", 1);
        if(cbmaprnum(counts) >= CB_LISTNUM(rwords)){
          cbmapclose(counts);
          counts = cbmapopenex(ESTMINIBNUM);
        }
        mywidth = awidth / 2 + 1;
        for(k = i - 2; k >= bi && mywidth >= 0; k -= 2){
          mywidth -= est_char_category(rtext[k] * 0x100 + rtext[k+1]) == ESTEASTALPH ? 2 : 1;
        }
        bi = k;
        mywidth = awidth / 2 + 1;
        for(k = i + rwsiz + 2; k < size && mywidth >= 0; k += 2){
          mywidth -= est_char_category(rtext[k] * 0x100 + rtext[k+1]) == ESTEASTALPH ? 2 : 1;
        }
        if(k > size) k = size;
        est_snippet_add_text(rtext + bi, ctext + bi, k - bi, 0, res, rwords);
        wwidth -= awidth + rwsiz / 2;
        bi = k + 2;
        i = bi - 2;
        cbdatumcat(res, "\n", 1);
        break;
      }
    }
  }
  cbmapclose(counts);
  free(ctext);
  free(rtext);
  cbdatumclose(sbuf);
  cblistclose(rwords);
  return cbdatumtomalloc(res, NULL);
}


/* Check whether the text of a document object includes every specified words. */
int est_doc_scan_words(ESTDOC *doc, const CBLIST *words){
  CBLIST *rwords;
  const unsigned char *rp, *rword;
  const char *vbuf;
  unsigned char *rbuf;
  int i, j, vsiz, rsiz, rwsiz, hit;
  assert(doc && words);
  rwords = cblistopen();
  for(i = 0; i < CB_LISTNUM(words); i++){
    vbuf = CB_LISTVAL2(words, i, &vsiz);
    if(vsiz < 1 || !strcmp(vbuf, ESTOPUVSET)) continue;
    rbuf = (unsigned char *)est_uconv_in(vbuf, vsiz, &rsiz);
    est_canonicalize_text(rbuf, rsiz, TRUE);
    cblistpushbuf(rwords, (char *)rbuf, rsiz);
  }
  if(doc->dtexts){
    for(i = 0; i < CB_LISTNUM(doc->dtexts) && CB_LISTNUM(rwords) > 0; i++){
      vbuf = CB_LISTVAL2(doc->dtexts, i, &vsiz);
      rbuf = (unsigned char *)est_uconv_in(vbuf, vsiz, &rsiz);
      est_canonicalize_text(rbuf, rsiz, TRUE);
      for(rp = rbuf; rsiz >= 0; rp += 2, rsiz -= 2){
        for(j = 0; j < CB_LISTNUM(rwords); j++){
          rword = (unsigned char *)CB_LISTVAL2(rwords, j, &rwsiz);
          if(est_str_fwmatch_wide(rp, rsiz, rword, rwsiz)){
            free(cblistremove(rwords, j, NULL));
            j--;
          }
        }
      }
      free(rbuf);
    }
  }
  if(doc->attrs && (vbuf = cbmapget(doc->attrs, "", 0, &vsiz)) != NULL){
    rbuf = (unsigned char *)est_uconv_in(vbuf, vsiz, &rsiz);
    est_canonicalize_text(rbuf, rsiz, TRUE);
    for(rp = rbuf; rsiz >= 0; rp += 2, rsiz -= 2){
      for(i = 0; i < CB_LISTNUM(rwords); i++){
        rword = (unsigned char *)CB_LISTVAL2(rwords, i, &rwsiz);
        if(est_str_fwmatch_wide(rp, rsiz, rword, rwsiz)){
          free(cblistremove(rwords, i, NULL));
          i--;
        }
      }
    }
    free(rbuf);
  }
  hit = CB_LISTNUM(rwords) < 1;
  cblistclose(rwords);
  return hit;
}


/*************************************************************************************************
 * API for search conditions
 *************************************************************************************************/


/* Create a condition object. */
ESTCOND *est_cond_new(void){
  ESTCOND *cond;
  CB_MALLOC(cond, sizeof(ESTCOND));
  cond->phrase = NULL;
  cond->gstep = 2;
  cond->tfidf = TRUE;
  cond->simple = FALSE;
  cond->attrs = NULL;
  cond->order = NULL;
  cond->max = -1;
  cond->scfb = FALSE;
  cond->scores = NULL;
  cond->snum = 0;
  cond->opts = 0;
  return cond;
}


/* Destroy a condition object. */
void est_cond_delete(ESTCOND *cond){
  assert(cond);
  if(cond->scores) free(cond->scores);
  if(cond->order) free(cond->order);
  if(cond->attrs) cblistclose(cond->attrs);
  if(cond->phrase) free(cond->phrase);
  free(cond);
}


/* Set a search phrase to a condition object. */
void est_cond_set_phrase(ESTCOND *cond, const char *phrase){
  assert(cond && phrase);
  if(cond->phrase) free(cond->phrase);
  while(*phrase > '\0' && *phrase <= ' '){
    phrase++;
  }
  cond->phrase = cbmemdup(phrase, -1);
}


/* Add a condition of an attribute fo a condition object. */
void est_cond_add_attr(ESTCOND *cond, const char *expr){
  assert(cond && expr);
  while(*expr > '\0' && *expr <= ' '){
    expr++;
  }
  if(*expr == '\0') return;
  if(!cond->attrs) cond->attrs = cblistopen();
  cblistpush(cond->attrs, expr, -1);
}


/* Set the order of a condition object. */
void est_cond_set_order(ESTCOND *cond, const char *expr){
  assert(cond && expr);
  while(*expr > '\0' && *expr <= ' '){
    expr++;
  }
  if(*expr == '\0') return;
  if(cond->order) free(cond->order);
  cond->order = cbmemdup(expr, -1);
}


/* Set the maximum number of retrieval of a condition object. */
void est_cond_set_max(ESTCOND *cond, int max){
  assert(cond && max >= 0);
  cond->max = max;
}


/* Set options of retrieval of a condition object. */
void est_cond_set_options(ESTCOND *cond, int options){
  assert(cond);
  if(options & ESTCONDSURE) cond->gstep = 1;
  if(options & ESTCONDUSU) cond->gstep = 2;
  if(options & ESTCONDFAST) cond->gstep = 3;
  if(options & ESTCONDAGIT) cond->gstep = 4;
  if(options & ESTCONDNOIDF) cond->tfidf = FALSE;
  if(options & ESTCONDSIMPLE) cond->simple = TRUE;
  if(options & ESTCONDSCFB) cond->scfb = TRUE;
  cond->opts |= options;
}


/*************************************************************************************************
 * API for database
 *************************************************************************************************/


/* Get the string of an error code. */
const char *est_err_msg(int ecode){
  switch(ecode){
  case ESTENOERR: return "no error";
  case ESTEINVAL: return "invalid argument";
  case ESTEACCES: return "access forbidden";
  case ESTELOCK: return "lock failure";
  case ESTEDB: return "database problem";
  case ESTEIO: return "I/O problem";
  case ESTENOITEM: return "no such item";
  default: break;
  }
  return "miscellaneous";
}


/* Open a database. */
ESTDB *est_db_open(const char *name, int omode, int *ecp){
  ESTDB *db;
  DEPOT *metadb;
  ESTIDX *idxdb;
  CURIA *attrdb, *textdb;
  VILLA *fwmdb, *listdb;
  char path[ESTPATHBUFSIZ], vbuf[ESTNUMBUFSIZ];
  int domode, comode, vomode, idxnum, dseq, dnum, amode, vsiz;
  assert(name && ecp);
  *ecp = ESTENOERR;
  if((omode & ESTDBWRITER) && (omode & ESTDBCREAT) && !est_mkdir(name)){
    switch(errno){
    case EACCES:
      *ecp = ESTEACCES;
      return NULL;
    case EEXIST:
      break;
    default:
      *ecp = ESTEIO;
      return NULL;
    }
  }
  domode = DP_OREADER;
  comode = CR_OREADER;
  vomode = VL_OREADER;
  if(omode & ESTDBWRITER){
    domode = DP_OWRITER;
    comode = CR_OWRITER;
    vomode = VL_OWRITER | VL_OZCOMP;
    if(omode & ESTDBCREAT){
      domode |= DP_OCREAT;
      comode |= CR_OCREAT;
      vomode |= VL_OCREAT;
    }
    if(omode & ESTDBTRUNC){
      domode |= DP_OTRUNC;
      comode |= CR_OTRUNC;
      vomode |= VL_OTRUNC;
    }
  }
  if(omode & ESTDBNOLCK){
    domode |= DP_ONOLCK;
    comode |= CR_ONOLCK;
    vomode |= VL_ONOLCK;
  }
  if(omode & ESTDBLCKNB){
    domode |= DP_OLCKNB;
    comode |= CR_OLCKNB;
    vomode |= VL_OLCKNB;
  }
  idxnum = 0;
  dseq = 0;
  dnum = 0;
  amode = ESTAMNORMAL;
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTMETADBNAME);
  if((metadb = dpopen(path, domode, ESTMINIBNUM)) != NULL){
    if((vsiz = dpgetwb(metadb, ESTKEYIDXNUM, -1, 0, ESTNUMBUFSIZ - 1, vbuf)) > 0){
      vbuf[vsiz] = '\0';
      idxnum = atoi(vbuf);
    }
    if((vsiz = dpgetwb(metadb, ESTKEYDSEQ, -1, 0, ESTNUMBUFSIZ - 1, vbuf)) > 0){
      vbuf[vsiz] = '\0';
      dseq = atoi(vbuf);
    }
    if((vsiz = dpgetwb(metadb, ESTKEYDNUM, -1, 0, ESTNUMBUFSIZ - 1, vbuf)) > 0){
      vbuf[vsiz] = '\0';
      dnum = atoi(vbuf);
    }
    if((vsiz = dpgetwb(metadb, ESTKEYAMODE, -1, 0, ESTNUMBUFSIZ - 1, vbuf)) > 0){
      vbuf[vsiz] = '\0';
      amode = atoi(vbuf);
    } else if(omode & ESTDBPERFNG){
      amode = ESTAMPERFNG;
    }
  }
  if(!metadb){
    *ecp = (dpecode == DP_ELOCK) ? ESTELOCK : ESTEDB;
    return NULL;
  }
  if(idxnum < 1) idxnum = 1;
  if(dseq < 0) dseq = 0;
  if(dnum < 0) dnum = 0;
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTIDXDBNAME);
  idxdb = est_idx_open(path, vomode, idxnum);
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTFWMDBNAME);
  fwmdb = vlopen(path, vomode, VL_CMPLEX);
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTATTRDBNAME);
  attrdb = cropen(path, comode, ESTATTRDBBNUM, ESTATTRDBDNUM);
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTTEXTDBNAME);
  textdb = cropen(path, comode, ESTTEXTDBBNUM, ESTTEXTDBDNUM);
  sprintf(path, "%s%c%s", name, ESTPATHCHR, ESTLISTDBNAME);
  listdb = vlopen(path, vomode, VL_CMPLEX);
  if(!metadb || !idxdb || !fwmdb || !attrdb ||!textdb || !listdb){
    if(listdb) vlclose(listdb);
    if(textdb) crclose(textdb);
    if(attrdb) crclose(attrdb);
    if(fwmdb) vlclose(fwmdb);
    if(idxdb) est_idx_close(idxdb);
    dpclose(metadb);
    *ecp = ESTEDB;
    return NULL;
  }
  if(omode & ESTDBWRITER){
    crsetalign(attrdb, ESTATTRDBALN);
    crsetalign(textdb, ESTTEXTDBALN);
    est_idx_set_tuning(idxdb, ESTIDXDBLRM, ESTIDXDBNIM, ESTIDXDBLCN, ESTIDXDBNCN);
    est_idx_set_current(idxdb);
    vlsettuning(fwmdb, ESTFWMDBLRM, ESTFWMDBNIM, ESTFWMDBLCN, ESTFWMDBNCN);
    vlsettuning(listdb, ESTLISTDBLRM, ESTLISTDBNIM, ESTLISTDBLCN, ESTLISTDBNCN);
  } else {
    est_idx_set_tuning(idxdb, -1, -1, ESTIDXDBRLCN, ESTIDXDBRNCN);
    vlsettuning(fwmdb, -1, -1, ESTFWMDBLCN, ESTFWMDBNCN);
    vlsettuning(listdb, -1, -1, ESTLISTDBLCN, ESTLISTDBNCN);
  }
  CB_MALLOC(db, sizeof(ESTDB));
  db->name = cbmemdup(name, -1);
  db->metadb = metadb;
  db->idxdb = idxdb;
  db->fwmdb = fwmdb;
  db->attrdb = attrdb;
  db->textdb = textdb;
  db->listdb = listdb;
  db->ecode = ESTENOERR;
  db->fatal = FALSE;
  db->dseq = dseq;
  db->dnum = dnum;
  db->amode = amode;
  if(omode & ESTDBWRITER){
    db->idxcc = cbmapopenex(ESTIDXCCBNUM);
    db->icsiz = 0;
    db->icmax = ESTIDXCCMAX;
    db->outcc = cbmapopenex(ESTOUTCCBNUM);
  } else {
    db->idxcc = cbmapopenex(1);
    db->icsiz = 0;
    db->icmax = 0;
    db->outcc = cbmapopenex(1);
  }
  db->keycc = cbmapopenex(ESTKEYCCMNUM + 1);
  db->kcmnum = ESTKEYCCMNUM;
  db->attrcc = cbmapopenex(ESTATTRCCMNUM + 1);
  db->acmnum = ESTATTRCCMNUM;
  db->textcc = cbmapopenex(ESTTEXTCCMNUM + 1);
  db->tcmnum = ESTTEXTCCMNUM;
  db->spacc = NULL;
  db->scmnum = 0;
  db->scname = NULL;
  db->cbinfo = NULL;
  db->cbvec = NULL;
  db->vecdata = NULL;
  db->metacc = NULL;
  return db;
}


/* Close a database. */
int est_db_close(ESTDB *db, int *ecp){
  int err;
  assert(db && ecp);
  *ecp = ESTENOERR;
  err = FALSE;
  if(dpwritable(db->metadb)){
    if(!est_db_flush(db, -1) || !est_db_write_meta(db)) err = TRUE;
  }
  est_db_inform(db, "closing");
  if(db->metacc) cbmapclose(db->metacc);
  if(db->spacc){
    free(db->scname);
    cbmapclose(db->spacc);
  }
  cbmapclose(db->textcc);
  cbmapclose(db->attrcc);
  cbmapclose(db->keycc);
  cbmapclose(db->outcc);
  cbmapclose(db->idxcc);
  if(!vlclose(db->listdb)) err = TRUE;
  if(!crclose(db->textdb)) err = TRUE;
  if(!crclose(db->attrdb)) err = TRUE;
  if(!vlclose(db->fwmdb)) err = TRUE;
  if(!est_idx_close(db->idxdb)) err = TRUE;
  if(!dpclose(db->metadb)) err = TRUE;
  free(db->name);
  if(db->fatal){
    *ecp = db->ecode;
    err = TRUE;
  } else if(err){
    *ecp = ESTEDB;
  }
  free(db);
  return err ? FALSE : TRUE;
}


/* Get the last happended error code of a database. */
int est_db_error(ESTDB *db){
  assert(db);
  return db->ecode;
}


/* Check whether a database has a fatal error. */
int est_db_fatal(ESTDB *db){
  assert(db);
  return db->fatal;
}


/* Flush index words in the cache of a database. */
int est_db_flush(ESTDB *db, int max){
  CBMAP *ids;
  CBLIST *keys;
  CBDATUM *nval;
  const char *kbuf, *vbuf, *rp, *pv;
  char *tbuf;
  int i, err, ksiz, vsiz, rnum, id, tsiz;
  assert(db);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  if(cbmaprnum(db->idxcc) < 1 && cbmaprnum(db->outcc) < 1) return TRUE;
  err = FALSE;
  keys = cblistopen();
  cbmapiterinit(db->idxcc);
  while((kbuf = cbmapiternext(db->idxcc, &ksiz)) != NULL){
    cblistpush(keys, kbuf, ksiz);
  }
  rnum = CB_LISTNUM(keys);
  cblistsort(keys);
  if(max > 0){
    while(CB_LISTNUM(keys) > max){
      free(cblistpop(keys, NULL));
    }
  }
  for(i = 0; i < CB_LISTNUM(keys); i++){
    kbuf = CB_LISTVAL2(keys, i, &ksiz);
    vbuf = cbmapget(db->idxcc, kbuf, ksiz, &vsiz);
    if(!est_idx_add(db->idxdb, kbuf, ksiz, vbuf, vsiz)){
      err = TRUE;
      break;
    }
    cbmapout(db->idxcc, kbuf, ksiz);
    db->icsiz -= vsiz;
    if(i % ESTCCCBFREQ == 0) est_db_inform(db, "flushing index words");
  }
  for(i = 0; i < CB_LISTNUM(keys); i++){
    kbuf = CB_LISTVAL2(keys, i, &ksiz);
    if(!vlput(db->fwmdb, kbuf, ksiz, "", 0, VL_DKEEP) && dpecode != DP_EKEEP){
      err = TRUE;
      break;
    }
    if(i % ESTCCCBFREQ == 0) est_db_inform(db, "flushing fwm keys");
  }
  cblistclose(keys);
  if(cbmaprnum(db->idxcc) < 1){
    cbmapclose(db->idxcc);
    db->idxcc = cbmapopenex(rnum > ESTIDXCCBNUM ? rnum * 1.5 : ESTIDXCCBNUM);
  }
  if(max < 0 && cbmaprnum(db->outcc) > 0){
    ids = cbmapopen();
    keys = cblistopen();
    cbmapiterinit(db->outcc);
    while((kbuf = cbmapiternext(db->outcc, &ksiz)) != NULL){
      if(*kbuf == '\t'){
        id = atoi(kbuf + 1);
        cbmapput(ids, (char *)&id, sizeof(int), "", 0, FALSE);
      } else {
        cblistpush(keys, kbuf, ksiz);
      }
    }
    cblistsort(keys);
    for(i = 0; i < CB_LISTNUM(keys); i++){
      if(i % (ESTIDXDBLRM * 4) == 0) est_idx_set_current(db->idxdb);
      kbuf = CB_LISTVAL2(keys, i, &ksiz);
      if((tbuf = est_idx_get(db->idxdb, kbuf, ksiz, &tsiz)) != NULL){
        nval = cbdatumopen("", 0);
        rp = tbuf;
        while(rp < tbuf + tsiz){
          pv = rp;
          rp += 5;
          while(*rp != 0x0){
            rp += 2;
          }
          rp++;
          if(!cbmapget(ids, pv, sizeof(int), NULL)) cbdatumcat(nval, pv, rp - pv);
        }
        if(!est_idx_out(db->idxdb, kbuf, ksiz) && dpecode != DP_ENOITEM) err = TRUE;
        if(CB_DATUMSIZE(nval) > 0){
          if(!est_idx_add(db->idxdb, kbuf, ksiz, CB_DATUMPTR(nval), CB_DATUMSIZE(nval)))
            err = TRUE;
        } else {
          if(!vlout(db->fwmdb, kbuf, ksiz) && dpecode != DP_ENOITEM) err = TRUE;
        }
        cbdatumclose(nval);
        free(tbuf);
      }
      cbmapout(db->outcc, kbuf, ksiz);
      if(i % ESTCCCBFREQ == 0) est_db_inform(db, "cleaning dispensable keys");
    }
    rnum = cbmaprnum(ids);
    cblistclose(keys);
    cbmapclose(ids);
    cbmapclose(db->outcc);
    db->outcc = cbmapopenex(ESTOUTCCBNUM);
  }
  cbmapclose(db->keycc);
  db->keycc = cbmapopenex(ESTKEYCCMNUM + 1);
  db->kcmnum = ESTKEYCCMNUM;
  if(err){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    return FALSE;
  }
  return TRUE;
}


/* Synchronize updating contents of a database. */
int est_db_sync(ESTDB *db){
  int err;
  assert(db);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  err = FALSE;
  if(!est_db_flush(db, -1) || !est_db_write_meta(db)) err = TRUE;
  est_db_inform(db, "synchronizing the database for meta information");
  if(!dpsync(db->metadb)) err = TRUE;
  est_db_inform(db, "synchronizing the inverted index");
  if(!est_idx_sync(db->idxdb)) err = TRUE;
  est_db_inform(db, "synchronizing the database for forward matching");
  if(!vlsync(db->fwmdb)) err = TRUE;
  est_db_inform(db, "synchronizing the database for attrutes");
  if(!crsync(db->attrdb)) err = TRUE;
  est_db_inform(db, "synchronizing the database for texts");
  if(!crsync(db->textdb)) err = TRUE;
  est_db_inform(db, "synchronizing the database for document list");
  if(!vlsync(db->listdb)) err = TRUE;
  if(err){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
  }
  return err ? FALSE : TRUE;
}


/* Optimize a database. */
int est_db_optimize(ESTDB *db, int options){
  CBMAP *dmap;
  CBLIST *words;
  CBDATUM *nval;
  const char *word, *rp, *pv;
  char *kbuf, *vbuf;
  int i, err, id, ksiz, vsiz, wsiz;
  assert(db);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  if(!est_db_flush(db, -1)) return FALSE;
  err = FALSE;
  if(!(options & ESTOPTNOPURGE)){
    dmap = cbmapopenex(vlrnum(db->listdb) + 1);
    vlcurfirst(db->listdb);
    while((vbuf = vlcurval(db->listdb, NULL)) != NULL){
      id = atoi(vbuf);
      cbmapput(dmap, (char *)&id, sizeof(int), "", 0, FALSE);
      free(vbuf);
      vlcurnext(db->listdb);
    }
    words = cblistopen();
    vlcurfirst(db->fwmdb);
    while((kbuf = vlcurkey(db->fwmdb, &ksiz)) != NULL){
      cblistpushbuf(words, kbuf, ksiz);
      vlcurnext(db->fwmdb);
    }
    for(i = 0; i < CB_LISTNUM(words); i++){
      if(i % (ESTIDXDBLRM * 4) == 0) est_idx_set_current(db->idxdb);
      word = CB_LISTVAL2(words, i, &wsiz);
      if((vbuf = est_idx_get(db->idxdb, word, wsiz, &vsiz)) != NULL){
        nval = cbdatumopen("", 0);
        rp = vbuf;
        while(rp < vbuf + vsiz){
          pv = rp;
          rp += 5;
          while(*rp != 0x0){
            rp += 2;
          }
          rp++;
          if(cbmapget(dmap, pv, sizeof(int), NULL)) cbdatumcat(nval, pv, rp - pv);
        }
        if(!est_idx_out(db->idxdb, word, wsiz)) err = TRUE;
        if(CB_DATUMSIZE(nval) > 0){
          if(!est_idx_add(db->idxdb, word, wsiz, CB_DATUMPTR(nval), CB_DATUMSIZE(nval)))
            err = TRUE;
        } else {
          if(!vlout(db->fwmdb, word, wsiz)) err = TRUE;
        }
        cbdatumclose(nval);
        free(vbuf);
      } else {
        err = TRUE;
      }
      free(kbuf);
      if(i % ESTCCCBFREQ == 0) est_db_inform(db, "cleaning dispensable keys");
    }
    cblistclose(words);
    cbmapclose(dmap);
  }
  if(!(options & ESTOPTNODBOPT)){
    est_db_inform(db, "optimizing the inverted index");
    if(!est_idx_optimize(db->idxdb)) err = TRUE;
    est_db_inform(db, "optimizing the database for forward matching");
    if(!vloptimize(db->fwmdb)) err = TRUE;
    est_db_inform(db, "optimizing the database for attrutes");
    if(!croptimize(db->attrdb, -1)) err = TRUE;
    est_db_inform(db, "optimizing the database for texts");
    if(!croptimize(db->textdb, -1)) err = TRUE;
    est_db_inform(db, "optimizing the database for document list");
    if(!vloptimize(db->listdb)) err = TRUE;
  }
  if(err){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
  }
  return err ? FALSE : TRUE;
}


/* Add a document to a database. */
int est_db_put_doc(ESTDB *db, ESTDOC *doc, int options){
  CBMAP *ocmap, *fmap, *qmap;
  CBLIST *words;
  CBDATUM *ocbuf;
  const char *uri, *text, *word, *fnext, *snext, *kbuf, *vbuf;
  unsigned char junc[2], c;
  char wbuf[ESTWORDMAXLEN+3], *sbuf, *zbuf, nbuf[ESTNUMBUFSIZ];
  int i, j, id, err, wnum, wsiz, fnsiz, snsiz, *np, num, ksiz, vsiz, ssiz, zsiz;
  double tune;
  assert(db && doc);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  if(!doc->attrs || !(uri = cbmapget(doc->attrs, ESTDATTRURI, -1, NULL))){
    db->ecode = ESTEINVAL;
    return FALSE;
  }
  if((id = est_db_uri_to_id(db, uri)) > 0 &&
     !est_db_out_doc(db, id, (options & ESTPDCLEAN) ? ESTODCLEAN : 0)) return FALSE;
  if(!doc->dtexts) doc->dtexts = cblistopen();
  doc->id = ++(db->dseq);
  sprintf(nbuf, "%d", doc->id);
  cbmapput(doc->attrs, ESTDATTRID, -1, nbuf, -1, TRUE);
  ocmap = cbmapopen();
  fmap = cbmapopen();
  qmap = cbmapopen();
  wnum = 0;
  for(i = -1; i < CB_LISTNUM(doc->dtexts); i++){
    if(i < 0){
      if(!(text = cbmapget(doc->attrs, "", 0, NULL))) continue;
    } else {
      text = CB_LISTVAL(doc->dtexts, i, NULL);
    }
    words = cblistopen();
    switch(db->amode){
    case ESTAMPERFNG:
      est_break_text_perfng(text, words, FALSE, TRUE);
      break;
    default:
      est_break_text(text, words, FALSE, TRUE);
      break;
    }
    wnum += CB_LISTNUM(words);
    for(j = 0; j < CB_LISTNUM(words); j++){
      word = CB_LISTVAL2(words, j, &wsiz);
      if(wsiz > ESTWORDMAXLEN) continue;
      fnext = cblistval(words, j + 1, &fnsiz);
      snext = cblistval(words, j + 2, &snsiz);
      junc[0] = fnext ? dpinnerhash(fnext, fnsiz) % ESTJHASHNUM + 1: 0xff;
      junc[1] = snext ? dpouterhash(snext, snsiz) % ESTJHASHNUM + 1: 0xff;
      memcpy(wbuf, word, wsiz);
      memcpy(wbuf + wsiz, "\t", 1);
      memcpy(wbuf + wsiz + 1, junc, 2);
      np = (int *)cbmapget(fmap, word, wsiz, NULL);
      num = np ? *(int *)np : 0;
      num += ESTOCPOINT;
      cbmapput(fmap, word, wsiz, (char *)&num, sizeof(int), TRUE);
      if(cbmapput(qmap, wbuf, wsiz + 3, "", 0, FALSE))
        cbmapputcat(ocmap, word, wsiz, (char *)junc, 2);
    }
    cblistclose(words);
  }
  cbmapiterinit(ocmap);
  while((kbuf = cbmapiternext(ocmap, &ksiz)) != NULL){
    vbuf = cbmapget(ocmap, kbuf, ksiz, &vsiz);
    ocbuf = cbdatumopen("", 0);
    cbdatumcat(ocbuf, (char *)&(doc->id), sizeof(int));
    num = *(int *)cbmapget(fmap, kbuf, ksiz, NULL);
    tune = log(wnum + 3);
    tune = (tune * tune) / 10.0;
    num /= tune > 4.0 ? tune : 4.0;
    if(num >= 0x80) num += (0x80 - num) * 0.75;
    if(num >= 0xc0) num += (0xc0 - num) * 0.75;
    c = num < 0xff ? num : 0xff;
    cbdatumcat(ocbuf, (char *)&c, 1);
    cbdatumcat(ocbuf, vbuf, vsiz);
    c = 0x00;
    cbdatumcat(ocbuf, (char *)&c, 1);
    cbmapputcat(db->idxcc, kbuf, ksiz, CB_DATUMPTR(ocbuf), CB_DATUMSIZE(ocbuf));
    db->icsiz += CB_DATUMSIZE(ocbuf);
    cbdatumclose(ocbuf);
  }
  cbmapclose(qmap);
  cbmapclose(fmap);
  cbmapclose(ocmap);
  err = FALSE;
  sbuf = cbmapdump(doc->attrs, &ssiz);
  if(!crput(db->attrdb, (char *)&(doc->id), sizeof(int), sbuf, ssiz, CR_DKEEP)){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    err = TRUE;
  }
  free(sbuf);
  sbuf = cblistdump(doc->dtexts, &ssiz);
  if(!(zbuf = est_deflate(sbuf, ssiz, &zsiz))){
    CB_MALLOC(zbuf, 1);
    zsiz = 0;
    db->ecode = ESTEMISC;
    db->fatal = TRUE;
    err = TRUE;
  }
  if(!crput(db->textdb, (char *)&(doc->id), sizeof(int), zbuf, zsiz, CR_DKEEP)){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    err = TRUE;
  }
  free(sbuf);
  free(zbuf);
  sprintf(nbuf, "%d", doc->id);
  if(!vlput(db->listdb, uri, -1, nbuf, -1, VL_DKEEP)){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    err = TRUE;
  }
  db->dnum++;
  if(est_db_used_cache_size(db) > db->icmax){
    if(!est_db_flush(db, -1)) err = TRUE;
    est_idx_increment(db->idxdb);
  }
  return err ? FALSE : TRUE;
}


/* Remove a document from a database. */
int est_db_out_doc(ESTDB *db, int id, int options){
  ESTDOC *doc;
  CBLIST *words;
  const char *uri, *text, *word;
  char numbuf[ESTNUMBUFSIZ];
  int i, j, len, wsiz;
  assert(db && id > 0);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  if(!(doc = est_db_get_doc(db, id, 0))) return FALSE;
  if(!doc->attrs || !(uri = cbmapget(doc->attrs, ESTDATTRURI, -1, NULL))){
    est_doc_delete(doc);
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    return FALSE;
  }
  if(!crout(db->attrdb, (char *)&id, sizeof(int)) ||
     !crout(db->textdb, (char *)&id, sizeof(int)) || !vlout(db->listdb, uri, -1)){
    est_doc_delete(doc);
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    return FALSE;
  }
  cbmapout(db->attrcc, (char *)&id, sizeof(int));
  cbmapout(db->textcc, (char *)&id, sizeof(int));
  if(db->spacc) cbmapout(db->spacc, (char *)&id, sizeof(int));
  if((options & ESTODCLEAN) && doc->dtexts){
    len = sprintf(numbuf, "\t%d", doc->id);
    cbmapput(db->outcc, numbuf, len, "", 0, FALSE);
    for(i = -1; i < CB_LISTNUM(doc->dtexts); i++){
      if(i < 0){
        if(!(text = cbmapget(doc->attrs, "", 0, NULL))) continue;
      } else {
        text = CB_LISTVAL(doc->dtexts, i, NULL);
      }
      words = cblistopen();
      switch(db->amode){
      case ESTAMPERFNG:
        est_break_text_perfng(text, words, FALSE, TRUE);
        break;
      default:
        est_break_text(text, words, FALSE, TRUE);
        break;
      }
      for(j = 0; j < CB_LISTNUM(words); j++){
        word = CB_LISTVAL2(words, j, &wsiz);
        cbmapput(db->outcc, word, wsiz, "", 0, FALSE);
      }
      cblistclose(words);
    }
  }
  est_doc_delete(doc);
  db->dnum--;
  return TRUE;
}


/* Retrieve a document in a database. */
ESTDOC *est_db_get_doc(ESTDB *db, int id, int options){
  ESTDOC *doc;
  const char *cbuf;
  char *vbuf, *zbuf;
  int i, csiz, vsiz, zsiz, num;
  assert(db && id > 0);
  cbuf = NULL;
  if(options & ESTGDNOATTR){
    if(!crvsiz(db->attrdb, (char *)&id, sizeof(int))){
      if(dpecode == DP_ENOITEM){
        db->ecode = ESTENOITEM;
        return NULL;
      } else {
        db->ecode = ESTEDB;
        db->fatal = TRUE;
        return NULL;
      }
    }
    vbuf = NULL;
  } else if((cbuf = cbmapget(db->attrcc, (char *)&id, sizeof(int), &csiz)) != NULL){
    cbmapmove(db->attrcc, (char *)&id, sizeof(int), FALSE);
    vbuf = NULL;
  } else if(!(vbuf = crget(db->attrdb, (char *)&id, sizeof(int), 0, -1, &vsiz))){
    if(dpecode == DP_ENOITEM){
      db->ecode = ESTENOITEM;
      return NULL;
    } else {
      db->ecode = ESTEDB;
      db->fatal = TRUE;
      return NULL;
    }
  }
  doc = est_doc_new();
  doc->id = id;
  if(cbuf){
    doc->attrs = cbmapload(cbuf, csiz);
  } else if(vbuf){
    doc->attrs = cbmapload(vbuf, vsiz);
    cbmapputvbuf(db->attrcc, (char *)&id, sizeof(int), vbuf, vsiz);
    if(cbmaprnum(db->attrcc) > db->acmnum){
      num = cbmaprnum(db->attrcc) * 0.1 + 1;
      cbmapiterinit(db->attrcc);
      for(i = 0; i < num && (cbuf = cbmapiternext(db->attrcc, NULL)) != NULL; i++){
        cbmapout(db->attrcc, cbuf, sizeof(int));
      }
    }
  } else {
    doc->attrs = NULL;
  }
  if(!(options & ESTGDNOTEXT)){
    if((cbuf = cbmapget(db->textcc, (char *)&id, sizeof(int), &csiz)) != NULL){
      cbmapmove(db->textcc, (char *)&id, sizeof(int), FALSE);
      doc->dtexts = cblistload(cbuf, csiz);
    } else {
      if(!(zbuf = crget(db->textdb, (char *)&id, sizeof(int), 0, -1, &zsiz))){
        db->ecode = ESTEDB;
        db->fatal = TRUE;
        est_doc_delete(doc);
        return NULL;
      }
      if(!(vbuf = est_inflate(zbuf, zsiz, &vsiz))){
        db->ecode = ESTEDB;
        db->fatal = TRUE;
        free(zbuf);
        est_doc_delete(doc);
        return NULL;
      }
      doc->dtexts = cblistload(vbuf, vsiz);
      cbmapputvbuf(db->textcc, (char *)&id, sizeof(int), vbuf, vsiz);
      if(cbmaprnum(db->textcc) > db->tcmnum){
        num = cbmaprnum(db->textcc) * 0.1 + 1;
        cbmapiterinit(db->textcc);
        for(i = 0; i < num &&(cbuf = cbmapiternext(db->textcc, NULL)) != NULL; i++){
          cbmapout(db->textcc, cbuf, sizeof(int));
        }
      }
      free(zbuf);
    }
  }
  return doc;
}


/* Retrieve the value of an attribute of a document in a database. */
char *est_db_get_doc_attr(ESTDB *db, int id, const char *name){
  const char *cbuf;
  char *mbuf, *vbuf;
  int cb, csiz, msiz, vsiz;
  assert(db && id > 0 && name);
  cb = db->spacc && !strcmp(name, db->scname);
  if(cb && (cbuf = cbmapget(db->spacc, (char *)&id, sizeof(int), &csiz)) != NULL){
    cbmapmove(db->spacc, (char *)&id, sizeof(int), FALSE);
    return cbmemdup(cbuf, csiz);
  }
  if(!(mbuf = crget(db->attrdb, (char *)&id, sizeof(int), 0, -1, &msiz))){
    db->ecode = dpecode == DP_ENOITEM ? ESTENOITEM : ESTEDB;
    return NULL;
  }
  if(!(vbuf = cbmaploadone(mbuf, msiz, name, -1, &vsiz))){
    db->ecode = ESTENOITEM;
    free(mbuf);
    return NULL;
  }
  if(cb) cbmapput(db->spacc, (char *)&id, sizeof(int), vbuf, vsiz, FALSE);
  free(mbuf);
  return vbuf;
}


/* Get the ID of a document spacified by URI. */
int est_db_uri_to_id(ESTDB *db, const char *uri){
  char *vbuf;
  int id;
  assert(db && uri);
  if(!(vbuf = vlget(db->listdb, uri, -1, NULL))){
    db->ecode = ESTENOITEM;
    return -1;
  }
  id = atoi(vbuf);
  free(vbuf);
  return id;
}


/* Extract keywords of a document object. */
CBMAP *est_db_etch_doc(ESTDB *db, ESTDOC *doc, int max){
  ESTKEYSC *scores;
  CBMAP *keys, *umap;
  CBLIST *words;
  const char *text, *word, *vbuf;
  char numbuf[ESTNUMBUFSIZ];
  int i, wsiz, num, smax, snum, vsiz;
  assert(doc && max >= 0);
  if(!doc->dtexts) return cbmapopenex(1);
  keys = cbmapopenex(max * 1.5);
  words = cblistopen();
  for(i = -1; i < CB_LISTNUM(doc->dtexts); i++){
    if(i < 0){
      if(!doc->attrs || !(text = cbmapget(doc->attrs, "", 0, NULL))) continue;
    } else {
      text = CB_LISTVAL(doc->dtexts, i, NULL);
    }
    if(db){
      switch(db->amode){
      case ESTAMPERFNG:
        est_break_text_perfng(text, words, FALSE, TRUE);
        break;
      default:
        est_break_text(text, words, FALSE, TRUE);
        break;
      }
    } else {
      est_break_text(text, words, FALSE, TRUE);
    }
  }
  umap = cbmapopenex(CB_LISTNUM(words) + 1);
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = CB_LISTVAL2(words, i, &wsiz);
    if(wsiz > ESTWORDMAXLEN) continue;
    num = (vbuf = cbmapget(umap, word, wsiz, NULL)) ? *(int *)vbuf + 1 : 1;
    cbmapput(umap, word, wsiz, (char *)&num, sizeof(int), TRUE);
  }
  smax = max * (db ? ESTKEYSCALW : 1) + 1;
  CB_MALLOC(scores, cbmaprnum(umap) * sizeof(ESTKEYSC) + 1);
  snum = 0;
  cbmapiterinit(umap);
  for(i = 0; i < smax && (word = cbmapiternext(umap, &wsiz)) != NULL; i++){
    scores[snum].word = word;
    scores[snum].wsiz = wsiz;
    scores[snum].pt = (vbuf = cbmapget(umap, word, wsiz, NULL)) ? *(int *)vbuf : 0;
    snum++;
  }
  qsort(scores, snum, sizeof(ESTKEYSC), est_keysc_compare);
  if(db){
    for(i = 0; i < snum; i++){
      if((vbuf = cbmapget(db->keycc, scores[i].word, scores[i].wsiz, NULL)) != NULL){
        cbmapmove(db->keycc, scores[i].word, scores[i].wsiz, FALSE);
        vsiz = *(int*)vbuf;
      } else {
        vsiz = est_idx_vsiz(db->idxdb, scores[i].word, scores[i].wsiz);
        cbmapput(db->keycc, scores[i].word, scores[i].wsiz, (char *)&vsiz, sizeof(int), FALSE);
      }
      scores[i].pt *= 400000.0 / (vsiz + 64);
    }
    if(db->kcmnum >= 0 && cbmaprnum(db->keycc) > db->kcmnum){
      num = db->kcmnum * 0.1 + 1;
      cbmapiterinit(db->keycc);
      for(i = 0; i < num && (word = cbmapiternext(db->keycc, &wsiz)) != NULL; i++){
        cbmapout(db->keycc, word, wsiz);
      }
    }
    qsort(scores, snum, sizeof(ESTKEYSC), est_keysc_compare);
  }
  for(i = 0; i < snum &&  i < max; i++){
    vsiz = sprintf(numbuf, "%d", scores[i].pt);
    cbmapput(keys, scores[i].word, scores[i].wsiz, numbuf, vsiz, FALSE);
  }
  free(scores);
  cbmapclose(umap);
  cblistclose(words);
  return keys;
}


/* Initialize the iterator of a database. */
int est_db_iter_init(ESTDB *db){
  assert(db);
  return vlcurfirst(db->listdb);
}


/* Get the next ID of the iterator of a database. */
int est_db_iter_next(ESTDB *db){
  char *vbuf;
  int id;
  assert(db);
  if(!(vbuf = vlcurval(db->listdb, NULL))){
    if(dpecode == DP_ENOITEM){
      db->ecode = ESTENOITEM;
      return 0;
    } else {
      db->ecode = ESTEDB;
      db->fatal = TRUE;
      return -1;
    }
  }
  id = atoi(vbuf);
  free(vbuf);
  vlcurnext(db->listdb);
  return id;
}


/* Get the name of a database. */
const char *est_db_name(ESTDB *db){
  assert(db);
  return db->name;
}


/* Get the number of documents in a database. */
int est_db_doc_num(ESTDB *db){
  assert(db);
  return db->dnum;
}


/* Get the number of words in a database. */
int est_db_word_num(ESTDB *db){
  assert(db);
  return vlrnum(db->fwmdb);
}


/* Get the size of a database. */
double est_db_size(ESTDB *db){
  assert(db);
  return dpfsiz(db->metadb) + est_idx_size(db->idxdb) + vlfsiz(db->fwmdb) +
    crfsizd(db->attrdb) + crfsizd(db->textdb) + vlfsiz(db->listdb);
}


/* Search documents corresponding a condition for a database. */
int *est_db_search(ESTDB *db, ESTCOND *cond, int *nump, CBMAP *hints){
  ESTSCORE *scores, *tscores;
  CBMAP *svmap;
  CBLIST *terms;
  const char *term, *rp;
  char *tmp, numbuf[ESTNUMBUFSIZ];
  int i, j, snum, pcnum, ncnum, tsnum, add, nnum, id, score, hnum, len, *rval;
  double tune;
  assert(db && cond && nump);
  scores = NULL;
  snum = 0;
  if(cond->phrase && cond->phrase[0] == ESTOPSIMILAR[0] &&
     cbstrfwmatch(cond->phrase, ESTOPSIMILAR)){
    rp = cond->phrase;
    rp += strlen(ESTOPSIMILAR);
    while(*rp > '\0' && *rp <= ' '){
      rp++;
    }
    svmap = est_phrase_vector(rp);
    scores = est_search_similar(db, svmap, &snum, ESTSMLRKNUM, ESTSMLRUNUM, cond->tfidf,
                                cond->order ? ESTSMLRNMIN : 0.0);
    cbmapclose(svmap);
  } else if(cond->phrase){
    if(cond->simple){
      tmp = est_phrase_from_thumb(cond->phrase);
      terms = est_phrase_terms(tmp);
      free(tmp);
    } else {
      terms = est_phrase_terms(cond->phrase);
    }
    pcnum = 0;
    ncnum = 0;
    add = TRUE;
    for(i = 0; i < CB_LISTNUM(terms); i++){
      term = CB_LISTVAL(terms, i, NULL);
      if(!strcmp(term, ESTOPISECT)){
        add = TRUE;
      } else if(!strcmp(term, ESTOPDIFF)){
        add = FALSE;
      } else {
        if(!strcmp(term, ESTOPUVSET)){
          tscores = est_search_uvset(db, &tsnum, hints, add);
        } else {
          tscores = est_search_union(db, term, cond->gstep, &tsnum, hints, add);
        }
        if(add){
          if(cond->tfidf){
            tune = log(tsnum + 3);
            tune =  tune * tune * tune;
            if(tune < 8.0) tune = 8.0;
            for(j = 0; j < tsnum; j++){
              tscores[j].score *= 10000 / tune;
            }
          }
          pcnum++;
        } else {
          ncnum++;
        }
        if(scores){
          CB_REALLOC(scores, (snum + tsnum) * sizeof(ESTSCORE) + 1);
          for(j = 0; j < tsnum; j++){
            scores[snum+j].id = tscores[j].id;
            scores[snum+j].score = add ? tscores[j].score : -1;
          }
          snum += tsnum;
          free(tscores);
        } else {
          scores = tscores;
          snum = tsnum;
        }
      }
    }
    if(scores){
      if(pcnum > 1 || ncnum > 0){
        qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_id);
        nnum = 0;
        for(i = 0; i < snum; i++){
          id = scores[i].id;
          score = scores[i].score;
          hnum = score >= 0 ? 1 : 0;
          for(j = i + 1; j < snum && scores[j].id == id; j++){
            if(score >= 0 && scores[j].score >= 0){
              score += scores[j].score;
              hnum++;
            } else {
              score = -1;
            }
          }
          if(score >= 0 && hnum >= pcnum){
            scores[nnum].id = id;
            scores[nnum].score = score;
            nnum++;
          }
          i = j - 1;
        }
        snum = nnum;
      }
    } else {
      CB_MALLOC(scores, 1);
      snum = 0;
    }
    cblistclose(terms);
  } else if(cond->attrs){
    scores = est_search_uvset(db, &snum, hints, TRUE);
  } else {
    CB_MALLOC(scores, 1);
    snum = 0;
  }
  if(cbmaprnum(db->outcc) > 0){
    tsnum = 0;
    for(i = 0; i < snum; i++){
      len = sprintf(numbuf, "\t%d", scores[i].id);
      if(cbmapget(db->outcc, numbuf, len, NULL)) continue;
      scores[tsnum++] = scores[i];
    }
    snum = tsnum;
  }
  if(cond->attrs || cond->order)
    snum = est_narrow_scores(db, cond->attrs, cond->order, scores, snum);
  if(!cond->order) qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_score);
  if(hints){
    sprintf(numbuf, "%d", snum);
    cbmapput(hints, "", 0, numbuf, -1, FALSE);
  }
  if(cond->max >= 0 && cond->max < snum) snum = cond->max;
  CB_MALLOC(rval, snum * sizeof(int) + 1);
  for(i = 0; i < snum; i++){
    rval[i] = scores[i].id;
  }
  if(cond->scfb){
    CB_REALLOC(cond->scores, snum * sizeof(int) + 1);
    for(i = 0; i < snum; i++){
      cond->scores[i] = scores[i].score;
    }
    cond->snum = snum;
  }
  *nump = snum;
  if(*nump < 1) db->ecode = ESTENOITEM;
  free(scores);
  return rval;
}


/* Set the maximum size of the cache memory of a database. */
void est_db_set_cache_size(ESTDB *db, size_t size, int anum, int tnum){
  assert(db);
  if(dpwritable(db->metadb) && size > 0) db->icmax = size;
  if(anum > 0) db->acmnum = anum;
  if(tnum > 0) db->tcmnum = tnum;
}


/* Set the special cache for narrowing and sorting with document attributes. */
void est_db_set_special_cache(ESTDB *db, const char *name, int num){
  assert(db && name && num >= 0);
  if(db->spacc){
    free(db->scname);
    cbmapclose(db->spacc);
  }
  db->spacc = cbmapopenex(num + 1);
  db->scmnum = num;
  db->scname = cbmemdup(name, -1);
}


/*************************************************************************************************
 * features for experts
 *************************************************************************************************/


/* Handle to the file of random number generator. */
FILE *est_random_ifp = NULL;


/* Break a sentence of text and extract words. */
void est_break_text(const char *text, CBLIST *list, int norm, int tail){
  CBLIST *words;
  const unsigned char *word, *next;
  unsigned char *utext;
  char *tmp;
  int i, j, k, size, cc, wsiz, nsiz, tsiz;
  assert(text);
  utext = (unsigned char *)est_uconv_in(text, strlen(text), &size);
  if(norm) est_normalize_text(utext, size, &size);
  est_canonicalize_text(utext, size, FALSE);
  words = cblistopen();
  for(i = 0; i < size; i += 2){
    cc = est_char_category(utext[i] * 0x100 + utext[i+1]);
    for(j = i + 2; j < size; j += 2){
      if(est_char_category(utext[j] * 0x100 + utext[j+1]) != cc) break;
    }
    switch(cc){
    case ESTDELIMCHR:
    case ESTWESTALPH:
      cblistpush(words, (char *)(utext + i), j - i);
      break;
    case ESTEASTALPH:
      for(k = i; k < j; k += 2){
        if(j - k >= 4){
          cblistpush(words, (char *)(utext + k), 4);
        } else {
          cblistpush(words, (char *)(utext + k), 2);
        }
      }
      break;
    default:
      break;
    }
    i = j - 2;
  }
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = (unsigned char *)CB_LISTVAL2(words, i, &wsiz);
    if(est_char_category(word[0] * 0x100 + word[1]) == ESTEASTALPH && wsiz == 2 &&
       i < CB_LISTNUM(words) - 1){
      next = (unsigned char *)cblistval(words, i + 1, &nsiz);
      if(nsiz > 4) nsiz = 4;
      if(est_char_category(next[0] * 0x100 + next[1]) == ESTEASTALPH && nsiz > 2) nsiz = 2;
      CB_MALLOC(tmp, wsiz + nsiz + 1);
      memcpy(tmp, word, wsiz);
      memcpy(tmp + wsiz, next, nsiz);
      cblistover(words, i, tmp, wsiz + nsiz);
      free(tmp);
    }
  }
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = (unsigned char *)CB_LISTVAL2(words, i, &wsiz);
    if(!tail && wsiz == 2 && i == CB_LISTNUM(words) - 1){
      if(est_char_category(word[0] * 0x100 + word[1]) == ESTEASTALPH) continue;
    }
    tmp = est_uconv_out((char *)word, wsiz, &tsiz);
    cblistpushbuf(list, tmp, tsiz);
  }
  cblistclose(words);
  free(utext);
}


/* Break a sentence of text and extract words using perfect N-gram analyzer. */
void est_break_text_perfng(const char *text, CBLIST *list, int norm, int tail){
  CBLIST *words;
  const unsigned char *word, *next;
  unsigned char *utext;
  char *tmp;
  int i, j, k, size, cc, wsiz, nsiz, tsiz;
  assert(text);
  utext = (unsigned char *)est_uconv_in(text, strlen(text), &size);
  if(norm) est_normalize_text(utext, size, &size);
  est_canonicalize_text(utext, size, FALSE);
  words = cblistopen();
  for(i = 0; i < size; i += 2){
    cc = est_char_category_perfng(utext[i] * 0x100 + utext[i+1]);
    for(j = i + 2; j < size; j += 2){
      if(est_char_category_perfng(utext[j] * 0x100 + utext[j+1]) != cc) break;
    }
    switch(cc){
    case ESTEASTALPH:
      for(k = i; k < j; k += 2){
        if(j - k >= 4){
          cblistpush(words, (char *)(utext + k), 4);
        } else {
          cblistpush(words, (char *)(utext + k), 2);
        }
      }
      break;
    default:
      break;
    }
    i = j - 2;
  }
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = (unsigned char *)CB_LISTVAL2(words, i, &wsiz);
    if(est_char_category_perfng(word[0] * 0x100 + word[1]) == ESTEASTALPH && wsiz == 2 &&
       i < CB_LISTNUM(words) - 1){
      next = (unsigned char *)cblistval(words, i + 1, &nsiz);
      if(nsiz > 4) nsiz = 4;
      if(est_char_category_perfng(next[0] * 0x100 + next[1]) == ESTEASTALPH && nsiz > 2) nsiz = 2;
      CB_MALLOC(tmp, wsiz + nsiz + 1);
      memcpy(tmp, word, wsiz);
      memcpy(tmp + wsiz, next, nsiz);
      cblistover(words, i, tmp, wsiz + nsiz);
      free(tmp);
    }
  }
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = (unsigned char *)CB_LISTVAL2(words, i, &wsiz);
    if(!tail && wsiz == 2 && i == CB_LISTNUM(words) - 1){
      if(est_char_category_perfng(word[0] * 0x100 + word[1]) == ESTEASTALPH) continue;
    }
    tmp = est_uconv_out((char *)word, wsiz, &tsiz);
    cblistpushbuf(list, tmp, tsiz);
  }
  cblistclose(words);
  free(utext);
}


/* Convert the character encoding of a string. */
char *est_iconv(const char *ptr, int size,
                const char *icode, const char *ocode, int *sp, int *mp){
  iconv_t ic;
  char *obuf, *wp, *rp;
  size_t isiz, osiz;
  int miss;
  assert(ptr && icode && ocode);
  if(size < 0) size = strlen(ptr);
  if(icode[0] == 'x' && icode[1] == '-'){
    if(!cbstricmp(icode, "x-sjis")){
      icode = "Shift_JIS";
    } else if(!cbstricmp(icode, "x-ujis")){
      icode = "EUC-JP";
    } else if(!cbstricmp(icode, "x-euc-jp")){
      icode = "EUC-JP";
    }
  } else if(icode[0] == 'w' || icode[0] == 'W'){
    if(!cbstricmp(icode, "windows-31j")){
      icode = "CP932";
    }
  }
  if(ocode[0] == 'x' && ocode[1] == '-'){
    if(!cbstricmp(ocode, "x-sjis")){
      ocode = "Shift_JIS";
    } else if(!cbstricmp(ocode, "x-ujis")){
      ocode = "EUC-JP";
    } else if(!cbstricmp(ocode, "x-euc-jp")){
      ocode = "EUC-JP";
    }
  } else if(ocode[0] == 'w' || ocode[0] == 'W'){
    if(!cbstricmp(ocode, "windows-31j")){
      ocode = "CP932";
    }
  }
  if((ic = iconv_open(ocode, icode)) == (iconv_t)-1) return NULL;
  isiz = size;
  osiz = isiz * 5;
  CB_MALLOC(obuf, osiz + 1);
  wp = obuf;
  rp = (char *)ptr;
  miss = 0;
  while(isiz > 0){
    if(iconv(ic, (void *)&rp, &isiz, &wp, &osiz) == -1){
      if(errno == EILSEQ && (*rp == 0x5c || *rp == 0x7e)){
        *wp = *rp;
        wp++;
        rp++;
        isiz--;
      } else if(errno == EILSEQ || errno == EINVAL){
        rp++;
        isiz--;
        miss++;
      } else {
        break;
      }
    }
  }
  *wp = '\0';
  if(sp) *sp = wp - obuf;
  if(mp) *mp = miss;
  if(iconv_close(ic) == -1){
    free(obuf);
    return NULL;
  }
  return obuf;
}


/* Detect the encoding of a string automatically. */
const char *est_enc_name(const char *ptr, int size, int plang){
  const char *hypo;
  int i, miss, cr;
  assert(ptr);
  if(size < 0) size = strlen(ptr);
  if(size > ESTICCHECKSIZ) size = ESTICCHECKSIZ;
  if(size >= 2 && (!memcmp(ptr, "\xfe\xff", 2) || !memcmp(ptr, "\xff\xfe", 2))) return "UTF-16";
  for(i = 0; i < size - 1; i += 2){
    if(ptr[i] == 0 && ptr[i+1] != 0) return "UTF-16BE";
    if(ptr[i+1] == 0 && ptr[i] != 0) return "UTF-16LE";
  }
  switch(plang){
  case ESTLANGEN:
    if(est_enc_miss(ptr, size, "US-ASCII", "UTF-16BE") < 1) return "US-ASCII";
    if(est_enc_miss(ptr, size, "UTF-8", "UTF-16BE") < 1) return "UTF-8";
    return "ISO-8859-1";
  case ESTLANGJA:
    for(i = 0; i < size - 3; i++){
      if(ptr[i] == 0x1b){
        i++;
        if(ptr[i] == '(' && strchr("BJHI", ptr[i+1])) return "ISO-2022-JP";
        if(ptr[i] == '$' && strchr("@B(", ptr[i+1])) return "ISO-2022-JP";
      }
    }
    if(est_enc_miss(ptr, size, "US-ASCII", "UTF-16BE") < 1) return "US-ASCII";
    if(est_enc_miss(ptr, size, "UTF-8", "UTF-16BE") < 1) return "UTF-8";
    hypo = NULL;
    cr = FALSE;
    for(i = 0; i < size; i++){
      if(ptr[i] == 0xd){
        cr = TRUE;
        break;
      }
    }
    if(cr){
      if((miss = est_enc_miss(ptr, size, "Shift_JIS", "EUC-JP")) < 1) return "Shift_JIS";
      if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "Shift_JIS";
      if((miss = est_enc_miss(ptr, size, "EUC-JP", "UTF-16BE")) < 1) return "EUC-JP";
      if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "EUC-JP";
    } else {
      if((miss = est_enc_miss(ptr, size, "EUC-JP", "UTF-16BE")) < 1) return "EUC-JP";
      if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "EUC-JP";
      if((miss = est_enc_miss(ptr, size, "Shift_JIS", "EUC-JP")) < 1) return "Shift_JIS";
      if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "Shift_JIS";
    }
    if((miss = est_enc_miss(ptr, size, "UTF-8", "UTF-16BE")) < 1) return "UTF-8";
    if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "UTF-8";
    if((miss = est_enc_miss(ptr, size, "CP932", "UTF-16BE")) < 1) return "CP932";
    if(!hypo && miss / (double)size <= ESTICALLWRAT) hypo = "CP932";
    return hypo ? hypo : "ISO-8859-1";
  case ESTLANGZH:
    if(est_enc_miss(ptr, size, "US-ASCII", "UTF-16BE") < 1) return "US-ASCII";
    if(est_enc_miss(ptr, size, "UTF-8", "UTF-16BE") < 1) return "UTF-8";
    if(est_enc_miss(ptr, size, "EUC-CN", "UTF-16BE") < 1) return "EUC-CN";
    if(est_enc_miss(ptr, size, "BIG5", "UTF-16BE") < 1) return "BIG5";
    return "ISO-8859-1";
  case ESTLANGKO:
    if(est_enc_miss(ptr, size, "US-ASCII", "UTF-16BE") < 1) return "US-ASCII";
    if(est_enc_miss(ptr, size, "UTF-8", "UTF-16BE") < 1) return "UTF-8";
    if(est_enc_miss(ptr, size, "EUC-KR", "UTF-16BE") < 1) return "EUC-KR";
    return "ISO-8859-1";
  default:
    break;
  }
  return "ISO-8859-1";
}


/* Convert a UTF-8 string into UTF-16BE. */
char *est_uconv_in(const char *ptr, int size, int *sp){
  const unsigned char *rp;
  char *rbuf, *wp;
  assert(ptr && size >= 0 && sp);
  rp = (unsigned char *)ptr;
  CB_MALLOC(rbuf, size * 2 + 1);
  wp = rbuf;
  while(rp < (unsigned char *)ptr + size){
    if(*rp < 0x7f){
      *(wp++) = 0x00;
      *(wp++) = *rp;
      rp += 1;
    } else if(*rp < 0xdf){
      if(rp >= (unsigned char *)ptr + size - 1) break;
      *(wp++) = (rp[0] & 0x1f) >> 2;
      *(wp++) = (rp[0] << 6) | (rp[1] & 0x3f);
      rp += 2;
    } else if(*rp < 0xf0){
      if(rp >= (unsigned char *)ptr + size - 2) break;
      *(wp++) = (rp[0] << 4) | ((rp[1] & 0x3f) >> 2);
      *(wp++) = (rp[1] << 6) | (rp[2] & 0x3f);
      rp += 3;
    } else if(*rp < 0xf8){
      if(rp >= (unsigned char *)ptr + size - 3) break;
      *(wp++) = 0x00;
      *(wp++) = '?';
      rp += 4;
    } else if(*rp < 0xfb){
      if(rp >= (unsigned char *)ptr + size - 4) break;
      *(wp++) = 0x00;
      *(wp++) = '?';
      rp += 5;
    } else if(*rp < 0xfd){
      if(rp >= (unsigned char *)ptr + size - 5) break;
      *(wp++) = 0x00;
      *(wp++) = '?';
      rp += 6;
    } else {
      break;
    }
  }
  *wp = '\0';
  *sp = wp - rbuf;
  return rbuf;
}


/* Convert a UTF-16BE string into UTF-8. */
char *est_uconv_out(const char *ptr, int size, int *sp){
  const unsigned char *rp;
  char *rbuf, *wp;
  int c;
  assert(ptr && size >= 0);
  if(size % 2 != 0) size--;
  rp = (unsigned char *)ptr;
  CB_MALLOC(rbuf, size * 2 + 1);
  wp = rbuf;
  while(rp < (unsigned char *)ptr + size){
    c = rp[0] * 0x100 + rp[1];
    if(c < 0x0080){
      *(wp++) = rp[1];
    } else if(c < 0x0900){
      *(wp++) = 0xc0 | (rp[0] << 2) | ((rp[1] >> 6) & 0x03);
      *(wp++) = 0x80 | (rp[1] & 0x3f);
    } else {
      *(wp++) = 0xe0 | ((rp[0] >> 4) & 0x0f);
      *(wp++) = 0x80 | ((rp[0] & 0x0f) << 2) | ((rp[1] >> 6) & 0x03);
      *(wp++) = 0x80 | (rp[1] & 0x3f);
    }
    rp += 2;
  }
  *wp = '\0';
  if(sp) *sp = wp - rbuf;
  return rbuf;
}


/* Compress a serial object with ZLIB. */
char *est_deflate(const char *ptr, int size, int *sp){
  z_stream zs;
  char *buf;
  unsigned char obuf[ESTIOBUFSIZ];
  int rv, asiz, bsiz, osiz;
  assert(ptr && sp);
  if(size < 0) size = strlen(ptr);
  zs.zalloc = Z_NULL;
  zs.zfree = Z_NULL;
  zs.opaque = Z_NULL;
  if(deflateInit(&zs, ESTZCOMPLEVEL) != Z_OK) return NULL;
  asiz = ESTIOBUFSIZ;
  CB_MALLOC(buf, asiz);
  bsiz = 0;
  zs.next_in = (unsigned char *)ptr;
  zs.avail_in = size;
  zs.next_out = obuf;
  zs.avail_out = ESTIOBUFSIZ;
  while((rv = deflate(&zs, Z_FINISH)) == Z_OK){
    osiz = ESTIOBUFSIZ - zs.avail_out;
    if(bsiz + osiz > asiz){
      asiz = asiz * 2 + osiz;
      CB_REALLOC(buf, asiz);
    }
    memcpy(buf + bsiz, obuf, osiz);
    bsiz += osiz;
    zs.next_out = obuf;
    zs.avail_out = ESTIOBUFSIZ;
  }
  if(rv != Z_STREAM_END){
    free(buf);
    deflateEnd(&zs);
    return NULL;
  }
  osiz = ESTIOBUFSIZ - zs.avail_out;
  if(bsiz + osiz > asiz){
    asiz = asiz * 2 + osiz;
    CB_REALLOC(buf, asiz);
  }
  memcpy(buf + bsiz, obuf, osiz);
  bsiz += osiz;
  *sp = bsiz;
  deflateEnd(&zs);
  return buf;
}


/* Decompress a serial object compressed with ZLIB. */
char *est_inflate(const char *ptr, int size, int *sp){
  z_stream zs;
  char *buf;
  unsigned char obuf[ESTIOBUFSIZ];
  int rv, asiz, bsiz, osiz;
  assert(ptr && size >= 0 && sp);
  zs.zalloc = Z_NULL;
  zs.zfree = Z_NULL;
  zs.opaque = Z_NULL;
  if(inflateInit(&zs) != Z_OK) return NULL;
  asiz = ESTIOBUFSIZ;
  CB_MALLOC(buf, asiz);
  bsiz = 0;
  zs.next_in = (unsigned char *)ptr;
  zs.avail_in = size;
  zs.next_out = obuf;
  zs.avail_out = ESTIOBUFSIZ;
  while((rv = inflate(&zs, Z_NO_FLUSH)) == Z_OK){
    osiz = ESTIOBUFSIZ - zs.avail_out;
    if(bsiz + osiz >= asiz){
      asiz = asiz * 2 + osiz;
      CB_REALLOC(buf, asiz);
    }
    memcpy(buf + bsiz, obuf, osiz);
    bsiz += osiz;
    zs.next_out = obuf;
    zs.avail_out = ESTIOBUFSIZ;
  }
  if(rv != Z_STREAM_END){
    free(buf);
    inflateEnd(&zs);
    return NULL;
  }
  osiz = ESTIOBUFSIZ - zs.avail_out;
  if(bsiz + osiz >= asiz){
    asiz = asiz * 2 + osiz;
    CB_REALLOC(buf, asiz);
  }
  memcpy(buf + bsiz, obuf, osiz);
  bsiz += osiz;
  buf[bsiz] = '\0';
  if(sp) *sp = bsiz;
  inflateEnd(&zs);
  return buf;
}


/* Get the border string for draft data of documents. */
const char *est_border_str(void){
  static int first = TRUE;
  static char border[ESTPATHBUFSIZ];
  int t, p;
  if(first){
    t = (int)(time(NULL) + est_random() * INT_MAX);
    p = (int)(getpid() + est_random() * INT_MAX);
    sprintf(border, "--------[%08X%08X]--------",
            dpouterhash((char *)&t, sizeof(int)), dpouterhash((char *)&p, sizeof(int)));
    first = FALSE;
  }
  return border;
}


/* Get the real random number. */
double est_random(void){
  static int first = TRUE;
  int num;
  if(first && !est_random_ifp){
    if((est_random_ifp = fopen("/dev/urandom", "rb")) != NULL){
      atexit(est_random_fclose);
    } else {
      srand(getpid());
    }
    first = FALSE;
  }
  if(est_random_ifp){
    fread(&num, sizeof(int), 1, est_random_ifp);
    return (num & 0x7fffffff) / (double)0x7fffffff;
  }
  return rand() / (double)RAND_MAX;
}


/* Get the random number in normal distribution. */
double est_random_nd(void){
  double d;
  d = (sqrt(-2 * log(1.0 - est_random())) * cos(3.1415926535 * 2 * est_random()) + 6.0) / 12.0;
  if(d > 1.0) d = 1.0;
  if(d < 0.0) d = 0.0;
  return d;
}


/* Get an MD5 hash string of a key string. */
char *est_make_crypt(const char *key){
  md5_state_t ms;
  char digest[32], str[64], *wp;
  int i;
  assert(key);
  md5_init(&ms);
  md5_append(&ms, (md5_byte_t *)key, strlen(key));
  md5_finish(&ms, (md5_byte_t *)digest);
  wp = str;
  for(i = 0; i < 16; i++){
    wp += sprintf(wp, "%02x", ((unsigned char *)digest)[i]);
  }
  return cbmemdup(str, -1);
}


/* Check whether a key matches an MD5 hash string. */
int est_match_crypt(const char *key, const char *hash){
  char *khash;
  int rv;
  assert(key && hash);
  khash = est_make_crypt(key);
  rv = !strcmp(khash, hash);
  free(khash);
  return rv;
}


/* Get the hidden texts of a document object. */
const char *est_doc_hidden_texts(ESTDOC *doc){
  const char *rv;
  assert(doc);
  rv = doc->attrs ? cbmapget(doc->attrs, "", 0, NULL) : NULL;
  return rv ? rv : "";
}


/* Get the phrase of a condition object. */
const char *est_cond_phrase(ESTCOND *cond){
  assert(cond);
  return cond->phrase;
}


/* Get a list object of attribute expressions of a condition object. */
const CBLIST *est_cond_attrs(ESTCOND *cond){
  assert(cond);
  return cond->attrs;
}


/* Get the order expression of a condition object. */
const char *est_cond_order(ESTCOND *cond){
  assert(cond);
  return cond->order;
}


/* Get the maximum number of retrieval of a condition object. */
int est_cond_max(ESTCOND *cond){
  assert(cond);
  return cond->max;
}


/* Get the options of a condition object. */
int est_cond_options(ESTCOND *cond){
  assert(cond);
  return cond->opts;
}


/* Get the score of a document corresponding to a condition object. */
int est_cond_score(ESTCOND *cond, int index){
  assert(cond);
  if(!cond->scores || index < 0 || index >= cond->snum) return -1;
  return cond->scores[index];
}


/* Set the error code of a database. */
void est_db_set_ecode(ESTDB *db, int ecode){
  assert(db);
  db->ecode = ecode;
}


/* Edit attributes of a document object in a database. */
int est_db_edit_doc(ESTDB *db, ESTDOC *doc){
  const char *uri;
  char *sbuf;
  int err, id, ssiz;
  assert(db && doc);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return FALSE;
  }
  if(!doc->attrs || !(uri = cbmapget(doc->attrs, ESTDATTRURI, -1, NULL)) || doc->id < 1){
    db->ecode = ESTEINVAL;
    return FALSE;
  }
  if((id = est_db_uri_to_id(db, uri)) > 0 && id != doc->id){
    db->ecode = ESTEINVAL;
    return FALSE;
  }
  err = FALSE;
  sbuf = cbmapdump(doc->attrs, &ssiz);
  if(!crput(db->attrdb, (char *)&(doc->id), sizeof(int), sbuf, ssiz, CR_DOVER)){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
    err = TRUE;
  }
  free(sbuf);
  if(db->spacc) cbmapout(db->spacc, (char *)&(doc->id), sizeof(int));
  return err ? FALSE : TRUE;
}


/* Add a piece of meta data to a database. */
void est_db_add_meta(ESTDB *db, const char *name, const char *value){
  assert(db && name);
  if(!dpwritable(db->metadb)){
    db->ecode = ESTEACCES;
    return;
  }
  if(!db->metacc) est_db_prepare_meta(db);
  if(value){
    cbmapput(db->metacc, name, -1, value, -1, TRUE);
  } else {
    cbmapout(db->metacc, name, -1);
  }
}


/* Get a list of names of meta data of a database. */
CBLIST *est_db_meta_names(ESTDB *db){
  assert(db);
  if(!db->metacc) est_db_prepare_meta(db);
  return cbmapkeys(db->metacc);
}


/* Get the value of a piece of meta data of a database. */
char *est_db_meta(ESTDB *db, const char *name){
  const char *vbuf;
  int vsiz;
  assert(db && name);
  if(!db->metacc) est_db_prepare_meta(db);
  if(!(vbuf = cbmapget(db->metacc, name, -1, &vsiz))) return NULL;
  return cbmemdup(vbuf, vsiz);
}


/* Get the number of records in the cache memory of a database. */
int est_db_cache_num(ESTDB *db){
  assert(db);
  return cbmaprnum(db->idxcc);
}


/* Set the callback function for database events. */
void est_db_set_informer(ESTDB *db, void (*func)(const char *)){
  assert(db && func);
  db->cbinfo = func;
  est_db_inform(db, "status");
}


/* Set the callback function to create a vector of keywords of a document. */
void est_db_set_vectorizer(ESTDB *db, CBMAP *(*func)(void *, int, void *), void *data){
  assert(db && func);
  db->cbvec = func;
  db->vecdata = data;
}


/* Fill the cache for keys for TF-IDF. */
void est_db_fill_key_cache(ESTDB *db){
  char *kbuf, *msg;
  int i, ksiz, vsiz;
  assert(db);
  vlcurfirst(db->fwmdb);
  for(i = 0; (kbuf = vlcurkey(db->fwmdb, &ksiz)) != NULL; i++){
    vsiz = est_idx_vsiz(db->idxdb, kbuf, ksiz);
    cbmapput(db->keycc, kbuf, ksiz, (char *)&vsiz, sizeof(int), TRUE);
    free(kbuf);
    vlcurnext(db->fwmdb);
    if(i % ESTCCCBFREQ == 0){
      msg = cbsprintf("filling the key cache for TF-IDF (%d)", i + 1);
      est_db_inform(db, msg);
      free(msg);
    }
  }
  db->kcmnum = -1;
}


/* Make a directory. */
int est_mkdir(const char *path){
#if defined(_SYS_MSVC_) || defined(_SYS_MINGW_)
  return mkdir(path) == 0 ? TRUE : FALSE;
#else
  assert(path);
  return mkdir(path, ESTDIRMODE) == 0 ? TRUE : FALSE;
#endif
}


/* Remove a directory and its contents recursively. */
int est_rmdir_rec(const char *path){
  CBLIST *files;
  const char *file;
  char pbuf[ESTPATHBUFSIZ];
  int i;
  assert(path);
  if((files = cbdirlist(path)) != NULL){
    for(i = 0; i < cblistnum(files); i++){
      file = cblistval(files, i, NULL);
      if(!strcmp(file, ESTCDIRSTR) || !strcmp(file, ESTPDIRSTR)) continue;
      sprintf(pbuf, "%s%c%s", path, ESTPATHCHR, file);
      if(unlink(pbuf) == -1) est_rmdir_rec(pbuf);
    }
    cblistclose(files);
  }
  return rmdir(path) == 0;
}


/* Get the canonicalized absolute pathname of a file. */
char *est_realpath(const char *path){
#if defined(_SYS_MSVC_) || defined(_SYS_MINGW_)
  char pbuf[ESTPATHBUFSIZ], *p;
  if(GetFullPathName(path, ESTPATHBUFSIZ, pbuf, &p) == 0) sprintf(pbuf, "%s", path);
  return cbmemdup(pbuf, -1);
#else
  char pbuf[ESTPATHBUFSIZ*2];
  assert(path);
  if(!realpath(path, pbuf)) sprintf(pbuf, "%s", path);
  return cbmemdup(pbuf, -1);
#endif
}


/* Get the time of day in milliseconds. */
double est_gettimeofday(void){
#if defined(_SYS_MSVC_) || defined(_SYS_MINGW_)
  SYSTEMTIME st;
  struct tm ts;
  GetLocalTime(&st);
  memset(&ts, 0, sizeof(struct tm));
  ts.tm_year = st.wYear - 1900;
  ts.tm_mon = st.wMonth - 1;
  ts.tm_mday = st.wDay;
  ts.tm_hour = st.wHour;
  ts.tm_min = st.wMinute;
  ts.tm_sec = st.wSecond;
  return (double)mktime(&ts) * 1000 + (double)st.wMilliseconds;
#else
  struct timeval tv;
  struct timezone tz;
  if(gettimeofday(&tv, &tz) == -1) return 0.0;
  return (double)tv.tv_sec * 1000 + (double)tv.tv_usec / 1000;
#endif
}


/* Suspend execution for microsecond intervals. */
void est_usleep(unsigned long usec){
#if defined(_SYS_MSVC_) || defined(_SYS_MINGW_)
  Sleep(usec / 1000);
#else
  usleep(usec);
#endif
}


/* Send a signal to a process. */
int est_kill(int pid, int sig){
#if defined(_SYS_MSVC_) || defined(_SYS_MINGW_)
  return FALSE;
#else
  return kill(pid, sig) == 0;
#endif
}


/* get the media type of an extention */
const char *est_ext_type(const char *ext){
  static const char *list[] = {
    ".txt", "text/plain", ".txt.en", "text/plain",
    ".txt.ja", "text/plain", ".asc", "text/plain",
    ".in", "text/plain", ".c", "text/plain",
    ".h", "text/plain", ".cc", "text/plain",
    ".java", "text/plain", ".sh", "text/plain",
    ".pl", "text/plain", ".py", "text/plain",
    ".rb", "text/plain", ".idl", "text/plain",
    ".csv", "text/plain", ".log", "text/plain",
    ".conf", "text/plain", ".rc", "text/plain",
    ".ini", "text/plain", ".html", "text/html",
    ".htm", "text/html", ".xhtml", "text/html",
    ".xht", "text/html", ".css", "text/css",
    ".js", "text/javascript", ".tsv", "text/tab-separated-values",
    ".eml", "message/rfc822", ".mime", "message/rfc822",
    ".mht", "message/rfc822", ".mhtml", "message/rfc822",
    ".sgml", "application/sgml", ".sgm", "application/sgml",
    ".xml", "application/xml", ".xsl", "application/xml",
    ".xslt", "application/xslt+xml", ".xhtml", "application/xhtml+xml",
    ".xht", "application/xhtml+xml", ".rdf", "application/rdf+xml",
    ".rss", "application/rss+xml", ".dtd", "application/xml-dtd",
    ".rtf", "application/rtf", ".pdf", "application/pdf",
    ".ps", "application/postscript", ".eps", "application/postscript",
    ".doc", "application/msword", ".xls", "application/vnd.ms-excel",
    ".ppt", "application/vnd.ms-powerpoint", ".xdw", "application/vnd.fujixerox.docuworks",
    ".swf", "application/x-shockwave-flash", ".zip", "application/zip",
     ".tar", "application/x-tar", ".gz", "application/x-gzip",
    ".bz2", "application/octet-stream", ".z", "application/octet-stream",
    ".lha", "application/octet-stream", ".lzh", "application/octet-stream",
    ".cab", "application/octet-stream", ".rar", "application/octet-stream",
    ".sit", "application/octet-stream", ".bin", "application/octet-stream",
    ".o", "application/octet-stream", ".so", "application/octet-stream",
    ".exe", "application/octet-stream", ".dll", "application/octet-stream",
    ".class", "application/octet-stream", ".png", "image/png",
    ".gif", "image/gif", ".jpg", "image/jpeg",
    ".jpeg", "image/jpeg", ".tif", "image/tiff",
    ".tiff", "image/tiff", ".bmp", "image/bmp",
    ".au", "audio/basic", ".snd", "audio/basic",
    ".mid", "audio/midi", ".midi", "audio/midi",
    ".mp2", "audio/mpeg", ".mp3", "audio/mpeg",
    ".wav", "audio/x-wav", ".mpg", "video/mpeg",
    ".mpeg", "video/mpeg", ".qt", "video/quicktime",
    ".mov", "video/quicktime", ".avi", "video/x-msvideo",
    NULL
  };
  int i;
  assert(ext);
  for(i = 0; list[i]; i++){
    if(!cbstricmp(ext, list[i])) return list[i+1];
  }
  return "application/octet-stream";
}


/*************************************************************************************************
 * private objects
 *************************************************************************************************/


/* Count the number of missing characters when converting.
   `ptr' specifies the pointer to a region.
   `size' specifies the size of the region.
   `icode' specifies the name of encoding of the input string.
   `ocode' specifies the name of encoding of the output string.
   The return value is the number of missing characters. */
static int est_enc_miss(const char *ptr, int size, const char *icode, const char *ocode){
  iconv_t ic;
  char obuf[ESTICCHECKSIZ], *wp, *rp;
  size_t isiz, osiz;
  int miss;
  assert(ptr && size >= 0 && icode && ocode);
  isiz = size;
  if((ic = iconv_open(ocode, icode)) == (iconv_t)-1) return ESTICMISSMAX;
  miss = 0;
  rp = (char *)ptr;
  while(isiz > 0){
    osiz = ESTICCHECKSIZ;
    wp = obuf;
    if(iconv(ic, (void *)&rp, &isiz, &wp, &osiz) == -1){
      if(errno == EILSEQ || errno == EINVAL){
        rp++;
        isiz--;
        miss++;
        if(miss >= ESTICMISSMAX) break;
      } else {
        break;
      }
    }
  }
  if(iconv_close(ic) == -1) return ESTICMISSMAX;
  return miss;
}


/* Normalize a text.
   `utext' specifies a text whose encoding is UTF-16BE.
   `size' specifies the size of the text.
   `sp' specifies the pointer to a variable to which the size of the result is assigned. */
static void est_normalize_text(unsigned char *utext, int size, int *sp){
  int i, wi;
  assert(utext && size >= 0 && sp);
  wi = 0;
  for(i = 0; i < size - 1; i += 2){
    if(utext[i] == 0x0 && (utext[i+1] <= 0x8 || (utext[i+1] >= 0x0e && utext[i+1] <= 0x1f))){
      /* control characters */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0x0 && utext[i+1] == 0xa0){
      /* no-break space */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0x20 && utext[i+1] == 0x2){
      /* en space */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0x20 && utext[i+1] == 0x3){
      /* em space */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0x20 && utext[i+1] == 0x9){
      /* thin space */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0x30 && utext[i+1] == 0x0){
      /* fullwidth space */
      utext[wi] = 0x0;
      utext[wi+1] = 0x20;
    } else if(utext[i] == 0xff){
      if(utext[i+1] >= 0x21 && utext[i+1] <= 0x3a){
        /* fullwidth alphabets */
        utext[wi] = 0x0;
        utext[wi+1] = utext[i+1] - 0x21 + 0x41;
      } else if(utext[i+1] >= 0x41 && utext[i+1] <= 0x5a){
        /* fullwidth small alphabets */
        utext[wi] = 0x0;
        utext[wi+1] = utext[i+1] - 0x41 + 0x61;
      } else if(utext[i+1] >= 0x10 && utext[i+1] <= 0x19){
        /* fullwidth numbers */
        utext[wi] = 0x0;
        utext[wi+1] = utext[i+1] - 0x10 + 0x30;
      } else if(utext[i+1] == 0x61){
        /* halfwidth full stop */
        utext[wi] = 0x30;
        utext[wi+1] = 0x2;
      } else if(utext[i+1] == 0x62){
        /* halfwidth left corner */
        utext[wi] = 0x30;
        utext[wi+1] = 0xc;
      } else if(utext[i+1] == 0x63){
        /* halfwidth right corner */
        utext[wi] = 0x30;
        utext[wi+1] = 0xd;
      } else if(utext[i+1] == 0x64){
        /* halfwidth comma */
        utext[wi] = 0x30;
        utext[wi+1] = 0x1;
      } else if(utext[i+1] == 0x65){
        /* halfwidth middle dot */
        utext[wi] = 0x30;
        utext[wi+1] = 0xfb;
      } else if(utext[i+1] == 0x66){
        /* halfwidth wo */
        utext[wi] = 0x30;
        utext[wi+1] = 0xf2;
      } else if(utext[i+1] >= 0x67 && utext[i+1] <= 0x6b){
        /* halfwidth small a-o */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x67) * 2 + 0xa1;
      } else if(utext[i+1] >= 0x6c && utext[i+1] <= 0x6e){
        /* halfwidth small ya-yo */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x6c) * 2 + 0xe3;
      } else if(utext[i+1] == 0x6f){
        /* halfwidth small tu */
        utext[wi] = 0x30;
        utext[wi+1] = 0xc3;
      } else if(utext[i+1] == 0x70){
        /* halfwidth prolonged mark */
        utext[wi] = 0x30;
        utext[wi+1] = 0xfc;
      } else if(utext[i+1] >= 0x71 && utext[i+1] <= 0x75){
        /* halfwidth a-o */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x71) * 2 + 0xa2;
        if(i + 2 < size - 1 && utext[i+1] == 0x73 && utext[i+2] == 0xff && utext[i+3] == 0x9e){
          utext[wi+1] = 0xf4;
          i += 2;
        }
      } else if(utext[i+1] >= 0x76 && utext[i+1] <= 0x7a){
        /* halfwidth ka-ko */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x76) * 2 + 0xab;
        if(i + 2 < size - 1 && utext[i+2] == 0xff && utext[i+3] == 0x9e){
          utext[wi+1] += 1;
          i += 2;
        }
      } else if(utext[i+1] >= 0x7b && utext[i+1] <= 0x7f){
        /* halfwidth sa-so */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x7b) * 2 + 0xb5;
        if(i + 2 < size - 1 && utext[i+2] == 0xff && utext[i+3] == 0x9e){
          utext[wi+1] += 1;
          i += 2;
        }
      } else if(utext[i+1] >= 0x80 && utext[i+1] <= 0x84){
        /* halfwidth ta-to */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x80) * 2 + 0xbf + (utext[i+1] >= 0x82 ? 1 : 0);
        if(i + 2 < size - 1 && utext[i+2] == 0xff && utext[i+3] == 0x9e){
          utext[wi+1] += 1;
          i += 2;
        }
      } else if(utext[i+1] >= 0x85 && utext[i+1] <= 0x89){
        /* halfwidth na-no */
        utext[wi] = 0x30;
        utext[wi+1] = utext[i+1] - 0x85 + 0xca;
      } else if(utext[i+1] >= 0x8a && utext[i+1] <= 0x8e){
        /* halfwidth ha-ho */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x8a) * 3 + 0xcf;
        if(i + 2 < size - 1){
          if(utext[i+2] == 0xff && utext[i+3] == 0x9e){
            utext[wi+1] += 1;
            i += 2;
          } else if(utext[i+2] == 0xff && utext[i+3] == 0x9f){
            utext[wi+1] += 2;
            i += 2;
          }
        }
      } else if(utext[i+1] >= 0x8f && utext[i+1] <= 0x93){
        /* halfwidth ma-mo */
        utext[wi] = 0x30;
        utext[wi+1] = utext[i+1] - 0x8f + 0xde;
      } else if(utext[i+1] >= 0x94 && utext[i+1] <= 0x96){
        /* halfwidth ya-yo */
        utext[wi] = 0x30;
        utext[wi+1] = (utext[i+1] - 0x94) * 2 + 0xe4;
      } else if(utext[i+1] >= 0x97 && utext[i+1] <= 0x9b){
        /* halfwidth ra-ro */
        utext[wi] = 0x30;
        utext[wi+1] = utext[i+1] - 0x97 + 0xe9;
      } else if(utext[i+1] == 0x9c){
        /* halfwidth wa */
        utext[wi] = 0x30;
        utext[wi+1] = 0xef;
      } else if(utext[i+1] == 0x9d){
        /* halfwidth wo */
        utext[wi] = 0x30;
        utext[wi+1] = 0xf3;
      } else {
        utext[wi] = utext[i];
        utext[wi+1] = utext[i+1];
      }
    } else {
      utext[wi] = utext[i];
      utext[wi+1] = utext[i+1];
    }
    wi += 2;
  }
  *sp = wi;
}


/* Canonicalize a text for search keys.
   `utext' specifies a text whose encoding is UTF-16BE.
   `size' specifies the size of the text.
   `funcspc' specifies whether to allow functional space characters. */
static void est_canonicalize_text(unsigned char *utext, int size, int funcspc){
  int i;
  for(i = 0; i < size; i += 2){
    if(utext[i] == 0x0){
      if(utext[i+1] >= 'A' && utext[i+1] <= 'Z'){
        /* ascii */
        utext[i+1] += 'a' - 'A';
      } else if((utext[i+1] >= 0xc0 && utext[i+1] <= 0xd6) ||
                (utext[i+1] >= 0xd8 && utext[i+1] <= 0xde)){
        /* latin-1 supplement */
        utext[i+1] += 0x20;
      } else if(!funcspc && utext[i+1] < ' '){
        /* functional spaces */
        utext[i+1] = ' ';
      }
    } else if(utext[i] == 0x1){
      if((utext[i+1] <= 0x36 && utext[i+1] % 2 == 0) ||
         (utext[i+1] >= 0x39 && utext[i+1] <= 0x47 && utext[i+1] % 2 == 1) ||
         (utext[i+1] >= 0x4a && utext[i+1] <= 0x76 && utext[i+1] % 2 == 0) ||
         (utext[i+1] >= 0x79 && utext[i+1] <= 0x7d && utext[i+1] % 2 == 1)){
        /* latin extended-a */
        utext[i+1] += 0x1;
      } else if(utext[i+1] == 0x78){
        /* y with umlaut */
        utext[i] = 0x0;
        utext[i+1] = 0xff;
      }
    } else if(utext[i] == 0x3){
      if(utext[i+1] >= 0x91 && utext[i+1] <= 0xa9){
        /* greek */
        utext[i+1] += 0x20;
      }
    } else if(utext[i] == 0x4){
      if(utext[i+1] >= 0x10 && utext[i+1] <= 0x2f){
        /* cyrillic */
        utext[i+1] += 0x20;
      } else if(utext[i+1] <= 0x0f){
        /* cyrillic with mark */
        utext[i+1] += 0x50;
      }
    } else if(utext[i] == 0xff){
      if(utext[i] >= 0xf0){
        /* special */
        utext[i] = 0x0;
        utext[i+1] = ' ';
      }
    }
  }
}


/* Categorize a character.
   `c' specifies the UCS number of a character.
   The return value is the category of the character. */
static int est_char_category(int c){
  /* ascii space */
  if(c <= 0x0020) return ESTSPACECHR;
  /* ascii alnum */
  if((c >= 0x0030 && c <= 0x0039) || (c >= 0x0041 && c <= 0x005a) ||
     (c >= 0x0061 && c <= 0x007a)) return ESTWESTALPH;
  /* latin */
  if((c >= 0x00c0 && c <= 0x00ff && c != 0x00d7 && c != 0x00f7) || (c >= 0x0100 && c <= 0x017f))
    return ESTWESTALPH;
  /* arabic and syrian */
  if(c >= 0x0600 && c <= 0x08ff) return ESTEASTALPH;
  /* south and south east asia */
  if((c >= 0x0900 && c <= 0x109f) || (c >= 0x1700 && c <= 0x1cff)) return ESTEASTALPH;
  /* cjk */
  if((c >= 0x1100 && c <= 0x11ff) || (c >= 0x2e80 && c <= 0xd7af) ||
     (c >= 0xf900 && c <= 0xfaff) || (c >= 0xff00 && c <= 0xffef)) return ESTEASTALPH;
  /* asian presentation forms */
  if((c >= 0xfb50 && c <= 0xfdff) || (c >= 0xfe30 && c <= 0xfe4f) ||
     (c >= 0xfe70 && c <= 0xfeff)) return ESTEASTALPH;
  /* others */
  return ESTDELIMCHR;
}


/* Categorize a character for perfect N-gram analyzer.
   `c' specifies the UCS number of a character.
   The return value is the category of the character. */
static int est_char_category_perfng(int c){
  if(c <= 0x0020) return ESTSPACECHR;
  return ESTEASTALPH;
}


/* Convert a simplified phrase into complete form.
   `sphrase' specifies a simplified phrase.
   The return value is the complete form of the phrase. */
static char *est_phrase_from_thumb(const char *sphrase){
  CBDATUM *datum;
  const char *oper, *rp;
  unsigned char *utext;
  char *rtext;
  int size, quote;
  assert(sphrase);
  datum = cbdatumopen("", 0);
  utext = (unsigned char *)est_uconv_in(sphrase, strlen(sphrase), &size);
  est_normalize_text(utext, size, &size);
  est_canonicalize_text(utext, size, FALSE);
  rtext = est_uconv_out((char *)utext, size, NULL);
  cbstrsqzspc(rtext);
  quote = FALSE;
  oper = NULL;
  for(rp = rtext; *rp != '\0'; rp++){
    if(*rp == '"'){
      if(oper){
        cbdatumcat(datum, oper, -1);
        oper = NULL;
      }
      quote = !quote;
      continue;
    }
    if(quote){
      cbdatumcat(datum, rp, 1);
      continue;
    }
    switch(*rp){
    case ' ':
      if(!oper) oper = " AND ";
      break;
    case '&':
      oper = " AND ";
      break;
    case '|':
      oper = " OR ";
      break;
    case '!':
      oper = " ANDNOT ";
      break;
    default:
      if(oper){
        cbdatumcat(datum, oper, -1);
        oper = NULL;
      }
      cbdatumcat(datum, rp, 1);
    }
  }
  free(rtext);
  free(utext);
  return cbdatumtomalloc(datum, NULL);
}


/* Add a string to a snippet.
   `rtext' specifies a raw text.
   `ctext' specifies a canonicalized text.
   `size' specifies the size of the raw text and the canonicalized text.
   `awsiz' specifies the size of allowance for matching words.
   `res' specifies a datum object for the result.
   `rwords' specifies a list object of raw words. */
static void est_snippet_add_text(const unsigned char *rtext, const unsigned char *ctext,
                                 int size, int awsiz, CBDATUM *res, const CBLIST *rwords){
  const unsigned char *rword;
  char *orig;
  int i, j, bi, rwsiz, step, osiz;
  bi = 0;
  for(i = 0; i < size; i += 2){
    for(j = 0; j < CB_LISTNUM(rwords); j++){
      rword = (unsigned char *)CB_LISTVAL2(rwords, j, &rwsiz);
      if((step = est_str_fwmatch_wide(ctext + i, size + awsiz - i, rword, rwsiz)) > 0){
        if(i - bi > 0){
          orig = est_uconv_out((char *)rtext + bi, i - bi, &osiz);
          cbdatumcat(res, orig, osiz);
          cbdatumcat(res, "\n", 1);
          free(orig);
        }
        orig = est_uconv_out((char *)rtext + i, step, &osiz);
        cbdatumcat(res, orig, osiz);
        free(orig);
        cbdatumcat(res, "\t", 1);
        orig = est_uconv_out((char *)rword, rwsiz, &osiz);
        cbdatumcat(res, orig, osiz);
        free(orig);
        cbdatumcat(res, "\n", 1);
        bi = i + step;
        i = bi - 2;
        break;
      }
    }
  }
  if(i - bi > 0){
    orig = est_uconv_out((char *)rtext + bi, i - bi, &osiz);
    cbdatumcat(res, orig, osiz);
    cbdatumcat(res, "\n", 1);
    free(orig);
  }
}


/* Check whether a string begins with a key.
   `string' specifies a target string whose encoding is UTF-16BE.
   `size' specifies the size of the target string.
   `key' specifies a key string whose encoding is UTF-16BE.
   `ksiz' specifies the size of the key string.
   `key' specifies the pointer
   The return value is the number of characters of the corresponding string, or 0 if the target
   string does not begin with the key. */
static int est_str_fwmatch_wide(const unsigned char *str, int size,
                                const unsigned char *key, int ksiz){
  int si, ki;
  assert(str && size >= 0 && key && ksiz >= 0);
  if(size < 2 || ksiz < 2 || (str[0] == 0x0 && str[1] <= 0x20)) return 0;
  si = 0;
  ki = 0;
  while(ki < ksiz){
    if(si >= size) return 0;
    if(str[si] == 0x0 && str[si+1] <= 0x20){
      si += 2;
      continue;
    }
    if(key[ki] == 0x0 && key[ki+1] <= 0x20){
      ki += 2;
      continue;
    }
    if(str[si] != key[ki] || str[si+1] != key[ki+1]) return 0;
    si += 2;
    ki += 2;
  }
  return si;
}


/* Open the inverted index.
   `name' specifies the name of a directory.
   `omode' specifies an open mode of Villa.
   `dnum' specifies the number of database files.
   The return value is a database object of the database. */
static ESTIDX *est_idx_open(const char *name, int omode, int dnum){
  ESTIDX *idx;
  CBLIST *files;
  char path[ESTPATHBUFSIZ];
  int i;
  assert(name && dnum > 0);
  if(dnum > ESTIDXDMAX) dnum = ESTIDXDMAX;
  CB_MALLOC(idx, sizeof(ESTIDX));
  if((omode & VL_OCREAT) && !est_mkdir(name) && errno != EEXIST) return NULL;
  if((omode & VL_OTRUNC) && (files = cbdirlist(name)) != NULL){
    for(i = 0; i < CB_LISTNUM(files); i++){
      sprintf(path, "%s%c%s", name, ESTPATHCHR, CB_LISTVAL(files, i, NULL));
      unlink(path);
    }
    cblistclose(files);
  }
  for(i = 0; i < dnum; i++){
    sprintf(path, "%s%c%04d", name, ESTPATHCHR, i + 1);
    if(!(idx->dbs[i] = vlopen(path, omode, VL_CMPLEX))){
      while(--i >= 0){
        vlclose(idx->dbs[i]);
      }
      return NULL;
    }
  }
  idx->name = cbmemdup(name, -1);
  idx->omode = omode;
  idx->dnum = dnum;
  idx->cdb = idx->dbs[dnum-1];
  return idx;
}


/* Close the inverted index.
   `idx' specifies an object of the inverted index.
   The return value is true if success, else it is false. */
static int est_idx_close(ESTIDX *idx){
  int i, err;
  assert(idx);
  err = FALSE;
  for(i = 0; i < idx->dnum; i++){
    if(!vlclose(idx->dbs[i])) err = TRUE;
  }
  free(idx->name);
  free(idx);
  return err ? FALSE : TRUE;
}


/* Set the tuning parameters of the inverted index.
   `idx' specifies an object of the inverted index.
   Other parameters are same with `vlsettuning' of Villa. */
static void est_idx_set_tuning(ESTIDX *idx, int lrecmax, int nidxmax, int lcnum, int ncnum){
  int i;
  assert(idx);
  for(i = 0; i < idx->dnum; i++){
    vlsettuning(idx->dbs[i], lrecmax, nidxmax, lcnum, ncnum);
  }
}


/* Increment the inverted index.
   `idx' specifies an object of the inverted index. */
static void est_idx_increment(ESTIDX *idx){
  char path[ESTPATHBUFSIZ];
  if(idx->dnum >= ESTIDXDMAX){
    est_idx_set_current(idx);
    return;
  }
  sprintf(path, "%s%c%04d", idx->name, ESTPATHCHR, idx->dnum + 1);
  if((idx->dbs[idx->dnum] = vlopen(path, idx->omode | VL_OCREAT | VL_OTRUNC, VL_CMPLEX)) != NULL){
    idx->cdb = idx->dbs[idx->dnum];
    idx->dnum++;
  }
}


/* Add a record to the inverted index.
   `idx' specifies an object of the inverted index.
   `word' specifies a word.
   `vbuf' specifies the pointer to the value of a record.
   `vsiz' specifies the size of the value.
   The return value is true if success, else it is false. */
static int est_idx_add(ESTIDX *idx, const char *word, int wsiz, const char *vbuf, int vsiz){
  assert(idx && word && wsiz >= 0 && vbuf && vsiz >= 0);
  return vlput(idx->cdb, word, wsiz, vbuf, vsiz, VL_DDUP);
}


/* Remove a record from the inverted index.
   `idx' specifies an object of the inverted index.
   `word' specifies a word.
   `wsiz' specifies the size of the word.
   The return value is true if success, else it is false.  Even if no item correspongs, it is
   success. */
static int est_idx_out(ESTIDX *idx, const char *word, int wsiz){
  int i, err;
  assert(idx && word && wsiz >= 0);
  err = FALSE;
  for(i = 0; i < idx->dnum; i++){
    if(!vloutlist(idx->dbs[i], word, wsiz) && dpecode != DP_ENOITEM) err = TRUE;
  }
  return err ? FALSE : TRUE;
}


/* Get a record from the inverted index.
   `idx' specifies an object of the inverted index.
   `word' specifies a word.
   `wsiz' specifies the size of the word.
   `sp' specifies the pointer to a variable to which the size of the region of the return value
   is assigned.
   The return value is the pointer to the region of the value of the corresponding record.
   if no item correspongs, empty region is returned. */
static char *est_idx_get(ESTIDX *idx, const char *word, int wsiz, int *sp){
  CBDATUM *datum;
  char *vbuf;
  int i, vsiz;
  assert(idx && word && wsiz >= 0 && sp);
  datum = cbdatumopen("", 0);
  for(i = 0; i < idx->dnum; i++){
    if(!(vbuf = vlgetcat(idx->dbs[i], word, wsiz, &vsiz))) continue;
    cbdatumcat(datum, vbuf, vsiz);
    free(vbuf);
  }
  return cbdatumtomalloc(datum, sp);
}


/* Get the size of the value of a record in the inverted index.
   `idx' specifies an object of the inverted index.
   `word' specifies a word.
   `wsiz' specifies the size of the word.
   The return value is the size of the value of the corresponding record.
   if no item correspongs, 0 is returned. */
static int est_idx_vsiz(ESTIDX *idx, const char *word, int wsiz){
  char *vbuf;
  int i, sum, vsiz;
  assert(idx && word && wsiz >= 0);
  sum = 0;
  for(i = 0; i < idx->dnum; i++){
    if(!(vbuf = vlgetcat(idx->dbs[i], word, wsiz, &vsiz))) continue;
    sum += vsiz;
    free(vbuf);
  }
  return sum;
}


/* Get the number of division of the inverted index.
   `idx' specifies an object of the inverted index.
   The return value is the number of division of the inverted index. */
static int est_idx_num(ESTIDX *idx){
  assert(idx);
  return idx->dnum;
}


/* Get the size of the inverted index.
   `idx' specifies an object of the inverted index.
   The return value is the size of the inverted index. */
static int est_idx_size(ESTIDX *idx){
  int i, size;
  assert(idx);
  size = 0;
  for(i = 0; i < idx->dnum; i++){
    size += vlfsiz(idx->dbs[i]);
  }
  return size;
}


/* Syncronize the inverted index.
   `idx' specifies an object of the inverted index.
   The return value is the size of the inverted index. */
static int est_idx_sync(ESTIDX *idx){
  int i;
  assert(idx);
  for(i = 0; i < idx->dnum; i++){
    if(!vlsync(idx->dbs[i])) return FALSE;
  }
  return TRUE;
}


/* Optimize the inverted index.
   `idx' specifies an object of the inverted index.
   The return value is the size of the inverted index. */
static int est_idx_optimize(ESTIDX *idx){
  int i;
  assert(idx);
  for(i = 0; i < idx->dnum; i++){
    if(!vloptimize(idx->dbs[i])) return FALSE;
  }
  return TRUE;
}


/* Set the current database to the smallest one in the inverted index.
   `idx' specifies an object of the inverted index. */
static void est_idx_set_current(ESTIDX *idx){
  int i, size, min;
  assert(idx);
  min = vlfsiz(idx->cdb);
  for(i = 0; i < idx->dnum; i++){
    if((size = vlfsiz(idx->dbs[i])) < min){
      idx->cdb = idx->dbs[i];
      min = size;
    }
  }
}


/* Write meta data to the database.
   `db' specifies a database object.
   The return value is true if success, else it is false. */
static int est_db_write_meta(ESTDB *db){
  char vbuf[ESTNUMBUFSIZ], *sbuf;
  int err, ssiz;
  assert(db);
  err = FALSE;
  sprintf(vbuf, "%d", est_idx_num(db->idxdb));
  if(!dpput(db->metadb, ESTKEYIDXNUM, -1, vbuf, -1, DP_DOVER)) err = TRUE;
  sprintf(vbuf, "%d", db->dseq);
  if(!dpput(db->metadb, ESTKEYDSEQ, -1, vbuf, -1, DP_DOVER)) err = TRUE;
  sprintf(vbuf, "%d", db->dnum);
  if(!dpput(db->metadb, ESTKEYDNUM, -1, vbuf, -1, DP_DOVER)) err = TRUE;
  sprintf(vbuf, "%d", db->amode);
  if(!dpput(db->metadb, ESTKEYAMODE, -1, vbuf, -1, DP_DOVER)) err = TRUE;
  if(db->metacc){
    sbuf = cbmapdump(db->metacc, &ssiz);
    if(!dpput(db->metadb, ESTKEYMETA, -1, sbuf, ssiz, DP_DOVER)) err = TRUE;
    free(sbuf);
  }
  if(err){
    db->ecode = ESTEDB;
    db->fatal = TRUE;
  }
  return err ? FALSE : TRUE;
}


/* Call the callback function of a database.
   `db' specifies a database object.
   `info' specifies an extra message. */
static void est_db_inform(ESTDB *db, const char *info){
  char *msg;
  assert(db);
  if(!db->cbinfo) return;
  msg = cbsprintf("%s: name=%s dnum=%d wnum=%d fsiz=%.0f crnum=%d csiz=%.0f",
                  info, db->name, db->dnum, vlrnum(db->fwmdb), (double)est_db_size(db),
                  cbmaprnum(db->idxcc), (double)est_db_used_cache_size(db));
  db->cbinfo(msg);
  free(msg);
}


/* Get the size of used cache region.
   `db' specifies a database object.
   The return value is the size of used cache region. */
static int est_db_used_cache_size(ESTDB *db){
  assert(db);
  return (db->icsiz + cbmaprnum(db->idxcc) * (sizeof(CBMAPDATUM) + ESTWORDAVGLEN)) * ESTMEMIRATIO;
}


/* Prepare cache for meta data.
   `db' specifies a database object. */
static void est_db_prepare_meta(ESTDB *db){
  char *sbuf;
  int ssiz;
  assert(db);
  if((sbuf = dpget(db->metadb, ESTKEYMETA, -1, 0, -1, &ssiz)) != NULL){
    db->metacc = cbmapload(sbuf, ssiz);
    free(sbuf);
  } else {
    db->metacc = cbmapopenex(ESTMINIBNUM);
  }
}


/* Create a list of terms for search.
   `phrase' specifies a search phrase.
   The return value is a list object of the terms of the phrase. */
static CBLIST *est_phrase_terms(const char *phrase){
  CBLIST *terms, *elems;
  CBDATUM *datum;
  const char *elem;
  char *tbuf, *pbuf;
  int i, tsiz, psiz, lw;
  assert(phrase);
  terms = cblistopen();
  tbuf = est_uconv_in(phrase, strlen(phrase), &tsiz);
  est_normalize_text((unsigned char *)tbuf, tsiz, &tsiz);
  pbuf = est_uconv_out(tbuf, tsiz, &psiz);
  elems = cbsplit(pbuf, psiz, "\a\b\t\n\v\f\r ");
  datum = cbdatumopen("", 0);
  lw = FALSE;
  for(i = 0; i < CB_LISTNUM(elems); i++){
    elem = CB_LISTVAL(elems, i, NULL);
    if(elem[0] == '\0') continue;
    if(!strcmp(elem, ESTOPUNION)){
      if(CB_DATUMSIZE(datum) < 1) continue;
      if(lw) cbdatumcat(datum, "\t", -1);
      lw = FALSE;
    } else if(!strcmp(elem, ESTOPISECT) || !strcmp(elem, ESTOPDIFF)){
      if(CB_DATUMSIZE(datum) < 1) continue;
      cblistpush(terms, CB_DATUMPTR(datum), CB_DATUMSIZE(datum));
      cbdatumsetsize(datum, 0);
      cblistpush(terms, elem, -1);
      lw = FALSE;
    } else {
      if(CB_DATUMSIZE(datum) > 0 && lw) cbdatumcat(datum, " ", 1);
      cbdatumcat(datum, elem, -1);
      lw = TRUE;
    }
  }
  if(CB_DATUMSIZE(datum) > 0) cblistpush(terms, CB_DATUMPTR(datum), CB_DATUMSIZE(datum));
  cbdatumclose(datum);
  cblistclose(elems);
  free(pbuf);
  free(tbuf);
  for(i = 0; i < CB_LISTNUM(terms); i++){
    elem = CB_LISTVAL(terms, i, NULL);
    if(!strcmp(elem, ESTOPUVSET) || !strcmp(elem, ESTOPISECT) ||
       !strcmp(elem, ESTOPDIFF)) continue;
    tbuf = est_uconv_in(elem, strlen(elem), &tsiz);
    est_canonicalize_text((unsigned char *)tbuf, tsiz, TRUE);
    pbuf = est_uconv_out(tbuf, tsiz, &psiz);
    cbstrtrim(pbuf);
    cblistover(terms, i, pbuf, -1);
    free(pbuf);
    free(tbuf);
  }
  for(i = CB_LISTNUM(terms) - 1; i >= 0; i--){
    elem = CB_LISTVAL(terms, i, NULL);
    if(strcmp(elem, ESTOPISECT) && strcmp(elem, ESTOPDIFF)) break;
    free(cblistpop(terms, NULL));
  }
  return terms;
}


/* Compare two scores by each ID.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_id(const void *ap, const void *bp){
  assert(ap && bp);
  return ((ESTSCORE *)ap)->id - ((ESTSCORE *)bp)->id;
}


/* Compare two scores by each score point.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_score(const void *ap, const void *bp){
  assert(ap && bp);
  return ((ESTSCORE *)bp)->score - ((ESTSCORE *)ap)->score;
}


/* Compare two scores by attributes of strings for ascending order.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_str_asc(const void *ap, const void *bp){
  assert(ap && bp);
  return strcmp(((ESTSCORE *)ap)->value, ((ESTSCORE *)bp)->value);
}


/* Compare two scores by attributes of strings for descending order.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_str_desc(const void *ap, const void *bp){
  assert(ap && bp);
  return strcmp(((ESTSCORE *)bp)->value, ((ESTSCORE *)ap)->value);
}


/* Compare two scores by attributes of numbers for ascending order.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_num_asc(const void *ap, const void *bp){
  assert(ap && bp);
  return (time_t)((ESTSCORE *)ap)->value - (time_t)((ESTSCORE *)bp)->value;
}


/* Compare two scores by attributes of numbers for descending order.
   `ap' specifies the pointer to one score.
   `bp' specifies the pointer to the other score.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_score_compare_by_num_desc(const void *ap, const void *bp){
  assert(ap && bp);
  return (time_t)((ESTSCORE *)bp)->value - (time_t)((ESTSCORE *)ap)->value;
}


/* Get the universal set of documents in a database.
   `db' specifies a database object.
   `nump' specifies the pointer to which the number of elements in the result is assigned.
   `hints' specifies a list object.  If it is `NULL', it is not used.
   `add' specifies whether the result to be treated in union or difference.
   The return value is an array whose elements are ID numbers of corresponding documents. */
static ESTSCORE *est_search_uvset(ESTDB *db, int *nump, CBMAP *hints, int add){
  ESTSCORE *scores;
  char *vbuf, numbuf[ESTNUMBUFSIZ];
  int snum, smax;
  assert(db && nump);
  smax = ESTALLOCUNIT;
  CB_MALLOC(scores, smax * sizeof(ESTSCORE));
  snum = 0;
  vlcurfirst(db->listdb);
  while((vbuf = vlcurval(db->listdb, NULL)) != NULL){
    if(snum >= smax){
      smax *= 2;
      CB_REALLOC(scores, smax * sizeof(ESTSCORE));
    }
    scores[snum].id = atoi(vbuf);
    scores[snum].score = 0;
    snum++;
    free(vbuf);
    vlcurnext(db->listdb);
  }
  *nump = snum;
  if(hints){
    sprintf(numbuf, "%d", snum * (add ? 1 : -1));
    cbmapput(hints, ESTOPUVSET, -1, numbuf, -1, FALSE);
  }
  return scores;
}


/* Expand a word to words which begins with it.
   `db' specifies a database object.
   `word' specifies a word.
   `list' specifies a list object to contain the results. */
static void est_expand_word(ESTDB *db, const char *word, CBLIST *list){
  char *kbuf;
  int ksiz;
  assert(db && word && list);
  vlcurjump(db->fwmdb, word, -1, VL_JFORWARD);
  while((kbuf = vlcurkey(db->fwmdb, &ksiz)) != NULL){
    if(!cbstrfwmatch(kbuf, word)){
      free(kbuf);
      break;
    }
    cblistpushbuf(list, kbuf, ksiz);
    vlcurnext(db->fwmdb);
  }
}


/* Get a correspinding set of documents in a database.
   `db' specifies a database object.
   `term' specifies a union term.
   `gstep' specifies number of steps of N-gram.
   `nump' specifies the pointer to which the number of elements in the result is assigned.
   `hints' specifies a list object.  If it is `NULL', it is not used.
   `add' specifies whether the result to be treated in union or difference.
   The return value is an array whose elements are ID numbers of corresponding documents. */
static ESTSCORE *est_search_union(ESTDB *db, const char *term, int gstep,
                                  int *nump, CBMAP *hints, int add){
  ESTSCORE *scores, *tscores;
  CBLIST *words, *grams;
  const char *word, *gram, *rp, *fnext, *snext, *cbuf;
  char *vbuf, numbuf[ESTNUMBUFSIZ];
  int i, j, k, snum, smax, single, tsmax, tsnum, vsiz, gcnum, gsiz, csiz, wgstep, nnum;
  int mfsiz, mssiz, mfhash, mshash, tfhash, tshash, id, score, hit, hnum;
  assert(db && term && gstep > 0 && nump);
  smax = ESTALLOCUNIT;
  CB_MALLOC(scores, smax * sizeof(ESTSCORE));
  snum = 0;
  words = cbsplit(term, -1, "\t");
  for(i = 0; i < CB_LISTNUM(words); i++){
    word = CB_LISTVAL(words, i, NULL);
    grams = cblistopen();
    switch(db->amode){
    case ESTAMPERFNG:
      est_break_text_perfng(word, grams, TRUE, FALSE);
      break;
    default:
      est_break_text(word, grams, TRUE, FALSE);
      break;
    }
    single = FALSE;
    if(CB_LISTNUM(grams) < 1){
      est_expand_word(db, word, grams);
      single = TRUE;
    }
    tsmax = ESTALLOCUNIT;
    CB_MALLOC(tscores, tsmax * sizeof(ESTSCORE));
    tsnum = 0;
    gcnum = 0;
    wgstep = CB_LISTNUM(grams) > 2 || gstep > 2 ? gstep : 1;
    if(((unsigned char *)word)[0] <= 0xdf && gstep <= 2) wgstep = 1;
    for(j = 0; j < CB_LISTNUM(grams); j += wgstep){
      gcnum++;
      gram = CB_LISTVAL2(grams, j, &gsiz);
      fnext = j < CB_LISTNUM(grams) - 1 ? CB_LISTVAL2(grams, j + 1, &mfsiz) : NULL;
      snext = j < CB_LISTNUM(grams) - 2 ? CB_LISTVAL2(grams, j + 2, &mssiz) : NULL;
      mfhash = fnext ? dpinnerhash(fnext, mfsiz) % ESTJHASHNUM + 1: 0xff;
      mshash = snext ? dpouterhash(snext, mssiz) % ESTJHASHNUM + 1: 0xff;
      vbuf = est_idx_get(db->idxdb, gram, gsiz, &vsiz);
      if((cbuf = cbmapget(db->idxcc, gram, gsiz, &csiz)) != NULL){
        if(vbuf){
          CB_REALLOC(vbuf, vsiz + csiz + 100);
          memcpy(vbuf + vsiz, cbuf, csiz);
          vsiz += csiz;
        } else {
          vbuf = cbmemdup(cbuf, csiz);
          vsiz = csiz;
        }
      }
      if(!vbuf) continue;
      rp = vbuf;
      while(rp < vbuf + vsiz){
        memcpy(&id, rp, sizeof(int));
        rp += sizeof(int);
        score = *(unsigned char *)rp;
        rp++;
        hit = mfhash == 0xff && mshash == 0xff;
        while(rp < vbuf + vsiz){
          tfhash = *(unsigned char *)rp;
          rp++;
          tshash = *(unsigned char *)rp;
          rp++;
          if((mfhash == 0xff || mfhash == tfhash) && (mshash == 0xff || mshash == tshash))
            hit = TRUE;
          if(*(unsigned char *)rp == 0x00){
            rp++;
            break;
          }
        }
        if(hit || single){
          if(tsnum >= tsmax){
            tsmax *= 2;
            CB_REALLOC(tscores, tsmax * sizeof(ESTSCORE));
          }
          tscores[tsnum].id = id;
          tscores[tsnum].score = score * 100;
          tsnum++;
        }
      }
      free(vbuf);
    }
    if(gcnum > 1){
      qsort(tscores, tsnum, sizeof(ESTSCORE), est_score_compare_by_id);
      nnum = 0;
      for(j = 0; j < tsnum; j++){
        id = tscores[j].id;
        score = tscores[j].score;
        hnum = 1;
        for(k = j + 1; k < tsnum && tscores[k].id == id; k++){
          score += tscores[k].score;
          hnum++;
        }
        if(hnum >= gcnum || single){
          tscores[nnum].id = id;
          tscores[nnum].score = score / hnum;
          nnum++;
        }
        j = k - 1;
      }
      tsnum = nnum;
    }
    if(hints){
      sprintf(numbuf, "%d", tsnum * (add ? 1 : -1));
      cbmapput(hints, word, -1, numbuf, -1, FALSE);
    }
    for(j = 0; j < tsnum; j++){
      if(snum >= smax){
        smax *= 2;
        CB_REALLOC(scores, smax * sizeof(ESTSCORE));
      }
      scores[snum].id = tscores[j].id;
      scores[snum].score = tscores[j].score;
      snum++;
    }
    free(tscores);
    cblistclose(grams);
  }
  cblistclose(words);
  qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_id);
  nnum = 0;
  for(i = 0; i < snum; i++){
    id = scores[i].id;
    score = scores[i].score;
    hnum = 1;
    for(j = i + 1; j < snum && scores[j].id == id; j++){
      score += scores[j].score;
      hnum++;
    }
    scores[nnum].id = id;
    scores[nnum].score = score / hnum;
    nnum++;
    i = j - 1;
  }
  *nump = nnum;
  return scores;
}


/* Narrow and sort scores of search candidates.
   `db' specifies a database object.
   `attrs' specifies a list object of narrowing attributes.
   `order' specifies an expression for sorting.
   `scores' specifies an array of scores of search candidates.
   `snum' specifies the number of the array.
   The return value is the new number of the array. */
static int est_narrow_scores(ESTDB *db, const CBLIST *attrs, const char *order,
                             ESTSCORE *scores, int snum){
  ESTCATTR *list;
  const char *otype, *cbuf, *rp, *pv, *ibuf;
  unsigned char *utmp;
  char *oname, *wp, *mbuf, *vbuf;
  int i, j, k, ci, oi, anum, tsiz, nnum, csiz, msiz, miss, vsiz, num, isiz, onlen;
  time_t tval;
  assert(db && scores && snum >= 0);
  ci = -1;
  oi = -1;
  oname = NULL;
  otype = NULL;
  if(order){
    oname = cbmemdup(order, -1);
    cbstrtrim(oname);
    otype = ESTORDSTRA;
    if((wp = strchr(oname, ' ')) != NULL){
      *wp = '\0';
      rp = wp + 1;
      while(*rp == ' '){
        rp++;
      }
      otype = rp;
    }
  }
  if(attrs){
    anum = CB_LISTNUM(attrs);
    CB_MALLOC(list, sizeof(ESTCATTR) * anum + 1);
    for(i = 0; i < anum; i++){
      list[i].name = NULL;
      list[i].oper = NULL;
      list[i].val = NULL;
      rp = CB_LISTVAL(attrs, i, NULL);
      while(*rp > 0 && *rp <= ' '){
        rp++;
      }
      if((pv = strchr(rp, ' ')) != NULL){
        list[i].nsiz = pv - rp;
        list[i].name = cbmemdup(rp, list[i].nsiz);
        rp = pv;
        while(*rp > 0 && *rp <= ' '){
          rp++;
        }
        if((pv = strchr(rp, ' ')) != NULL){
          list[i].oper = cbmemdup(rp, pv - rp);
          rp = pv;
          while(*rp > 0 && *rp <= ' '){
            rp++;
          }
          list[i].vsiz = strlen(rp);
          list[i].val = cbmemdup(rp, list[i].vsiz);
        } else {
          list[i].oper = cbmemdup(rp, -1);
        }
      } else {
        list[i].nsiz = strlen(rp);
        list[i].name = cbmemdup(rp, list[i].nsiz);
      }
      if(!list[i].oper){
        list[i].oper = cbmemdup("", 0);
      }
      if(!list[i].val){
        list[i].vsiz = 0;
        list[i].val = cbmemdup("", 0);
      }
    }
    for(i = 0; i < anum; i++){
      rp = list[i].oper;
      if(*rp == '!'){
        list[i].sign = FALSE;
        rp++;
      } else {
        list[i].sign = TRUE;
      }
      if(*rp == 'I' || *rp == 'i'){
        utmp = (unsigned char *)est_uconv_in(list[i].val, list[i].vsiz, &tsiz);
        est_normalize_text(utmp, tsiz, &tsiz);
        est_canonicalize_text(utmp, tsiz, FALSE);
        list[i].sval = (char *)est_uconv_out((char *)utmp, tsiz, &(list[i].ssiz));
        free(utmp);
        rp++;
      } else {
        list[i].sval = NULL;
        list[i].ssiz = 0;
      }
      list[i].num = cbstrmktime(list[i].val);
      if(!cbstricmp(rp, ESTOPSTREQ)){
        list[i].cop = ESTOPSTREQ;
      } else if(!cbstricmp(rp, ESTOPSTRNE)){
        list[i].cop = ESTOPSTRNE;
      } else if(!cbstricmp(rp, ESTOPSTRINC)){
        list[i].cop = ESTOPSTRINC;
      } else if(!cbstricmp(rp, ESTOPSTRBW)){
        list[i].cop = ESTOPSTRBW;
      } else if(!cbstricmp(rp, ESTOPSTREW)){
        list[i].cop = ESTOPSTREW;
      } else if(!cbstricmp(rp, ESTOPNUMEQ)){
        list[i].cop = ESTOPNUMEQ;
      } else if(!cbstricmp(rp, ESTOPNUMNE)){
        list[i].cop = ESTOPNUMNE;
      } else if(!cbstricmp(rp, ESTOPNUMGT)){
        list[i].cop = ESTOPNUMGT;
      } else if(!cbstricmp(rp, ESTOPNUMGE)){
        list[i].cop = ESTOPNUMGE;
      } else if(!cbstricmp(rp, ESTOPNUMLT)){
        list[i].cop = ESTOPNUMLT;
      } else if(!cbstricmp(rp, ESTOPNUMLE)){
        list[i].cop = ESTOPNUMLE;
      } else {
        list[i].cop = NULL;
      }
    }
    if(db->spacc){
      for(i = 0; i < anum; i++){
        if(!strcmp(list[i].name, db->scname)){
          ci = i;
          break;
        }
      }
    }
    if(oname){
      for(i = 0; i < anum; i++){
        if(!strcmp(list[i].name, oname)){
          oi = i;
          break;
        }
      }
    }
    nnum = 0;
    for(i = 0; i < snum; i++){
      scores[i].value = NULL;
      if(ci >= 0){
        if((cbuf = cbmapget(db->spacc, (char *)&(scores[i].id), sizeof(int), &csiz)) != NULL)
          cbmapmove(db->spacc, (char *)&(scores[i].id), sizeof(int), FALSE);
      } else {
        cbuf = NULL;
        csiz = 0;
      }
      mbuf = NULL;
      if((cbuf && anum == 1) ||
         (mbuf = crget(db->attrdb, (char *)&(scores[i].id), sizeof(int), 0, -1, &msiz)) != NULL){
        miss = FALSE;
        for(j = 0; !miss && j < anum; j++){
          if(list[j].nsiz < 1) continue;
          if(mbuf){
            vbuf = cbmaploadone(mbuf, msiz, list[j].name, list[j].nsiz, &vsiz);
          } else if(csiz != 1 || cbuf[0] != '\0'){
            vbuf = cbmemdup(cbuf, csiz);
            vsiz = csiz;
          } else {
            vbuf = NULL;
          }
          if(list[j].oper[0] == '\0'){
            if(!vbuf) miss = TRUE;
          } else {
            if(!vbuf){
              vbuf = cbmemdup("", 0);
              vsiz = 0;
            }
            if(!est_match_attr(vbuf, vsiz, list[j].cop, list[j].sign, list[j].val, list[j].vsiz,
                               list[j].sval, list[j].ssiz, list[j].num))
              miss = TRUE;
          }
          if(j == ci && !cbuf){
            if(vbuf){
              cbmapput(db->spacc, (char *)&(scores[i].id), sizeof(int), vbuf, vsiz, FALSE);
            } else {
              cbmapput(db->spacc, (char *)&(scores[i].id), sizeof(int), "", 1, FALSE);
            }
            if(cbmaprnum(db->spacc) > db->scmnum){
              num = db->scmnum * 0.1 + 1;
              cbmapiterinit(db->spacc);
              for(k = 0; k < num && (ibuf = cbmapiternext(db->spacc, &isiz)) != NULL; k++){
                cbmapout(db->spacc, ibuf, isiz);
              }
            }
          }
          if(j == oi){
            scores[i].value = vbuf;
          } else {
            free(vbuf);
          }
        }
        if(miss){
          free(scores[i].value);
        } else {
          scores[nnum++] = scores[i];
        }
      }
      free(mbuf);
    }
    snum = nnum;
    for(i = 0; i < anum; i++){
      free(list[i].sval);
      free(list[i].val);
      free(list[i].oper);
      free(list[i].name);
    }
    free(list);
  } else {
    for(i = 0; i < snum; i++){
      scores[i].value = NULL;
    }
  }
  if(oname){
    ci = db->spacc && !strcmp(oname, db->scname);
    onlen = strlen(oname);
    for(i = 0; i < snum; i++){
      if(scores[i].value) continue;
      if(ci && (cbuf = cbmapget(db->spacc, (char *)&(scores[i].id), sizeof(int), &csiz)) != NULL){
        cbmapmove(db->spacc, (char *)&(scores[i].id), sizeof(int), FALSE);
        if(csiz == 1 && cbuf[0] == '\0'){
          scores[i].value = cbmemdup("", 0);
        } else {
          scores[i].value = cbmemdup(cbuf, csiz);
        }
        continue;
      }
      if((mbuf = crget(db->attrdb, (char *)&(scores[i].id), sizeof(int), 0, -1, &msiz)) != NULL){
        if((vbuf = cbmaploadone(mbuf, msiz, oname, onlen, &vsiz)) != NULL){
          if(ci) cbmapput(db->spacc, (char *)&(scores[i].id), sizeof(int), vbuf, vsiz, FALSE);
          scores[i].value = vbuf;
        } else {
          if(ci) cbmapput(db->spacc, (char *)&(scores[i].id), sizeof(int), "", 1, FALSE);
          scores[i].value = cbmemdup("", 0);
        }
        if(ci && cbmaprnum(db->spacc) > db->scmnum){
          num = db->scmnum * 0.1 + 1;
          cbmapiterinit(db->spacc);
          for(j = 0; j < num && (ibuf = cbmapiternext(db->spacc, &isiz)) != NULL; j++){
            cbmapout(db->spacc, ibuf, isiz);
          }
        }
        free(mbuf);
      } else {
        scores[i].value = cbmemdup("", 0);
      }
    }
    if(!cbstricmp(otype, ESTORDSTRA)){
      qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_str_asc);
    } else if(!cbstricmp(otype, ESTORDSTRD)){
      qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_str_desc);
    } else if(!cbstricmp(otype, ESTORDNUMA)){
      for(i = 0; i < snum; i++){
        tval = cbstrmktime(scores[i].value);
        free(scores[i].value);
        scores[i].value = (void *)tval;
      }
      qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_num_asc);
      for(i = 0; i < snum; i++){
        scores[i].value = NULL;
      }
    } else if(!cbstricmp(otype, ESTORDNUMD)){
      for(i = 0; i < snum; i++){
        tval = cbstrmktime(scores[i].value);
        free(scores[i].value);
        scores[i].value = (void *)tval;
      }
      qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_num_desc);
      for(i = 0; i < snum; i++){
        scores[i].value = NULL;
      }
    }
    for(i = 0; i < snum; i++){
      free(scores[i].value);
    }
    free(oname);
  }
  return snum;
}


/* Check whether a score matches an attribute condition.
   `tval' specifies the target value;
   `tsiz' specifies the size of the target value
   `oval' specifies the operation value;
   `osiz' specifies the size of the operation value
   `sval' specifies the operation value of small cases;
   `ssiz' specifies the size of the operation value of small cases.
   `onum' specifies the numeric value.
   The return value is true if it does match, else it is false. */
static int est_match_attr(const char *tval, int tsiz, const char *cop, int sign,
                          const char *oval, int osiz, const char *sval, int ssiz, int onum){
  unsigned char *eval;
  char *cval;
  int csiz, esiz, hit;
  assert(tval && tsiz >= 0 && oval && osiz >= 0);
  cval = NULL;
  if(sval){
    eval = (unsigned char *)est_uconv_in(tval, tsiz, &esiz);
    est_normalize_text(eval, esiz, &esiz);
    est_canonicalize_text(eval, esiz, FALSE);
    cval = (char *)est_uconv_out((char *)eval, esiz, &csiz);
    free(eval);
    tval = cval;
    tsiz = csiz;
    oval = sval;
    osiz = ssiz;
  }
  if(cop == ESTOPSTREQ){
    hit = !strcmp(tval, oval);
  } else if(cop == ESTOPSTRNE){
    hit = strcmp(tval, oval) != 0;
  } else if(cop == ESTOPSTRINC){
    hit = strstr(tval, oval) != NULL;
  } else if(cop == ESTOPSTRBW){
    hit = cbstrfwmatch(tval, oval);
  } else if(cop == ESTOPSTREW){
    hit = cbstrbwmatch(tval, oval);
  } else if(cop == ESTOPNUMEQ){
    hit = cbstrmktime(tval) == onum;
  } else if(cop == ESTOPNUMNE){
    hit = cbstrmktime(tval) != onum;
  } else if(cop == ESTOPNUMGT){
    hit = cbstrmktime(tval) > onum;
  } else if(cop == ESTOPNUMGE){
    hit = cbstrmktime(tval) >= onum;
  } else if(cop == ESTOPNUMLT){
    hit = cbstrmktime(tval) < onum;
  } else if(cop == ESTOPNUMLE){
    hit = cbstrmktime(tval) <= onum;
  } else {
    hit = FALSE;
  }
  free(cval);
  return sign ? hit : !hit;
}


/* Compare two keywords by scores in descending order.
   `ap' specifies the pointer to one keyword.
   `bp' specifies the pointer to the other keyword.
   The return value is negative if one is small, positive if one is big, 0 if both are equal. */
static int est_keysc_compare(const void *ap, const void *bp){
  assert(ap && bp);
  return ((ESTKEYSC *)bp)->pt - ((ESTKEYSC *)ap)->pt;
}


/* Get a similar set of documents in a database.
   `db' specifies a database object.
   `svmap' specifies a map object of a seed vector.
   `nump' specifies the pointer to which the number of elements in the result is assigned.
   `knum' specifies the number of keywords to get candidates.
   `unum' specifies the number of adopted documents for a keyword.
   `tfidf' specifies whether to perform TF-IDF tuning.
   `nmin' specifies the minimum value for narrowing.
   The return value is an array whose elements are ID numbers of similar documents. */
static ESTSCORE *est_search_similar(ESTDB *db, CBMAP *svmap, int *nump,
                                    int knum, int unum, int tfidf, double nmin){
  ESTSCORE *scores, *tscores;
  CBMAP *tvmap;
  const char *word;
  int i, j, vnum, snum, tmax, tsnum, nnum, lid, *svec, *tvec;
  double dval;
  assert(db && svmap && nump && knum >= 0 && unum >= 0 && nmin >= 0.0);
  CB_MALLOC(scores, sizeof(ESTSCORE) * unum * knum);
  snum = 0;
  if((vnum = cbmaprnum(svmap)) < 1) vnum = 1;
  cbmapiterinit(svmap);
  tmax = unum;
  for(i = 0; i < knum && (word = cbmapiternext(svmap, NULL)) != NULL; i++){
    tscores = est_search_union(db, word, 1, &tsnum, NULL, TRUE);
    qsort(tscores, tsnum, sizeof(ESTSCORE), est_score_compare_by_score);
    for(j = 0; j < tmax && j < tsnum; j++){
      scores[snum].id = tscores[j].id;
      scores[snum].score = tscores[j].score;
      snum++;
    }
    free(tscores);
    tmax -= unum / knum / 1.25;
  }
  qsort(scores, snum, sizeof(ESTSCORE), est_score_compare_by_id);
  nnum = 0;
  lid = -1;
  CB_MALLOC(svec, vnum * sizeof(int));
  CB_MALLOC(tvec, vnum * sizeof(int));
  est_set_svec(svmap, svec, vnum);
  for(i = 0; i < snum; i++){
    if(scores[i].id != lid){
      tvmap = NULL;
      if(db->cbvec) tvmap = db->cbvec(db, scores[i].id, db->vecdata);
      if(!tvmap) tvmap = est_get_tvmap(db, scores[i].id, vnum, tfidf);
      if(tvmap){
        est_set_tvec(svmap, tvmap, tvec, vnum);
        if((dval = est_vec_cos(svec, tvec, vnum)) >= nmin){
          scores[nnum].id = scores[i].id;
          scores[nnum].score = (int)(dval * 10000);
          if(scores[nnum].score == 9999) scores[nnum].score = 10000;
          nnum++;
        }
        cbmapclose(tvmap);
      }
    }
    lid = scores[i].id;
  }
  free(tvec);
  free(svec);
  snum = nnum;
  *nump = snum;
  return scores;
}


/* Create a map object of a vector for similar search from a phrase.
   `phrase' specifies a search phrase for similar search.
   The return value is a map object of the seed vector. */
static CBMAP *est_phrase_vector(const char *phrase){
  CBMAP *svmap;
  CBLIST *list;
  const char *pv, *rp;
  char *utext, *rtext;
  int i, num, len, size;
  svmap = cbmapopenex(ESTMINIBNUM);
  list = cblistopen();
  while(*phrase != '\0'){
    if(*phrase == ESTOPWITH[0] && cbstrfwmatch(phrase, ESTOPWITH)){
      phrase += strlen(ESTOPWITH);
      pv = phrase;
      while(*phrase != '\0'){
        if(*phrase <= ' ' && cbstrfwmatch(phrase + 1, ESTOPWITH)){
          phrase++;
          break;
        }
        phrase++;
      }
      cblistpush(list, pv, phrase - pv);
    } else {
      phrase++;
    }
  }
  for(i = 0; i < CB_LISTNUM(list); i++){
    pv = CB_LISTVAL(list, i, NULL);
    while(*pv > '\0' && *pv <= ' '){
      pv++;
    }
    num = strtol(pv, (char **)&rp, 10);
    if(rp && (len = rp - pv) > 0 && num >= 0){
      utext = est_uconv_in(rp, strlen(rp), &size);
      est_normalize_text((unsigned char *)utext, size, &size);
      est_canonicalize_text((unsigned char *)utext, size, FALSE);
      rtext = est_uconv_out(utext, size, NULL);
      cbstrsqzspc(rtext);
      if(rtext[0] != '\0') cbmapput(svmap, rtext, -1, pv, len, FALSE);
      free(rtext);
      free(utext);
    }
  }
  cblistclose(list);
  return svmap;
}


/* Get the target vector of a document dynamically.
   `db' specifies a database object.
   `id' specifies the ID of a document.
   `vnum' specifies the number of dimensions of the vector.
   `tfidf' specifies whether to perform TF-IDF tuning.
   The return value is a map object of the target vector. */
static CBMAP *est_get_tvmap(ESTDB *db, int id, int vnum, int tfidf){
  ESTDOC *doc;
  CBMAP *tvmap;
  assert(db && id > 0);
  if(!(doc = est_db_get_doc(db, id, 0))) return NULL;
  tvmap = est_db_etch_doc(tfidf ? db : NULL, doc, vnum);
  est_doc_delete(doc);
  return tvmap;
}


/* Set a seed vector from a map object.
   `svmap' specifies a map object of a seed vector.
   `svec' specifies a vector object.
   `vnum' specifies the number of dimensions of the vector. */
static void est_set_svec(CBMAP *svmap, int *svec, int vnum){
  const char *kbuf;
  int i, ksiz;
  assert(svmap && svec && vnum > 0);
  cbmapiterinit(svmap);
  for(i = 0; i < vnum; i++){
    if((kbuf = cbmapiternext(svmap, &ksiz)) != NULL){
      svec[i] = atoi(cbmapget(svmap, kbuf, ksiz, NULL));
    } else {
      svec[i] = 0;
    }
  }
}


/* Set a target vector from a map object.
   `svmap' specifies a map object of a seed vector.
   `tvmap' specifies a map object of a target vector.
   `tvec' specifies a vector object.
   `vnum' specifies the number of dimensions of the vector. */
static void est_set_tvec(CBMAP *svmap, CBMAP *tvmap, int *tvec, int vnum){
  const char *kbuf, *vbuf;
  int i, ksiz;
  assert(svmap && tvmap && tvec && vnum > 0);
  cbmapiterinit(svmap);
  for(i = 0; i < vnum; i++){
    if((kbuf = cbmapiternext(svmap, &ksiz)) != NULL){
      vbuf = cbmapget(tvmap, kbuf, ksiz, NULL);
      tvec[i] = vbuf ? atoi(vbuf) : 0;
    } else {
      tvec[i] = 0;
    }
  }
}


/* Get the absolute of a vector.
   `vec' specifies a vector object.
   `vnum' specifies the number of dimensions of the vector.
   The return value is the absolute of the vector. */
static double est_vec_abs(const int *vec, int vnum){
  double rv;
  int i;
  assert(vec && vnum >= 0);
  rv = 0;
  for(i = 0; i < vnum; i++){
    rv += (double)vec[i] * (double)vec[i];
  }
  return sqrt(rv);
}


/* Get the inner product of two vectors.
   `avec' specifies a vector object.
   `bvec' specifies the other vector object.
   `vnum' specifies the number of dimensions of the vector.
   The return value is the inner product of two vectors. */
static double est_vec_iprod(const int *avec, const int *bvec, int vnum){
  double rv;
  int i;
  assert(avec && bvec && vnum >= 0);
  rv = 0;
  for(i = 0; i < vnum; i++){
    rv += (double)avec[i] * (double)bvec[i];
  }
  return rv;
}


/* Get the cosine of the angle of two vectors.
   `avec' specifies a vector object.
   `bvec' specifies the other vector object.
   `vnum' specifies the number of dimensions of the vector.
   The return value is the cosine of the angle of two vectors. */
static double est_vec_cos(const int *avec, const int *bvec, int vnum){
  double rv;
  assert(avec && bvec && vnum >= 0);
  rv = est_vec_iprod(avec, bvec, vnum) /
    ((est_vec_abs(avec, vnum) * est_vec_abs(bvec, vnum)));
  return rv > 0.0 ? rv : 0.0;
}


/* Close the handle to the file of random number generator. */
static void est_random_fclose(void){
  if(est_random_ifp) fclose(est_random_ifp);
}


/* END OF FILE */