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