/*
 * Copyright (c) 2020 Red Hat, Inc.
 *
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA. 
 *
 * $Id: //eng/uds-releases/jasper/src/uds/deltaIndex.h#4 $
 */

#ifndef DELTAINDEX_H
#define DELTAINDEX_H 1

#include "compiler.h"
#include "deltaMemory.h"

enum {
  // the number of extra bytes and bits needed to store a collision entry
  COLLISION_BYTES = UDS_CHUNK_NAME_SIZE,
  COLLISION_BITS  = COLLISION_BYTES * CHAR_BIT
};

typedef struct deltaIndex {
  DeltaMemory *deltaZones;    // The zones
  unsigned int numZones;      // The number of zones
  unsigned int numLists;      // The number of delta lists
  unsigned int listsPerZone;  // Lists per zone (last zone can be smaller)
  bool isMutable;             // True if this index is mutable
  byte tag;                   // Tag belonging to this delta index
} DeltaIndex;

/*
 * A DeltaIndexPage describes a single page of a chapter index.  The deltaIndex
 * field allows the page to be treated as an immutable DeltaIndex.  We use the
 * deltaMemory field to treat the chapter index page as a single zone index,
 * and without the need to do an additional memory allocation.
 */

typedef struct deltaIndexPage {
  DeltaIndex   deltaIndex;
  // These values are loaded from the DeltaPageHeader
  unsigned int lowestListNumber;
  unsigned int highestListNumber;
  uint64_t     virtualChapterNumber;
  // This structure describes the single zone of a delta index page.
  DeltaMemory  deltaMemory;
} DeltaIndexPage;

/*
 * Notes on the DeltaIndexEntries:
 *
 * The fields documented as "public" can be read by any code that uses a
 * DeltaIndex.  The fields documented as "private" carry information
 * between DeltaIndex method calls and should not be used outside the
 * DeltaIndex module.
 *
 * (1) The DeltaIndexEntry is used like an iterator when searching a delta
 *     list.
 *
 * (2) And it is also the result of a successful search and can be used to
 *     refer to the element found by the search.
 *
 * (3) And it is also the result of an unsuccessful search and can be used
 *     to refer to the insertion point for a new record.
 *
 * (4) If atEnd==true, the DeltaListEntry can only be used as the insertion
 *     point for a new record at the end of the list.
 *
 * (5) If atEnd==false and isCollision==true, the DeltaListEntry fields
 *     refer to a collision entry in the list, and the DeltaListEntry can
 *     be used a a reference to this entry.
 *
 * (6) If atEnd==false and isCollision==false, the DeltaListEntry fields
 *     refer to a non-collision entry in the list.  Such DeltaListEntries
 *     can be used as a reference to a found entry, or an insertion point
 *     for a non-collision entry before this entry, or an insertion point
 *     for a collision entry that collides with this entry.
 */

typedef struct deltaIndexEntry {
  // Public fields
  unsigned int key;          // The key for this entry
  bool         atEnd;        // We are after the last entry in the list
  bool         isCollision;  // This record is a collision
  // Private fields (but DeltaIndex_t1 cheats and looks at them)
  bool           listOverflow;  // This delta list overflowed
  unsigned short valueBits;     // The number of bits used for the value
  unsigned short entryBits;     // The number of bits used for the entire entry
  DeltaMemory   *deltaZone;     // The delta index zone
  DeltaList     *deltaList;     // The delta list containing the entry,
  unsigned int   listNumber;    // The delta list number
  uint32_t       offset;        // Bit offset of this entry within the list
  unsigned int   delta;         // The delta between this and previous entry
  DeltaList      tempDeltaList; // Temporary delta list for immutable indices
} DeltaIndexEntry;

typedef struct {
  size_t memoryAllocated;  // Number of bytes allocated
  RelTime rebalanceTime;   // The time spent rebalancing
  int  rebalanceCount;     // Number of memory rebalances
  long recordCount;        // The number of records in the index
  long collisionCount;     // The number of collision records
  long discardCount;       // The number of records removed
  long overflowCount;      // The number of UDS_OVERFLOWs detected
  unsigned int numLists;   // The number of delta lists
} DeltaIndexStats;

/**
 * Initialize a delta index.
 *
 * @param deltaIndex      The delta index to initialize
 * @param numZones        The number of zones in the index
 * @param numLists        The number of delta lists in the index
 * @param meanDelta       The mean delta value
 * @param numPayloadBits  The number of bits in the payload or value
 * @param memorySize      The number of bytes in memory for the index
 *
 * @return error code or UDS_SUCCESS
 **/
int initializeDeltaIndex(DeltaIndex *deltaIndex, unsigned int numZones,
                         unsigned int numLists, unsigned int meanDelta,
                         unsigned int numPayloadBits, size_t memorySize)
  __attribute__((warn_unused_result));

