1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 /* Bitmap, implemented as a balanced binary tree.
18
19 Each operation has O(lg N) cost, where N is the number of
20 contiguous regions of 1-bits in the bitmap. Also, a cache
21 reduces the second and subsequent containment tests within a
22 single contiguous region to O(1). */
23
24 #ifndef LIBPSPP_RANGE_SET_H
25 #define LIBPSPP_RANGE_SET_H
26
27 #include <stdbool.h>
28 #include "libpspp/bt.h"
29 #include "libpspp/cast.h"
30
31 /* A set of ranges. */
32 struct range_set
33 {
34 struct pool *pool; /* Pool for freeing range_set. */
35 struct bt bt; /* Tree of range_set_nodes. */
36
37 /* Cache. */
38 unsigned long int cache_start; /* Start of region. */
39 unsigned long int cache_end; /* One past end of region. */
40 bool cache_value; /* Is the region in the set? */
41 };
42
43 /* A node in the range set. */
44 struct range_set_node
45 {
46 struct bt_node bt_node; /* Binary tree node. */
47 unsigned long int start; /* Start of region. */
48 unsigned long int end; /* One past end of region. */
49 };
50
51 struct range_set *range_set_create (void);
52 struct range_set *range_set_create_pool (struct pool *);
53 struct range_set *range_set_clone (const struct range_set *, struct pool *);
54 void range_set_destroy (struct range_set *);
55
56 void range_set_set1 (struct range_set *,
57 unsigned long int start, unsigned long int width);
58 void range_set_set0 (struct range_set *,
59 unsigned long int start, unsigned long int width);
60 bool range_set_allocate (struct range_set *, unsigned long int request,
61 unsigned long int *start, unsigned long int *width);
62 bool range_set_allocate_fully (struct range_set *, unsigned long int request,
63 unsigned long int *start);
64 bool range_set_contains (const struct range_set *, unsigned long int position);
65 unsigned long int range_set_scan (const struct range_set *,
66 unsigned long int start);
67
68 static inline bool range_set_is_empty (const struct range_set *);
69
70 #define RANGE_SET_FOR_EACH(NODE, RANGE_SET) \
71 for ((NODE) = range_set_first (RANGE_SET); \
72 (NODE) != NULL; \
73 (NODE) = range_set_next (RANGE_SET, NODE))
74
75 static inline const struct range_set_node *range_set_first (
76 const struct range_set *);
77 static inline const struct range_set_node *range_set_next (
78 const struct range_set *, const struct range_set_node *);
79 static inline const struct range_set_node *range_set_last (
80 const struct range_set *);
81 static inline const struct range_set_node *range_set_prev (
82 const struct range_set *, const struct range_set_node *);
83 static inline unsigned long int range_set_node_get_start (
84 const struct range_set_node *);
85 static inline unsigned long int range_set_node_get_end (
86 const struct range_set_node *);
87 static inline unsigned long int range_set_node_get_width (
88 const struct range_set_node *);
89
90 /* Inline functions. */
91
92 static inline struct range_set_node *range_set_node_from_bt__ (
93 const struct bt_node *);
94 static inline struct range_set_node *range_set_next__ (
95 const struct range_set *, const struct range_set_node *);
96 static inline struct range_set_node *range_set_first__ (
97 const struct range_set *);
98 static inline struct range_set_node *range_set_prev__ (
99 const struct range_set *, const struct range_set_node *);
100 static inline struct range_set_node *range_set_last__ (
101 const struct range_set *);
102
103 /* Returns true if RS contains no 1-bits, false otherwise. */
104 static inline bool
range_set_is_empty(const struct range_set * rs)105 range_set_is_empty (const struct range_set *rs)
106 {
107 return bt_count (&rs->bt) == 0;
108 }
109
110 /* Returns the node representing the first contiguous region of
111 1-bits in RS, or a null pointer if RS is empty.
112 Any call to range_set_set1, range_set_set0, or
113 range_set_allocate invalidates the returned node. */
114 static inline const struct range_set_node *
range_set_first(const struct range_set * rs)115 range_set_first (const struct range_set *rs)
116 {
117 return range_set_first__ (rs);
118 }
119
120 /* If NODE is nonnull, returns the node representing the next
121 contiguous region of 1-bits in RS following NODE, or a null
122 pointer if NODE is the last region in RS.
123 If NODE is null, returns the first region in RS, as for
124 range_set_first.
125 Any call to range_set_set1, range_set_set0, or
126 range_set_allocate invalidates the returned node. */
127 static inline const struct range_set_node *
range_set_next(const struct range_set * rs,const struct range_set_node * node)128 range_set_next (const struct range_set *rs, const struct range_set_node *node)
129 {
130 return (node != NULL
131 ? range_set_next__ (rs, CONST_CAST (struct range_set_node *, node))
132 : range_set_first__ (rs));
133 }
134
135 /* Returns the node representing the last contiguous region of
136 1-bits in RS, or a null pointer if RS is empty.
137 Any call to range_set_set1, range_set_set0, or
138 range_set_allocate invalidates the returned node. */
139 static inline const struct range_set_node *
range_set_last(const struct range_set * rs)140 range_set_last (const struct range_set *rs)
141 {
142 return range_set_last__ (rs);
143 }
144
145 /* If NODE is nonnull, returns the node representing the previous
146 contiguous region of 1-bits in RS following NODE, or a null
147 pointer if NODE is the first region in RS.
148 If NODE is null, returns the last region in RS, as for
149 range_set_last.
150 Any call to range_set_set1, range_set_set0, or
151 range_set_allocate invalidates the returned node. */
152 static inline const struct range_set_node *
range_set_prev(const struct range_set * rs,const struct range_set_node * node)153 range_set_prev (const struct range_set *rs, const struct range_set_node *node)
154 {
155 return (node != NULL
156 ? range_set_prev__ (rs, CONST_CAST (struct range_set_node *, node))
157 : range_set_last__ (rs));
158 }
159
160 /* Returns the position of the first 1-bit in NODE. */
161 static inline unsigned long int
range_set_node_get_start(const struct range_set_node * node)162 range_set_node_get_start (const struct range_set_node *node)
163 {
164 return node->start;
165 }
166
167 /* Returns one past the position of the last 1-bit in NODE. */
168 static inline unsigned long int
range_set_node_get_end(const struct range_set_node * node)169 range_set_node_get_end (const struct range_set_node *node)
170 {
171 return node->end;
172 }
173
174 /* Returns the number of contiguous 1-bits in NODE. */
175 static inline unsigned long int
range_set_node_get_width(const struct range_set_node * node)176 range_set_node_get_width (const struct range_set_node *node)
177 {
178 return node->end - node->start;
179 }
180
181 /* Internal helper functions. */
182
183 /* Returns the range_set_node corresponding to the given
184 BT_NODE. Returns a null pointer if BT_NODE is null. */
185 static inline struct range_set_node *
range_set_node_from_bt__(const struct bt_node * bt_node)186 range_set_node_from_bt__ (const struct bt_node *bt_node)
187 {
188 return bt_node ? BT_DATA (bt_node, struct range_set_node, bt_node) : NULL;
189 }
190
191 /* Returns the next range_set_node in RS after NODE,
192 or a null pointer if NODE is the last node in RS. */
193 static inline struct range_set_node *
range_set_next__(const struct range_set * rs,const struct range_set_node * node)194 range_set_next__ (const struct range_set *rs,
195 const struct range_set_node *node)
196 {
197 return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
198 }
199
200 /* Returns the first range_set_node in RS,
201 or a null pointer if RS is empty. */
202 static inline struct range_set_node *
range_set_first__(const struct range_set * rs)203 range_set_first__ (const struct range_set *rs)
204 {
205 return range_set_node_from_bt__ (bt_first (&rs->bt));
206 }
207
208 /* Returns the previous range_set_node in RS after NODE,
209 or a null pointer if NODE is the first node in RS. */
210 static inline struct range_set_node *
range_set_prev__(const struct range_set * rs,const struct range_set_node * node)211 range_set_prev__ (const struct range_set *rs,
212 const struct range_set_node *node)
213 {
214 return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
215 }
216
217 /* Returns the last range_set_node in RS,
218 or a null pointer if RS is empty. */
219 static inline struct range_set_node *
range_set_last__(const struct range_set * rs)220 range_set_last__ (const struct range_set *rs)
221 {
222 return range_set_node_from_bt__ (bt_last (&rs->bt));
223 }
224
225 #endif /* libpspp/range-set.h */
226