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
|
/* 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);
/* 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 */
|
