/*
 * 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/vdo-releases/aluminum/src/c++/vdo/base/priorityTable.h#2 $
 */

#ifndef PRIORITY_TABLE_H
#define PRIORITY_TABLE_H

#include "ringNode.h"

/**
 * A PriorityTable is a simple implementation of a priority queue for entries
 * with priorities that are small non-negative integer values. It implements
 * the obvious priority queue operations of enqueuing an entry and dequeuing
 * an entry with the maximum priority. It also supports removing an arbitrary
 * entry. The priority of an entry already in the table can be changed by
 * removing it and re-enqueuing it with a different priority. All operations
 * have O(1) complexity.
 *
 * The links for the table entries must be embedded in the entries themselves.
 * RingNode is used to link entries in the table and no wrapper type is
 * declared, so an existing RingNode link in an object can also be used to
 * queue it in a PriorityTable, assuming the field is not used for anything
 * else while so queued.
 *
 * The table is implemented as an array of queues (circular lists) indexed by
 * priority, along with a hint for which queues are non-empty. Steven Skiena
 * calls a very similar structure a "bounded height priority queue", but given
 * the resemblance to a hash table, "priority table" seems both shorter and
 * more apt, if somewhat novel.
 **/

typedef struct priorityTable PriorityTable;

/**
 * Allocate and initialize a new PriorityTable.
 *
 * @param [in]  maxPriority  The maximum priority value for table entries
 * @param [out] tablePtr     A pointer to hold the new table
 *
 * @return VDO_SUCCESS or an error code
 **/
int makePriorityTable(unsigned int maxPriority, PriorityTable **tablePtr)
  __attribute__((warn_unused_result));

/**
 * Free a PriorityTable and null out the reference to it. NOTE: The table does
 * not own the entries stored in it and they are not freed by this call.
 *
 * @param [in,out] tablePtr  The reference to the table to free
 **/
void freePriorityTable(PriorityTable **tablePtr);

/**
 * Add a new entry to the priority table, appending it to the queue for
 * entries with the specified priority.
 *
 * @param table     The table in which to store the entry
 * @param priority  The priority of the entry
 * @param entry     The RingNode embedded in the entry to store in the table
 *                  (the caller must have initialized it)
 **/
void priorityTableEnqueue(PriorityTable *table,
                          unsigned int   priority,
                          RingNode      *entry);

/**
 * Reset a priority table, leaving it in the same empty state as when newly
 * constructed. NOTE: The table does not own the entries stored in it and they
 * are not freed (or even unlinked from each other) by this call.
 *
 * @param table  The table to reset
 **/
void resetPriorityTable(PriorityTable *table);

/**
 * Find the highest-priority entry in the table, remove it from the table, and
 * return it. If there are multiple entries with the same priority, the one
 * that has been in the table with that priority the longest will be returned.
 *
 * @param table  The priority table from which to remove an entry
 *
 * @return the dequeued entry, or NULL if the table is currently empty
 **/
RingNode *priorityTableDequeue(PriorityTable *table)
  __attribute__((warn_unused_result));

/**
 * Remove a specified entry from its priority table.
 *
 * @param table   The table from which to remove the entry
 * @param entry   The entry to remove from the table
 **/
void priorityTableRemove(PriorityTable *table, RingNode *entry);

/**
 * Return whether the priority table is empty.
 *
 * @param table   The table to check
 *
 * @return <code>true</code> if the table is empty
 **/
bool isPriorityTableEmpty(PriorityTable *table)
  __attribute__((warn_unused_result));

#endif /* PRIORITY_TABLE_H */