/*
* 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/recordPage.c#3 $
*/
#include "recordPage.h"
#include "permassert.h"
/**********************************************************************/
static unsigned int encodeTree(byte recordPage[],
const UdsChunkRecord *sortedPointers[],
unsigned int nextRecord,
unsigned int node,
unsigned int nodeCount)
{
if (node < nodeCount) {
unsigned int child = (2 * node) + 1;
nextRecord = encodeTree(recordPage, sortedPointers, nextRecord,
child, nodeCount);
// In-order traversal: copy the contents of the next record
// into the page at the node offset.
memcpy(&recordPage[node * BYTES_PER_RECORD],
sortedPointers[nextRecord],
BYTES_PER_RECORD);
++nextRecord;
nextRecord = encodeTree(recordPage, sortedPointers, nextRecord,
child + 1, nodeCount);
}
return nextRecord;
}
/**********************************************************************/
int encodeRecordPage(const Volume *volume,
const UdsChunkRecord records[],
byte recordPage[])
{
unsigned int recordsPerPage = volume->geometry->recordsPerPage;
const UdsChunkRecord **recordPointers = volume->recordPointers;
// Build an array of record pointers. We'll sort the pointers by the block
// names in the records, which is less work than sorting the record values.
unsigned int i;
for (i = 0; i < recordsPerPage; i++) {
recordPointers[i] = &records[i];
}
STATIC_ASSERT(offsetof(UdsChunkRecord, name) == 0);
int result = radixSort(volume->radixSorter, (const byte **) recordPointers,
recordsPerPage, UDS_CHUNK_NAME_SIZE);
if (result != UDS_SUCCESS) {
return result;
}
// Use the sorted pointers to copy the records from the chapter to the
// record page in tree order.
encodeTree(recordPage, recordPointers, 0, 0, recordsPerPage);
return UDS_SUCCESS;
}
/**********************************************************************/
bool searchRecordPage(const byte recordPage[],
const UdsChunkName *name,
const Geometry *geometry,
UdsChunkData *metadata)
{
// The record page is just an array of chunk records.
const UdsChunkRecord *records = (const UdsChunkRecord *) recordPage;
// The array of records is sorted by name and stored as a binary tree in
// heap order, so the root of the tree is the first array element.
unsigned int node = 0;
while (node < geometry->recordsPerPage) {
const UdsChunkRecord *record = &records[node];
int result = memcmp(name, &record->name, UDS_CHUNK_NAME_SIZE);
if (result == 0) {
if (metadata != NULL) {
*metadata = record->data;
}
return true;
}
// The children of node N are in the heap at indexes 2N+1 and 2N+2.
node = ((2 * node) + ((result < 0) ? 1 : 2));
}
return false;
}