/* ***************************************************************** *
 * Copyright 1998 International Business Machines Corporation. All   *
 * Rights Reserved.                                                  *
 *                                                                   *
 * Please read this carefully.  Your use of this reference           *
 * implementation of certain of the IETF public-key infrastructure   *
 * specifications ("Software") indicates your acceptance of the      *
 * following.  If you do not agree to the following, do not install  *
 * or use any of the Software.                                       *
 *                                                                   *
 * Permission to use, reproduce, distribute and create derivative    *
 * works from the Software ("Software Derivative Works"), and to     *
 * distribute such Software Derivative Works is hereby granted to    *
 * you by International Business Machines Corporation ("IBM").  This *
 * permission includes a license under the patents of IBM that are   *
 * necessarily infringed by your use of the Software as provided by  *
 * IBM.                                                              *
 *                                                                   *
 * IBM licenses the Software to you on an "AS IS" basis, without     *
 * warranty of any kind.  IBM HEREBY EXPRESSLY DISCLAIMS ALL         *
 * WARRANTIES OR CONDITIONS, EITHER EXPRESS OR IMPLIED, INCLUDING,   *
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OR CONDITIONS OF       *
 * MERCHANTABILITY, NON INFRINGEMENT AND FITNESS FOR A PARTICULAR    *
 * PURPOSE.  You are solely responsible for determining the          *
 * appropriateness of using this Software and assume all risks       *
 * associated with the use of this Software, including but not       *
 * limited to the risks of program errors, damage to or loss of      *
 * data, programs or equipment, and unavailability or interruption   *
 * of operations.                                                    *
 *                                                                   *
 * IBM WILL NOT BE LIABLE FOR ANY DIRECT DAMAGES OR FOR ANY SPECIAL, *
 * INCIDENTAL, OR  INDIRECT DAMAGES OR FOR ANY ECONOMIC              *
 * CONSEQUENTIAL DAMAGES (INCLUDING LOST PROFITS OR SAVINGS), EVEN   *
 * IF IBM HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.  IBM  *
 * will not be liable for the loss of, or damage to, your records or *
 * data, or any damages claimed by you based on a third party claim. *
 *                                                                   *
 * IBM wishes to obtain your feedback to assist in improving the     *
 * Software.  You grant IBM a world-wide, royalty-free right to use, *
 * copy, distribute, sublicense and prepare derivative works based   *
 * upon any feedback, including materials, error corrections,        *
 * Software Derivatives, enhancements, suggestions and the like that *
 * you provide to IBM relating to the Software (this does not        *
 * include products for which you charge a royalty and distribute to *
 * IBM under other terms and conditions).                            *
 *                                                                   *
 * You agree to distribute the Software and any Software Derivatives *
 * under a license agreement that: 1) is sufficient to notify all    *
 * licensees of the Software and Software Derivatives that IBM       *
 * assumes no liability for any claim that may arise regarding the   *
 * Software or Software Derivatives, and 2) that disclaims all       *
 * warranties, both express and implied, from IBM regarding the      *
 * Software and Software Derivatives.  (If you include this          *
 * Agreement with any distribution of the Software or Software       *
 * Derivatives you will have met this requirement.)  You agree that  *
 * you will not delete any copyright notices in the Software.        *
 *                                                                   *
 * This Agreement is the exclusive statement of your rights in the   *
 * Software as provided by IBM.   Except for the rights granted to   *
 * you in the second paragraph above, You are not granted any other  *
 * patent rights, including but not limited to the right to make     *
 * combinations of the Software with products that infringe IBM      *
 * patents. You agree to comply with all applicable laws and         *
 * regulations, including all export and import laws and regulation. *
 * This Agreement is governed by the laws of the State of New York.  *
 * This Agreement supersedes all other communications,               *
 * understandings or agreements we may have had prior to this        *
 * Agreement.                                                        *
 * ***************************************************************** */

