1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
/*
* ***** BEGIN GPL LICENSE BLOCK *****
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
* All rights reserved.
*
* The Original Code is: all of this file.
*
* Contributor(s): none yet.
*
* ***** END GPL LICENSE BLOCK *****
*/
/** \file blender/blenlib/intern/gsqueue.c
* \ingroup bli
*
* \brief A generic structure queue
* (a queue for fixed length generally small) structures.
*
* \note Only use this if you need (first-in-first-out),
* otherwise #BLI_stack is more efficient (first-in-last-out).
*/
#include <string.h>
#include "MEM_guardedalloc.h"
#include "BLI_utildefines.h"
#include "BLI_gsqueue.h"
#include "BLI_strict_flags.h"
typedef struct _GSQueueElem GSQueueElem;
struct _GSQueueElem {
GSQueueElem *next;
char data[0];
};
struct _GSQueue {
GSQueueElem *head;
GSQueueElem *tail;
size_t elem_size;
};
/**
* Create a new GSQueue.
*
* \param elem_size The size of the structures in the queue.
* \retval The new queue
*/
GSQueue *BLI_gsqueue_new(size_t elem_size)
{
GSQueue *gq = MEM_mallocN(sizeof(*gq), "gqueue_new");
gq->head = gq->tail = NULL;
gq->elem_size = elem_size;
return gq;
}
/**
* Query if the queue is empty
*/
bool BLI_gsqueue_is_empty(GSQueue *gq)
{
return (gq->head == NULL);
}
/**
* Query number elements in the queue
*/
int BLI_gsqueue_size(GSQueue *gq)
{
GSQueueElem *elem;
int size = 0;
for (elem = gq->head; elem; elem = elem->next)
size++;
return size;
}
/**
* Access the item at the head of the queue
* without removing it.
*
* \param r_item: A pointer to an appropriately
* sized structure (the size passed to #BLI_gsqueue_new)
*/
void BLI_gsqueue_peek(GSQueue *gq, void *r_item)
{
memcpy(r_item, &gq->head->data, gq->elem_size);
}
/**
* Access the item at the head of the queue
* and remove it.
*
* \param r_item: A pointer to an appropriately
* sized structure (the size passed to #BLI_gsqueue_new).
* Can be NULL if desired.
*/
void BLI_gsqueue_pop(GSQueue *gq, void *r_item)
{
GSQueueElem *elem = gq->head;
if (elem == gq->tail) {
gq->head = gq->tail = NULL;
}
else {
gq->head = gq->head->next;
}
if (r_item) {
memcpy(r_item, elem->data, gq->elem_size);
}
MEM_freeN(elem);
}
/**
* Push an element onto the tail of the queue.
*
* \param item A pointer to an appropriately
* sized structure (the size passed to BLI_gsqueue_new).
*/
void BLI_gsqueue_push(GSQueue *gq, const void *item)
{
GSQueueElem *elem;
/* compare: prevent events added double in row */
if (!BLI_gsqueue_is_empty(gq)) {
if (0 == memcmp(item, gq->head->data, gq->elem_size))
return;
}
elem = MEM_mallocN(sizeof(*elem) + gq->elem_size, "gqueue_push");
memcpy(elem->data, item, gq->elem_size);
elem->next = NULL;
if (BLI_gsqueue_is_empty(gq)) {
gq->tail = gq->head = elem;
}
else {
gq->tail = gq->tail->next = elem;
}
}
/**
* Push an element back onto the head of the queue (so
* it would be returned from the next call to BLI_gsqueue_pop).
*
* \param item A pointer to an appropriately
* sized structure (the size passed to BLI_gsqueue_new).
*/
void BLI_gsqueue_pushback(GSQueue *gq, const void *item)
{
GSQueueElem *elem = MEM_mallocN(sizeof(*elem) + gq->elem_size, "gqueue_push");
memcpy(elem->data, item, gq->elem_size);
elem->next = gq->head;
if (BLI_gsqueue_is_empty(gq)) {
gq->head = gq->tail = elem;
}
else {
gq->head = elem;
}
}
/**
* Free the queue
*/
void BLI_gsqueue_free(GSQueue *gq)
{
while (gq->head) {
BLI_gsqueue_pop(gq, NULL);
}
MEM_freeN(gq);
}
|
