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 #ifndef LIBPSPP_DEQUE_H
20 #define LIBPSPP_DEQUE_H 1
26 #include <libpspp/compiler.h>
30 /* Declares data and functions for a deque whose elements have
31 the given ELEMENT_TYPE. Instances of the deque are declared
32 as "struct NAME", and each function that operates on the deque
33 has NAME_ as a prefix. */
34 #define DEQUE_DECLARE(NAME, ELEMENT_TYPE) \
35 /* An instance of the deque. */ \
38 size_t capacity; /* Capacity, which must be a power of 2. */ \
39 size_t front; /* One past the front of the queue. */ \
40 size_t back; /* The back of the queue. */ \
41 ELEMENT_TYPE *data; /* Pointer to CAPACITY elements. */ \
44 /* Initializes DEQUE as an empty deque that can store at least \
45 CAPACITY elements. (The actual capacity may be larger and is \
46 always a power of 2.) */ \
48 NAME##_init (struct NAME *deque, size_t capacity) \
50 deque->capacity = 1; \
51 while (deque->capacity < capacity) \
52 deque->capacity <<= 1; \
53 deque->front = deque->back = 0; \
54 deque->data = xnmalloc (deque->capacity, sizeof *deque->data); \
57 /* Destroys DEQUE, which must be empty. */ \
59 NAME##_destroy (struct NAME *deque) \
64 /* Returns the number of elements currently in DEQUE. */ \
65 static inline size_t \
66 NAME##_count (const struct NAME *deque) \
68 return deque->front - deque->back; \
71 /* Returns the maximum number of elements that DEQUE can hold at \
73 static inline size_t \
74 NAME##_capacity (const struct NAME *deque) \
76 return deque->capacity; \
79 /* Returns true if DEQUE is currently empty (contains no \
80 elements), false otherwise. */ \
82 NAME##_is_empty (const struct NAME *deque) \
84 return NAME##_count (deque) == 0; \
87 /* Returns true if DEQUE is currently full (cannot take any more \
88 elements), false otherwise. */ \
90 NAME##_is_full (const struct NAME *deque) \
92 return NAME##_count (deque) >= NAME##_capacity (deque); \
95 /* Returns the element in DEQUE that is OFFSET elements from its \
96 front. A value 0 for OFFSET requests the element at the \
97 front, a value of 1 the element just behind the front, and so \
98 on. OFFSET must be less than the current number of elements \
100 static inline ELEMENT_TYPE * \
101 NAME##_front (const struct NAME *deque, size_t offset) \
103 assert (NAME##_count (deque) > offset); \
104 return &deque->data[(deque->front - offset - 1) & (deque->capacity - 1)]; \
107 /* Returns the element in DEQUE that is OFFSET elements from its \
108 back. A value 0 for OFFSET requests the element at the back, \
109 a value of 1 the element just ahead of the back, and so on. \
110 OFFSET must be less than the current number of elements in \
112 static inline ELEMENT_TYPE * \
113 NAME##_back (const struct NAME *deque, size_t offset) \
115 assert (NAME##_count (deque) > offset); \
116 return &deque->data[(deque->back + offset) & (deque->capacity - 1)]; \
119 /* Adds and returns the address of a new element at the front of \
120 DEQUE, which must not be full. The caller is responsible for \
121 assigning a value to the returned element. */ \
122 static inline ELEMENT_TYPE * \
123 NAME##_push_front (struct NAME *deque) \
125 assert (!NAME##_is_full (deque)); \
126 return &deque->data[deque->front++ & (deque->capacity - 1)]; \
129 /* Adds and returns the address of a new element at the back of \
130 DEQUE, which must not be full. The caller is responsible for \
131 assigning a value to the returned element. */ \
132 static inline ELEMENT_TYPE * \
133 NAME##_push_back (struct NAME *deque) \
135 assert (!NAME##_is_full (deque)); \
136 return &deque->data[--deque->back & (deque->capacity - 1)]; \
139 /* Pops the front element off DEQUE (which must not be empty) and \
140 returns its address. The element may be reused the next time \
141 an element is pushed into DEQUE or when DEQUE is expanded. */ \
142 static inline ELEMENT_TYPE * \
143 NAME##_pop_front (struct NAME *deque) \
145 assert (!NAME##_is_empty (deque)); \
146 return &deque->data[--deque->front & (deque->capacity - 1)]; \
149 /* Pops the back element off DEQUE (which must not be empty) and \
150 returns its address. The element may be reused the next time \
151 an element is pushed into DEQUE or when DEQUE is expanded. */ \
152 static inline ELEMENT_TYPE * \
153 NAME##_pop_back (struct NAME *deque) \
155 assert (!NAME##_is_empty (deque)); \
156 return &deque->data[deque->back++ & (deque->capacity - 1)]; \
159 /* Expands DEQUE, doubling its capacity. */ \
161 NAME##_expand (struct NAME *deque) \
163 struct NAME old_deque = *deque; \
164 NAME##_init (deque, deque->capacity * 2); \
165 while (!NAME##_is_empty (&old_deque)) \
166 *NAME##_push_front (deque) = *NAME##_pop_back (&old_deque); \
167 free (old_deque.data); \
170 #endif /* libpspp/deque.h */