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