/*

 * 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/deltaMemory.c#3 $

 */

#include "deltaMemory.h"

#include "bits.h"

#include "buffer.h"

#include "compiler.h"

#include "errors.h"

#include "hashUtils.h"

#include "logger.h"

#include "memoryAlloc.h"

#include "permassert.h"

#include "timeUtils.h"

#include "typeDefs.h"

#include "uds.h"

/*

 * The DeltaMemory structure manages the memory that stores delta lists.

 *

 * The "mutable" form of DeltaMemory is used for the master index and for

 * an open chapter index.  The "immutable" form of DeltaMemory is used for

 * regular chapter indices.

 */

// This is the number of guard bits that are needed in the tail guard list

enum { GUARD_BITS = POST_FIELD_GUARD_BYTES * CHAR_BIT };

/**

 * Get the offset of the first byte that a delta list bit stream resides in

 *

 * @param deltaList  The delta list

 *

 * @return the number byte offset

 **/

static INLINE uint64_t getDeltaListByteStart(const DeltaList *deltaList)

{

  return getDeltaListStart(deltaList) / CHAR_BIT;

}

/**

 * Get the actual number of bytes that a delta list bit stream resides in

 *

 * @param deltaList  The delta list

 *

 * @return the number of bytes

 **/

static INLINE uint16_t getDeltaListByteSize(const DeltaList *deltaList)

{

  uint16_t startBitOffset = getDeltaListStart(deltaList) % CHAR_BIT;

  uint16_t bitSize = getDeltaListSize(deltaList);

  return ((unsigned int) startBitOffset + bitSize + CHAR_BIT - 1) / CHAR_BIT;

}

/**

 * Get the number of bytes in the delta lists headers.

 *

 * @param numLists  The number of delta lists

 *

 * @return the number of bytes in the delta lists headers

 **/

static INLINE size_t getSizeOfDeltaLists(unsigned int numLists)

{

  return (numLists + 2) * sizeof(DeltaList);

}

/**

 * Get the size of the flags array (in bytes)

 *

 * @param numLists  The number of delta lists

 *

 * @return the number of bytes for an array that has one bit per delta

 *         list, plus the necessary guard bytes.

 **/

static INLINE size_t getSizeOfFlags(unsigned int numLists)

{

  return (numLists + CHAR_BIT - 1) / CHAR_BIT + POST_FIELD_GUARD_BYTES;

}

/**

 * Get the number of bytes of scratch memory for the delta lists.

 *

 * @param numLists  The number of delta lists

 *

 * @return the number of bytes of scratch memory for the delta lists

 **/

static INLINE size_t getSizeOfTempOffsets(unsigned int numLists)

{

  return (numLists + 2) * sizeof(uint64_t);

}

/**********************************************************************/

/**

 * Clear the transfers flags.

 *

 * @param deltaMemory  The delta memory

 **/

static void clearTransferFlags(DeltaMemory *deltaMemory)

{

  memset(deltaMemory->flags, 0, getSizeOfFlags(deltaMemory->numLists));

  deltaMemory->numTransfers = 0;

  deltaMemory->transferStatus = UDS_SUCCESS;

}

/**********************************************************************/

/**

 * Set the transfer flags for delta lists that are not empty, and count how

 * many there are.

 *

 * @param deltaMemory  The delta memory

 **/

static void flagNonEmptyDeltaLists(DeltaMemory *deltaMemory)

{

  clearTransferFlags(deltaMemory);

  unsigned int i;

  for (i = 0; i < deltaMemory->numLists; i++) {

    if (getDeltaListSize(&deltaMemory->deltaLists[i + 1]) > 0) {

      setOne(deltaMemory->flags, i, 1);

      deltaMemory->numTransfers++;

    }

  }

}

/**********************************************************************/

void emptyDeltaLists(DeltaMemory *deltaMemory)

