1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* Deque data structure.
21 This code slightly simplifies the implementation of a deque as
22 a circular queue. To use it, declare a "struct deque" and a
23 pointer to the element type. For example, for a deque of
29 To initialize the deque with a initial capacity of 0:
31 deque_init_null (&deque);
34 Alternatively, to initialize the deque with an initial minimum
37 data = deque_init (&deque, 4, sizeof *data);
39 Functions that access elements in the deque return array
40 indexes. This is fairly convenient:
42 // Push X at the back of the deque.
43 data[deque_push_back (&deque)] = x;
45 // Pop off the front of the deque into X.
46 x = data[deque_pop_front (&deque)];
48 // Obtain the element just past the back of the deque as X.
49 x = data[deque_back (&deque, 1)];
51 The push functions will not expand the deque on their own.
52 Use the deque_expand function if necessary, as in:
54 // Push X at the back of the deque, first expanding the
55 // deque if necessary.
56 if (deque_is_full (&deque))
57 data = deque_expand (&deque, data, sizeof *data);
58 data[deque_push_back (&deque)] = x;
60 Expanding a deque will copy its elements from one memory
61 region to another using memcpy. Thus, your deque elements
62 must tolerate copying if their deque is to be expanded. */
64 #ifndef LIBPSPP_DEQUE_H
65 #define LIBPSPP_DEQUE_H 1
70 #include <libpspp/assertion.h>
72 /* A deque implemented as a circular buffer. */
75 size_t capacity; /* Capacity, which must be a power of 2. */
76 size_t front; /* One past the front of the queue. */
77 size_t back; /* The back of the queue. */
80 void deque_init_null (struct deque *);
81 void *deque_init (struct deque *, size_t capacity, size_t elem_size);
82 void *deque_expand (struct deque *, void *, size_t elem_size);
84 /* Returns the number of elements currently in DEQUE. */
86 deque_count (const struct deque *deque)
88 return deque->front - deque->back;
91 /* Returns the maximum number of elements that DEQUE can hold at
92 any time. (Use deque_expand to increase a deque's
95 deque_capacity (const struct deque *deque)
97 return deque->capacity;
100 /* Returns true if DEQUE is currently empty (contains no
101 elements), false otherwise. */
103 deque_is_empty (const struct deque *deque)
105 return deque_count (deque) == 0;
108 /* Returns true if DEQUE is currently full (cannot take any more
109 elements), false otherwise. */
111 deque_is_full (const struct deque *deque)
113 return deque_count (deque) >= deque_capacity (deque);
116 /* Returns the index of the element in DEQUE that is OFFSET
117 elements from its front. A value 0 for OFFSET requests the
118 element at the front, a value of 1 the element just behind the
119 front, and so on. OFFSET must be less than the current number
120 of elements in DEQUE. */
122 deque_front (const struct deque *deque, size_t offset)
124 assert (deque_count (deque) > offset);
125 return (deque->front - offset - 1) & (deque->capacity - 1);
128 /* Returns the index of the element in DEQUE that is OFFSET
129 elements from its back. A value 0 for OFFSET requests the
130 element at the back, a value of 1 the element just ahead of
131 the back, and so on. OFFSET must be less than the current
132 number of elements in DEQUE. */
134 deque_back (const struct deque *deque, size_t offset)
136 assert (deque_count (deque) > offset);
137 return (deque->back + offset) & (deque->capacity - 1);
140 /* Adds a new element at the front of DEQUE, which must not be
141 full, and returns the index of the new element. The caller is
142 responsible for assigning a value to the returned element. */
144 deque_push_front (struct deque *deque)
146 assert (!deque_is_full (deque));
147 return deque->front++ & (deque->capacity - 1);
150 /* Adds a new element at the back of DEQUE, which must not be
151 full, and returns the index of the new element. The caller is
152 responsible for assigning a value to the returned element. */
154 deque_push_back (struct deque *deque)
156 assert (!deque_is_full (deque));
157 return --deque->back & (deque->capacity - 1);
160 /* Pops the front element off DEQUE (which must not be empty) and
161 returns its index. The element may be reused the next time an
162 element is pushed into DEQUE or when DEQUE is expanded. */
164 deque_pop_front (struct deque *deque)
166 assert (!deque_is_empty (deque));
167 return --deque->front & (deque->capacity - 1);
170 /* Pops the back element off DEQUE (which must not be empty) and
171 returns its index. The element may be reused the next time
172 an element is pushed into DEQUE or when DEQUE is expanded. */
174 deque_pop_back (struct deque *deque)
176 assert (!deque_is_empty (deque));
177 return deque->back++ & (deque->capacity - 1);
180 #endif /* libpspp/deque.h */