1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009 Free Software Foundation, Inc.
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.
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.
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/>. */
17 /* Bitmap, implemented as a balanced binary tree.
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). */
24 #ifndef LIBPSPP_RANGE_SET_H
25 #define LIBPSPP_RANGE_SET_H
28 #include <libpspp/bt.h>
30 /* A set of ranges. */
33 struct pool *pool; /* Pool for freeing range_set. */
34 struct bt bt; /* Tree of range_set_nodes. */
37 unsigned long int cache_start; /* Start of region. */
38 unsigned long int cache_end; /* One past end of region. */
39 bool cache_value; /* Is the region in the set? */
42 /* A node in the range set. */
45 struct bt_node bt_node; /* Binary tree node. */
46 unsigned long int start; /* Start of region. */
47 unsigned long int end; /* One past end of region. */
50 struct range_set *range_set_create (void);
51 struct range_set *range_set_create_pool (struct pool *);
52 struct range_set *range_set_clone (const struct range_set *, struct pool *);
53 void range_set_destroy (struct range_set *);
55 void range_set_insert (struct range_set *,
56 unsigned long int start, unsigned long int width);
57 void range_set_delete (struct range_set *,
58 unsigned long int start, unsigned long int width);
59 bool range_set_allocate (struct range_set *, unsigned long int request,
60 unsigned long int *start, unsigned long int *width);
61 bool range_set_allocate_fully (struct range_set *, unsigned long int request,
62 unsigned long int *start);
63 bool range_set_contains (const struct range_set *, unsigned long int position);
64 unsigned long int range_set_scan (const struct range_set *,
65 unsigned long int start);
67 static inline bool range_set_is_empty (const struct range_set *);
69 static inline const struct range_set_node *range_set_first (
70 const struct range_set *);
71 static inline const struct range_set_node *range_set_next (
72 const struct range_set *, const struct range_set_node *);
73 static inline unsigned long int range_set_node_get_start (
74 const struct range_set_node *);
75 static inline unsigned long int range_set_node_get_end (
76 const struct range_set_node *);
77 static inline unsigned long int range_set_node_get_width (
78 const struct range_set_node *);
80 /* Inline functions. */
82 static inline struct range_set_node *range_set_node_from_bt__ (
83 const struct bt_node *);
84 static inline struct range_set_node *range_set_next__ (
85 const struct range_set *, const struct range_set_node *);
86 static inline struct range_set_node *range_set_first__ (
87 const struct range_set *);
89 /* Returns true if RS contains no 1-bits, false otherwise. */
91 range_set_is_empty (const struct range_set *rs)
93 return bt_count (&rs->bt) == 0;
96 /* Returns the node representing the first contiguous region of
97 1-bits in RS, or a null pointer if RS is empty.
98 Any call to range_set_insert, range_set_delete, or
99 range_set_allocate invalidates the returned node. */
100 static inline const struct range_set_node *
101 range_set_first (const struct range_set *rs)
103 return range_set_first__ (rs);
106 /* If NODE is nonnull, returns the node representing the next
107 contiguous region of 1-bits in RS following NODE, or a null
108 pointer if NODE is the last region in RS.
109 If NODE is null, returns the first region in RS, as for
111 Any call to range_set_insert, range_set_delete, or
112 range_set_allocate invalidates the returned node. */
113 static inline const struct range_set_node *
114 range_set_next (const struct range_set *rs, const struct range_set_node *node)
117 ? range_set_next__ (rs, (struct range_set_node *) node)
118 : range_set_first__ (rs));
121 /* Returns the position of the first 1-bit in NODE. */
122 static inline unsigned long int
123 range_set_node_get_start (const struct range_set_node *node)
128 /* Returns one past the position of the last 1-bit in NODE. */
129 static inline unsigned long int
130 range_set_node_get_end (const struct range_set_node *node)
135 /* Returns the number of contiguous 1-bits in NODE. */
136 static inline unsigned long int
137 range_set_node_get_width (const struct range_set_node *node)
139 return node->end - node->start;
142 /* Internal helper functions. */
144 /* Returns the range_set_node corresponding to the given
145 BT_NODE. Returns a null pointer if BT_NODE is null. */
146 static inline struct range_set_node *
147 range_set_node_from_bt__ (const struct bt_node *bt_node)
149 return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
152 /* Returns the next range_set_node in RS after NODE,
153 or a null pointer if NODE is the last node in RS. */
154 static inline struct range_set_node *
155 range_set_next__ (const struct range_set *rs,
156 const struct range_set_node *node)
158 return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
161 /* Returns the first range_set_node in RS,
162 or a null pointer if RS is empty. */
163 static inline struct range_set_node *
164 range_set_first__ (const struct range_set *rs)
166 return range_set_node_from_bt__ (bt_first (&rs->bt));
169 #endif /* libpspp/range-set.h */