{

  // Zero all the delta list headers

  DeltaList *deltaLists = deltaMemory->deltaLists;

  memset(deltaLists, 0, getSizeOfDeltaLists(deltaMemory->numLists));

  /*

   * Initialize delta lists to be empty. We keep 2 extra delta list

   * descriptors, one before the first real entry and one after so that we

   * don't need to bounds check the array access when calculating

   * preceeding and following gap sizes.

   *

   * Because the delta list headers were zeroed, the head guard list is

   * already at offset zero and size zero.

   *

   * The end guard list contains guard bytes so that the bit field

   * utilities can safely read past the end of any byte we are interested

   * in.

   */

  uint64_t numBits = (uint64_t) deltaMemory->size * CHAR_BIT;

  deltaLists[deltaMemory->numLists + 1].startOffset = numBits - GUARD_BITS;

  deltaLists[deltaMemory->numLists + 1].size        = GUARD_BITS;

  // Set all the bits in the end guard list.  Do not use the bit field

  // utilities.

  memset(deltaMemory->memory + deltaMemory->size - POST_FIELD_GUARD_BYTES,

         ~0, POST_FIELD_GUARD_BYTES);

  // Evenly space out the real delta lists.  The sizes are already zero, so

  // we just need to set the starting offsets.

  uint64_t spacing = (numBits - GUARD_BITS) / deltaMemory->numLists;

  uint64_t offset = spacing / 2;

  unsigned int i;

  for (i = 1; i <= deltaMemory->numLists; i++) {

    deltaLists[i].startOffset = offset;

    offset += spacing;

  }

  // Update the statistics

  deltaMemory->discardCount  += deltaMemory->recordCount;

  deltaMemory->recordCount    = 0;

  deltaMemory->collisionCount = 0;

}

/**********************************************************************/

/**

 * Compute the Huffman coding parameters for the given mean delta

 *

 * @param meanDelta  The mean delta value

 * @param minBits    The number of bits in the minimal key code

 * @param minKeys    The number of keys used in a minimal code

 * @param incrKeys   The number of keys used for another code bit

 **/

static void computeCodingConstants(unsigned int    meanDelta,

                                   unsigned short *minBits,

                                   unsigned int   *minKeys,

                                   unsigned int   *incrKeys)

{

  // We want to compute the rounded value of log(2) * meanDelta.  Since we

  // cannot always use floating point, use a really good integer approximation.

  *incrKeys = (836158UL * meanDelta + 603160UL) / 1206321UL;

  *minBits  = computeBits(*incrKeys + 1);

  *minKeys  = (1 << *minBits) - *incrKeys;

}

/**********************************************************************/

/**

 * Rebalance a range of delta lists within memory.

 *

 * @param deltaMemory  A delta memory structure

 * @param first        The first delta list index

 * @param last         The last delta list index

 **/

static void rebalanceDeltaMemory(const DeltaMemory *deltaMemory,

                                 unsigned int first, unsigned int last)

{

  if (first == last) {

    DeltaList *deltaList = &deltaMemory->deltaLists[first];

    uint64_t newStart = deltaMemory->tempOffsets[first];

    // We need to move only one list, and we know it is safe to do so

    if (getDeltaListStart(deltaList) != newStart) {

      // Compute the first source byte

      uint64_t source = getDeltaListByteStart(deltaList);

      // Update the delta list location

      deltaList->startOffset = newStart;

      // Now use the same computation to locate the first destination byte

      uint64_t destination = getDeltaListByteStart(deltaList);

      memmove(deltaMemory->memory + destination, deltaMemory->memory + source,

              getDeltaListByteSize(deltaList));

    }

  } else {

    // There is more than one list.  Divide the problem in half, and use

    // recursive calls to process each half.  Note that after this

    // computation, first <= middle, and middle < last.

    unsigned int middle = (first + last) / 2;

    const DeltaList *deltaList = &deltaMemory->deltaLists[middle];

    uint64_t newStart = deltaMemory->tempOffsets[middle];

    // The direction that our middle list is moving determines which half

    // of the problem must be processed first.

    if (newStart > getDeltaListStart(deltaList)) {

      rebalanceDeltaMemory(deltaMemory, middle + 1, last);

      rebalanceDeltaMemory(deltaMemory, first, middle);

    } else {

      rebalanceDeltaMemory(deltaMemory, first, middle);

      rebalanceDeltaMemory(deltaMemory, middle + 1, last);

    }

  }

}

