sfxdisk.c

后缀数存储算法

/**************************************************************************
 *                                                                        *
 * Suffix tree implementation library 1.2                                 *
 * Copyright (C) 2001 Fabien Menemenlis ([e-mail])        *
 *                                                                        *
 * This program is free software; you can redistribute it and/or          *
 * modify it under the terms of the GNU General Public License            *
 * as published by the Free Software Foundation; either version 2         *
 * of the License, or (at your option) any later version.                 *
 *                                                                        *
 * This program is distributed in the hope that it will be useful,        *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of         *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
 * GNU General Public License for more details.                           *
 *                                                                        *
 * You should have received a copy of the GNU General Public License      *
 * along with this program; if not, write to the Free Software            *
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, *
 * USA                                                                    *
 *                                                                        *
 **************************************************************************/

/*
 * Fabien Menemenlis 2001-07-18
 * Works directly on disk, uses a custom cache
 *
 * Note: this has only been tested as with 32 bits offsets for now.
 * You can change offset_t to long long type in sfxdisk.h if you want to
 * play with 64 bits (just check that standards file functions returns
 * long long ints on your system)
 *
 * rev 1.2: added STdelete(), and "finished" STclose() (frees descriptor
 *          and memory)
 * rev 1.1: cleaned code to avoid global variables, a structure is now
 *          given to functions instead of the file descriptor
 *          added STopen(), removed STinit()
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

#include "sfxdisk.h"


//#define DEBUG

#ifdef DEBUG
int nbnode = 0;
int nbread = 0;
int nbwrite = 0;
int nbreadcached = 0;
int nbwritecached = 0;
#endif


/*
 * ok this is a global variable... modify it for your needs: the table
 * needs to include ALL characters possible in your keys. But the bigger
 * it is, the bigger nodes will be, and the bigger the file will be and the
 * slower queries will be
 */
static char *SThashtable = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";


/*
 * opens a file for reading and/or writing, returns a structure filled
 * with the file descriptor and newly allocated cache space or NULL is
 * opening failed
 */
STFile *STopen(char *filename, int mode)
{
  FILE *file;
  STFile *stfile;
  offset_t off;


  /*
   * read only
   */
  if (mode == ST_RDONLY)
  {
    if ((file = fopen(filename, "r")) == NULL)
      return(NULL);
 
    stfile = (STFile *)malloc(sizeof(STFile));
    memset(stfile, 0, sizeof(STFile));
    stfile->file = file;

    return(stfile);
  }

  /*
   * opens for reading and writing
   */
  if ((file = fopen(filename, "r+")) == NULL)
  {
    if ((file = fopen(filename, "w+")) == NULL)
      return(NULL);
  }

  /*
   * initialization: if it's a newly created file we have to reserve the space
   * for the root node
   */
  fseek(file, 0, SEEK_END);
  off = ftell(file);

  stfile = (STFile *)malloc(sizeof(STFile));
  memset(stfile, 0, sizeof(STFile));
  stfile->file = file;
 
  if (off == 0)
    stfile->SToffset = sizeof(STnode);
  else
    stfile->SToffset = off;

  return(stfile);
}


/*
 * compares 2 strings and returns the number of common characters from
 * the beginning of the string
 */
int STcomparechaine(char *chaine1, char *chaine2)
{
  int cpt;


  cpt = 0;
  if (chaine1 == NULL || chaine2 == NULL)
    return(0);
  while (*chaine1 != '\0' && *chaine2 != '\0')
  {
    if (*chaine1 != *chaine2)
      break;
    chaine1++;
    chaine2++;
    cpt++;
  }
  return(cpt);
}


/*
 * returns the position of the given character in the hash table defined
 * in the header file
 * it IS a sequential search, but it gives you complete freedom for your
 * alphabet (and our main problem is disks speed anyway)
 */
int STfindinhash(char c)
{
  int pos;
  char *ptr;


  if (c == '$')
    return(0);
  pos = 1;
  ptr = SThashtable;
  while (*ptr != '\0')
  {
    if (*ptr == c)
      return(pos);
    pos++;
    ptr++;
  }
  return(-1);
}


/*
 * goes through the cache blocks chained list to the last block and
 * removes the LRU (least recently used) block in case the max number of
 * cache block has been reached
 */
void STCachecheckLRU(STFile *stfile)
{
  int i = 0;
  STCache *cache;


  cache = stfile->STCacheroot;
  while (cache)
  {
    i++;
    if (i == MAXNODES && cache->next)
    {
      /*
       * si le bloc cach