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