Blender  V3.3
gsqueue.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
10 #include <string.h>
11 
12 #include "MEM_guardedalloc.h"
13 
14 #include "BLI_gsqueue.h"
15 #include "BLI_strict_flags.h"
16 #include "BLI_utildefines.h"
17 
18 /* target chunk size: 64kb */
19 #define CHUNK_SIZE_DEFAULT (1 << 16)
20 /* ensure we get at least this many elems per chunk */
21 #define CHUNK_ELEM_MIN 32
22 
23 struct QueueChunk {
24  struct QueueChunk *next;
25  char data[0];
26 };
27 
28 struct _GSQueue {
29  struct QueueChunk *chunk_first; /* first active chunk to pop from */
30  struct QueueChunk *chunk_last; /* last active chunk to push onto */
31  struct QueueChunk *chunk_free; /* free chunks to reuse */
32  size_t chunk_first_index; /* index into 'chunk_first' */
33  size_t chunk_last_index; /* index into 'chunk_last' */
34  size_t chunk_elem_max; /* number of elements per chunk */
35  size_t elem_size; /* memory size of elements */
36  size_t elem_num; /* total number of elements */
37 };
38 
40 {
41  return ((char *)(queue)->chunk_first->data) + ((queue)->elem_size * (queue)->chunk_first_index);
42 }
43 
45 {
46  return ((char *)(queue)->chunk_last->data) + ((queue)->elem_size * (queue)->chunk_last_index);
47 }
48 
52 static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
53 {
54  /* get at least this number of elems per chunk */
55  const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
56 
57  BLI_assert((elem_size != 0) && (chunk_size != 0));
58 
59  while (UNLIKELY(chunk_size <= elem_size_min)) {
60  chunk_size <<= 1;
61  }
62 
63  /* account for slop-space */
64  chunk_size -= (sizeof(struct QueueChunk) + MEM_SIZE_OVERHEAD);
65 
66  return chunk_size / elem_size;
67 }
68 
69 GSQueue *BLI_gsqueue_new(const size_t elem_size)
70 {
71  GSQueue *queue = MEM_callocN(sizeof(*queue), "BLI_gsqueue_new");
72 
73  queue->chunk_elem_max = queue_chunk_elem_max_calc(elem_size, CHUNK_SIZE_DEFAULT);
74  queue->elem_size = elem_size;
75  /* force init */
76  queue->chunk_last_index = queue->chunk_elem_max - 1;
77 
78  return queue;
79 }
80 
81 static void queue_free_chunk(struct QueueChunk *data)
82 {
83  while (data) {
84  struct QueueChunk *data_next = data->next;
85  MEM_freeN(data);
86  data = data_next;
87  }
88 }
89 
91 {
92  queue_free_chunk(queue->chunk_first);
93  queue_free_chunk(queue->chunk_free);
95 }
96 
97 void BLI_gsqueue_push(GSQueue *queue, const void *item)
98 {
99  queue->chunk_last_index++;
100  queue->elem_num++;
101 
102  if (UNLIKELY(queue->chunk_last_index == queue->chunk_elem_max)) {
103  struct QueueChunk *chunk;
104  if (queue->chunk_free) {
105  chunk = queue->chunk_free;
106  queue->chunk_free = chunk->next;
107  }
108  else {
109  chunk = MEM_mallocN(sizeof(*chunk) + (queue->elem_size * queue->chunk_elem_max), __func__);
110  }
111 
112  chunk->next = NULL;
113 
114  if (queue->chunk_last == NULL) {
115  queue->chunk_first = chunk;
116  }
117  else {
118  queue->chunk_last->next = chunk;
119  }
120 
121  queue->chunk_last = chunk;
122  queue->chunk_last_index = 0;
123  }
124 
125  BLI_assert(queue->chunk_last_index < queue->chunk_elem_max);
126 
127  /* Return last of queue */
128  memcpy(queue_get_last_elem(queue), item, queue->elem_size);
129 }
130 
131 void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
132 {
134 
135  memcpy(r_item, queue_get_first_elem(queue), queue->elem_size);
136  queue->chunk_first_index++;
137  queue->elem_num--;
138 
139  if (UNLIKELY(queue->chunk_first_index == queue->chunk_elem_max || queue->elem_num == 0)) {
140  struct QueueChunk *chunk_free = queue->chunk_first;
141 
142  queue->chunk_first = queue->chunk_first->next;
143  queue->chunk_first_index = 0;
144  if (queue->chunk_first == NULL) {
145  queue->chunk_last = NULL;
146  queue->chunk_last_index = queue->chunk_elem_max - 1;
147  }
148 
149  chunk_free->next = queue->chunk_free;
150  queue->chunk_free = chunk_free;
151  }
152 }
153 
155 {
156  return queue->elem_num;
157 }
158 
160 {
161  return (queue->chunk_first == NULL);
162 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
#define UNLIKELY(x)
Read Guarded memory(de)allocation.
#define MEM_SIZE_OVERHEAD
SyclQueue * queue
static void * queue_get_last_elem(GSQueue *queue)
Definition: gsqueue.c:44
void BLI_gsqueue_free(GSQueue *queue)
Definition: gsqueue.c:90
static void * queue_get_first_elem(GSQueue *queue)
Definition: gsqueue.c:39
void BLI_gsqueue_push(GSQueue *queue, const void *item)
Definition: gsqueue.c:97
GSQueue * BLI_gsqueue_new(const size_t elem_size)
Definition: gsqueue.c:69
void BLI_gsqueue_pop(GSQueue *queue, void *r_item)
Definition: gsqueue.c:131
#define CHUNK_ELEM_MIN
Definition: gsqueue.c:21
static void queue_free_chunk(struct QueueChunk *data)
Definition: gsqueue.c:81
bool BLI_gsqueue_is_empty(const GSQueue *queue)
Definition: gsqueue.c:159
static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
Definition: gsqueue.c:52
#define CHUNK_SIZE_DEFAULT
Definition: gsqueue.c:19
size_t BLI_gsqueue_len(const GSQueue *queue)
Definition: gsqueue.c:154
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static const int chunk_size
struct QueueChunk * next
Definition: gsqueue.c:24
char data[0]
Definition: gsqueue.c:25
size_t elem_size
Definition: gsqueue.c:35
struct QueueChunk * chunk_free
Definition: gsqueue.c:31
size_t chunk_first_index
Definition: gsqueue.c:32
size_t chunk_elem_max
Definition: gsqueue.c:34
size_t chunk_last_index
Definition: gsqueue.c:33
struct QueueChunk * chunk_last
Definition: gsqueue.c:30
size_t elem_num
Definition: gsqueue.c:36
struct QueueChunk * chunk_first
Definition: gsqueue.c:29