#include <qdisam.h>
#include <qdisamint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// QDISAM provides a BLOB store, indexed by a 32-bit integer key.  Keys are allocated
// by QDISAM, not provided by the user.  QDISAM should be thought of as providing a
// relatively robust persistent store for flat data (or objects that know how to 
// flatten themselves,  for example, the Jonah ASN.1 classes).
//
// The QDISAM on-disk format is as follows.
// A QDISAM store consists of three files: An index, an allocation map, and a data file.
//
// The index is a simple array of records, mapping keys to offsets in the data-file.  
// Each index record also holds a uint32 flags value, that can be used as a filter on
// the enumerate_XXX calls.
//
// Apart from a header portion that contains various file constants (e.g. blocksize), 
// the data-file is just an array of blocks.  Each block has a 4-byte header that gives
// the record number of the record contained in that block, or zero if the block is empty.  
// Blocks and records are two distinct levels of structure - A record always starts on 
// a block boundary, but may continue across multiple contiguous blocks.  A record is 
// introduced by a 4-byte count field, followed by the record data.  
//
// The allocation map is a bitmap that contains one bit for each block of the data-file.
// The bit is set if the block is allocated, clear if the block is free.
//
// Storing a record always involves allocating a fresh set of blocks.  This involves
// searching the allocation map for a sequence of free blocks long enough to contain 
// the data, writing the data to the blocks, marking the blocks as in-use, updating 
// the index to point to the new start block, then updating the allocation map to
// release the original record blocks.  A crash prior to marking the data in-use 
// will lose the record but retain the integrity of the store; A crash after 
// marking but before updating the index will cause the blocks to be lost from 
// the file.
// 
// The file-structure is designed so that both the index and allocation files can be
// easily reconstructed from the data-file (although the flags information in the
// index file will be lost), and so that database compaction is fairly trivial.  
// However, these features aren't yet implemented.
//
// Blocksize and initial index size may be defined when you create a QDISAM store.
// Performance will probably be much better if records generally don't span multiple
// blocks, so it's worth doing some calculations to set a reasonable blocksize.
//
//
// QDISAM stands for "Quick and Dirty ISAM".  The "quick" refers to the amount
// of coding time it took to implement, and is explicitly NOT a performance claim :-)
//
//
// The #ifdef _WIN32 stanzas below make fflush actually flush the buffers.
// Why anyone would want it to _not_ flush the buffers is a mystery to me.



#ifndef ASN_CLASSES_H_

#define CHUNKSIZE 64

#define chunk(x) CHUNKSIZE * ((x + CHUNKSIZE - 1) / CHUNKSIZE)

r_buffer_t::r_buffer_t(void) {
  data = NULL;
  data_len = 0;
  init_data = NULL;
  init_data_len = 0;
}


r_buffer_t::r_buffer_t(unsigned char * d, uint32 l) {
  data = d;
  data_len = l;
}

void r_buffer_t::set(unsigned char * d, uint32 l) {
  init_data = d; 
  init_data_len = l;
  data = init_data; 
  data_len = init_data_len;
}

void r_buffer_t::reset(void) {
  data = init_data;
  data_len = init_data_len;
}

r_buffer_t & r_buffer_t::operator = (const r_buffer_t o) {
  init_data = o.init_data;
  data = o.data;
  init_data_len = o.init_data_len;
  data_len = o.data_len;
  return *this;
}

bool r_buffer_t::operator == (const r_buffer_t & o) const {
  if (data_len != o.data_len) return false;
  return (memcmp(data, o.data, data_len) == 0);
}

buffer_t::buffer_t(void) : r_buffer_t () {
  buf_len = 0;
  buf = NULL;
}


void buffer_t::detach(void) {
  buf = NULL;
  buf_len = 0; 
  clear();
}

buffer_t::~buffer_t() {
  free(data);
}

int buffer_t::clear(void) { 
  data = buf;
  data_len = 0; 
  return 0;
}

int buffer_t::extend(uint32 delta) {
  unsigned char * temp;
  uint32 temp_len = chunk(buf_len + delta);
  uint32 offset = data - buf;
  if ((temp = (unsigned char *)realloc(buf, temp_len)) == NULL)
      throw "Out of memory in buffer_t::extend";
  buf = temp;
  buf_len = temp_len;
  init_data = temp;
  init_data_len = temp_len;
  data = buf + offset;
  return 0;
}

int buffer_t::append(unsigned char * cp, uint32 len) {
  if (data_len + len > buf_len) extend(len);
  memcpy(&buf[data_len], cp, len);
  data_len+= len;
  return 0;
}

int buffer_t::append(const r_buffer_t b) {
  if (data_len + b.data_len > buf_len) extend(b.data_len);
  memcpy(&buf[data_len], b.data, b.data_len);
  data_len += b.data_len;
  return 0;
}

#endif



static bool zerobits(unsigned char * base, unsigned bitCount, long offset, unsigned startBit, unsigned runLength);
static bool bit(unsigned char * base, unsigned offset);
static void bitset(unsigned char * base, unsigned offset, unsigned bitCount);
static void bitset(unsigned char * base, unsigned offset);
static void bitclr(unsigned char * base, unsigned offset, unsigned bitCount);
static void bitclr(unsigned char * base, unsigned offset);

