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