drivers/md/dm-vdo/priority-table.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #ifndef VDO_PRIORITY_TABLE_H
   7 #define VDO_PRIORITY_TABLE_H
   8
   9 #include <linux/list.h>
  10
  11 /*
  12  * A priority_table is a simple implementation of a priority queue for entries with priorities that
  13  * are small non-negative integer values. It implements the obvious priority queue operations of
  14  * enqueuing an entry and dequeuing an entry with the maximum priority. It also supports removing
  15  * an arbitrary entry. The priority of an entry already in the table can be changed by removing it
  16  * and re-enqueuing it with a different priority. All operations have O(1) complexity.
  17  *
  18  * The links for the table entries must be embedded in the entries themselves. Lists are used to
  19  * link entries in the table and no wrapper type is declared, so an existing list entry in an
  20  * object can also be used to queue it in a priority_table, assuming the field is not used for
  21  * anything else while so queued.
  22  *
  23  * The table is implemented as an array of queues (circular lists) indexed by priority, along with
  24  * a hint for which queues are non-empty. Steven Skiena calls a very similar structure a "bounded
  25  * height priority queue", but given the resemblance to a hash table, "priority table" seems both
  26  * shorter and more apt, if somewhat novel.
  27  */
  28
  29 struct priority_table;
  30
  31 int __must_check vdo_make_priority_table(unsigned int max_priority,
  32                                          struct priority_table **table_ptr);
  33
  34 void vdo_free_priority_table(struct priority_table *table);
  35
  36 void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority,
  37                                 struct list_head *entry);
  38
  39 void vdo_reset_priority_table(struct priority_table *table);
  40
  41 struct list_head * __must_check vdo_priority_table_dequeue(struct priority_table *table);
  42
  43 void vdo_priority_table_remove(struct priority_table *table, struct list_head *entry);
  44
  45 bool __must_check vdo_is_priority_table_empty(struct priority_table *table);
  46
  47 #endif /* VDO_PRIORITY_TABLE_H */