static void bitset(unsigned char * base, unsigned offset) {
  unsigned o, b;
  o = offset / 8;
  b = offset % 8;
  switch (b) {
  case 0: base[o] |= 0x80; break;
  case 1: base[o] |= 0x40; break;
  case 2: base[o] |= 0x20; break;
  case 3: base[o] |= 0x10; break;
  case 4: base[o] |= 0x08; break;
  case 5: base[o] |= 0x04; break;
  case 6: base[o] |= 0x02; break;
  case 7: base[o] |= 0x01; break;
  };
}

static void bitclr(unsigned char * base, unsigned offset, unsigned bitCount) {
  unsigned i;
  for (i=0;i<bitCount;i++) bitclr(base, offset+i);
}

static void bitclr(unsigned char * base, unsigned offset) {
  unsigned o, b;
  o = offset / 8;
  b = offset % 8;
  switch (b) {
  case 0: base[o] &= 0x7f; break;
  case 1: base[o] &= 0xbf; break;
  case 2: base[o] &= 0xdf; break;
  case 3: base[o] &= 0xef; break;
  case 4: base[o] &= 0xf7; break;
  case 5: base[o] &= 0xfb; break;
  case 6: base[o] &= 0xfd; break;
  case 7: base[o] &= 0xfe; break;
  };
}

static void bitset(unsigned char * base, unsigned offset, unsigned bitCount) {
  unsigned i;
  for (i=0;i<bitCount;i++) bitset(base, offset+i);
}

static bool bit(unsigned char * base, unsigned offset) {
  unsigned o, b;
  o = offset / 8;
  b = offset % 8;
  switch (b) {
  case 0: return ((base[o] & 0x80) != 0);
  case 1: return ((base[o] & 0x40) != 0);
  case 2: return ((base[o] & 0x20) != 0);
  case 3: return ((base[o] & 0x10) != 0);
  case 4: return ((base[o] & 0x08) != 0);
  case 5: return ((base[o] & 0x04) != 0);
  case 6: return ((base[o] & 0x02) != 0);
  case 7: return ((base[o] & 0x01) != 0);
  };
  return false;
}

static bool zerobits(unsigned char * base, unsigned bitCount, long offset, unsigned startBit, unsigned runLength) {
// Divide the run we're looking for into an initial byte, a length of null bytes, and a final byte.
  unsigned initialByte = 0;
  unsigned finalByte = 0;
  unsigned nullLength = 0;
  unsigned i;

  if ((offset * 8 + startBit + runLength) > bitCount) return false;

  if (startBit + runLength <= 8) {
// We're looking within a single byte.
    switch(startBit) {
    case 0: initialByte = 0x80; break;
    case 1: initialByte = 0x40; break;
    case 2: initialByte = 0x20; break;
    case 3: initialByte = 0x10; break;
    case 4: initialByte = 0x08; break;
    case 5: initialByte = 0x04; break;
    case 6: initialByte = 0x02; break;
    case 7: initialByte = 0x01; break;
    };
    for (i=1;i<runLength; i++) initialByte |= (initialByte >> 1);
    return ((base[offset] & initialByte) == 0);
  } else {
// We're stretching over at least two bytes.
    switch (startBit) {
    case 0: initialByte = 0xff; break;
    case 1: initialByte = 0x7f; break;
    case 2: initialByte = 0x3f; break;
    case 3: initialByte = 0x1f; break;
    case 4: initialByte = 0x0f; break;
    case 5: initialByte = 0x07; break;
    case 6: initialByte = 0x03; break;
    case 7: initialByte = 0x01; break;
    };

    if ((base[offset] & initialByte) != 0) return false;

    nullLength = ((startBit + runLength - 1) / 8) - 1;

    for (i=1;i<=nullLength;i++) if (base[offset + i] != 0) return false;

    switch ((startBit + runLength) % 8) {
    case 0: finalByte = 0xff;
    case 1: finalByte = 0x80;
    case 2: finalByte = 0xc0;
    case 3: finalByte = 0xe0;
    case 4: finalByte = 0xf0;
    case 5: finalByte = 0xf8;
    case 6: finalByte = 0xfc;
    case 7: finalByte = 0xfe;
    };
    return ((base[offset+nullLength+1] & finalByte) == 0);
  };
}


isam::isam(const char * theDir) {
  datFile = NULL;
  idxFile = NULL;
  bitFile = NULL;

  if (theDir) strncpy(dir, theDir, sizeof(dir));
  else dir[0] = 0;
  keymap = NULL;
  keymap_size = 0;
  keymap_valid = false;
  logicalBlocksize = 0;
  physicalBlocksize = 0;
  elements = 0;
  initialElements = 0;
  idxRecords = 0;
  bitBytes = 0;
  buffer = NULL;
  bitmap = NULL;
}

