GNU Radio's DVBS2RX Package
cdeque.h
Go to the documentation of this file.
1/* -*- c++ -*- */
2/*
3 * Copyright (c) 2021 Igor Freire.
4 *
5 * This file is part of gr-dvbs2rx.
6 *
7 * SPDX-License-Identifier: GPL-3.0-or-later
8 */
9
10#ifndef INCLUDED_DVBS2RX_CDEQUE_H
11#define INCLUDED_DVBS2RX_CDEQUE_H
12
13#include <volk/volk_alloc.hh>
14#include <cstring>
15
16/**
17 * @brief Fixed-length double-ended queue with contiguous volk-aligned elements
18 *
19 * Creates a queue (or first-in first-out data structure) that stores data on a
20 * fixed-length and contiguous range of indexes with proper alignment created by
21 * volk_malloc. Similarly to an std::deque, this implementation supports
22 * insertion at both the queue's back (or tail) and front (or head). On the
23 * other hand, unlike an std::dequeue, this implementation always has L elements
24 * from tail to head, namely the queue has a fixed length.
25 *
26 * To enforce the fixed length, this template class only allows for writing of
27 * new elements, while not providing any function to pop elements
28 * explicitly. The front element is popped automatically whenever a new element
29 * is written at the back. Likewise, the back element is popped whenever a new
30 * element is pushed into the head.
31 *
32 * The key feature of this class is that it ensures the elements from tail to
33 * head (or back to front) are always on a contiguous memory block with
34 * sequential indexes. Hence, one can safely pass this buffer's tail pointer to
35 * a function that processes up to L elements from a C-style array. For
36 * instance, a function "sum(float* x)" that sums up to L elements from a
37 * float[L] array at address x.
38 *
39 * The implementation is based on a ring buffer, with a fixed-size volk-aligned
40 * array allocated on the heap by the constructor. However, unlike a regular
41 * ring buffer, this implementation ensures the data is on a contiguous and
42 * sequential range of indexes even when the head and tail pointers wrap around.
43 *
44 * For example, consider a four-element circular buffer holding the sequence [0,
45 * 1, 2, 3], where 0 is at the tail index and 3 is at the head. Then, suppose
46 * that, at first, we want to call a volk kernel based on this array. Later on,
47 * a new number comes in, and the buffer advances such that the previous tail
48 * element (i.e., 0) is thrown away, the tail pointer advances to the next
49 * number (i.e., 1), and the head pointer wraps around to where number 0 was
50 * before. Suppose the new number is 4, such that the hypothetical ring buffer
51 * now holds [4, 1, 2, 3]. In this scenario, the actual array of interest is [1,
52 * 2, 3, 4], but the circular buffer no longer holds these values sequentially
53 * on a contiguous range of indexes. Hence, if we were to use such a ring buffer
54 * for something like a volk dot product with a fixed array of taps, it would be
55 * necessary to execute two calls, one for the first part (e.g., [1, 2, 3]) and
56 * the other for the remaining part ([4] in the example). That would reduce the
57 * efficiency of processing a large batch of samples at once.
58 *
59 * This implementation avoids the problem by using a buffer whose actual length
60 * is (n_reps * L), i.e. much longer than necessary, where "n_reps" is a chosen
61 * number of repetitions of L-length segments. When the head pointer reaches the
62 * end of the buffer, the implementation copies the last L-1 values back to the
63 * beginning and rewinds the head pointer back to index L-1, instead of index
64 * 0. As a result, the range [i_tail, i_head) will process samples 0 to
65 * L-1. Consequently, the L numbers of interest are always available on a
66 * contiguous range of indexes. The sample applies when moving the tail pointer
67 * in the other direction.
68 *
69 * This double-ended queue allows for ring buffer movement in both clockwise and
70 * counterclockwise directions. The buffer spins counterclockwise when writing
71 * elements on its back (tail). For instance, if the tail index is 10 and we
72 * push an element on this index, the buffer moves to the left
73 * (counterclockwise) such that the next tail index becomes 9. As a result, the
74 * previous write (on index 10) shifts to the second position when reading
75 * samples from tail to head. In contrast, the buffer spins clockwise when
76 * writing elements on its head. On a similar example, if the head index is 10
77 * and we push a new element on this index, the buffer shifts to the right such
78 * that the next head index becomes 11. Consequently, the previous write (on
79 * index 10) shifts to the penultimate position when reading samples from tail
80 * to head. In both cases, the buffer shifts in a direction that keeps the
81 * previous write inside the buffer.
82 *
83 * The two movement directions can be used in different applications. For
84 * example, by writing samples on the queue's back, one can implement a delay
85 * line (see delay_line.h). That is, a buffer holding the last L samples, which
86 * can be read on a contiguous array from tail to head starting with the most
87 * recent sample and ending at the oldest sample. In contrast, by writing on the
88 * queue's front, one can keep the last L samples in reversed order. That is,
89 * the contiguous array from tail to head will hold the last L samples starting
90 * from the oldest sample and ending at the most recent sample.
91 *
92 * Besides, note the adopted terminology is such that the tail pointer is
93 * interchangeably called the back of the queue and the head pointer is
94 * considered the front of the queue. The natural FIFO direction would be to
95 * enter the queue at the back and leave it on its front. The reverse movement
96 * is to enter the queue on its front and leave it on its back. In any case,
97 * this class always reads the buffer contents from back to front (tail to
98 * head). The beginning and end of the queue depends on the movement direction.
99 *
100 * Note this data structure is primarily meant to be used with Volk kernels,
101 * which usually take the pointer to a contiguous volk-allocated data array. The
102 * reason for using n_reps is to avoid doing the aforementioned copy too
103 * often. The tradeoff is between copying often or allocating too much memory.
104 */
105namespace gr {
106namespace dvbs2rx {
107
108template <typename T>
110{
111private:
112 volk::vector<T> buf; /** Contiguous Volk buffer */
113 unsigned int i_tail; /** Tail index */
114 const unsigned int L; /** Queue length */
115 const unsigned int n_reps; /** Number of L-length segment repetitions */
116
117public:
118 explicit cdeque(unsigned int len, unsigned int n_reps = 10)
119 : buf(n_reps * len), i_tail(0), L(len), n_reps(n_reps)
120 {
121 }
122
123 /**
124 * @brief Push new element into the ring buffer's back (tail).
125 *
126 * Move the ring buffer counterclockwise before and then push the given
127 * element on the new tail index.
128 *
129 * @param in New element.
130 */
131 void push_back(const T& in)
132 {
133 /* When the tail pointer needs to wrap around, copy the first L-1
134 * elements back to the end of the buffer. */
135 if (i_tail == 0) {
136 i_tail = ((n_reps - 1) * L) + 1; // next index is that minus 1
137 std::copy(buf.begin(), buf.begin() + L - 1, buf.end() - L + 1);
138 }
139 buf[--i_tail] = in;
140 }
141
142 /**
143 * @brief Push new element into the ring buffer's front (head).
144 *
145 * Move the ring buffer clockwise before and then push the given element on
146 * the new head index.
147 *
148 * @param in New element.
149 */
150 void push_front(const T& in)
151 {
152 /* When the tail pointer needs to wrap around, copy the last L-1
153 * elements back to the beginning of the buffer. */
154 if (i_tail == ((n_reps - 1) * L)) {
155 i_tail = -1; // next index is that plus 1 (i.e., 0)
156 std::copy(buf.end() - L + 1, buf.end(), buf.begin());
157 }
158 buf[++i_tail + L - 1] = in;
159 }
160
161 /**
162 * @brief Access the element at the back of the queue.
163 * @return Reference to the back element.
164 */
165 const T& back() const { return buf[i_tail]; }
166
167 /**
168 * @brief Access the element at the front of the queue.
169 * @return Reference to the front element.
170 */
171 const T& front() const { return buf[i_tail + L - 1]; }
172
173 /**
174 * @brief Get length L of the queue
175 * @return Queue length.
176 */
177 unsigned int length() const { return L; }
178};
179
180} // namespace dvbs2rx
181} // namespace gr
182
183#endif /* INCLUDED_DVBS2RX_CDEQUE_H */
Definition cdeque.h:110
unsigned int length() const
Get length L of the queue.
Definition cdeque.h:177
void push_front(const T &in)
Push new element into the ring buffer's front (head).
Definition cdeque.h:150
const T & front() const
Access the element at the front of the queue.
Definition cdeque.h:171
void push_back(const T &in)
Push new element into the ring buffer's back (tail).
Definition cdeque.h:131
const T & back() const
Access the element at the back of the queue.
Definition cdeque.h:165
cdeque(unsigned int len, unsigned int n_reps=10)
Definition cdeque.h:118
Fixed-length double-ended queue with contiguous volk-aligned elements.
Definition gr_bch.h:22