/**********************************************************************/

int initializeDeltaMemory(DeltaMemory *deltaMemory, size_t size,

                          unsigned int firstList, unsigned int numLists,

                          unsigned int meanDelta, unsigned int numPayloadBits)

{

  if (numLists == 0) {

    return logWarningWithStringError(UDS_INVALID_ARGUMENT,

                                     "cannot initialize delta memory with 0 "

                                     "delta lists");

  }

  byte *memory = NULL;

  int result = ALLOCATE(size, byte, "delta list", &memory);

  if (result != UDS_SUCCESS) {

    return result;

  }

  uint64_t *tempOffsets = NULL;

  result = ALLOCATE(numLists + 2, uint64_t, "delta list temp",

                    &tempOffsets);

  if (result != UDS_SUCCESS) {

    FREE(memory);

    return result;

  }

  byte *flags = NULL;

  result = ALLOCATE(getSizeOfFlags(numLists), byte, "delta list flags",

                    &flags);

  if (result != UDS_SUCCESS) {

    FREE(memory);

    FREE(tempOffsets);

    return result;

  }

  computeCodingConstants(meanDelta, &deltaMemory->minBits,

                         &deltaMemory->minKeys, &deltaMemory->incrKeys);

  deltaMemory->valueBits       = numPayloadBits;

  deltaMemory->memory          = memory;

  deltaMemory->deltaLists      = NULL;

  deltaMemory->tempOffsets     = tempOffsets;

  deltaMemory->flags           = flags;

  deltaMemory->bufferedWriter  = NULL;

  deltaMemory->size            = size;

  deltaMemory->rebalanceTime   = 0;

  deltaMemory->rebalanceCount  = 0;

  deltaMemory->recordCount     = 0;

  deltaMemory->collisionCount  = 0;

  deltaMemory->discardCount    = 0;

  deltaMemory->overflowCount   = 0;

  deltaMemory->firstList       = firstList;

  deltaMemory->numLists        = numLists;

  deltaMemory->numTransfers    = 0;

  deltaMemory->transferStatus  = UDS_SUCCESS;

  deltaMemory->tag             = 'm';

  // Allocate the delta lists.

  result = ALLOCATE(deltaMemory->numLists + 2, DeltaList,

                    "delta lists", &deltaMemory->deltaLists);

  if (result != UDS_SUCCESS) {

    uninitializeDeltaMemory(deltaMemory);

    return result;

  }

  emptyDeltaLists(deltaMemory);

  return UDS_SUCCESS;

}

/**********************************************************************/

void uninitializeDeltaMemory(DeltaMemory *deltaMemory)

{

  FREE(deltaMemory->flags);

  deltaMemory->flags = NULL;

  FREE(deltaMemory->tempOffsets);

  deltaMemory->tempOffsets = NULL;

  FREE(deltaMemory->deltaLists);

  deltaMemory->deltaLists = NULL;

  FREE(deltaMemory->memory);

  deltaMemory->memory = NULL;

}

/**********************************************************************/

void initializeDeltaMemoryPage(DeltaMemory *deltaMemory, byte *memory,

                               size_t size, unsigned int numLists,

                               unsigned int meanDelta,

                               unsigned int numPayloadBits)

