md/dm-vdo/priority-table.c

6 #include "priority-table.h"
16 /* We use a single 64-bit search vector, so the maximum priority is 63 */
20  * All the entries with the same priority are queued in a circular list in a bucket for that
21  * priority. The table is essentially an array of buckets.
25 	 * The head of a queue of table entries, all having the same priority
28 	/* The priority of all the entries in this bucket */
29 	unsigned int priority;
33  * A priority table is an array of buckets, indexed by priority. New entries are added to the end
34  * of the queue in the appropriate bucket. The dequeue operation finds the highest-priority
39 	/* The maximum priority of entries that may be stored in this table */
43 	/* The array of all buckets, indexed by priority */
49  * @max_priority: The maximum priority value for table entries.
58 	unsigned int priority;
68 	for (priority = 0; priority <= max_priority; priority++) {
69 		struct bucket *bucket = &table->buckets[priority];
71 		bucket->priority = priority;
103  * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when
112 	unsigned int priority;
115 	for (priority = 0; priority <= table->max_priority; priority++)
116 		list_del_init(&table->buckets[priority].queue);
120  * vdo_priority_table_enqueue() - Add a new entry to the priority table, appending it to the queue
121  *                                for entries with the specified priority.
123  * @priority: The priority of the entry.
127 void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority,
130 	VDO_ASSERT_LOG_ONLY((priority <= table->max_priority),
131 			    "entry priority must be valid for the table");
134 	list_move_tail(entry, &table->buckets[priority].queue);
137 	table->search_vector |= (1ULL << priority);
142 	table->search_vector &= ~(1ULL << bucket->priority);
146  * vdo_priority_table_dequeue() - Find the highest-priority entry in the table, remove it from the
148  * @table: The priority table from which to remove an entry.
150  * If there are multiple entries with the same priority, the one that has been in the table with
151  * that priority the longest will be returned.
167 	 * Find the highest priority non-empty bucket by finding the highest-order non-zero bit in
185  * vdo_priority_table_remove() - Remove a specified entry from its priority table.
216  * vdo_is_priority_table_empty() - Return whether the priority table is empty.