|
Packit Service |
b3514a |
/*
|
|
Packit Service |
b3514a |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
b3514a |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
b3514a |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
b3514a |
* of the License, or (at your option) any later version.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
b3514a |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
b3514a |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
b3514a |
* GNU General Public License for more details.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
b3514a |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
b3514a |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
b3514a |
* 02110-1301, USA.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/priorityTable.h#2 $
|
|
Packit Service |
b3514a |
*/
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
#ifndef PRIORITY_TABLE_H
|
|
Packit Service |
b3514a |
#define PRIORITY_TABLE_H
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
#include "ringNode.h"
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* A PriorityTable is a simple implementation of a priority queue for entries
|
|
Packit Service |
b3514a |
* with priorities that are small non-negative integer values. It implements
|
|
Packit Service |
b3514a |
* the obvious priority queue operations of enqueuing an entry and dequeuing
|
|
Packit Service |
b3514a |
* an entry with the maximum priority. It also supports removing an arbitrary
|
|
Packit Service |
b3514a |
* entry. The priority of an entry already in the table can be changed by
|
|
Packit Service |
b3514a |
* removing it and re-enqueuing it with a different priority. All operations
|
|
Packit Service |
b3514a |
* have O(1) complexity.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* The links for the table entries must be embedded in the entries themselves.
|
|
Packit Service |
b3514a |
* RingNode is used to link entries in the table and no wrapper type is
|
|
Packit Service |
b3514a |
* declared, so an existing RingNode link in an object can also be used to
|
|
Packit Service |
b3514a |
* queue it in a PriorityTable, assuming the field is not used for anything
|
|
Packit Service |
b3514a |
* else while so queued.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* The table is implemented as an array of queues (circular lists) indexed by
|
|
Packit Service |
b3514a |
* priority, along with a hint for which queues are non-empty. Steven Skiena
|
|
Packit Service |
b3514a |
* calls a very similar structure a "bounded height priority queue", but given
|
|
Packit Service |
b3514a |
* the resemblance to a hash table, "priority table" seems both shorter and
|
|
Packit Service |
b3514a |
* more apt, if somewhat novel.
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
typedef struct priorityTable PriorityTable;
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Allocate and initialize a new PriorityTable.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param [in] maxPriority The maximum priority value for table entries
|
|
Packit Service |
b3514a |
* @param [out] tablePtr A pointer to hold the new table
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @return VDO_SUCCESS or an error code
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
int makePriorityTable(unsigned int maxPriority, PriorityTable **tablePtr)
|
|
Packit Service |
b3514a |
__attribute__((warn_unused_result));
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Free a PriorityTable and null out the reference to it. NOTE: The table does
|
|
Packit Service |
b3514a |
* not own the entries stored in it and they are not freed by this call.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param [in,out] tablePtr The reference to the table to free
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
void freePriorityTable(PriorityTable **tablePtr);
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Add a new entry to the priority table, appending it to the queue for
|
|
Packit Service |
b3514a |
* entries with the specified priority.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param table The table in which to store the entry
|
|
Packit Service |
b3514a |
* @param priority The priority of the entry
|
|
Packit Service |
b3514a |
* @param entry The RingNode embedded in the entry to store in the table
|
|
Packit Service |
b3514a |
* (the caller must have initialized it)
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
void priorityTableEnqueue(PriorityTable *table,
|
|
Packit Service |
b3514a |
unsigned int priority,
|
|
Packit Service |
b3514a |
RingNode *entry);
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Reset a priority table, leaving it in the same empty state as when newly
|
|
Packit Service |
b3514a |
* constructed. NOTE: The table does not own the entries stored in it and they
|
|
Packit Service |
b3514a |
* are not freed (or even unlinked from each other) by this call.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param table The table to reset
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
void resetPriorityTable(PriorityTable *table);
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Find the highest-priority entry in the table, remove it from the table, and
|
|
Packit Service |
b3514a |
* return it. If there are multiple entries with the same priority, the one
|
|
Packit Service |
b3514a |
* that has been in the table with that priority the longest will be returned.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param table The priority table from which to remove an entry
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @return the dequeued entry, or NULL if the table is currently empty
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
RingNode *priorityTableDequeue(PriorityTable *table)
|
|
Packit Service |
b3514a |
__attribute__((warn_unused_result));
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Remove a specified entry from its priority table.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param table The table from which to remove the entry
|
|
Packit Service |
b3514a |
* @param entry The entry to remove from the table
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
void priorityTableRemove(PriorityTable *table, RingNode *entry);
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
/**
|
|
Packit Service |
b3514a |
* Return whether the priority table is empty.
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @param table The table to check
|
|
Packit Service |
b3514a |
*
|
|
Packit Service |
b3514a |
* @return true if the table is empty
|
|
Packit Service |
b3514a |
**/
|
|
Packit Service |
b3514a |
bool isPriorityTableEmpty(PriorityTable *table)
|
|
Packit Service |
b3514a |
__attribute__((warn_unused_result));
|
|
Packit Service |
b3514a |
|
|
Packit Service |
b3514a |
#endif /* PRIORITY_TABLE_H */
|