void isam::rebuild_keymap(void) {
  index_record_t idx;
  unsigned i;
  memset(keymap, 0, keymap_size);
  fseek(idxFile, 0, SEEK_SET);
  for (i=0; i<elements; i++) {
    fread(&idx, sizeof(index_record_t), 1, idxFile);
    if (idx.blockOffset != 0) bitset(keymap, i);
  };
  keymap_valid = true;  
}

uint32 isam::open(const char * table, bool build_keymap) {
  dbHeader_t dbHeader;
  char fname[1024];
  uint32 status = 0;
  unsigned datBlocks;

  status = ISM_FILE_NOT_FOUND;
  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jdx", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  idxFile = fopen(fname, "r+bc");
#else
  idxFile = fopen(fname, "r+b");
#endif
  if (idxFile == NULL) goto error;

  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jbm", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  bitFile = fopen(fname, "r+bc");
#else
  bitFile = fopen(fname, "r+b");
#endif
  if (bitFile == NULL) goto error;

  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jdt", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  datFile = fopen(fname, "r+bc");
#else
  datFile = fopen(fname, "r+b");
#endif
  if (datFile == NULL) goto error;

  
  status = ISM_DB_CORRUPT;
  if (fread(&dbHeader, sizeof(dbHeader), 1, datFile) != 1) goto error;

  if (memcmp(dbHeader.ident, st_ident, sizeof(st_ident)) != 0) goto error;

  logicalBlocksize = dbHeader.val.blocksize;
  physicalBlocksize = logicalBlocksize + sizeof(block_header_t);
  initialElements = 8 * ((dbHeader.val.elements + 7) / 8);
  
  fseek(idxFile, 0, SEEK_END);
  idxRecords = ftell(idxFile) / sizeof(index_record_t);
  elements = idxRecords;

  fseek(datFile, 0, SEEK_END);
  datBlocks = (ftell(datFile) - sizeof(dbHeader_t)) / physicalBlocksize;

  fseek(bitFile, 0, SEEK_END);
  bitBytes = ftell(bitFile);

  status = ISM_DB_CORRUPT;
  if (((datBlocks + 7) / 8) < bitBytes) goto error;

// Allocate the keymap
  keymap_size = (elements + 7) / 8;
  status = ISM_NOMEM;
  if ((keymap = (unsigned char *)malloc(keymap_size)) == NULL) goto error;

  memset(keymap, 0, keymap_size);

// Now generate the keymap from the index.
  if (build_keymap) rebuild_keymap();

// Allocate the block buffer.
  if ((buffer = (unsigned char *)malloc(physicalBlocksize)) == NULL) goto error;


// Allocate the bitmap buffer.
  if ((bitmap = (unsigned char *)malloc(bitBytes)) == NULL) goto error;
  status = ISM_INTERNAL_ERROR;
  fseek(bitFile, 0, SEEK_SET);
  if (fread(bitmap, bitBytes, 1, bitFile) != 1) goto error;
  
  
  return ISM_OK;

error:
  if (idxFile) fclose(idxFile);
  idxFile = NULL;
  if (bitFile) fclose(bitFile);
  bitFile = NULL;
  if (datFile) fclose(datFile);
  datFile = NULL;
  if (keymap) free(keymap);
  keymap = NULL;
  if (buffer) free(buffer);
  buffer = NULL;
  return status;

}

