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 */ 48