{

  computeCodingConstants(meanDelta, &deltaMemory->minBits,

                         &deltaMemory->minKeys, &deltaMemory->incrKeys);

  deltaMemory->valueBits       = numPayloadBits;

  deltaMemory->memory          = memory;

  deltaMemory->deltaLists      = NULL;

  deltaMemory->tempOffsets     = NULL;

  deltaMemory->flags           = NULL;

  deltaMemory->bufferedWriter  = NULL;

  deltaMemory->size            = size;

  deltaMemory->rebalanceTime   = 0;

  deltaMemory->rebalanceCount  = 0;

  deltaMemory->recordCount     = 0;

  deltaMemory->collisionCount  = 0;

  deltaMemory->discardCount    = 0;

  deltaMemory->overflowCount   = 0;

  deltaMemory->firstList       = 0;

  deltaMemory->numLists        = numLists;

  deltaMemory->numTransfers    = 0;

  deltaMemory->transferStatus  = UDS_SUCCESS;

  deltaMemory->tag             = 'p';

}

/**********************************************************************/

bool areDeltaMemoryTransfersDone(const DeltaMemory *deltaMemory)

{

  return deltaMemory->numTransfers == 0;

}

/**********************************************************************/

int startRestoringDeltaMemory(DeltaMemory *deltaMemory)

{

  // Extend and balance memory to receive the delta lists

  int result = extendDeltaMemory(deltaMemory, 0, 0, false);

  if (result != UDS_SUCCESS) {

    return UDS_SUCCESS;

  }

  // The tail guard list needs to be set to ones

  DeltaList *deltaList = &deltaMemory->deltaLists[deltaMemory->numLists + 1];

  setOne(deltaMemory->memory, getDeltaListStart(deltaList),

         getDeltaListSize(deltaList));

  flagNonEmptyDeltaLists(deltaMemory);

  return UDS_SUCCESS;

}

/**********************************************************************/

__attribute__((warn_unused_result))

static int readDeltaListSaveInfo(BufferedReader *reader,

                                 DeltaListSaveInfo *dlsi)

{

  byte buffer[sizeof(DeltaListSaveInfo)];

  int result = readFromBufferedReader(reader, buffer, sizeof(buffer));

  if (result != UDS_SUCCESS) {

    return result;

  }

  dlsi->tag =  buffer[0];

  dlsi->bitOffset = buffer[1];

  dlsi->byteCount = getUInt16LE(&buffer[2]);

  dlsi->index = getUInt32LE(&buffer[4]);

  return result;

}

/**********************************************************************/

int readSavedDeltaList(DeltaListSaveInfo *dlsi,

                       byte data[DELTA_LIST_MAX_BYTE_COUNT],

                       BufferedReader *bufferedReader)

{

  int result = readDeltaListSaveInfo(bufferedReader, dlsi);

  if (result == UDS_END_OF_FILE) {

    return UDS_END_OF_FILE;

  }

  if (result != UDS_SUCCESS) {

    return logWarningWithStringError(result, "failed to read delta list data");

  }

  if ((dlsi->bitOffset >= CHAR_BIT)

      || (dlsi->byteCount > DELTA_LIST_MAX_BYTE_COUNT)) {

    return logWarningWithStringError(UDS_CORRUPT_COMPONENT,

                                     "corrupt delta list data");

  }

  if (dlsi->tag == 'z') {

    return UDS_END_OF_FILE;

  }

  result = readFromBufferedReader(bufferedReader, data, dlsi->byteCount);

  if (result != UDS_SUCCESS) {

    return logWarningWithStringError(result, "failed to read delta list data");

  }

  return UDS_SUCCESS;

}

/**********************************************************************/

int restoreDeltaList(DeltaMemory *deltaMemory, const DeltaListSaveInfo *dlsi,

                     const byte data[DELTA_LIST_MAX_BYTE_COUNT])

