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
|
/* 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 INCLUDE_QUEUE_H
#define INCLUDE_QUEUE_H
#include "common.h"
#include <stddef.h>
#include <stdint.h>
/* Generic queue container. */
/*
* 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;
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.
*/
#define QUEUE_CONFIG(NAME, SIZE, TYPE) \
static TYPE CONCAT2(NAME, _buffer)[SIZE]; \
\
static struct queue_state CONCAT2(NAME, _state); \
struct queue const NAME = \
{ \
.state = &CONCAT2(NAME, _state), \
.buffer_units = SIZE, \
.unit_bytes = sizeof(TYPE), \
.buffer = (uint8_t *) CONCAT2(NAME, _buffer), \
};
/* 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, void const *src);
/* Add multiple units to queue. */
size_t queue_add_units(struct queue const *q, void const *src, size_t count);
/* Add multiple units to queue using supplied memcpy. */
size_t queue_add_memcpy(struct queue const *q,
void const *src,
size_t count,
void *(*memcpy)(void *dest,
void const *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,
void const *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);
/*
* 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 /* INCLUDE_QUEUE_H */
|