uint32 isam::create(const char * table,
                    unsigned theElements,
                    unsigned theBlocksize) {
  dbHeader_t dbHeader;
  char fname[1024];
  unsigned char buffer[1024];
  size_t fsz;
  uint32 status;
  long datBlocks;
  unsigned i;

  status = ISM_FILE_ERROR;
  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jdx", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  idxFile = fopen(fname, "w+bc");
#else
  idxFile = fopen(fname, "w+b");
#endif
  if (idxFile == NULL) goto error;

  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jdt", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  datFile = fopen(fname, "w+bc");
#else
  datFile = fopen(fname, "w+b");
#endif
  if (datFile == NULL) goto error;

  strcpy(fname, dir);
  strncat(fname, table, sizeof(fname) - strlen(fname));
  strncat(fname, ".jbm", sizeof(fname) - strlen(fname));

#ifdef _WIN32
  bitFile = fopen(fname, "w+bc");
#else
  bitFile = fopen(fname, "w+b");
#endif
  if (bitFile == NULL) goto error;
  

  memcpy(dbHeader.ident, st_ident, sizeof(st_ident));

  logicalBlocksize = theBlocksize;
  physicalBlocksize = logicalBlocksize + sizeof(block_header_t);
  initialElements = 8 * ((theElements + 7)/8);
  elements = initialElements;

  dbHeader.val.blocksize = logicalBlocksize;
  dbHeader.val.elements = initialElements;
  memset(dbHeader.padding, 0, sizeof(dbHeader.padding));
 
  fwrite(&dbHeader, 1, sizeof(dbHeader), datFile);

  memset(buffer, 0, sizeof(buffer));

// Zero the index...
  idxRecords = elements;
  fsz = elements * sizeof(index_record_t);
  for (i=0; i < fsz / sizeof(buffer); i++) fwrite(buffer, 1, sizeof(buffer), idxFile);
  if ((fsz % sizeof(buffer)) != 0) fwrite(buffer, 1, fsz % sizeof(buffer), idxFile);

// Zero the datafile...
  datBlocks = elements;
  fsz = (physicalBlocksize * datBlocks) + sizeof(block_header_t);
  for (i=0; i < fsz / sizeof(buffer); i++) fwrite(buffer, 1, sizeof(buffer), datFile);
  if ((fsz % sizeof(buffer)) != 0) fwrite(buffer, 1, fsz % sizeof(buffer), datFile);

// Zero the bitmap...
  fsz = (datBlocks + 7) / 8;
  for (i=0; i < fsz / sizeof(buffer); i++) fwrite(buffer, sizeof(buffer), 1, bitFile);
  if ((fsz % sizeof(buffer)) != 0) fwrite(buffer, fsz % sizeof(buffer), 1, bitFile);

  fclose(idxFile);
  fclose(bitFile);
  fclose(datFile);
  return open(table, false);

  return ISM_OK;

error:
  if (idxFile) fclose(idxFile);
  idxFile = NULL;
  if (bitFile) fclose(bitFile);
  bitFile = NULL;
  if (datFile) fclose(datFile);
  datFile = NULL;
  return status;
}

uint32 isam::close(void) {
  if (datFile) fclose(datFile);
  if (bitFile) fclose(bitFile);
  if (idxFile) fclose(idxFile);
  datFile = NULL;
  idxFile = NULL;
  bitFile = NULL;
  return ISM_OK;
}

uint32 isam::fetch(uint32 key, uint32 & flags, buffer_t & record) {
  index_record_t idx;
  unsigned offset;
  unsigned bytesLeft;
  unsigned bytesThisBlock;
  block_header_t block_header;
  record_header_t record_header;

  record.clear();
  
  if (datFile == NULL) return ISM_DB_NOT_OPEN;

  if (key > idxRecords) return ISM_RECORD_NOT_FOUND;
  fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
  fread(&idx, sizeof(idx), 1, idxFile);
  offset = idx.blockOffset;
  
  if (offset == 0) return ISM_RECORD_NOT_FOUND;
  
  flags = idx.flags;
  offset = block2fptr(offset);
  fseek(datFile, offset, SEEK_SET);
  fread(&block_header, sizeof(block_header_t), 1, datFile);
  if (block_header.key != key) return ISM_DB_CORRUPT;
  fread(&record_header, sizeof(record_header_t), 1, datFile);
  bytesLeft = record_header.recordLength;
  
  if (bytesLeft < logicalBlocksize - sizeof(record_header_t)) bytesThisBlock = bytesLeft;
  else bytesThisBlock = logicalBlocksize - sizeof(record_header_t);

  while (bytesLeft > 0) {
    fread(buffer, bytesThisBlock, 1, datFile);
    record.append(buffer, bytesThisBlock);
    bytesLeft -= bytesThisBlock;
    if (bytesLeft > 0) {
// We need to read the next block header...
      fread(&block_header, sizeof(block_header_t), 1, datFile);
      if (block_header.key != key) return ISM_DB_CORRUPT;
    };
    if (bytesLeft < logicalBlocksize) bytesThisBlock = bytesLeft;
    else bytesThisBlock = logicalBlocksize;
  };


  return ISM_OK;
}

static unsigned char nulls[32] = {0};

