Blender V5.3
gsqueue.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <cstring>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_gsqueue.hh"
17#include "BLI_utildefines.hh"
18
19#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
20
21namespace blender {
22
23/* target chunk size: 64kb */
24#define CHUNK_SIZE_DEFAULT (1 << 16)
25/* ensure we get at least this many elems per chunk */
26#define CHUNK_ELEM_MIN 32
27
28struct QueueChunk {
30 char data[0];
31};
32
33struct GSQueue {
34 QueueChunk *chunk_first; /* first active chunk to pop from */
35 QueueChunk *chunk_last; /* last active chunk to push onto */
36 QueueChunk *chunk_free; /* free chunks to reuse */
37 size_t chunk_first_index; /* index into 'chunk_first' */
38 size_t chunk_last_index; /* index into 'chunk_last' */
39 size_t chunk_elem_max; /* number of elements per chunk */
40 size_t elem_size; /* memory size of elements */
41 size_t elem_num; /* total number of elements */
42};
43
44static void *queue_get_first_elem(GSQueue *queue)
45{
46 return (static_cast<char *>((queue)->chunk_first->data)) +
47 ((queue)->elem_size * (queue)->chunk_first_index);
48}
49
50static void *queue_get_last_elem(GSQueue *queue)
51{
52 return (static_cast<char *>((queue)->chunk_last->data)) +
53 ((queue)->elem_size * (queue)->chunk_last_index);
54}
55
59static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
60{
61 /* get at least this number of elems per chunk */
62 const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
63
64 BLI_assert((elem_size != 0) && (chunk_size != 0));
65
66 while (chunk_size <= elem_size_min) [[unlikely]] {
67 chunk_size <<= 1;
68 }
69
70 /* account for slop-space */
71 chunk_size -= (sizeof(QueueChunk) + MEM_SIZE_OVERHEAD);
72
73 return chunk_size / elem_size;
74}
75
76GSQueue *BLI_gsqueue_new(const size_t elem_size)
77{
78 GSQueue *queue = MEM_new_zeroed<GSQueue>("BLI_gsqueue_new");
79
81 queue->elem_size = elem_size;
82 /* force init */
83 queue->chunk_last_index = queue->chunk_elem_max - 1;
84
85 return queue;
86}
87
89{
90 while (data) {
91 QueueChunk *data_next = data->next;
92 MEM_delete(data);
93 data = data_next;
94 }
95}
96
98{
101 MEM_delete(queue);
102}
103
104void BLI_gsqueue_push(GSQueue *queue, const void *item)
105{
106 queue->chunk_last_index++;
107 queue->elem_num++;
108
109 if (queue->chunk_last_index == queue->chunk_elem_max) [[unlikely]] {
110 QueueChunk *chunk;
111 if (queue->chunk_free) {
112 chunk = queue->chunk_free;
113 queue->chunk_free = chunk->next;
114 }
115 else {
116 chunk = static_cast<QueueChunk *>(MEM_new_uninitialized(
117 sizeof(*chunk) + (queue->elem_size * queue->chunk_elem_max), __func__));
118 }
119
120 chunk->next = nullptr;
121
122 if (queue->chunk_last == nullptr) {
123 queue->chunk_first = chunk;
124 }
125 else {
126 queue->chunk_last->next = chunk;
127 }
128
129 queue->chunk_last = chunk;
130 queue->chunk_last_index = 0;
131 }
132
134
135 /* Return last of queue */
136 memcpy(queue_get_last_elem(queue), item, queue->elem_size);
137}
138
139void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
140{
141 BLI_assert(BLI_gsqueue_is_empty(queue) == false);
142
143 memcpy(r_item, queue_get_first_elem(queue), queue->elem_size);
144 queue->chunk_first_index++;
145 queue->elem_num--;
146
147 if (queue->chunk_first_index == queue->chunk_elem_max || queue->elem_num == 0) [[unlikely]] {
148 QueueChunk *chunk_free = queue->chunk_first;
149
150 queue->chunk_first = queue->chunk_first->next;
151 queue->chunk_first_index = 0;
152 if (queue->chunk_first == nullptr) {
153 queue->chunk_last = nullptr;
154 queue->chunk_last_index = queue->chunk_elem_max - 1;
155 }
156
157 chunk_free->next = queue->chunk_free;
158 queue->chunk_free = chunk_free;
159 }
160}
161
162size_t BLI_gsqueue_len(const GSQueue *queue)
163{
164 return queue->elem_num;
165}
166
168{
169 return (queue->chunk_first == nullptr);
170}
171
172} // namespace blender
Read Blender memory allocation and freeing.
#define MEM_SIZE_OVERHEAD
#define CHUNK_ELEM_MIN
Definition gsqueue.cc:26
#define CHUNK_SIZE_DEFAULT
Definition gsqueue.cc:24
BMesh Iterators.
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BLI_gsqueue_push(GSQueue *queue, const void *item)
Definition gsqueue.cc:104
static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
Definition gsqueue.cc:59
void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
Definition gsqueue.cc:139
void BLI_gsqueue_free(GSQueue *queue)
Definition gsqueue.cc:97
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
GSQueue * BLI_gsqueue_new(size_t elem_size)
Definition gsqueue.cc:76
static void * queue_get_last_elem(GSQueue *queue)
Definition gsqueue.cc:50
BMesh const char void * data
static void queue_free_chunk(QueueChunk *data)
Definition gsqueue.cc:88
size_t BLI_gsqueue_len(const GSQueue *queue)
Definition gsqueue.cc:162
bool BLI_gsqueue_is_empty(const GSQueue *queue)
Definition gsqueue.cc:167
static void * queue_get_first_elem(GSQueue *queue)
Definition gsqueue.cc:44
size_t elem_num
Definition gsqueue.cc:41
size_t chunk_last_index
Definition gsqueue.cc:38
QueueChunk * chunk_last
Definition gsqueue.cc:35
size_t chunk_first_index
Definition gsqueue.cc:37
QueueChunk * chunk_first
Definition gsqueue.cc:34
size_t elem_size
Definition gsqueue.cc:40
size_t chunk_elem_max
Definition gsqueue.cc:39
QueueChunk * chunk_free
Definition gsqueue.cc:36
QueueChunk * next
Definition gsqueue.cc:29