Logo Search packages:      
Sourcecode: qsf version File versions  Download package

btree.c

/*
 * Binary tree database backend.
 *
 * Copyright 2007 Andrew Wood, distributed under the Artistic License.
 */

#include "config.h"
#include "database.h"
#include "log.h"

#ifdef USING_BTREE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#ifdef HAVE_FCNTL
#include <fcntl.h>
#endif
#ifdef HAVE_MMAP
#include <sys/mman.h>
#endif
#ifdef HAVE_UTIME
#include <time.h>
#include <utime.h>
#endif

#define BT_RECORD_SIZE sizeof(struct bt_record)
#define BT_TOKEN_MAX   36

typedef unsigned long bt_ul;

struct bt_record {                   /* single binary tree record */
      bt_ul lower;                   /* offset of "lower" token */
      bt_ul higher;                  /* offset of "higher" token */
      unsigned char token[BT_TOKEN_MAX];  /* RATS: ignore - 0-term. token */
      long data[3];                  /* token data (i.e. the counts) */
};

typedef struct bt_record *bt_record_t;

struct qdbint_s {              /* database state */
      int fd;                        /* file descriptor of database file */
      bt_ul size;              /* total size of database */
#ifdef HAVE_FCNTL
      int lockcount;                 /* number of times lock asked for */
      int locktype;                  /* type of lock to use (read or write) */
#endif
      int gotheadoffs;         /* flag, set once head offset read */
      bt_ul head_offset;             /* offset of head record of tree */
#ifdef HAVE_MMAP
      unsigned char *data;           /* mmap()ed database data */
      bt_ul filepos;                 /* current file pointer */
#endif
      char *filename;                /* filename of database */
      int modified;                  /* flag, set if db modified at all */
};

static char *bt_lasterror = "";


#ifdef HAVE_FCNTL
/*
 * Obtain / release a read or write lock on the database. Returns nonzero on
 * error, and blocks until a lock can be obtained.
 */
static int dbbt_lock(qdbint_t db, int lock_type)
{
      int ret;
      ret = qdb_int__lock(db->fd, lock_type, &(db->lockcount));
      if (ret != 0) {
            bt_lasterror = strerror(errno);
            return 1;
      }
      return 0;
}
#endif                        /* HAVE_FCNTL */


static off_t dbbt_lseek(qdbint_t db, off_t offset, int whence)
{
#ifdef HAVE_MMAP
      if ((db->data == 0) || (db->filepos < 0) || (whence != SEEK_SET)) {
            db->filepos = lseek(db->fd, offset, whence);
      } else {
            db->filepos = offset;
      }
      return db->filepos;
#else
      return lseek(db->fd, offset, whence);
#endif
}


/*
 * Analogue of fread().
 */
static int dbbt_chunkread_raw(void *ptr, int size, int nmemb, int fd)
{
      int numread, togo, got;

      for (numread = 0; nmemb > 0; nmemb--, numread++) {
            for (togo = size; togo > 0;) {
                  got = read(fd, ptr, togo);    /* RATS: ignore (OK) */
                  if (got <= 0)
                        return numread;
                  togo -= got;
                  ptr = (void *) (((char *) ptr) + got);
            }
      }

      return numread;
}


/*
 * Analogue of fwrite().
 */
static int dbbt_chunkwrite_raw(void *ptr, int size, int nmemb, int fd)
{
      int numwritten, togo, written;

      for (numwritten = 0; nmemb > 0; nmemb--, numwritten++) {
            for (togo = size; togo > 0;) {
                  written = write(fd, ptr, togo);
                  if (written <= 0)
                        return numwritten;
                  togo -= written;
                  ptr = (void *) (((char *) ptr) + written);
            }
      }

      return numwritten;
}


/*
 * Analogue of fread(), using memory mapped data if possible.
 */
static int dbbt_chunkread(void *ptr, int size, int nmemb, qdbint_t db)
{
#ifdef HAVE_MMAP
      long available, copyable, tocopy;

      if ((db->data == 0) || (db->filepos < 0)) {
            return dbbt_chunkread_raw(ptr, size, nmemb, db->fd);
      }

      if (size < 1)
            return 0;

      available = db->size - db->filepos;

      if (available <= 0)
            return 0;

      copyable = available / size;
      if (copyable < nmemb)
            nmemb = copyable;

      tocopy = nmemb * size;
      memcpy(ptr, db->data + db->filepos, tocopy);
      db->filepos += tocopy;

      return nmemb;
#else                   /* !HAVE_MMAP */
      return dbbt_chunkread_raw(ptr, size, nmemb, db->fd);
#endif                        /* HAVE_MMAP */
}