uint32 isam::store(uint32 key, uint32 flags, r_buffer_t & record, bool overwrite) {
// First search the bitmap for enough contiguous space to write the record.

  unsigned i;
  unsigned blockCount = (record.data_len + sizeof(record_header_t) + logicalBlocksize - 1) / logicalBlocksize;
  long blockNumber = 0;
  int found;
  index_record_t idx;
  block_header_t block_header;  
  record_header_t record_header;  
  long oldBlocknumber;
  unsigned oldBlockcount;
  long offset;
  unsigned bytesThisBlock;
  unsigned bytesLeft;
  unsigned char * dptr;

  if (key > idxRecords) return ISM_RECORD_NOT_FOUND;
  fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
  fread(&idx, sizeof(idx), 1, idxFile);
  oldBlocknumber = idx.blockOffset;
  if ((oldBlocknumber != 0) && !overwrite) return ISM_RECORD_EXISTS;

  if (blockCount == 1) {
// Optimize this case  
    for (i=0; i<bitBytes; i++) 
      if (bitmap[i] != 0xff) {
        if ((bitmap[i] & 0x80) == 0) blockNumber =i*8+1;
        else if ((bitmap[i] & 0x40) == 0) blockNumber =i*8+2;
        else if ((bitmap[i] & 0x20) == 0) blockNumber =i*8+3;
        else if ((bitmap[i] & 0x10) == 0) blockNumber =i*8+4;
        else if ((bitmap[i] & 0x08) == 0) blockNumber =i*8+5;
        else if ((bitmap[i] & 0x04) == 0) blockNumber =i*8+6;
        else if ((bitmap[i] & 0x02) == 0) blockNumber =i*8+7;
        else if ((bitmap[i] & 0x01) == 0) blockNumber =i*8+8;
        break;
      };
    if (blockNumber == 0) {
// We need to extend the file(s)
      blockNumber = bitBytes*8+1;
      fseek(bitFile, 0, SEEK_END);
      fwrite(nulls, sizeof(nulls), 1, bitFile);
      bitBytes += sizeof(nulls);
      fseek(datFile, 0, SEEK_END);
      memset(buffer, 0, physicalBlocksize);
      for (i=0; i < sizeof(nulls) * 8; i++) fwrite(buffer, physicalBlocksize, 1, datFile);
    };
  } else if (((blockCount + 7) / 8) > sizeof(nulls)) {
// For now...
    return ISM_RECORD_TOO_LONG;
  } else {
// We need to search for blockCount contiguous zero bits.  Ugh!
    found = 0;
    for (i=0; i<bitBytes; i++) {
      if (bitmap[i] == 0xff) continue; // Quickly skip over totally full bytes.
      if (((bitmap[i] & 0x80) == 0) && (zerobits(bitmap, 8*bitBytes, i, 0, blockCount))) blockNumber = i*8+1;
      else if (((bitmap[i] & 0x40) == 0) && (zerobits(bitmap, 8*bitBytes, i, 1, blockCount))) blockNumber = i*8+2;
      else if (((bitmap[i] & 0x20) == 0) && (zerobits(bitmap, 8*bitBytes, i, 2, blockCount))) blockNumber = i*8+3;
      else if (((bitmap[i] & 0x10) == 0) && (zerobits(bitmap, 8*bitBytes, i, 3, blockCount))) blockNumber = i*8+4;
      else if (((bitmap[i] & 0x08) == 0) && (zerobits(bitmap, 8*bitBytes, i, 4, blockCount))) blockNumber = i*8+5;
      else if (((bitmap[i] & 0x04) == 0) && (zerobits(bitmap, 8*bitBytes, i, 5, blockCount))) blockNumber = i*8+6;
      else if (((bitmap[i] & 0x02) == 0) && (zerobits(bitmap, 8*bitBytes, i, 6, blockCount))) blockNumber = i*8+7;
      else if (((bitmap[i] & 0x01) == 0) && (zerobits(bitmap, 8*bitBytes, i, 7, blockCount))) blockNumber = i*8+8;
      if (blockNumber != 0) break;
    };
    if (blockNumber == 0) {
// We need to extend the file(s) and their in-memory images.
      blockNumber = bitBytes*8+1;
      while ((blockNumber > 0) && (bit(bitmap, blockNumber-2) == false)) blockNumber--;
      fseek(bitFile, 0, SEEK_END);
      fwrite(nulls, sizeof(nulls), 1, bitFile);
      bitmap = (unsigned char *)realloc(bitmap, bitBytes + sizeof(nulls));
      memset(&bitmap[bitBytes], 0, sizeof(nulls));
      bitBytes += sizeof(nulls);

      fseek(datFile, 0, SEEK_END);
      memset(buffer, 0, physicalBlocksize);
      for (i=0; i < sizeof(nulls) * 8; i++) fwrite(buffer, physicalBlocksize, 1, datFile);
      fflush(datFile);
    };
  };
// Now blockNumber contains the block number we should start 
// writing, and we know there's enough space there...
  block_header.key = key;
  record_header.recordLength = record.data_len;
  offset = block2fptr(blockNumber);
  fseek(datFile, offset, SEEK_SET);
  fwrite(&block_header, sizeof(block_header), 1, datFile);
  fwrite(&record_header, sizeof(record_header), 1, datFile);
  bytesLeft = record.data_len;
  if (bytesLeft < logicalBlocksize - sizeof(record_header_t)) bytesThisBlock = bytesLeft;
  else bytesThisBlock = logicalBlocksize - sizeof(record_header_t);
  dptr = record.data;
  while (bytesLeft > 0) {
    fwrite(dptr, bytesThisBlock, 1, datFile);
    bytesLeft -= bytesThisBlock;
    if (bytesLeft > 0) {
      dptr+= bytesThisBlock;
      fwrite(&block_header, sizeof(block_header), 1, datFile);
      if (bytesLeft < logicalBlocksize) bytesThisBlock = bytesLeft;
      else bytesThisBlock = logicalBlocksize;
    };
  };
  fflush(datFile);

// We've appended the data.  Now mark the blocks allocated...

  bitset(bitmap, blockNumber-1, blockCount);
  fseek(bitFile, (blockNumber-1)/8, SEEK_SET);
  fwrite(&(bitmap[(blockNumber-1)/8]), 
        (blockNumber+blockCount-1)/8 - (blockNumber-1)/8 + 1, 
        1, 
        bitFile);
  fflush(bitFile);

// Now update the index file...

  idx.blockOffset = blockNumber;
  idx.flags = flags;
  fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
  fwrite(&idx, sizeof(idx), 1, idxFile);
  fflush(idxFile);

// finally mark the old blocks as free...
  
  if (oldBlocknumber != 0) {
    fseek(datFile, block2fptr(oldBlocknumber), SEEK_SET);
    fread(&block_header, sizeof(block_header), 1, datFile);
    if (block_header.key != key) return ISM_DB_CORRUPT;
    fread(&record_header, sizeof(record_header), 1, datFile);
    oldBlockcount = 
      (record_header.recordLength + sizeof(record_header_t) + logicalBlocksize - 1) / logicalBlocksize;
    bitclr(bitmap, oldBlocknumber-1, oldBlockcount);
    fseek(bitFile, (oldBlocknumber-1)/8, SEEK_SET);
    fwrite(&(bitmap[(oldBlocknumber-1)/8]), 
           (oldBlocknumber+oldBlockcount-1)/8 - (oldBlocknumber-1)/8 + 1, 
           1, 
           bitFile);
    fflush(bitFile);
  };
  
  return ISM_OK;
}

