Blame source/uds/recordPage.c

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
}