/*

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

 */

#include "searchList.h"

#include "errors.h"

#include "logger.h"

#include "memoryAlloc.h"

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

int makeSearchList(unsigned int   capacity,

                   SearchList   **listPtr)

{

  if (capacity == 0) {

    return logErrorWithStringError(UDS_INVALID_ARGUMENT,

                                   "search list must have entries");

  }

  if (capacity > UINT8_MAX) {

    return logErrorWithStringError(UDS_INVALID_ARGUMENT,

                                  "search list capacity must fit in 8 bits");

  }

  // We need three temporary entry arrays for purgeSearchList(). Allocate them

  // contiguously with the main array.

  unsigned int bytes = (sizeof(SearchList) + (4 * capacity * sizeof(uint8_t)));

  SearchList *list;

  int result = allocateCacheAligned(bytes, "search list", &list);

  if (result != UDS_SUCCESS) {

    return result;

  }

  list->capacity       = capacity;

  list->firstDeadEntry = 0;

  // Fill in the indexes of the chapter index cache entries. These will be

  // only ever be permuted as the search list is used.

  uint8_t i;

  for (i = 0; i < capacity; i++) {

    list->entries[i] = i;

  }

  *listPtr = list;

  return UDS_SUCCESS;

}

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

void freeSearchList(SearchList **listPtr)

{

  FREE(*listPtr);

  *listPtr = NULL;

}

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

void purgeSearchList(SearchList               *searchList,

                     const CachedChapterIndex  chapters[],

                     uint64_t                  oldestVirtualChapter)

{

  if (searchList->firstDeadEntry == 0) {

    // There are no live entries in the list to purge.

    return;

  }

  /*

   * Partition the previously-alive entries in the list into three temporary

   * lists, keeping the current LRU search order within each list. The element

   * array was allocated with enough space for all four lists.

   */

  uint8_t *entries = &searchList->entries[0];

  uint8_t *alive   = &entries[searchList->capacity];

  uint8_t *skipped = &alive[searchList->capacity];

  uint8_t *dead    = &skipped[searchList->capacity];

  unsigned int nextAlive   = 0;

  unsigned int nextSkipped = 0;

  unsigned int nextDead    = 0;

  int i;

  for (i = 0; i < searchList->firstDeadEntry; i++) {

    uint8_t entry = entries[i];

    const CachedChapterIndex *chapter = &chapters[entry];

    if ((chapter->virtualChapter < oldestVirtualChapter)

        || (chapter->virtualChapter == UINT64_MAX)) {

      dead[nextDead++] = entry;

    } else if (chapter->skipSearch) {

      skipped[nextSkipped++] = entry;

    } else {

      alive[nextAlive++] = entry;

    }

  }

  // Copy the temporary lists back to the search list so we wind up with

  // [ alive, alive, skippable, new-dead, new-dead, old-dead, old-dead ]

  memcpy(entries, alive, nextAlive);

  entries += nextAlive;

  memcpy(entries, skipped, nextSkipped);

  entries += nextSkipped;

  memcpy(entries, dead, nextDead);

  // The first dead entry is now the start of the copied dead list.

  searchList->firstDeadEntry = (nextAlive + nextSkipped);

}