/**
 * Initialize an immutable delta index page.
 *
 * @param deltaIndexPage  The delta index page to initialize
 * @param expectedNonce   If non-zero, the expected nonce.
 * @param meanDelta       The mean delta value
 * @param numPayloadBits  The number of bits in the payload or value
 * @param memory          The memory page
 * @param memSize         The size of the memory page
 *
 * @return error code or UDS_SUCCESS
 **/
int initializeDeltaIndexPage(DeltaIndexPage *deltaIndexPage,
                             uint64_t        expectedNonce,
                             unsigned int    meanDelta,
                             unsigned int    numPayloadBits,
                             byte           *memory,
                             size_t          memSize)
  __attribute__((warn_unused_result));

/**
 * Uninitialize a delta index.
 *
 * @param deltaIndex  The delta index to uninitialize
 **/
void uninitializeDeltaIndex(DeltaIndex *deltaIndex);

/**
 * Empty the delta index.
 *
 * @param deltaIndex  The delta index being emptied.
 **/
void emptyDeltaIndex(const DeltaIndex *deltaIndex);

/**
 * Empty a zone of the delta index.
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone being emptied
 **/
void emptyDeltaIndexZone(const DeltaIndex *deltaIndex,
                         unsigned int zoneNumber);

/**
 * Pack delta lists from a mutable delta index into an immutable delta index
 * page.  A range of delta lists (starting with a specified list index) is
 * copied from the mutable delta index into a memory page used in the immutable
 * index.  The number of lists copied onto the page is returned to the caller.
 *
 * @param deltaIndex            The delta index being converted
 * @param headerNonce           The header nonce to store
 * @param headerNativeEndian    If true, write native endian header
 * @param memory                The memory page to use
 * @param memSize               The size of the memory page
 * @param virtualChapterNumber  The virtual chapter number
 * @param firstList             The first delta list number to be copied
 * @param numLists              The number of delta lists that were copied
 *
 * @return error code or UDS_SUCCESS.  On UDS_SUCCESS, the numLists
 *         argument contains the number of lists copied.
 **/
int packDeltaIndexPage(const DeltaIndex *deltaIndex,
                       uint64_t          headerNonce,
                       bool              headerNativeEndian,
                       byte             *memory,
                       size_t            memSize,
                       uint64_t          virtualChapterNumber,
                       unsigned int      firstList,
                       unsigned int     *numLists)
  __attribute__((warn_unused_result));


/**
 * Set the tag value used when saving and/or restoring a delta index.
 *
 * @param deltaIndex  The delta index
 * @param tag         The tag value
 **/
void setDeltaIndexTag(DeltaIndex *deltaIndex, byte tag);

/**
 * Start restoring a delta index from an input stream.
 *
 * @param deltaIndex       The delta index to read into
 * @param bufferedReaders  The buffered readers to read the delta index from
 * @param numReaders       The number of buffered readers
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int startRestoringDeltaIndex(const DeltaIndex *deltaIndex,
                             BufferedReader **bufferedReaders, int numReaders)
  __attribute__((warn_unused_result));

/**
 * Have all the data been read while restoring a delta index from an
 * input stream?
 *
 * @param deltaIndex  The delta index
 *
 * @return true if all the data are read
 **/
bool isRestoringDeltaIndexDone(const DeltaIndex *deltaIndex);

/**
 * Restore a saved delta list
 *
 * @param deltaIndex  The delta index
 * @param dlsi        The DeltaListSaveInfo describing the delta list
 * @param data        The saved delta list bit stream
 *
 * @return error code or UDS_SUCCESS
 **/
int restoreDeltaListToDeltaIndex(const DeltaIndex *deltaIndex,
                                 const DeltaListSaveInfo *dlsi,
                                 const byte data[DELTA_LIST_MAX_BYTE_COUNT])
  __attribute__((warn_unused_result));

/**
 * Abort restoring a delta index from an input stream.
 *
 * @param deltaIndex  The delta index
 **/
void abortRestoringDeltaIndex(const DeltaIndex *deltaIndex);

/**
 * Start saving a delta index zone to a buffered output stream.
 *
 * @param deltaIndex      The delta index
 * @param zoneNumber      The zone number
 * @param bufferedWriter  The index state component being written
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int startSavingDeltaIndex(const DeltaIndex *deltaIndex,
                          unsigned int zoneNumber,
                          BufferedWriter *bufferedWriter)
  __attribute__((warn_unused_result));

/**
 * Have all the data been written while saving a delta index zone to an
 * output stream?  If the answer is yes, it is still necessary to call
 * finishSavingDeltaIndex(), which will return quickly.
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return true if all the data are written
 **/
bool isSavingDeltaIndexDone(const DeltaIndex *deltaIndex,
                            unsigned int zoneNumber);

