xref: /third_party/mesa3d/src/util/u_worklist.c (revision bf215546) 
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
32void
33u_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
43void
44u_worklist_fini(u_worklist *w)
45{
46   ralloc_free(w->present);
47   ralloc_free(w->entries);
48}
49
50void
51u_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
70unsigned *
71u_worklist_peek_head_index(const u_worklist *w)
72{
73   assert(w->count > 0);
74
75   return w->entries[w->start];
76}
77
78unsigned *
79u_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
92void
93u_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
109unsigned *
110u_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
119unsigned *
120u_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