{

  unsigned int listNumber = dlsi->index - deltaMemory->firstList;

  if (listNumber >= deltaMemory->numLists) {

    return logWarningWithStringError(UDS_CORRUPT_COMPONENT,

                                     "invalid delta list number %u not in"

                                     " range [%u,%u)",

                                     dlsi->index, deltaMemory->firstList,

                                     deltaMemory->firstList

                                     + deltaMemory->numLists);

  }

  if (getField(deltaMemory->flags, listNumber, 1) == 0) {

    return logWarningWithStringError(UDS_CORRUPT_COMPONENT,

                                     "unexpected delta list number %u",

                                     dlsi->index);

  }

  DeltaList *deltaList = &deltaMemory->deltaLists[listNumber + 1];

  uint16_t bitSize = getDeltaListSize(deltaList);

  unsigned int byteCount

    = ((unsigned int) dlsi->bitOffset + bitSize + CHAR_BIT - 1) / CHAR_BIT;

  if (dlsi->byteCount != byteCount) {

    return logWarningWithStringError(UDS_CORRUPT_COMPONENT,

                                     "unexpected delta list size %u != %u",

                                     dlsi->byteCount, byteCount);

  }

  moveBits(data, dlsi->bitOffset, deltaMemory->memory,

           getDeltaListStart(deltaList), bitSize);

  setZero(deltaMemory->flags, listNumber, 1);

  deltaMemory->numTransfers--;

  return UDS_SUCCESS;

}

/**********************************************************************/

void abortRestoringDeltaMemory(DeltaMemory *deltaMemory)

{

  clearTransferFlags(deltaMemory);

  emptyDeltaLists(deltaMemory);

}

/**********************************************************************/

void startSavingDeltaMemory(DeltaMemory *deltaMemory,

                            BufferedWriter *bufferedWriter)

{

  flagNonEmptyDeltaLists(deltaMemory);

  deltaMemory->bufferedWriter = bufferedWriter;

}

/**********************************************************************/

int finishSavingDeltaMemory(DeltaMemory *deltaMemory)

{

  unsigned int i;

  for (i = 0;

       !areDeltaMemoryTransfersDone(deltaMemory)

         && (i < deltaMemory->numLists);

       i++) {

    lazyFlushDeltaList(deltaMemory, i);

  }

  if (deltaMemory->numTransfers > 0) {

    deltaMemory->transferStatus

      = logWarningWithStringError(UDS_CORRUPT_DATA,

                                  "Not all delta lists written");

  }

  deltaMemory->bufferedWriter = NULL;

  return deltaMemory->transferStatus;

}

/**********************************************************************/

void abortSavingDeltaMemory(DeltaMemory *deltaMemory)

{

  clearTransferFlags(deltaMemory);

  deltaMemory->bufferedWriter = NULL;

}

/**********************************************************************/

__attribute__((warn_unused_result))

static int writeDeltaListSaveInfo(BufferedWriter *bufferedWriter,

                                  DeltaListSaveInfo *dlsi)

{

  byte buffer[sizeof(DeltaListSaveInfo)];

  buffer[0] = dlsi->tag;

  buffer[1] = dlsi->bitOffset;

  storeUInt16LE(&buffer[2], dlsi->byteCount);

  storeUInt32LE(&buffer[4], dlsi->index);

  return writeToBufferedWriter(bufferedWriter, buffer, sizeof(buffer));

}

/**********************************************************************/

void flushDeltaList(DeltaMemory *deltaMemory, unsigned int flushIndex)

{

  ASSERT_LOG_ONLY((getField(deltaMemory->flags, flushIndex, 1) != 0),

                  "flush bit is set");

  setZero(deltaMemory->flags, flushIndex, 1);

  deltaMemory->numTransfers--;

  DeltaList *deltaList = &deltaMemory->deltaLists[flushIndex + 1];

  DeltaListSaveInfo dlsi;

  dlsi.tag       = deltaMemory->tag;

  dlsi.bitOffset = getDeltaListStart(deltaList) % CHAR_BIT;

  dlsi.byteCount = getDeltaListByteSize(deltaList);

  dlsi.index     = deltaMemory->firstList + flushIndex;

  int result = writeDeltaListSaveInfo(deltaMemory->bufferedWriter, &dlsi);

  if (result != UDS_SUCCESS) {

    if (deltaMemory->transferStatus == UDS_SUCCESS) {

      logWarningWithStringError(result, "failed to write delta list memory");

      deltaMemory->transferStatus = result;

    }

  }

  result = writeToBufferedWriter(deltaMemory->bufferedWriter,

                                 deltaMemory->memory

                                 + getDeltaListByteStart(deltaList),

                                 dlsi.byteCount);

  if (result != UDS_SUCCESS) {

    if (deltaMemory->transferStatus == UDS_SUCCESS) {

      logWarningWithStringError(result, "failed to write delta list memory");

      deltaMemory->transferStatus = result;

    }

  }

}