/**
 * Finish saving a delta index zone to an output stream.  Force the writing
 * of all of the remaining data.  If an error occurred asynchronously
 * during the save operation, it will be returned here.
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int finishSavingDeltaIndex(const DeltaIndex *deltaIndex,
                           unsigned int zoneNumber)
  __attribute__((warn_unused_result));

/**
 * Abort saving a delta index zone to an output stream.  If an error
 * occurred asynchronously during the save operation, it will be dropped.
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int abortSavingDeltaIndex(const DeltaIndex *deltaIndex,
                          unsigned int zoneNumber)
  __attribute__((warn_unused_result));

/**
 * Compute the number of bytes required to save a delta index
 *
 * @param numLists    The number of delta lists in the index
 * @param memorySize  The number of bytes in memory for the index
 *
 * @return numBytes  The number of bytes required to save the master index
 **/
size_t computeDeltaIndexSaveBytes(unsigned int numLists, size_t memorySize)
  __attribute__((warn_unused_result));

/**
 * Validate the delta index
 *
 * @param deltaIndex  The delta index
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int validateDeltaIndex(const DeltaIndex *deltaIndex)
  __attribute__((warn_unused_result));

/**
 * Prepare to search for an entry in the specified delta list.
 *
 * <p> This is always the first routine to be called when dealing with delta
 * index entries. It is always followed by calls to nextDeltaIndexEntry to
 * iterate through a delta list. The fields of the DeltaIndexEntry argument
 * will be set up for iteration, but will not contain an entry from the list.
 *
 * @param deltaIndex  The delta index to search
 * @param listNumber  The delta list number
 * @param key         First delta list key that the caller is interested in
 * @param readOnly    True if this is a read-only operation
 * @param iterator    The index entry being used to search through the list
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int startDeltaIndexSearch(const DeltaIndex *deltaIndex,
                          unsigned int listNumber, unsigned int key,
                          bool readOnly, DeltaIndexEntry *iterator)
  __attribute__((warn_unused_result));

/**
 * Find the next entry in the specified delta list
 *
 * @param deltaEntry  Info about an entry, which is updated to describe the
 *                    following entry
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int nextDeltaIndexEntry(DeltaIndexEntry *deltaEntry)
  __attribute__((warn_unused_result));

/**
 * Remember the position of a delta index entry, so that we can use it when
 * starting the next search.
 *
 * @param deltaEntry  Info about an entry found during a search.  This should
 *                    be the first entry that matches the key exactly (i.e.
 *                    not a collision entry), or the first entry with a key
 *                    greater than the entry sought for.
 *
 * @return UDS_SUCCESS on success, or an error code on failure
 **/
int rememberDeltaIndexOffset(const DeltaIndexEntry *deltaEntry)
  __attribute__((warn_unused_result));

/**
 * Find the delta index entry, or the insertion point for a delta index
 * entry.
 *
 * @param deltaIndex  The delta index to search
 * @param listNumber  The delta list number
 * @param key         The key field being looked for
 * @param name        The 256 bit full name
 * @param readOnly    True if this is a read-only index search
 * @param deltaEntry  Updated to describe the entry being looked for
 *
 * @return UDS_SUCCESS or an error code
 **/
int getDeltaIndexEntry(const DeltaIndex *deltaIndex, unsigned int listNumber,
                       unsigned int key, const byte *name, bool readOnly,
                       DeltaIndexEntry *deltaEntry)
  __attribute__((warn_unused_result));

/**
 * Get the full name from a collision DeltaIndexEntry
 *
 * @param deltaEntry  The delta index record
 * @param name        The 256 bit full name
 *
 * @return UDS_SUCCESS or an error code
 **/
int getDeltaEntryCollision(const DeltaIndexEntry *deltaEntry, byte *name)
  __attribute__((warn_unused_result));

/**
 * Get the bit offset into delta memory of a delta index entry.
 *
 * @param deltaEntry  The delta index entry
 *
 * @return the bit offset into delta memory
 **/
static INLINE uint64_t getDeltaEntryOffset(const DeltaIndexEntry *deltaEntry)
{
  return getDeltaListStart(deltaEntry->deltaList) + deltaEntry->offset;
}

/**
 * Get the number of bits used to encode the entry key (the delta).
 *
 * @param entry         The delta index record
 *
 * @return the number of bits used to encode the key
 **/
static INLINE unsigned int getDeltaEntryKeyBits(const DeltaIndexEntry *entry)
{
  /*
   * Derive keyBits by subtracting the sizes of the other two fields from the
   * total. We don't actually use this for encoding/decoding, so it doesn't
   * need to be super-fast. We save time where it matters by not storing it.
   */
  return (entry->entryBits - entry->valueBits
          - (entry->isCollision ? COLLISION_BITS : 0));
}

