|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
310c69 |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
310c69 |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
310c69 |
* of the License, or (at your option) any later version.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
310c69 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
310c69 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
310c69 |
* GNU General Public License for more details.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
310c69 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
310c69 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
310c69 |
* 02110-1301, USA.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* $Id: //eng/uds-releases/jasper/src/uds/recordPage.c#3 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "recordPage.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "permassert.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
static unsigned int encodeTree(byte recordPage[],
|
|
Packit Service |
310c69 |
const UdsChunkRecord *sortedPointers[],
|
|
Packit Service |
310c69 |
unsigned int nextRecord,
|
|
Packit Service |
310c69 |
unsigned int node,
|
|
Packit Service |
310c69 |
unsigned int nodeCount)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (node < nodeCount) {
|
|
Packit Service |
310c69 |
unsigned int child = (2 * node) + 1;
|
|
Packit Service |
310c69 |
nextRecord = encodeTree(recordPage, sortedPointers, nextRecord,
|
|
Packit Service |
310c69 |
child, nodeCount);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// In-order traversal: copy the contents of the next record
|
|
Packit Service |
310c69 |
// into the page at the node offset.
|
|
Packit Service |
310c69 |
memcpy(&recordPage[node * BYTES_PER_RECORD],
|
|
Packit Service |
310c69 |
sortedPointers[nextRecord],
|
|
Packit Service |
310c69 |
BYTES_PER_RECORD);
|
|
Packit Service |
310c69 |
++nextRecord;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
nextRecord = encodeTree(recordPage, sortedPointers, nextRecord,
|
|
Packit Service |
310c69 |
child + 1, nodeCount);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return nextRecord;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
int encodeRecordPage(const Volume *volume,
|
|
Packit Service |
310c69 |
const UdsChunkRecord records[],
|
|
Packit Service |
310c69 |
byte recordPage[])
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
unsigned int recordsPerPage = volume->geometry->recordsPerPage;
|
|
Packit Service |
310c69 |
const UdsChunkRecord **recordPointers = volume->recordPointers;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Build an array of record pointers. We'll sort the pointers by the block
|
|
Packit Service |
310c69 |
// names in the records, which is less work than sorting the record values.
|
|
Packit Service |
310c69 |
unsigned int i;
|
|
Packit Service |
310c69 |
for (i = 0; i < recordsPerPage; i++) {
|
|
Packit Service |
310c69 |
recordPointers[i] = &records[i];
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
STATIC_ASSERT(offsetof(UdsChunkRecord, name) == 0);
|
|
Packit Service |
310c69 |
int result = radixSort(volume->radixSorter, (const byte **) recordPointers,
|
|
Packit Service |
310c69 |
recordsPerPage, UDS_CHUNK_NAME_SIZE);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Use the sorted pointers to copy the records from the chapter to the
|
|
Packit Service |
310c69 |
// record page in tree order.
|
|
Packit Service |
310c69 |
encodeTree(recordPage, recordPointers, 0, 0, recordsPerPage);
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
bool searchRecordPage(const byte recordPage[],
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
const Geometry *geometry,
|
|
Packit Service |
310c69 |
UdsChunkData *metadata)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// The record page is just an array of chunk records.
|
|
Packit Service |
310c69 |
const UdsChunkRecord *records = (const UdsChunkRecord *) recordPage;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// The array of records is sorted by name and stored as a binary tree in
|
|
Packit Service |
310c69 |
// heap order, so the root of the tree is the first array element.
|
|
Packit Service |
310c69 |
unsigned int node = 0;
|
|
Packit Service |
310c69 |
while (node < geometry->recordsPerPage) {
|
|
Packit Service |
310c69 |
const UdsChunkRecord *record = &records[node];
|
|
Packit Service |
310c69 |
int result = memcmp(name, &record->name, UDS_CHUNK_NAME_SIZE);
|
|
Packit Service |
310c69 |
if (result == 0) {
|
|
Packit Service |
310c69 |
if (metadata != NULL) {
|
|
Packit Service |
310c69 |
*metadata = record->data;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return true;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
// The children of node N are in the heap at indexes 2N+1 and 2N+2.
|
|
Packit Service |
310c69 |
node = ((2 * node) + ((result < 0) ? 1 : 2));
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return false;
|
|
Packit Service |
310c69 |
}
|