uint32 isam::new_key(void) {
// Search the keymap.  If no key is found, extend the index to create one.
  uint32 key;
  index_record_t idx;
  unsigned i;

  if (!keymap_valid) rebuild_keymap();
  
  for (i=0;i<keymap_size;i++) {
    if (keymap[i] != 0xff) break;
  };
  if (i<keymap_size) {
    if ((keymap[i] & 0x80) == 0) {
      keymap[i] |= 0x80;
      key = i*8+1;
    } else if ((keymap[i] & 0x40) == 0) {
      keymap[i] |= 0x40;
      key = i*8+2;
    } else if ((keymap[i] & 0x20) == 0) {
      keymap[i] |= 0x20;
      key = i*8+3;
    } else if ((keymap[i] & 0x10) == 0) {
      keymap[i] |= 0x10;
      key = i*8+4;
    } else if ((keymap[i] & 0x08) == 0) {
      keymap[i] |= 0x08;
      key = i*8+5;
    } else if ((keymap[i] & 0x04) == 0) {
      keymap[i] |= 0x04;
      key = i*8+6;
    } else if ((keymap[i] & 0x02) == 0) {
      keymap[i] |= 0x02;
      key = i*8+7;
    } else if ((keymap[i] & 0x01) == 0) {
      keymap[i] |= 0x01;
      key = i*8+8;
    };
  } else {
// we need to extend the keymap

    keymap = (unsigned char *)realloc(keymap, keymap_size + (initialElements / 8));
    memset(&keymap[keymap_size], 0, initialElements/8);
    key = keymap_size * 8;
    keymap[keymap_size] = 0x80;
    keymap_size += initialElements/8;
  };

// Now we've picked a key, we need to ensure there's a slot in the index file for it...

  if (key > idxRecords) {
    idx.blockOffset = 0;
    fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
    fwrite(&idx, sizeof(idx), 1, idxFile);
    fflush(idxFile);
  };
  return key;
}

uint32 isam::compact(void) {
  return ISM_OK;
}

uint32 isam::rebuild_index(void) {
  return ISM_OK;
}

long isam::block2fptr(uint32 block) {
  if (block == 0) return -1l;
  return (block-1) * physicalBlocksize + sizeof(dbHeader_t);
}

isam::~isam() {
  if (idxFile) fclose(idxFile);
  idxFile = NULL;
  if (bitFile) fclose(bitFile);
  bitFile = NULL;
  if (datFile) fclose(datFile);
  datFile = NULL;
  if (keymap) free(keymap);
  keymap = NULL;
  if (buffer) free(buffer);
  buffer = NULL;
  if (bitmap) free(bitmap);
  bitmap = NULL;

 
}

