1/* 2 * Copyright (c) 2022 Collabora Ltd. 3 * Copyright © 2014 Intel Corporation 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 22 * IN THE SOFTWARE. 23 * 24 * Authors: 25 * Jason Ekstrand (jason@jlekstrand.net) 26 * 27 */ 28 29 30#ifndef _U_WORKLIST_ 31#define _U_WORKLIST_ 32 33#include "util/bitset.h" 34 35#ifdef __cplusplus 36extern "C" { 37#endif 38 39/** Represents a double-ended queue of unique entries. Each entry must have a 40 * unique index in the range [0, num_entries). Internally, entries are tracked 41 * as pointers to that index (so you can go from the index pointer back to a 42 * containing structure). This requires index pointers to remain valid while 43 * they are in the worklist (i.e. no realloc). 44 * 45 * The worklist data structure guarantees that each entry is in the queue at 46 * most once. Pushing an entry onto either end of the queue is a no-op if the 47 * entry is already in the queue. Internally, the data structure maintains a 48 * bitset of present entries. 49 */ 50typedef struct { 51 /* The total size of the worklist */ 52 unsigned size; 53 54 /* The number of entries currently in the worklist */ 55 unsigned count; 56 57 /* The offset in the array of entries at which the list starts */ 58 unsigned start; 59 60 /* A bitset of all of the entries currently present in the worklist */ 61 BITSET_WORD *present; 62 63 /* The actual worklist */ 64 unsigned **entries; 65} u_worklist; 66 67void u_worklist_init(u_worklist *w, unsigned num_entries, void *mem_ctx); 68 69void u_worklist_fini(u_worklist *w); 70 71static inline bool 72u_worklist_is_empty(const u_worklist *w) 73{ 74 return w->count == 0; 75} 76 77void u_worklist_push_head_index(u_worklist *w, unsigned *block); 78 79unsigned *u_worklist_peek_head_index(const u_worklist *w); 80 81unsigned *u_worklist_pop_head_index(u_worklist *w); 82 83unsigned *u_worklist_peek_tail_index(const u_worklist *w); 84 85void u_worklist_push_tail_index(u_worklist *w, unsigned *block); 86 87unsigned *u_worklist_pop_tail_index(u_worklist *w); 88 89#define u_worklist_push_tail(w, block, index) \ 90 u_worklist_push_tail_index(w, &((block)->index)) 91 92#define u_worklist_push_head(w, block, index) \ 93 u_worklist_push_head_index(w, &((block)->index)) 94 95#define u_worklist_pop_head(w, entry_t, index) \ 96 container_of(u_worklist_pop_head_index(w), entry_t, index) 97 98#define u_worklist_pop_tail(w, entry_t, index) \ 99 container_of(u_worklist_pop_tail_index(w), entry_t, index) 100 101#define u_worklist_peek_head(w, entry_t, index) \ 102 container_of(u_worklist_peek_head_index(w), entry_t, index) 103 104#define u_worklist_peek_tail(w, entry_t, index) \ 105 container_of(u_worklist_peek_tail_index(w), entry_t, index) 106 107#ifdef __cplusplus 108} /* extern "C" */ 109#endif 110 111#endif /* _U_WORKLIST_ */ 112