/**********************************************************************/

int writeGuardDeltaList(BufferedWriter *bufferedWriter)

{

  DeltaListSaveInfo dlsi;

  dlsi.tag       = 'z';

  dlsi.bitOffset = 0;

  dlsi.byteCount = 0;

  dlsi.index     = 0;

  int result = writeToBufferedWriter(bufferedWriter, (const byte *) &dlsi,

                                     sizeof(DeltaListSaveInfo));

  if (result != UDS_SUCCESS) {

    logWarningWithStringError(result, "failed to write guard delta list");

  }

  return result;

}

/**********************************************************************/

int extendDeltaMemory(DeltaMemory *deltaMemory, unsigned int growingIndex,

                      size_t growingSize, bool doCopy)

{

  if (!isMutable(deltaMemory)) {

    return logErrorWithStringError(UDS_BAD_STATE,

                                   "Attempt to read into an immutable delta"

                                   " list memory");

  }

  AbsTime startTime = currentTime(CLOCK_MONOTONIC);

  // Calculate the amount of space that is in use.  Include the space that

  // has a planned use.

  DeltaList *deltaLists = deltaMemory->deltaLists;

  size_t usedSpace = growingSize;

  unsigned int i;

  for (i = 0; i <= deltaMemory->numLists + 1; i++) {

    usedSpace += getDeltaListByteSize(&deltaLists[i]);

  }

  if (deltaMemory->size < usedSpace) {

    return UDS_OVERFLOW;

  }

  // Compute the new offsets of the delta lists

  size_t spacing = (deltaMemory->size - usedSpace) / deltaMemory->numLists;

  deltaMemory->tempOffsets[0] = 0;

  for (i = 0; i <= deltaMemory->numLists; i++) {

    deltaMemory->tempOffsets[i + 1] = (deltaMemory->tempOffsets[i]

                                       + getDeltaListByteSize(&deltaLists[i])

                                       + spacing);

    deltaMemory->tempOffsets[i] *= CHAR_BIT;

    deltaMemory->tempOffsets[i]

      += getDeltaListStart(&deltaLists[i]) % CHAR_BIT;

    if (i == 0) {

      deltaMemory->tempOffsets[i + 1] -= spacing / 2;

    }

    if (i + 1 == growingIndex) {

      deltaMemory->tempOffsets[i + 1] += growingSize;

    }

  }

  deltaMemory->tempOffsets[deltaMemory->numLists + 1]

    = (deltaMemory->size * CHAR_BIT

       - getDeltaListSize(&deltaLists[deltaMemory->numLists + 1]));

  // When we rebalance the delta list, we will include the end guard list

  // in the rebalancing.  It contains the end guard data, which must be

  // copied.

  if (doCopy) {

    rebalanceDeltaMemory(deltaMemory, 1, deltaMemory->numLists + 1);

    AbsTime endTime = currentTime(CLOCK_MONOTONIC);

    deltaMemory->rebalanceCount++;

    deltaMemory->rebalanceTime += timeDifference(endTime, startTime);

  } else {

    for (i = 1; i <= deltaMemory->numLists + 1; i++) {

      deltaLists[i].startOffset = deltaMemory->tempOffsets[i];

    }

  }

  return UDS_SUCCESS;

}

/**********************************************************************/

int validateDeltaLists(const DeltaMemory *deltaMemory)