/**
 * Get the value field of the DeltaIndexEntry
 *
 * @param deltaEntry  The delta index record
 *
 * @return the value
 **/
static INLINE unsigned int getDeltaEntryValue(const DeltaIndexEntry *deltaEntry)
{
  return getField(deltaEntry->deltaZone->memory,
                  getDeltaEntryOffset(deltaEntry), deltaEntry->valueBits);
}

/**
 * Set the value field of the DeltaIndexEntry
 *
 * @param deltaEntry  The delta index record
 * @param value       The new value
 *
 * @return UDS_SUCCESS or an error code
 **/
int setDeltaEntryValue(const DeltaIndexEntry *deltaEntry, unsigned int value)
  __attribute__((warn_unused_result));

/**
 * Create a new entry in the delta index
 *
 * @param deltaEntry  The delta index entry that indicates the insertion point
 *                    for the new record.  For a collision entry, this is the
 *                    non-collision entry that the new entry collides with.
 *                    For a non-collision entry, this new entry is inserted
 *                    before the specified entry.
 * @param key         The key field
 * @param value       The value field
 * @param name        For collision entries, the 256 bit full name;
 *                    Otherwise null
 *
 * @return UDS_SUCCESS or an error code
 **/
int putDeltaIndexEntry(DeltaIndexEntry *deltaEntry, unsigned int key,
                       unsigned int value, const byte *name)
  __attribute__((warn_unused_result));

/**
 * Remove an existing delta index entry, and advance to the next entry in
 * the delta list.
 *
 * @param deltaEntry  On call the delta index record to remove.  After
 *                    returning, the following entry in the delta list.
 *
 * @return UDS_SUCCESS or an error code
 **/
int removeDeltaIndexEntry(DeltaIndexEntry *deltaEntry)
  __attribute__((warn_unused_result));

/**
 * Map a delta list number to a delta zone number
 *
 * @param deltaIndex  The delta index
 * @param listNumber  The delta list number
 *
 * @return the zone number containing the delta list
 **/
static INLINE unsigned int getDeltaIndexZone(const DeltaIndex *deltaIndex,
                                             unsigned int listNumber)
{
  return listNumber / deltaIndex->listsPerZone;
}

/**
 * Get the first delta list number in a zone
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return the first delta list index in the zone
 **/
unsigned int getDeltaIndexZoneFirstList(const DeltaIndex *deltaIndex,
                                        unsigned int zoneNumber);

/**
 * Get the number of delta lists in a zone
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return the number of delta lists in the zone
 **/
unsigned int getDeltaIndexZoneNumLists(const DeltaIndex *deltaIndex,
                                        unsigned int zoneNumber);

/**
 * Get the number of bytes used for master index entries in a zone
 *
 * @param deltaIndex  The delta index
 * @param zoneNumber  The zone number
 *
 * @return The number of bits in use
 **/
uint64_t getDeltaIndexZoneDlistBitsUsed(const DeltaIndex *deltaIndex,
                                        unsigned int zoneNumber)
  __attribute__((warn_unused_result));

/**
 * Get the number of bytes used for master index entries.
 *
 * @param deltaIndex  The delta index
 *
 * @return The number of bits in use
 **/
uint64_t getDeltaIndexDlistBitsUsed(const DeltaIndex *deltaIndex)
  __attribute__((warn_unused_result));

/**
 * Get the number of bytes allocated for master index entries.
 *
 * @param deltaIndex  The delta index
 *
 * @return The number of bits allocated
 **/
uint64_t getDeltaIndexDlistBitsAllocated(const DeltaIndex *deltaIndex)
  __attribute__((warn_unused_result));

/**
 * Get the delta index statistics.
 *
 * @param deltaIndex  The delta index
 * @param stats       The statistics
 **/
void getDeltaIndexStats(const DeltaIndex *deltaIndex, DeltaIndexStats *stats);

/**
 * Get the number of pages needed for an immutable delta index.
 *
 * @param numEntries      The number of entries in the index
 * @param numLists        The number of delta lists
 * @param meanDelta       The mean delta value
 * @param numPayloadBits  The number of bits in the payload or value
 * @param bytesPerPage    The number of bytes in a page
 *
 * @return the number of pages needed for the index
 **/
unsigned int getDeltaIndexPageCount(unsigned int numEntries,
                                    unsigned int numLists,
                                    unsigned int meanDelta,
                                    unsigned int numPayloadBits,
                                    size_t bytesPerPage);

/**
 * Log a delta index entry, and any error conditions related to the entry.
 *
 * @param deltaEntry  The delta index entry.
 **/
void logDeltaIndexEntry(DeltaIndexEntry *deltaEntry);

#endif /* DELTAINDEX_H */