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 #include "u_worklist.h"
30 #include "ralloc.h"
31
32 void
u_worklist_init(u_worklist * w,unsigned num_entries,void * mem_ctx)33 u_worklist_init(u_worklist *w, unsigned num_entries, void *mem_ctx)
34 {
35 w->size = num_entries;
36 w->count = 0;
37 w->start = 0;
38
39 w->present = rzalloc_array(mem_ctx, BITSET_WORD, BITSET_WORDS(num_entries));
40 w->entries = rzalloc_array(mem_ctx, unsigned *, num_entries);
41 }
42
43 void
u_worklist_fini(u_worklist * w)44 u_worklist_fini(u_worklist *w)
45 {
46 ralloc_free(w->present);
47 ralloc_free(w->entries);
48 }
49
50 void
u_worklist_push_head_index(u_worklist * w,unsigned * index)51 u_worklist_push_head_index(u_worklist *w, unsigned *index)
52 {
53 /* Pushing a block we already have is a no-op */
54 if (BITSET_TEST(w->present, *index))
55 return;
56
57 assert(w->count < w->size);
58
59 if (w->start == 0)
60 w->start = w->size - 1;
61 else
62 w->start--;
63
64 w->count++;
65
66 w->entries[w->start] = index;
67 BITSET_SET(w->present, *index);
68 }
69
70 unsigned *
u_worklist_peek_head_index(const u_worklist * w)71 u_worklist_peek_head_index(const u_worklist *w)
72 {
73 assert(w->count > 0);
74
75 return w->entries[w->start];
76 }
77
78 unsigned *
u_worklist_pop_head_index(u_worklist * w)79 u_worklist_pop_head_index(u_worklist *w)
80 {
81 assert(w->count > 0);
82
83 unsigned head = w->start;
84
85 w->start = (w->start + 1) % w->size;
86 w->count--;
87
88 BITSET_CLEAR(w->present, *(w->entries[head]));
89 return w->entries[head];
90 }
91
92 void
u_worklist_push_tail_index(u_worklist * w,unsigned * index)93 u_worklist_push_tail_index(u_worklist *w, unsigned *index)
94 {
95 /* Pushing a block we already have is a no-op */
96 if (BITSET_TEST(w->present, *index))
97 return;
98
99 assert(w->count < w->size);
100
101 w->count++;
102
103 unsigned tail = (w->start + w->count - 1) % w->size;
104
105 w->entries[tail] = index;
106 BITSET_SET(w->present, *index);
107 }
108
109 unsigned *
u_worklist_peek_tail_index(const u_worklist * w)110 u_worklist_peek_tail_index(const u_worklist *w)
111 {
112 assert(w->count > 0);
113
114 unsigned tail = (w->start + w->count - 1) % w->size;
115
116 return w->entries[tail];
117 }
118
119 unsigned *
u_worklist_pop_tail_index(u_worklist * w)120 u_worklist_pop_tail_index(u_worklist *w)
121 {
122 assert(w->count > 0);
123
124 unsigned tail = (w->start + w->count - 1) % w->size;
125
126 w->count--;
127
128 BITSET_CLEAR(w->present, *(w->entries[tail]));
129 return w->entries[tail];
130 }
131