{

  // Validate the delta index fields set by restoring a delta index

  if (deltaMemory->collisionCount > deltaMemory->recordCount) {

    return logWarningWithStringError(UDS_BAD_STATE,

                                     "delta index contains more collisions"

                                     " (%ld) than records (%ld)",

                                     deltaMemory->collisionCount,

                                     deltaMemory->recordCount);

  }

  // Validate the delta lists

  DeltaList *deltaLists = deltaMemory->deltaLists;

  if (getDeltaListStart(&deltaLists[0]) != 0) {

    return logWarningWithStringError(UDS_BAD_STATE,

                                     "the head guard delta list does not start"

                                     " at 0: %llu",

                                     getDeltaListStart(&deltaLists[0]));

  }

  uint64_t numBits = getDeltaListEnd(&deltaLists[deltaMemory->numLists + 1]);

  if (numBits != deltaMemory->size * CHAR_BIT) {

    return logWarningWithStringError(UDS_BAD_STATE,

                                     "the tail guard delta list does not end "

                                     "at end of allocated memory:  %" PRIu64

                                     " != %zd",

                                     numBits, deltaMemory->size * CHAR_BIT);

  }

  int numGuardBits = getDeltaListSize(&deltaLists[deltaMemory->numLists + 1]);

  if (numGuardBits < GUARD_BITS) {

    return logWarningWithStringError(UDS_BAD_STATE,

                                     "the tail guard delta list does not "

                                     "contain sufficient guard bits:  %d < %d",

                                     numGuardBits, GUARD_BITS);

  }

  unsigned int i;

  for (i = 0; i <= deltaMemory->numLists + 1; i++) {

    if (getDeltaListStart(&deltaLists[i]) > getDeltaListEnd(&deltaLists[i])) {

      return logWarningWithStringError(UDS_BAD_STATE,

                                       "invalid delta list %u: [%" PRIu64

                                       ", %llu)",

                                       i,

                                       getDeltaListStart(&deltaLists[i]),

                                       getDeltaListEnd(&deltaLists[i]));

    }

    if (i > deltaMemory->numLists) {

      // The rest of the checks do not apply to the tail guard list

      continue;

    }

    if (getDeltaListEnd(&deltaLists[i])

        > getDeltaListStart(&deltaLists[i + 1])) {

      return logWarningWithStringError(UDS_BAD_STATE,

                                       "delta lists %u and %u overlap:  %"

                                       PRIu64 " > %llu",

                                       i, i + 1,

                                       getDeltaListEnd(&deltaLists[i]),

                                       getDeltaListStart(&deltaLists[i + 1]));

    }

    if (i == 0) {

      // The rest of the checks do not apply to the head guard list

      continue;

    }

    if (deltaLists[i].saveOffset > getDeltaListSize(&deltaLists[i])) {

      return logWarningWithStringError(UDS_BAD_STATE,

                                       "delta lists %u saved offset is larger"

                                       " than the list:  %u > %u",

                                       i, deltaLists[i].saveOffset,

                                       getDeltaListSize(&deltaLists[i]));

    }

  }

  return UDS_SUCCESS;

}

/**********************************************************************/

size_t getDeltaMemoryAllocated(const DeltaMemory *deltaMemory)

{

  return (deltaMemory->size

          + getSizeOfDeltaLists(deltaMemory->numLists)

          + getSizeOfFlags(deltaMemory->numLists)

          + getSizeOfTempOffsets(deltaMemory->numLists));

}

/**********************************************************************/

size_t getDeltaMemorySize(unsigned long numEntries, unsigned int meanDelta,

                          unsigned int numPayloadBits)

{

  unsigned short minBits;

  unsigned int incrKeys, minKeys;

  computeCodingConstants(meanDelta, &minBits, &minKeys, &incrKeys);

  // On average, each delta is encoded into about minBits+1.5 bits.

  return (numEntries * (numPayloadBits + minBits + 1) + numEntries / 2);

}