uint32 isam::delete_record(uint32 key) {

  index_record_t idx;
  block_header_t block_header;
  record_header_t record_header;
  long oldBlocknumber;
  unsigned oldBlockcount;
  unsigned blockCount;
  unsigned blockNumber;

  if (!keymap_valid) rebuild_keymap();

  if (key > idxRecords) return ISM_RECORD_NOT_FOUND;
  fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
  fread(&idx, sizeof(idx), 1, idxFile);
  oldBlocknumber = idx.blockOffset;
  if (oldBlocknumber == 0) return ISM_RECORD_NOT_FOUND;
  
// First remove the record from the index.

  idx.blockOffset = 0;
  fseek(idxFile, (key-1) * sizeof(idx), SEEK_SET);
  fwrite(&idx, sizeof(idx), 1, idxFile);
  fflush(idxFile);
  bitclr(keymap, key-1);

// Now run through the record, resetting the ownership key...


  fseek(datFile, block2fptr(oldBlocknumber), SEEK_SET);
  fread(&block_header, sizeof(block_header), 1, datFile);
  if (block_header.key != key) return ISM_DB_CORRUPT;
  fread(&record_header, sizeof(record_header), 1, datFile);
  oldBlockcount = 
      (record_header.recordLength + sizeof(record_header_t) + logicalBlocksize - 1) / logicalBlocksize;

  blockCount = 0; 
  blockNumber = oldBlocknumber;
  while (blockCount < oldBlockcount) {
    block_header.key = 0;
    fseek(datFile, block2fptr(blockNumber), SEEK_SET);
    fwrite(&block_header, sizeof(block_header), 1, datFile);
    blockCount++;
    blockNumber++;
    if (blockCount < oldBlockcount) {
      fseek(datFile, block2fptr(blockNumber), SEEK_SET);
      fread(&block_header, sizeof(block_header), 1, datFile);
      if (block_header.key != key) return ISM_DB_CORRUPT;
    };
  };
  fflush(datFile);

// Almost done.  Just reset the allocation bitmap
  bitclr(bitmap, oldBlocknumber-1, oldBlockcount);
  fseek(bitFile, (oldBlocknumber-1)/8, SEEK_SET);
  fwrite(&(bitmap[(oldBlocknumber-1)/8]), 
         (oldBlocknumber+oldBlockcount-1)/8 - (oldBlocknumber-1)/8 + 1, 
         1, 
         bitFile);
  fflush(bitFile);
  
  return ISM_OK;
}

uint32 isam::enumerate_all(buffer_t & keys, buffer_t * flags) {
  return enumerate_bits(0xfffffffflu, keys, flags);
}

uint32 isam::enumerate_bits(uint32 mask, buffer_t & keys, buffer_t * flags) {

  index_record_t idx;
  uint32 i;
  uint32 theKey;
  size_t recCnt;
 
  keys.clear();
  fseek(idxFile, 0l, SEEK_SET);
  for (i=0; i<elements; i++) {
    if ((recCnt = fread(&idx, sizeof(index_record_t), 1, idxFile)) != 1) {
      return ISM_DB_CORRUPT;
    };
    if (idx.blockOffset == 0) {
      bitclr(keymap, i);
    } else {
      bitset(keymap, i);
      if (idx.flags & mask) {
        theKey = i+1;
        keys.append((unsigned char *)&theKey, sizeof(uint32));
        if (flags) flags->append((unsigned char *)&idx.flags, sizeof(uint32));
      };
    };
  };
  keymap_valid = true;
  return 0;
}

uint32 isam::enumerate_match(uint32 mask, uint32 value, buffer_t & keys, buffer_t * flags) {
  uint32 i;
  uint32 theKey;
  index_record_t idx;
  size_t recCnt;

  value = value & mask;
  keys.clear();
  fseek(idxFile, 0, SEEK_SET);
  for (i=0; i<elements; i++) {
    if ((recCnt = fread(&idx, sizeof(index_record_t), 1, idxFile)) != 1) {
      return ISM_DB_CORRUPT;
    };
    if (idx.blockOffset == 0) {
      bitclr(keymap, i);
    } else {
      bitset(keymap, i);
      if ((idx.flags & mask) == value) {
        theKey = i+1;
        keys.append((unsigned char *)&theKey, sizeof(uint32));
        if (flags) flags->append((unsigned char *)&idx.flags, sizeof(uint32));
      };
    };
  };
  keymap_valid = true;
  return 0;
}
