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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
|
/* Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*
* Queue data structure.
*/
#ifndef __CROS_EC_QUEUE_H
#define __CROS_EC_QUEUE_H
#include "common.h"
#include <stddef.h>
#include <stdint.h>
/* Generic queue container. */
/*
* Queue policies describe how a queue behaves (who it notifies, in what
* contexts) when units are added or removed from the queue.
*
* The queue_policy structure is a table of virtual function pointers. Each
* policy will implement the add and remove functions. Each policy also
* optionally defines a new structure that contains the queue_policy struct by
* value any any additional data needed to implement the policy. This
* structure is then initialized using the policy specific functions and the
* additional data.
*
* If a policy is so simple that it doesn't require any additional data then
* the queue_policy structure can just be used directly, as queue_policy_null
* does below.
*/
struct queue_policy {
void (*add)(struct queue_policy const *queue_policy, size_t count);
void (*remove)(struct queue_policy const *queue_policy, size_t count);
};
/*
* The NULL policy does no notification when units are added or removed from
* the queue. Since the NULL policy doesn't do anything it doesn't actually
* need to extend the queue_policy interface and can just use it directly.
*
* The QUEUE_NULL macro constructs a queue that uses the NULL policy.
*/
extern struct queue_policy const queue_policy_null;
#define QUEUE_NULL(SIZE, TYPE) QUEUE(SIZE, TYPE, queue_policy_null)
/*
* RAM state for a queue.
*/
struct queue_state {
/*
* The queue head and tail pointers are not wrapped until they are
* needed to access the queue buffer. This has a number of advantages,
* the queue doesn't have to waste an entry to disambiguate full and
* empty for one. It also provides a convenient total enqueue/dequeue
* log (one that does wrap at the limit of a size_t however).
*
* Empty:
* head == tail
*
* Full:
* head - tail == buffer_units
*/
size_t head; /* head: next to dequeue */
size_t tail; /* tail: next to enqueue */
};
/*
* Queue configuration stored in flash.
*/
struct queue {
struct queue_state volatile *state;
struct queue_policy const *policy;
size_t buffer_units; /* size of buffer (in units) */
size_t unit_bytes; /* size of unit (in byte) */
uint8_t *buffer;
};
/*
* Convenience macro for construction of a Queue along with its backing buffer
* and state structure. This macro creates a compound literal that can be used
* to statically initialize a queue.
*/
#define QUEUE(SIZE, TYPE, POLICY) \
((struct queue) { \
.state = &((struct queue_state){}), \
.policy = &POLICY, \
.buffer_units = SIZE, \
.unit_bytes = sizeof(TYPE), \
.buffer = (uint8_t *) &((TYPE[SIZE]){}), \
})
/* Initialize the queue to empty state. */
void queue_init(struct queue const *q);
/* Return TRUE if the queue is empty. */
int queue_is_empty(struct queue const *q);
/* Return the number of units stored in the queue. */
size_t queue_count(struct queue const *q);
/* Return the number of units worth of free space the queue has. */
size_t queue_space(struct queue const *q);
/* Return TRUE if the queue is full. */
int queue_is_full(struct queue const *q);
/*
* Chunk based queue access. A queue_chunk is a contiguous region of queue
* buffer bytes, not units. It may represent either free space in the queue
* or entries.
*/
struct queue_chunk {
size_t length;
uint8_t *buffer;
};
/*
* Return the largest contiguous block of free space from the tail of the
* queue. This may not be all of the available free space in the queue. Once
* some or all of the free space has been written to you must call
* queue_advance_tail to update the queue. You do not need to fill all of the
* free space returned before calling queue_advance_tail, and you may call
* queue_advance tail multiple times for a single chunk. But you must not
* advance the tail more than the length of the chunk, or more than the actual
* number of units that you have written to the free space represented by the
* chunk.
*/
struct queue_chunk queue_get_write_chunk(struct queue const *q);
/*
* Return the largest contiguous block of units from the head of the queue.
* This may not be all of the available units in the queue. Similar rules to
* the above apply to reading from this chunk, you can call queue_advance_head
* after reading, and you can all it multiple times if you like. However, if
* you do not call queue_advance_head this chunk will effectively be a peek
* into the queue contents, and later calls to queue_remove_* will see the
* same units.
*/
struct queue_chunk queue_get_read_chunk(struct queue const *q);
/*
* Move the queue head pointer forward count units. This discards count
* elements from the head of the queue. It will only discard up to the total
* number of elements in the queue, and it returns the number discarded.
*/
size_t queue_advance_head(struct queue const *q, size_t count);
/*
* Move the queue tail pointer forward count units. This signals to the queue
* that count new elements have been added to the queue using a queue_chunk
* that was returned by queue_get_write_chunk. Make sure that count units have
* been added to the chunk before calling queue_advance_tail.
*/
size_t queue_advance_tail(struct queue const *q, size_t count);
/* Add one unit to queue. */
size_t queue_add_unit(struct queue const *q, const void *src);
/* Add multiple units to queue. */
size_t queue_add_units(struct queue const *q, const void *src, size_t count);
/* Add multiple units to queue using supplied memcpy. */
size_t queue_add_memcpy(struct queue const *q,
const void *src,
size_t count,
void *(*memcpy)(void *dest,
const void *src,
size_t n));
/* Remove one unit from the begin of the queue. */
size_t queue_remove_unit(struct queue const *q, void *dest);
/* Remove multiple units from the begin of the queue. */
size_t queue_remove_units(struct queue const *q, void *dest, size_t count);
/* Remove multiple units from the begin of the queue using supplied memcpy. */
size_t queue_remove_memcpy(struct queue const *q,
void *dest,
size_t count,
void *(*memcpy)(void *dest,
const void *src,
size_t n));
/* Peek (return but don't remove) the count elements starting with the i'th. */
size_t queue_peek_units(struct queue const *q,
void *dest,
size_t i,
size_t count);
/* Peek (return but don't remove) the count elements starting with the i'th. */
size_t queue_peek_memcpy(struct queue const *q,
void *dest,
size_t i,
size_t count,
void *(*memcpy)(void *dest,
const void *src,
size_t n));
/*
* These macros will statically select the queue functions based on the number
* of units that are to be added or removed if they can. The single unit add
* and remove functions are much faster than calling the equivalent generic
* version with a count of one.
*/
#define QUEUE_ADD_UNITS(q, src, count) \
({ \
size_t result; \
\
if (count == 1) \
result = queue_add_unit(q, src); \
else \
result = queue_add_units(q, src, count); \
\
result; \
})
#define QUEUE_REMOVE_UNITS(q, dest, count) \
({ \
size_t result; \
\
if (count == 1) \
result = queue_remove_unit(q, dest); \
else \
result = queue_remove_units(q, dest, count); \
\
result; \
})
#endif /* __CROS_EC_QUEUE_H */
|
