/*
* 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.c#1 $
*/
#include "priorityTable.h"
#include "errors.h"
#include "memoryAlloc.h"
#include "numUtils.h"
#include "statusCodes.h"
/** We use a single 64-bit search vector, so the maximum priority is 63 */
enum { MAX_PRIORITY = 63 };
/**
* All the entries with the same priority are queued in a circular list in a
* bucket for that priority. The table is essentially an array of buckets.
**/
typedef struct bucket {
/** The head of a queue of table entries, all having the same priority */
RingNode queue;
/** The priority of all the entries in this bucket */
unsigned int priority;
} Bucket;
/**
* A priority table is an array of buckets, indexed by priority. New entries
* are added to the end of the queue in the appropriate bucket. The dequeue
* operation finds the highest-priority non-empty bucket by searching a bit
* vector represented as a single 8-byte word, which is very fast with
* compiler and CPU support.
**/
struct priorityTable {
/** The maximum priority of entries that may be stored in this table */
unsigned int maxPriority;
/** A bit vector flagging all buckets that are currently non-empty */
uint64_t searchVector;
/** The array of all buckets, indexed by priority */
Bucket buckets[];
};
/**
* Convert a queue head to to the bucket that contains it.
*
* @param head The bucket queue ring head pointer to convert
*
* @return the enclosing bucket
**/
static inline Bucket *asBucket(RingNode *head)
{
STATIC_ASSERT(offsetof(Bucket, queue) == 0);
return (Bucket *) head;
}
/**********************************************************************/
int makePriorityTable(unsigned int maxPriority, PriorityTable **tablePtr)
{
if (maxPriority > MAX_PRIORITY) {
return UDS_INVALID_ARGUMENT;
}
PriorityTable *table;
int result = ALLOCATE_EXTENDED(PriorityTable, maxPriority + 1, Bucket,
__func__, &table);
if (result != VDO_SUCCESS) {
return result;
}
for (unsigned int priority = 0; priority <= maxPriority; priority++) {
Bucket *bucket = &table->buckets[priority];
bucket->priority = priority;
initializeRing(&bucket->queue);
}
table->maxPriority = maxPriority;
table->searchVector = 0;
*tablePtr = table;
return VDO_SUCCESS;
}
/**********************************************************************/
void freePriorityTable(PriorityTable **tablePtr)
{
PriorityTable *table = *tablePtr;
if (table == NULL) {
return;
}
// Unlink the buckets from any entries still in the table so the entries
// won't be left with dangling pointers to freed memory.
resetPriorityTable(table);
FREE(table);
*tablePtr = NULL;
}
/**********************************************************************/
void resetPriorityTable(PriorityTable *table)
{
table->searchVector = 0;
for (unsigned int priority = 0; priority <= table->maxPriority; priority++) {
unspliceRingNode(&table->buckets[priority].queue);
}
}
/**********************************************************************/
void priorityTableEnqueue(PriorityTable *table,
unsigned int priority,
RingNode *entry)
{
ASSERT_LOG_ONLY((priority <= table->maxPriority),
"entry priority must be valid for the table");
// Append the entry to the queue in the specified bucket.
pushRingNode(&table->buckets[priority].queue, entry);
// Flag the bucket in the search vector since it must be non-empty.
table->searchVector |= (1ULL << priority);
}
/**********************************************************************/
static inline void markBucketEmpty(PriorityTable *table, Bucket *bucket)
{
table->searchVector &= ~(1ULL << bucket->priority);
}
/**********************************************************************/
RingNode *priorityTableDequeue(PriorityTable *table)
{
// Find the highest priority non-empty bucket by finding the highest-order
// non-zero bit in the search vector.
int topPriority = logBaseTwo(table->searchVector);
if (topPriority < 0) {
// All buckets are empty.
return NULL;
}
// Dequeue the first entry in the bucket.
Bucket *bucket = &table->buckets[topPriority];
RingNode *entry = unspliceRingNode(bucket->queue.next);
// Clear the bit in the search vector if the bucket has been emptied.
if (isRingEmpty(&bucket->queue)) {
markBucketEmpty(table, bucket);
}
return entry;
}
/**********************************************************************/
void priorityTableRemove(PriorityTable *table, RingNode *entry)
{
// We can't guard against calls where the entry is on a ring for a different
// table, but it's easy to deal with an entry not in any table or ring.
if (isRingEmpty(entry)) {
return;
}
// Remove the entry from the bucket ring, remembering a pointer to another
// entry in the ring.
RingNode *nextNode = entry->next;
unspliceRingNode(entry);
// If the rest of the ring is now empty, the next node must be the ring head
// in the bucket and we can use it to update the search vector.
if (isRingEmpty(nextNode)) {
markBucketEmpty(table, asBucket(nextNode));
}
}
/**********************************************************************/
bool isPriorityTableEmpty(PriorityTable *table)
{
return (table->searchVector == 0);
}