/*
 * Analogue of fwrite(), using memory mapped data if possible, remapping
 * after extending the file if not.
 */
static int dbbt_chunkwrite(void *ptr, int size, int nmemb, qdbint_t db)
{
#ifdef HAVE_MMAP
      long available, copyable, tocopy;

      db->modified = 1;

      if ((db->data == 0) || (db->filepos < 0))
            return dbbt_chunkwrite_raw(ptr, size, nmemb, db->fd);

      if (size < 1)
            return 0;

      available = db->size - db->filepos;
      copyable = available / size;
      if (copyable < nmemb) {
            int retval;

            munmap(db->data, db->size);
            db->data = 0;

            lseek(db->fd, db->filepos, SEEK_SET);
            retval = dbbt_chunkwrite_raw(ptr, size, nmemb, db->fd);

            db->size = lseek(db->fd, 0, SEEK_END);
            db->data =
                mmap(NULL, db->size, PROT_READ | PROT_WRITE,
                   MAP_SHARED, db->fd, 0);
            if (db->data == MAP_FAILED)
                  db->data = 0;
            db->filepos = db->size;

            return retval;
      } else {
            tocopy = nmemb * size;
            memcpy(db->data + db->filepos, ptr, tocopy);
            db->filepos += tocopy;

            return nmemb;
      }
#else                   /* !HAVE_MMAP */
      return dbbt_chunkwrite_raw(ptr, size, nmemb, db->fd);
#endif                        /* HAVE_MMAP */
}


/*
 * Read a record from the database at the given offset into the given record
 * structure, returning nonzero on failure.
 */
