/*

 * 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/openChapterZone.c#2 $

 */

#include "openChapterZone.h"

#include "compiler.h"

#include "hashUtils.h"

#include "logger.h"

#include "memoryAlloc.h"

#include "permassert.h"

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

static INLINE size_t recordsSize(const OpenChapterZone *openChapter)

{

  return (sizeof(UdsChunkRecord) * (1 + openChapter->capacity));

}

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

static INLINE size_t slotsSize(size_t slotCount)

{

  return (sizeof(Slot) * slotCount);

}

/**

 * Round up to the first power of two greater than or equal

 * to the supplied number.

 *

 * @param val  the number to round up

 *

 * @return the first power of two not smaller than val for any

 *         val <= 2^63

 **/

static INLINE size_t nextPowerOfTwo(size_t val)

{

  if (val == 0) {

    return 1;

  }

  return (1 << computeBits(val - 1));

}

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

int makeOpenChapter(const Geometry   *geometry,

                    unsigned int      zoneCount,

                    OpenChapterZone **openChapterPtr)

{

  int result = ASSERT(zoneCount > 0, "zone count must be > 0");

  if (result != UDS_SUCCESS) {

    return result;

  }

  result = ASSERT_WITH_ERROR_CODE(geometry->openChapterLoadRatio > 1,

                                  UDS_BAD_STATE,

                                  "Open chapter hash table is too small");

  if (result != UDS_SUCCESS) {

    return result;

  }

  result = ASSERT_WITH_ERROR_CODE((geometry->recordsPerChapter

                                   <= OPEN_CHAPTER_MAX_RECORD_NUMBER),

                                  UDS_BAD_STATE,

                                  "Too many records (%u) for a single chapter",

                                  geometry->recordsPerChapter);

  if (result != UDS_SUCCESS) {

    return result;

  }

  if (geometry->recordsPerChapter < zoneCount) {

    return logUnrecoverable(

      UDS_INVALID_ARGUMENT,

      "zone count: %u is larger than the records per chapter %u",

      zoneCount, geometry->recordsPerChapter);

  }

  size_t capacity = geometry->recordsPerChapter / zoneCount;

  // The slot count must be at least one greater than the capacity.

  // Using a power of two slot count guarantees that hash insertion

  // will never fail if the hash table is not full.

  size_t slotCount = nextPowerOfTwo(capacity * geometry->openChapterLoadRatio);

  OpenChapterZone *openChapter;

  result = ALLOCATE_EXTENDED(OpenChapterZone, slotCount, Slot,

                             "open chapter", &openChapter);

  if (result != UDS_SUCCESS) {

    return result;

  }

  openChapter->slotCount = slotCount;

  openChapter->capacity = capacity;

  result = allocateCacheAligned(recordsSize(openChapter), "record pages",

                                &openChapter->records);

  if (result != UDS_SUCCESS) {

    freeOpenChapter(openChapter);

    return result;

  }

  *openChapterPtr = openChapter;

  return UDS_SUCCESS;

}

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

size_t openChapterSize(const OpenChapterZone *openChapter)

{

  return openChapter->size - openChapter->deleted;

}

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

void resetOpenChapter(OpenChapterZone *openChapter)

{

  openChapter->size    = 0;

  openChapter->deleted = 0;

  memset(openChapter->records, 0, recordsSize(openChapter));

  memset(openChapter->slots,   0, slotsSize(openChapter->slotCount));

}

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

static UdsChunkRecord *probeChapterSlots(OpenChapterZone    *openChapter,

                                         const UdsChunkName *name,

                                         unsigned int       *slotPtr,

                                         unsigned int       *recordNumberPtr)

{

  unsigned int slots     = openChapter->slotCount;

  unsigned int probe     = nameToHashSlot(name, slots);

  unsigned int firstSlot = 0;

  UdsChunkRecord *record;

  unsigned int probeSlot;

  unsigned int recordNumber;

  unsigned int probeAttempts;

  for (probeAttempts = 1; ; ++probeAttempts) {

    probeSlot = firstSlot + probe;

    recordNumber = openChapter->slots[probeSlot].recordNumber;

    // If the hash slot is empty, we've reached the end of a chain without

    // finding the record and should terminate the search.

    if (recordNumber == 0) {

      record = NULL;

      break;

    }

    // If the name of the record referenced by the slot matches and has not

    // been deleted, then we've found the requested name.

    record = &openChapter->records[recordNumber];

    if ((memcmp(&record->name, name, UDS_CHUNK_NAME_SIZE) == 0)

        && !openChapter->slots[recordNumber].recordDeleted) {

      break;

    }

    // Quadratic probing: advance the probe by 1, 2, 3, etc. and try again.

    // This performs better than linear probing and works best for 2^N slots.

    probe += probeAttempts;

    if (probe >= slots) {

      probe = probe % slots;

    }

  }

  // These NULL checks will be optimized away in callers who don't care about

  // the values when this function is inlined.

  if (slotPtr != NULL) {

    *slotPtr = probeSlot;

  }

  if (recordNumberPtr != NULL) {

    *recordNumberPtr = recordNumber;

  }

  return record;

}

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

void searchOpenChapter(OpenChapterZone     *openChapter,

                       const UdsChunkName  *name,

                       UdsChunkData        *metadata,

                       bool                *found)

{

  UdsChunkRecord *record = probeChapterSlots(openChapter, name, NULL, NULL);

  if (record == NULL) {

    *found = false;

  } else {

    *found = true;

    if (metadata != NULL) {

      *metadata = record->data;

    }

  }

}

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

int putOpenChapter(OpenChapterZone    *openChapter,

                   const UdsChunkName *name,

                   const UdsChunkData *metadata,

                   unsigned int       *remaining)

{

  unsigned int slot;

  UdsChunkRecord *record = probeChapterSlots(openChapter, name, &slot, NULL);

  if (record != NULL) {

    record->data = *metadata;

    *remaining = openChapter->capacity - openChapter->size;

    return UDS_SUCCESS;

  }

  if (openChapter->size >= openChapter->capacity) {

    return makeUnrecoverable(UDS_VOLUME_OVERFLOW);

  }

  unsigned int recordNumber = ++openChapter->size;

  openChapter->slots[slot].recordNumber = recordNumber;

  record                                = &openChapter->records[recordNumber];

  record->name                          = *name;

  record->data                          = *metadata;

  *remaining = openChapter->capacity - openChapter->size;

  return UDS_SUCCESS;

}

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

void removeFromOpenChapter(OpenChapterZone    *openChapter,

                           const UdsChunkName *name,

                           bool               *removed)

{

  unsigned int recordNumber;

  UdsChunkRecord *record

    = probeChapterSlots(openChapter, name, NULL, &recordNumber);

  if (record == NULL) {

    *removed = false;

    return;

  }

  // Set the deleted flag on the recordNumber in the slot array so search

  // won't find it and close won't index it.

  openChapter->slots[recordNumber].recordDeleted = true;

  openChapter->deleted += 1;

  *removed = true;

}

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

void freeOpenChapter(OpenChapterZone *openChapter)

{

  if (openChapter != NULL) {

    FREE(openChapter->records);

    FREE(openChapter);

  }

}