/*

 * 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 true if the table is empty

 **/

bool isPriorityTableEmpty(PriorityTable *table)

  __attribute__((warn_unused_result));

#endif /* PRIORITY_TABLE_H */