1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bli
19 *
20 * \brief A generic structure queue
21 * (a queue for fixed length generally small) structures.
22 */
23
24 #include <string.h>
25
26 #include "MEM_guardedalloc.h"
27
28 #include "BLI_gsqueue.h"
29 #include "BLI_strict_flags.h"
30 #include "BLI_utildefines.h"
31
32 /* target chunk size: 64kb */
33 #define CHUNK_SIZE_DEFAULT (1 << 16)
34 /* ensure we get at least this many elems per chunk */
35 #define CHUNK_ELEM_MIN 32
36
37 struct QueueChunk {
38 struct QueueChunk *next;
39 char data[0];
40 };
41
42 struct _GSQueue {
43 struct QueueChunk *chunk_first; /* first active chunk to pop from */
44 struct QueueChunk *chunk_last; /* flast active chunk to push onto */
45 struct QueueChunk *chunk_free; /* free chunks to reuse */
46 size_t chunk_first_index; /* index into 'chunk_first' */
47 size_t chunk_last_index; /* index into 'chunk_last' */
48 size_t chunk_elem_max; /* number of elements per chunk */
49 size_t elem_size; /* memory size of elements */
50 size_t totelem; /* total number of elements */
51 };
52
queue_get_first_elem(GSQueue * queue)53 static void *queue_get_first_elem(GSQueue *queue)
54 {
55 return ((char *)(queue)->chunk_first->data) + ((queue)->elem_size * (queue)->chunk_first_index);
56 }
57
queue_get_last_elem(GSQueue * queue)58 static void *queue_get_last_elem(GSQueue *queue)
59 {
60 return ((char *)(queue)->chunk_last->data) + ((queue)->elem_size * (queue)->chunk_last_index);
61 }
62
63 /**
64 * \return number of elements per chunk, optimized for slop-space.
65 */
queue_chunk_elem_max_calc(const size_t elem_size,size_t chunk_size)66 static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
67 {
68 /* get at least this number of elems per chunk */
69 const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
70
71 BLI_assert((elem_size != 0) && (chunk_size != 0));
72
73 while (UNLIKELY(chunk_size <= elem_size_min)) {
74 chunk_size <<= 1;
75 }
76
77 /* account for slop-space */
78 chunk_size -= (sizeof(struct QueueChunk) + MEM_SIZE_OVERHEAD);
79
80 return chunk_size / elem_size;
81 }
82
BLI_gsqueue_new(const size_t elem_size)83 GSQueue *BLI_gsqueue_new(const size_t elem_size)
84 {
85 GSQueue *queue = MEM_callocN(sizeof(*queue), "BLI_gsqueue_new");
86
87 queue->chunk_elem_max = queue_chunk_elem_max_calc(elem_size, CHUNK_SIZE_DEFAULT);
88 queue->elem_size = elem_size;
89 /* force init */
90 queue->chunk_last_index = queue->chunk_elem_max - 1;
91
92 return queue;
93 }
94
queue_free_chunk(struct QueueChunk * data)95 static void queue_free_chunk(struct QueueChunk *data)
96 {
97 while (data) {
98 struct QueueChunk *data_next = data->next;
99 MEM_freeN(data);
100 data = data_next;
101 }
102 }
103
104 /**
105 * Free the queue's data and the queue itself
106 */
BLI_gsqueue_free(GSQueue * queue)107 void BLI_gsqueue_free(GSQueue *queue)
108 {
109 queue_free_chunk(queue->chunk_first);
110 queue_free_chunk(queue->chunk_free);
111 MEM_freeN(queue);
112 }
113
114 /**
115 * Copies the source value onto the end of the queue
116 *
117 * \note This copies #GSQueue.elem_size bytes from \a item,
118 * (the pointer itself is not stored).
119 *
120 * \param item: source data to be copied to the queue.
121 */
BLI_gsqueue_push(GSQueue * queue,const void * item)122 void BLI_gsqueue_push(GSQueue *queue, const void *item)
123 {
124 queue->chunk_last_index++;
125 queue->totelem++;
126
127 if (UNLIKELY(queue->chunk_last_index == queue->chunk_elem_max)) {
128 struct QueueChunk *chunk;
129 if (queue->chunk_free) {
130 chunk = queue->chunk_free;
131 queue->chunk_free = chunk->next;
132 }
133 else {
134 chunk = MEM_mallocN(sizeof(*chunk) + (queue->elem_size * queue->chunk_elem_max), __func__);
135 }
136
137 chunk->next = NULL;
138
139 if (queue->chunk_last == NULL) {
140 queue->chunk_first = chunk;
141 }
142 else {
143 queue->chunk_last->next = chunk;
144 }
145
146 queue->chunk_last = chunk;
147 queue->chunk_last_index = 0;
148 }
149
150 BLI_assert(queue->chunk_last_index < queue->chunk_elem_max);
151
152 /* Return last of queue */
153 memcpy(queue_get_last_elem(queue), item, queue->elem_size);
154 }
155
156 /**
157 * Retrieves and removes the first element from the queue.
158 * The value is copies to \a r_item, which must be at least \a elem_size bytes.
159 *
160 * Does not reduce amount of allocated memory.
161 */
BLI_gsqueue_pop(GSQueue * queue,void * r_item)162 void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
163 {
164 BLI_assert(BLI_gsqueue_is_empty(queue) == false);
165
166 memcpy(r_item, queue_get_first_elem(queue), queue->elem_size);
167 queue->chunk_first_index++;
168 queue->totelem--;
169
170 if (UNLIKELY(queue->chunk_first_index == queue->chunk_elem_max || queue->totelem == 0)) {
171 struct QueueChunk *chunk_free = queue->chunk_first;
172
173 queue->chunk_first = queue->chunk_first->next;
174 queue->chunk_first_index = 0;
175 if (queue->chunk_first == NULL) {
176 queue->chunk_last = NULL;
177 queue->chunk_last_index = queue->chunk_elem_max - 1;
178 }
179
180 chunk_free->next = queue->chunk_free;
181 queue->chunk_free = chunk_free;
182 }
183 }
184
BLI_gsqueue_len(const GSQueue * queue)185 size_t BLI_gsqueue_len(const GSQueue *queue)
186 {
187 return queue->totelem;
188 }
189
190 /**
191 * Returns true if the queue is empty, false otherwise
192 */
BLI_gsqueue_is_empty(const GSQueue * queue)193 bool BLI_gsqueue_is_empty(const GSQueue *queue)
194 {
195 return (queue->chunk_first == NULL);
196 }
197