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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
/* PSPP - a program for statistical analysis.
Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Bitmap, implemented as a balanced binary tree.
Each operation has O(lg N) cost, where N is the number of
contiguous regions of 1-bits in the bitmap. Also, a cache
reduces the second and subsequent containment tests within a
single contiguous region to O(1). */
#ifndef LIBPSPP_RANGE_SET_H
#define LIBPSPP_RANGE_SET_H
#include <stdbool.h>
#include "libpspp/bt.h"
#include "libpspp/cast.h"
/* A set of ranges. */
struct range_set
{
struct pool *pool; /* Pool for freeing range_set. */
struct bt bt; /* Tree of range_set_nodes. */
/* Cache. */
unsigned long int cache_start; /* Start of region. */
unsigned long int cache_end; /* One past end of region. */
bool cache_value; /* Is the region in the set? */
};
/* A node in the range set. */
struct range_set_node
{
struct bt_node bt_node; /* Binary tree node. */
unsigned long int start; /* Start of region. */
unsigned long int end; /* One past end of region. */
};
struct range_set *range_set_create (void);
struct range_set *range_set_create_pool (struct pool *);
struct range_set *range_set_clone (const struct range_set *, struct pool *);
void range_set_destroy (struct range_set *);
void range_set_set1 (struct range_set *,
unsigned long int start, unsigned long int width);
void range_set_set0 (struct range_set *,
unsigned long int start, unsigned long int width);
bool range_set_allocate (struct range_set *, unsigned long int request,
unsigned long int *start, unsigned long int *width);
bool range_set_allocate_fully (struct range_set *, unsigned long int request,
unsigned long int *start);
bool range_set_contains (const struct range_set *, unsigned long int position);
unsigned long int range_set_scan (const struct range_set *,
unsigned long int start);
static inline bool range_set_is_empty (const struct range_set *);
#define RANGE_SET_FOR_EACH(NODE, RANGE_SET) \
for ((NODE) = range_set_first (RANGE_SET); \
(NODE) != NULL; \
(NODE) = range_set_next (RANGE_SET, NODE))
static inline const struct range_set_node *range_set_first (
const struct range_set *);
static inline const struct range_set_node *range_set_next (
const struct range_set *, const struct range_set_node *);
static inline const struct range_set_node *range_set_last (
const struct range_set *);
static inline const struct range_set_node *range_set_prev (
const struct range_set *, const struct range_set_node *);
static inline unsigned long int range_set_node_get_start (
const struct range_set_node *);
static inline unsigned long int range_set_node_get_end (
const struct range_set_node *);
static inline unsigned long int range_set_node_get_width (
const struct range_set_node *);
/* Inline functions. */
static inline struct range_set_node *range_set_node_from_bt__ (
const struct bt_node *);
static inline struct range_set_node *range_set_next__ (
const struct range_set *, const struct range_set_node *);
static inline struct range_set_node *range_set_first__ (
const struct range_set *);
static inline struct range_set_node *range_set_prev__ (
const struct range_set *, const struct range_set_node *);
static inline struct range_set_node *range_set_last__ (
const struct range_set *);
/* Returns true if RS contains no 1-bits, false otherwise. */
static inline bool
range_set_is_empty (const struct range_set *rs)
{
return bt_count (&rs->bt) == 0;
}
/* Returns the node representing the first contiguous region of
1-bits in RS, or a null pointer if RS is empty.
Any call to range_set_set1, range_set_set0, or
range_set_allocate invalidates the returned node. */
static inline const struct range_set_node *
range_set_first (const struct range_set *rs)
{
return range_set_first__ (rs);
}
/* If NODE is nonnull, returns the node representing the next
contiguous region of 1-bits in RS following NODE, or a null
pointer if NODE is the last region in RS.
If NODE is null, returns the first region in RS, as for
range_set_first.
Any call to range_set_set1, range_set_set0, or
range_set_allocate invalidates the returned node. */
static inline const struct range_set_node *
range_set_next (const struct range_set *rs, const struct range_set_node *node)
{
return (node != NULL
? range_set_next__ (rs, CONST_CAST (struct range_set_node *, node))
: range_set_first__ (rs));
}
/* Returns the node representing the last contiguous region of
1-bits in RS, or a null pointer if RS is empty.
Any call to range_set_set1, range_set_set0, or
range_set_allocate invalidates the returned node. */
static inline const struct range_set_node *
range_set_last (const struct range_set *rs)
{
return range_set_last__ (rs);
}
/* If NODE is nonnull, returns the node representing the previous
contiguous region of 1-bits in RS following NODE, or a null
pointer if NODE is the first region in RS.
If NODE is null, returns the last region in RS, as for
range_set_last.
Any call to range_set_set1, range_set_set0, or
range_set_allocate invalidates the returned node. */
static inline const struct range_set_node *
range_set_prev (const struct range_set *rs, const struct range_set_node *node)
{
return (node != NULL
? range_set_prev__ (rs, CONST_CAST (struct range_set_node *, node))
: range_set_last__ (rs));
}
/* Returns the position of the first 1-bit in NODE. */
static inline unsigned long int
range_set_node_get_start (const struct range_set_node *node)
{
return node->start;
}
/* Returns one past the position of the last 1-bit in NODE. */
static inline unsigned long int
range_set_node_get_end (const struct range_set_node *node)
{
return node->end;
}
/* Returns the number of contiguous 1-bits in NODE. */
static inline unsigned long int
range_set_node_get_width (const struct range_set_node *node)
{
return node->end - node->start;
}
/* Internal helper functions. */
/* Returns the range_set_node corresponding to the given
BT_NODE. Returns a null pointer if BT_NODE is null. */
static inline struct range_set_node *
range_set_node_from_bt__ (const struct bt_node *bt_node)
{
return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
}
/* Returns the next range_set_node in RS after NODE,
or a null pointer if NODE is the last node in RS. */
static inline struct range_set_node *
range_set_next__ (const struct range_set *rs,
const struct range_set_node *node)
{
return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
}
/* Returns the first range_set_node in RS,
or a null pointer if RS is empty. */
static inline struct range_set_node *
range_set_first__ (const struct range_set *rs)
{
return range_set_node_from_bt__ (bt_first (&rs->bt));
}
/* Returns the previous range_set_node in RS after NODE,
or a null pointer if NODE is the first node in RS. */
static inline struct range_set_node *
range_set_prev__ (const struct range_set *rs,
const struct range_set_node *node)
{
return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
}
/* Returns the last range_set_node in RS,
or a null pointer if RS is empty. */
static inline struct range_set_node *
range_set_last__ (const struct range_set *rs)
{
return range_set_node_from_bt__ (bt_last (&rs->bt));
}
#endif /* libpspp/range-set.h */
|
