+
+void
+util_sparse_array_free_list_init(struct util_sparse_array_free_list *fl,
+ struct util_sparse_array *arr,
+ uint32_t sentinel,
+ uint32_t next_offset)
+{
+ fl->head = sentinel;
+ fl->arr = arr;
+ fl->sentinel = sentinel;
+ fl->next_offset = next_offset;
+}
+
+static uint64_t
+free_list_head(uint64_t old, uint32_t next)
+{
+ return ((old & 0xffffffff00000000ull) + 0x100000000ull) | next;
+}
+
+void
+util_sparse_array_free_list_push(struct util_sparse_array_free_list *fl,
+ uint32_t *items, unsigned num_items)
+{
+ assert(num_items > 0);
+ assert(items[0] != fl->sentinel);
+ void *last_elem = util_sparse_array_get(fl->arr, items[0]);
+ uint32_t *last_next = (uint32_t *)((char *)last_elem + fl->next_offset);
+ for (unsigned i = 1; i < num_items; i++) {
+ *last_next = items[i];
+ assert(items[i] != fl->sentinel);
+ last_elem = util_sparse_array_get(fl->arr, items[i]);
+ last_next = (uint32_t *)((char *)last_elem + fl->next_offset);
+ }
+
+ uint64_t current_head, old_head;
+ old_head = p_atomic_read(&fl->head);
+ do {
+ current_head = old_head;
+ *last_next = current_head; /* Index is the bottom 32 bits */
+ uint64_t new_head = free_list_head(current_head, items[0]);
+ old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
+ } while (old_head != current_head);
+}
+
+uint32_t
+util_sparse_array_free_list_pop_idx(struct util_sparse_array_free_list *fl)
+{
+ uint64_t current_head;
+
+ current_head = p_atomic_read(&fl->head);
+ while (1) {
+ if ((uint32_t)current_head == fl->sentinel)
+ return fl->sentinel;
+
+ uint32_t head_idx = current_head; /* Index is the bottom 32 bits */
+ void *head_elem = util_sparse_array_get(fl->arr, head_idx);
+ uint32_t *head_next = (uint32_t *)((char *)head_elem + fl->next_offset);
+ uint32_t new_head = free_list_head(current_head, *head_next);
+ uint64_t old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
+ if (old_head == current_head)
+ return head_idx;
+ current_head = old_head;
+ }
+}
+
+void *
+util_sparse_array_free_list_pop_elem(struct util_sparse_array_free_list *fl)
+{
+ uint64_t current_head;
+
+ current_head = p_atomic_read(&fl->head);
+ while (1) {
+ if ((uint32_t)current_head == fl->sentinel)
+ return NULL;
+
+ uint32_t head_idx = current_head; /* Index is the bottom 32 bits */
+ void *head_elem = util_sparse_array_get(fl->arr, head_idx);
+ uint32_t *head_next = (uint32_t *)((char *)head_elem + fl->next_offset);
+ uint32_t new_head = free_list_head(current_head, *head_next);
+ uint64_t old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
+ if (old_head == current_head)
+ return head_elem;
+ current_head = old_head;
+ }
+}