/* ***************************************************************** *
 * 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 <slindex.h>
#include <malloc.h>
#include <stdlib.h>
#ifdef _WIN32
#include <winsock2.h>
#else
#include <sockets.h>
#endif

#define DEFAULT_MAX_LEVELS 10

static int p = RAND_MAX / 3;

typedef struct {
  char ident[32];
  uint32 maxLevels;
  uint32 currentMax;
  uint32 root;
} header_val_t;

typedef struct {
  header_val_t val;
  unsigned char padding[64-sizeof(header_val_t)];
} header_t;

static char s_ident[32] = "Jonah Skip-list Index V1.0\n";


uint32 slnode_t::read(FILE * f) {
  uint32 b;
  int i;

  if (fread(&b, sizeof(uint32), 1, f) != 1) return ISM_DB_CORRUPT;

  if (keySize != ntohl(b)) return ISM_DB_CORRUPT;

  if (fread(&b, sizeof(uint32), 1, f) != 1) return ISM_DB_CORRUPT;
  if (maxLevel != ntohl(b)) return ISM_DB_CORRUPT;

  if (fread(&b, sizeof(uint32), 1, f) != 1) return ISM_DB_CORRUPT;
  level = ntohl(b);
  if (level > maxLevel) return ISM_DB_CORRUPT;

  if (fread(key, keySize, 1, f) != 1) return ISM_DB_CORRUPT;

  if (fread(&b, sizeof(uint32), 1, f) != 1) return ISM_DB_CORRUPT;
  data = ntohl(b);

  if (fread(ptrs, sizeof(uint32) * maxLevel, 1, f) != 1) return ISM_DB_CORRUPT;
  for (i=0; i < maxLevel; i++) ptrs[i] = ntohl(ptrs[i]);

  if (fread(keys, keySize * maxLevel, 1, f) != 1) return ISM_DB_CORRUPT;

  return 0;  
}

uint32 slnode_t::write(FILE * f) {
  uint32 b;
  int i;

  if (level > maxLevel) return ISM_DB_CORRUPT;

  b = htonl(keySize);
  fwrite(&b, sizeof(uint32), 1, f);

  b = htonl(maxLevel);
  fwrite(&b, sizeof(uint32), 1, f);

  b = htonl(level);
  fwrite(&b, sizeof(uint32), 1, f);

  fwrite(key, keySize, 1, f);

  b = htonl(data);
  fwrite(&b, sizeof(uint32), 1, f);

  for (i=0; i<maxLevel; i++) {
    b = htonl(ptrs[i]);
    fwrite(&b, sizeof(uint32), 1, f);
  };

  fwrite(keys, keySize * maxLevel, 1, f);

  return 0;  
}

slnode_t::slnode_t(uint32 max_level, uint32 key_size) {
  keySize = key_size;
  maxLevel = max_level;
  ptrs = (uint32 *)malloc(sizeof(uint32) * maxLevel);
  memset(ptrs, 0, sizeof(uint32) * maxLevel);
  keys = (unsigned char *)malloc(keySize * maxLevel);
  memset(keys, 0, keySize * maxLevel);
  key = (unsigned char *)malloc(keySize);
  memset(key, 0, keySize);
  level = 0;
}

slnode_t::~slnode_t() {
  if (ptrs) free(ptrs);
  if (keys) free(keys);
  if (key) free(key);
}

uint32 slindex_t::logical_to_physical(uint32 offset) const {
  return offset + header_size + sizeof(header_t);
}

uint32 slindex_t::physical_to_logical(uint32 offset) const {
  return offset - header_size - sizeof(header_t);
}

uint32 slnode_t::pick_level(uint32 currentMax) {
  uint32 newLevel = 1;
  while ((newLevel < maxLevel) && (newLevel <= currentMax) && (rand() < p)) newLevel++;
  return newLevel;
}


uint32 slindex_t::read_node(uint32 offset, slnode_t * nodePtr) {
  fseek(file, logical_to_physical(offset), SEEK_SET);
  return nodePtr->read(file);  
}

uint32 slindex_t::write_node(uint32 offset, slnode_t * nodePtr) {
  fseek(file, logical_to_physical(offset), SEEK_SET);
  return nodePtr->write(file);  
}

slindex_t::slindex_t(const char * name) : index_t(name) {
  maxLevels = 0;
  dataOffset = 0;
  newNode = NULL;
  curNode = NULL;
  rootNode = NULL;
  newPtr = 0;
  curPtr = 0;
  rootPtr = 0;
}

slindex_t::~slindex_t() {
}

uint32 slindex_t::open(void) {
  uint32 status;
  header_t header;
  delete curNode;
  curNode = NULL;
  delete rootNode;
  rootNode = NULL;
  delete newNode;
  newNode = NULL;
  rootPtr = 0;
  curPtr = 0;
  newPtr = 0;
  status = index_t::open();
  if (status) return status;
  if (fseek(file, header_size, SEEK_SET) < 0) {
    index_t::close();
    return ISM_DB_CORRUPT;
  };
  if (created) {
    maxLevels = DEFAULT_MAX_LEVELS;
    currentMax = 0;
    strncpy(header.val.ident, s_ident, sizeof(header.val.ident));
    header.val.maxLevels = htonl(maxLevels);
    header.val.currentMax = htonl(currentMax);
    header.val.root = htonl(0);
    fwrite(&header, sizeof(header), 1, file);
    rootPtr = 0;
    rootNode = new slnode_t(maxLevels, keySize);
    write_node(rootPtr, rootNode);
  } else {
    if (fread(&header, sizeof(header), 1, file) != 1) {
      index_t::close();
      return ISM_DB_CORRUPT;
    }
    if (strncmp(header.val.ident, s_ident, sizeof(header.val.ident)) != 0) {
      index_t::close();
      return ISM_DB_CORRUPT;
    };
    maxLevels = ntohl(header.val.maxLevels);
    currentMax = ntohl(header.val.currentMax);
    if (currentMax > maxLevels) {
      index_t::close();
      return ISM_DB_CORRUPT;
    };
    rootPtr = ntohl(header.val.root);
    rootNode = new slnode_t(maxLevels, keySize);
    read_node(rootPtr, rootNode);
  };
  curPtr = 0;
  dataOffset = header_size + sizeof(header_t);
  curNode = new slnode_t(maxLevels, keySize);
  newNode = new slnode_t(maxLevels, keySize);
  return 0;
}

uint32 slindex_t::close(void) {
  maxLevels = 0;
  dataOffset = 0;
  delete curNode;
  curNode = NULL;
  delete rootNode;
  rootNode = NULL;
  delete newNode;
  newNode = NULL;
  return index_t::close();
}

uint32 slindex_t::update_header(void) {
  header_t header;
  fseek(file, header_size, SEEK_SET);
  strncpy(header.val.ident, s_ident, sizeof(header.val.ident));
  header.val.maxLevels = htonl(maxLevels);
  header.val.currentMax = htonl(currentMax);
  header.val.root = htonl(rootPtr);
  if (fwrite(&header, sizeof(header), 1, file) != 1) return ISM_FILE_ERROR;
  return 0;
}

uint32 slindex_t::lookup(const unsigned char * key, 
                         uint32 & result,
                         uint32 * context) {
  int i;
  int res;
  slnode_t * n = rootNode;
  uint32 loc_context = 0;
  uint32 status;

  if (context == NULL) context = &loc_context;

  result = 0;
  if (*context) {
// This is a follow-on call to retrieve the next record for the given key
    curPtr = *context;  
    if (status = read_node(curPtr, curNode)) return status;
    res = keycmp(key, curNode->key);
    if (res == 0) {
      result = curNode->data;
      if (keycmp(key, &(curNode->keys[0])) == 0) *context = curNode->ptrs[0];
      else *context = 0;
      return 0;
    } else {
      *context = 0;
      return ISM_RECORD_NOT_FOUND;
    };
  } else {
    for (i = n->level; i>0; i--) { 
      if (n->ptrs[i-1] == 0) continue;
      if ((res = keycmp(key, &(n->keys[keySize*(i-1)]))) >= 0) break;
    };
    if (i == 0) {
// We didn't find the key
      *context = 0;
      return ISM_RECORD_NOT_FOUND;
    } else {
      curPtr = n->ptrs[i-1];
      read_node(curPtr, curNode);
      n = curNode;
      if (res == 0) {
// We found the exact record, and it should be the record we just read...
        result = n->data;
        if (keycmp(key, &(n->keys[0])) == 0) *context = n->ptrs[0];
        else *context = 0;
        return 0;
      } else {
// We need to skip and try again
        while (1) {
          for (i = n->level; i>0; i--) { 
            if (n->ptrs[i-1] == 0) continue;
            if ((res = keycmp(key, &(n->keys[keySize*(i-1)]))) >= 0) break;
          };
          if (i == 0) {
// We didn't find the key
            *context = 0;
            return ISM_RECORD_NOT_FOUND;
          } else {
            curPtr = n->ptrs[i-1];
            read_node(curPtr, curNode);
            n = curNode;
            if (res == 0) {
// We found the exact record, and it should be the record we just read...
              result = n->data;
              if (keycmp(key, &(n->keys[0])) == 0) *context = n->ptrs[0];
              else *context = 0;
              return 0;
            };
// Else skip and try again
          };
        };        
      };
    };
  };
}



uint32 slindex_t::insert(const unsigned char * key, 
                         uint32 result) {
// First see if there is an existing record for this key...
  uint32 curRes;
  uint32 level;
  slnode_t * n;
  int cmp;
  uint32 ptr;
  int i;
  uint32 searchStatus;
  
  searchStatus = lookup(key, curRes);

  if (!duplicatesAllowed) {
// Verify that the record doesn't currently exist...
    if (searchStatus == 0) {
      if (curRes == result) return 0;  // If it exists, but is the same, ignore
      return ISM_RECORD_EXISTS;
    };
  };
// Record isn't already there, so first work out where we're going to add the new node...
  fseek(file, 0, SEEK_END);
  newPtr = physical_to_logical(ftell(file));
  n = newNode;
  memset(newNode->ptrs, 0, sizeof(uint32) * maxLevels);
  memset(newNode->keys, 0, keySize * maxLevels);
  newNode->data = result;
  memcpy(newNode->key, key, keySize);
// If we are inserting a duplicate record, we need to ensure that the levels of all
// but the first key is 1...
  if (searchStatus == 0) level = 1;
  else if ((level = n->pick_level(currentMax)) > currentMax) {
    currentMax = level;
    update_header();
  };
  newNode->level = level;
// Now fix up the pointers...
// We start at the highest level of the new node we're adding.

  n = rootNode;
  ptr = rootPtr;

  if (newNode->level > rootNode->level) {
    for (i=rootNode->level; i<newNode->level; i++) {
      rootNode->ptrs[i] = 0;
      memset(&(rootNode->keys[i * keySize]), 0, keySize);
    };
    rootNode->level = newNode->level;
  };

  for (i=rootNode->level; i>0; i--) {
// For each level, we find the node immediately before the new node (in
// its skip-list), and if the new node exists on this level, change the 
// pointers on the new node and the existing node.
    while ((n->ptrs[i-1] != 0) && 
           ((cmp = keycmp(newNode->key,
                          &(n->keys[keySize*(i-1)]))) >= 0)) {
// Move forward along this skip-list 'til we find the right place...
      curPtr = n->ptrs[i-1];
      read_node(curPtr, curNode);
      n = curNode;
      ptr = curPtr;
    };
    if (i <= newNode->level) {
      memcpy(&(newNode->keys[keySize*(i-1)]),
             &(n->keys[keySize*(i-1)]),
             keySize);
      newNode->ptrs[i-1] = n->ptrs[i-1];
  
      n->ptrs[i-1] = newPtr;
      memcpy(&(n->keys[keySize*(i-1)]),
             newNode->key,
             keySize);
      write_node(ptr, n);
    };
  };
  write_node(newPtr, newNode);
  return 0;  
}

uint32 slindex_t::replace(const unsigned char * key, uint32 result) {
  return ISM_OPERATION_NOT_SUPPORTED;
}
