/*

 * 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.h#1 $

 */

#ifndef SEARCH_LIST_H

#define SEARCH_LIST_H

#include "cachedChapterIndex.h"

#include "compiler.h"

#include "stringUtils.h"

#include "typeDefs.h"

/**

 * A SearchList represents the permutations of the sparse chapter index cache

 * entry array. Those permutations express an ordering on the chapter indexes,

 * from most recently accessed to least recently accessed, which is the order

 * in which the indexes should be searched and the reverse order in which they

 * should be evicted from the cache (LRU cache replacement policy).

 *

 * Cache entries that are dead (virtualChapter == UINT64_MAX) are kept as a

 * suffix of the list, avoiding the need to even iterate over them to search,

 * and ensuring that dead entries are replaced before any live entries are

 * evicted.

 *

 * The search list is intended to be instantated for each zone thread,

 * avoiding any need for synchronization. The structure is allocated on a

 * cache boundary to avoid false sharing of memory cache lines between zone

 * threads.

 **/

typedef struct searchList {

  /** The number of cached chapter indexes and search list entries */

  uint8_t capacity;

  /** The index in the entries array of the first dead cache entry */

  uint8_t firstDeadEntry;

  /** The chapter array indexes representing the chapter search order */

  uint8_t entries[];

} SearchList;

/**

 * SearchListIterator captures the fields needed to iterate over the live

 * entries in a search list and return the CachedChapterIndex pointers that

 * the search code actually wants to deal with.

 **/

typedef struct {

  /** The search list defining the chapter search iteration order */

  SearchList         *list;

  /** The index of the next entry to return from the search list */

  unsigned int        nextEntry;

  /** The cached chapters that are referenced by the search list */

  CachedChapterIndex *chapters;

} SearchListIterator;

/**

 * Allocate and initialize a new chapter cache search list with the same

 * capacity as the cache. The index of each entry in the cache will appear

 * exactly once in the array. All the chapters in the cache are assumed to be

 * initially dead, so firstDeadEntry will be zero and no chapters will be

 * returned when the search list is iterated.

 *

 * @param [in]  capacity  the number of entries in the search list

 * @param [out] listPtr   a pointer in which to return the new search list

 **/

int makeSearchList(unsigned int   capacity,

                   SearchList   **listPtr)

  __attribute__((warn_unused_result));

/**

 * Free a search list and null out the reference to it.

 *

 * @param listPtr the reference to the search list to free

 **/

void freeSearchList(SearchList **listPtr);

/**

 * Copy the contents of one search list to another.

 *

 * @param source  the list to copy

 * @param target  the list to replace

 **/

static INLINE void copySearchList(const SearchList *source,

                                  SearchList       *target)

{

  *target = *source;

  memcpy(target->entries, source->entries, source->capacity);

}

/**

 * Prepare to iterate over the live cache entries a search list.

 *

 * @param list      the list defining the live chapters and the search order

 * @param chapters  the chapter index entries to return from getNextChapter()

 *

 * @return an iterator positioned at the start of the search list

 **/

static INLINE SearchListIterator

iterateSearchList(SearchList *list, CachedChapterIndex chapters[])

{

  SearchListIterator iterator = {

    .list      = list,

    .nextEntry = 0,

    .chapters  = chapters,

  };

  return iterator;

}

/**

 * Check if the search list iterator has another entry to return.

 *

 * @param iterator  the search list iterator

 *

 * @return true if getNextChapter() may be called

 **/

static INLINE bool hasNextChapter(const SearchListIterator *iterator)

{

  return (iterator->nextEntry < iterator->list->firstDeadEntry);

}

/**

 * Return a pointer to the next live chapter in the search list iteration and

 * advance the iterator. This must only be called when hasNextChapter()

 * returns true.

 *

 * @param iterator  the search list iterator

 *

 * @return a pointer to the next live chapter index in the search list order

 **/

static INLINE CachedChapterIndex *getNextChapter(SearchListIterator *iterator)

{

  return &iterator->chapters[iterator->list->entries[iterator->nextEntry++]];

}

/**

 * Rotate the pointers in a prefix of a search list downwards by one item,

 * pushing elements deeper into the list and moving a new chapter to the start

 * of the search list. This is the "make most recent" operation on the search

 * list.

 *

 * If the search list provided is [ 0 1 2 3 4 ] and the prefix

 * length is 4, then 3 is being moved to the front.

 * The search list after the call will be [ 3 0 1 2 4 ] and the

 * function will return 3.

 *

 * @param searchList    the chapter index search list to rotate

 * @param prefixLength  the length of the prefix of the list to rotate

 *

 * @return the array index of the chapter cache entry that is now at the front

 *         of the search list

 **/

static INLINE uint8_t rotateSearchList(SearchList *searchList,

                                       uint8_t     prefixLength)

{

  // Grab the value of the last entry in the list prefix.

  uint8_t mostRecent = searchList->entries[prefixLength - 1];

  if (prefixLength > 1) {

    // Push the first N-1 entries down by one entry, overwriting the entry

    // we just grabbed.

    memmove(&searchList->entries[1],

            &searchList->entries[0],

            prefixLength - 1);

    // We now have a hole at the front of the list in which we can place the

    // rotated entry.

    searchList->entries[0] = mostRecent;

  }

  // This function is also used to move a dead chapter to the front of the

  // list, in which case the suffix of dead chapters was pushed down too.

  if (searchList->firstDeadEntry < prefixLength) {

    searchList->firstDeadEntry += 1;

  }

  return mostRecent;

}

/**

 * Purge invalid cache entries, marking them as dead and moving them to the

 * end of the search list, then push any chapters that have skipSearch set

 * down so they follow all the remaining live, valid chapters in the search

 * list. This effectively sorts the search list into three regions--active,

 * skippable, and dead--while maintaining the LRU ordering that already

 * existed (a stable sort).

 *

 * This operation must only be called during the critical section in

 * updateSparseCache() since it effectively changes cache membership.

 *

 * @param searchList            the chapter index search list to purge

 * @param chapters              the chapter index cache entries

 * @param oldestVirtualChapter  the oldest virtual chapter

 **/

void purgeSearchList(SearchList               *searchList,

                     const CachedChapterIndex  chapters[],

                     uint64_t                  oldestVirtualChapter);

#endif /* SEARCH_LIST_H */