1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "priority-table.h"
11 #include "memory-alloc.h"
14 #include "status-codes.h"
16 /* We use a single 64-bit search vector, so the maximum priority is 63 */
34  * of the queue in the appropriate bucket. The dequeue operation finds the highest-priority
35  * non-empty bucket by searching a bit vector represented as a single 8-byte word, which is very
41 	/* A bit vector flagging all buckets that are currently non-empty */
48  * vdo_make_priority_table() - Allocate and initialize a new priority_table.
69 		struct bucket *bucket = &table->buckets[priority];  in vdo_make_priority_table()
71 		bucket->priority = priority;  in vdo_make_priority_table()
72 		INIT_LIST_HEAD(&bucket->queue);  in vdo_make_priority_table()
75 	table->max_priority = max_priority;  in vdo_make_priority_table()
76 	table->search_vector = 0;  in vdo_make_priority_table()
83  * vdo_free_priority_table() - Free a priority_table.
103  * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when
114 	table->search_vector = 0;  in vdo_reset_priority_table()
115 	for (priority = 0; priority <= table->max_priority; priority++)  in vdo_reset_priority_table()
116 		list_del_init(&table->buckets[priority].queue);  in vdo_reset_priority_table()
120  * vdo_priority_table_enqueue() - Add a new entry to the priority table, appending it to the queue
130 	VDO_ASSERT_LOG_ONLY((priority <= table->max_priority),  in vdo_priority_table_enqueue()
134 	list_move_tail(entry, &table->buckets[priority].queue);  in vdo_priority_table_enqueue()
136 	/* Flag the bucket in the search vector since it must be non-empty. */  in vdo_priority_table_enqueue()
137 	table->search_vector |= (1ULL << priority);  in vdo_priority_table_enqueue()
142 	table->search_vector &= ~(1ULL << bucket->priority);  in mark_bucket_empty()
146  * vdo_priority_table_dequeue() - Find the highest-priority entry in the table, remove it from the
153  * Return: The dequeued entry, or NULL if the table is currently empty.
161 	if (table->search_vector == 0) {  in vdo_priority_table_dequeue()
162 		/* All buckets are empty. */  in vdo_priority_table_dequeue()
167 	 * Find the highest priority non-empty bucket by finding the highest-order non-zero bit in  in vdo_priority_table_dequeue()
170 	top_priority = ilog2(table->search_vector);  in vdo_priority_table_dequeue()
173 	bucket = &table->buckets[top_priority];  in vdo_priority_table_dequeue()
174 	entry = bucket->queue.next;  in vdo_priority_table_dequeue()
178 	if (list_empty(&bucket->queue))  in vdo_priority_table_dequeue()
185  * vdo_priority_table_remove() - Remove a specified entry from its priority table.
204 	next_entry = entry->next;  in vdo_priority_table_remove()
208 	 * If the rest of the list is now empty, the next node must be the list head in the bucket  in vdo_priority_table_remove()
216  * vdo_is_priority_table_empty() - Return whether the priority table is empty.
219  * Return: true if the table is empty.
223 	return (table->search_vector == 0);  in vdo_is_priority_table_empty()