static int dbbt_read_record(qdbint_t db, bt_ul offset, bt_record_t record)
{
      int got;

      if (dbbt_lseek(db, offset, SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      got = dbbt_chunkread(record, BT_RECORD_SIZE, 1, db);
      if (got < 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      record->token[BT_TOKEN_MAX - 1] = 0;

      return 0;
}


/*
 * Write a record to the database at the given offset, returning nonzero on
 * failure.
 */
static int dbbt_write_record(qdbint_t db, bt_ul offset, bt_record_t record)
{
      if (dbbt_lseek(db, offset, SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      if (dbbt_chunkwrite(record, BT_RECORD_SIZE, 1, db) < 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      return 0;
}


/*
 * Find the given token in the database and fill in the given record
 * structure if found, also filling in the offset of the record (or 0 if not
 * found) and the offset of the parent record (0 if none).
 *
 * Returns -1 if the token looked for was "lower" than its parent or +1 if
 * "higher", or 0 if there was no parent record (i.e. this is the first
 * record).
 */
static int dbbt_find_token(qdbint_t db, qdb_datum key, bt_record_t record,
                     bt_ul * offset, bt_ul * parent)
{
      int hilow = 0;
      int x;

      *offset = 0;
      *parent = 0;

      if (db == NULL)
            return 0;

      if (db->size < 2 * sizeof(long))
            return 0;

      if (!db->gotheadoffs) {
            dbbt_lseek(db, 4, SEEK_SET);
            dbbt_chunkread(offset, sizeof(*offset), 1, db);
            db->head_offset = *offset;
            db->gotheadoffs = 1;
      } else {
            *offset = db->head_offset;
      }

      while (*offset > 0) {
            int len;

            if (dbbt_read_record(db, *offset, record)) {
                  *offset = 0;
                  break;
            }

            x = strncmp((char *) (record->token), (char *) (key.data),
                      key.size);
            len = strlen((char *) (record->token));
            if (len < key.size) {
                  x = -1;
            } else if (len > key.size) {
                  x = 1;
            }

            if (x == 0) {
                  return hilow;
            } else if (x < 0) {
                  *parent = *offset;
                  hilow = -1;
                  *offset = record->lower;
            } else {
                  *parent = *offset;
                  hilow = 1;
                  *offset = record->higher;
            }
      }

      return hilow;
}


/*
 * Mark the block at the given offset as free space by adding it to the head
 * of the free space list. Returns nonzero on error.
 */
static int dbbt_markfree(qdbint_t db, bt_ul offset)
{
      bt_ul nextfree, storeoffs;

      /*
       * Read the "next free" offset from the free space head block
       */
      if (dbbt_lseek(db, 4 + sizeof(offset), SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }
      nextfree = 0x80000000;
      if (dbbt_chunkread(&nextfree, sizeof(nextfree), 1, db) < 0) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      /*
       * Write the given offset as the new "next free" offset
       */
      if (dbbt_lseek(db, 4 + sizeof(offset), SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }
      storeoffs = offset;
      storeoffs |= 0x80000000;
      if (dbbt_chunkwrite(&storeoffs, sizeof(offset), 1, db) < 0) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      /*
       * Write the old "next free" offset into the block being freed
       */
      if (dbbt_lseek(db, offset, SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }
      if (dbbt_chunkwrite(&nextfree, sizeof(nextfree), 1, db) < 1) {
            bt_lasterror = strerror(errno);
            return 1;
      }

      return 0;
}


/*
 * Return nonzero if the given file is of this database type.
 */
int qdb_btree_identify(const char *file)
{
      FILE *fptr;
      unsigned char buf[8];          /* RATS: ignore (checked) */

      if (file == NULL)
            return 0;
      if (strncasecmp(file, "btree:", 6) == 0)
            return 1;

      fptr = fopen(file, "rb");
      if (fptr == NULL)
            return 0;
      if (fread(buf, 4, 1, fptr) < 1) {
            fclose(fptr);
            return 0;
      }

      fclose(fptr);

      if (strncmp((char *) buf, "QSF1", 4) == 0)
            return 1;

      return 0;
}


/*
 * Open the given database in the given way (new database, read-only, or
 * read-write); return a qdbint_t or NULL on error.
 */
qdbint_t qdb_btree_open(const char *file, qdb_open_t method)
{
      qdbint_t db;
      int fd = -1;
#ifdef HAVE_FCNTL
      int locktype = F_RDLCK;
#endif

      if (strncasecmp(file, "btree:", 6) == 0)
            file += 6;

      switch (method) {
      case QDB_NEW:
            fd = open(file,             /* RATS: ignore (no race) */
                    O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
            if (fd < 0)
                  bt_lasterror = strerror(errno);
#ifdef HAVE_FCNTL
            locktype = F_WRLCK;
#endif
            break;
      case QDB_READONLY:
            fd = open(file,             /* RATS: ignore (no race) */
                    O_RDONLY);
            if (fd < 0)
                  bt_lasterror = strerror(errno);
            break;
      case QDB_READWRITE:
            fd = open(file,             /* RATS: ignore (no race) */
                    O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
            if (fd < 0)
                  bt_lasterror = strerror(errno);
#ifdef HAVE_FCNTL
            locktype = F_WRLCK;
#endif
            break;
      default:
            break;
      }

      if (fd < 0)
            return NULL;

      db = calloc(1, sizeof(*db));
      if (db == NULL) {
            bt_lasterror = strerror(errno);
            close(fd);
            return NULL;
      }

      db->filename = strdup(file);
      db->fd = fd;
      db->modified = 0;

#ifdef HAVE_FCNTL
      db->locktype = locktype;

      if (dbbt_lock(db, locktype)) {
            close(fd);
            if (db->filename)
                  free(db->filename);
            free(db);
            return NULL;
      }
#endif

      db->size = dbbt_lseek(db, 0, SEEK_END);

      /*
       * If this is a new database, and it's not readonly, write our
       * header to it and return.
       */
      if ((db->size < 5) && (method != QDB_READONLY)) {
            dbbt_lseek(db, 0, SEEK_SET);
            dbbt_chunkwrite_raw("QSF1", 4, 1, db->fd);
            db->size = 4;
            db->modified = 1;
#ifdef HAVE_MMAP
            db->filepos = 0;
            db->data =
                mmap(NULL, db->size,
                   PROT_READ | (method ==
                              QDB_READONLY ? 0 : PROT_WRITE),
                   MAP_SHARED, db->fd, 0);
            if (db->data == MAP_FAILED)
                  db->data = 0;
#endif
            return db;
      }

      /*
       * We now do some simple checks to make sure that the file is a
       * database of the format we're expecting.
       */

      /*
       * If it's shorter than 4 bytes plus 2 long ints, it's not a valid
       * database.
       */
      if (db->size < 4 + 2 * sizeof(long)) {
            bt_lasterror = _("invalid database (too small)");
            close(fd);
            if (db->filename)
                  free(db->filename);
            free(db);
            return NULL;
      }

      /*
       * If its size, discounting the two longs at the start, isn't a
       * multiple of our record size, it's not a valid database.
       */
      if (((db->size - (4 + 2 * sizeof(long))) % BT_RECORD_SIZE) != 0) {
            bt_lasterror = _("invalid database (irregular size)");
            close(fd);
            if (db->filename)
                  free(db->filename);
            free(db);
            return NULL;
      }

      /*
       * If the first long int (the "head offset") is larger than the size
       * of the file, this isn't a valid database.
       */
      {
            bt_ul offset = db->size + 1;
            dbbt_lseek(db, 4, SEEK_SET);
            dbbt_chunkread(&offset, sizeof(offset), 1, db);
            if (offset > db->size) {
                  bt_lasterror =
                      _("invalid database (bad head offset)");
                  close(fd);
                  if (db->filename)
                        free(db->filename);
                  free(db);
                  return NULL;
            }
            dbbt_lseek(db, 4, SEEK_SET);
      }

#ifdef HAVE_MMAP
      db->data =
          mmap(NULL, db->size,
             PROT_READ | (method == QDB_READONLY ? 0 : PROT_WRITE),
             MAP_SHARED, db->fd, 0);
      if (db->data == MAP_FAILED)
            db->data = 0;
#endif

      return db;
}


/*
 * Close the given database.
 */
void qdb_btree_close(qdbint_t db)
{
      if (db == NULL)
            return;

#ifdef HAVE_MMAP
      if (db->data)
            munmap(db->data, db->size);
#endif

#ifdef HAVE_FCNTL
      while (db->lockcount > 0)
            dbbt_lock(db, F_UNLCK);
#endif

      close(db->fd);

      if (db->modified && db->filename) {
#ifdef HAVE_UTIME
            struct utimbuf utb;

            utb.actime = time(NULL);
            utb.modtime = time(NULL);
            utime(db->filename, &utb);
#endif
      }

      if (db->filename)
            free(db->filename);

      free(db);
}


/*
 * Fetch a value from the database. The datum returned needs its val.data
 * free()ing after use. If val.data is NULL, no value was found for the
 * given key.
 */
qdb_datum qdb_btree_fetch(qdbint_t db, qdb_datum key)
{
      struct bt_record record;
      unsigned long offset, parent;
      qdb_datum val;

      val.data = NULL;
      val.size = 0;

      if (db == NULL)
            return val;

      if (key.size >= BT_TOKEN_MAX)
            key.size = BT_TOKEN_MAX - 1;

      dbbt_find_token(db, key, &record, &offset, &parent);
      if (offset == 0)
            return val;

      val.size = 3 * sizeof(long);
      val.data = calloc(1, val.size);
      if (val.data == NULL) {
            val.size = 0;
            return val;
      }

      ((long *) val.data)[0] = record.data[0];
      ((long *) val.data)[1] = record.data[1];
      ((long *) val.data)[2] = record.data[2];

      return val;
}


/*
 * Return a file descriptor for the given database, or -1 on error.
 */
int qdb_btree_fd(qdbint_t db)
{
      if (db == NULL)
            return -1;
      return db->fd;
}


/*
 * Store the given key with the given value into the database, replacing any
 * existing value for that key. Returns nonzero on error.
 */
int qdb_btree_store(qdbint_t db, qdb_datum key, qdb_datum val)
{
      struct bt_record record, head;
      unsigned long offset, parent, nextfree;
      int x;

      if (db == NULL)
            return 1;

      memset(&head, 0, BT_RECORD_SIZE);
      memset(&record, 0, BT_RECORD_SIZE);

      if (key.size >= BT_TOKEN_MAX)
            key.size = BT_TOKEN_MAX - 1;

      x = dbbt_find_token(db, key, &record, &offset, &parent);

      memcpy(record.token, key.data, key.size);
      record.token[key.size] = 0;
      record.data[0] = ((long *) val.data)[0];
      record.data[1] = ((long *) val.data)[1];
      if (val.size > 2 * sizeof(long))
            record.data[2] = ((long *) val.data)[2];

      qdb_int__sig_block();

      /*
       * Record exists - overwrite it.
       */
      if (offset > 0) {
            if (dbbt_write_record(db, offset, &record)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
            qdb_int__sig_unblock();
            return 0;
      }

      record.lower = 0;
      record.higher = 0;

      /*
       * Database has just been created, so fill in the header and write
       * this record as the first one.
       */
      if (db->size <= 4 + sizeof(offset)) {

            if (dbbt_lseek(db, 4, SEEK_SET) == (off_t) - 1) {
                  bt_lasterror = strerror(errno);
                  qdb_int__sig_unblock();
                  return 1;
            }
            offset = 4 + 2 * sizeof(offset);
            if (dbbt_chunkwrite(&offset, sizeof(offset), 1, db) < 1) {
                  bt_lasterror = strerror(errno);
                  qdb_int__sig_unblock();
                  return 1;
            }

            db->gotheadoffs = 0;

            offset = 0;
            if (dbbt_chunkwrite(&offset, sizeof(offset), 1, db) < 1) {
                  bt_lasterror = strerror(errno);
                  qdb_int__sig_unblock();
                  return 1;
            }

            head.lower = (4 + 2 * sizeof(offset)) + BT_RECORD_SIZE;
            if (dbbt_chunkwrite(&head, BT_RECORD_SIZE, 1, db) < 1) {
                  bt_lasterror = strerror(errno);
                  qdb_int__sig_unblock();
                  return 1;
            }

            if (dbbt_chunkwrite(&record, BT_RECORD_SIZE, 1, db) < 1) {
                  bt_lasterror = strerror(errno);
                  qdb_int__sig_unblock();
                  return 1;
            }

            db->size = dbbt_lseek(db, 0, SEEK_CUR);
            qdb_int__sig_unblock();
            return 0;
      }

      /*
       * Get offset of next free space block.
       */
      if (dbbt_lseek(db, 4 + sizeof(offset), SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            qdb_int__sig_unblock();
            return 1;
      }
      if (dbbt_chunkread(&offset, sizeof(offset), 1, db) < 1) {
            bt_lasterror = strerror(errno);
            qdb_int__sig_unblock();
            return 1;
      }

      offset &= 0x7FFFFFFF;

      /*
       * If offset is 0 or we can't read from that offset, it's a new
       * block at the end of the file, otherwise we take the next free
       * offset from there and store it in the core free pointer, and then
       * use that free offset.
       */
      if (dbbt_lseek(db, offset, SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            qdb_int__sig_unblock();
            return 1;
      }
      if ((offset < 5)
          || (dbbt_chunkread(&nextfree, sizeof(nextfree), 1, db) < 1)
          ) {
            offset = dbbt_lseek(db, 0, SEEK_END);
            nextfree = 0x80000000;
      }
      if (dbbt_lseek(db, 4 + sizeof(offset), SEEK_SET) == (off_t) - 1) {
            bt_lasterror = strerror(errno);
            qdb_int__sig_unblock();
            return 1;
      }
      if (dbbt_chunkwrite(&nextfree, sizeof(nextfree), 1, db) < 0) {
            bt_lasterror = strerror(errno);
            qdb_int__sig_unblock();
            return 1;
      }

      if (dbbt_write_record(db, offset, &record)) {
            qdb_int__sig_unblock();
            return 1;
      }

      /*
       * Now attach the new record to its parent, if applicable.
       */
      if (parent > 0) {
            if (dbbt_read_record(db, parent, &record)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
            if (x < 0) {
                  record.lower = offset;
            } else {
                  record.higher = offset;
            }
            if (dbbt_write_record(db, parent, &record)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
      }

      qdb_int__sig_unblock();

      return 0;
}


/*
 * Return the "first" key in the database, suitable for using with repeated
 * calls to qdb_nextkey() to walk through every key in the database.
 */
qdb_datum qdb_btree_firstkey(qdbint_t db)
{
      struct bt_record record;
      qdb_datum newkey;

      newkey.data = NULL;
      newkey.size = 0;

      if (dbbt_lseek(db, 4 + 2 * sizeof(unsigned long) + BT_RECORD_SIZE,
                   SEEK_SET) == (off_t) - 1)
            return newkey;

      do {
            if (dbbt_chunkread(&record, BT_RECORD_SIZE, 1, db) < 1) {
                  return newkey;
            }
      } while (record.lower & 0x80000000);

      record.token[BT_TOKEN_MAX - 1] = 0;

      newkey.data = (unsigned char *) strdup((char *) (record.token));
      newkey.size = strlen((char *) (record.token));

      return newkey;
}


/*
 * Return the "next" key in the database, or key.data=NULL when all keys
 * have been returned.
 */
qdb_datum qdb_btree_nextkey(qdbint_t db, qdb_datum key)
{
      struct bt_record record;
      unsigned long offset, parent;
      qdb_datum newkey;

      newkey.data = NULL;
      newkey.size = 0;

      if (key.data == NULL) {
            return newkey;
      }

      dbbt_find_token(db, key, &record, &offset, &parent);

      if (offset < 1) {
            return newkey;
      }

      if (dbbt_lseek(db, offset + BT_RECORD_SIZE, SEEK_SET) ==
          (off_t) - 1) {
            return newkey;
      }

      do {
            if (dbbt_chunkread(&record, BT_RECORD_SIZE, 1, db) < 1) {
                  return newkey;
            }
      } while (record.lower & 0x80000000);

      record.token[BT_TOKEN_MAX - 1] = 0;

      newkey.data = (unsigned char *) strdup((char *) (record.token));
      newkey.size = strlen((char *) (record.token));

      return newkey;
}


/*
 * Put the given record back into the binary tree, by storing it over again. 
 * Returns nonzero on error.
 */
static int qdb_btree_delete__rewrite(qdbint_t db, bt_record_t record)
{
      qdb_datum key, val;
      struct bt_record newrec;
      unsigned long offset, parent;
      int x;

      key.data = record->token;
      key.size = strlen((char *) (record->token));
      val.data = (void *) (record->data);
      val.size = 3 * sizeof(long);

      if (qdb_btree_store(db, key, val))
            return 1;

      x = dbbt_find_token(db, key, &newrec, &offset, &parent);
      if (offset < 4)
            return 1;

      newrec.lower = record->lower;
      newrec.higher = record->higher;

      qdb_int__sig_block();
      if (dbbt_write_record(db, offset, &newrec)) {
            qdb_int__sig_unblock();
            return 1;
      }

      qdb_int__sig_unblock();

      return 0;
}


/*
 * Delete the given key from the database. Returns nonzero on error.
 */
int qdb_btree_delete(qdbint_t db, qdb_datum key)
{
      struct bt_record record, recparent, reclower, rechigher;
      unsigned long offset, parent;

      int x;

      if (db == NULL)
            return 1;

      if (key.size < 1)
            return 1;

      x = dbbt_find_token(db, key, &record, &offset, &parent);
      if (offset < 5)
            return 1;

      /*
       * Get a copy of the lower and higher records, if any.
       */
      if (record.lower > 0) {
            if (dbbt_read_record(db, record.lower, &reclower))
                  return 1;
      }

      if (record.higher > 0) {
            if (dbbt_read_record(db, record.higher, &rechigher))
                  return 1;
      }

      qdb_int__sig_block();

      /*
       * Remove the link to this record from its parent.
       */
      if (parent > 0) {
            if (dbbt_read_record(db, parent, &recparent)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
            if (x < 0) {
                  recparent.lower = 0;
            } else {
                  recparent.higher = 0;
            }
            if (dbbt_write_record(db, parent, &recparent)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
      }

      /*
       * Now we add this record's offset to the head of the "free records"
       * linked list.
       */
      if (dbbt_markfree(db, offset)) {
            qdb_int__sig_unblock();
            return 1;
      }

      /*
       * If there were any direct children, mark them as free as well.
       */
      if (record.lower > 0) {
            if (dbbt_markfree(db, record.lower)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
      }
      if (record.higher > 0) {
            if (dbbt_markfree(db, record.higher)) {
                  qdb_int__sig_unblock();
                  return 1;
            }
      }

      qdb_int__sig_unblock();

      /*
       * Re-attach any children of this record to the database.
       */
      if (record.lower > 0) {
            if (qdb_btree_delete__rewrite(db, &reclower)) {
                  return 1;
            }
      }
      if (record.higher > 0) {
            if (qdb_btree_delete__rewrite(db, &rechigher)) {
                  return 1;
            }
      }

      return 0;
}


/*
 * Temporarily release the lock on the database.
 */
void qdb_btree_unlock(qdbint_t db)
{
#ifdef HAVE_FCNTL
      dbbt_lock(db, F_UNLCK);
#endif
}


/*
 * Reassert the lock on the database.
 */
void qdb_btree_relock(qdbint_t db)
{
#ifdef HAVE_FCNTL
      dbbt_lock(db, db->locktype);
#endif
      db->gotheadoffs = 0;
}


/*
 * Reorganise the database for better efficiency.
 *
 * This is done by dumping all the tokens in this database into a temporary
 * new one, then copying this temporary database over the top of the current
 * database.
 */
void qdb_btree_optimise(qdbint_t db)
{
      char filename[1024];           /* RATS: ignore (checked all) */
      qdbint_t newdb;
      qdb_datum key, val, nextkey;
      int newdbfd, got;

#ifdef P_tmpdir
#ifdef HAVE_SNPRINTF
      snprintf(filename, sizeof(filename),
#else
      sprintf(filename,           /* RATS: ignore (checked) */
#endif
            "%.*s", (int) (sizeof(filename) - 1),
            P_tmpdir "/qsfXXXXXX");
#else
#ifdef HAVE_SNPRINTF
      snprintf(filename, sizeof(filename),
#else
      sprintf(filename,           /* RATS: ignore (checked) */
#endif
            "%.*s", (int) (sizeof(filename) - 1), "/tmp/qsfXXXXXX");
#endif

#ifdef HAVE_MKSTEMP
      newdbfd = mkstemp(filename);
#else
      newdbfd = -1;
      if (tmpnam(filename) != NULL) {         /* RATS: ignore (OK) */
            newdbfd = open(filename,    /* RATS: ignore (OK) */
                         O_RDWR | O_CREAT | O_EXCL,
                         S_IRUSR | S_IWUSR);
      }
#endif

      if (newdbfd < 0) {
            fprintf(stderr, "%s: %s: %s\n",
                  filename,
                  _("failed to create temporary file"),
                  strerror(errno));
            return;
      }

      newdb = qdb_btree_open(filename, QDB_NEW);
      if (newdb == NULL) {
            close(newdbfd);
            return;
      }

      key = qdb_btree_firstkey(db);
      while (key.data != NULL) {
            val = qdb_btree_fetch(db, key);
            if (val.data != NULL) {
                  qdb_btree_store(newdb, key, val);
                  free(val.data);
            }
            nextkey = qdb_btree_nextkey(db, key);
            free(key.data);
            key = nextkey;
      }

      qdb_btree_close(newdb);

#ifdef HAVE_MMAP
      munmap(db->data, db->size);
      db->data = 0;
#endif

      qdb_int__sig_block();

      dbbt_lseek(db, 0, SEEK_SET);
      lseek(newdbfd, 0, SEEK_SET);

      do {
            unsigned char buf[4096]; /* RATS: ignore (checked) */

            got = dbbt_chunkread_raw(buf, 1, sizeof(buf), newdbfd);
            if (got > 0)
                  dbbt_chunkwrite_raw(buf, 1, got, db->fd);

      } while (got > 0);

      if (ftruncate(db->fd, lseek(db->fd, 0, SEEK_CUR)) != 0) {
            log_add(0, "%s: failed to truncate database: %s",
                  db->filename, strerror(errno));
      }

      close(newdbfd);
      remove(filename);

      qdb_int__sig_unblock();

      db->size = dbbt_lseek(db, 0, SEEK_END);
      db->gotheadoffs = 0;

#ifdef HAVE_MMAP
      db->data =
          mmap(NULL, db->size, PROT_READ | PROT_WRITE, MAP_SHARED,
             db->fd, 0);
      if (db->data == MAP_FAILED)
            db->data = 0;
      db->filepos = db->size;
#endif
}


/*
 * Return a string describing the last database error to occur.
 */
char *qdb_btree_error(void)
{
      return bt_lasterror;
}

#endif                        /* USING_BTREE */

/* EOF */

Generated by  Doxygen 1.6.0   Back to index