/*
* 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);
}