|
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/openChapterZone.h#1 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#ifndef OPEN_CHAPTER_ZONE_H
|
|
Packit Service |
310c69 |
#define OPEN_CHAPTER_ZONE_H 1
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "common.h"
|
|
Packit Service |
310c69 |
#include "geometry.h"
|
|
Packit Service |
310c69 |
#include "typeDefs.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* OpenChapterZone is the mutable, in-memory representation of one zone's
|
|
Packit Service |
310c69 |
* section of an Albireo index chapter.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* In addition to providing the same access to records as an on-disk
|
|
Packit Service |
310c69 |
* chapter, the open chapter zone must allow records to be added or
|
|
Packit Service |
310c69 |
* modified. It must provide a way to generate the on-disk representation
|
|
Packit Service |
310c69 |
* without excessive work. It does that by accumulating records in the order
|
|
Packit Service |
310c69 |
* they are added (maintaining temporal locality), and referencing them (as
|
|
Packit Service |
310c69 |
* record numbers) from hash slots selected from the name. If the metadata for
|
|
Packit Service |
310c69 |
* a name changes, the record field is just modified in place.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* Storage for the records (names and metadata) is allocated when the zone
|
|
Packit Service |
310c69 |
* is created. It keeps no references to the data passed to it, and performs
|
|
Packit Service |
310c69 |
* no additional allocation when adding records. Opening a new chapter simply
|
|
Packit Service |
310c69 |
* marks it as being empty.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* Records are stored in a flat array. To allow a value of zero in a
|
|
Packit Service |
310c69 |
* hash slot to indicate that the slot is empty, records are numbered starting
|
|
Packit Service |
310c69 |
* at one (1-based). Since C arrays are 0-based, the records array contains
|
|
Packit Service |
310c69 |
* enough space for N+1 records, and the record that starts at array index
|
|
Packit Service |
310c69 |
* zero is never used or referenced.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The array of hash slots is actually two arrays, superimposed: an
|
|
Packit Service |
310c69 |
* array of record numbers, indexed by hash value, and an array of deleted
|
|
Packit Service |
310c69 |
* flags, indexed by record number. This overlay is possible because the
|
|
Packit Service |
310c69 |
* number of hash slots always exceeds the number of records, and is done
|
|
Packit Service |
310c69 |
* simply to save on memory.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
enum {
|
|
Packit Service |
310c69 |
OPEN_CHAPTER_RECORD_NUMBER_BITS = 23,
|
|
Packit Service |
310c69 |
OPEN_CHAPTER_MAX_RECORD_NUMBER = (1 << OPEN_CHAPTER_RECORD_NUMBER_BITS) - 1
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
typedef struct {
|
|
Packit Service |
310c69 |
/** If non-zero, the record number addressed by this hash slot */
|
|
Packit Service |
310c69 |
unsigned int recordNumber : OPEN_CHAPTER_RECORD_NUMBER_BITS;
|
|
Packit Service |
310c69 |
/** If true, the record at the index of this hash slot was deleted */
|
|
Packit Service |
310c69 |
bool recordDeleted : 1;
|
|
Packit Service |
310c69 |
} __attribute__((packed)) Slot;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
typedef struct openChapterZone {
|
|
Packit Service |
310c69 |
/** Maximum number of records that can be stored */
|
|
Packit Service |
310c69 |
unsigned int capacity;
|
|
Packit Service |
310c69 |
/** Number of records stored */
|
|
Packit Service |
310c69 |
unsigned int size;
|
|
Packit Service |
310c69 |
/** Number of deleted records */
|
|
Packit Service |
310c69 |
unsigned int deleted;
|
|
Packit Service |
310c69 |
/** Record data, stored as (name, metadata), 1-based */
|
|
Packit Service |
310c69 |
UdsChunkRecord *records;
|
|
Packit Service |
310c69 |
/** The number of slots in the chapter zone hash table. */
|
|
Packit Service |
310c69 |
unsigned int slotCount;
|
|
Packit Service |
310c69 |
/** Hash table, referencing virtual record numbers */
|
|
Packit Service |
310c69 |
Slot slots[];
|
|
Packit Service |
310c69 |
} OpenChapterZone;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Allocate an open chapter zone.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param geometry the geometry of the volume
|
|
Packit Service |
310c69 |
* @param zoneCount the total number of open chapter zones
|
|
Packit Service |
310c69 |
* @param openChapterPtr a pointer to hold the new open chapter
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int makeOpenChapter(const Geometry *geometry,
|
|
Packit Service |
310c69 |
unsigned int zoneCount,
|
|
Packit Service |
310c69 |
OpenChapterZone **openChapterPtr)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Return the number of records in the open chapter zone that have not been
|
|
Packit Service |
310c69 |
* deleted.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the number of non-deleted records
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
size_t openChapterSize(const OpenChapterZone *openChapter)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Open a chapter by marking it empty.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param openChapter The chapter to open
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
void resetOpenChapter(OpenChapterZone *openChapter);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Search the open chapter for a chunk name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param openChapter The chapter to search
|
|
Packit Service |
310c69 |
* @param name The name of the desired chunk
|
|
Packit Service |
310c69 |
* @param metadata The holder for the metadata associated with the
|
|
Packit Service |
310c69 |
* chunk, if found (or NULL)
|
|
Packit Service |
310c69 |
* @param found A pointer which will be set to true if the chunk
|
|
Packit Service |
310c69 |
* name was found
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
void searchOpenChapter(OpenChapterZone *openChapter,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
UdsChunkData *metadata,
|
|
Packit Service |
310c69 |
bool *found);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Put a record into the open chapter.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param openChapter The chapter into which to put the record
|
|
Packit Service |
310c69 |
* @param name The name of the record
|
|
Packit Service |
310c69 |
* @param metadata The record data
|
|
Packit Service |
310c69 |
* @param remaining Pointer to an integer set to the number of additional
|
|
Packit Service |
310c69 |
* records that can be added to this chapter
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int putOpenChapter(OpenChapterZone *openChapter,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
const UdsChunkData *metadata,
|
|
Packit Service |
310c69 |
unsigned int *remaining)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Remove a record from the open chapter.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param openChapter The chapter from which to remove the record
|
|
Packit Service |
310c69 |
* @param name The name of the record
|
|
Packit Service |
310c69 |
* @param removed Pointer to bool set to true if the
|
|
Packit Service |
310c69 |
* record was found
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
void removeFromOpenChapter(OpenChapterZone *openChapter,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
bool *removed);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Clean up an open chapter and its memory.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param openChapter the chapter to destroy
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
void freeOpenChapter(OpenChapterZone *openChapter);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#endif /* OPEN_CHAPTER_ZONE_H */
|