6 #include "priority-table.h"
21  * priority. The table is essentially an array of buckets.
25 	 * The head of a queue of table entries, all having the same priority
33  * A priority table is an array of buckets, indexed by priority. New entries are added to the end
39 	/* The maximum priority of entries that may be stored in this table */
49  * @max_priority: The maximum priority value for table entries.
50  * @table_ptr: A pointer to hold the new table.
56 	struct priority_table *table;  in vdo_make_priority_table()  local
64 				       struct bucket, __func__, &table);  in vdo_make_priority_table()
69 		struct bucket *bucket = &table->buckets[priority];  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()
78 	*table_ptr = table;  in vdo_make_priority_table()
84  * @table: The table to free.
86  * The table does not own the entries stored in it and they are not freed by this call.
88 void vdo_free_priority_table(struct priority_table *table)  in vdo_free_priority_table()  argument
90 	if (table == NULL)  in vdo_free_priority_table()
94 	 * Unlink the buckets from any entries still in the table so the entries won't be left with  in vdo_free_priority_table()
97 	vdo_reset_priority_table(table);  in vdo_free_priority_table()
99 	vdo_free(table);  in vdo_free_priority_table()
103  * vdo_reset_priority_table() - Reset a priority table, leaving it in the same empty state as when
105  * @table: The table to reset.
107  * The table does not own the entries stored in it and they are not freed (or even unlinked from
110 void vdo_reset_priority_table(struct priority_table *table)  in vdo_reset_priority_table()  argument
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
122  * @table: The table in which to store the entry.
124  * @entry: The list_head embedded in the entry to store in the table (the caller must have
127 void vdo_priority_table_enqueue(struct priority_table *table, unsigned int priority,  in vdo_priority_table_enqueue()  argument
130 	VDO_ASSERT_LOG_ONLY((priority <= table->max_priority),  in vdo_priority_table_enqueue()
131 			    "entry priority must be valid for the table");  in vdo_priority_table_enqueue()
134 	list_move_tail(entry, &table->buckets[priority].queue);  in vdo_priority_table_enqueue()
137 	table->search_vector |= (1ULL << priority);  in vdo_priority_table_enqueue()
140 static inline void mark_bucket_empty(struct priority_table *table, struct bucket *bucket)  in mark_bucket_empty()  argument
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
147  *                                table, and return it.
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
153  * Return: The dequeued entry, or NULL if the table is currently empty.
155 struct list_head *vdo_priority_table_dequeue(struct priority_table *table)  in vdo_priority_table_dequeue()  argument
161 	if (table->search_vector == 0) {  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()
179 		mark_bucket_empty(table, bucket);  in vdo_priority_table_dequeue()
185  * vdo_priority_table_remove() - Remove a specified entry from its priority table.
186  * @table: The table from which to remove the entry.
187  * @entry: The entry to remove from the table.
189 void vdo_priority_table_remove(struct priority_table *table, struct list_head *entry)  in vdo_priority_table_remove()  argument
194 	 * We can't guard against calls where the entry is on a list for a different table, but  in vdo_priority_table_remove()
195 	 * it's easy to deal with an entry not in any table or list.  in vdo_priority_table_remove()
212 		mark_bucket_empty(table, list_entry(next_entry, struct bucket, queue));  in vdo_priority_table_remove()
216  * vdo_is_priority_table_empty() - Return whether the priority table is empty.
217  * @table: The table to check.
219  * Return: true if the table is empty.
221 bool vdo_is_priority_table_empty(struct priority_table *table)  in vdo_is_priority_table_empty()  argument
223 	return (table->search_vector == 0);  in vdo_is_priority_table_empty()